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