第5章
K-NN算法

5.1　K-NN概述

K-NN的全称为K-Nearest Neighbors（中文常被译作“K最近邻算法”），是模式识别领域应用相当广泛的一个算法。K-NN经典算法起源于20世纪70年代，它既可以用于分类任务，也能够支持回归任务。K-NN在处理这两种情况时的算法输入都是一样的，即包含特征空间的k个最接近的训练样本，只不过它们在输出结果上有所差异。

1．K-NN分类

当K-NN用于分类任务时，一个对象A的分类结果取决于训练集中与它最相近的k个元素的投票结果（例如少数服从多数）。如果k取值为1，那么意味着只要找寻与A最相近的训练样本就可以确定它的类别，如图5-1所示。

图5-1　K-NN分类图示

2．K-NN回归

当K-NN用于回归任务时，输出结果代表的是该对象A的属性值（取与A最相近的k个样本的平均值），如图5-2所示。

图5-2　K-NN回归

K-NN的另一个显著特点是它不需要训练，所有计算（分类／回归）都是在应用推理的时候才会执行，因而也被人们归于惰性学习法（Lazy Learning）——与之相对的是急性学习法（Eager Learning）。后者是指先利用训练数据进行训练得到一个目标函数，然后应用推理时只需利用训练好的函数进行决策。SVM等算法就属于这种学习方式。

这两种学习方法的区别如下。

（1）急性学习法需要基于所有样本开展训练过程，因而训练的时间较长，但推理决策时间较短。

（2）惰性学习法虽然在做最终决策时通常只用到了局部的几个样本，但由于它需要计算推理对象与所有样本之间的距离，复杂度还是达到了O（n）。所以惰性学习法不仅需要较大的存储空间，而且决策过程比较慢（没有训练过程）。

5.2　K-NN分类算法

K-NN算法本身并不复杂，它主要由以下三个核心要素组成。

（1）k的取值。

（2）近邻算法。

（3）投票机制。

接下来围绕上述三个核心点来展开分析。

1．k的取值

理论上，k可以取合法范围内的任何数值——但需要思考的是，k取不同值会不会影响最终的结果呢？答案是肯定的，而且影响很大。

例如，如图5-3所示的经典案例。

图5-3　k的取值对结果的影响示例

在图5-3的范例中，当k取不同值时，结果如下。

（1）k=3时：不难发现，此时中间的圆圈与两个三角形及一个正方形最近，所以如果按照投票法，它应该归属于三角形类别。

（2）k=5时：此时圆圈与两个三角形及三个正方形最近，因而如果按照投票法，它就变成归属于正方形。

对于k的取值，我们可以思考：

（1）因为到目前为止还没有成熟的理论来支撑k的选值过程，所以一般的做法是：采用交叉验证的方式来得到一个理论上最佳的k值（类似于模型训练）。

（2）k值较小时。

k值越小，代表参与最终决策的样本数量越少。这种情况下的训练误差可能会较小，但泛化误差会增大，或者说容易发生过拟合。

（3）k值较大时。

k值越大，代表参加最终决策的样本数量越多。其优点是可以减少噪声的影响，因而泛化误差较小，但缺点是训练误差会增大。

（4）k等于样本数n时。

这是一种极端的情况，此时相当于没有分类。

（5）根据实践经验来选取k值。

从项目实践经验来看，k的取值一般都是：，n为样本数量。

2．近邻算法

K-NN的可选近邻算法有很多种，包括但不限于：

1）曼哈顿（Manhattan）距离

典型公式如下。

2）欧几里得（Euclidean）距离

典型公式如下。

3）马氏（Mahalanobis）距离

典型公式如下。

其中，S为协方差矩阵。

4）闵可夫斯基（Minkowsky）距离

典型公式如下。

其中，“欧几里得距离”是K-NN中最常用的一种距离度量方法。

3．投票机制

K-NN的投票机制也有多种选择，例如：

1）少数服从多数

这是最简单的一种投票方式，但是它没有考虑k个最近邻元素之间的“远近”差异，因而在效果上并不是最佳的。

2）加权投票

和上述“人人平等”的投票方式不同，加权投票针对不同近邻元素的差异性进行了考量——例如，按照它们与被预测对象的距离远近分别赋予相应的权重，保证距离近的元素对最终决策的影响力更大一些，反之距离远的作用则被有目的性地降低了。

综合来看，距离加权的投票方法是K-NN中采用最广泛的其中一种投票机制。

5.3　K-NN回归算法

K-NN回归算法和K-NN分类算法大致相同，接下来结合一个范例来进行实际的讲解。

假设要帮客户出租一套3室的房子，那么定价多少合适呢？

K-NN可以回答这个问题——可以基于市面上相同或者相近户型的房子的出租价格，来得出一个相对合理的答案，如表5-1所示。

表5-1　市面房租价格

假如选择欧氏距离作为度量标准，那么：

1．对于3室样本

此时欧氏距离公式中的n=1，即

2．对于5室样本

同理，可得d=2。

再假设k的取值为4，换句话说，我们考虑的是4个最相近的房租样本，那么按照K-NN的算法思想可以得到待出租的3室的价格myPrice：

可以看到上述计算过程中，使用的是针对k个样本取均值的方式——不过和K-NN分类算法中的加权投票法类似，我们在回归场景中也可以考虑基于样本的差异性来区分对待，从而更好地发挥出样本数据的价值。

5.4　K-NN的优缺点

K-NN虽然是一个经典的算法，但它既有优点，同时也有不足之处。

5.4.1　K-NN的优点

K-NN算法的主要优点如下。

（1）算法简单，易于理解，易于实现。

（2）不需要训练过程。

（3）预测精度较高。

（4）通常对噪声数据不是特别敏感。

（5）针对多分类问题（即对象具有多个类别标签的情况），K-NN算法的表现比较突出，甚至超过SVM等算法。

5.4.2　K-NN的缺点

K-NN算法的主要缺点如下。

（1）属于惰性学习法的一种。在前面已经分析过，这种类型的算法虽然在做最终决策时只用到了局部的几个样本，但由于它对每一个待分类的样本都需要计算其到全体样本数据的距离，才能获取k个最近邻点，所以整体复杂度还是O（n）。在实践中，针对这一问题的一个常用解决方法是提前减除掉对分类结果作用不大的部分样本。

（2）不仅决策过程比较慢（虽然理论上没有训练过程），而且空间开销也较大。

（3）可解释性较差。

（4）当样本不均衡时（即归属于某些类别的样本数量很大，而其他类别样本数量又很小的情况），针对新样本的预测有可能出现偏差——因为与该样本最近邻的k个数据中，样本数量大的类别很可能会占绝对多数。

（5）向量的维度越高，那么欧式距离用于计算样本差异的能力就越弱，由此可能导致预测结果的不准确性。

当然，K-NN的上述这些缺点并非完全无法解决。只要做到“知己知彼”，那么就有可能在实际项目中采取有效的手段来规避或者减少这些缺点所带来的影响。

5.5　K-NN工程范例

本节中将通过scikit-learn的一个范例来讲解如何使用K-NN算法来解决一些实际问题。

scikit-learn框架下，与K-NN算法相关的包是sklearn.neighbors，这个包中不仅包含K-NN的经典实现，还包含它的多种扩展实现，如图5-4所示。

图5-4　K-NN扩展实现

其中，KNeighborsClassifier的原型如下。

接下来的代码范例中就是基于KNeighborsClassifier来实现的，核心代码节选以及详细释义如下。

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
from sklearn import neighbors, datasets
n_neighbors = 15 ##k值选取15
#加载iris(鸢尾花)数据集
iris = datasets.load_iris()
#iris是多维数据集，我们只选取两个维度进行示例
X = iris.data[:, :2]
y = iris.target

该数据集是关于鸢尾花的，大致是如图5-5所示的样式。

图5-5　iris数据集

h = .02  #通过步进值产生大量被预测对象
#一共有三种类型的iris，因而需要创建三种颜色
cmap_light = ListedColormap(['#FFAAAA', '#AAFFAA', '#AAAAFF'])
cmap_bold = ListedColormap(['#FF0000', '#00FF00', '#0000FF'])
for weights in ['uniform', 'distance']:

这两种weights（uniform和distance），分别对应前面讲解的“少数服从多数”和“加权投票”两种机制。

最终结果如图5-6所示。

图5-6　基于K-NN算法的工程范例

读者可以仔细比较一下K-NN采用两种不同weights时在分类表现上的异同点。