本节书摘来自华章出版社《机器学习与R语言（原书第2版）》一书中的第3章，第3.1节，美]　布雷特·兰茨（Brett Lantz）　著,李洪成　许金炜　李舰　译更多章节内容可以访问云栖社区“华章计算机”公众号查看。

第3章

懒惰学习——使用近邻分类

一种新型有趣的餐饮体验已经出现在世界各地的城市中，顾客在一个完全黑暗的餐厅里接受服务，而服务员在仅凭触觉和听觉记忆的路上小心地移动。这些餐厅的魅力在于这样的信仰：去掉一个人的视觉感官输入将会增强他的味觉和嗅觉，从而可以使他以一种全新的方式来体验食物。当发现厨师已经准备好的美味时，他的每一口食物都提供了新奇感。
你能够想象用餐者是如何体验看不到的食物吗？对于第一口，感觉就消失。占主导地位的味道是什么？食物尝起来是咸还是甜？食物的味道类似于以前吃的什么东西吗？就个人而言，我用一句稍加修改的谚语来想象这一探索过程：如果该食物闻起来像只鸭子，并且尝起来也像只鸭子，那么你就很可能在吃鸭子。
这阐述了一个可以用于机器学习的思想—就像另一句有关鸟类的格言：有一样羽毛的鸟会聚集在一起（即“物以类聚，人以群分”）。换句话说就是：相似的东西很可能具有相似的属性。利用这个原理，机器学习可以对数据进行分类，将其划分到同一类别，比如相似或者“最近”的邻居中。本章将专门讨论使用这种方法进行分类，你将会学到：
定义近邻分类器的关键概念，以及为什么它们被认为是“懒惰”（lazy）学习器。
通过距离来测量两个案例相似性的方法。
应用一种流行的名为kNN的近邻分类器。
如果所有这些关于食物的话题让你感到饿了，那么随意吃些点心。我们的第一个任务就是通过安排一个持续较长的有关烹饪的讨论来使用kNN方法，从而理解kNN方法。

3.1　理解近邻分类

用一句话来说，近邻分类器就是把无标记的案例归类为与它们最相似的带有标记的案例所在的类。尽管这个想法很简单，但是近邻分类方法是极其强大的，它们已经成功地应用在下列领域中：
计算机视觉应用，包括在静止图像和视频中的光学字符识别和面部识别。
预测一个人是否会喜欢推荐的电影或者音乐。
识别基因数据的模式，或许使用它们可以检测特定的蛋白质或者疾病。
一般来说，近邻分类器非常适用于这样的分类任务，其中的特征和目标类之间的关系是众多的、复杂的或极难理解的，但是具有相似类的项目又是非常近似的。也就是说，如果一个概念很难定义，但是当你看到它时你知道它是什么，那么近邻分类就可能是合适的方法。另一方面，如果数据是噪声数据，于是组与组之间没有明确的界限，那么近邻算法可能难以确定类边界。

3.1.1　kNN算法

用于分类的近邻方法可以通过k近邻（k-Nearest Neighbor, kNN）算法举例说明。虽然这可能是最简单的机器学习算法之一，但它仍被广泛使用。
该算法的优缺点如下表所示：

kNN算法源于这样一个事实：它使用关于一个案例的k个近邻的信息来分类无标记的例子。字母k是一个可变选项，表示任意数目的近邻都可以使用。在选定k之后，该算法需要一个已经分成几个类别的案例组成的训练数据集，类别由名义变量来标记。然后，对于测试数据集中的每一个无标记的记录，kNN确定训练数据集中与该记录相似度“最近”的k条记录，将无标记的测试例子分配到k个近邻中占比最大的那个类中。
为了说明这个过程，让我们回顾引言中所描述的黑暗餐厅用餐的经历。假设在吃一顿神秘的膳食之前，我们已经创建了一个品味数据集，在这个数据集中，记录了我们对于之前所品尝过的很多配料的印象。为了简单起见，我们只估算了每种配料（ingredient）的两个特征，第一个特征是配料的脆度（crunchiness），从1～10；第二个特征是配料的甜度（sweetness），从1～10。然后，我们标记配料为3种类型之一：水果ruit）、蔬菜（vegetable）或者蛋白质（protein）。该数据集的前几行可能具有如下所示的结构：



kNN算法将特征处理为一个多维特征空间内的坐标。由于我们的数据集只包含了两个特征，所以特征空间是二维的。我们可以绘制二维数据散点图，维度x表示配料的甜度，维度y表示配料的脆度。在品味数据集中增加更多的配料后，散点图看起来可能类似于下图。



你注意到上图了吗？相似类型的食物趋向于聚集得更近。如下图所示，vegetable（蔬菜）往往是脆而不甜的；fruit（水果）往往是甜的，有可能是脆的，也有可能是不脆的；而protein（蛋白质）往往是既不脆也不甜的。



假设在创建此数据集后，我们决定用它来解决一个古老的问题：西红柿（tomato）是水果（fruit），还是蔬菜（vegetable）？我们可以使用一种近邻方法来确定哪类更适合西红柿（tomato），如下图所示。



1.通过距离度量相似性
定位tomato（西红柿）的近邻需要一个距离函数或者一个用来度量两个案例之间相似性的公式。
计算距离有许多种不同的方法。传统上，kNN算法采用欧式距离（Euclidean distance），如果可能，这种距离可以通过用尺子连接两个点来测量，在上图中，我们通过虚线将西红柿（tomato）与它的邻居连接在一起。
欧式距离通过“直线距离”（as the crow flies）来度量，即最短的直接路线。另一种常见的距离度量是曼哈顿距离（Manhattan distance），该距离基于一个行人在城市街区步行所采取的路线。如果你有兴趣了解更多关于距离度量的方法，可以使用?dist命令，阅读R中的距离函数文档（该文档本身就是一个很有用的工具）。
欧式距离通过如下的公式定义，其中p和q是需要比较的案例，它们都有n个特征，项p1代表案例p的第一个特征的值，而q1代表案例q的第一个特征的值：

距离公式涉及比较每个特征的值。例如，为了计算西红柿（tomato）（sweetness（甜度）= 6, crunchiness（脆度）=4）和绿豆（green bean）（sweetness（甜度）=3, crunchiness（脆度）=7）之间的距离，可以使用如下公式：

与此类似，可以计算西红柿（tomato）与它的几个近邻之间的距离，如下表所示。



为了将西红柿（tomato）归类为蔬菜（vegetable）、蛋白质（protein），或者水果（fruit），我们先从把西红柿（tomato）归类到离它最近的一种食物所在的类型开始。因为这里k=1，所以这称为1NN分类。橙子（orange）是西红柿（tomato）的近邻，距离是1.4。因为橙子（orange）是一种水果，所以1NN算法把西红柿（tomato）归类为一种水果。
如果我们使用k=3的kNN算法，那么它会在3个近邻即橙子（orange）、葡萄（grape）和坚果（nuts）之间进行投票表决。因为这3个邻居的大多数归类为水果（2/3的票数），所以西红柿（tomato）再次归类为水果。
2.选择一个合适的k
确定用于kNN算法的邻居数量将决定把模型推广到未来数据时模型的好坏。过度拟合和低度拟合训练数据之间的平衡问题称为偏差-方差权衡（bias-variance tradeoff）。选择一个大的k会减少噪声数据对模型的影响或者减少噪声导致的模型波动，但是它会使分类器产生偏差，比如，它有忽视不易察觉但却很重要模式的风险。
假设我们采取一个极端的情况，即设置一个非常大的k，它等于训练数据中所有观测值的数量。由于每一个训练案例都会在最后的投票表决中出现，所以最常见的训练类总会获得大多数的票。因此，模型总会预测为数量占大多数的那个训练类，而不管哪个邻居是最近的。
在相反的极端情况下，使用一个单一的近邻会使得噪声数据或者异常值过度影响案例的分类。例如，假设一些训练案例被意外地贴错了标签，而另一些无标记的案例恰好是最接近于被错误标记的训练案例，那么即使其他的9个近邻有不同的投票，它也会被预测到错误的类中。
显然，最好的k值应该取这两个极端值之间的某个值。
下图更一般地说明了决策边界（由虚线表示）如何受到较大的或者较小的k值的影响。较小的k值会给出更复杂的决策边界，它可以更精细地拟合训练数据。但问题是，我们并不知道是直线边界还是曲线边界能更好地代表我们将要学习的正确概念。



在实际中，k的选取取决于要学习概念的难度和训练数据中记录的数量。一种常见的做法就是从k等于训练集中案例数量的平方根开始。在我们之前研究的食物分类器中，我们可以设置k=4，因为训练数据中有15个案例，15的平方根是3.87。
然而，这样的规则可能并不总是产生一个最好的k值。另一种方法是基于各种测试数据集来测试多个k值，并选择一个可以提供最好分类性能的k值。也就是说，除非数据的噪声非常大，否则大的训练数据集可以使k值的选择并不那么重要。这是因为即使是微小的概念，也将有一个足够大的案例池来进行投票，以便选举出近邻。
一个不太常见但很有趣的解决这个问题的方法是选择一个较大的k值，但是同时应用一个权重投票（weighted voting）过程，在这个过程中，认为较近邻的投票比远邻的投票更有权威。许多kNN的实现提供这样的选择。
3.准备kNN算法使用的数据
在应用kNN算法之前，通常将特征转换为一个标准的范围内。这个步骤的合理性在于，距离公式高度依赖于特征是如何被度量的。特别地，如果某个特征具有比其他特征更大范围的值，那么距离的度量就会强烈地被这个具有较大范围的特征所支配。而对于食物品味案例，这并不算是一个问题，因为甜度（sweetness）和脆度（crunchiness）的度量都是在1～10的范围内。
然而，假设我们在数据集中增加一个额外的特征来表示食物的辛辣度（spiciness），并使用史高维尔指标来测量它。如果你不熟悉这个指标，它是辛辣热量的一种标准化度量，范围从0（完全不辣）到超过100万（最火辣的辣椒）。因为辛辣食物和非辛辣食物之间的差异可能会超过100万，而甜食和非甜食或者脆食和非脆食之间的差异至多是10，所以尺度的差异使得辛辣对于距离函数的影响水平远远超过其他两个因素。如果没有调整我们的数据，我们可能会发现距离度量只能通过食物的辛辣度来加以区别，而脆度和甜度的影响将会由于辛辣度对于距离的贡献而显得相形见绌。
解决的方法便是通过收缩或者放大它们的范围来重新调整特征，使得每个特征对距离公式的贡献相对平均。例如，如果甜度和脆度都在范围1～10，那么我们也希望辛辣度在范围1～10，有一些方法可以完成这样的尺度调整。
对kNN算法的特征进行重新调整的传统方法是min-max标准化（min-max normali-zation），该过程变换特征，使它的所有值都落在0～1范围内。将特征进行min-max标准化的公式如下所示：

本质上，该公式就是特征X的每一个值减去它的最小值再除以特征X的极差。
min-max标准化的特征值可以这样解释：按0%～100%来说，在原始最小值和原始最大值的范围内，原始值到原始最小值的距离有多远。
另一种常见的变换称为z-分数标准化（z-score standardization）。下面的公式是减去特征X的均值后，再除以X的标准差：

这个公式是基于第2章所介绍的正态分布的性质（即根据每一个特征的值落在均值上下的标准差的数量）来重新调整每一个特征的值，所得到的值称为z分数（z-score）。z分数落在一个无界的负数和正数构成的范围内，它们与min-max标准化后的值不同，没有预定义的最小值和最大值。
用于kNN训练数据集的同一个重新调整方法必须也应用于算法之后将要分类的样本。对于min-max标准化，这可能会导致一种棘手的情形，即未来样本的最小值或者最大值可能在训练数据中观测值的范围之外。如果你事先知道合理的最小值或者最大值，你可以使用这些常量，而不是观测值。另外，你也可以使用z分数标准化，基于这样的假设：作为训练样本，未来样本具有相似的均值和标准差。
欧式距离公式并不是为名义数据定义的。因此，为了计算名义特征之间的距离，需要将它们转化成数值型格式。一种典型的解决方案就是利用哑变量编码（dummy coding），其中1表示一个类别，0表示其他类别。例如，可以如下构建性别变量的哑变量编码：

注意对含有两个可能取值的（二元）性别变量进行哑变量编码产生一个新的名为male的特征，而为female构建一个单独的特征是没有必要的，因为两种性别是互斥的，知道其中一个就足够了。
这种方法实际上可以更广泛地应用。一个具有n个类别的名义特征可以通过对特征的（n－1）个水平创建二元指示变量来进行哑变量编码。例如，为一个具有3个类别的温度变量（比如，hot、medium或者cold）进行哑变量编码，可以用（3－1）＝2个特征来进行设置，如下式所示：

只要知道hot和medium的值同时为0就足以说明温度是cold，因此我们不需要为cold类设置第3个特征。
哑变量编码的一个方便之处就在于哑变量编码的特征之间的距离总是为1或者0，因此，与min-max标准化的数值数据一样，这些值落在了一个相同的标度内，不需要进行额外的变换。
如果名义特征是有序的（可以将温度变量作为例子），那么一种哑变量编码的替代方法就是给类别编号并且应用min-max标准化。例如，cold、warm和hot可以编号为1、2和3，min-max标准化后为0、0.5和1。使用该方法要注意的是，只有当类别之间的步长相等时，才能应用该方法。例如，对于收入分类，尽管poor、middle class和wealthy是有序的，但是poor和middle class之间的差异与middle class和wealthy之间的差异可能是不同的。由于组别之间的步长不相等，所以哑变量编码是一种更保险的方法。

3.1.2　为什么kNN算法是懒惰的

基于近邻方法的分类算法被认为是懒惰学习（lazy learning）算法，因为从技术上来说，没有抽象化的步骤。抽象过程和一般化过程都被跳过了，这就破坏了第1章给出的学习的定义。
基于学习这个概念的严格定义，懒惰学习并不是真正在学习什么。相反，它仅仅是一字不差地存储训练数据，这样训练阶段并不是实际训练什么，于是就进行得很快。当然，不利因素就是进行预测的过程相对于训练往往会变得相对较慢。由于高度依赖于训练实例而不是一个抽象的模型，所以懒惰学习又称为基于实例的学习（instance-based learning）或者机械学习（rote learning）。
由于基于实例的学习算法并不会建立一个模型，所以该方法归类为非参数（non-parametric）学习方法，即没有需要学习的数据参数。因为没有产生关于数据的理论，所以非参数方法限制了我们理解分类器如何使用数据的能力。另一方面，它允许学习算法发现数据中的自然模式，而不是试图将数据拟合为一个预先设定的可能的偏差函数形式。

尽管kNN分类器可能被认为是懒惰的，但它们还是很强大的，正如你不久就会看到的，近邻学习的简单原则可以用于癌症的自动化筛查过程。