机器学习算法总结-决策树(含代码)

1、第六章提升算法6.1引言当做重要决定时，大家可能都会考虑吸取多个专家而不是一个人的意见。机器学习处理问题时也是如此，这就是提升算法背后的思路，提升算法是对其它算法进行组合的一种方式，接下来我们将对提升算法，以及提升算法中最流行的一个算法AdaBoost算法进行介绍，并对提升树以及简单的基于单层决策树的Adaboost算法进行讨论。提升方法是一种常用的统计学习方法，应用广泛且有效，在分类问题上，它通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类性能。一个分类器在训练数据上能够获得比其他分类器更好的拟合，但是在训练数据外的数据集上却不能很好的拟合数据，这时就称为该分类器

2、出现了过拟合(overfitting)提升算法能够有效地防止过拟合现象的发生。提升算法是一种为了拟合自适应基函数模型(adaptivebasis-functionmodels,ABM)的贪心算法，自适应基函数模型可表达为：f(X)=w+w(X)(6-1)0mmm=1其中，是一种分类算法或者回归算法，被称为弱分类器(weaklearner)或者基分类m器(baselearner)o也可以表达为如下形式：f(X)=第卩b(X;y)(6-2)mm提升算法的目的是对以下公式的优化：6-3)min*L(y,f(x)fi=i11其中，L(y，y)称为损失函数(lossfunction),f是ABM模型。不

3、同的损失函数有着不同的性质，对应不同的提升算法，如表1所示。6-4)将(2)式代入(3)式可得如下表达式：min乙I/WmJ询mim丿因为学习的是加法模型，如果能够从前向后，每一步只学习一个基分类器及其系数，那么就可以简化优化的复杂度，具体推导过程如下所示：6-5)min、L(y,卩Q(x;y)6丫imimmj=表1常见损失函数以及相应提升算法名称损失函数导数f*算法平差误；(y-f(x)b2iiy-f(x)iiL2Boosting绝对误差Gradient指数损失对数损失|y-f(x)|iiiii-()()_exp-yf(x/-yexp-yf(x)logiiiii21-兀iTkisgny-f(

4、x)mediary|x)boostingAdaBoostIog1+e-yifiIIy-兀iiLogitBoostf(X)=argminL(y,0yiii=1(卩,y)=argminL(y,f(x)+卩Q(x;y)mmim-1ii卩,yi=1f(X)=f(X)+卩0(X;y)mm-1mm算法不进行回溯对参数进行修改，因此该算法称为前向分步算法6.2AdaBoost算法6-6)6-7)6-8)AdaBoost(Adaptiveboosting)算法，也称为自适应提升算法。训练数据中的每个样本，并赋予其一个权重，这些权重构成向量D。一开始，这些权重都初始化为相等值，首先在训练数据上训练出一个弱分类器

5、并计算该分类器的错误率，然后在同一数据集上再次训练弱分类器。再次训练分类器的过程中，将会重新调整每个样本的权重，其中上一次分对的样本权重会降低，而上一次分错的样本权重会提高。分类器分类器10.87图2AdaBoost算法示意图给定一个二类分类的训练数据集T=（x,y）,（x,y）,Xy），其中，每个样本点由实例与标记组成，实例x二Rn，标记yG丫=l；1，；是实例空间，Y是标记集合。损失函数可以表达为：L=细exp-y(f(x)+卩Q(x)=细wexp-卩yQ(x)心Y*mim-1iii,mi=1i=1其中，wexp-yf(x)，yw1汁小则可以有如卞推导：i,mim-1iiL(妨=e邛工w+

6、邙工w=(环e_卩丿)mi,mi,myi“(xi)X神(x”工nwj(y冷(x)i_1i,mijmiNwi_1i,mi=1ywI(yhQ(x)+e卩wi,miii,mi_16-9)6-10)其中，t;m个分类器：1-errlogmerrmerrmerr称为分类误差率。m则可以得到第f（X）=f（X）+卩e（x）m介1m6-11)计算第m+1个分类器的参数可以通过下式得到：wi,m+1_we_py.e(x)_we(2I(y詡(x)-1)_we2卩I(y詢(x)e-卩mimimimimimimi,mi,mi,m总结起来Adaboost算法主要有以卞7步。(6-12)wi_1Nform_1:MdoF

7、itaclassifier凶tothetrainingsetusingweightswymnwI(yh(x)i_i,ymiNwi_1i1-err_logm(a_2卩)errmm4Computeerrm5Computem6SetmwJWQI(yh(x)iimimi7Returnf(x)=sgnT工Mae(X)Lm=1mm-算法结束条件是训练错误率为0或者弱分类器数目达到用户指定的值。在具体应用AdaBoost算法时，可以将其总结为以下的一般流程：(1)收集数据：可以使用任意方法；准备数据：依赖于所使用弱分类器的类型，这里k-近邻、决策树、朴素贝叶斯、逻辑回归、支持向量机等任意分类算法都可以作为本

8、部分弱分类器；分析数据：可使用任意方法；训练算法：AdaBoost算法大部分时间都用在训练上，分类器将多次在同一数据集上训练弱分类器；测试算法：计算分类错误率；使用算法：同支持向量机类似，AdaBoost算法预测两个类别中的一个，如果想应用多分类，需要做与支持向量机类似的相应修改。6.3提升树分类与回归树(Classificationandregressiontrees,CART)又称为决策树(decisiontree),使用分类数与回归树作为基本分类器的提升方法，称为提升树B6ostingtree)。图3决策树示意图决策树模型将空间分为数个互不相交的区域只=1,J，每一个区域作为树的叶子节点

9、，并为每个区域分配一个参数v:fjXeRnf(x)=y(6-13)因此决策树则可以表达为如下形式：T(x;0)=2vi(XeR)(6-14)=jj其中，0=R,vJ，该参数由最小化经验风险计算得到：jj16-15)0=argmin工L(y,y)0j=1X衆jj决策树模型是一种传统的学习方法，易于被理解，相比较人工神经网络，我们能够清晰地了解如何构建决策树，而且决策树模型无信息丢失。但是决策树模型也存在不稳定的缺点，训练样本较小的变化会导致结果的较大差异。为解决这一问题，研究者主要通过提升算法来对决策树模型进行优化，即所谓的提升树(Boostingtree),其基本算法思路为，构建多个决策树，多

10、个决策树决策结果的加权平均对样本的变化不敏感。提升树模型是一系列的决策树的和：Mm=16-16)6-17)6-18)f(x)=第T(x;0)引入前向分步算法：0=argminL(y,f(x)+T(x;0)m0mi=iim-1iimhm已知R求y:jm已知f(X)求得0=R,ym1mjmjm1jmy=argmin工L(y,f(x)+y)jmyjmxeRim-1ijm6.4基于单层决策树的AdaBoost算法单层决策树(decisionstump，也称决策树桩)是一种简单的决策树，仅基于单个特征来做决策，由于这棵树只有一次分裂过程，因此它实际上就是一个树桩。利用Python对单层决策树进行实现，代

11、码如下：defstumpClassify(dataMatrix,dimen,threshVal,threshIneq):retArray=ones(shape(dataMatrix)0,1)ifthreshIneq=lt:retArraydataMatrix:,dimenthreshVal=-1.0returnretArraydefbuildStump(dataArr,classLabels,D):dataMatrix=mat(dataArr);labelMat=mat(classLabels).Tm,n=shape(dataMatrix)numSteps=10.0;bestStump=;be

12、stClasEst=mat(zeros(m,1)minError=infforiinrange(n):rangeMin=dataMatrix:,i.min();rangeMax=dataMatrix:,i.max();stepSize=(rangeMax-rangeMin)/numStepsforjinrange(-1,int(numSteps)+1):forinequalinlt,gt:threshVal=(rangeMin+float(j)*stepSize)predictedVals=stumpClassify(dataMatrix,i,threshVal,inequal)errArr=

13、mat(ones(m,1)errArrpredictedVals=labelMat=0weightedError=D.T*errArrifweightedError-Vjlfcy9Mjfatri5筑Qxx-ain.nLuttsex:Z39tram,erloxrate：0.1572309699tCJt-ezsot:14o七estk*JT匕(T567化3匚errorlate:.Zv955223-55150个分类器wedklearnererrorraue:0eatclearnererTorrate:D.1ST15Q35452w&ak1电謹片21色才Ortit-S:;：0-.1571903545weak&xcrrac;0.15T1日0石3旨h亡耳轻|.亍f盯|3herrorrate:.l&713)fi3552weaklearnererrorrace20reak1电arnere*Tarrate:D.157190635452weaklearnereTorrate:D.151903542weakltarnererrorrate：0祐UM昴討恥trainerrGritrazrniurher:299e*aind护亢忙丄*-rat:0,157150勺客生吕2tescrrcr:17tQteat砧辽nhn；67c