在樹的構(gòu)建過程中，需要解決多種類型數(shù)據(jù)的存儲(chǔ)問題。在此將使用一部字典來存儲(chǔ)樹的數(shù)據(jù)結(jié)構(gòu)，該字典將包含以下4個(gè)元素。

? 待切分的特征。

? 待切分的特征值。

? 右子樹。當(dāng)不再需要切分的時(shí)候，也可以是單個(gè)值。

? 左子樹。與右子樹類似。

CART算法只做二元切分，所以這里可以固定樹的數(shù)據(jù)結(jié)構(gòu)。樹包含左鍵和右鍵，可以存儲(chǔ)另一棵子樹或者單個(gè)值。字典還包含特征和特征值這兩個(gè)鍵，它們給出切分算法所有的特征和特征值。當(dāng)然，讀者可以用面向?qū)ο蟮木幊棠Ｊ絹斫⑦@個(gè)數(shù)據(jù)結(jié)構(gòu)。例如，可以用下面的Python代碼來建立樹節(jié)點(diǎn)：

class treeNode ():

     def __init__(self, feat, val, right, left):

           featureToSplitOn = feat

           valueofSplit = val

           rightBranch = right

           leftBranch = left

當(dāng)使用C++這樣不太靈活的編程語言時(shí)，你可能要用面向?qū)ο缶幊棠Ｊ絹韺?shí)現(xiàn)樹結(jié)構(gòu)。Python具有足夠的靈活性，可以直接使用字典來存儲(chǔ)樹結(jié)構(gòu)而無須另外自定義一個(gè)類，從而有效地減少代碼量。Python不是一種強(qiáng)類型編程語言，因此接下來會(huì)看到，樹的每個(gè)分枝還可以再包含其他樹、數(shù)值型數(shù)據(jù)甚至是向量。

在此將構(gòu)建兩種樹：第一種是回歸樹（regression tree)，其每個(gè)葉節(jié)點(diǎn)包含單個(gè)值；第二種是模型樹（model tree），其每個(gè)葉節(jié)點(diǎn)包含一個(gè)線性方程。創(chuàng)建這兩種樹時(shí)，我們將盡量使得代碼之間可以重用。下面先給出兩種樹構(gòu)建算法中的一些共用代碼。

函數(shù)createTree()的偽代碼大致如下：

找到最佳的待切分特征：

      如果該節(jié)點(diǎn)不能再分，將該節(jié)點(diǎn)存為葉節(jié)點(diǎn)

      執(zhí)行二元切分

      在右子樹調(diào)用createTree()方法

      在左子樹調(diào)用createTree()方法

打開文本編輯器，創(chuàng)建文件regTrees.py并添加如下代碼。