K近邻算法 – 原理


k-NN近邻算法(k-nearest neighbor,k-NN),在1968年由Cover和Hart提出。
k-NN的输入为实例的特征向量,即对应于特征空间的点;输出为实例的类别,可取多类。k-NN是在给定实例类别的训练数据集中,根据新的实例其k个最近邻的训练实例的类别,通过多数表决等方式进行预测新的实例的类别。
k-NN不具有显式的学习过程,利用训练数据集对特征向量空间进行划分,并作为其分类的“模型”。
k-NN是一种用于实现分类回归的非参数方法。k-NN在分类中,输出结果是一个类别标签,在回归中,输出结果是对象的属性值(This value is the average of the values of its k nearest neighbors)。k-NN是一种基于实例的学习(lazy learning,in which generalization beyond the training data is delayed until a query is made to the system)。

K-NN三要素:k值得选择、距离度量、分类决策规则


k近邻算法

直观描述:针对一个给定的训练数据集,对新的输入实例,在训练数据集中找到与该实例对近邻的k个实例,这k个实例的多数属于某个类别,就把该输入实例分类为这个类。
算法

  • 输入:训练数据集 $T = lbrace(x_1,y_1),(x_2,y_2),…,(x_n,y_n)rbrace $,其中$x_i$为实例的特征向量,$y_i$为实例的类别,$y_i∈lbrace c_1,c_2,…,c_k rbrace,i=1,2,…,N$;实例特征向量$x$。
  • 输出:实例x所属的类别C。

(1)根据给定的举例度量方法,在训练集T中找出与x最近邻的k个点,记作邻域$N_k(x)$;
(2)在$N_k(x)$中根据分类决策规则决定x的类别c

k-NN的特殊情形是k=1,称为最近邻算法。


k-NN模型

k-NN模型实际上对应于对数据集特征空间的划分。
模型
当训练集、距离度量、k值和分类决策规则确定后,对任意新的输入实例,确定其唯一的所属类别。相当于将特征空间划分为一些子空间,确定子空间里的每个点所属的类别。


距离度量
特征空间中两个实例点的距离是相似程度的反映。
设特征空间$X$是n维实数向量空间$R^n$,$x_i,x_j∈X$,$x_i=(x_i^{(1)},x_i^{(2)},…,x_i^{(n)})^{T},x_j=(x_j^{(1)},x_j^{(2)},…,x_j^{(n)})^{T}$,$x_i,x_j$的$L_P$距离定义为:
$$
L_P(x_i,x_j)=(sum_{l=1}^{n}|x_i^{(l)}-x_j^{(l)}|^p)^{1/p}
$$

当p=2时,称为欧式距离Euclidean Distance,即:
$$
L_2(x_i,x_j)=(sum_{l=1}^{n}|x_i^{(l)}-x_j^{(l)}|^2)^{1/2}
$$
当p=1时,称为曼哈顿距离,即:
$$
L_1(x_i,x_j)=sum_{l=1}^{n}|x_i^{(l)}-x_j^{(l)}|
$$
当p=∞时,是各个坐标距离的最大值,即:
$$
L_∞(x_i,x_j)=max_l|x_i^{(l)}-x_j^{(l)}|
$$

k-NN对距离度量的定义敏感,可能不同的距离定义所确定的最近邻点是不同的。

注:后续详细讨论数距离度量的方法和实现


k值的选择
k-NN对k值的选择敏感。

若k值较小,即用较少的训练实例进行预测,近似误差会减小,只有与输入实例较近的训练实例才会对预测结果起作用;但缺点是估计误差会增大,预测结果会对近邻的实例点非常敏感。如果近邻点恰巧是噪声,预测则会出错。k值的减小就意味着整体模型变得复杂,容易发生过拟合。
若k值较大,即用较多的训练实例进行预测,优点是可减少学习的估计误差;但缺点是学习的近似误差会增大。与输入实例较远的训练实例也会对预测起作用,使预测发生错误。k值的增大就意味着整体的模型变得简单。

k值一般取一个比较小的数值,通常采用经验和交叉验证法来选取最优的k值。


分类决策规则
分类的决策规则往往是多数表决(majority voting rule),即由输入实例的k个邻近的训练实例中的多数类决定输入实例的类。
如果分类的损失函数为0-1损失函数,分类函数为:
$$f:R^n - lbrace c_1,c_2,…,c_krbrace $$

损失函数:直观的含义就是预测值与真实值的差值

那么误分类的概率是:
$$P(Y≠f(X))=1-P(Y=f(X))$$
对给定的实例$x∈X$,其最近邻的k个训练实例点构成集合$N_k(x)$,如果$N_k(x)$区域的类别是$C_j$,那么误分类概率是:
$$frac{1}{k}sum{I(y_i≠c_j)}=1-frac{1}{k}sum{I(y_i=c_j)}$$
要使误分类概率最小即经验风险最小,就要使$frac{1}{k}sum{I(y_i=c_j)}$最大,所以多数表决规则等价于经验风险最小化。

经验风险:直观的含义就是训练误差


k-NN实现:kd树

k-NN算法主要的问题是如何对训练数据进行快速k近邻搜索。在特征空间的维数较大以及训练数据量较大时尤其重要。
k-NN最简单的实现方法是现行扫描(linear scan),计算输入实例与每一个训练实例的举例。优点是简单直观,但缺点更明显,计算非常耗时,方法不可取。

为提高k-NN搜索的效率,使用特殊的结构存储训练数据,以减少计算距离的次数。接下来介绍kd树方法


构造kd树

kd树概括的讲是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。kd树是二叉树,表示对k维空间的一个划分(partition)。
构造kd树相当于不断用垂直于坐标轴的超平面将k维空间切分,构成一系列的k维超巨型区域,kd树的每个节点对应于一个k维超巨型区域。

构造kd树的方法:

  • 构造根节点,使根结点对应于k维空间中包含所有实例点的超矩形区域;
  • 通过下面的递归,不断地对k维空间进行切分,生成子结点;
  • 在超矩形区域(结点)上选择一个坐标轴和在此坐标轴上的一个切分点,确定一个超平面,这个超平面通过选定的切分点并垂直于选定的坐标轴,将当前超矩形区域切分为左右两个子区域(子结点);
    这时,实例被分到两个子区域,这个过程直到子区域内没有实例时终止(终止时的结点为叶节点)。

在此过程中,将实例保存在相应的结点上。

通常,选择坐标轴对空间切分,选择训练实例点在选定坐标轴的中位数为切分点,这样得到的kd树是平衡的。但平衡的kd树搜索时的效率未必是最优的。


算法

输入:k维空间数据集$T=lbrace x_1,x_2,…,x_nrbrace $
其中$x_i=(x_i^{(1)},x_i^{(2)},…,x_i^{(n)})^{T},i=1,2,3,…,N$
输出:kd树

(1) 开始:构造根结点,根结点对应于包含$T$的k维空间的超矩形区域。
选择$x^{(l)}$为坐标轴,以$T$中所有实例的$x^{(l)}$坐标的中位数为切分点,将根结点对应的超矩形区域切分为两个子区域,切分由通过切分点并与坐标轴$x^{(l)}$垂直的超平面实现。
由根结点生成深度为1的左、右子结点:左子结点对应坐标$x^{(l)}$小于切分点的子区域,右子结点对应于坐标$x^{(l)}$大于切分点的子区域。
(2) 重复:对深度为$j$的结点,选择$x^{(l)}$为切分的坐标轴,以该结点的区域中所有的实例的$x^{(l)}$坐标的中位数为切分点,将该结点对应的超矩形区域切分为两个子区域,切分由通过切分点并与坐标轴$x^{(l)}$垂直的超平面实现。
由该结点生成深度为$j+1$的左、右子结点:左子结点对应坐标$x^{(l)}$小于切分点的子区域,右子结点对应坐标$x^{(l)}$大于切分点的子区域。
将落在切分超平面上的实例点保存在该结点。
(3) 直到两个子区域没有实例存在时停止,从而形成kd树的区域划分。


搜索kd树

kd树可省去对大部分数据点的搜索,从而减少搜索的计算量。下面以最近领为例加以说明,同样的方法可以推广到k-NN。

给定一个目标点,搜索其最近邻。

  • 首先,找到包含目标点的叶结点;
  • 然后,从该叶结点出发,依次回退到父结点;
  • 不断查找与目标点最近邻的结点,当确定不可能存在更近的结点时终止。

这样,搜索就被限制在空间的局部区域上,效率大为提高。
包含目标点的叶结点对应包含目标点的最小超矩形区域。以此叶结点的实例点作为当前最近点。目标点的最近邻一定在以目标点为中心并通过当前最近点的超球体的内部。然后返回当前结点的父结点,如果父结点的另一子节点的超矩形区域与超球体相交,那么在相交的区域内寻找与目标点更近的实例点,继续上述过程。如果父结点的另一子结点的超矩形区域与超球体不相交,或不存在比当前最近点更近的点,则停止搜索。

算法

输入:已构造的kd数,目标点x
输出:x的最近邻

(1) 在kd树种找出包含目标点x的叶结点:从根结点出发,递归地向下访问kd树。若目标点x当前维的坐标小于切分点的坐标,则移动到左子结点,否则移动到右子结点。直到子结点为叶结点为止。
(2) 以此叶结点为“当前最近点”
(3) 递归地向上回退,在每个结点进行以下操作

(a) 如果该结点保存的实例点比当前最近距离目标点更近,则以该实例点为“当前最近点”
(b) 当前最近点一定存在于该结点一个子结点对应的区域。检查该子结点的父结点的另一子节点对应的区域是否有更近的点。具体地,检查另一子结点对应的区域是否与以目标点为球心,以目标点与“当前最近点”间的距离为半径的超球体相交。
如果相交,可能在另一个子结点对应的区域内存在距目标点更近的点,移动到另一个子结点。接着,递归地进行最近邻搜索;
如果不相交,向上回退。

(4) 当回退到根结点时,搜索结束。最后的“当前最近点”即为x的最近邻点。

如果实例点是随机分布的,kd树搜索的平均计算复杂度是$O(logN)$,N是训练实例数。
kd树更适用于训练实例数远大于空间维数时的k-NN搜索。当空间维数接近训练实例时,它的效率会迅速下降,几乎接近线性扫描。


数据处理

  • 异常数据处理
  • 数据标准化
  • 数据归一化

注:后续详细讨论数据处理的方法和实现


权重k-NN

无论是在分类还是回归算法中,均可以通过增加权重以调整各个近邻实例点的贡献,即离输入实例点越近的邻近点比相对距离稍远的邻近点的贡献越大。
常见的权重是$frac{1}{d}$,其中d是与近邻点的距离。


数据倾斜

在“Majority viting”分类过程中,如果训练实例数据集的分类标签存在数据倾斜,即大量出现的某个类标签往往决定了预测的实例点的类别,因为它们更可能是最近邻的k个最近邻的邻近点。
其中的一种解决方法是,对分类过程增加权重,考虑各邻近点到测试点的距离的倒数。
另外一种解决方法是abstraction in data representation(不会准确的翻译这个术语),例如SOM(self-organizing map),个人理解,简而言之即将相同类标签的相似聚簇点抽象一个质点或中心点,而忽略原始数据实例点的密度分布问题。


参考资料

<<统计学习方法>> 李航 著
https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm