KNN 意思就是K个最近的邻居，是一种监督学习下的分类算法，注意不要和K-Means（聚类算法）混淆。
积极学习方法和消极学习方法
按照由训练数据-建立模型-用模型对测试集进行测试-评价这种模式进行的学习方法，叫做积极学习方法。
而与之相反，消极学习方法推迟建模，直到需要分类测试样例的时候再进行（先分类）。
KNN算法就是一种消极学习方法，这种方法原理还是比较简单的。
原理
找出和测试样例的属性相对接近的所有训练样例（和某个训练样例最接近，所以他可能就是这个类别的）。
简述
把每个样例看作维空间上的一个数据点，其中
是特征个数，给定一个测试样例，计算该测试样例与训练集中其他数据点的邻近度。
给定样例的k-最近邻是指和z样例距离最近的
个数据点。
判断邻近度的方法有：
-
欧几里得距离
设有两点(,
)和(
,
)，欧几里得距离就是上学时候学过的相减平方开根号：
-
曼哈顿距离
-
余弦相似度
如果x,y是两个向量，则有
其中x·y是向量的点积，||x||是向量x的长度。
点积：
-
广义Jaccard系数
定义同余弦相似度。 -
相关系数
统计学里比较常用的了：
其中代表x和y的协方差，
代表x的标准差。
如下图所示，绿色点是待分类点，画实线圈的是最近邻点的范围，那么就是有三个最近邻点，也就是3-最近邻，虚线圈就是5-最近邻。
最近邻演示
圈定范围里的点之后，可以根据多数表决方案来判断分类。
如果根据3-最近邻来判断上图，那么绿点就属于三角类，如果按照5-最近邻来分类，那么就是方形类。
如何选择一个最佳的K值取决于数据。一般情况下，在分类时较大的 K 值能够减小噪声的影响，但会使类别之间的界限变得模糊。因此 K 的取值一般比较小 ( K < 20 )。
问题
按照上面的图的结论，很明显当值取的不一样的时候，分类结果也不一样，这样容易受到噪声影响产生过拟合或者欠拟合。
图中的绿点实际上里5-最近邻中的方形都比较远，但是根据多数表决，被分为了方形类，这是未必准确的。
改进
为了改进上述方案，可以考虑对每个近邻点到测试点的距离不同，给予一定的权重，距离远的权重低，距离近的权重高。
权重可以考虑用如下的公式：
设测试点为，每个最近邻点为
，每个最近邻点的权重为
，则有：
为测试点到该最近邻点的距离。
这样的话，距离远的点，权重比较小，距离近的权重比较大。
计算分类结果则用*1，每个分类的加到一起，最终的值哪个大就属于哪个分类。
特点
KNN算法是一种比较简单的算法，由于是消极学习方法，不需要建模。
而且在多分类问题上，比较简单，比其他复杂算法更合适。
但是，由于该算法没有生成模型，解释性比较差，而且由于判断每个测试点都要进行周边距离运算，效率上是比较低的。
网友评论