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

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

2、类器出现了过拟合（overfitting）。提升算法能够有效地防止过拟合现象的发生。图1 过拟合现象示意图提升算法是一种为了拟合自适应基函数模型（adaptive basis-function models, ABM）的贪心算法，自适应基函数模型可表达为： （6-1）其中，是一种分类算法或者回归算法，被称为弱分类器（weak learner）或者基分类器（base learner）。也可以表达为如下形式： （6-2）提升算法的目的是对以下公式的优化： （6-3）其中，称为损失函数（loss function），是ABM模型。不同的损失函数有着不同的性质，对应不同的提升算法，如表1所示。将(2)

3、式代入(3)式可得如下表达式： （6-4）因为学习的是加法模型，如果能够从前向后，每一步只学习一个基分类器及其系数，那么就可以简化优化的复杂度，具体推导过程如下所示： （6-5）表1 常见损失函数以及相应提升算法名称损失函数导数算法平方误差L2Boosting绝对误差Gradient boosting指数损失AdaBoost对数损失LogitBoost （6-6） （6-7） （6-8）算法不进行回溯对参数进行修改，因此该算法称为前向分步算法。6.2 AdaBoost算法AdaBoost（Adaptive boosting）算法，也称为自适应提升算法。训练数据中的每个样本，并赋予其一个权重，这

4、些权重构成向量D。一开始，这些权重都初始化为相等值，首先在训练数据上训练出一个弱分类器并计算该分类器的错误率，然后在同一数据集上再次训练弱分类器。再次训练分类器的过程中，将会重新调整每个样本的权重，其中上一次分对的样本权重会降低，而上一次分错的样本权重会提高。图2 AdaBoost算法示意图给定一个二类分类的训练数据集，其中，每个样本点由实例与标记组成，实例，标记，是实例空间，是标记集合。损失函数可以表达为： （6-9）其中，则可以有如下推导： （6-10）其中，称为分类误差率。则可以得到第m个分类器： （6-11）计算第m+1个分类器的参数可以通过下式得到： （6-12）总结起来Adaboo

5、st算法主要有以下7步。1 2 for do3 Fit a classifier to the training set using weights w4 Compute 5 Compute 6 Set 7 Return 算法结束条件是训练错误率为0或者弱分类器数目达到用户指定的值。在具体应用AdaBoost算法时，可以将其总结为以下的一般流程：(1) 收集数据：可以使用任意方法；(2) 准备数据：依赖于所使用弱分类器的类型，这里k-近邻、决策树、朴素贝叶斯、逻辑回归、支持向量机等任意分类算法都可以作为本部分弱分类器；(3) 分析数据：可使用任意方法；(4) 训练算法：AdaBoost算法大部

6、分时间都用在训练上，分类器将多次在同一数据集上训练弱分类器；(5) 测试算法：计算分类错误率；(6) 使用算法：同支持向量机类似，AdaBoost算法预测两个类别中的一个，如果想应用多分类，需要做与支持向量机类似的相应修改。6.3 提升树分类与回归树（Classification and regression trees, CART）又称为决策树（decision tree），使用分类数与回归树作为基本分类器的提升方法，称为提升树（Boosting tree）。图3 决策树示意图决策树模型将空间分为数个互不相交的区域，每一个区域作为树的叶子节点，并为每个区域分配一个参数： （6-13）因此决策

7、树则可以表达为如下形式： （6-14）其中，该参数由最小化经验风险计算得到： （6-15）决策树模型是一种传统的学习方法，易于被理解，相比较人工神经网络，我们能够清晰地了解如何构建决策树，而且决策树模型无信息丢失。但是决策树模型也存在不稳定的缺点，训练样本较小的变化会导致结果的较大差异。为解决这一问题，研究者主要通过提升算法来对决策树模型进行优化，即所谓的提升树（Boosting tree），其基本算法思路为，构建多个决策树，多个决策树决策结果的加权平均对样本的变化不敏感。提升树模型是一系列的决策树的和： （6-16）引入前向分步算法： （6-17）已知求得，已知求： （6-18）6.4 基于

8、单层决策树的AdaBoost算法单层决策树（decision stump，也称决策树桩）是一种简单的决策树，仅基于单个特征来做决策，由于这棵树只有一次分裂过程，因此它实际上就是一个树桩。利用Python对单层决策树进行实现，代码如下：def stumpClassify(dataMatrix,dimen,threshVal,threshIneq): retArray = ones(shape(dataMatrix)0,1) if threshIneq = 'lt': retArraydataMatrix:,dimen <= threshVal = -1.0 else: re

9、tArraydataMatrix:,dimen > threshVal = -1.0 return retArraydef buildStump(dataArr,classLabels,D): dataMatrix = mat(dataArr); labelMat = mat(classLabels).T m,n = shape(dataMatrix) numSteps = 10.0; bestStump = ; bestClasEst = mat(zeros(m,1) minError = inf for i in range(n): rangeMin = dataMatrix:,i.

10、min(); rangeMax = dataMatrix:,i.max(); stepSize = (rangeMax-rangeMin)/numSteps for j in range(-1,int(numSteps)+1): for inequal in 'lt', 'gt': threshVal = (rangeMin + float(j) * stepSize) predictedVals = stumpClassify(dataMatrix,i,threshVal,inequal) errArr = mat(ones(m,1) errArrpredic

11、tedVals = labelMat = 0 weightedError = D.T*errArr if weightedError < minError: minError = weightedError bestClasEst = predictedVals.copy() bestStump'dim' = i bestStump'thresh' = threshVal bestStump'ineq' = inequal return bestStump,minError,bestClasEst上述程序包含两个函数。第一个函数stumpC

12、lassfy()是通过阈值比较对数据进行分类的，所有的阈值一边的数据会分到类别-1，而在另一边的数据分到类别+1.该函数可以通过数组过滤来实现，首先将返回数组的全部元素设置为1，然后将所有不满足不等式要求的元素设置为-1，可以给予数据集中的任意元素进行比较，同时也可以将不等号在大于、小于之间切换。第二个函数buildStump()将会遍历stumpClassfy()函数所有可能的输入，并找到数据集上最佳的单层决策树。在确保输入数据符合矩阵格式之后，整个函数就开始执行了，然后函数将构建一个称为bestStump的空字典，这个字典用语存储给定权重向量D时所得到的最佳单层决策树的相关信息。变量num

13、Steps用于在特征的所有可能值上进行遍历。而变量minError则在一开始就初始化成正无穷大，之后用语寻找可能的最小错误率。三层嵌套的for循环是程序最主要的部分。第一层for循环在数据集所有特征上遍历。考虑到数值型的特征，我们就可以通过计算最小值和最大值来了解应该需要多大的不畅。然后，第二层for循环再在这些值上遍历。甚至将阈值设置为整个取值范围之外也是可以的。因此在取值范围之外还应该有两个额外的步骤，最后一个for循环则是在大于和小于之间切换不等式。上述单层决策树的生成函数是决策树的一个简化版本，即是所谓的弱学习器（弱分类器）。到现在为止，我们已经建立了单层决策树，并生成了程序，做好了过

14、渡到完整AdaBoost算法，如下所示：def adaBoostTrainDS(dataArr,classLabels,numIt=40): weakClassArr = m = shape(dataArr)0 D = mat(ones(m,1)/m) #init D to all equal aggClassEst = mat(zeros(m,1) for i in range(numIt): bestStump,error,classEst = buildStump(dataArr,classLabels,D) alpha = float(0.5*log(1.0-error)/max(er

15、ror,1e-16) bestStump'alpha' = alpha weakClassArr.append(bestStump) expon = multiply(-1*alpha*mat(classLabels).T,classEst) D = multiply(D,exp(expon) D = D/D.sum() aggClassEst += alpha*classEst aggErrors = multiply(sign(aggClassEst) != mat(classLabels).T,ones(m,1) errorRate = aggErrors.sum()/m

16、 print "total error:",errorRate if errorRate = 0.0: break return weakClassArr伪代码可以简单总结为以下步骤：对每次迭代：利用buildStump( )函数找到最佳的单层决策树将最佳单层决策树加入到单层决策树组计算alpha计算新的权重向量D更新累积类别估计值如果错误率等于0.0，则退出循环该AdaBoost算法的输入参数包括数据集、类别标签以及迭代次数numIt，其中numI是在整个AdaBoost算法中唯一需要用户指定的参数。AdaBoost算法的核心在于for循环，该循环运行numIt次，或者知道训练错误率为0为止。循环中的第一件事就是利用前面介绍的buildStump()函数建立一个单层决策树，同时返回的还有最小的错误率以及估计的类别向量。然后则需要计算的则是alpha值，该值会告诉总分类器本次单层决策树输出结果的权重，其中的语句max(error, 1e-16)用语确保在没有错误时，不会发生除零溢出，而后，alpha值加入到bestStump字典中，该字典又添加到列表中。该字典包含分类所需要的所有信息。接下来则是计算下一次迭代中的新权重向量D，在训练错误率为0时则提前结束for循环。图4则为我们所得到的一组弱分类器及其权重。图4 弱分类器如图5所示，