0. 写在前面

在这一讲的讨论班中，我们将要讨论一下K近邻模型。可能有人会说，K近邻模型有什么好写的，那分明就是一个最简单的机器学习模型，哦，不，连机器学习也算不上的算法吧。但是这里，我想提醒的是，我们要讨论的，不仅仅是简单的K近邻模型，而是和它相关的一些有困惑的话题。

1. K近邻定义

k近邻算法，也成为KNN算法，是一种基本分类与回归算法。它在基本实现上，使用的是多数表决的惰性学习过程。也就是它实际上是基于记忆的学习方法。它并没有学出一个什么判别模型，其实也没有像贝叶斯那样算出一个新东西，而是简单的统计距离目标点最近的K个节点里数目最多的标签赋予目标点。就是这么一个简单的算法。我们这里给出一个最朴素的K近邻算法：

K近邻算法
输入：训练数据集 $T={(x_1,y_1),(x_2,y_2),...(x_N,y_N)}$
输出：实例x所属的类y

算法步骤：
（1）根据给定的距离度量，在训练集T中找出与x最近邻的k个点，涵盖这k个点的x的邻域记作 $N_k(x)$
（2）在 $N_k(x)$ 中根据分类决策规则，如多数表决决定x的类别y。

1.1. k近邻模型

k近邻模型的核心就是使用一种距离度量，获得距离目标点最近的k个点，根据分类决策规则，决定目标点的分类。

就是这么三句话，决定了k近邻模型的三个基本要素——距离度量、k值的选择、分类决策规则。

1.2. 距离度量

一个点和一个点之间的距离，无论是什么计算方式，基本上离不开 $L_p$ 距离。我们熟知的欧式距离，则是 $L_2$ 范式，也就是p=2的情况，而另一个很熟悉的距离曼哈顿距离，则是 $L_1$ 范式。 $L_p$ 距离的定义如下：
$L_p(x_i,x_j)=(\displaystyle\sum_{l=1}^{n}|x_i^{(l)}-x_j^{(l)}|^p)^{\frac{1}{p}}$

当然，如果p→∞的时候，就叫做切比雪夫距离了。

除了这个闵可夫斯基距离集合外，还有另外的距离评估体系，例如马氏距离、巴氏距离、汉明距离，这些都是和概率论中的统计学度量标准相关。而像夹角余弦、杰卡德相似系数、皮尔逊系数等都是和相似度有关的。

因此，简单说来，各种“距离”的应用场景简单概括为，空间：欧氏距离，路径：曼哈顿距离，国际象棋国王：切比雪夫距离，以上三种的统一形式:闵可夫斯基距离，加权：标准化欧氏距离，排除量纲和依存：马氏距离，向量差距：夹角余弦，编码差别：汉明距离，集合近似度：杰卡德类似系数与距离，相关：相关系数与相关距离。

这其实只是个度量标准而已，应当根据数据特征选择相应的度量标准。

1.3. k值的选择

k值的选择也很有必要，因为k的选择小了，则近似误差会减小，但估计误差会增大；相反k的选择大了，则近似误差会增大，估计误差会减小。这一点，我们会在近似误差与估计误差那一部分进一步讲解。

1.4. 分类决策规则

k近邻的分类决策规则是最为常见的简单多数规则，也就是在最近的K个点中，哪个标签数目最多，就把目标点的标签归于哪一类。

实际上，也是可行的，也是唯一可行的分类决策规则。无论是全体一致规则（一票否决制）还是绝对多数规则，都不能在任何时候对目标点做出确切的预测，更不用提少数原则这种不靠谱的决策规则了。

当然，这也是有理论依据的：
如果分类的损失函数为0-1损失函数，则误分类的概率是：
$P (Y ̸ = f (X)) = 1 - P (Y = f (X))$

也就是说误分类率为：

$\frac{1}{k}\sum I(y_i≠c_j)=1-\frac{1}{k}I(y_i=c_j)$

要使得误分类率最小，也就是经验风险最小，就要使得 $\frac{1}{k}I(y_i=c_j)$ 最大，所以多数表决规则等价于经验最小化。

其实，还可以使用权重加权的多数表决，对于K个最近点，根据其距离的远近来进行加权统计，从而获得一个折中的效果。本方法为个人所想，不知有没有实践来论证。

2. 估计误差与近似误差

2.1. 估计误差

估计误差我们应该在初中或者高中物理的时候就已经学过了，也许只是忘记了而已。估计误差主要包含四个部分：系统误差、随机误差、过失误差、精密度和精确度。

就我们K近邻来讲，如果K值比较小，那么例如像噪点，错误的数据，不恰当的度量标准以及数据本身的缺陷等，都会很大程度上影响最终的结果，而如果K值比较大，那么以上缺陷就会尽可能的平均，从而减小对最终结果的影响。

2.2. 近似误差

近似误差与估计误差的描述对象不同，估计误差度量的是预测结果与最优结果的相近程度，而近似误差是度量与最优误差之间的相似程度。就K近邻算法来讲，K值越小，那么与目标点相近的点的标签对于其目标点的影响也就越大，其标签的一致性就越高，这样近似误差就会变小。

2.3. 两者区别与联系

总而言之，近似误差指的是目标点对于其原样本点的可信度，误差越小，对于原样本点的信任度越高，也就是说，目标点可能只需要对最近的点确认一次就可以标注自己的标签，而无需去询问其他目标点。而估计误差则是原模型本身的真实性，也就是说，该模型所表现出的分类特性，是不是就是真实的分类特性，比如有噪点影响，有错误数据记录，或者本身数据分布就不是很好，都会是影响估计误差的因素，而询问的点越多，那么这些坏点对于目标点的标签影响就越小。

这就像是你向别人征求意见，你对于别人意见的采纳率越高，则别人意见的近似误差越小。而别人意见越符合实际情况，则估计误差越小。这么说应该有个大致的理解了吧。

3. K近邻的实现kd树

我们通过上述描述，应该清楚了一个K近邻算法的基本运作思想，由于没有训练过程，没有预测模型，使得K近邻算法的计算量十分巨大，因为它需要把所有的样本点都和目标点进行一次距离度量，很难适应大规模的数据样本。那么kd树就应运而生了。

3.1. kd树定义

kd树，指的是k-dimensional tree，是一种分割K维数据空间的数据结构，主要用于多维空间关键数据的搜索。kd树是二进制空间分割树的特殊情况。

索引结构中相似性查询有两种基本的方式：一种是范围查询，另一种是K近邻查询。范围查询就是给定查询点和查询距离的阈值，从数据集中找出所有与查询点距离小于阈值的数据；K近邻查询是给定查询点及正整数K，从数据集中找到距离查询点最近的K个数据，当K=1时，就是最近邻查询。

而对于这类问题，解决办法有两类：一类是线性扫描法，即将数据集中的点与查询点逐一进行距离比较，也就是穷举，缺点很明显，就是没有利用数据集本身蕴含的任何结构信息，搜索效率较低，第二类是建立数据索引，然后再进行快速匹配。因为实际数据一般都会呈现出簇状的聚类形态，通过设计有效的索引结构可以大大加快检索的速度。索引树属于第二类，其基本思想就是对搜索空间进行层次划分。根据划分的空间是否有混叠可以分为Clipping和Overlapping两种。前者划分空间没有重叠，其代表就是k-d树；后者划分空间相互有交叠，其代表为R树。

但是要说明的是kd树的朴素用法，只能解决最近邻算法，对于K近邻算法还需要改进后才能够使用，这里我们放到最后再讲。

3.2. kd树的构造算法

构造kd树的方法根据不同的决策规则分为很多种，但最终都是平衡二叉树。具体方法如下：

构造根节点，使根节点对应用于K维空间中包含所有实例点的超矩形区域。
通过下面的递归方法，不断切分K维空间，生成子节点：
1. 在超矩形区域上选择一个坐标轴和该坐标上的一个切分点，确定一个超平面。
2. 以经过该点且垂直于该坐标轴做一个超平面，该超平面将当前的超矩形区域切分成左右两个子区域，实例被分到两个子区域。
该过程直到子区域内无实例时终止（终止时的节点为子节点）。
在此过程中将实例集合保存在相应的节点上。

在这个方法中，有两个部分时可以进行调节的，第一个部分就是选取的维度的顺序，另一个部分就是选取分割点的度量标准。

在第一部分，我们可以使用顺序采样，即从第1维，第2维，第n维一直到分割完毕为止。也可以使用最大方差所在的维度，也可以使用维度主次优先级为顺序，以此等等。

在第二部分，我们可以使用的是所在维度的中位数作为切分点，也可以使用中值作为切分点，以此等等。

这里，我们使用的是最朴素的方法，维度采用顺序采样，切分点选取中位数作为切分点，来描述一下kd树构造算法。

kd树构造算法
输入：k维空间数据集T = ${x_1,x_2, …, x_N}$ ，其中， $x_i = (x_i^{(1)}, x_i^{(2)},…, x_i^{(k)})，i = 1, 2, …, N$
输出：kd树
开始：

构造根节点（根节点对应于包含T的K维空间的超矩形区域）
选择 $x^{(1)}$ 为坐标轴，以T中所有实例的 $x^{(1)}$ 坐标的中位数为切分点，这样，经过该切分点且垂直与 $x^{(1)}$ 的超平面就将超矩形区域切分成2个子区域。保存这个切分点为根节点。
重复如下步骤：
对深度为j的节点选择 $x^{(l)}$ 为切分的坐标轴， $j(mod\;k) + 1$ ,以该节点区域中所有实例的 $x^{(l)}$ 坐标的中位数为切分点，将该节点对应的超平面切分成两个子区域。切分由通过切分点并与坐标轴 $x^{(l)}$ 垂直的超平面实现。保存这个切分点为一般节点。
直到两个子区域没有实例存在时停止。

具体的例子大家可以看一下书，我们的重点不在于此。对于书上的例子，一句话概括为：偶数层以第一维为二分检索树，奇数层以第二维为二分检索树。对于n个实例的k维数据来说，建立kd-tree的时间复杂度为O(k×n×logn)。

而对于kd树的插入删除等不在我们这堂课的讨论范围内，大家可以课后自己查阅资料，因为这方面比较复杂。

对于kd树的插入来说，就相当于一个随时改变比较维度的二叉检索树：在偶数层比较x坐标值，而在奇数层比较y坐标值。当我们到达了树的底部，（也就是当一个空指针出现），我们也就找到了结点将要插入的位置。

这一部分感兴趣的同学可以更深入的研究一下。

3.3. kd树的检索算法

既然已经建成了kd树了，那么kd树的检索算法就被提上议程，这次，我们使用的就是针对上面的kd树构建算法而写出的kd树检索算法：

kd树最近邻搜索算法
输入：已构造的kd树：目标点x;
输出：x的最近邻。

在kd树中找出包含目标点x的叶结点：从根结点出发，递归的向下访问kd树。若目标点x当前维的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子节点，直到子节点为叶结点为止。
以此叶节点为“当前最近点”。
递归的向上回退，在每个结点进行以下操作：
1. 如果该结点保存的实例点比当前最近点距离目标点更近，则以该实例点为“当前最近点”。
2. 当前最近点一定存在于该结点一个子结点对应的区域。检查该子结点的另一子结点对应的区域是否有更近的点。
  具体的，检查另一子结点对应的区域是否与以目标点为球心，以目标点与“当前最近点”间的距离为半径的超球体相交。
  如果相交，可能在另一个子结点对应的区域内存在距离目标点更近的点，移动到另一个子结点，接着，递归地进行最近邻搜索。
  如果不相交，向上回退。
当回退到根结点时，搜索结束，最后的“当前最近点”即为x的最近邻点。

这样，其实只要把握住了这么个几个部分，首先，是当前最近点的初始值的确定，第二，如何回溯比较，第三，如何搜索可能存在的解。

总而言之，若实例点随机分布，则KD树搜索的时间复杂度为O(logN)，N为训练实例数。就具体而言，KD树更适用于训练实例数远大于空间维度的K近邻搜索。一般是20维以下的，效果比较好。

4. 关于K近邻算法的若干其他问题

关于K近邻算法还有很多更加深入的问题，我们在下面进行简要的讨论，在以后有时间时，我们会针对某些具体的问题，做出专题讲解。

4.1. K近邻算法与K-means聚类算法的区别

K近邻算法和K均值聚类算法看起来十分相似，不过还是有一些区别的，我们这里给出一张表：

KNN	K-Means
KNN是分类算法	K-Means是聚类算法
KNN是监督学习	K-Means非监督学习
没有明显的前期训练过程	有明显的前期训练过程
K的含义指的是判断依据来源个数	K的含义是集合的分类数目

而这两者都用到了NN算法，一般使用kd树来实现。

4.2. 如何使用kd树来进行K近邻查找

这道题是课后习题第三题，网上说通过维护一个包含 k 个最近邻结点的队列来实现，就我个人想法而言，实际上，主要是看这些队列里的值从何而来。我认为，这些较近的点是来源于那些最近邻点可能存在的点的集合中，也就是最近邻点的父节点以及跨越了超球面的那些区域内的点及他们的父节点。

也就是说，只需要改动这么几个步骤，就是在与最近邻点相比较的所有节点都可以存入到k近邻队列中，然后队列未满时，其最短距离为∞，队列已满时，其最短距离为队列中最长的结点的距离。一旦新来的结点小于这个最长距离，则删除最长结点，插入新来的结点，并且更新队列的最短距离。

一般来讲，如果k比较小，那么常规kd树检索已经足够查到K个近邻点。但是如果发生了没有找全k个最小的，可以在另一半的树中查找剩下的近邻点。

4.3. 课后习题3.1

课后题目3.1描述如下：

参照图3.1，在二维空间中给出实例点，画出k为1和2时的k近邻法构成的空间划分，并对其进行比较，体会k值选择与模型复杂度及预测准确率的关系。

我们不去考虑k为1的情况，因为k为1的情况我们可以很容易从原图中获取，我们来考虑k=2时候的空间划分。

我们都知道，在2维空间中，我们通常使用的是一条线来进行2分类，这也是最优的分类方式（每次减小样本空间一半），那么在这个题目中，如果k=2的时候，我们考虑最近的3个点开始，其实无论是多少都没关系的，只不过时间复杂度比较大，但是我们通常不会选取过多的候选点。

现在，这条线就是2个点的连线的垂直平分线，如下图所示：
2个点的图片
为了更清楚，我把图片放大，以至于A，B点变成了圆，l为AB两点连线的垂直平分线。如图上所标，这时候只能考虑k=1d的时候的划分。一条垂直平分线可以把平面分成两个部分，左边红色的部分都会被归结为离A点近，右边的蓝色部分都会被归结于B点近。

那么如果我们考虑三个点的k近邻，如下图所示：

如果K=1，那么最终的分类就会是如此，蓝色的点都是被归于点A，红色的点都归于点B，紫色的点都归于点C，但是如果是K=2的时候呢？K=2的时候，只需要把垂直平分线延长就可以了，如下图：

三种颜色

为了区分归属，我把三个点都标上了颜色，而被划分的6个区域，其最近的2个点的颜色都在图上标出，其实就是一个二维层面的三次切分，取其中最近的2个点。这样就得到了空间划分。

实际上4个点，5个点，n个点都是同样的道理，这个算法不一定是最优的，但是是可以推广到n个点的普适算法，而且又由于k的取值不会过大，因此不会造成大数灾难。

你可能觉得很巧，为什么所有的垂直平分线都会交于一点，实际上，所有的凸多边体都会有一个外接圆，那么圆心到所有点的距离都相等，这就是所有边的垂直平分线的焦点。但是对于凹多边体，就没有外接圆了，但是也不用担心，空间中所有的部分都会被若干个垂直平分线所分割，只需要比较围成这个区域的n个垂直平分线，然后再根据k的取值取前K个点即可。

这样就解决了题目3.1。

4.4. kd树的若干改进算法

但是事实上，即使我们上面的Kd树可以完成k近邻的查找，但是对于大数据来讲，仍然是效率不够的。

4.4.1. BBF算法

那么一个最基本的改进就可以被提出了，那就是BBF（Best-Bin-First）查询算法。这个算法是由发明sift算法的David Lowe在1997的一篇文章中针对高维数据提出的一种近似算法，此算法能确保优先检索包含最近邻点可能性较高的空间，此外，BBF机制还设置了一个运行超时限定。采用了BBF查询机制后，kd树便可以有效的扩展到高维数据集上。

BBF算法的改进思路为：将“查询路径”上的结点进行排序，如按各自分割超平面（也称bin）与查询点的距离排序，也就是说，回溯检查总是从优先级最高（Best Bin）的树结点开始。

4.4.2. 球树

仅仅在kd树上进行BBF算法的改进，仍然还是不能够避免一些结构本身存在的弊端，当处理不均匀分布的数据集时便会呈现出一个基本冲突：既要求树有完美的平衡结构，又要求待查找的区域近似方形，但不管是近似方形，还是矩形，甚至正方形，都不是最好的使用形状，因为他们都有角。

其实这个问题的实质是因为，我们对于距离的度量使用的是圆形，也就是欧氏距离，如果是我们之前提到的像切比雪夫距离这种方形的，就可以在一定程度上减少这个冲突。因为无论是你的模板和样本，其度量标准是一致的，也就是要么是方形的，都是方形的，要是圆形的，都是圆形的。
例如下面这个就是球树：
在这里插入图片描述
从球中选择一个离球的中心最远的点，然后选择第二个点离第一个点最远，将球中所有的点分配到离这两个聚类中心最近的一个上，然后计算每个聚类的中心，以及聚类能够包含它所有数据点所需的最小半径。这种方法的优点是分裂一个包含n个殊绝点的球的成本只是随n呈线性增加。

使用球树找出给定目标点的最近邻方法是，首先自上而下贯穿整棵树找出包含目标点所在的叶子，并在这个球里找出与目标点最靠近的点，这将确定出目标点距离它的最近邻点的一个上限值，然后跟KD树查找一样，检查同胞结点，如果目标点到同胞结点中心的距离超过同胞结点的半径与当前的上限值之和，那么同胞结点里不可能存在一个更近的点；否则的话，必须进一步检查位于同胞结点以下的子树。

5. 小结

在本次讨论课上，我们对于K近邻算法有了一个直观的认识，并且针对一些特定的问题，我们也做了一些深入的了解和探究，但是这还远远不够，一些问题我们仍然没有展开来说，例如度量标准中的那些距离的具体表现形式，还有没有给出k近邻算法的一些实例，以及kd树的数据结构和实际运行代码。这些还需要大家在课后加以补充。好了，我们下期见。