分类算法之邻近算法:KNN（理论篇）

起步

今天介绍另一种分类算法，k邻近算法( k-nearest neighbors )，即 KNN 算法。

Cover 和 Hart 在 1968 年提出了最初的邻近算法，用于解决分类( classification )的问题。关于这个算法在维基百科中也有介绍:https://zh.wikipedia.org/wiki... 。

KNN是一种基于实例学习( instance-based learning )，或者所是将所有计算推迟到分类之后的惰性学习( lazy learning )的一种算法，KNN是所有机器学习算法中最简单算法之一。

一个有关电影分类的例子：

分类算法之邻近算法:KNN（理论篇）

这个一个根据打斗次数和接吻次数作为特征来进行类型的分类。最后一条的记录就是待分类的数据。

KNN这个分类过程比较简单的一个原因是它不需要创建模型，也不需要进行训练，并且非常容易理解。把例子中打斗次数和接吻次数看成是x轴和y轴，那么就很容易能建立一个二维坐标，每条记录都是坐标中的点。对于未知点来说，寻找其最近的几个点，哪种分类数较多，未知点就属于哪一类。

KNN算法的思路是: 如果一个样本在特征空间中的 k 个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。通常 K 的取值比较小，不会超过 20。

算法步骤为：

关于距离的测量方式有多种，这里只介绍两种。

欧拉距离
这种测量方式就是简单的平面几何中两点之间的直线距离。

分类算法之邻近算法:KNN（理论篇）

并且这种方法可以延伸至三维或更多维的情况。它的公式可以总结为:

$$d(x,y) = \sqrt{\sum_{i=0}^n(x_i-y_i)^2}$$

曼哈顿距离
顾名思义，城市街区的距离就不能是点和点的直线距离，而是街区的距离。如棋盘上也会使用曼哈顿距离的计算方法：

$$d(x,y) = \sqrt{\sum_{i=0}^n|x_i-y_i|}$$

K值的选择会影响结果，有一个经典的图如下:

分类算法之邻近算法:KNN（理论篇）

图中的数据集是良好的数据，即都打好了 label ，一类是蓝色的正方形，一类是红色的三角形，那个绿色的圆形是待分类的数据。

如何选择一个最佳的K值取决于数据。一般情况下，在分类时较大的 K 值能够减小噪声的影响，但会使类别之间的界限变得模糊。因此 K 的取值一般比较小 ( K < 20 )。

在下面一种情况中：

分类算法之邻近算法:KNN（理论篇）

在点Y的预测中，改范围内三角形分类数量占优，因此将Y点归为三角形。但是从视觉上观测，应该是分为圆形分类更为合理。根据这种情况就在距离测量中加上权重，比如 1/d (d: 距离)。

优点：

缺点：