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

第三章K近邻K-近邻算法（K-NearestNeighbor，KNN）是一种基于一定距离测度的抽样检验方法，属于监督学习，所以使用算法时必须有已知标记的训练集。K-近邻算法既可用于分类也可用于回归。在处理分类问题时，该方法只依据最邻近的一个或者几个样本的类别来决定待分类样本所属的类别。处理回归问题的流程与分类问题相似，区别在于样本的输出标记为距离其最近的一个或者几个样本的标记的加权平均值。1

3.1算法原理在分类问题中，给定一个训练数据集，对于任何一个待分类样本，在训练数据集中找到与该样本最邻近的K个样本（也就是最近的K个邻居），那么即可以使用这K个样本中的多数类别标记作为待分类样本的类别标记。特别的，必须保证训练数据集中的每个样本都有类别标记。在回归问题中，样本的标记为连续变量，因此一般将待处理样本的K个最近邻的标记的加权平均值作为输出（以距离的倒数为权重）。除此之外，还可以指定一个半径，将半径范围内的全部邻居的标记的加权平均值作为输出。2

3.1算法原理图中的样本有两个类别，分别以正方形和三角形表示，而图正中间的圆形代表待分类样本。 首先假设我们选择K的值为3，圆形样本最近的3个邻居是2个三角形和1个正方形，少数从属于多数，基于统计的方法，判定这个待分类样本属于三角形一类。 如果我们选择K的值为5，那么圆形样本最近的5个邻居是2个三角形和3个正方形，还是少数从属于多数，可以判定这个待分类点属于正方形一类。3

3.1算法原理K-近邻算法的基本流程为：1）计算已经正确分类的数据集中每个样本与待分 类样本之间的距离；2）按照距离递增次序对数据集中的样本排序；3）选取与待分类样本距离最小的K个样本；4）确定该K个样本所在类别的出现频率；5）返回该K个样本出现频率最高的类别作为待分 类样本的预测类别。4

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

3.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.1k-d树 k-d树（k-dimensionalTree）是针对暴力搜索效率低下而提出的基于树的数据结构。 基本思想：若A点距离B点非常远，B点距离C点非常近，可知A点与C点很远，因此不需要准确计算它们之间的距离。通过这种方式，对于具有k个特征的n个样本来说，近邻搜索的计算成本可以降低至O[knlog(??)]以下，可以显著改善暴力搜索在大样本容量数据集中的表现。12

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

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

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

3.3.1k-d树k-d树的构建过程可以总结为：1）构造根