K近邻法

       K近邻法：假定存在已标记的训练数据集，分类时对新的实例根据其K个最近邻的训练实例的类别，通过多数表决等分类决策规则进行预测。

       k近邻不具有显示学习的过程，是“懒惰学习”（lazy learning）。分类器不需要使用训练集进行训练。实际上是利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。

（标注：Lazy learning懒惰学习：训练阶段仅仅把样本保存起来，无训练时间开销，收到测试样本再进行处理；

           Eager laarning急切学习：训练阶段就对样本学习处理的方法。）

1  K近邻分类法的三个基本要素

     K近邻分类法的三个基本要素为：k值的选择、距离度量、分类决策规则。当三个要素确定后，对于任何一个新的输入实例，它所属的类唯一的确定。

1.1 k值的选择

      K值的选择会对k近邻法的结果产生较大的影响。

    当k较小时：

           优点：学习的近似误差会减小。

        缺点：预测结果会对近邻的实例点非常敏感，k值的减小就意味着整体模型变得复杂，容易发生过拟合。

    当k较大时：

           优点：减小学习的估计误差。

        缺点：学习的近似误差会增大，k值的增大意味着整体的模型变得简单，过于简单会完全忽略训练实例中的大量有用信息。

      K值一般取一个较小的值，通常采用交叉验证法来选取最优的k值。

1.2 距离度量

       特征空间中的两个实例点的距离是两个实例点相似程度的反映。不同的距离度量方式所确定的最近邻点是不同的。K近邻的一般使用的是欧式距离，但也可以是其他距离。

          Lp距离：

                                             （p>=1）

              P=2  欧式距离

              P=1  曼哈顿距离

              P= 各个坐标距离的最大值

1.3 分类决策规则

          K近邻中的分类决策规则一般是多数表决，即由输入实例的k个最近邻中的多数类决定输入实例的类。

          多数表决规则等价于经验风险最小化。

2  K近邻的一个实现方法：kd树

      问题：如何对训练数据进行快速k近邻搜索

      最简单的实现方法：线性扫描。缺点：当训练集很大时，计算非常耗时。所以需要特殊的存储结构存储训练数据：kd树，以减少计算距离的次数。

因为实际数据一般都会呈现簇状的聚类形态，因此我们想到建立数据索引，然后再进行快速匹配。索引树是一种树结构索引方法，其基本思想是对搜索空间进行层次划分。若划分空间没有重叠，其代表就是k-d树。

         k-d树（k-dimensional tree），是一种分割k维数据空间的数据结构。本质上是二叉树，表示对k维空间的一个划分，构成一系列的k维超矩形区域。

      方法：依次选择坐标轴对空间切分，选在一个坐标轴并在此坐标轴上选定一个切分点，根据选定的切分点垂直于选定的切分点将当前矩形区域切分（若选择中位数为切分点，这样得到的kd树是平衡的），直到每一个子区域内没有实例点为止。

      例：6个二维数据点{（2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}，数据点位于二维空间内（如图1中黑点所示）。k-d树算法就是要确定图1中这些分割空间的分割线（多维空间即为分割平面，一般为超平面）。

        分析：首先选择x轴，6个点的x坐标的中位数为7，以x=7划分为左右两个子矩形。选择y轴，左矩形以y=4划分，右矩形以y=6划分，如此递归，直到划分如图1所示并生成如图2所示的k-d树。

         搜索以最近邻为例：

      查找点为（2，4.5）。从（7,2）开始，横坐标2小于7进入左子树（5,4），4.5大于4进入右子树（4,7），形成搜索路径<（7,2），（5,4），（4,7）>，取（4,7）为当前最近邻点，计算其与目标查找点的距离为3.202。然后回溯到（5,4），计算其与查找点之间的距离为3.041。以（2，4.5）为圆心，以3.041为半径作圆，可见该圆和y = 4超平面交割，所以需要进入（5,4）左子空间进行查找。此时需将（2,3）节点加入搜索路径中得<（7,2），（2,3）>。回溯至（2,3）叶子节点，（2,3）距离（2,4.5）比（5,4）要近，所以最近邻点更新为（2，3），最近距离更新为1.5。回溯至（7,2），以（2,4.5）为圆心1.5为半径作圆，并不和x = 7分割超平面交割。至此，搜索路径回溯完。返回最近邻点（2,3），最近距离1.5。

        Kd树搜索的平均时间复杂度是O（logN），kd树更适合于训练实例数远大于空间维数，当其接近时效率下降，几乎接近于线性扫描。

3  k近邻法用于回归

        KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成反比。　

参考

百度百科：k近邻算法 

http://baike.baidu.com/link?url=niNGb6_6PCMqgofzhI8Ku1MtGOjJY2tkK3D6eUq8f2Ws-G0VWAWeexRt-m42TjmvJptskDtBE2BYKLqE-yHlHK

百度百科：Kd树：

http://baike.baidu.com/link?url=B2eikDcSHrYQw2pHkEI0A0kVrNywu7pfCTPwlYvCADvW5cupT7-rIyUNu_LPOApA-PClHiSOefnjbYUA6JomH_

李航  《统计学习方法》

博客：http://blog.csdn.net/likika2012/article/details/39619687

K近邻分类法