3.7　k-近邻——一种惰性学习算法

本章将要讨论的最后一个监督学习算法是k-近邻（KNN）分类器，它特别有趣，因为它与迄今为止我们所讨论过的其他学习算法有本质的不同。

KNN是惰性学习的典型例子。所谓的惰性，并不是说它看上去很简单，而在于它不是从训练数据中学习判别函数，而是靠记忆训练过的数据集来完成任务。

参数模型与非参数模型

机器学习算法可以分为参数模型与非参数模型。参数模型指我们从训练数据集估计参数来学习，一个能分类新数据点的函数，而不再需要原始训练数据集。参数模型的典型例子是感知器、逻辑回归和线性支持向量机。相比之下，非参数模型不能用一组固定的参数来描述，参数的个数随着训练数据的增加而增长。前面已经看到两个非参数模型的例子，决策树分类器/随机森林和核支持向量机。

KNN算法是基于实例的学习，属于非参数模型。基于实例学习的模型以记忆训练数据集为特征，惰性学习是基于实例学习的一种特殊情况，这与它在学习过程中付出零代价有关。

KNN算法本身相当简单，可以总结为以下几个步骤；

• 选择k个数和一个距离度量。
• 找到要分类样本的k-近邻。
• 以多数票机制确定分类标签。

图3-24显示了在五个近邻里，如何基于多数票机制为新数据点（？）分配三角形标签。

基于所选择的距离度量，KNN算法从训练数据集中找到最接近要分类新数据点的k个样本。新数据点的分类标签由最靠近该点的k个数据点的多数票决定。

基于记忆方法的主要优点是当新的训练数据出现时，分类器可以立即适应。缺点是新样本分类的计算复杂度与最坏情况下训练数集的样本数呈线性关系，除非数据集只有很少的维度（特征），而且算法实现采用有效的数据结构（如KD树）[2]。此外，由于没有训练步骤，因此不能丢弃训练样本。因此，如果要处理大型数据集，存储空间将面临挑战。

执行下面的代码可以用scikit-learn的欧氏距离度量实现KNN模型：

该数据集用KNN模型指定五个邻居，得到图3-25所示的相对平滑的决策边界。

仲裁

在争执不下的情况下，用scikit-learn实现的KNN算法将更喜欢近距离样本的邻居。如果邻居有相似的距离，该算法将在训练数据集中选择最先出现的分类标签。

正确（right）选择k值对在过拟合与欠拟合之间找到恰当的平衡至关重要。我们还必须确保选择的距离度量适合数据集中的特征。通常用简单的欧氏距离来度量，例如，鸢尾花数据集中的花样本，其特征以厘米为单位度量。然而，如果用欧氏距离度量，那么对数据进行标准化也很重要，确保每个特征都能对距离起着同样的作用。在前面代码中使用的minkowski距离只是欧氏距离和曼哈顿（Manhattan）距离的推广，可以表达如下：

如果参数p=2，就是欧氏距离，如果p=1，就是曼哈顿距离。在scikit-learn中还有许多其他距离度量，可以提供给metric参数。可以在http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.DistanceMetric.html找到。

维数诅咒

由于维数诅咒，KNN易于过拟合，了解这一点非常重要。当固定规模的训练数据集的维数越来越大时，特征空间就变得越来越稀疏，这种现象被称为维数诅咒。直观地说，可以认为即使是最近的邻居在高维空间的距离也很远，以至于无法合适地估计。

在3.3节讨论了正则化的概念，并以此作为避免过拟合的一种方法。然而，在不适用正则化的模型（如决策树和KNN）中，可以利用特征选择和降维技术避免维数诅咒。下一章将对此进行更详细的讨论。