|
|
作者简介作者简介：周济(1988-)，男，湖南工业大学智能信息处理研究所硕士研究生，研究方向为机器学习、数字图像；文志强(1973-)，男，博士，湖南工业大学计算机与通信学院副教授，研究方向为人工智能、机器视觉。0引言 集成学习最早由 hansen 和 salamon 提出［1］。他们研究发现，训练多个神经网络并将其结果按照一定的规则进行组合，能够显著提高整个学习系统的泛化性能。schapire通过构造性方法提出 boosting 算法［2］证明了这一观点。受到这些研究的启发，人们开始认识到集成学习所蕴涵的潜力和应用前景，集成学习成为近十年来机器学习领域最主要的研究方向之一。本文创新性地从理论分析和实验验证两个方面阐述了集成学习的有效性。 探讨一下标准的监督学习问题：一个学习问题是给定一些训练样本{（x1,y1),•••,（xm,ym)}得到一个未知的函数 y=f(x）。xi是一个表示第i个样本特征的向量， 一共有n个特征。例如，高度、宽度、颜色、年龄等。这个向量也叫做样本xi的特征。xi,j表示样本xi的第j个特征，在上下文意义明确的时候我们会省略这个下标i。
y的值是从类别集合{1，•••，k}中挑选出来的，监督学习主要是分类问题和回归问题，在这里我们主要讨论分类问题，而且训练样本会含有一些随机的噪声。给定一个训练集s，学习算法会输出一个分类器，这个分类器是关于这个真实的函数f的一个假设（近似）。WWW.11665.CoM给定一个新样本x，分类器能够预测出正确的y（类标签）值，用h1，…，hl表示分类器集合。
1有效性分析
分类器集成是用某些方法（典型的是加权或者不加权的投票）将一个分类器集合中各个分类器的独立决策结果组合起来形成最后的输出，从而对一个新的样本进行分类。监督学习中最活跃的研究方向是怎样更好地组合各个独立的分类器，集成后的分类准确率相对于各个独立的分类器往往有较大幅度的提高。
集成后的分类器比任何独立的单个分类器在分类时更加准确的充分且必要条件是：单个分类器要达到一定的准确率且个别分类器之间要有一定的差异性(hansen & salamon, 1990)。一定的准确率是指这个分类器的分类结果要比随机猜测要好，对于二分类问题来说就是单个分类器的准确率要超过50%。当两个分类器在一个新的数据集上的错误预测不一样就认为这两个分类器是有差异的。让我们来分析一下为什么准确率和差异性是非常重要的。用3个分类器来组合：{h1,h2,h3}，并且考虑一个新的样本x。如果这3个分类器是相似的（也就是没有足够大的差异），当h1(x)的分类结果是错误的时候，h2(x)和h3(x)也会是错误的。然而当分类器的错误分类不是同时发生的时候，如果h1(x)分类结果是错误的，h2(x)和h3(x)的分类结果可能是正确的，因此，使用多数投票法的时候就能够得到正确的分类结果。更严格地，如果假设空间l中所有的分类器hl的错误率p<12并且这些错误是彼此独立的，那么当多于l2的假设函数是错误的时候，采用多数投票法产生错误分类的概率，就是二项分布中位于错误率p以下的面积。图1显示了集成21个分类器的实验结果，并且每个分类器的错误率是0.3，我们用最简单的方式去集成这些分类器的预测结果——“投票”，比如说总是选择超过一半分类器预测的结果作为最终预测结果，在这里就是选出大于或等于11的预测结果作为最终预测结果，分类的错误率小于0.026，这个错误率要小于任何一个独立的分类器的错误率。用公式来表示就是：∑kx=11ck21(0.3)k(0.7)n－k=0.026389941,(n=21)(1)图121个假设函数的错误率
（假设每个函数的错误率是0.3并且相互独立）
如果这些独立分类器的错误率高于0.5，那么集成后的分类器采用多数投票法的错误率将会比单个的更高。因此，集成学习成功的一个关键问题就是构建一些相互独立并且错误率低于0.5的单个分类器。
这就是pac学习模型：弱学习算法和强学习算法的等价性问题,即任意给定仅比随机猜测略好的弱学习算法,可以将其提升为强学习算法。只满足这个结论并不能保证能构造出一个好的组合分类器，但是通常来说，满足这个条件的一般都是好的组合分类器，主要有3个原因：
（1）数据量方面。一个学习算法可以看成是从假设空间h去寻找一个最好的假设函数。当可用训练样本的数量远远小于假
空间大小的时候，就会有非常突出的数据问题。没有充足的训练样本，学习算法就会从假设空间h中找到很多不同的假设函数，而这些假设在训练集上的正确率却是相同的，此时就很难抉择哪个假设在测试集上会得到好的结果了。通过集成这些假设就可以减少选错分类器的风险。
图2（a）描画了这种情况。外面的曲线表示假设空间h，里面的曲线表示能在训练集上达到一个较高的准确率的假设函数集合。点f表示这个真实的假设函数，从图中可以看出，对这些比较准确的假设函数加以平均，能够较好地近似表示f。
(2)计算问题。很多学习算法都会遇到局部最优的状况，例如，神经网络是通过梯度下降来最小化错误率的，假如训练集是足够充足的（此时数据量问题就基本不存在了），学习算法也很难得到全局最优解。实际上，找出最优化的神经网络和决策树是np-hard［3］。通过把不同起始点得到的分类器集成可以更好地靠近这个未知的全局最优解，并且这个近似的假设函数常比任何一个单独的分类器效果都要好，图2(b)表示了这种情况。
图2组合后的分类器比单个分类器效果好的3个主要原因
（3）假设的描述问题。大多数的机器学习实际应用中，很难用假设空间h中的假设去表示真实的f，通过对假设空间h中的假设进行加权求和进而扩展假设空间h的规模或许能够表示真实函数f，图2(c)表示了这种情况。在图2中,空间h是一个在给定的训练数据集上能搜索到的有效的假设空间。
这3个基本问题是导致学习算法有可能失败的3个最重要的方面。因此，一个好的集成方法要能够尽可能地减少（甚至是消除）标准学习算法这3个缺点。
2不同集成方法比较
构造单个基分类器和集成分类器的方法主要有:贝叶斯投票、处理训练数据集［4］ 、处理输入特征［5］、处理输出类标签［6］、引入随机性［7］等。
为了比较不同集成方法的效果，我们进行了一些对比试验，使用的是uci标准数据库,一共选择了33组数据，实验平台是weka。
2.1实验结果
表1是其中的一个结果，显示adaboost算法比较的结果，分别是：好、差、相同（几乎）,例如：14-0-19表示random c4.5和 c4.5比， 14次好、0次差、19次类似。虽然引入随机化以后在非常大的数据集上有时候比bagging的效果好，但是通常来说bagging和随机森林的准确率差不多。
需要注意的是用来训练的数据几乎是没有噪声的。当加入20%的人工噪声（错误类标签）时bagging和adaboost的效果有了明显的差别。adaboost效果不是很好（对噪声敏感），但是bagging表现比较好，随机森林一般。
表13种集成方法的比较
c4.5adaboost c4.5bagged c4.5random c4.514-0-191-7-256-3-24bagged c4.511-0-221-8-24adaboost c4.517-0-16表29个含有20%人工噪声的数据集比较
c4.5adaboost c4.5bagged c4.5random c4.55-2-25-0-40-2-7bagged c4.57-0-26-0-3adaboost c4.53-6-0理解这个结果的关键要从上面提出的学习算法的3个不足出发，分别是：数据问题、计算问题和表示问题。对于c4.5决策树算法来说，这3个问题都会出现，而分类器集成能有效减少这3个不足的影响，所以效果比单个c4.5要好。
2.2实验分析
决策树算法实质上是将特征空间用一些和坐标轴平行的线段来划分，每一个线段就代表了一个节点，也就是一次决策。
如果真实的函数f能够被一棵小的决策树表示的话，c4.5不需要集成也能有较好的效果。但是如果真实函数f需要一棵很大的决策树才能正确表示的话，那么c4.5为了找到一个好的分类函数就会需要一个很大的训练数据集，这时数据问题就出现了。
出现计算问题是由于在寻找最优决策树（例如，最小的）的过程中进行了一系列的贪心（局部最优）决策。如果一个决策错了，就会导致训练数据集被错误划分，并且会影响接下来的决策，所以c4.5的高度是不稳定的，训练数据集的任何改变都会使决策树的结果有很大的改变。
表示问题主要是由于决策树用平行于坐标轴的线段划分特征空间。如果这个真实的分类边界并不是和坐标轴完全平行的，c4.5就要求有一颗无限大的树来正确表示这个边界，也就是用无限多的平行于坐标轴的小线段来近似表示那个不平行于坐标轴的边界，如图3所示（图3（a）是3个小的决策树分类边界，每个有5个节点。图3（b）是这3个决策树通过多
数投票产生的边界，它等价于一个13个节点的复杂决策树边界），也就是说用很多小的决策树经过组合以后能够达到大决策树的效果，从而实现对非平行与坐标轴的边界近似表示。
图3多个决策树投票后产生的边界
现在来考虑3个集成方法：adaboost、bagging和随机森林。bagging和随机森林都是独立构造各个基分类器，也就是子决策树。bagging通过处理输入的数据集来独立构造基分类器，而随机森林则是直接改变c4.5的决策。实质上这两种做法类似于贝叶斯投票，不同的假设在训练集的不同子区域上面的准确率是不一样的，因此在训练集的某个子区域上表现最好的假设起到更多的作用，从这个角度来说，这两种做法主要解决了数据问题，部分解决了计算问题，但是对表示问题并没有直接的影响。
相比之下，adaboost通过构造每一个新的决策树（子分类器）去消除前面决策树加权投票没有完全解决的残留错误。adaboost直接去优化这些加权的投票，因此，直接瞄准了表示问题。但是，这种直接优化的做法会增加过拟合的风险，因为集成后的假设空间通常大于原始算法的假设空间。
这样，我们就能理解在大数据机上随机森林为什么比bagging表现更好了。因为bootstrap抽样法产生了一个和原始训练集非常类似的更大的训练集，导致了训练出来的基本分类器（决策树）差异不明显。尽管很容易产生一些垃圾决策树，但随机森林产生的基分类器的差异性却十分明显。
3结语
集成学习是一种从弱分类器产生强分类器的有效且稳定的方法。本文简单总结了一些主要的集成方法并且分析了集成学习比单个分类器效果要好的3个主要原因。本文用一些实验证明了这些结论，并进行了说明［8］，但是对adaboost和一些底层算法的相互作用［9］没有讨论。大多数与adaboost结合的算法都有全局性的特点，例如学习一个相对低维的决策边界。是否存在一些局部算法（例如径向基函数或者最近邻方法）能和adaboost结合，从而产生新的算法，值得进一步研究。
参考文献参考文献：
\[1\]hansen l k,salamon p.neural network ensembles［j］.pattern analysis and machineintelligence, ieee transactions on, 1990,12(10):9931001.
［2］schapire r e. the strength of weak learnability［j］. machine learning, 1990, 5(2): 197227.
［3］hyafile l , rivest r l. constructing optimal binary decision trees is npcompltet［j］.information processing letters,1976，5(1)：1517.
［4］freundy,schapirere.a decisiontheoretic generalization of online learning and a application to boosting［z］.tech.rep,at&t bell laboratories,murray hill,nj,1995.
［5］dietterichtg,bakirig. solving multiclass learning problems via errorcorrecting output codes［j］. journal of artificial intelligence research,1995(2):263286.
［6］kolenjf ,pollackj b. back propagation is sensitive to initial conditions［j］.in advances in neural information processing systems, san francisco, ca.morgan kaufmann,1991(3): 860867.
［7］chipman h, george e, mcculloch r. bayesian cart［r］.technicalreport. chicago:department of statistics, university of chicago, 1996.
［8］王清.集成学习中若干关键问题的研究［d］. 上海：复旦大学 ，2011.
［9］方育柯.集成学习理论研究及其在个性化推荐中的应用［d］.
|
|
|
|
|
