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

第六章提升算法6.1引言当做重要决定时，大家可能都会考虑吸取多个专家而不是一个人的意见。机器学习处理问题时也是如此，这就是提升算法背后的思路，提升算法是对其它算法进行组合的一种方式，接下来我们将对提升算法，以及提升算法中最流行的一个算法AdaBoost算法进行介绍，并对提升树以及简单的基于单层决策树的Adaboost算法进行讨论。提升方法是一种常用的统计学习方法，应用广泛且有效，在分类问题上，它通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类性能。一个分类器在训练数据上能够获得比其他分类器更好的拟合，但是在训练数据外的数据集上却不能很好的拟合数据，这时就称为该分类器出现了过拟合（overfitting）。提升算法能够有效地防止过拟合现象的发生。图1过拟合现象示意图提升算法是一种为了拟合自适应基函数模型（adaptivebasis-functionmodels,ABM）的贪心算法，自适应基函数模型可表达为：01MmmmfXwwX（6-1）其中，m是一种分类算法或者回归算法，被称为弱分类器（weaklearner）或者基分类器（baselearner）。也可以表达为如下形式：1()(;)MmmmfXbX（6-2）提升算法的目的是对以下公式的优化：1min(,())NiifiLyfx（6-3）其中，ˆ(,)Lyy称为损失函数（lossfunction），f是ABM模型。不同的损失函数有着不同的性质，对应不同的提升算法，如表1所示。将(2)式代入(3)式可得如下表达式：,11min,(;)mmNMimimimLyx（6-4）因为学习的是加法模型，如果能够从前向后，每一步只学习一个基分类器及其系数，那么就可以简化优化的复杂度，具体推导过程如下所示：,1min,(;)mmNimimiLyx（6-5）表1常见损失函数以及相应提升算法名称损失函数导数*f算法平方误差21(())2iiyfx()iiyfx|iyxL2Boosting绝对误差()iiyfxsgn(())iiyfx(|)imedianyxGradientboosting指数损失exp()iiyfxexp()iiiyyfx1log21iiAdaBoost对数损失log1iiyfeiiy1log21iiLogitBoost01()argmin(,(;))NiiifXLyfx（6-6）1,1(,)argmin(,()(;))NmmimiiiLyfxx（6-7）1()()(;)mmmmfXfXX（6-8）算法不进行回溯对参数进行修改，因此该算法称为前向分步算法。6.2AdaBoost算法AdaBoost（Adaptiveboosting）算法，也称为自适应提升算法。训练数据中的每个样本，并赋予其一个权重，这些权重构成向量D。一开始，这些权重都初始化为相等值，首先在训练数据上训练出一个弱分类器并计算该分类器的错误率，然后在同一数据集上再次训练弱分类器。再次训练分类器的过程中，将会重新调整每个样本的权重，其中上一次分对的样本权重会降低，而上一次分错的样本权重会提高。图2AdaBoost算法示意图给定一个二类分类的训练数据集1122{(,),(,),,(,)}NNTxyxyxy，其中，每个样本点由实例与标记组成，实例nixR，标记{1,1}iyY，是实例空间，Y是标记集合。损失函数可以表达为：1,11()exp[(()())]exp(())NNmimiiimiiiiLyfxxwyx（6-9）其中，,1exp(())imimiwyfx，1,1iy，则可以有如下推导：,,,,()()11()(())iiiiNNmimimimiiimyxyxiiLeweweewIyxew（6-10）其中，11log2mmmerrerr，,1,1(())NimimiimNimiwIyxerrw，merr称为分类误差率。则可以得到第m个分类器：1()()()mmmfXfXX（6-11）计算第m+1个分类器的参数可以通过下式得到：()(2(())1)2(()),1,,,mimimimimimimyxIyxIyximimimimwwewewee（6-12）总结起来Adaboost算法主要有以下7步。11iwN2for1:mMdo3Fitaclassifier()mXtothetrainingsetusingweightsw4Compute,11(())NimimiimNiiwIyxerrw5Compute1log(2)mmmmmerrerr6Set(())mimiIyxiiwwe7Return1()sgn()MmmmfxX算法结束条件是训练错误率为0或者弱分类器数目达到用户指定的值。在具体应用AdaBoost算法时，可以将其总结为以下的一般流程：(1)收集数据：可以使用任意方法；(2)准备数据：依赖于所使用弱分类器的类型，这里k-近邻、决策树、朴素贝叶斯、逻辑回归、支持向量机等任意分类算法都可以作为本部分弱分类器；(3)分析数据：可使用任意方法；(4)训练算法：AdaBoost算法大部分时间都用在训练上，分类器将多次在同一数据集上训练弱分类器；(5)测试算法：计算分类错误率；(6)使用算法：同支持向量机类似，AdaBoost算法预测两个类别中的一个，如果想应用多分类，需要做与支持向量机类似的相应修改。6.3提升树分类与回归树（Classificationandregressiontrees,CART）又称为决策树（decisiontree），使用分类数与回归树作为基本分类器的提升方法，称为提升树（Boostingtree）。图3决策树示意图决策树模型将空间分为数个互不相交的区域,1,,jRjJ，每一个区域作为树的叶子节点，并为每个区域分配一个参数j：()jjxRfx（6-13）因此决策树则可以表达为如下形式：1;JjjjTxIxR（6-14）其中，1{,}JjjR，该参数由最小化经验风险计算得到：1argmin(,)jjJjjjxRLy（6-15）决策树模型是一种传统的学习方法，易于被理解，相比较人工神经网络，我们能够清晰地了解如何构建决策树，而且决策树模型无信息丢失。但是决策树模型也存在不稳定的缺点，训练样本较小的变化会导致结果的较大差异。为解决这一问题，研究者主要通过提升算法来对决策树模型进行优化，即所谓的提升树（Boostingtree），其基本算法思路为，构建多个决策树，多个决策树决策结果的加权平均对样本的变化不敏感。提升树模型是一系列的决策树的和：1();MMmmfxTx（6-16）引入前向分步算法：11ˆargmin(,()(;))mNmimiimiLyfxTx（6-17）已知1()mfx求得1{,}mJmjmjmR，已知jmR求jm：1ˆargmin(,())jmijmjmimijmxRLyfx（6-18）6.4基于单层决策树的AdaBoost算法单层决策树（decisionstump，也称决策树桩）是一种简单的决策树，仅基于单个特征来做决策，由于这棵树只有一次分裂过程，因此它实际上就是一个树桩。利用Python对单层决策树进行实现，代码如下：defstumpClassify(dataMatrix,dimen,threshVal,threshIneq):retArray=ones((shape(dataMatrix)[0],1))ifthreshIneq=='lt':retArray[dataMatrix[:,dimen]=threshVal]=-1.0else:retArray[dataMatrix[:,dimen]threshVal]=-1.0returnretArraydefbuildStump(dataArr,classLabels,D):dataMatrix=mat(dataArr);labelMat=mat(classLabels).Tm,n=shape(dataMatrix)numSteps=10.0;bestStump={};bestClasEst=mat(zeros((m,1)))minError=infforiinrange(n):rangeMin=dataMatrix[:,i].min();rangeMax=dataMatrix[:,i].max();stepSize=(rangeMax-rangeMin)/numStepsforjinrange(-1,int(numSteps)+1):forinequalin['lt','gt']:threshVal=(rangeMin+float(j)*stepSize)predictedVals=stumpClassify(dataMatrix,i,threshVal,inequal)errArr=mat(ones((m,1)))errArr[predictedVals==labelMat]=0weightedError=D.T*errArrifweightedErrorminError:minError=weightedErrorbestClasEst=predictedVals.copy()bestStump['dim']=ibestStump['thresh']=threshValbestStump['ineq']=inequalreturnbestStump,minError,bestClasEst上述程序包含两个函数。第一个函数stumpClassfy()是通过阈值比较对数据进行分类的，所有的阈值一边的数据会分到类别-1，而在另一边的数据分到类别+1.该函数可以通过数组过滤来实现，首先将返回数组的全部元素设置为1，然后将所有不满足不等式要求的元素设置为-1，可以给予数据集中的任意元素进行比较，同时也可以将不等号在大于、小于之间切换。第二个函数buildStump()将会遍历stumpClassfy()函数所有可能的输入，并找到数据集上最佳的单层决策树。在确保输入数据符合矩阵格式之后，整个函数就开始执行了，然后函数将构建一个称为bestStump的空字典，这个字典用语存储给定权重向量D时所得到的最佳单层决策树的相关信息。变量numSteps用于在特征的所有可能值上进行遍历。而变量minError则在一开始就初始化成正无穷大，之后用语寻找可能的最小错误率。三层嵌套的for循环是程序最主要的部分。第一层for循环在数据集所有特征上遍历。考虑到数值型的特征，我们就可以通过计算最小值和最大值来了解应该需要多大的不畅。然后，第二层for循环再在这些值上遍历。甚至将阈值设置为整个取值范围之外也是可以的。因此在取值范围之外还应该有两个额外的步骤，最后一个for循环则是在大于和小于之间切换不等式。上述单层决策树的生成函数是决策树的一个简化版本，即是所谓的弱学习器（弱分类器）。到现在为止，我们已经建立了单层决策树，并生成了程序，做好了过渡到完整AdaBoost算法，如下所示：defadaBoostTrainDS(dataArr,classLabels,numIt=40):weakClassArr=[]m=shape(dataArr)[0]D=mat(ones((m,1))/m)#initDtoallequalaggClassEst=mat(zeros((m,1)))foriinrange(numIt):bestStump,error,classEst=buildStump(dataArr,cl