数据挖掘算法—K近邻算法

控制思维

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

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

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

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

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

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


二、 k- 近邻法
基于实例的学习方法中最基本的是 k - 近邻算法。这个算法假定所有的实例对应于 n维欧氏空间Â n 中的点。一个实例的最近邻是根据标准欧氏距离定义的。更精确地讲，把任意的实例 x 表示为下面的特征向量：
< a 1 ( x ) ， a 2 ( x )，...， a n ( x )>
其中 a r ( x ) 表示实例 x 的第 r 个属性值。那么两个实例 x i 和 x j 间的距离定义为 d (x i , x j ) ，其中：

说明：
1、在最近邻学习中，目标函数值可以为离散值也可以为实值。
2、我们先考虑学习以下形式的离散目标函数  。其中 V 是有限集合 { v1， ... 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
分类算法：
给定一个要分类的查询实例 x q
在 training _ examples 中选出最靠近 x q 的 k 个实例，并用 x 1.... x k 表示
返回

其中如果 a = b 那么 d ( a , b )=1 ，否则 d ( a , b )=0 。

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

图解说明： 左图画出了一系列的正反训练样例和一个要分类的查询实例 x q 。 1- 近邻算法把 xq 分类为正例，然而 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、问题二： 应用 k - 近邻算法的另外一个实践问题是如何建立高效的索引。因为这个算法推迟所有的处理，直到接收到一个新的查询，所以处理每个新查询可能需要大量的计算。

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