k-近邻算法是基于实例的学习方法中最基本的，先介绍基于实例学习的相关概念。

一、基于实例的学习。

1、已知一系列的训练样例，很多学习方法为目标函数建立起明确的一般化描述；但与此不同，基于实例的学习方法只是简单地把训练样例存储起来。

从这些实例中泛化的工作被推迟到必须分类新的实例时。每当学习器遇到一个新的查询实例，它分析这个新实例与以前存储的实例的关系，并据此把一个目标函数值赋给新实例。

2、基于实例的方法可以为不同的待分类查询实例建立不同的目标函数逼近。事实上，很多技术只建立目标函数的局部逼近，将其应用于与新查询实例邻近的实例，而从不建立在整个实例空间上都表现良好的逼近。当目标函数很复杂，但它可用不太复杂的局部逼近描述时，这样做有显著的优势。

3、基于实例方法的不足：

     （1）分类新实例的开销可能很大。这是因为几乎所有的计算都发生在分类时，而不是在第一次遇到训练样例时。所以，如何有效地索引训练样例，以减少查询时所需计算是一个重要的实践问题。

    （2）当从存储器中检索相似的训练样例时，它们一般考虑实例的所有属性。如果目标概念仅依赖于很多属性中的几个时，那么真正最“相似”的实例之间很可能相距甚远。

二、k-近邻法

基于实例的学习方法中最基本的是k-近邻算法。这个算法假定所有的实例对应于n维欧氏空间Âⁿ中的点。一个实例的最近邻是根据标准欧氏距离定义的。更精确地讲，把任意的实例x表示为下面的特征向量：

                                               <a₁(x)，a₂(x)，...，a_n(x)>

其中a_r(x)表示实例x的第r个属性值。那么两个实例x_i和x_j间的距离定义为d(x_i,x_j)，其中：

说明：

1、在最近邻学习中，目标函数值可以为离散值也可以为实值。

2、我们先考虑学习以下形式的离散目标函数。其中V是有限集合{v_1，...v_s}。下表给出了逼近离散目标函数的k-近邻算法。

3、正如下表中所指出的，这个算法的返回值f'(x_q)为对f(x_q)的估计，它就是距离x_q最近的k个训练样例中最普遍的f值。

4、如果我们选择k=1，那么“1-近邻算法”就把f(x_i)赋给(x_q)，其中x_i是最靠近x_q的训练实例。对于较大的k值，这个算法返回前k个最靠近的训练实例中最普遍的f值。

逼近离散值函数f: Â^n_V的k-近邻算法

训练算法：    对于每个训练样例<x,f(x)>，把这个样例加入列表training_examples 分类算法：    给定一个要分类的查询实例xq    在training_examples中选出最靠近xq的k个实例，并用x1....xk表示   返回                           其中如果a=b那么d(a,b)=1，否则d(a,b)=0。

 

下图图解了一种简单情况下的k-近邻算法，在这里实例是二维空间中的点，目标函数具有布尔值。正反训练样例用“+”和“-”分别表示。图中也画出了一个查询点x_q。注意在这幅图中，1-近邻算法把x_q分类为正例，然而5-近邻算法把x_q分类为反例。

 

图解说明：左图画出了一系列的正反训练样例和一个要分类的查询实例x_q。1-近邻算法把x_q分类为正例，然而5-近邻算法把x_q分类为反例。

                    右图是对于一个典型的训练样例集合1-近邻算法导致的决策面。围绕每个训练样例的凸多边形表示最靠近这个点的实例空间（即这个空间中的实例会被1-近邻算法赋予该训练样例所属的分类）。

 

对前面的k-近邻算法作简单的修改后，它就可被用于逼近连续值的目标函数。为了实现这一点，我们让算法计算k个最接近样例的平均值，而不是计算其中的最普遍的值。更精确地讲，为了逼近一个实值目标函数，我们只要把算法中的公式替换为：

                      

三、距离加权最近邻算法

对k-近邻算法的一个显而易见的改进是对k个近邻的贡献加权，根据它们相对查询点x_q的距离，将较大的权值赋给较近的近邻。

例如，在上表逼近离散目标函数的算法中，我们可以根据每个近邻与x_q的距离平方的倒数加权这个近邻的“选举权”。

方法是通过用下式取代上表算法中的公式来实现：

                               

其中

                              

 

为了处理查询点x_q恰好匹配某个训练样例x_i，从而导致分母为0的情况，我们令这种情况下的f '(x_q)等于f(x_i)。如果有多个这样的训练样例，我们使用它们中占多数的分类。

我们也可以用类似的方式对实值目标函数进行距离加权，只要用下式替换上表的公式：

 

           

其中w_i的定义与之前公式中相同。

注意这个公式中的分母是一个常量，它将不同权值的贡献归一化（例如，它保证如果对所有的训练样例x_i，f(x_i)=c，那么(x_q)<--c）。

注意以上k-近邻算法的所有变体都只考虑k个近邻以分类查询点。如果使用按距离加权，那么允许所有的训练样例影响x_q的分类事实上没有坏处，因为非常远的实例对(x_q)的影响很小。考虑所有样例的惟一不足是会使分类运行得更慢。如果分类一个新的查询实例时考虑所有的训练样例，我们称此为全局（global）法。如果仅考虑最靠近的训练样例，我们称此为局部（local）法。

四、对k-近邻算法的说明

按距离加权的k-近邻算法是一种非常有效的归纳推理方法。它对训练数据中的噪声有很好的鲁棒性，而且当给定足够大的训练集合时它也非常有效。注意通过取k个近邻的加权平均，可以消除孤立的噪声样例的影响。

 

1、问题一：近邻间的距离会被大量的不相关属性所支配。

          应用k-近邻算法的一个实践问题是，实例间的距离是根据实例的所有属性（也就是包含实例的欧氏空间的所有坐标轴）计算的。这与那些只选择全部实例属性的一个子集的方法不同，例如决策树学习系统。

          比如这样一个问题：每个实例由20个属性描述，但在这些属性中仅有2个与它的分类是有关。在这种情况下，这两个相关属性的值一致的实例可能在这个20维的实例空间中相距很远。结果，依赖这20个属性的相似性度量会误导k-近邻算法的分类。近邻间的距离会被大量的不相关属性所支配。这种由于存在很多不相关属性所导致的难题，有时被称为维度灾难（curse of dimensionality）。最近邻方法对这个问题特别敏感。

2、解决方法：当计算两个实例间的距离时对每个属性加权。

      这相当于按比例缩放欧氏空间中的坐标轴，缩短对应于不太相关属性的坐标轴，拉长对应于更相关的属性的坐标轴。每个坐标轴应伸展的数量可以通过交叉验证的方法自动决定。

 

3、问题二：应用k-近邻算法的另外一个实践问题是如何建立高效的索引。因为这个算法推迟所有的处理，直到接收到一个新的查询，所以处理每个新查询可能需要大量的计算。

4、解决方法：目前已经开发了很多方法用来对存储的训练样例进行索引，以便在增加一定存储开销情况下更高效地确定最近邻。一种索引方法是kd-tree（Bentley 1975；Friedman et al. 1977），它把实例存储在树的叶结点内，邻近的实例存储在同一个或附近的结点内。通过测试新查询x_q的选定属性，树的内部结点把查询x_q排列到相关的叶结点。

python和java版本代码讲解和下载