一、KNN算法原理

1.算法概述

k近邻(k-Nearest Neighbor，简称kNN)学习是一种常用的监督学习方法，其工作机制非常简单：给定测试样本，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后基于这k个"邻居"的信息来进行预测。通常，在分类任务中可使用"投票法"即选择这k个样本中出现最多的类别标记作为预测结果；在回归任务中时使用"平均法"，即将这k个样本的实值输出标记的平均值作为预测结果；还可基于距离远近进行加权平均或加权投票，距离越近的样本权重越大。

kNN算法的指导思想是“近朱者赤，近墨者黑”，由你的邻居来推断出你的类别。

以二分类为例，k近邻分类示意图如图1所示。

 

虚线显示出等距线；测试样本在k=1或k=5时被判别为正例，k=3时被判别为负例。

2.算法的计算步骤

1)算距离：给定测试对象，计算它与训练集中每个对象的距离；

2)找邻居：圈定距离最近的k个训练对象，作为测试对象的近邻;

3)做分类：根据这k个近邻归属的主要类别，来对测试对象分类。

3.算法的优缺点

优点：简单，易于理解，易于实现，无需估计参数，无需训练；适合对稀有事件进行分类；特别适合于多分类问题(multi-modal,对象具有多个类别标签)。

缺点：懒惰算法，对测试样本分类时的计算量大，内存开销大，评分慢；可解释性较差，无法给出决策树那样的规则。

4.算法存在的常见问题

1)K值设定的大小

k太小，分类结果易受噪声点影响；k太大，近邻中又可能包含太多的其它类别的点。

k值通常是采用交叉检验来确定（以k=1为基准）

经验规则：k一般低于训练样本数的平方根。

2)类别判定

投票法没有考虑近邻的距离的远近，距离更近的近邻也许更应该决定最终的分类，所以采用加权投票法(对距离加权，距离越近的样本权重越大)。

3)选择合适的距离衡量

高维度对距离衡量的影响：当变量数越多，欧式距离的区分能力就越差；

变量值域对距离的影响：值域越大的变量常常会在距离计算中占据主导作用，因此应先对变量进行标准化。

常用的距离度量公式如图2所示。

 

4)训练样本是否要一视同仁

在训练集中，有些样本可能是更值得依赖的，可以给不同的样本施加不同的权重，加强依赖样本的权重，降低不可信赖样本的影响。

5)性能问题

KNN是一种懒惰算法，平时不好好学习，考试（对测试样本分类）时才临阵磨枪（临时去找k个近邻）；

懒惰的后果：构造模型很简单，但在对测试样本分类时系统开销大，因为要扫描全部训练样本并计算距离；

已经有一些方法提高计算的效率，例如压缩训练样本量等。

6)能否大幅减少训练样本量，同时又保持分类精度？

浓缩技术(condensing)

编辑技术(editing)

二、KNN算法的MATLAB代码实现

对4组不同的信号分别采集20组，总共80组，然后经过特征提取(特征数量为8个)，得到80x8的矩阵。

划分数据集：将64组数据作为训练数据，16组数据作为测试数据，4类信号在训练集和测试集的数量比例相同，将训练集和测试集整体归一化，再分别作为KNN的输入。

源程序是利用KNN算法对训练集和测试集整体归一化后的测试数据进行分类，得到分类准确率。

名称：基于MATLAB的KNN算法实现多分类(类别判定采用投票法)。

源代码的博客地址：https://download.csdn.net/download/weixin_45317919/12850227

 

参考文献

[1]周志华.机器学习[M].北京:清华大学出版社,2017:225.

[2]KNN算法理解.

https://blog.csdn.net/jmydream/article/details/8644004

[3]齐兴敏.基于PCA的人脸识别技术的研究[D].武汉:武汉理工大学,2007.