2014-06-10
K-近邻算法，简称KNN（k-Nearest Neighbor），是一个相当简单的分类/预测算法。其主要思想就是，选取与待分类/预测数据的最相似的K个训练数据，通过对这K个数据的结果或者分类标号取平均、取众数等方法得到待分类/预测数据的结果或者分类标号。
一个示例
以根据地理位置和大小预测房价为例子。
假设某城市一间房子的价钱与它自身的面积以及与市中心的距离关系很大，我们搜集到了以下的训练数据：
| 与市中心距离（公里） | 面积（平方米） | 房价（万元） |
|---|---|---|
| 2 | 60 | 400 |
| 3 | 80 | 500 |
| 5 | 60 | 390 |
| 15 | 100 | 350 |
| 25 | 60 | 200 |
| 26 | 90 | 270 |
| 27.5 | 80 | 260 |
取K=2。现在预测一下与市中心距离为4公里，面积70平方米的房子的价钱。在此，使用数据之间的欧几里得距离的平方作为两个数据点之间的距离，距离越小，代表着两个房子越“近邻”。这里，也可以在距离的基础上判断相似性，但略显多余。现在，计算各训练数据与待预测数据之间的距离。
| 与市中心距离（公里） | 面积（平方米） | 与待预测房子的“距离” | 房价（万元） |
|---|---|---|---|
| 2 | 60 | 104 | 400 |
| 3 | 80 | 101 | 500 |
| 5 | 60 | 101 | 390 |
| 15 | 100 | 1021 | 350 |
| 25 | 60 | 541 | 200 |
| 26 | 90 | 884 | 270 |
| 27.5 | 80 | 652.25 | 260 |
真实情况下，数据量会稍大，需要对计算的距离进行排序。不过，这里，直观上(3, 80)、(5, 60)这两个房子与(4, 70)是最近邻的两个。于是可以认为(4,70)这个房子的价钱为：
(500+390) / 2 = 445
注意，选取的特征一定要与分类/预测结果有较强的因果关系。另外，K的值的选取也是很重要的，过大或者过小都会让预测出现问题。例如取K=1，那么预测的房价可能是500或者350，这种差距是没法让人接受的。如果取K=6，那么(4, 70)的房价将是：
(400+500+390+200+270+260) / 6 = 336
(4, 70)的条件比(5,60)要好，但是价钱缺低了很多，自然也不合理。
在KNN中还有一个数据缩放的问题。上面的示例中数据还是比较合理的。以(26, 80)为例子，距离的计算结果将是：
| 与市中心距离（公里） | 面积（平方米） | 与待预测房子的“距离” | 房价（万元） |
|---|---|---|---|
| 2 | 60 | 976 | 400 |
| 3 | 80 | 529 | 500 |
| 5 | 60 | 841 | 390 |
| 15 | 100 | 521 | 350 |
| 25 | 60 | 401 | 200 |
| 26 | 90 | 100 | 270 |
| 27.5 | 80 | 2.25 | 260 |
取K=2，这个房子的价钱是(260+270)/2 = 265。
不过如果把与市中心距离这一项的单位改成米，(26, 80)变成(26000,80)，即：
| 与市中心距离（米） | 面积（平方米） | 房价（万元） |
|---|---|---|
| 2000 | 60 | 400 |
| 3000 | 80 | 500 |
| 5000 | 60 | 390 |
| 15000 | 100 | 350 |
| 25000 | 60 | 200 |
| 26000 | 90 | 270 |
| 27500 | 80 | 260 |
距离的计算结果将依次是：
576000400
529000000
441000400
121000400
1000400
100
2250000
取K=2，这个房子的价钱是(200+270)/2 = 235。
从上面看出，数据的实际的值是相同的，但是由于单位的不同却得到了两个不同的结果。要避免这种问题，一种方法是手动选择合理的单位，另一种方法将数据按照比例缩放，比如数据的归一化，即将所有数据映射到[0,1]这个区间中。对于某个特征，要将特定值归一化，将这个值减去最小值得到的值除以该特征最大值与最小值的差即可。例如房子与市中心的距离，最大值是27500，最小值是2000，那么3000将被缩放为：
(3000 - 2000) / (27500 - 2000) = 0.039
当然，在对与市中心距离进行归一化的同时，对面积归一化也是有必要的。如果每个特征对房价的影响程度不同，可以在计算距离时，采取加权平均的方法。
关于KNN的分类速度
KNN的一个有趣的特征是，这个算法并不像贝叶斯分类、支持向量机等方法那样会对训练集进行训练，KNN只是将训练集存起来，在分类/预测的时候需要将待分类/预测数据与训练数据一一比较求得距离，然后还要排序。所以KNN的预测时间是比较长的。
在实际使用中，训练数据最好是放在数据库中，计算所得的距离也可以考虑放在数据库中，这样可以借助数据库的排序功能迅速得到结果。
当然，也可以考虑对KNN算法进行改进。一种提高K-近邻算法效率的新算法提出了一个比较简单但效果很好的方法。这个改进，主要是在训练阶段“动了手脚”：
其在训练阶段，做了下面的工作：
- 在训练数据集中随机取一个数据实例作为基准实例O
- 计算训练数据集中其它各实例到基准实例O的距离, 并按从小到大排序
- 从排序好的实例中取第100×k个实例到基准实例的距离作为参数d的值。（这里的k就是KNN中的K）
在分类阶段，给定一个待分类的实例x，然后：
- 计算该实例到基准实例O的距离r
- 从在训练阶段排好序的实例中取出到基准实例的距离为[r-d, r+d]的所有实例, 然后在这个范围内找出到实例x距离小于或等于d的所有的实例, 并按从小到大排序, 最后选出最靠近x的k个实例。
这篇论文的作者说：实验表明, 该算法能够提高KNN效率80%以上。