拟自适应分类随机森林算法

拟自适应分类随机森林算法马景义吴喜之谢邦昌2011-12-1315:00:25来源：《数理统计与管理》(京)2010年5期第805～811页内容提要：本文给出了集成学习模型可以收敛的集成学习算法，拟自适应分类随机森林算法。拟自适应分类随机森林算法综合了Adaboost算法和随机森林算法的优势，实验数据分析表明，训练集较大时，拟自适应随机森林算法的效果会好于随机森林算法。另外，拟自适应分类随机森林算法的收敛性确保它的推广误差可以通过训练集估计，所以，对于实际数据，拟自适应分类随机森林算法不需要把数据划分为训练集和测试集，从而，可以有效地利用数据信息。关键词：集成学习拟自适应随机森林作者简介：马景义，中央财经大学统计学院（北京100081）；吴喜之，中国人民大学统计学院（北京100872）；谢邦昌，中央财经大学统计学院（北京100081），台湾辅仁大学统计资讯学系（台北24205）。0引言通过对的训练，分类树[1]、C4.5[2]和神经网络[3]等算法都可以得到预测y的函数，或者模型；分类问题的集成学习方法(ensemblelearningmethods)则把多个不同个体分类模型的预测结果集合到一起，通过投票，得到一个分类更精确的预测结果。这里个体分类模型的投票模型就是集成学习模型；而个体分类模型被称作基学习模型(baselearningmodel)，通过基学习算法获得。在一类集成学习算法中，基学习模型可以被视为某个随机模型的实现。例如Bagging分类树算法中，通过基学习算法（分类树算法）训练，从中等权重抽取的随机自助训练集(bootstraptrainingdata)L，得到的随机模型可以被表示为f(x；L)，f指代采用分类树算法得到的模型，L为随机参数。只要获得L的随机实现，就可以通过分类树算法得到基学习模型f(x；)，i=l，…，m。每个基学习器模型以权重1/m（等权重）投票，就可以得到集成学习模型，或者Bagging分类树模型其中，I（·）是示性函数。出于简便，本文后面部分将类似Bagging分类树模型，简称特定集成学习算法的集成学习模型。另外，需要说明的是，等权重自助抽样权重为N维向量。本文后面的部分中，自助抽样权重也是N维向量，自助训练集的大小为N。以自助权重从中抽取自助训练集指，独立地，从中的元素中随机选出（中第n个样本被选中的概率为自助抽样权重的第n个元素，n=1，…，N）N个样本组成自助训练样本。Breiman的分类随机森林算法[4]业已证明为集成学习算法中最为优秀的算法之一，实践表明，分类随机森林模型的预测性能要优于Bagging分类树模型。和Bagging分类树算法类似，分类随机森林算法的基学习模型也可以表示为随机模型h（x；θ）的实现，只是h（x；θ）通过随机变量划分分类树算法获得。此处，h代表以随机变量划分分类树得到的模型；随机参数θ表示两个方面的随机要素：从中等权重获得的随机自助训练样本L，以及对L实施随机变量划分分类树算法的过程中，在每个节点处产生划分条件时，随机选择的p个自变量。L的第i个随机实现，以及每个节点处随机选择的p个自变量被确定，则意味着得到了θ的第i个实现，相应的，基学习模型h(x；)就可以被确定，i=1，…，m。基学习模型的等权投票模型就是分类随机森林模型。Adaboost算法是另一个优秀的集成学习算法[5-6]，实践中，它的集成学习模型和分类随机森林模型均有上佳，而且难分伯仲的预测效果。Adaboost算法也是通过多个基学习器模型的投票得到集成学习模型，基学习器模型也利用对的自助训练集训练获得；然而，在获取自助训练集时，它采用自适应自助抽样权重，在集成基学习器模型时，采用自适应投票权重。所谓的自适应自助抽样权重指，随着算法的运行，根据已得到的基学习器模型确定下一个自助训练集的自助抽样权重，更具体地，第i个自助抽样权重和前i-1个基学习器模型有关，有了后，以为抽样权重，从中抽取自助训练样本。自适应投票权重指，Adaboost算法采用基学习器算法，如分类树算法，得到基学习器模型f(x；)（f指代分类树模型，Adaboost算法中也使用C4.5和弱神经网络算法为基学习器算法）后，将它们集成为集成学习模型理论研究表明，在样本量N→∞时，Adaboost算法的集成学习模型的推广误差(generalizationerror)可以收敛到贝叶斯误差(Bayesrisk)[7]；然而，许多应用问题中，N→∞是不能被保证的，例如那些样本成本非常高的研究。Breiman[8]指出：N非常大，并不意味着无穷大，许多数据的研究中，N可能非常大，但上述的收敛并不能被保证；Adaboost算法的集成学习模型的预测误差之所以较小，很可能与自适应自助抽样权重和自适应投票权重有关。本文的立意如下：随机森林算法和Adaboost算法，二者集成学习模型的分类性能难分高下，然而，二者在基学习算法的选择，自助抽样权重的选择，投票权重的选择等三个方面迥然不同；所以，本文考虑建立一个新的算法，把二者的优点集中在一起；以期得到性能更佳的集成学习模型。在给出新集成算法时，需要考虑一个现实问题。Adaboost算法的基学习模型并不能被表示为某个随机模型的实现，因为不同的基学习模型对应的自助训练集的分布不同；于是，其集成学习模型的收敛性（m→∞）难以被严格证明。如果一个集成学习算法（例如随机森林算法）的集成学习模型是收敛的，那么，用以评价集成学习模型预测效果的推广误差可以通过训练集估计，也就是推广误差的Out-of-Bag估计[9]，反之，评价集成学习模型预测效果的推广误差需通过测试集估计，也就是说数据必须被分成训练集和测试集两个部分。然而，数据挖掘中的分类任务中，数据并不都是海量数据，为了评估模型，不得不减少训练集的大小，将导致模型的预测性能下降。换而言之，对于同样的数据，相比随机森林算法，新算法得到的集成学习模型的性能可能更好，但为了评估集成学习模型的性能，不得不使用原始数据中的部分数据得到集成学习模型，其预测性能很可能差于随机森林训练所有原始数据得到的集成学习模型。本文考虑模仿Adaboost算法中的自适应机制，发明拟自适应机制，并把它运用到分类随机森林算法中，给出集成学习模型可以收敛的拟自适应分类随机森林算法算法。值得一提的是，本文研究的内容只和分类随机森林算法及Adaboost算法有关，机器学习领域中还有其他优秀的集成学习算法和理论，如随机决策森林[10]及拓展算法[11-12]。本文后续的研究将进一步拓宽视野，从尽可能多的集成学习算法中归纳出更一般性的结论。本文的内容安排如下：第1节中，给出拟自适应分类随机森林算法算法，拟自适应分类随机森林模型和分类随机森林模型的预测效果比较，拟自适应分类随机森林模型的收敛性证明及其推广误差的Out-of-Bag估计；第2节是本文的结论。1拟自适应分类随机森林算法本节中，1.1节将给出拟自适应分类随机森林算法的细节，1.2中用机器学习的基准数据比较拟自适应分类随机森林模型和分类随机森林模型的预测效果，1.3节给出拟自适应分类随机森林模型的收敛性证明的收敛性证明，1.4节给出拟自适应分类随机森林模型的推广误差的Out-of-Bag估计。1.1拟自适应Adaboost分类随机森林算法描述本小节首先给出，以随机划分分类树为基学习算法的Adaboost算法中，自适应抽样权重和自适应投票权重的定义方式。定义拟自适应分类随机森林算法如下。第1步，运行以随机划分分类树为基学习算法的Adaboost算法S次，记录S个再抽样权重向量，s=1，…，S。1.2拟自适应分类随机森林算法的预测效果本小节以机器学习算法比较的基准数据twonorm数据和threenorm数据[13]（twonorm数据的贝叶斯误差为0.025，threenorm数据的贝叶斯误差为0.1154），经验分析拟自适应分类随机森林算法的有效性。每个数据，共生成自变量为21的5个数据集，大小依次为100、200、300、400和10000，前面4个数据集为训练集，最后1个数据为测试集。前面4个数据集可以得到4个分类随机森林模型（m=10000，随机选择3个变量生成划分条件，模型记为RF）和4个拟自适应分类随机森林模型（S=50，m=10000，随机选择3个变量生成划分条件，模型记为QRF），然后，用第5个数据集估计前面训练出的集成学习模型的推广误差，见下页表1。关于threenorm，在训练集大小为100和200时，分类随机森林模型的推广误差小于拟自适应分类随机森林的推广误差，在训练集大小为300和400时，随机森林算法的推广误差大于拟自适应随机森林算法的推广误差。关于twonorm，在训练集大小为100时，随机森林算法的推广误差小于拟自适应随机森林算法的推广误差，在训练集大小为200，300和400时，随机森林算法的推广误差大于拟自适应随机森林算法的推广误差。出现上述情况的原因如下：以自适应抽样权重抽样时，自助训练集中包含的原始数据占原始数据比例常小于50%[6]，所以原始训练集较小时，其效果不如等权重自助抽样方法（等权自助抽样训练集中包含的原始数据占原始数据的比例约为63%）。表1四组数据，集成模型推广误差的估计训练集大小模型threenorm数据twonorm数据n=100RF0.162700.03370QRF0.188500.03655n=200RF0.148600.02680QRF0.153050.02320n=300RF0.123400.02670QRF0.113700.02505n=400RF0.124300.02135QRF0.115600.01850所以，在数据量较大时，本文给出的拟自适应分类随机森林算法比随机森林算法更具竞争力。另外，Breiman[4]的分析表明：训练集较大时，分类随机森林模型和以分类树为基学习算法的Adaboost算法模型的预测效果不相上下，训练集较小时，分类随机森林模型的预测效果要略差。这和本文的结论隐隐相合。1.3拟自适应分类随机森林算法的收敛性本节探讨拟自适应分类随机森林算法的收敛性。从中等概率选择的自助抽样权重向量w的样本空间有限，从w为自助抽样权重，从中得到的自助训练集L的样本空间也有限。以L为训练集，随机划分分类树算法得到预测模型的过程中，每个节点处，随机选择的p个划分变量的样本空间有限，节点个数也有限，所以，随机划分分类树算法得到的基学习器模型h（x；π）和它对应的投票权重φ的样本空间有限，我们把它们表示为这个估计就是推广误差的Out-of-Bag估计，其效果和大小N的测试集得到的推广误差估计一致。2结论本文给出了集成学习模型可以收敛的拟自适应分类随机森林算法，拟自适应分类随机森林算法把拟自适应自助抽样权重和拟自适应投票权重加权运用到分类随机森林算法中。经验表明，训练集较大时，拟自适应随机森林算法的效果会好于随机森林算法。拟自适应分类随机森林算法的收敛性确保它的推广误差可以通过训练集估计。这样，对于实际数据，拟自适应分类随机森林算法不需要把数据划分为训练集和测试集，从而，可以有效地利用数据信息，尤其是对于样本获取成本较高的应用。参考文献：[1]BreimanL,FriedmanJ,OlshenR,andStoneC.ClassificationandRegressionTrees[M].Monterey,CA:WadsworthandBrooks,1984.[2]QuinlanJR.Bagging,boosting,andC4.5[A].In:ProceedingsoftheThirteenthNationalConferenceonArtificialIntelligence,725-730[C].Cambridge,MA:AAAIPress/MITPress,Portland,Oregon1996.[3]RipleyBD.PatternRecognitionandNeuralNetworks[M].NewYork:CambridgeUniversityPress,1996