基于距离度量的K近邻基本分类算法研究

张大伟 李明艳

（北海职业学院 广西·北海 536000）

0 引言

K近邻分类算法（KNN，K-NearestNeighbor）是数据分类技术中最传统的算法之一，它是由Cover和Hart在1968年提出来的。所谓K最近邻，就是未知样本周边K个最近的邻居的意思，意为每个未知样本都可以用它最接近的K个邻近值来表示，俗语“你的薪水约是你最好的6个朋友的平均薪水”与K近邻分类算法有异曲同工之妙。K近邻分类算法以其稳定性好、准确率高等特点广泛的应用于分类与回归。[1]

1 距离度量

在数学中，欧几里得距离（度量）是欧几里得空间中两点间“普通”（即直线）距离。欧几里得距离也称欧氏距离，在数据分析及挖掘中经常被提及，例如聚类或计算相似度。[2]曼哈顿距离是几何学用语，由十九世纪的明可夫斯基首先提出，其用来标明两个点在标准坐标系上的绝对轴距总和。

曼哈顿距离是指在曼哈顿城市中，从一个红绿灯驾车到另外一个路口的距离，也称为城市街区距离。图1中蓝色实线是曼哈顿距离，红色虚线代表欧氏距离，也就是直线距离，而紫色和绿色代表等价的曼哈顿距离。[3]如下所示公式1和公式2分别代表欧氏距离和曼哈顿距离的计算方法，其中a和b代表两个点。

图1：曼哈顿距离与欧氏距离

2 K近邻分类算法

2.1 K近邻分类算法定义

K近邻分类算法是对“近朱者赤近墨者黑”这句话的完美诠释。若要判断某个未知样本属于哪个分类，只需要找到最接近该样本的K个邻居，这些邻居中哪种分类占比最大，K近邻分类算法就认为该样本就属于此分类。[6]如图2所示在K=3的时候（内圆与绿色有3个最近的图形，2个红色三角形）K近邻分类算法推测绿色的圆形是红色三角形；同理在K=5的时候（外圆与绿色有5个最近的图形，3个蓝色矩形）K近邻分类算法将推测绿色圆形为蓝色矩形。

图2：K近邻分类算法原理

2.2 K近邻算法的计算过程

K近邻分类算法本质上是一种统计学习方法，在程序运行时数据集就被加载到内存开始分类，从而无须进行前期训练。在判断未知的样本时，以该样本为中心寻找与其最接近的K个元素进行判断，通常K是一个不大的整数，根据实际需要进行限定。[7]

K近邻分类算法的计算过程：

（1）利用距离算法（如明可夫斯基距离）度量未知样本与已知样本之间的距离；

（2）对所有样本按距离递增排序；

（3）选取与未知样本距离最小的K个点；

（4）计算前K个样本所属类别的数量；

（5）统计出K个样本中，出现频率最高的类别作为未知样本的预测分类。

2.3 距离的度量方式对K近邻分类算法的影响

K近邻分类算法主要任务是基于距离度量，找出与未知（被测）样本距离最近的K个点，其三个基本要素：K值的选择、距离度量以及分类决策规则。距离的度量是对训练样本与测试样本相似程度的描述，这个相似程度就是K个样本选择的依据，在K近邻分类算法中，如果特征是连续的，那么距离度量一般用明可夫斯基距算法；如果特征是离散的，一般采用其它的距离度量算法，如汉明距离。[8]运用K近邻分类算法进行分类预测时，距离的度量算法不同，得到的结果可能不同。因此，在实际应用中需要对数据集的分类结果进行评价（这是评估模型存在的价值），从而采取最优的距离度量算法。[9]

2.4 K值的选择对分类结果的影响

如果选择较小的K值，就相当于用较小的领域中的训练实例进行预测，“学习”的近似误差会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是“学习”的估计误差会增大，换句话说，K值的减小就意味着整体模型变得复杂，容易发生过拟合，（偏差小方差大）；如果选择较大的K值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少学习的估计误差，但缺点是学习的近似误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，且K值的增大就意味着整体的模型变得简单。[10]

3 结语

K近邻分类算法优点非常突出，其理论成熟、精度高且简单易于理解，既可以用于分类又可以用于回归在机器学习中有着较高的利用；但其缺点与优点一样突出，其计算复杂度和空间复杂度都较高适用于数值型和标称型的数据。在实际应用中采取不同的K值或不同的距离度量方法都有可能影响最终的分类结果，良好的评价模型结合实际的情况预估是提高分类有效率的不可或缺的方法。