第 2 章 懒惰学习:最近邻方法

第 2 章 懒惰学习:最近邻方法

自然不允许跳跃。

如果你还记得小时候是如何识字的,那么你就可以理解什么是从实例中学习,尤其是监督学习。父母和老师给你展示一些带有英文字母(a、b、c,等等)的实例,然后告诉你:这是a,这是b,……

当然,他们并没有用数学公式或者精确的规律来描述这些字母的几何形状。他们只是展示了一些不同风格、不同形式、不同大小和不同颜色的已标记的实例。经过一些努力和失误之后,你的大脑就能够正确识别这些实例了。然而这不是关键,因为仅凭记忆你其实就能够做到这一点。重要的是,通过这些实例的训练,你的大脑还能从中提取出与认字真正相关的模式和规律,过滤掉不相关的“噪声”(比如颜色),从而进行泛化(generalize),以识别在训练阶段从未见过 的新实例。这是很自然的结果,但确实是值得注意的成果。取得这一成果不需要什么先进的理论,也不需要博士学位。如果有一种方法也能如此自然而又轻松地解决商业问题,是不是很令人振奋呢?结合了从数据中学习和优化的LION范式就是这样的一种方法,我们将从这一熟悉的语境开始。

监督学习中,由监督者(老师)给出 一些已标记的实例,系统根据这些已标记的实例来完成训练。每一个实例是一个数列,它包括一个作为输入参数的向量 x,称为特征(feature),和与之相对应的输出标记 y

本书作者生活的地方有很多的山地和森林,因此采蘑菇是一项十分普及的消遣活动。虽然采蘑菇很受欢迎也很有趣,但是误食有毒的蘑菇将造成致命的危害(见图2-1)。这里的小孩子在很小的时候就学会了如何区分可以食用的和有毒的蘑菇。到这里来的游客可以买到相关的书籍,书中有这两类蘑菇的图片和特征;他们也可以把采到的蘑菇带到当地的警察局,让专家帮他们免费检验这些蘑菇。

图 2-1 采蘑菇要区分可以食用的和有毒的

这里有一个被简化过的例子,如图2-2所示,假设我们用两个参数,比如高度和宽度,就能够区分这两种蘑菇。当然,一般来说,我们需要考虑更多的输入参数,像颜色、形状、气味等,甚至是更加令人困惑的正类(可以食用的)和负类实例的概率分布。

图 2-2 简化的例子:两个特征(宽度和高度)用以区分可以食用的和有毒的蘑菇

那些懒惰的初学者在采蘑菇的时候遵循简单的模式。通常他们在采摘蘑菇之前没有学习任何相关的知识,毕竟,他们到特伦蒂诺是来度假的,而不是来工作的。当发现一个蘑菇时,他们会在书中寻找相似的图片,然后仔细检查对照细节列表中的相似特征。这就是机器学习中懒惰的“最近邻”(nearestneighbor)算法在实际问题中的一次应用。

为什么这样一种简单的方法是有效的呢? 我们可以用Natura non facitsaltus(“自然不允许跳跃”的拉丁文)原则来解释它。自然的事物与特征常常是逐渐改变,而不是突然改变的。如果你将书中的一个可食用的蘑菇作为原型,然后发现你自己采摘的蘑菇与这个原型蘑菇的各项特征非常相似,那么你也许会认为你的蘑菇是可以食用的。

声明:不要使用这个简单的例子来区分真正的蘑菇,因为每一种分类器都有一定的概率出错,另外蘑菇分类中的假正类%原书第1版中误为“假负”,但第2版中已经修改为“假正”。(把有毒的蘑菇当成可食用的)将会对你的健康造成极大的损害。

最近邻方法

在机器学习领域,最近邻方法的基本形式与基于实例的学习、 基于案例的学习和基于记忆的学习有关。它的工作原理如下:我们把已标记的实例(包括输入及相应的输出的标记)储存起来,不进行任何操作,直到一个新输入模式需要一个输出。这种系统被称为懒惰的学习者:它们只是将这些实例储存起来,其他的什么也不做,直到用户询问它们。当一个新输入模式到达时,我们在存储器中查找到与这个新模式相近的那些实例,输出则由这些相近模式的输出所决定,见图2-3。一百多年来,这种数据挖掘的形式仍然被统计学家和机器学习专家广泛地用于分类问题和回归问题。

图 2-3 最近邻分类:一个清晰的情形(左),一个不太清晰的情形(右)。在第二种 情形中,标有问号的查询点的最近的邻居属于负类,但它的更多近邻属于正类

简单点说,一个新输入对应的输出就是存储器里相距最近的那个实例的输出。如果要判断一个新遇见的蘑菇是否可以食用,我们就把它归到记忆中与之最相似的蘑菇的那一类。

虽然十分简单,但很多情况下这种技术都出奇地有效。然而它毕竟是一种偷懒的方法,要为懒惰付出代价!不幸的是,为识别一个新实例所花费的时间可能与存储器中的实例数量成正比,除非用不那么偷懒的方法。这就好比有一个学生,虽然平常买了不少书,但是只在遇到问题时才去读这些书。

一个更具健壮性和灵活性的方法是考虑大小为k的近邻集合,而不仅仅是最相近的那一个,不难猜到这种方法被称为 K近邻(KNN)方法。它的灵活性来源于可以使用不同的分类方法。例如,新实例的输出可以用多数同意规则,即输出这k个近邻中占大多数的那一个输出。如果想要更加安全的方法,可以仅在这k个近邻的输出完全相同时才确定新实例的类别(一致同意规则),否则就输出“未知”。这个建议可以用在区分有毒的蘑菇时:如果输出“未知”,就联系当地警方寻求帮助。

如果面临的是一个回归问题(预测一个实数,例如蘑菇中有毒物质的含量),我们可以将这k个最相近的实例的输出平均值作为新实例的输出。

当然,这k 个实例到新实例的距离可能有所差别,而且在某些情况下,距离较近的实例对新实例的输出影响更大是很合理的。在这种被称为加权K近邻(WKNN)的方法中, 权重取决于距离。

设给定的正整数k\leqslant\ell\ell为已标记实例的个数);x 表示新的实例,是一个属性向量1

1featurevector若译为“特征向量”, 恐被误认为eigenvector,因此译作“属性向量”。——译者注

下面是一个用于估计x 所对应的输出y 的简单算法,分两个步骤。

(1) 在训练集中找到k 个下标i_1,\cdots,i_k,使得属性向量\boldsymbol{x}_{i_1},\cdots,\boldsymbol{x}_{i_k}与给定的x 最相近(根据某种给定的属性空间度量)。

(2)通过下面的加权平均来计算估计的输出,权重反比于属性向量之间的距离:

y=\frac{\displaystyle\sum_{j=1}^k\frac{y_{i_j}}{d(\boldsymbol{x}_{i_j},\boldsymbol{x})+d_0}}{\displaystyle\sum_{j=1}^k\frac{1}{d(\boldsymbol{x}_{i_j},\boldsymbol{x})+d_0}}\qquad\qquad\qquad\qquad\qquad\qquad\qquad(2.1)

其中d(\boldsymbol{x}_i,\boldsymbol{x})指两个向量在属性空间中的距离(例如欧氏距离),d_0是一个小的偏移常数,用以避免出现0作为除数的情况。d_0越大,距离较远的点的贡献就越大。如果d_0趋近于无穷大,那么这k 个实例的权重就几乎一样了。

WKNN算法很容易实现,并且相应的估计误差也很小。它的主要缺点是需要大量的内存空间,以及在测试阶段巨大的计算量。因此我们常常将已标记的实例进行聚类,用来减少所需的内存空间。聚类方法按照相似性将它们划分成一个个小组,并且只存储每个小组的原型(中心)。第15章会讨论更多的细节。

本书接下来将继续考虑新实例和内存中实例之间的距离,并且将这一想法一般化。核方法局部加权回归就可看作最近邻方法的一般化,这两种方法并不是粗鲁地直接将远处的点排除,而是根据它们到查询点的距离,灵活地赋予它们相应的重要性(权重)。

 梗概

KNN(K近邻)是一种原始的懒惰的机器学习方式:它只是把所有的训练实例存在存储器中(输入和对应的输出标记)。

当有一个新输入并需要计算其对应的输出时,在存储器中查找k 个最接近的实例。读取它们的输出,并根据它们的大多数或平均值推导出新实例的输出。当存储了非常多的实例时,训练阶段的懒惰会让预测阶段的响应时间变得很长。

相似的输入经常对应着相似的输出,这是机器学习领域的一个基本假设,因此KNN方法在很多实际案例中都有效。它与人类的某些“基于案例”的推理具有相似性。虽然这个方法简单粗暴,但它在很多现实案例中的效果都令人惊奇。

从现在起,不要做一个懒惰的学习者,别以为这样可以高枕无忧。继续读下面的章节,坚持学下去。早起的鸟儿有虫吃,睡懒觉只能肚子空空了。

目录

  • 版权声明
  • 第 1 章 引言
  • 第 2 章 懒惰学习:最近邻方法
  • 第 3 章 学习需要方法
  • 第一部分 监督学习
  • 第 4 章 线性模型
  • 第 5 章 广义线性最小二乘法
  • 第 6 章 规则、决策树和森林
  • 第 7 章 特征排序及选择
  • 第 8 章 特定非线性模型
  • 第 9 章 神经网络:多层感知器
  • 第 10 章 深度和卷积网络
  • 第 11 章 统计学习理论和支持向量机
  • 第 12 章 最小二乘法和健壮内核机器
  • 第 13 章 机器学习中的民主
  • 第 14 章 递归神经网络和储备池计算
  • 第二部分 无监督学习和聚类
  • 第 15 章 自顶向下的聚类:K 均值
  • 第 16 章 自底向上(凝聚)聚类
  • 第 17 章 自组织映射
  • 第 18 章 通过线性变换降维(投影)
  • 第 19 章 通过非线性映射可视化图与网络
  • 第 20 章 半监督学习
  • 第三部分 优化:力量之源
  • 第 21 章 自动改进的局部方法
  • 第 22 章 局部搜索和反馈搜索优化
  • 第 23 章 合作反馈搜索优化
  • 第 24 章 多目标反馈搜索优化
  • 第四部分 应用精选
  • 第 25 章 文本和网页挖掘
  • 第 26 章 协同过滤和推荐
  • 参考文献