k近邻算法的实现
一.k近邻算法的内容
k近邻算法（k-nearest neighbor,k-NN）
作用：用来基本分类和实现回归
内容：给定一个训练数据集，对新的输入实例，在整个训练数据集中找到与该输入实例最近的k个实例，这k个实例的最多数属于哪个类，就把该输入实例分为这个类。
三要素：1.距离度量:何为最近？距离最近，如何确定距离最近？生活中最常使用的是欧式距离，另一个常用的是曼哈顿距离，它们都是拉式距离的特例。
2.k值的选择：最近的k个实例，k为多大？如何确定一个相对的k值使分类误差更小？当我们选择一个较小k值时，预测结果会对近邻的实例点非常敏感，如果该邻近点恰恰是噪声，预测就会出错。
当选择一个较大的k值时，这时与实例较远的训练实例也会对预测起作用，使预测发生错误。
如果k=N，都将输入实例分为整个训练实例中最多的类，此时模型过于简单。
突出强调的是，k值一般取一个比较小的值，通常采用交叉验证法来选取最优的k值。
3.分类决策规则：这里往往采用大自然最基本规律，多数表决，也就是这k个邻近训练实例中多数类决定该输入实例的类。
二.k邻近算法的实现：kd树
算法思想有了，如何实现呢？如何快速找到这个实例在一个训练集中的k个邻近实例呢？
最简单的方法是一个一个扫描，即线性扫描（linearscan），这要计算输入实例与每一个训练实例的距离，当训练集非常庞大时，将会非常耗时，故这种方法不可取。
下面介绍一种kd树（kd tree）方法，使用特殊的树型存储结构来存储数据，以减少计算距离的次数。
1.构造kd树
kd树是对所有训练集中的实例点进行存储以便对其进行快速检索的树形数据结构，其为二叉树。构造kd树相当于不断地用垂直于坐标轴的平面将k维空间划分，kd树的每个结点都对应于一个k维超矩形区域。kd树的k即为k维空间。
构造kd树思想：a.构造根结点，根结点对应于k维空间包含所有实例点的超矩形区域。
b.在坐标轴上选定一个切分点，对这个超矩形区域进行切分成左右两个子区域，将所有的实例点分到这两个子区域中。
c.再选定切分点，对子区域进行切分，不断递归。
d.直到最终的子区域没有实例时终止。
从中可以看出1.确定切分点是构造kd树的最重要环节；2最终的实例点全落在切分点所在的平面上。
2.构造平衡kd树
一般选择每个区域内所有实例点的中位数为切分点，这样得到的kds树是平衡的。
对深度为m的结点，选择x（i）为切分的坐标轴，其中x（i）为x向量的第i位值，i=m+1；
例 构造平衡kd树
训练集 T=｛（2，3），（5，4），（9，6），（4，7），（8，1），（7，2）｝。
（1）从深度为1开始，选择x（1）为切分的坐标轴，对x（1）排序：2，4，5，7，8，9.中位数为7，(7,2)在此划分平面上。
（2）深度为2时，选择x(2)为划分点，已划分成的左区域有三个点，x(2)分别为3，4，7，选择中位数4进行切分，（5，4）在这个切分平面上；右区域有两个点，x(2)分别为1，6，选择中位数6为切分点，（9，6）落在这个切分平面上。
（3）深度为3时，选择x(1)为划分点。剩下三个点落在各自划分平面上。
整体思想就是如此，kd树示例：
三.搜索kd树
算法：用kd树的最近邻搜索
输入：已构造的kd树；目标点x；
输出：x的最近邻。
（1）在kd树中找出包含目标点x的叶结点：从根结点出发，递归向下访问kd树。若目标点x当前维坐标小于切分点的坐标，则移动到左子结点，否则到右子结点。直到子结点到叶结点为止。
（2）以此叶结点为“当前最近点”。
（3）递归地向上回退，如果该结点保存的实例点比当前最近点距离目标点更近，则以该实例点为“当前最近点”。
检查该结点的父节点的另一个结点区域，以目标点与“当前最近点”间的距离为半径画球，如有有结点存在于这个球内，则该结点为“当前最近点”。如果没有点存在球内，继续向上回退。
（4）当回退到根结点时，搜索结束，“当前最近点”即为x的最近邻点。
例 已知根结点A,树上共有7个存储点，求另一个目标输入点S的最近邻。
a.首先找包含s结点的叶结点D，以D为当前最近邻。
b.真正最近邻一定在以点S为中心通过D的圆内。故返回D的父结点B，在B的另一子结点找在圆内的点，没找到。
c.在B的父结点A的另一子结点中寻找，由于E的坐标，可直接到A的子结点C区域中寻找，寻找到圆内有结点E，且点E比点D更近，成为新的最近邻。接着向上回退，发现回退到根结点A，搜索结束，即结点E即为最邻近点。
k邻近算法整体思想到这里就结束了，先设计算法模型，再构造kd树存储数据以便搜素，最后实现对kd树的搜索，很有意思吧！
参考：李航，《统计学习方法》