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

本章将要讨论的最后一个监督学习算法是k-近邻算法（k-nearest neighbor classifier，KNN），此算法非常有趣，因为它区别于目前已经介绍过的所有学习算法。

KNN是惰性学习算法的典型例子。说它具有惰性不是因为它看起来简单，而是因为它仅仅对训练数据集有记忆功能，而不会从训练集中通过学习得到一个判别函数。

参数化模型与非参数化模型

机器学习算法可以划分为参数化模型和非参数化模型。当使用参数化模型时，需要我们通过训练数据估计参数，并通过学习得到一个模式，以便在无需原始训练数据信息的情况下对新的数据点进行分类操作。典型的参数化模型包括：感知器、逻辑斯谛回归和线性支持向量机等。与之相反，非参数化模型无法通过一组固定的参数来进行表征，而参数的数量也会随着训练数据的增加而递增。我们已经学习了两个非参数化模型：决策树（包括随即森林）和核SVM。

KNN属于非参数化模型的一个子类，它可以被描述为基于实例的学习（instance-based learning）。此类模型的特点是会对训练数据进行记忆；而惰性学习（lazy learning）则是基于实例学习的一个特例，它在学习阶段的计算成本为0。

KNN算法本身是很简单的，可以归纳为以下几步：

1）选择近邻的数量k和距离度量方法。

2）找到待分类样本的k个最近邻居。

3）根据最近邻的类标进行多数投票。

下图说明了新的数据点（问号所在位置）如何根据最近的5个邻居进行多数投票而被标记上三角形类标：

基于选定的距离度量标准，KNN算法从训练数据集中^[1]找到与待预测目标点的k个距离最近的样本（最相似）。目标点的类标基于这k个最近的邻居的类标使用多数投票确定。

这种基于记忆的学习算法的优点在于：分类器可以快速地适应新的训练数据。不过其缺点也是显而易见的：在最坏情况下，计算复杂度随着样本数量的增多而呈线性增长，除非数据集中的样本维度（特征数量）有限，而且使用了高效的数据结构（如KD树等）。具体请参照J.H.Friedman、J.L.Bentley在R.A.Finkel发表在ACM Transactions on Mathematical Software（TOMS）3（3）:209–226,1977的论文“An algorithm for finding best matches in logari-thmic expected time”。此外，我们还不能忽视训练样本，因为此模型没有训练的步骤。由此一来，如果使用了大型数据集，对于存储空间来说也是一个挑战。

使用以下代码，以欧几里得距离为度量标准，使用scikit-learn实现了一个KNN模型。

将此数据集上的KNN模型的近邻数量设定为5个，我们得到了相对平滑的决策边界，如下图所示：

通常情况下，scikit-learn中实现的KNN算法对类标的判定倾向于与样本距离最近邻居的类标。如果几个邻居的距离相同，则判定为在训练数据集中位置靠前的那个样本的类标。

就KNN来说，找到正确的k值是在过拟合与欠拟合之间找到平衡的关键所在。我们还必须保证所选的距离度量标准适用于数据集中的特征。相对简单的欧几里得距离度量标准常用于特征值为实数的样本，如鸢尾花数据集中的花朵，其特征值是以厘米为单位的实数。注意，当我们使用欧几里得距离时，对数据进行标准化处理，保持各属性度量的尺度统一也是非常重要的。在代码中用到的“闵可夫斯基”（'minkowski'）距离是对欧几里得距离及曼哈顿距离的一种泛化，可写作：

如果将参数设定为p＝2，则为欧几里得距离；当p＝1时，就是曼哈顿距离。scikit-learn中还实现了许多其他的距离度量标准，具体内容可见如下网址：http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.DistanceMetric.html。

维度灾难

由于维度灾难（curse of dimensionality）的原因，使得KNN算法易于过拟合。维度灾难是指这样一种现象：对于一个样本数量大小稳定的训练数据集，随着其特征数量的增加，样本中有具体值的特征数量变得极其稀疏（大多数特征的取值为空）。直观地说，可以认为即使是最近的邻居，它们在高维空间中的实际距离也是非常远的，因此难以给出一个合适的类标判定。

在逻辑斯谛回归一节中，我们讨论了通过正则化使其避免过拟合。不过，正则化方法并不适用于诸如决策树和KNN等算法，但可以使用特征选择和降维等技术来帮助其避免维度灾难。具体内容将在下一章中探讨。

[1] 此处不应叫训练数据集，与协同过滤类似，就是数据集，但原文如此。——译者注