k近邻算法

k近邻算法是“最简单”的监督机器学习算法之一，并且在上个世纪在模式识别领域得到了广泛的研究。虽然现在 kNN 不像以前那样流行，但在实践中仍然被广泛使用。kNN 算法在分类项目中可以作为更复杂模型的预测性能基准。

1. 历史背景

Evelyn Fix(1904-1965) 是一位数学家/统计学家，在伯克利攻读博士学位并继续在那里教授统计学。

Joseph Lawson Hodges Jr.(1922-2000) 也是伯克利的一名统计学家，并从1944年开始参与与美国空军第二十空军（Twentieth Air Force of USAF）的统计合作。

这两位天才在1951年为美国空军制作的一份技术分析报告中相遇，在那里他们引入了一种非参数分类方法（判别分析）。他们从未正式发表过这篇论文，可能是因为所涉及的工作性质和保密性，特别是考虑到二战后不久的全球气氛。

接下来，Thomas Cover 和 Peter Hart 在1967年证明了 kNN 分类的上限错误率[11]。

2. 算法模型

kNN 算法在某些条件下是一个通用的函数逼近器，但潜在的概念相对简单。kNN 是一种监督学习算法，它在训练阶段简单地存储标记的训练样本。因此，kNN 也被称为惰性学习算法，它对训练样本的处理推迟到做预测的时候才进行。

假设训练数据集：

其中，${\displaystyle \mathbf x_i\in X\subseteq R^n}$ 表示实例的特征向量，$y\in Y$ 表示实例的类别。给定实例特征向量$\mathbf x$，输出所属的类 $y$ 。

具体过程：

  1. 通过给定的距离度量，在训练集 $T$ 中找出与 $\mathbf x$ 最近邻的 $k$ 个点，涵盖这 $k$ 个点的 $\mathbf x$ 的领域记作 $N_k(\mathbf x)$
  2. 随后在 $N_k(\mathbf x)$ 中根据分类决策规则决定 $\mathbf x$ 的类别 $y$。

可以看出，kNN 算法的主要三个要素分别为距离度量、$k$ 值和分类决策规则。

2.1 距离度量

距离度量有曼哈顿距离、欧式距离或更一般的闵式距离。

假设两个特征向量 $\mathbf{x}_i=(x_i^{(1)},x_i^{(2)},…,x_i^{(n)})^T$，$\mathbf{x}_j=(x_j^{(1)},x_j^{(2)},…,x_j^{(n)})^T$，$\mathbf{x}_i,\mathbf{x}_j$ 的 $L_p$距离定义为：

当 $p=1$ 时，称为曼哈顿距离，即

当 $p=2$ 时，称为欧式距离，即

当 $p=\infty$，它是各个坐标距离的最大值，即

下图给出了二维空间中不同 $p$ 值情况下，与原点距离为 $1$ 的图形。
Minkowski distance

Minkowski distance

范数即为特征向量到原点的距离，表征自身的长度

2.2 $k$ 值的选择

如果选择较小的 $k$ 值，相当于用较小的领域中的训练数据进行预测，近似误差（approximation error）会减少，只有与输入实例较近的训练数据才会对预测结果产生影响。但缺点是估计误差（estimation error）会增大，预测结果对近邻的实例点非常敏感，容易发生过拟合。当 $k$ 为1时，称为最近邻算法，对于输入实例，将与其最近的数据点的类作为预测结果。

相反的，当使用较大的 $k$ 值时，意味着距离输入实例较远的训练数据也会对预测结果产生影响，使预测产生错误，容易发生欠拟合。当 $k$ 为 $N$ 时，无论输入实例是什么，预测结果都将是训练数据中存在最多的类。

在应用中，$k$ 一般选取一个比较小的值，采用交叉验证法来选取最优的 $k$ 值。

2.3 决策规则

kNN算法在分类问题中决策规则往往是“多数表决”，即由输入实例的 $k$ 个近邻的训练实例中的多数类决定输入实例的类。事实上，多数表决（Majority vote）分为简单多数表决和特定多数表决，是要求满足一半数量以上或者特定数量，而不是占比最多的（Plurality vote），在二分类问题中两者没有区别，而在多分类问题中，不需要某一类投票数过半，超过 $N$ 分之一（$N$ 是分类总数）就可以预测了。

在回归问题中，可使用“平均法”，即将这 $k$ 个样本的实值输出标记的平均值作为预测结果，还可基于距离远近进行加权平均或加权投票，距离越近的样本权重越大。

3. 模型优化

在考虑 kNN 算法时间复杂度之前，先看一下特征维度对算法的影响。

假设我们有 $100$ 个训练实例均匀分布在 $(0,1]$ 区间， 它们的间隔为 $0.01$ 单元。假设 $k$ 值为 $3$，就是找到查询点的三个最近邻，期望覆盖特征轴 $0.03$ 的范围。当我们增加一个维度的时候，总体分布在 $1\times 1$ 的区域中，为了覆盖相同的领域，需要 $0.03^{1/2}\approx 0.17$ 范围的坐标轴区域。当维度为 $10$ 的时候，这一数值 $0.03^{1/10}\approx 0.704=70.4\%$。可以发现，在高维中我们需要考虑很大的超体积来找到 $k$ 个近邻样本，这些点与查询点的距离相对较远，变得越来越不“相似”。

这种现象在机器学习中被称为维度灾难，指的是训练样本大小固定但维度的数量和每个维度的特征值范围不断增加的场景。

kNN 算法的时间复杂度是 $O(k\ast N\ast m)$ ，$N$ 是训练样本的数量，$m$ 是训练数据集的特征维度，由于 $N\gg m$，时间复杂度简化为 $O(k\ast N)$，可以看出时间复杂度较高，通过数据结构的方法可以将时间进行优化。

3.1 堆优化

最暴力的解法是重复 $k$ 次找到 $k$ 个最近邻的训练实例，通过堆优化可以将时间复杂度降到 $O(n\log(k))$。

随机选取 $k$ 个训练数据集的点来初始化查询点的堆。通过维护一个堆来保存距离查询点最近的 $k$ 个点。通过遍历数据集，如果该点到查询点的距离比堆中保存的最大的距离还要小，则从堆中剔除最远的点并插入当前点。一旦完成了训练数据集的一次迭代，我们就有了一组 $k$ 个最近邻的点。

3.2 桶优化

上面的优化方法在每次查询时都还是要对训练数据集进行遍历，如果要快速查询还是需要对数据的存储方式进行优化。

最简单的方法就是分桶（bucketing），我们将搜索空间划分为相同大小的单元格，类似于网格。

突然发现，工作中要把热力点匹配到距离最近的道路点上，同事就是用的种方法，取热力点所在单元格周围的九个格子中的link，再将取到的道路点和热力点进行匹配。

3.3 KD-树优化

找到 $k$ 个最近邻的点，本质还是搜索，而提高搜索效率很自然的就会想到二叉树，KD-树就是二叉搜索树（BST）的一种推广。KD-树的时间复杂度平均为 $O(\log(N))$ ，它在笛卡尔坐标系中垂直于特征轴划分搜索空间，这在较低的维度上表现较好，随着特征轴的增多，KD-树将变得低效。

KD-树构建

构造KD-树相当于不断用垂直于坐标轴的超平面将k维空间切分，构造一系列的k维超矩形区域。KD-树的每个结点存储一个训练实例点，每一颗子树对应于一个k维超矩形空间。

二叉搜索树是KD-树在一维空间的特例，任何一个节点相当于一个分割点，左边的比它小，右边的所有节点比它大。在二维空间，一个节点就相当于一条分割线，以此类推，三维空间就是一个面。这种分割方式意味着垂直于一条坐标轴进行分割。分割维度的方式是通过二叉树的深度，第一层根结点分割x轴，第二层分割y轴，以此类推，如果维度遍历完了，下一层又回到x轴，不断重复。

KD-树构建步骤：

  1. 初始化数据集 $T=\{x_1, x_2,…,x_N\}$，KD树深度 $j=1$，数据集的维度为 $k$。
  2. 选择第 $l=j\bmod k + 1$ 维进行分割，找到数据集中所有实例的第 $l$ 维坐标的中位数，把该点作为切分点。
  3. （可选）不按照固定顺序选择切割维度，而是选取方差最大特征作为分割特征。
  4. 把切分点记录到KD-树节点上，把数据集中该特征值小于中位数的传递给左子树，把大于中位数的传递给右子树。
  5. 递归执行步骤2-4，直到所有数据都被建立到KD-树节点上。

KD-树搜索

KD-树构建完成之后，每次进行查找最近邻时就可以通过KD-树进行查找，类似于二分查找，但由于存在每一层只有一个节点的树形情况，时间复杂度介于 $O(\log(N))$、$O(N)$。相较于二叉搜索树，KD-树多了一个回溯的过程。

KD-树搜索步骤：

  1. 从根节点起始，根据当前节点的分割维度查看查询点相应的特征值，与节点同一维度的特征值对比，根据大小相应的向左或向右移动。
  2. 当移动到叶子结点时，记录当前节点为“当前最近点”。
  3. 回溯，再从叶子结点返回根节点。
  4. 如果当前节点比当前最近点距离查询点更近，则记录当前节点为“当前最近点”。
  5. 判断查询点到当前节点的父节点所在的将数据集分割为两部分的超平面的距离，如果该距离比到“当前最近点”的距离要小，意味着兄弟节点所在的子树中可能包含更近的点。进入到兄弟节点，重复进行1-4步骤。
  6. 当回溯到根节点时，结束搜索。

用查询点到“当前最近点”的距离可以形成一个圆或者一个超球体，如果到超平面的距离更小，意味着超球体与另一半空间相交，那么另一半空间可能存在比当前最近点更近的点，否则的话，另一半空间一定不存在更近的点，可以略去搜索。

4. KD-树实现

KD-树的构建

import numpy as np

class Node():
    def __init__(self, feature):
        self.father = None
        self.feature = feature
        self.left = None
        self.right = None
        self.divide = None

    @property
    def brother(self):
        if self == self.father.left:
            return self.father.right
        else:
            return self.father.left

    def __str__(self):
        return 'feature: {}'.format(self.feature)

class KDTree():
    def __init__(self, points):
        self.root = self.build_tree(points)

    def build_tree(self, points, dim = 0, father = None):
        if not points:
            return None

        points = sorted(points, key = lambda x: x[dim])
        mid = len(points) // 2
        curNode = Node(points[mid])
        curNode.divide = dim
        curNode.father = father
        curNode.left  = self.build_tree(points[:mid], (dim + 1) % len(points[0]), curNode)
        curNode.right = self.build_tree(points[mid + 1:], (dim + 1) % len(points[0]), curNode)

        return curNode


    def __str__(self):
        def inorder(root, depth = 0):
            if not root:
                return
            ret.append('depth: {}, {}'.format(str(depth), str(root)))
            inorder(root.left, depth + 1)
            inorder(root.right, depth + 1)

        ret = []
        inorder(self.root)
        return '\n'.join(ret)

pnts = [[2,3], [5,4], [9,6], [4,7], [8,1], [7,2]]
tree = KDTree(pnts)
print(tree)

depth: 0, feature: [7, 2]
depth: 1, feature: [5, 4]
depth: 2, feature: [2, 3]
depth: 2, feature: [4, 7]
depth: 1, feature: [9, 6]
depth: 2, feature: [8, 1]

KD-树的搜索

    def _search(self, root, target):
        if not root:
            return None
        if target[root.divide] < root.feature[root.divide]:
            res = self._search(root.left, target)
        else:
            res = self._search(root.right, target)

        return res if res else root

    def _get_distance(self, x, y):
        return np.sqrt(np.sum((np.array(x) - np.array(y)) ** 2))

    def _get_hyper_plane_distance(self, node, target):
        return abs(target[node.divide] - node.feature[node.divide])


    def nearest_neighbour_search(self, target, root):
        nearest_node = self._search(root, target)
        nearest_distance = self._get_distance(nearest_node.feature, target)
        currnode = nearest_node

        while currnode != root:
            tempnode = currnode
            currnode = currnode.father  #如果currnode没有父节点，它一定等于root，就不会进入这一层
            if self._get_distance(currnode.feature, target) < nearest_distance:
                nearest_node = currnode
                nearest_distance = self._get_distance(currnode.feature, target)

            if self._get_hyper_plane_distance(currnode, target) < nearest_distance:
                bro_distance, bro_nearest_node = self.nearest_neighbour_search(target, tempnode.brother)
                if bro_distance < nearest_distance:
                    nearest_node = bro_nearest_node
                    nearest_distance = bro_distance

        return nearest_distance, nearest_node
pnts = [[2,3], [5,4], [9,6], [4,7], [8,1], [7,2]]
tree = KDTree(pnts)
dis, node = tree.nearest_neighbour_search([6,2], tree.root)
print(dis, node)

1.0 feature: [7, 2]

5. 算例

参考

1. K近邻算法KNN的简述
2. KNN（K近邻算法）基本介绍
3. 机器学习之KNN（k近邻）算法详解
4. K-近邻算法-维基百科
5. K-nearest neighbor
6. KD Tree的原理及Python实现-李小文
7. STAT 479: Machine Learning Lecture Notes
8. 【数学】kd 树算法之详细篇
9. KD树简介
10. k-d tree算法
11. Nearest Neighbor Pattern Classification


Machine Learning
2021-11-09