【Python机器学习】利用AdaBoost元算法提高分类性能——基于单层决策树构建弱分类器

单层决策树（也称决策树桩）是一种简单的决策树。它基于单个特征来做决策，由于这棵树只有一次分裂过程，因此它实际上就是一个树桩。

在构造AdaBoost代码时，首先通过一个简单数据集来确保在算法上一切就绪：

from numpy import *

def loadSimpData():
    datMat=matrix([[1.0,2.1],
                   [2.0,1.1],
                   [1.3,1.0],
                   [1.0,1.0],
                   [2.0,1.0]])
    classLabels=[1.0,1.0,-1.0,-1.0,1.0]
    return datMat,classLabels

下图为数据集的示意图：

如果要试着从某个坐标轴上选择一个值（即选择一条与坐标轴平行的直线）来将所有的圆点与方形点分开，显然是不可能的。这就是单层决策树难以处理的一个著名问题。通过多颗单层决策树，就可以构建出一个能够对该数据集完全正确分类的分类器。

构建单层决策树的伪代码：

将最小错误率minError设为正无穷

对数据集中的每一个特征（第一层循环）：

    对每个步长（第二层循环）：

        对每个不等号（第三层循环）：

            建立一棵单层决策树并利用加权数据集对它进行测试

            如果错误率低于minError，则将当前单层决策树设为最佳单层决策树

返回最佳单层决策树

接下来为实际代码：

#通过阈值对比对数据进行分类
#所有在阈值一边的数据会分到类别-1，另一边的数据分到类别+1
#可以通过数组过滤来实现，首先将返回数组的全部元素设置为1，然后将所有不满足不等式要求的元素设置为-1
def stumpClassify(dataMatrix,dimen,threshVal,threshIneq):
    retArray=ones((shape(dataMatrix)[0,1]))
    if threshIneq=='lt':
        retArray[dataMatrix[:,dimen] <= threshVal] = -1.0
    else:
        retArray[dataMatrix[:, dimen] > threshVal] = -1.0
    return retArray

#遍历stumpClassify()函数所有的可能输入值，并找到数据集上最佳的单层决策树
#这里的“最佳”是基于数据的权重向量D来定义的。
def builsStump(dataArr,classLabels,D):
    dataMatrix=mat(dataArr)
    labelMat=mat(classLabels).T
    m,n=shape(dataMatrix)
    numSteps=10.0
    bestStump={}
    bestClassEst=mat(zeros((m,1)))
    minError=inf
    for i in range(n):
        rangeMin=dataMatrix[:,i].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)))
                errArr[predictedVals==labelMat]=0
                #计算加权错误率
                weightedError=D.T*errArr
                if weightedError<minError:
                    minError=weightedError
                    bestClassEst=predictedVals.copy()
                    bestStump['dim']=i
                    bestStump['thresh']=threshVal
                    bestStump['ineq']=inequal
    return bestStump,minError,bestClassEst

函数builsStump()将会遍历stumpClassify()函数所有的可能输入值，并找到数据集上最佳的单层决策树。这里的“最佳”是基于数据的权重向量D来定义的。在确保输入数据符合矩阵格式之后，整个函数开始执行。然后，函数将构建一个称为bestStump的空字典，用于存储给定权重向量D时所得到的最佳单层决策树的相关信息。遍历numSteps用于在特征的所有可能值上进行遍历。而变量minError则在一开始就初始化为正无穷大，之后用于寻找可能的最小错误率。

三层嵌套的for循环是程序的最主要部分。第一层for循环在数据集的所有特征上遍历。考虑到数值型的特征，我们就可以通过计算最小值和最大值来了解应该需要多大的步长。第二次for循环再在这些值上进行遍历。甚至将阈值设置为整个取值范围之外也是可以的。因此，在取值范围之外还应该有两个额外的步骤。最后一个for循环则是在大于和小于之间切换不等式。

在嵌套的三层for循环之内，我们在数据集及三个循环变量上调用stumpClassify()函数。基于这些循环变量，该函数将会返回分类预测结果。接下来构建一个列向量errArr，如果predictedVals中的值不等于labelMat中的真正类别标签值，那么errArr的相应位置为1。将错误向量errArr和权重向量D的相应元素相乘并求和，就得到了数值weightedError。这就是AdaBoost和分类器交互的地方。这里，我们是基于权重向量D而不是其他错误计算指标来评价分类器的。如果需要使用其他分类器的话，就需要考虑D上最佳分类器所定义的计算过程。

程序接下来输出所有值。最后，将当前的凑无虑与已有的最小错误率进行对比，如果当前的值较小，那么就在词典bestStump中保存该单层决策树。字典、错误率和类别估计值都会返回给AdaBoost算法。

实际运行：

dataMat,classLabels=loadSimpData()
D=mat(ones((5,1))/5)
print(builsStump(dataMat,classLabels,D))

上述单层决策树的生成函数是决策树的一个简化版本，它就是所谓的弱学习器，即弱分类算法。