单层决策树（decision stump，也称决策树桩）是一种简单的决策树。前面我们已经介绍了决策树的工作原理，接下来将构建一个单层决策树，而它仅基于单个特征来做决策。由于这棵树只有一次分裂过程，因此它实际上就是一个树桩。
在构造AdaBoost的代码时，我们将首先通过一个简单数据集来确保在算法实现上一切就绪。然后，建立一个叫adaboost.py的新文件并加入如下代码：
def loadSimpData:datMat = matrix([[ 1. , 2.1],[ 2. , 1.1],[ 1.3, 1. ],[ 1. , 1. ],[ 2. , 1. ]])classLabels = [1.0, 1.0, -1.0, -1.0, 1.0]return datMat,classLabels 图7-2给出了上述数据集的示意图。如果想要试着从某个坐标轴上选择一个值（即选择一条与坐标轴平行的直线）来将所有的圆形点和方形点分开，这显然是不可能的。这就是单层决策树难以处理的一个著名的问题。通过使用多棵单层决策树，我们就可以构建出一个能够对该数据集完全正确分类的分类器。
图7-2 用于检测AdaBoost构建函数的简单数据。这不可能仅仅通过在某个坐标轴上选择某个阈值来将圆形点和方形点分开。AdaBoost需要将多个单层决策树组合起来才能对该数据集进行正确分类
通过键入如下命令可以实现数据集和类标签的导入：
>>> import adaboost>>> datMat,classLabels=adaboost.loadSimpData 有了数据，接下来就可以通过构建多个函数来建立单层决策树。
第一个函数将用于测试是否有某个值小于或者大于我们正在测试的阈值。第二个函数则更加复杂一些，它会在一个加权数据集中循环，并找到具有最低错误率的单层决策树。
这个程序的伪代码看起来大致如下：
将最小错误率minError设为+∞ 对数据集中的每一个特征（第一层循环）： 对每个步长（第二层循环）： 对每个不等号（第三层循环）： 建立一棵单层决策树并利用加权数据集对它进行测试 如果错误率低于minError，则将当前单层决策树设为最佳单层决策树 返回最佳单层决策树
接下来，我们开始构建这个函数。将程序清单7-1中的代码输入到boost.py中并保存文件。
程序清单7-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 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].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 #❶ 计算加权错误率 #print /"split: dim %d, thresh %.2f, thresh ineqal: %s, the weighted error is %.3f/" %(i, threshVal, inequal, weightedError) if weightedError < minError: minError = weightedError bestClasEst = predictedVals.copy bestStump[/'dim/'] = i bestStump[/'thresh/'] = threshVal bestStump[/'ineq/'] = inequal return bestStump,minError,bestClasEst 上述程序包含两个函数。第一个函数stumpClassify是通过阈值比较对数据进行分类的。所有在阈值一边的数据会分到类别-1，而在另外一边的数据分到类别+1。该函数可以通过数组过滤来实现，首先将返回数组的全部元素设置为1，然后将所有不满足不等式要求的元素设置为-1。可以基于数据集中的任一元素进行比较，同时也可以将不等号在大于、小于之间切换。
第二个函数buildStump将会遍历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算法。
为了解实际运行过程，在Python提示符下输入如下命令：
>>> D = mat(ones((5,1))/5)>>> adaboost.buildStump(datMat,classLabels,D)split: dim 0, thresh 0.90, thresh ineqal: lt, the weighted error is 0.400split: dim 0, thresh 0.90, thresh ineqal: gt, the weighted error is 0.600split: dim 0, thresh 1.00, thresh ineqal: lt, the weighted error is 0.400split: dim 0, thresh 1.00, thresh ineqal: gt, the weighted error is 0.600 .split: dim 1, thresh 2.10, thresh ineqal: lt, the weighted error is 0.600split: dim 1, thresh 2.10, thresh ineqal: gt, the weighted error is 0.400({/'dim/': 0, /'ineq/': /'lt/', /'thresh/': 1.3}, matrix([[ 0.2]]), array([[-1.], [ 1.], [-1.], [-1.], [ 1.]])) buildStump在所有可能的值上遍历的同时，我们也可以看到输出的结果，并且最后会看到返回的字典。读者可以思考一下，该词典是否对应了最小可能的加权错误率？是否存在其他的设置也能得到相同的错误率？
上述单层决策树的生成函数是决策树的一个简化版本。它就是所谓的弱学习器，即弱分类算法。到现在为止，我们已经构建了单层决策树，并生成了程序，做好了过渡到完整AdaBoost算法的准备。在下一节当中，我们将使用多个弱分类器来构建AdaBoost代码。