机器学习算法总结.docx

第六章提升算法6.1引言当做重要打算时，大家可能都会考虑吸取多个专家而不是一个人的意见。机器学习处理 问题时也是如此，这就是提升算法背后的思路，提升算法是对其它算法进行组合的一种方 式，接下来我们将对提升算法，以及提升算法中最流行的一个算法AdaBoost算法进行介 绍，并对提升树以及简洁的基于单层决策树的Adaboost算法进行争论。提升方法是一种常用的统计学习方法，应用广泛且有效，在分类问题上，它通过转变训 练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类性能。一个分类 器在训练数据上能够获得比其他分类器更好的拟合，但是在训练数据外的数据集上却不能很 好的拟合数据，这时就称为该分类器消失了过拟合(overfitting)o提升算法能够有效地防止 过拟合现象的发生。图1过拟合现象示意图提升算法是一种为了拟合自适应基函数模型(adaptive basis-function models, ABM) 的贪心算法，自适应基函数模型可表达为：M/") =% +之叼展(X)(6-1)m=其中，耙是一种分类算法或者回归算法，被称为弱分类器(weak learner)或者基分类 器(base learner)。也可以表达为如下形式：(6-2)M/(X) = Z&(X；4)m=提升算法的目的是对以下公式的优化：(6-3)Nmin "(七)/ /=1其中，L（yJ）称为损失函数（loss function）, /是ABM模型。不同的损失函数有着不同 的性质，对应不同的提升算法，如表1所示。将（2）式代入（3）式可得如下表达式：N （ M眄nZL y乩。（七；/）（6-4）4"，%上i I w=i7由于学习的是加法模型，假如能够从前向后，每一步只学习一个基分类器及其系数，那 么就可以简化优化的简单度，详细推导过程如下所示：N典n Z 乙（y，&。（七；/,）（ 6-5）"阳，%j=表1常见损失函数以及相应提升算法名称损失函数导数/*算法平方误 差1 9乙y -/(七)Eyx；L2Boosting肯定误 差应-/(七)|sgn(y /(%)mediany | xz)Gradient boosting指数损 失exp (一”%)exp (一”)1 %J%2-7iiAdaBoost对数损 失log(l + e-'")y一巧1 区21 一%LogitBoost/（X） = arg min Z L（ X，/（七；/）（6-6）7 /=1N（4，丫,）= Mg min Z L（», fm.x （七）+ 13Mxi; /）（ 6-7 ）人，/=1/（X）=加（X）+&0（X； %）（ 6-8）算法不进行回溯对参数进行修改，因此该算法称为前向分步算法。6.2 AdaBoost 算法AdaBoost （Adaptive boosting）算法，也称为自适应提升算法。训练数据中的每个样 本，并赐予其一个权重，这些权重构成向量Do 一开头，这些权重都初始化为相等值，首先 在训练数据上训练出一个弱分类器并计算该分类器的错误率，然后在同一数据集上再次训练 弱分类器。再次训练分类器的过程中，将会重新调整每个样本的权重，其中上一次分对的样 本权重会降低，而上一次分错的样本权重会提高。图2 AdaBoost算法示意图给定一个二类分类的训练数据集7 = （和）（），（加明），其中，每个样本点由实例 与标记组成，实例为“7内，标记y.T = T+l,力是实例空间，y是标记集合。损失函数 可以表达为：NNLM）= ZexpT （力1 （七）+）1 = Z 叫 exp（-为/（%）（ 6-9 ）i=i=l其中，以 £expf _（玉）,X e -1,4-1）,那么可以有如下推导:NN-e" Z W5 +T Z 叱即。工。（玉）+ "小叱即（6-10）%=。（外）用工。（再）/=!/=1其中，乩=Logj%，*工:产二？尸.（为）,勺称为分类误差率。那么可以得到第 2 叫，外m个分类器：力（x）*a（x）+»。（x）（6-11）计算第m+1个分类器的参数可以通过下式得到：W =147 "一四"反助"（看）=卬,An（2/（.%，%（片）-1）=卬,24地（再）-4（6-2）ijn+ i,mi,mi,m、- i j /总结起来Adaboost算法主要有以下7步。1 w>=Yn2 for m = :M6o3 Fit a classifier （x）to the training set using weights w4 Compute errm =Z7 w;1 c rrCompute % =iog=24） errm5 Set 吗< e m rt i）6 Return /O) = sgnZ二%4(x)算法结束条件是训练错误率为0或者弱分类器数目到达用户指定的值。在详细应用 AdaBoost算法时，可以将其总结为以下的一般流程：收集数据：可以使用任意方法；预备数据：依靠于所使用弱分类器的类型，这里k-近邻、决策树、朴实贝叶斯、规律 回归、支持向量机等任意分类算法都可以作为本局部弱分类器；(3)分析数据：可使用任意方法；(4)训练算法：AdaBoost算法大局部时间都用在训练上，分类器将屡次在同一数据集上训 练弱分类器；测试算法：计算分类错误率；使用算法：同支持向量机类似，AdaBoost算法猜想两个类别中的一个，假如想应用多 分类，需要做与支持向量机类似的相应修改。6.3 提升树分类与回归树(Classification and regression trees, CART)又称为决策树(decision tree),使用分类数与回归树作为基本分类器的提升方法，称为提升树(Boosting tree)o%(6-13)(6-14)图3决策树木意图决策树模型将空间分为数个互不相交的区域=，每一个区域作为树的叶子节点，并为每个区域安排一个参数为：X G Rj n /(x) = /j因此决策树那么可以表达为如下形式：7(无。)=Z力/(1£0)六1其中， = 与,为：，该参数由最小化阅历风险计算得到:0 = arg min Z z（方力）（6-15）° j=i勺哂决策树模型是一种传统的学习方法，易于被理解，相比拟人工神经网络，我们能够清楚 地了解如何构建决策树，而且决策树模型无信息丧失。但是决策树模型也存在不稳定的缺 点，训练样本较小的变化会导致结果的较大差异。为解决这一问题，争论者主要通过提升算 法来对决策树模型进行优化，即所谓的提升树（Boosting tree）,其基本算法思路为，构建 多个决策树，多个决策树决策结果的加权平均对样本的变化不敏感。提升树模型是一系列的决策树的和：M九（九）7（%；"）（6-16）m=引入前向分步算法：八N= arg 噌n Z 乙（X，力-（x,） + 丁（七；"）（6-17）i=力I （尤）求得“= Rjm，/曾，R加求Yjm'方向=arg min Z K，力-（匕）+ /）（6-18）6.4 基于单层决策树的AdaBoost算法单层决策树(decision stump,也称决策树桩)是一种简洁的决策树，仅基于单个特征 来做决策，由于这棵树只有一次分裂过程，因此它实际上就是一个树桩。采用Python对单 层决策树进行实现，代码如下：def stumpClassify(dataMatrix,dimen,threshVal,threshlneq):retArray = ones(shape(dataMatrix)0,1)if threshlneq = If:retArraydataMatrix:,dimen <= threshVal = -1.0else:retArraydataMatrix:,dimen > threshVal = -1.0return retArraydef buildStump(dataArr,classLabels,D):dataMatrix = mat(dataArr); labelMat = mat(classLabels).Tm,n = shape(dataMatrix)numSteps = 10.0; bestStump = ; bestClasEst = mat(zeros(m,1)minError = inffor i in range(n):rangeMin = dataMatrix:,i.min(); rangeMax = dataMatrix:,i.max();stepSize = (rangeMax-rangeMin)/numStepsfor j in range(-1 ,int(numSteps)+1):for inequal in If, t,:threshVal = (rangeMin + float(j) * stepSize)predictedVals = stumpClassify(dataMatrix,i,threshVal,inequal)errArr = mat(ones(m,1)errArrpredictedVals = labelMat = 0weightedError = D.T*errArrif weightedError < minError:minError = weightedErrorbestClasEst = predictedVals.copy()bestStumpCdim1 = ibestStumppthresh1 = threshValbestStumpflneq1 = inequalreturn bestStump,minError,bestClasEst上述程序包含两个函数。第一个函数stumpClassfy()是通过阈值比拟对数据进行分类 的，全部的阈值一边的数据会分到类别-1,而在另一边的数据分到类别+1.该函数可以通过 数组过滤来实现，首先将返回数组的全部元素设置为1,然后将全部不满意不等式要求的元 素设置为-1,可以赐予数据集中的任意元素进行比拟，同时也可以将不等号在大于、小于之 间切换。其次个函数buildStump。将会遍历stumpCIassfy。函数全部可能的输入，并找到数据集 上最正确的单层决策树。在确保输入数据符合矩阵格式之后，整个函数就开头执行了，然后函 数将构建一个称为bestStump的空字典，这个字典用语存储给定权重向量D时所得到的最 佳单层决策树的相关信息。变量numSteps用于在特征的全部可能值上进行遍历。而变量 minError那么在一开头就初始化成正无穷大，之后用语查找可能的最小错误率。三层嵌套的for循环是程序最主要的局部。第一层for循环在数据集全部特征上遍历。考 虑到数值型的特征，我们就可以通过计算最小值和最大值来了解应当需要多大的不畅。然 后，其次层for循环再在这些值上遍历。甚至将阈值设置为整个取值范围之外也是可以的。 因此在取值范围之外还应当有两个额外的步骤，最终一个for循环那么是在大于和小于之间切 换不等式。上述单层决策树的生成函数是决策树的一个简化版本，即是所谓的弱学习器(弱分类 器)。到现在为止，我们已经建立了单层决策树，并生成了程序，做好了过渡到完整 AdaBoost算法，如下所示：def adaBoostTrainDS(dataArr,classLabels,numlt=40):weakClassArr =m = shape(dataArr)OD = mat(ones(m,1)/m) #init D to all equalaggClassEst = mat(zeros(m,1)for i in range(numlt):bestStump,error,classEst = buildStump(dataArr,classLabels,D)alpha = float(0.5*log(1.0-error)/max(error, 1 e-16)bestStumpPalpha1 = alphaweakClassArr.append(bestStump)expon = multiply(-1*alpha*mat(classLabels).T,classEst)D = multiply(D,exp(expon)D = D/D.sum()aggClassEst += alpha*classEstaggErrors = multiply(sign(aggClassEst) != mat(classLabels).T,ones(m,1)errorRate = aggErrors.sum()/mprint "total error:11,errorRateif errorRate = 0.0: breakreturn weakClassArr伪代码可以简洁总结为以下步骤：对每次迭代：采用buildStump。函数找到最正确的单层决策树将最正确单层决策树加入到单层决策树组计算alpha计算新的权重向量D更新累积类别估量值假如错误率等于0.0,那么退出循环该AdaBoost算法的输入参数包括数据集、类别标签以及迭代次数numlt,其中numl是 在整个AdaBoost算法中唯一需要用户指定的参数。AdaBoost算法的核心在于for循环，该 循环运行numlt次，或者知道训练错误率为0为止。循环中的第一件事就是采用前面介绍的 buildStump()函数建立一个单层决策树，同时返回的还有最小的错误率以及估量的类别向 量。然后那么需要计算的那么是alpha值，该值会告知总分类器本次单层决策树输出结果的权 重，其中的语句max(error, 1e-16)用语确保在没有错误时，不会发生除零溢出，而后， alpha值加入到bestStump字典中，该字典又添加到列表中。该字典包含分类所需要的全部 信息。接下来那么是计算下一次迭代中的新权重向量D,在训练错误率为0时那么提前结束for 循环。图4那么为我们所得到的一组弱分类器及其权重。'dim': 9, 'ineq': 'gc', 'thresh': 3.0, 'alpha': 1: 17, 'ineq': "gt'r 'thresh': 52.5r 'alpha': 0.f 'dim': 3, 'ine q': 'gt', 'thresh': : 'It'z 'thresh': 62.300000000000004, 'alpha': 0.23297004638939772, 'd im': 10, 'ineq': '1七'thresh': r 'dim': 5, 'ineq': 'gt', 'thresh': 2.0, 'alpha': 0.z 'dim': 12, 'ineq': 'It'r 'thresh*: 'dim': 1, 'ineq': 'g七'thr esh': 1.2,5, 'ineq': '1七','thresh': 0.0 ,'alpha': 'dim': 4, 'ineq': 'It', 'thresh': 28.7999999999 99997, 'alpha': 图4弱分类器如图5所示，为不同弱分类器数，所得的分类结果，可以看到，弱分类器越多，在训练 集上分类错误率越低，分类效果越好，但是并不是弱分类器越多，对测试数据的分类效果越 好。weaklearnererrorrate:0.284280936455weaklearnererrorrate:0.284280936455weaklearnererrorrace:0.247491638796weaklearnererrorrate:0.247491638796weaklearnererrorrate:0.254180602007weaklearnererrorrace:weaklearnererrorrate:weaklearnererrorrace:weakweak learner error weak learner errorrate: rate:weak learner error rate:weak learnererror rate:weak learner error rate: weak learner error race:weak learner error rate: weak learner error rate:train error: 57.0train number: 299test error: 15.0test number: 67test error rate:0.223880597015train error: 47.0test error: 17.0test ntimber:67test error rate: 0.253731343284100个分类器500个分类器weak learner errorrate:0.284280936455weak learner errorrate:0.284280936455weak learner errorrate:0.284280936455weak learner errorrate:0.284280936455weak learner errorrace:0.247491638796weak learner errorrate:0.247491638796weak learner errorrate:0.247491638796weak learner errorrate:0.247491638796weak learner errorrace:0.254180602007weak learner errorrace:0.254180602007weak learner error weak learner errorrate:rate:0.2408026755850.240802675585weak learner errorrate:0.220735785953weak learner errorrace:0.1872909699weak learner errorrace:0.247491638796weak learner errorrate:weak learner error tram error: 69.0 train number: 299rate:0.230769230769weak learner error cram error: 56.0 tram nxircber:299rate:0.1872909699train error race: test error: 16.0 test nurcber:670.230769230769traxn error rate: test error: 14.0 test nuinber:670.1872909699test error rate:0.238805970149test error rate:0.20895522388110个分类器50个分类器图5不同数量弱分类器分类结果6.5小结提升方法通过组合多个弱分类器的分类结果，获得了比简洁的单分类器更好的分类结 果。目前还存在采用不同分类器的集成方法，但是本章仅介绍了采用同一分类器的集成方 法。多个分类器组合可能会进一步凸显单分类器的缺乏，比方过拟合问题。假如分类器之间 差异显著，那么多个分类器组合就可能会缓解这一问题。分类器之间的差异可以使算法本身 或者是应用于算法上的数据的不同。