机器学习原理与应用课件 第6章 K近邻

第6章K近邻1学习目标理解K近邻算法的基本原理掌握利用Scikit-learn库构建K近邻分类器的基本流程122目录页36.1基本原理6.2应用实例K近邻6.1基本原理K近邻是1967年由美国信息理论家科弗（ThomasCover）与计算机科学家哈特（PeterHart）提出的一种基于模板匹配思想的的分类方法，其基本原理可描述为：在特征空间中，若与新样本最相近的K个已分类样本中的大多数样本属于某一个类别，则新样本也属于该类别。一般情况下，K通常设置为不大于20的奇数。4ThomasCoverPeterHart6.1.1基本概念已知训练样本中每个样本对应的类别，当对新样本进行分类时，首先计算新样本与训练样本中每个样本之间的距离或特征相似度，进而从训练样本中提取K个与新样本距离最近（即在特征空间中最邻近）或特征最相似的样本，然后统计此K个样本所属类别并将对应样本数最多的类别标记分配给新样本。5K近邻算法分类原理6.1.1基本概念K近邻算法的基本流程如下：（1）计算新样本与所有已分类样本之间的特征距离（如欧氏距离、曼哈顿距离等）。（2）按照递增次序对特征距离进行排序。（3）选择K个特征距离最相近的已分类样本（K值一般设置为奇数）。（4）确定K个已分类样本所属类别及相应样本的数量。（5）将K个已分类样本所属类别相应样本数最多的类别作为新样本的类别。6

6.1.2KD树KD树是一种利用二叉树对K维空间中的样本点进行存储与快速检索的数据结构，每个非叶节点对应于垂直于坐标轴的超平面，多级二叉树则构成K维超矩形空间或区域。7

6.1.2KD树KD树在使用前应先根据已知数据对其进行构造。具体而言，若样本集包含K维特征，首先计算每个特征取值的方差并选择方差最大的特征作为KD树的根节点，然后以该特征取值的中位数作为阈值对样本集中的样本进行划分以生成左子树与右子树（即：若样本在该特征维度的取值小于阈值则分至左子树，否则则分至右子树）。对于左子树与右子树，分别采用类似方式持续对相关样本进行划分，则可以递归的方式生成KD树。8

6.1.2KD树KD树的构建过程：以二维样本{(3,1),(2,7),(8,5),(6,9),(5,3),(8,8)}（1）根节点：计算X与Y轴相应特征取值的方差，其结果分别为6.3与9.5；由于Y轴相应特征的方差最大，因而依据Y轴相应特征构建KD树根节点。具体而言，由于Y轴相应特征取值（即1、3、5、7、8与9）中，7为中位数，故以Y=7为轴将二维空间划分为上、下两个区域并选择样本(2,7)作为KD树的根节点。（2）左右子树：对于除根节点(2,7)之外的其他样本，将位于上、下两个区域的样本分别划分为左子树节点{(3,1),(5,3),(8,5)}（X与Y轴方差分别6.3与4）及右子树节点{(8,8),(7,9)}（X与Y轴方差分别2与0.5）。（3）循环执行步骤1-2对确定左右子树的根节点及其左右子树直至左右子树无法再分割。9

6.1.2KD树KD树的构建过程：以二维样本{(3,1),(2,7),(8,5),(6,9),(5,3),(8,8)}10(2,7)(5,3)(8,8)(3,1)(8,5)(7,9)(2,7)(5,3)(3,1)(8,5)(7,9)(8,8)(Y)(X)(a)KD树对应二维空间划分(b)KD树结构6.1.3常见问题（1）数据不平衡问题当所属不同类别的样本数量偏差较大时（即样本不平衡），易导致K近邻算法失败。例如，一个类别的样本数量很大，而其他类别的样本数量很小，则新样本的K个近邻样本更可能属于样本数量较大的类别，因而会将其错分至样本数量较大的类别。如图6-3(a)所示，在对黑方点所示新样本分类时，如果将K值设置为3且以已知类别的样本数量作为标准判别新样本的所属类别，则黑方点将被错分至白圆点所属类别（实际应分至距离其最近的黑圆点所属类别）。116.1.3常见问题

12451

6.1.3常见问题（2）距离类型在特征空间中，两样本之间的距离表示两样本相应特征之间的相似度，其度量方式可采用曼哈顿距离、欧氏距离、马式距离等多种类型；由于不同类型的距离适用场合的差异（如欧氏距离适于样本之间的绝对距离度量，而马式距离则适于考虑特征之间依存关系时样本之间的距离度量），因而可能导致相应的邻近样本不同及后续分类结果的不同。136.1.3常见问题（3）特征取值的差异特征取值的差异也可能导致样本之间距离计算的不可靠，例如，包含体重与身高特征的特征向量X_1=[80,1.70]与X_2=[60,1.65]，当利用曼哈顿距离（或欧氏距离）计算两者之间的相似度时，身高特征所占的比重几乎可以忽略不计（即：D(X_1,X_2)=|80-60|+|1.70-1.65|=20.05≈20），因而将由于不能真实地反映身高特征对样本分类的影响，导致样本分类错误。146.1.3常见问题（3）特征取值的差异此问题的解决方法是将不同特征的取值变换至同一数量级或尺度下（如采用数据标准化或归一化方法对特征取值进行预处理），消除其间差异以提高模型训练或参数求取的可靠性。156.1.3常见问题（4）K值的选择在K近邻算法中，K值的选择会对K近邻算法的可靠性产生较大的影响。如图6-4所示，当K值设置为5时，黑方点所属类别标记将分配给白圆点，这与K值设置为3时的分类结果恰恰相反。事实上，如果K值较小，相当于用较小邻域内的已知类别样本预测新样本所属类别，因而对近邻的样本非常敏感，一旦出现噪点，结果即会出错。另一方面，如果K值较大，虽然可减小噪声的影响，相当于用较大邻域内的已知类别样本进行预测，此时距离新样本较远的已知类别样本也会对预测结果产生影响，进而导致预测结果错误。16知识拓展

17知识拓展

18知识拓展

19知识拓展（6）汉明距离:两个等长字符串之间的汉明距离是其对应位置不同字符的个数(如1011101与1001001之间的汉明距离是2,2143896与2233796之间的汉明距离是3,)。

20知识拓展

21知识拓展

22知识拓展

236.2应用实例Scikit-learn库包含KNeighborsClassifier（利用K个距离新样本最近的已知类别样本对新样本分类）与RadiusNeighborsClassifier（利用距离新样本指定半径内的已知类别样本对新样本进行分类）两种不同类型的K近邻分类模型，本节以KNeighborsClassifier为例描述其应用方法。导入方法：fromsklearn.neighborsimportKNeighborsClassifier函数原型如下：KNeighborsClassifier(n_neighbors=5,weights='uniform',algorithm='auto',leaf_size=30,p=2,metric='minkowski',metric_params=None,n_jobs=1,**kwargs)246.2.1参数分析在特征空间，相邻样本之间的特征相似度越高，其越可能属于同一类别；其中，以样本之间距离的倒数作为样本分类权重，可在一定程度上解决样本不均衡问题以提高K近邻分类的精度。（1）问题描述构造仿真数据并利用K近邻算法对其进行分类，具体要求如下：①以可视化的方式描述不同加权方式对精度的影响。②绘制不同类别之间的分类边界。（2）编程实现见6.2.1参数分析.py256.2.1参数分析（3）结果分析['A''B''B''A''B''B''A''B']在此例中，训练样本集前4个样本A类（圆形点）、后3个为B类（方形点）；在利用K近邻分类器对测试样本（三角形点）进行分类后，测试样本显示为圆形点（A点）或方形点（B类）。从K近邻分类器采用不同权重时的对应结果可知，序号为4的测试样本在采用“距离倒数”权重时被分至B类，而在采用“相同”权重时却被错分A类，因而，采用“距离倒数”权重时的精度相对更高。26(a)测试样本(b)距离倒数权重

(b)相同权重6.2.2学生就业安置预测学生就业安置预测是高校学生管理工作的重要构成部分，根据学生学习表现、个人技能等信息对其就业安置情况进行分析，对提高高校学生管理工作的质量具有重要作用。表6-3所示为学生的累计平均绩点与简历分值（F1，累计平均绩点；F2，简历分值）相关数据，利用K近邻分类器对其就业安置情况（0，未安置；1，安置）进行预测。（1）问题描述加载表6-3所示数据以构建并测试K近邻分类器，具体要求如下。①

利用交叉验证的方式确定最优K值并构建与测试相应的K近邻分类器。②

分析不同特征之间的相关性。③

对K近邻分类器预测的不同类别之间的边界进行可视化。（2）编程实现见6.2.2学生就业安置预测.py276.2.2学生就业安置预测（3）结果分析样本数与特征数(60,2)预测精度:0.92F1与F2之间的相关性:-0.009124081118932457286.2.2学生就业安置预测（3）结果分析在利用K近邻算法对样本进行分类时，过小的K值易导致分类器对噪声较为敏感，而过大的K值则易导致分类器辨识能力较低，均不利于生成较好的结果。29(a)利用交叉验证选择最优K值(b)预测分类边界与样本真实类别6.2.3KD树应用KD树是一种用于对K维空间中的数据进行划分与组织的二叉树型数据结构，其中每个节点代表一个K维空间中的一个点，而节点的左子树与右子树分别代表其左边和右边的子空间。在数据量及维度较高时，相对于K近邻分类器，KD树通常具有更高的效率。Scikit-learn库包含KDTree模块，其导入方法如下：classsklearn.neighbors.KDTree(X,leaf_size=40,metric='minkowski',**kwargs)306.2.3KD树应用（1）问题描述利用make_blobs数据构建KD树并查询指定数据点的近邻点，具体要求如下：①根据指定近邻点数量查询近邻点。②根据指定半径查询相应范围内的近邻点。③比较KD树生成的近邻点与K近邻分类器生成的近邻点之间的差异。④对指定数据点及其近邻点进行可视化。（2）编程实现见6.2.3KD树应用.py31

6.2.3KD树应用（3）结果分析近邻点序号(KD树-数量):[[2013162721]]近邻点距离与样本点之间的距离(KD树-距离):[[0.0.973343881.141874111.401798851.57143472]]近邻点序号(KD树-半径):[array([16,27,20,13],dtype=int64)]近邻点距离与样本点之间的距离(KD树-半径):[array([1.14187411,1.40179885,0.,0.97334388])]近邻点序号(KNN-数量):[[2013162721]]近邻点距离与样本点之间的距离(KNN-距离):[[0.0.973343881.141874111.401798851.57143472]]32

6.2.3KD树应用（3）结果分析对于指定数据点及其近邻数，KD树与常规K近邻分类器生成的近邻点相同，而在指