在樹的構建過程中，需要解決多種類型數據的存儲問題。與第3章類似，這裡將使用一部字典來存儲樹的數據結構，該字典將包含以下4個元素。
- 待切分的特徵。
- 待切分的特徵值。
- 右子樹。當不再需要切分的時候，也可以是單個值。
- 左子樹。與右子樹類似。
這與第3章的樹結構有一點不同。第3章用一部字典來存儲每個切分，但該字典可以包含兩個或兩個以上的值。而CART算法只做二元切分，所以這裡可以固定樹的數據結構。樹包含左鍵和右鍵，可以存儲另一棵子樹或者單個值。字典還包含特徵和特徵值這兩個鍵，它們給出切分算法所有的特徵和特徵值。當然，讀者可以用面向對象的編程模式來建立這個數據結構。例如，可以用下面的Python代碼來建立樹節點：
class treeNode:
def __init__(self, feat, val, right, left):
featureToSplitOn = feat
valueOfSplit = val
rightBranch = right
leftBranch = left
當使用C++這樣不太靈活的編程語言時，你可能要用面向對像編程模式來實現樹結構。Python具有足夠的靈活性，可以直接使用字典來存儲樹結構而無須另外自定義一個類，從而有效地減少代碼量。Python不是一種強類型編程語言 ，因此接下來會看到，樹的每個分枝還可以再包含其他樹、數值型數據甚至是向量。
本章將構建兩種樹：第一種是9.4節的回歸樹（regression tree），其每個葉節點包含單個值；第二種是9.5節的模型樹（model tree），其每個葉節點包含一個線性方程。創建這兩種樹時，我們將盡量使得代碼之間可以重用。下面先給出兩種樹構建算法中的一些共用代碼。
函數createTree的偽代碼大致如下：
找到最佳的待切分特徵:
如果該節點不能再分，將該節點存為葉節點
執行二元切分
在右子樹調用createTree方法
在左子樹調用createTree方法
打開文本編輯器，創建文件regTrees.py並添加如下代碼。
程序清單9-1 CART算法的實現代碼
from numpy import *
def loadDataSet(fileName):
dataMat =
fr = open(fileName)
for line in fr.readlines:
curLine = line.strip.split(\'t\')
#❶ 將每行映射成浮點數
fltLine = map(float,curLine)
dataMat.append(fltLine)
return dataMat
def binSplitDataSet(dataSet, feature, value):
mat0 = dataSet[nonzero(dataSet[:,feature] > value)[0],:][0]
mat1 = dataSet[nonzero(dataSet[:,feature] <= value)[0],:][0]
return mat0,mat1
def createTree(dataSet, leafType=regLeaf, errType=regErr, ops=(1,4)):
feat, val = chooseBestSplit(dataSet, leafType, errType, ops)
#❷ 滿足停止條件時返回葉節點值
if feat == None: return val
retTree = {}
retTree[\'spInd\'] = feat
retTree[\'spVal\'] = val
lSet, rSet = binSplitDataSet(dataSet, feat, val)
retTree[\'left\'] = createTree(lSet, leafType, errType, ops)
retTree[\'right\'] = createTree(rSet, leafType, errType, ops)
return retTree
上述程序清單包含3個函數：第一個函數是loadDataSet ，該函數與其他章節中同名函數功能類似。在前面的章節中，目標變量會單獨存放其自己的列表中，但這裡的數據會存放在一起。該函數讀取一個以tab鍵為分隔符的文件，然後將每行的內容保存成一組浮點數❶。
第二個函數是binSplitDataSet，該函數有3個參數：數據集合、待切分的特徵和該特徵的某個值。在給定特徵和特徵值的情況下，該函數通過數組過濾方式將上述數據集合切分得到兩個子集並返回。
最後一個函數是樹構建函數createTree，它有4個參數：數據集和其他3個可選參數。這些可選參數決定了樹的類型：leafType給出建立葉節點的函數；errType代表誤差計算函數；而ops是一個包含樹構建所需其他參數的元組。
函數createTree是一個遞歸函數。該函數首先嘗試將數據集分成兩個部分，切分由函數chooseBestSplit完成（這裡未給出該函數的實現）。如果滿足停止條件，chooseBestSplit將返回None和某類模型的值❷。如果構建的是回歸樹，該模型是一個常數。如果是模型樹，其模型是一個線性方程。後面會看到停止條件的作用方式。如果不滿足停止條件，chooseBestSplit將創建一個新的Python字典並將數據集分成兩份，在這兩份數據集上將分別繼續遞歸調用createTree函數。
程序清單9-1的代碼很容易理解，但其中的方法 chooseBestSplit現在暫時尚未實現，所以函數還不能看到createTree的實際效果。但是下面可以先測試其他兩個函數的效果。將程序清單9-1的代碼保存在文件regTrees.py中並在Python提示符下輸入如下命令：
>>> import regTrees
>>> testMat=mat(eye(4))
>>> testMat
matrix([[ 1., 0., 0., 0.],
[ 0., 1., 0., 0.],
[ 0., 0., 1., 0.],
[ 0., 0., 0., 1.]])
這樣就創建了一個簡單的矩陣，現在按指定列的某個值來切分該矩陣。
>>> mat0,mat1=regTrees.binSplitDataSet(testMat,1,0.5)
>>> mat0
matrix([[ 0., 1., 0., 0.]])
>>> mat1
matrix([[ 1., 0., 0., 0.],
[ 0., 0., 1., 0.],
[ 0., 0., 0., 1.]])
很有趣吧。下面給出回歸樹的chooseBestSplit函數，還會看到更有趣的結果。下一節將針對回歸樹構建，在chooseBestSplit函數里加入具體代碼，之後就可以使用程序清單9-1的CART算法來構建回歸樹。