k近邻法的原理与实现_试简述k近邻算法,并描述k值选择对算法的结果的影响,假设给定6个二维数据点

一、基本概念

        k近邻法（k-nearest neighbor, k-NN）是一种基本分类与回归方法，由Cover和Hart于1968年提出。分类时，对于新的实例，根据与它最接近的k个训练实例的类别，通过多数表决等方式，进行预测。对于给定的训练集，当k值，距离度量和分类决策规则（统称三要素）确定后，基于k近邻法的模型就已经确定了。所以，它实际上利用训练集对特征向量空间进行划分，并没有显示的学习过程。k近邻法，符合我们基本的认知，即“物以类聚，人以群分”，一件事物的类别通常与它附近的事物具有相似性。

        看一个最简单的例子，当k=1时，即新实例的类别由里它最近的训练实例的类别决定。更一般的，当k>1时，如图1：绿的圆点的类别可能会被预测为红色三角形代表的a类，也可能被预测为蓝色正方形代表的b类。当k=3时，预测为a类，因为红色三角形占2个；当k=5时，预测为b类，因为蓝色正方形占3个。因此，新实例预测的类别会因k值得不同而不同。当k值等于训练集实例的数目时，对于任何新的实例都会被预测为训练集中占多数的那个类别，模型达到最简化，丧失了大部分有用的信息。

（图1 k值的选择）

        另外，距离度量除了常用的欧式距离（Euclidean distance），还可以使用曼哈顿距离（Manhattan distance）。更一般的可以用Lp距离（Lp distance）或闵式距离（Minkowski distance）。

二、算法实现：kd树

        对于给定训练集，当上述三要素（k值、距离度量和分类决策规则）确定后，新实例的类别就已经确定了。实际上，根本不需要学习的过程，分类仅仅只是在训练集上进行搜索，找出最近的k个实例，通过投票法进行预测。一种最简单的实现是线性扫描（linear scan），即计算训练集中每个实例与新实例的距离，找到最近的k个实例。但是，当训练集很大时，这种算法的效率极其低下。这时，就需要我们用一种特殊的结构对数据集进行存储，以方便进行搜索。

（一）kd树的构造

        kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。kd树是二叉树，表示对k维空间的一个划分。构造kd树相当于不断利用垂直于坐标轴的超平面将k维空间划分，构成一些列的k维超矩形区域。设想一个最简单的情况（当k=1时），kd树就退化为二叉搜索树，我们可以以O(logn)的时间复杂度查找数据。

        构造kd树的方法如下：构造根节点，使根结点对应于k维空间中包含所有实例点的超矩形区域；通过下面的递归方法，不断地对k维空间进行划分，生成子节点。在超矩形区域（结点）上选择一个坐标轴和在此坐标轴上的一个切分点，确定一个超平面，这个超平面通过选定的切分点并垂直于选定的坐标轴，将当前超矩形区域划分为左右两个子区域（子结点）；这时，实例被分到两个子区域。重复此过程直到子区域没有实例时终止。在此过程中，将实例保存在相应的结点上。

        这里有两个需