單層決策樹（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 retArray
def 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.400
split: dim 0, thresh 0.90, thresh ineqal: gt, the weighted error is 0.600
split: dim 0, thresh 1.00, thresh ineqal: lt, the weighted error is 0.400
split: 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.600
split: 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代碼。