【机器学习】K-Nearest Neighbor KNN算法原理简介及要点

简介

KNN的全称是K Nearest Neighbors. 这种算法可以被用来进行分类，原理是根据离特征点最近的K个点所属的类别进行分类。

KNN分类算法的流程

• KNN算法的整体流程是我们需要将训练数据的特征点全部输入，这些特征点，假设有N维。
• 输入需要预测的特征点，对这个特征点和之前所输入的训练数据的特征点，使用距离函数来求距离。
• 选取K个距离最近的特征点，进行分类表决，即使用其中数量最多的分类来作为我们所求特征点的分类。

距离度量

KNN的输入的训练数据是N维特征向量，需要把我们已知的点的N维特征向量输入到模型中，进行预测时，需要将我们所需要预测的点的特征向量，计算其到已知的特征向量的距离，这个距离可以使用多种方式来进行计算，包括明氏距离、曼哈顿距离、欧式距离等。
曼哈顿距离是指的每一维度上的距离的加和。直观上来理解，就相当于我们看到了曼哈顿地区的地图，大楼方方正正，然后我们沿着地图上的路来行走，有直行有拐弯，而不是说直接穿越建筑使用直线上最短的路径来行走，这样得到的距离称为曼哈顿距离，也称为出租车距离。曼哈顿距离的概念在地图导航中经常被使用，因为我们在地图导航的时候不能直接穿过建筑，而是要沿着比较规则的路来行驶。
欧式距离，直观上理解，在数据为二维或三维时，就相当于在二维或三维空间中的两个点的直线距离。在更高维度的空间中，因为我们的特征向量有可能是N维的，所以涉及到这个问题。在向量为高维时，其计算方法就相当于两个向量的相应维度的差值的平方之和，最后取取平方根。这可以通俗的理解为二维，三维或更高维度的几何距离。

K值选择

第二个需要注意的问题是K值的选择。如果我们把K值选的过大，这样可能会导致欠拟合。假设我们取极端情况，K值等所有训练样本的特征点的数量。在这种情况下，任何一个需要判断分类的点，我们只需要输出所有特征向量中类别所对应数量最多的那个类别即可。当这个情况下，我们说出现了欠拟合（Underfit）。
在K值过小的时候，会出现过拟合（Overfit）。在这种情况下，我们输入的任何数据，它的输出就是距离它最近的一个点的类别。在这种情况下，我们考虑的样本非常少，所以说难以得到其真正有实际意义的归属，分类容易被少量样本左右。
这里K值可以选一个奇数值，以防止出现多种类别数量相同的情况。

分类表决

计算完特征值后，对特征点的归属进行分类表决。分类表决就是说在K个距离最近的邻居中，哪个分类出现的次数最多，我们新的特征点就认为是哪个分类的，这是平均权值的分类表决。

加权分类表决

还有加权分类表决，可以给不同的特征点赋予不同的权重，然后以类别为分别计算加权分数，得到各个类别的最终分数，新的特征点就属于类别分数大的这一类