3.1　k最近邻算法的原理

如图3-1所示，有两类不同的样本数据，分别用小正方形和小三角形表示，而图正中间的那个圆所标示的数据则是待分类的数据。这也就是我们的目的，来了一个新的数据点，我要得到它的类别是什么？我们根据k最近邻的思想来给中间的那个圆点进行分类。

图3-1

如果k=3，圆点的最邻近的3个点是2个小三角形和1个小正方形，少数从属于多数，基于统计的方法，判定圆点的这个待分类点属于三角形一类。

如果k=5，圆点的最邻近的5个邻居是2个三角形和3个正方形，还是少数从属于多数，基于统计的方法，判断圆点的这个待分类点属于正方形一类。

从上面的例子可以看出，根据k最近邻的算法思想如何给新来的点进行归类，只要找到离它最近的k个实例，哪个类别最多即可。简单来说，kNN可以看成：有那么一堆你已经知道分类的数据，当一个新数据进入的时候，就开始跟训练数据里的每个点求距离，然后挑离这个训练数据最近的k个点看看这几个点属于什么类型，最后用少数服从多数的原则，给新数据归类。

kNN算法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

kNN算法的核心思想是：如果一个数据在特征空间中最相邻的k个数据中的大多数属于某一个类别，则该样本也属于这个类别（类似投票），并具有这个类别上样本的特性。通俗地说，对于给定的测试样本和基于某种度量距离的方式，通过最靠近的k个训练样本来预测当前样本的分类结果。

总结一下kNN的工作原理，kNN算法就是根据距离待分类样本A最近的k个样本数据的分类来预测A可能属于的类别，基本的计算步骤如下：

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

（2）计算待分类数据与训练集中每一个样本之间的距离。

（3）找出与待分类样本距离最近的k个样本。

（4）观测这k个样本的分类情况。

（5）把出现次数最多的类别作为待分类数据的类别。