机器学习算法与实践 课件 第3章 K近邻

第三章K近邻K-近邻算法（K-NearestNeighbor，KNN）是一种基于一定距离测度的抽样检验方法，属于监督学习，所以使用算法时必须有已知标记的训练集。K-近邻算法既可用于分类也可用于回归。在处理分类问题时，该方法只依据最邻近的一个或者几个样本的类别来决定待分类样本所属的类别。处理回归问题的流程与分类问题相似，区别在于样本的输出标记为距离其最近的一个或者几个样本的标记的加权平均值。13.1算法原理在分类问题中，给定一个训练数据集，对于任何一个待分类样本，在训练数据集中找到与该样本最邻近的K个样本（也就是最近的K个邻居），那么即可以使用这K个样本中的多数类别标记作为待分类样本的类别标记。特别的，必须保证训练数据集中的每个样本都有类别标记。在回归问题中，样本的标记为连续变量，因此一般将待处理样本的K个最近邻的标记的加权平均值作为输出（以距离的倒数为权重）。除此之外，还可以指定一个半径，将半径范围内的全部邻居的标记的加权平均值作为输出。23.1算法原理图中的样本有两个类别，分别以正方形和三角形表示，而图正中间的圆形代表待分类样本。

首先假设我们选择K的值为3，圆形样本最近的3个邻居是2个三角形和1个正方形，少数从属于多数，基于统计的方法，判定这个待分类样本属于三角形一类。

如果我们选择K的值为5，那么圆形样本最近的5个邻居是2个三角形和3个正方形，还是少数从属于多数，可以判定这个待分类点属于正方形一类。33.1算法原理K-近邻算法的基本流程为：1）计算已经正确分类的数据集中每个样本与待分

类样本之间的距离；2）按照距离递增次序对数据集中的样本排序；3）选取与待分类样本距离最小的K个样本；4）确定该K个样本所在类别的出现频率；5）返回该K个样本出现频率最高的类别作为待分

类样本的预测类别。43.1算法原理K值的选择会对算法的结果产生重大影响：K值较小意味着只有与待分类样本较近的已知样本才会对预测结果起作用，但容易发生过拟合K值较大可以减少学习的估计误差，但是学习的近似误差增大，因为这时与待分类样本较远的已知样本也会对预测起作用，容易使预测发生错误。K值一般选择一个奇数值，因为算法中的分类决策规则往往是多数表决，奇数取值可防止出现邻居中不同类别样本数量相等的情况。53.2距离度量方法

在K-近邻算法以及其他很多机器学习算法中都会涉及到距离的计算，距离度量方式对算法的性能有很大的影响。

常用的距离计算方式如下： 1.闵科夫斯基距离（Minkowskidistance） 2.欧几里德距离（Euclideandistance） 3.曼哈顿距离（Manhattandistance） 4.切比雪夫距离（Chebyshevdistance） 5.余弦相似度（Cosinesimilarity） 6.皮尔逊相关系数（Pearsoncorrelationcoefficient） 7.杰卡德相似系数（Jaccardsimilaritycoefficient） 8.马氏距离（Mahalanobisdistance）6

3.2距离度量方法

7

3.2距离度量方法

8

3.2距离度量方法

9

3.2距离度量方法

10

3.3搜索优化方法

当数据集和特征数量较大时，K-近邻算法的距离计算成本可能会较高。在近邻搜索的过程中，算法会有较高的计算成本。因此，为了提高K-近邻算法的搜索效率，可以考虑使用特殊的结构来存储已知样本，以减少距离计算的次数。11

3.3.1

k-d树 k-d树（k-dimensionalTree）是针对暴力搜索效率低下而提出的基于树的数据结构。

基本思想：若A点距离B点非常远，B点距离C点非常近，可知A点与C点很远，因此不需要准确计算它们之间的距离。通过这种方式，对于具有k个特征的n个样本来说，近邻搜索的计算成本可以降低至O[knlog(𝑛)]以下，可以显著改善暴力搜索在大样本容量数据集中的表现。12

3.3.1

k-d树例1：假设数据集有2个特征、6个样本，如T={(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}。使用k-d树算法确定样本点的划分空间分割线。

13

3.3.1

k-d树首先，选择划分特征，即确定分割线是垂直于X轴还是Y轴。分别计算X轴和Y轴方向样本的方差，得知X轴方向的方差最大，所以首先对X轴进行划分，确定分割线的X轴坐标。然后基于上述步骤，对Y轴进行同样划分操作。14

3.3.1

k-d树最后，对依然有样本存在的子空间再按X轴进行划分，直至子空间不再有样本为止。由于此时的每个子空间仅包含一个样本，因此可直接按剩余样本划分空间区域。15

3.3.1

k-d树k-d树的构建过程可以总结为：1）构造根结点，使根结点对应于k维空间中包含所有样本点的超矩形区域；2）通过递归的方法，不断地对k维空间进行切分，生成子结点。3）重复上述过程直到子区域内没有样本时终止。在此过程中，将样本保存在相应的结点上。4）通常，循环的依次选择坐标轴对空间切分。16

3.3.1

k-d树构建k-d树时，关键需要解决2个问题：1）选择向量的哪一维进行划分？2）如何划分数据？对于第一个问题，简单的解决方法可以是随机选择某一维或按顺序选择，但是更好的方法应该是在数据比较分散的那一维进行划分。好的划分方法可以使构建的树比较平衡，可以每次选择中位数来进行划分，这样第二个问题也得到了解决。17

3.3.1

k-d树如何利用k-d树进行最近邻搜索？

18

3.3.1

k-d树如何利用k-d树进行最近邻搜索？

接着，由于被搜索点的划分维度值3小于当前节点的划分维度的值7，因此将当前节点的左子节点(5,4)作为新的当前节点。由于此时当前节点到被搜索点的距离为2.83，小于全局最短距离，所以更新当前最佳点为(5,4)。19

3.3.1

k-d树如何利用k-d树进行最近邻搜索？

继续下去，由于被搜索点的划分维度值2小于当前节点的划分维度值4，因此设当前节点的左子节点(2,3)为新的当前节点。由于此时当前节点到被搜索点的距离为1.41，小于全局最短距离，所以更新当前最佳点为(2,3)，全局最短距离为1.4120

3.3.1

k-d树如何利用k-d树进行最近邻搜索？

21

3.3.1

k-d树如何利用k-d树进行最近邻搜索？

22

3.3.2球树 k-d树算法虽然提高了K-近邻算法的搜索效率，但在处理非均匀数据集和高维数据时也会出现效率不高的情况。为了优化k-d树的算法策略，提出了球树模型。

球树将数据递归地划分为由质心c和半径r定义的节点，每个结点本质上是一个空间，包含了若干个样本点，每个空间内有一个独一无二的中心点23

3.3.2球树

24

3.3.2球树

首先建立根节点，找到包含所有样本点的超球体，记录球心位置，作为根节点。然后，找到所有点中距离最远的两个点，并判断其他样本点与这两个点的距离，距离哪个点最近，则将该样本点划分到该点的类内，这两个类即是根节点的左子节点和右子节点。分别对两个子节点构建超球体，记录球心坐标和半径。25

3.3.2球树重复上述过程直至样本全部划分完毕26

3.4本章小结本章主要介绍了K-近邻算法，给出了其在处理分类和回归问题时的原理和流程，并介绍了k-d树和球树两种提升K-近邻搜索效率的方法。K-近邻算法简单易懂且实用，但是因为每一次分类或者回归，都要把已知数据样本和测试样本的距离全部计算一遍并搜索其中最近的K个邻居，在数据量和数据维度很大的情况下，需要的计算资源会十