k-近邻分类算法

I K近邻算法

算法介绍：

K最近邻(k-Nearest neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。

KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。 该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。可以采用权值的方法（和该样本距离小的邻居权值大）来改进。

该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。

1

近邻方法是在一组历史数据记录中寻找一个或者若干个与当前记录最相似的历史纪录的已知特征值来预测当前记录的未知或遗失特征值。近邻方法是数据挖掘分类算法中比较常用的一种方法。K 近邻算法（简称 KNN）是基于统计的分类方法。KNN 分类算法根据待识样本在特征空间中 K 个最近邻样本中的多数样本的类别来进行分类，因此具有直观、无需先验统计知识、无师学习等特点，从而成为非参数分类的一种重要方法。

机器学习经典分类算法——k-近邻算法（附python实现代码及数

据集）⽬录

⼯作原理

存在⼀个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每⼀数据与所属分类的对应关系。输

⼊没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进⾏⽐较，然后算法提取样本集中特征最相似数据（最近邻）的分

类特征。⼀般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不⼤于20的整数。最后选择k个最

相似数据中出现次数最多的分类，作为新数据的分类。

举个例⼦，现在我们⽤k-近邻算法来分类⼀部电影，判断它属于爱情⽚还是动作⽚。现在已知六部电影的打⽃镜头、接吻镜头以及电影评估类型，如下图所⽰。

现在我们有⼀部电影，它有18个打⽃镜头、90个接吻镜头，想知道这部电影属于什么类型。根据k-近邻算法，我们可以这么算。⾸先计算未

知电影与样本集中其他电影的距离（先不管这个距离如何算，后⾯会提到）。现在我们得到了样本集中所有电影与未知电影的距离。按照距

离递增排序，可以找到k个距离最近的电影。

现在假定k=3，则三个最靠近的电影依次是He's Not Really into Dudes、Beautiful Woman、California Man。

k-近邻算法按照距离最近的三部电影的类型，决定未知电影的类型，⽽这三部电影全是爱情⽚，因此我们判定未知电影是爱情⽚。python实现

⾸先编写⼀个⽤于创建数据集和标签的函数，要注意的是该函数在实际⽤途上没有多⼤意义，仅⽤于测试代码。

def createDataSet():

group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])

labels = ['A','A','B','B']

return group, labels

然后是函数classify0()，该函数的功能是使⽤k-近邻算法将每组数据划分到某个类中，其伪代码如下：

ＩＳＳＮ　１００４—９０３７，ＣＯＤＥＮ　ＳＣＹＣＥ４　Ｊｏｕｒｎａｌ　ｏｆ　Ｄａｔａ　Ａｃｑｕｉｓｉｔｉｏｎ　ａｎｄ　Ｐｒｏｃｅｓｓｉｎｇ　Ｖｏ１．３２，Ｎｏ．６，Ｎｏｖ．２０１７，ＰＰ．１１５３—１１６２　ＤＯＩ：１０．１６３３７／ｊ．１００４—９０３７．２０１７．０６．０１０　◎２０１７　ｂｙ　Ｊｏｕｒｎａｌ　ｏｆ　Ｄａｔａ　Ａｃｑｕｉｓｉｔｉｏｎ　ａｎｄ　Ｐｒｏｃｅｓｓｉｎｇ　

基于分层抽样的ｋ近邻分类加速算法　

宋云胜　梁吉业　ｈｔｔｐ：／／ｓｊｃｊ．ｎｕａａ．ｅｄｕ．ｃｎ　Ｅ—ｍａｉｌ：ｓｉｃｊ＠ｎｕａａ．ｅｄｕ．ｃｎ　Ｔｅｌ／Ｆａｘ：４－８６—０２５—８４８９２７４２　

（１．山西大学计算机与信息技术学院，太原，０３０００６；２．山西大学计算智能与中文信息处理教育部重点实验室，太原，　

０３０００６）　

摘　要：ｋ近邻（ｋ　ｎｅａｒｅｓｔ　ｎｅｉｇｈｂｏｒ，ｋＮＮ）分类作为数据挖掘中最典型的算法之一，以较高的泛化性能　

以及充足的理论基础被广泛应用。然而ｋＮＮ在测试时需要计算待识别实例与所有训练实例之间的距　

离，以至于在面对大规模数据时需要大量的时间。为此，提出一种基于分层抽样的ｋＮＮ加速算法　

（ＫＮＮ　ｂａｓｅｄ　ｏｎ　ｓｔｒａｔｉｆｉｅｄ　ｓａｍｐｌｉｎｇ，Ｓ　ｋＮＮ）。首先将训练实例所在的空间划分为若干个实例个数相等　

的区域，然后从每个区域内抽取实例，最后判定待识别实例落入划分区域中的哪一个，并从此区域以及　

相邻区域抽取的实例中寻找其ｋ个近邻。与原始ｋＮＮ算法以及基于随机抽样的ｋＮＮ算法相比，ＳＳ－　

ｋＮＮ算法可以获得与其相近分类精度，但将其运行速度分别提高大约３９９倍和ｌ６倍。　

关键词：分层抽样；数据划分；近邻；分类精度；运行时间　

中图分类号：ＴＰ１８１　文献标志码：Ａ　

Ａｃｃｅｌｅｒａｔｉｏｎ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｋ　Ｎｅａｒｅｓｔ　Ｎｅｉｇｈｂｏｒ　Ｃｌａｓｓｉｆｉｃａｔｉｏｎ　Ｂａｓｅｄ　ｏｎ　Ｓｔｒａｔｉｆｉｅｄ　Ｓａｍ—　

k-近邻分类算法

K近邻分类算法是一种基于实例的分类算法，它的主要思想是通过计算每个样本点与其周围的k个最近邻点的距离来确定该点的类别。该算法主要应用于分类问题中，并且在实际应用过程中具有很好的可用性、易实现性和理解性。

算法原理

算法首先通过确定k值来确定分类的邻域大小，以及根据k值的选择来确定分类的准确性和鲁棒性。之后通过计算每个样本点与其邻域内k个最近邻点之间的距离来确定该样本点所属的分类。具体流程如下：

1.确定数据集中的k值和距离度量标准；

2.对于每个待分类的样本点，计算与其邻域中k个最近邻点之间的距离；

3.根据邻域中k个最近邻点的类别来确定该样本点所属的类别；

4.重复步骤2和3，直到所有待分类的样本点均被分类完毕；

5.给出分类结果。

距离度量标准

在k-近邻分类算法中，距离度量标准是非常重要的，因为它决定了样本点之间距离的计算方式。目前常见的距离度量标准有欧式距离、曼哈顿距离和切比雪夫距离。

欧式距离：$d=\sqrt{{\sum_{i=1}^{n}{(x_i-y_i)^2}}}$

优缺点

1.基于实例，不需要对数据进行任何假设和理论分析；

2.算法的可预测性高，具有很好的分类性能；

3.没有过拟合的现象，可以对复杂的数据集进行分类；

4.整体而言，k-近邻分类算法非常容易理解和实现。

1.计算量比较大，对于大型数据集而言，算法的效率较低；

2.对于高维数据集而言，容易出现维数灾难问题，即算法的效果会逐渐降低；

3.容易受到异常值的影响，且在分类决策区域方面可能存在不连续的问题。 应用场景

k-近邻分类算法广泛应用于模式识别、数据挖掘和生物信息学等领域，特别适合处理较小的数据集。目前该算法已被应用于医疗诊断、电子商务、物联网等领域，既可以用于分类问题，也可以用于回归问题。同时，对于分类问题而言，该算法并不适用于类别数比较多或类别间存在相互交叉的情况。因此，在实际应用过程中，应根据具体情况来选择算法，以达到最佳的分类效果。