kNN算法

一、kNN算法概述

       kNN是k-Nearest Neighbour的缩写，这是一种非常简单且易于理解的分类算法。回想我们从小到大在认知事物的过程当中，我们是如何判断一种事物是属于哪种类别的？通常的一种思路就是，分析当前这个事物与我们之前所知道的类别特征进行比对，找出最接近的一类，然后就可以把这个东西归属于这一个类别。kNN算法大致就是这么一个思路，直接通过测量不同特征值之间的距离来达到分类的目的。

       kNN中的k是指在分类过程中，我们选择样本数据中前k个最相似的数据，以出现次数最多的分类，作为新数据的分类。这里的k通常是不大于20的正整数，k取3或者5的情况比较常见。

二、kNN算法的原理

      首先是训练模型。对kNN而言，在编码过程中训练模型实际上就是记录训练集的所有数据，所以我们常说kNN没有训练模型这一过程。

      接着是测试模型。测试过程有以下几个步骤：

1. 依次计算测试集数据与训练集各个数据之间的距离；

2. 对计算处理的距离进行递增排序；

3. 选择距离最小的k个数据；

4. 选择这k个数据中出现频率最高的类别作为测试数据的预测分类。

       最后是评价模型。根据测试结果计算模型预测分类的准确率。   

       整个过程看上去非常简单、直观、明了。需要说明的是，文中一直提到的距离这个概念，指的是闵可夫斯基距离（Minkowski distance），对应数学上的Lp范数。

      当p=1时，为曼哈顿距离（Manhattan distance），也称L1距离；

      当p=2时，为欧式距离（Euclidean distance），也称L2距离；

      当p=∞时，为切比雪夫距离（distance）。

      在我们使用kNN算法时，常用L1距离和L2距离，且以L2距离使用更多。

三、算法评价

      优点：kNN是最简单、最有效的分类器；精度高；对异常值（边缘值）不敏感。

      缺点：需要记录所有训练集的数据，空间复杂度高；需要进行大量的计算，计算复杂度高；无法提取出数据内涵的结构信息。

      注意点：由于计算距离时使用的是离散型数据，所以kNN算法常用于特征值为数值型和标称型的数据。如果数据特征值为连续值，则需要根据实际情况，对特征值进行离散采样或者采用其他算法模型。