基于局部有效性的选择性决策树集成

基于局部有效性的选择性决策树集成（申请南京大学理学学士学位论文）培养单位：南京大学计算机科学与技术系专业：计算机科学与技术本科生：俞扬指导教师：周志华教授二○○四年五月基于局部有效性的选择性决策树集成俞扬（001221154）（南京大学计算机科学与技术系，南京210093）摘要：集成学习通过为同一个问题训练出多个个体学习器并将结论进行合成，可以显著地提高学习系统的泛化能力。最近，一些研究者提出了选择性集成，即从训练好的学习器中选择一部分进行集成，可能获得比用所有学习器进行集成更强的泛化能力。本文对此进行了研究，并通过在局部样本空间上选择学习器，提出了一种基于局部有效性的选择性集成算法Lovsen。该算法使用k近邻来确定个体学习器在局部样本空间的有效性，从而为待预测的样本选择合适的个体学习器进行集成。实验结果表明，Lovsen可以较为稳定地生成泛化能力较强的决策树集成。关键词：机器学习;集成学习;选择性集成;决策树;惰性学习;k近邻LocalValidityBasedSelectiveEnsembleofDecisionTreesYUYang(001221154)(DepartmentofComputerScienceandTechnology,NanjingUniversity,Nanjing210093,China)Abstract:Ensemblelearningcansignificantlyimprovethegeneralizationabilityoflearningsystemsthroughtrainingafinitenumberofneuralnetworksandthencombingtheirresults.Recently,anewensemblelearningapproachnamedselectiveensemblehasbeenproposed,whichcanfurtherimprovelearningsystem’sperformancethroughensemblingmanyinsteadofallthebaselearnersathand.Inthispaper,theproblemofselectiveensemblehasbeeninvestigated.Throughensemblingbaselearnersfromlocalinstancespace,anovellocalvaliditybasedselectiveensembleapproachnameLovsenhasbeenproposed.Lovsenemploysk-nearestneighboralgorithmtodeterminethelocalvalidityofbaselearnersandthenensemblesappropriatebaselearnersforunseeninstances.ExperimentsshowthatLovsencanstablygenerateensembleofdecisiontreeswithbettergeneralizationability.Keywords:MachineLearning,EnsembleLearning,SelectiveEnsemble,DecisionTree,LazyLearning,k-NearestNeighbor-1-1、引言机器学习（MachineLearning）[26]是对计算机如何通过经验的积累，从而自动提高系统性能的机制的研究。机器学习涉及人工智能、概率统计、计算复杂性理论、哲学、心理学、遗传学、神经生物学等。随着该领域的发展，机器学习在最近20年的应用更加成熟而广泛，其成功应用的领域包括生物信息学、计算机辅助医疗诊断、计算金融学、行星地质学、网络安全等。在各种实验科学研究的共同的研究方法的每一步骤：观察、假设、验证、结论，机器学习都能够成为有利的助手[27]。机器学习的核心问题是如何在计算机上进行有效的学习。根据标记（label）给定的不同形式，目前大致有四种机器学习框架：y监督学习（SupervisedLearning）：给定一系列训练样本（trainingsamples/instances），其中每个样本都做上了标记，比如说标记出这个样本来自对一个苹果外观的一次观测。学习的目的是从这些带有标记的样本中学习到一些概念，比如说什么样的数据对应苹果而不是香蕉，并且在未来给出新的样本时，能够正确预测新样本的标记。y非监督学习（UnsupervisedLearning）：给定一系列没有任何标记的训练样本，学习的目的是发现隐藏在这些样本中的某种结构，例如样本的聚集情况。y强化学习（ReinforcementLearning）：从训练样本集中学习出状态到行为的映射，这些样本没有直接给出标记，而是给出了在一系列行为发生后导致的奖赏（rewards），也可视为滞后了的标记。y多示例学习（Multi-InstanceLearning）：训练样本被组织成包（bag），训练样本集包含一系列的包，每个包中又包含一组样本。包被标记为正包（positive）和反包（negative），而包中的样本却没有标记。本文的讨论仅限于监督学习。1988年，Kearns和Valiant[21]提出了弱学习器与强学习器的等价问题。如果一个多项式级学习算法能够产生高精度的学习器，则这个学习器称为强学习器，而如果产生的学习器只是略好于随机猜测，那么这个学习器就是弱学习器。要设计出强学习器是一件相当有挑战性的工作，然而如果存在简单的方法能够将弱学习器提升为强学习器，就可以以较少的代价获得很高的精度。Schapire[31]通过设计出一个集成学习算法（即后来著名的Boosting算法），构造性地对上述猜想进行了证明。1990年Hansen和Salamon[19]提出了神经网络集成（neuralnetworkensemble），一般认为这是神经网络集成的起源，而集成学习作为神经网络集成的超集，其起源必然在此之前。从今天来看，在正式使用“集成学习”（Ensemblelearning）这个名字之前，实际上已经有很多集成学习方面的研究工作，但其起源已经很难考证。简单地说，集成学习是为同一个问题训练一组学习器，并将这些学习器联合起来执行预测任务。按照个体学习器的生成方式，目前的集成学习方法大致可以分为个体学习器可以并行训练的方法，以及个体学习器只能串行训练的方法。研究表明，集成学习是目前泛化能力-2-最强的机器学习技术之一。以往的集成学习方法，如Bagging[2]，AdaBoost[14]，是将所训练的所有学习器都进行集成。而最近的研究发现[39]，从所训练的学习器中选择一部分进行集成预测，能够得到更好的泛化能力。这种思想称为选择性集成（SelectiveEnsemble）。本文对选择性集成进行了研究，提出对待预测样本所属的局部空间进行分析，仅利用在这个局部空间上有效的个体学习器进行集成，从而提出了Lovsen（LOcalValiditybasedSelectiveENsemble）算法。具体而言，在训练阶段，产生一批学习器后，LOVSEN利用k近邻来估计出每个学习器最“擅长”的区域，当给出一个测试样本时，选择在其邻域中的最佳学习器构成集成。本文后续部分组织如下：第二节回顾集成学习算法。在此基础上，第三节展示了新的集成学习算法Lovsen，试验对比结果在第四节中展现。第五节总结全文。2、集成学习对于传统的监督学习问题，给出属性集（attribute/featureset）12{,,}nAAAA=K和一个分布P，在A构成的空间上按照分布P抽取N个样本，构成一个训练样本集11{(,),(,)}tNNSyy=xxK。其中成对的(,)iiyx中，ix称为一个样本，iy是ix的标记，它由一个未知的函数()iiyf=x决定。ix是一个向量T,1,2,[,,]iiinxxxK，它的每一个分量是在属性集A对应分量上的取值。对于分类（classification）问题，iy属于一个离散数值集合{1,2,…,C}，集合中的每一个元素代表一个类别；对于回归（regression）问题，iy是一个实数。学习算法的输出是一个学习器（分类器或者回归器），这个学习器就是对未知函数f的估计，记作ˆf。当给出新样本x时，学习器将给出这个样本的预测值ˆˆ()yf=x（类别或实数）。这里，新样本是指独立于训练样本集tS，且符合分布P的样本。在实际问题中，由于训练样本数量有限、存在噪音以及学习算法本身的限制等多方面原因，ˆf与f之间往往会存在一定的误差。集成学习的方法首先在训练集上训练出m个学习器T1ˆˆ[,,]mffK，当给出新样本时，让每一个学习器都进行预测，产生结果T1ˆˆ[,,]myyK。然后通过某种方法，例如相对多数投票（majorityvoting），产生集成的预测结果ˆy。考虑一种简单情况，把每一个学习器看作随机变量T1[,,]mXXK，使用平均值作为集成的结果ˆ()/iyXxm=∑。当满足两个条件：a)iX的精度0.5，即比随机猜测要好；b)对于任意ij≠，iX独立于jX，这时ˆy与y的误差达到最小。这时，若令m趋向于无穷大，就可以得到ˆyy=。虽然在实际上无法满足第二个条件，即学习器之间相互独立，但是这个结论直观地阐述了集成要取得更强泛化能力的条件：每个学习器要有一定的精度，并且学习器之间存在一定的差异[19]。Krogh和Vedelsby[23]以回归学习器的集成推导出重要的集成学习的泛化误差公式，这个公式对于分类器的集成有着同样的意义。对于n个学习器，它们的集成的误差由(1)所示。-3-EEA=−(1)其中，E为n个学习器的绝对误差的加权平均，A为n个学习器相对于集成的误差的加权平均。E指示出学习器固有的误差，A指示出这些学习器之间的差异。这个式子表明了要获得好的集成就需要降低个体学习器的误差并增加学习器间的差异。2.1差异产生策略目前研究者们已经提出了许多集成学习算法，这些算法往往利用不同的策略来获得学习器之间的差异。下面根据Dietterich[8]对差异产生机制的分类进行介绍。2.1.1对训练样本集的扰动使用这一策略的方法从原来的训练样本集中产生多个新的训练样本集，在每个新的训练样本集上都训练出一个学习器，最后再将这些学习器聚集起来形成集成。研究者们发现，一些学习算法对训练样本的变动很敏感，例如决策树、神经网络、规则学习，训练集的微小变化会导致学习器较大的变化，这种学习算法称为不稳定的学习算法。而对另外一些算法来说，训练集的微小变化不会对学习结果有大的影响，例如k近邻、线性回归，这种算法称为稳定的学习算法。基于样本集扰动形成的集成，对不稳定的学习算法有好的效果，而对稳定的算法则没有明显作用。这一类集成算法中最为著名的有Bagging和Boosting。Table1.a)TheBaggingalgorithm.b)TheAdaBoostalgorithm.Input:trainingsetS,learningalgorithmL,iterationsIOutput:ensembleleanerLEInput:trainingsetSofsizem,learningalgorithmL,iterationsIOutput:ensembleleanerLEProcess:[1]fori=1toI[2]Si=bootstrapsamplefromS[3]Li=trainaleaneronSiviaL[4]endfor[5]:()argmax1iEyYiLxyL∈==∑Process:[1]fori=1toI[2]normalizetheweightssothatthetotalweightism[3]Si=samplefromSaccordingtoweightdistribution[4]Li=trainaleaneronSiviaL[5]:()1weight()i