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

第6章K近邻1

学习目标理解K近邻算法的基本原理掌握利用Scikit-learn库构建K近邻分类器的基本流程122

目录页36.1基本原理6.2应用实例K近邻

6.1基本原理K近邻是1967年由美国信息理论家科弗（ThomasCover）与计算机科学家哈特（PeterHart）提出的一种基于模板匹配思想的的分类方法，其基本原理可描述为：在特征空间中，若与新样本最相近的K个已分类样本中的大多数样本属于某一个类别，则新样本也属于该类别。一般情况下，K通常设置为不大于20的奇数。4ThomasCoverPeterHart

6.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且以已知类别的样本数量作为标准判别新样本的所属类别，则黑方点将被错分至白圆点所属类别（实际应分至距离其最近的黑圆点所属类别）。11

6.1.3常见问题?12451?

6.1.3常见问题（2）距离类型在特征空间中，两样本之间的距离表示两样本相应特征之间的相似度，其度量方式可采用曼哈顿距离、欧氏距离、马式距离等多种类型；由于不同类型的距离适用场合的差异（如欧氏距离适于样本之间的绝对距离度量，而马式距离则适于考虑特征之间依存关系时样本之间的距离度量），因而可能导致相应的邻近样本不同及后续分类结果的不同。13

6.1.3常见问题（3）特征取值的差异特征取值的差异也可能导致样本之间距离计算的不可靠，例如，包含体重与身高特征的特征向量X_1=[80,1.70]与X_2=[60,1.65]，当利用曼哈顿距离（或欧氏距离）计算两者之间的相似度时，身高特征所占的比重几乎可以忽略不计（即：