关于预测的两类核心算法

解决函数逼近问题有两类最有效和获得广泛使用的算法：惩罚线性回归和集成方法。本文将介绍这些算法，概述它们的特性，回顾算法性能对比研究的结果，以证明这些算法始终如一的高性能。

1.1　为什么这两类算法如此有用

有几个因素造就了惩罚线性回归和集成方法成为有用的算法集。简单地说，面对实践中遇到的绝大多数预测分析（函数逼近）问题，这两类算法都具有最优或接近最优的性能。这些问题包含：大数据集、小数据集、宽数据集（wide data sets）[1]、高瘦数据集（tall skinny data sets）[2]、复杂问题、简单问题，等等。Rich Caruana及其同事的两篇论文为上述论断提供了证据。

1．“An Empirical Comparison of Supervised Learning Algorithms,” Rich Caruana，Alexandru Niculescu-Mizi。

2．“An Empirical Evaluation of Supervised Learning in High Dimensions,” Rich Caruana, Nikos Karampatziakis和Ainur Yessenalina。

在这两篇论文中，作者选择了各种分类问题，用各种不同的算法来构建预测模型。然后测试这些预测模型在测试数据中的效果，这些测试数据当然不能应用于模型的训练阶段，对这些算法根据性能进行打分。第一篇论文针对11个不同的机器学习问题（二元分类问题）对比了9个基本算法。所选问题来源广泛，包括人口统计学、文本处理、模式识别、物理学和生物学。表1-1列出了此篇论文所用的数据集，所用名字与论文中的一致。此表还展示了针对每个数据集做预测时使用了多少属性（特征）以及正例所占的百分比。

术语“正例”（positive example）在分类问题中是指一个实验（输入数据集中的一行数据）其输出结果是正向的（positive）。例如，如果设计的分类器是判断雷达返回信号是否表明出现了一架飞机，那么正例则是指在雷达视野内确实有一架飞机的那些结果。正例这个词来源于这样的例子：两个输出结果分别代表出现或不出现。其他例子还包括在医学检测中某种疾病出现或不出现，退税中是否存在欺骗。

不是所有的分类问题都处理出现或不出现的问题。例如通过计算机分析一个作家发表的作品或者其手写体的样本来判断此人的性别：男性或女性，在这里性别的出现或不出现是没有什么意义的。在这些情况下，指定哪些为正例、哪些为负例则有些随意，但是一旦选定，在使用中要保持一致。

在第1篇论文的某些数据集中，某一类的数据（例子）要远多于其他类的数据（例子），这叫作非平衡（unbalanced）。例如，2个数据集Letter.p1 和Letter.p2.都是用于解决相似的问题：在多种字体下正确地分出大写字母。Letter.p1的任务是在标准字母的混合集中正确区分出大写字母O，Letter.p2的任务是将字母正确划分成A-M和N-2的两类。表1-1中的“正例百分比”一栏反映了这种数据非平衡的差异性。

表1-1　机器学习算法比较研究中问题的梗概

表1-1还显示了每个数据集所使用的属性（特征）的数量。特征就是基于此进行预测的变量。例如，预测一架飞机能否按时到达目的地，可能导入下列属性（特征）：航空公司的名字、飞机的制造商和制造年份、目的地机场的降水量和航线上的风速与风向等等。基于很多特征做预测很可能是一件很难说清楚是福还是祸的事情。如果导入的特征与预测结果直接相关，那么当然是一件值得祝福的事情。但是如果导入的特征与预测结果无关，就是一件该诅咒的事情了。

注意

当数据含有大量的特征，但是没有足够多的数据或时间来训练更复杂的集成方法模型时，惩罚回归方法将优于其他算法。

Caruana等人的最新研究（2008年）关注在特征数量增加的情况下，上述算法的性能。也就是说这些算法面对大数据表现如何。有很多领域的数据拥有的特征已远远超过了第一篇论文中的数据集的规模。例如，基因组问题通常有数以万计的特征（一个基因对应一个特征），文本挖掘问题通常有几百万个特征（每个唯一的词或词对对应一个特征）。线性回归和集成方法随着特征增加的表现如表1-3所示。表1-3列出了第2篇论文中涉及的算法的评分情况，包括算法针对每个问题的性能得分，最右列是此算法针对所有问题的平均得分。表1-3中的算法依次为：BSTDT（Boosted Decision Tress）-提升决策树；RF（Random Forests）-随机森林；BAGDT（Bagged Decision Trees）-投票决策树；BSTST（Boosted Stumps）-提升二叉树：LR（Logistic Regression）-逻辑回归；SVM（Support Vector Machines）-支持向量机；ANN（Artificial Neural Nets）-人工神经网络；KNN（Distance Weighted kNN）-距离加权K最近邻；PRC（Voted Perceptrons）-表决感知器；NB（Naive Bayes）-朴素贝叶斯。NB（Naive Bayes）-朴素贝叶斯。

表1-2中的问题是依其特征规模依次排列的，从761个特征到最终的685569个特征。线性（逻辑）回归在11个测试中的5个进入前3。而且这些优异的分数主要集中在更大规模的数据集部分。注意提升决策树（表1-2标为BSTDT）和随机森林（表1-2标为RF）其表现仍然接近最佳。它们针对所有问题的平均得分排名第1、第2。

表1-2　本文涵盖的机器学习算法面对大数据问题的性能

本文涵盖的算法除了性能外，在其他方面也有优势。惩罚线性回归模型一个重要优势就是它训练所需时间。当面对大规模的数据时，训练所需时间就成为一个需要考量的因素。某些问题的模型训练可能需要几天到几周，这往往是不能忍受的，特别是在开发早期，需要尽早在多次迭代之后找到最佳的方法。惩罚线性回归方法除了训练时间特别快，部署已训练好的模型后进行预测的时间也特别快，可用于高速交易、互联网广告的植入等。研究表明惩罚线性回归在许多情况下可以提供最佳的答案，在即使不是最佳答案的情况下，也可以提供接近最佳的答案。

而且这些算法使用十分简单，可调参数不多，都有定义良好、结构良好的输入数据类型。它们可以解决回归和分类的问题。当面临一个新问题的时候，在1～2小时内完成输入数据的处理、训练模型、输出预测结果是司空见惯的。

这些算法的一个最重要特性就是可以明确地指出哪个输入变量（特征）对预测结果最重要。这已经成为机器学习算法一个无比重要的特性。在预测模型构建过程中，最消耗时间的一步就是特征提取（feature selection）或者叫作特征工程（feature engineering）。就是数据科学家选择哪些变量用于预测结果的过程。

1.2　惩罚回归方法

惩罚线性回归方法是由普通最小二乘法（ordinary least squares，OLS）衍生出来的。而普通最小二乘法是在大约200年前由高斯（Gauss）和法国数学家阿德里安-马里•勒让德（Legendre）提出的。惩罚线性回归设计之初的想法就是克服最小二乘法的根本缺陷。最小二乘法的一个根本问题就是有时它会过拟合。如图1-1所示，考虑用最小二乘法通过一组点来拟合一条直线。这是一个简单的预测问题：给定一个特征x，预测目标值y。例如，可以是根据男人的身高来预测其收入。根据身高是可以稍微预测男人的收入的（但是女人不行）。

图1-1　普通最小二乘法拟合

图1-1中的点代表（男人的身高、男人的收入），直线代表使用最小二乘法的预测结果。在某种意义上说，这条直线就代表了在已知男人身高的情况下，对男人收入的最佳预测模型。现在这个数据集有6个点。假设这个数据集只有2个点。想象有一组点，就像图1-1中的点，但是你不能获得全部的点。可能的原因是要获得所有这些点的代价太昂贵了，就像前面提到的基因组数据。只要有足够多的人手，就可以分离出犯罪分子的基因组，但主要问题是代价的原因，你不可能获得他们的全部基因序列。

以简单的例子来模拟这个问题，想象只给你提供当初6个点中的任意2个点。那么拟合出来的直线会发生哪些变化？这将依赖于你得到的是哪2个点。实际看看这些拟合的效果，可以从图1-1中任意选出2个点，然后想象穿过这2个点的直线。图1-2展示了穿过图1-1中2个点的可能的直线。可以注意到拟合出来的直线依赖于这2个点是如何选择的。

图1-2　只有2个点的情况下拟合的直线

使用2个点来拟合一条直线的主要问题是针对直线的自由度（degrees of freedom）[3]没有提供足够的数据。一条直线有2个自由度。有2个自由度意味着需要2个独立的参数才能唯一确定一条直线。可以想象在一个平面抓住一条直线，然后在这个平面上下滑动这条直线，或者旋转它以改变其斜率。与x轴的交点和斜率是相互独立的，它们可以各自改变，两者结合在一起确定了一条直线。一条直线的自由度可以表示成几种等价的方式（可以表示成与y轴的交点和斜率、直线上的2个点，等等）。所有这些确定一条直线的表示方法都需要2个参数。

当自由度与点数相同时，预测效果并不是很好。连接这些点构成了直线，但是在不同点对之间可以形成大量不同的直线。对在自由度与点数相同的情况下所做的预测并不能报太大的信心。图1-1是6个点拟合一条直线（2个自由度）。也就是说6个点对应2个自由度。从大量的人类基因中找到可导致遗传基因的问题可以阐明相似的道理。例如要从大约20000个人类基因中找到可导致遗传的基因，可选择的基因越多，需要的数据也越多。20000个不同基因就代表20000个自由度，甚至从20000个人获取的数据都不足以得到可靠的结果，在很多情况下，一个相对预算合理的研究项目只能负担得起大约500个人的样本数据。在这种情况下，惩罚线性回归就是最佳的选择了。

惩罚线性回归可以减少自由度使之与数据规模、问题的复杂度相匹配。对于具有大量自由度的问题，惩罚线性回归方法获得了广泛的应用。在下列问题中更是得到了偏爱：基因问题，通常其自由度（也就是基因的数目）是数以万计的；文本分类问题，其自由度可以超过百万。第4章将提供更多的细节：这些方法如何工作、通过示例代码说明算法的机制、用Python工具包实现一个机器学习系统的过程示例。

1.3　集成方法

集成方法（ensemble methods）的基本思想是构建多个不同的预测模型，然后将其输出做某种组合作为最终的输出，如取平均值或采用多数人的意见（投票）。单个预测模型叫作基学习器（base learners）。计算学习理论（computation learning theory）的研究结果证明只要基学习器比随机猜测稍微好些（如果独立预测模型的数目足够多），那么集成方法就可以达到相当好的效果。

研究人员注意到某些机器学习算法输出结果不稳定，这一问题导致了集成方法的提出。例如，在现有数据集基础上增加新的数据会导致最终的预测模型或性能突变。二元决策树和传统的神经网络就有这种不稳定性。这种不稳定性会导致预测模型性能的高方差，取多个模型的平均值可以看作是一种减少方差的方法。技巧在于如何产生大量的独立预测模型，特别是当它们都采用同样的基学习器时。第6章将深入讨论这是如何做到的。方法很巧妙，理解其运作的基本原理也相对容易。下面是其概述。

集成方法为了实现最广泛的应用通常将二元决策树作为它的基学习器。二元决策树通常如图1-3所示。图1-3中的二元决策树以一个实数x作为最初的输入，然后通过一系列二元（二值）决策来决定针对x的最终输出应该是何值。第1次决策是判断x是否小于5。如果回答“no”，则二元决策树输出值4，在由决策的方框下面标为“No”的分支引出的圆圈内。每个可能的x值通过决策树都会产生输出y。图1-4将输出y画为针对决策树的输入x的函数。

图1-3　二元决策树示例

图1-4　二元决策树示例输入-输出图

由此产生的问题是：这些比较值是如何产生的（如例子中的x<5?），输出的值是如何确定的（图1-3决策树底部圆圈中的值）。这些值都来自于基于输入数据的二元决策树的训练。训练算法不难理解，在第6章会详细叙述。需要注意的很重要的一点是给定输入数据，训练所得的二元决策树的这些值都是确定的。一种获得不同模型的方法是先对训练数据随机取样，然后基于这些随机数据子集进行训练。这种技术叫作投票［bagging，来自于自举集成算法（bootstrap aggregating）的简化说法］。此方法可以产生大量的具有稍许差异的二元决策树。这些决策树的输出经过平均或投票产生最终的结果。第6章将描述此项技术的细节和其他更有力的工具。

1.4　算法的选择

这2类算法的概要比较如表1-4所示。惩罚线性回归的优势在于训练速度非常快。大规模数据集的训练时间可以是小时、天，甚至是几周。要获得一个可以部署的解决方案往往需要进行多次训练。过长的训练时间会影响大数据问题的解决进度及其部署。训练所需时间当然越短越好，因此惩罚线性回归因其训练所需时间短而获得广泛使用就是显而易见的了。依赖于问题，此类算法相比集成方法可能会有一些性能上的劣势。第3章将更深入地分析哪类问题适用于惩罚回归，哪类问题适用于集成方法。即使在某些情况下，惩罚线性回归的性能不如集成方法，它也可以是建立一个机器学习系统的有意义的第一步尝试。

表1-4　惩罚线性回归与集成方法权衡比较

在系统开发的早期阶段，为了特征的选择、进一步明确问题的形式化描述，训练的过程往往需要多次迭代。决定哪些特征作为预测模型的输入是需要考虑的。有时这个过程是显而易见的，但是通常需要多次迭代之后才逐渐显现出来。把能找到的所有特征都输入进去通常不是一个好的解决方案。

试错法是确定模型最佳输入的典型方法。例如，如果想预测网站的用户是否会点击某个广告链接，首先用到用户的人口统计学信息。但是结果可能并不能达到想要的精度，因此尝试导入用户在此网站过去行为的信息：在过去的网站访问过程中，此用户点击过哪些广告或购买过哪些产品。增加用户访问此网站之前的其他网站的相关信息也会有些帮助。这些尝试都导致了一系列的实验：导入新的数据，然后看看新的数据对结果是否有帮助。这种迭代过程在2个方面都是很耗时的：数据的处理、预测模型的训练。惩罚线性回归通常要比集成方法快，而这种时间上的差异性是机器学习系统开发阶段需要考虑的一个重要因素。

例如，如果训练集合在GB级别，惩罚线性回归算法的训练时间在30分钟这个级别，集成方法可能需要5～6小时。如果特征工程阶段需要10次迭代来选择最佳特征集合，则单单这个阶段就会产生1天对应1周的时间差异。一个有用的技巧就是在开发的早期阶段，如特征工程阶段，利用惩罚线性模型进行训练。这给数据科学家提供一个基本的判断：哪些变量（特征）是有用的、重要的，同时提供了一个后续与其他算法性能比较上的基线。

除了可以获得训练时间上的收益，惩罚线性方法产生预测结果也比集成方法快得多。产生预测结果需要使用一个训练好的模型。对于惩罚线性回归，训练好的模型就是一系列实数：每个实数对应一个用于做预测的特征。所涉及的浮点操作的次数就是用来做预测的变量数。对于对时间高度敏感的预测，如高速交易、互联网广告植入，计算时间上的差异往往意味着盈利还是亏损。

对于一些问题，线性方法相比集成方法可以获得同等或更好的性能。一些问题不需要复杂的模型。第3章将详细讨论问题的复杂度，数据科学家的任务就是如何平衡问题的复杂度、预测模型的复杂度和数据集规模，以获得一个最佳的可部署模型。基本思想是如果问题不是很复杂，而且不能获得足够多的数据，则线性方法比更加复杂的集成方法可能会获得全面更优的性能。基因组数据就是此类问题的典型代表。

一般的直观感受是基因数据规模巨大。当然以比特为单位，基因数据集确实是非常庞大的，但是如果为了产生准确的预测，则其规模还需要进一步增加。为了理解两者之间的差别，考虑下面一个假想的实验。假设有2个人，一个人有可遗传条件基因，另外一个人没有。如果有这2个人的基因序列，那么能确定哪个基因是可遗传条件基因？显然，这是不可能的，因为这2个人之间有很多基因是不同的。那么需要多少人才能完成这个任务呢？至少人数要与基因数相等，如果考虑到噪声，就需要更多的人了。人类大约有20000个基因，因计算方法不同而略有差异。获得每条数据大约需要1000美元，要获得足够多的数据以完美地解决此问题至少需要2000万美元。

就像本文前面讨论的那样，这种情况与用2个点来拟合一条直线非常相似。模型的自由度要比数据点少。数据集规模通常需要是自由度的倍数关系。因为数据集的规模是固定的，所以需要调整模型的自由度。惩罚线性回归的相关章节将介绍惩罚线性回归如何支持这种调整以及依此如何达到最优的性能。

参考文献

[1]　宽数据集（wide data set）指每次观测时有大量的测量项，但是观测次数有限的数据。若把数据看成表格形式，则此类数据集列数很多，而行数有限。典型的此类数据集包括神经影像、基因组以及其他生物医学方面的。——译者注。

[2]　高瘦数据集（tall skinny data set）指每次观测时测量项有限，但是进行了大量的观测。若把数据看成表格的形式，则此类数据集列数有限，行数很多。典型的此类数据集包括临床试验数据、社交网络数据等。——译者注。

[3]　自由度：统计学上的自由度（degree of freedom, df）是指当以样本的统计量来估计总体的参数时，样本中独立或能自由变化的自变量的个数称为该统计量的自由度。

本文节选自《Python机器学习——预测分析核心算法 》

内容简介

在学习和研究机器学习的时候，面临令人眼花缭乱的算法，机器学习新手往往会不知所措。本书从算法和Python语言实现的角度，帮助读者认识机器学习。

本书专注于两类核心的“算法族”，即惩罚线性回归和集成方法，并通过代码实例来展示所讨论的算法的使用原则。全书共分为7章，详细讨论了预测模型的两类核心算法、预测模型的构建、惩罚线性回归和集成方法的具体应用和实现。

本书主要针对想提高机器学习技能的Python开发人员，帮助他们解决某一特定的项目或是提升相关的技能。

本文仅用于学习和交流目的，不代表异步社区观点。非商业转载请注明作译者、出处，并保留本文的原始链接。

本文转载自异步社区。

原文链接：https://www.epubit.com/articleDetails?id=NC7E3EF935950000112A61360D5EE18B5