这篇博客来总结一下k近邻法(k-nearest neighbor, K-NN)的相关内容。对K-NN并不能严格的从模型、学习准则和优化方法三方面进行总结，因为K-NN是一种无参数学习的算法，它是基于实例的，这就意味这K-NN并没有显式的学习模型，而是利用训练数据集对特征向量空间进行划分。所以在K-NN中，并没有对参数的学习准则和优化方法，优化更多是从模型层面来做的。

k近邻法(K-nearest neighbor)

1. 定义

​ 简单来说，k近邻法假设给定一个训练数据集，其中的实例类别已经确定。在对新的不确定类别的实例进行分类时，根据离其最近的k个训练实例的类别，通过多数表决等方式对其类别进行预测。由以上简单定义，我们可以得出，k值的选择、实例点间的距离度量和分类决策规则是k近邻法的三个基本要素，也是K-NN方法的核心部分。如下图所示，我们需要对图中两个叉点进行类别预测时，距离度量采用欧氏距离，$k=1$k=1，分类决策规则选择多数表决，则两个点的类别可以根据图中点的相对位置很容易的确定。但这只是低维的情况，如果数据维度增加，数据间的相对位置关系将不再那么容易直接看出。同时，随着数据维度和数据量的增加，采用简单的线性扫描方法通过比较待预测点和数据集中每个点的距离来得到距离最小点的时间复杂度将大大提高，这使得我们需要一种新的算法来更快的完成k个近邻点的选择过程，否则时间复杂度的快速提高将使得KNN在大数据上的应用变得无法实现。

​ 接下来给出k近邻法的数学定义和一个简单的算法流程：

​ 设输入数据集为$T=\{(x_{1},y_{1}),(x_{2},y_{2}),\cdots ,(x_{N},y_{N})\}$T={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)}，其中$x_{i}\in R^{n}$xi​∈Rn为实例的特征向量，$y_{i}\in \textbf{y}=\{c_{1},c_{2},\cdots ,c_{k}\}$yi​∈y={c1​,c2​,⋯,ck​}为实例的类别，$i=1,2,\cdots ,N$i=1,2,⋯,N；待预测的实例特征向量为$x$x;

​ 输出：实例$x$x所属的类别$y$y。

1. 根据给定的__距离度量方法__，在训练集$T$T中找出与$x$x最邻近的$k$k个点 ，涵盖这$k$k个点的$x$x的邻域记作$N_{k}(x)$Nk​(x)；

2. 在$N_{k}(x)$Nk​(x)中根据__分类决策规则__决定$x$x的类别$y$y。例如，当选择多数表决策略时，预测点的最终类别的数学定义如下：

   $y=\underset{c_{j}}{argmax}\ \ \sum_{x_{i}\in N_{k}(x)}I(y_{i}=c_{j}), \quad i=1,2,\cdots ,N;j=1,2,\cdots ,K$y=cj​argmax​  xi​∈Nk​(x)∑​I(yi​=cj​),i=1,2,⋯,N;j=1,2,⋯,K

   ​ 其中，$I$I为指示函数，即当$y_{i}=c_{j}$yi​=cj​时$I$I为1，否则$I$I为0。

   接下来，首先详细介绍一下K-NN的模型，再分别讨论K-NN算法的三个基本要素：距离度量、k值的选择和分类决策规则

2. K-NN模型

​ 在K-NN中，当训练集、距离度量、k值和分类决策规则确定后，对于一个新的输入实例，它所属的类别是唯一确定的。这等价于根据上述要素将特征空间划分为一些子空间，确定子空间里的每个点所属的类。具体来说，特征空间中的每个点的类别都是和与其相近的那些点相关的，所以这就要求我们能采用恰当的距离度量方法来找出与待预测点最接近的那些点，同时当前待预测点的类别究竟由几个与其最接近的点的类别决定，也是需要我们手动定义的。最后，在得到了会对待预测点的类别产生影响的k个最近点后，我们采用确定的分类决策规则来得到待预测点的最终类别。

​ 更形象一点来说，在特征空间中，对每个训练实例点$x_{i}$xi​，距离该点比其他点更近的所有点组成的一个区域，叫做__单元(cell)__。每个训练实例点都拥有这样一个单元，所有实例点的单元构成对特征空间的一个划分。显然，如果训练集或者距离度量方法发生变化，对特征空间的划分都将改变。一个对特征空间进行划分的例子如下图所示。

​

3. 距离度量

​ 特征空间中的两个实例点的距离实际上是两个实例点的相似程度的反映，距离越小说明两个实例点越相似，一般常用的距离度量方法总结如下。

3.1 闵可夫斯基距离(Minkowski Distance，也叫$L_{p}$Lp​距离)

​ 闵可夫斯基距离的一般定义为：

$L_{2}(x,y)=(\sum_{i=1}^{n}\left | x_{i}-y_{i}\right |^{p})^{\frac{1}{p}}$L2​(x,y)=(i=1∑n​∣xi​−yi​∣p)p1​

​ 闵可夫斯基距离比较直观，但是它与数据的分布无关，具有一定的局限性，如果 x 方向的幅值远远大于 y 方向的值，这个距离公式就 会过度放大 x 维度的作用。所以，在计算距离之前，我们可能还需要对数据进行 z-transform 处理，即减去均值，除以标准差（即 标准化欧式距离）。
　　这种方法在假设数据各个维度不相关的情况下利用数据分布的特性计算出不同的距离。如果维度相互之间数据相关（例如：身高较高的 信息很有可能会带来体重较重的信息，因为两者是有关联的），这时候就要用到马氏距离（Mahalanobis distance）了。

​ 根据p值的不同， 闵可夫斯基距离可以有几种不同的形式。

3.1.1 欧式距离(Euclidean distance)

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

​ $L_{2}(x,y)=(\sum_{i=1}^{n}\left | x_{i}-y_{i}\right |^{2})^{\frac{1}{2}}$L2​(x,y)=(i=1∑n​∣xi​−yi​∣2)21​

​ 欧几里得距离或欧几里得度量是欧几里得空间中两点间“普通”（即直线）距离 ， 是一个通常采用的距离定义，指在m维空间中两个点之间的真实距离，或者向量的自然长度（即该点到原点的距离） 。

3.1.2 曼哈顿距离(Manhattan Distance)

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

$L_{1}(x,y)=\sum_{i=1}^{n}\left | x_{i}-y_{i}\right |$L1​(x,y)=i=1∑n​∣xi​−yi​∣

曼哈顿距离为在欧几里德空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和 。 想象你在曼哈顿要从一个十字路口开车到另外一个十字路口，驾驶距离是两点间的直线距离吗？显然不是，除非你能穿越大楼。实际驾 驶距离就是这个“曼哈顿距离”,也称为城市街区距离(City Block distance) 。

3.1.3 切比雪夫距离(Chebyshev distance)

​ 当$p\rightarrow \infty $，称为切比雪夫距离：

$L_{\infty }(x,y)=\underset{i}{max}\left | x_{i}-y_{i} \right |$L∞​(x,y)=imax​∣xi​−yi​∣

​ 切比雪夫距离是向量空间中的一种度量，二个点之间的距离定义是其各坐标数值差绝对值的最大值 .

3.2 标准化欧式距离(Standardized Euclidean distance)

​ 当数据各维分量的分布尺度不一样时(比如第一维范围为$[1000,1000]$[1000,1000],第二维范围为$[0.1,1]$[0.1,1])，不同的维度对最终距离的贡献是不一样的，这有可能会造成某些维度对最终结果的影响接近于0，很显然，这并不是件好事，所以我们在很多时候需要提出一种度量策略，来平衡各个维度的尺度对最终距离的影响。标准化欧氏距离先将各个分量都“标准化”到均值、方差相等，这样就实现了尺度上的统一。假设样本集 $X$X的均值(mean)为 $m$m ，标准差(standard deviation)为 $s$s ， $X $的“标准化变量”表示为：

$X^{'}=\frac{X-m}{s}$X′=sX−m​

​ 则标准化后的欧氏距离为：

$L_{2}(x,y)=(\sum_{i=1}^{n}\left | \frac{x_{i}-y_{i}}{s_{i}} \right|^{2})^{\frac{1}{2}}$L2​(x,y)=(i=1∑n​∣∣∣∣​si​xi​−yi​​∣∣∣∣​2)21​

3.3 余弦相似度(Cosine Similarity)

​ 余弦相似度的定义如下：

$CosineSimilarity(x,y)=\frac{x\cdot y}{\left | x \right |\cdot \left | y \right |}$CosineSimilarity(x,y)=∣x∣⋅∣y∣x⋅y​

​ 余弦相似度更多的是从方向上区分差异，度量两个向量之间夹角的余弦值，而对绝对的数值不敏感。因此没法衡量每个维数值的差异，会导致这样一个情况：比如用户对内容评分，5分制，X 和 Y 两个用户对两个内容的评分分别为(1,2)和(4,5)，使用余弦相似度得出的结果是0.98，两者极为相似，但从评分上看 X 似乎不喜欢这2个内容，而 Y 比较喜欢，余弦相似度对数值的不敏感导致了结果的误差，需要修正这种不合理性，就出现了调整余弦相似度，即所有维度上的数值都减去一个均值，比如 X 和 Y 的评分均值都是3，那么调整后为(-2,-1)和(1,2)，再用余弦相似度计算，得到-0.8，相似度为负值并且差异不小，但显然更加符合现实。

​ 余弦距离的定义为：

​ $CosineDistance(x,y)=1-CosineSimilarity(x,y)$CosineDistance(x,y)=1−CosineSimilarity(x,y)

3.4 调整余弦相似度(Adjust Cosine Similarity)

​ 修正cosine相似度的目的是解决cosine相似度仅考虑向量维度方向上的相似而没考虑到各个维度的量纲的差异性，所以在计算相似度的时候，做了每个维度减去均值的修正操作。定义如下：

$L(x,y)=\frac{\sum_{i}^{n} ((x_{i}-m_{i})\cdot (y_{i}-m_{i}))}{\left | x \right |\cdot \left | y \right |}$L(x,y)=∣x∣⋅∣y∣∑in​((xi​−mi​)⋅(yi​−mi​))​

​ 其中，$m_{i}$mi​为所有数据第$i$i维的平均值。

3.3 马氏距离(Mahalanobis distance)

​ 这一块目前还不是太想看，就先留着大佬的链接( https://www.cnblogs.com/Zhouwl/p/9482874.html )，之后有空再来填坑吧。

​ 马氏距离的两个实例点之间的距离是和整体样本分布有关的，可以考虑各种特性之间的联系，同时可以不受量纲的影响，这和其他的距离度量方式不一样。

3.4 汉明距离(Hamming Distance)

​ 两个等长字符串 s1 与 s2 的汉明距离为：将其中一个变为另外一个所需要作的最小字符替换次数。 同时这里也可以了解一下__编辑距离__，都是度量字符串相似度的方法。

3.5 杰卡德距离(Jaccard Distance)

​ 杰卡德距离(Jaccard Distance) 是用来衡量两个集合差异性的一种指标，它是杰卡德相似系数的补集，被定义为1减去Jaccard相似系数。而杰卡德相似系数(Jaccard similarity coefficient)，也称杰卡德指数(Jaccard Index)，是用来衡量两个集合相似度的一种指标。

3.6 相关距离(Correlation distance)

​ 相关系数是衡量随机变量X与Y相关程度的一种方法，相关系数的取值范围是[-1,1]。相关系数的绝对值越大，则表明X与Y相关度越高。当X与Y线性相关时，相关系数取值为1（正线性相关）或-1（负线性相关）：

相关距离为：

4. k值的选择

​ k值的选择上，其实并没有太多理论的内容可以讨论，更多的还是要通过实验的方法，来确定适合当前数据集的最优k值。

k值	误差	缺点	结果
较小的值	近似误差减小，估计误差增大	预测结果会对邻近的实例点非常敏感	模型变复杂，容易发生过拟合
较大的值	近似误差增大，估计误差减小	与待预测点较远的(不相似的)训练实例也会对预测起作用	模型变简单，容易发生欠拟合

5. 分类决策规则

​ 在得到与待预测点最近的k个最近邻点的标签后，就需要根据分类决策规则确定待预测点的类别

• 多数表决规则：这种规则很好理解，其实就是将k个最近邻点中包含实例点最多的类别作为待预测点的预测类别。当然，这里还需要解决一个问题，就是当有多个类别对应的实例点数相等且最大时，我们应该选择哪种类别作为待预测点的类别。
• 核方法：多数表决规则只考虑了k个近邻点的类别信息，而没有考虑近邻点和待预测点之间的距离信息。但直观上，我们可以知道，和待预测点距离较近的那些点对最终结果的影响应该比那些距离较远的点更大。核方法的引入，可以在进行决策时将两个点之间的距离信息考虑进来。简单而言，其实就相当于通过核函数给每个点对应的标签加一个权重，这个权重和距离成反比，距离越大权重越小，距离越小权重越大。
  

6. k近邻法的实现：kd树

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

k-NN中的k和kd树中的k意义是不同的：

• k-NN中的k表示的要选择k个近邻点
• kd树中的k表示树中存储的数据的维度为k维

​ 下面分别来说明一下kd树的构建过程和搜索kd树找到k个近邻点的过程

6.1 kd树的构建

​ 首先，要明确的是最终构建的kd树是一棵平衡二叉排序树，保证树是平衡能得到最好的搜索效率。那么问题来了：

1. 如何选择排序的标准？
2. 如何保证树是平衡的？

​ 针对第一个问题，kd树中的排序标准为实例点中某一维的值。那么在构建子树时应该选择哪一维作为排序标准呢？最简单的情况当然是顺序选择数据的维度作为排序标准，即在kd树中深度为$j$j的节点选择的维度$d$d为$d=j(mod \ \ k) + 1$d=j(mod  k)+1。我们也可以采用__最大方差法__找到当前数据域中方差最大的一维作为排序标准，方差越大说明数据越分散，那我们可以更容易的将其中的数据分开。

​ 至于第二个问题，当我们确定当前深度采用哪一维作为排序标准后，我们只需要取这一维的中位数对应的点作为当前子树的根节点，即可保准二叉树的平衡性。

构造平衡kd树的过程如下：

​

​ 下面给出一个例子说明一下这种通过超平面来分隔超矩形空间的例子。给定一个二维空间的数据集：

$T=\{ (2,3)^{T},(5,4)^{T},(9,6)^{T},(4,7)^{T},(8,1)^{T},(7,2)^{T} \}$T={(2,3)T,(5,4)T,(9,6)T,(4,7)T,(8,1)T,(7,2)T}

​ 结果如下图所示，给出了划分超平面中的点在kd树中的深度和二维平面的划分结果。

6.2 kd树的最近邻搜索

​ kd树的搜索过程：给定一个目标点，搜索其最近邻。首先找到包含目标点的叶节点；然后从该叶节点出发，依次退回到父节点；不断查找与目标点最邻近的节点，当确定不可能存在更近的结点时终止。这样的搜索就被限制在空间的局部区域上，效率大为提高。

​ 利用kd树进行k近邻搜索，可以省去对大部分数据点的搜索，这个过程其实就是一个对二叉树的剪枝过程，我们基于一定的策略剪掉那些一定不会存在更优解的子树，这样在平均情况下能大大提高kd树的搜索效率。

​ kd树的最近邻搜索过程如下：

​

​ 这个算法中，有两个问题需要重点关注：

1. 为什么需要有(1)步，首先找到目标点对应的划分子空间？
2. 在回溯的过程中，如果确定是否需要对当前节点的父节点的另一棵子树进行遍历

​ 第一个问题，需要有(1)步是为了剪枝的考虑。当我们首先将目标点定位到其对应的划分子空间后，一般情况下，目标点对应划分空间中的节点有很大概率会是最近点或者离最近点非常近的点，这样有助于算法能尽可能多的实现剪枝。

​ 针对第二个问题，其实也很好理解，首先我们知道算法需要寻找的是比当前最小距离更小的点，我们只需要确定当前目标点和最短距离确定的搜索域和当前节点的父节点的另一棵子树对应的区域有没有交集即可，如果没有交集，则可以进行剪枝，因为那个区域中所有的点到目标点的距离都会大于当前最小距离。如果有交集，则需要对另一棵子树进行遍历，首先找到从当前维度起目标节点在该子树中对应的划分区域，然后重复回溯过程。下面两个图能帮助我们更好的理解，很明显可以看出，当没有交集时，我们是不需要考虑由$y=4$y=4划分出的上方超平面的，而有交集时，我们需要考虑这个超平面中是否存在更近点。

6.3 将最近邻搜索推广到k近邻搜索

​ 其实这也是一个很简单的过程，我们只需要在递归的过程中首先选定最早遇到的k各点作为候选k近邻点，然后根据这k个点到目标点的距离进行排序，每次只更新到目标点距离最大的那个点即可。因为kd树中每个节点只保存一个数据，所以我们每次必定只能选择是否更新到目标点距离最大的那个点，如果当前点到目标点的距离小于这个值则进行更新，然后重新排序，否则不更新。这个过程其实和最近邻搜索是完全一样的，只是在初始化时，先选出了k个候选。

References

1. K近邻算法的kd树实现
2. ML笔记：机器学习中的几种距离度量方法比较
3. 李航《统计学习方法 第二版》
4. 距离度量方法