k近邻法

k近邻法(KNN)是一种基本分类与回归方法。k近邻法的输入为实例的特征向量,对应于特征空间的点输出为实例的类别

假设给定一个带标签的训练数据集。预测时,对新的实例,根据其k个最近邻的训练实例的类别,通过多数表决等方式进行预测。因此,k近邻法不具有显示的学习过程

k近邻法的三个基本要素:

  1. k值的选择
  2. 距离度量
  3. 分类决策规则

该算法于1968年由Cover和Hart提出。

本文首先叙述k近邻算法,然后讨论k近邻算法的模型及三个基本要素,最后讲述k近邻法的一个实现方法——kd树,介绍构造kd树和搜索kd树的算法。

3.1 k近邻算法

算法 3.1(k近邻法)

输入:训练数据集,其中,为实例的特征向量,为实例的类别,i=1,2,…,N;实例特征向量x:

输出:实例x所属的类y

  1. 根据给定的距离度量,在训练集T中找出与x最邻近的k个点,涵盖这k个点的x的邻域记作

  2. 中根据分类决策规则(如多数表决)决定x的类别y:

    式(3.1)中,I为指示函数,即当时I为1,否则I为0。

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

3.2 k近邻模型

k近邻法使用的模型实际上对应于对特征空间的划分

3.2.1 模型

k近邻法中,当训练集、距离度量(如欧式距离)、k值及分类决策规则(如多数表决)确定后,对于任何一个新的输入实例,它所属的类唯一确定

相当于根据上述要素将特征空间划分为一些子空间

3.2.2 距离度量

特征空间中两个点之间的距离是两个点相似程度的反映。k近邻法使用的距离是欧式距离。还有其他距离,如或Minkowski距离。

设特征空间是n维实数向量空间

对于距离定义为:

这里。当p=2时,称为欧式距离,即:

当p=1时,称为曼哈顿距离,即:

时,它是各个坐标距离的最大值,即:

注意:不同的距离度量所确定的最近邻点是不同的

3.2.3 k值的选择

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

如果选择较小的k值,就相当于用较小的邻域中的训练实例进行预测,“学习”的近似误差(approximation error)会减小,只有与输入实例较近的训练实例才会对预测结果起作用,但缺点是“学习”的估计误差(estimation error)会增大,预测结果会对近邻的实例点非常敏感。如果邻近的实例点恰巧是噪声,预测就会出错

换句话说,k值的减小就意味着整体模型变得复杂,容易发生过拟合。反之,则容易发生欠拟合

如果k=N,那么对于不均衡样本来说,相当于把所有的样本都预测成样本数最多的那个类别。

在实际应用中,k值一般先取一个比较小的数值。通常采用交叉验证法选取最优的k值

3.2.4 分类决策规则

多数表决规则:如果分类的损失函数为0-1损失函数,分类函数为

那么误分类的概率是:

对给定的实例,其最近邻的k个训练实例点构成集合。如果涵盖的区域的类别是$c_j$,那么误分类率是:

要是误分类率最小即经验风险最小,就要使最大,所以多数表决规则等价于经验风险最小化

3.3 k近邻法的实现:kd树

实现k近邻法时,主要考虑的问题是如何对训练数据进行快速k近邻搜索这点在特征空间的维数大及训练数据容量大时尤其必要

k近邻法最简单的实现方法是线性扫描。但需要遍历所有的训练样本,计算非常耗时,样本集非常大时,这种方法不可行。

为了提高k近邻搜索的效率,可以考虑使用特殊的结构存储训练数据,以减少计算距离的次数。如kd树方法。

3.3.1 构造kd树

kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。它有如下性质:

  1. 二叉树
  2. 表示对k维空间的一个划分
  3. 构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间切分,构成一系列的k维超矩形区域
  4. kd树的每个结点对应于一个k维超矩形区域

算法3.2(构造平衡kd树)

输入:k维空间数据集,其中,i=1,2,…,N;

输出:kd树

  1. 初始化构造根节点,根节点对应于包含T的k维空间的超矩形区域。

    选择为坐标轴,以T中所有实例的坐标的中位数为切分点,将根节点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴垂直的超平面实现

    由根节点生成深度为1的左、右子结点:左子结点对应坐标小于切分点的子区域,右子结点对应于坐标大于切分点的子区域

  2. 重复对深度为j的结点,选择为切分的坐标轴,,以该结点的区域中所有的实例的坐标的中位数为切分点,将该结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴垂直的超平面实现。

  3. 退出条件:直到两个子区域没有实例存在时停止。从而形成kd树的区域划分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def build_kdtree(data,d,k):
'''
data: 当前需要被划分的样本集
d:当前选取的坐标轴,取值范围为[0,k-1]
k:样本特征的总的维数,常量
'''
data = sorted(data, key=lambda x:x[d])
p,m = median(data)
tree = node(p)

if m>0: tree.set_left(build_kdtree(data[:m],(d+1)%k,k))#设置左节点,并递归构建左子树
if len(data)>1: tree.set_right(build_kdtree(data[m:], (d+1)%k,k)) #设置右子树

return tree

3.3.2 搜索kd树

算法3.3(用kd树的最近邻搜索)

输入:已构造的kd树;目标点x;

输出:x的最近邻。

  1. 在kd树中找出包含目标点x的叶结点:

    1. 从根结点出发,递归地向下访问kd树。
    2. 若目标点x当前维的坐标值小于切分点的坐标值,则移动到左子结点,否则移动到右子结点。直到子结点为叶结点位置
  2. 以此叶结点为”当前最近点”

  3. 递归地向上回退,在每个结点进行一下操作:

    a. 如果该结点保存的实例点比当前最近点距离目标点更近,则以该实例点为”当前最近点”

    b. 当前最近点一定存在于该结点一个子结点对应的区域。检查该子结点的父节点的另一个子结点(兄弟结点)对 应的区域是否有更近的点。

    具体地,检查兄弟结点的区域是否存在以目标点为球心,以目标点与”当前最近点”间的距离为半径的超球体相交

    如果相交,可能在兄弟结点对应的区域内存在距目标点更近的点,移动到兄弟结点上。接着,递归的进行最近邻搜索(即回到步骤1)

    c.如果不想交,重复步骤3。

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

搜索kd树的时间复杂度:O(log N)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def search_kdtree(tree, d, target, k, data):
if target[d]<tree.point[d]: #目标实例的值小于当前树结点的值时
if tree.left is not None:
return search_kdtree(tree.left, (d+1)%k, target, k, data)
else:
if tree.right is not None:
return search_kdtree(tree.right, (d+1)%k, target, k, data)

def update_best(t, best):
if t is None: return
t = t.point
dist = distance(t, target)
if dist < best[1]:
best[1]=dist #距离
best[0]=t#树结点
#遍历到了叶节点
best = [tree.point,np.inf] #初始化
while tree.parent is not None:
update_best(tree.parent.left, best)
update_best(tree.parent.right, best)
tree = tree.parent
return best[1],np.where(np.all(data==best[0],axis=1))[0]

3.4 knn相关算法

3.4.1 scipy中的kd树

使用的算法请参考:Analysis of Approximate Nearest Neighbor Searching with Clustered Point Sets

3.4.2 sklearn中的算法

官方文档,请参考:https://scikit-learn.org/stable/modules/neighbors.html#neighbors

  1. kd树算法参考:Multidimensional binary search trees used for associative searching
  2. balltree算法参考:Five Balltree Construction Algorithms