前面是做了一輪決策，按照信息論的方式，對各特征做了分析，確定了能夠帶來最大信息增益（注意是熵減）的特征。但僅這一步是不夠的，我們需要繼續(xù)對葉子節(jié)點進(jìn)行同樣的操作，直到完成如下的目標(biāo)：
[if !supportLists]1）[endif]程序遍歷完所有劃分?jǐn)?shù)據(jù)集的屬性；
[if !supportLists]2）[endif]每個分支下的所有實例都具有相同的分類；
如果程序已經(jīng)遍歷完所有劃分?jǐn)?shù)據(jù)集的屬性，葉子節(jié)點下的實例仍然不具備相同的分類，那就采用多數(shù)表決的方法（有點像KNN）來決定該葉子節(jié)點的分類。
好，上代碼。
def majorityCnt(classList):
????classCount={}
????for vote in classList:
????????if vote not in classCount.keys(): classCount[vote] = 0
????????classCount[vote] += 1
????sortedClassCount=sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
????return sortedClassCount[0][0]
如上代碼就不逐行展開了，其實就是把一個數(shù)組中的標(biāo)簽項數(shù)一下數(shù)，然后找到哪一個標(biāo)簽出現(xiàn)的次數(shù)最多，和KNN中相關(guān)的排序方式類似。
我們再來看看，整棵樹的遍歷：
def createTree(dataSet, labels):
????classList = [example[-1] for example in dataSet]
????if classList.count(classList[0]) == len(classList):
????????return classList[0]
????if len(dataSet[0]) == 1:
????????return majorityCnt(classList)
????bestFeat = chooseBestFeatureToSplit(dataSet)
????bestFeatLabel = labels[bestFeat]
????myTree = {bestFeatLabel:{}}
????del(labels[bestFeat])
????featValues = [example[bestFeat] for example in dataSet]
????uniqueVals = set(featValues)
????for value in uniqueVals:
????????subLabels = labels[:]
????????myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
????return myTree
代碼一共16行。這段代碼比較關(guān)鍵，而且不算太容易看懂，我們來逐行看一下：
def createTree(dataSet, labels):
#定義函數(shù)，dataSet實際上是帶了標(biāo)簽值的數(shù)據(jù)集，labels其實是標(biāo)簽值的意義定義，詳見前面的數(shù)據(jù)集定義
????classList = [example[-1] for example in dataSet]
#classList實際上就是標(biāo)簽值的數(shù)組，標(biāo)簽值位于數(shù)據(jù)集的最后一列
????if classList.count(classList[0]) == len(classList):
#這里做了一個判斷，count方法的作用就是數(shù)出數(shù)組中某個元素值的個數(shù)，在這里就是對classList[0]做了計數(shù)，當(dāng)它的數(shù)量等同于數(shù)組的長度時，說明這個數(shù)組里沒有別的標(biāo)簽了，即已經(jīng)分到了標(biāo)簽唯一的狀態(tài)；按決策樹葉子節(jié)點是否達(dá)到不可分的條件2，已經(jīng)完成
????????return classList[0]
#返回classList[0]，即當(dāng)前葉子節(jié)點唯一的標(biāo)簽值
????if len(dataSet[0]) == 1:
????????return majorityCnt(classList)
#如果dataSet的長度為1，那就等于是葉子節(jié)點中特征值只有1個，這個時候就滿足了決策樹葉子節(jié)點是否達(dá)到不可分的條件1，程序遍歷完所有劃分?jǐn)?shù)據(jù)集的屬性，這個時候我們要對葉子節(jié)點中的標(biāo)簽進(jìn)行統(tǒng)計，通過多數(shù)表決的方法確定并返回這一分支的標(biāo)簽值。
????bestFeat = chooseBestFeatureToSplit(dataSet)
????bestFeatLabel = labels[bestFeat]
#如果不是上述的兩種情況，即節(jié)點還可分，那么就用chooseBestFeatureToSplit方法找到最佳的特征項，并對節(jié)點進(jìn)行分解。
????myTree = {bestFeatLabel:{}}
#建立一個字典myTree
????del(labels[bestFeat])
#刪除已選出的特征
????featValues = [example[bestFeat] for example in dataSet]
#根據(jù)最佳特征的下標(biāo)，從dataSet里取出相關(guān)特征的值的數(shù)組
????uniqueVals = set(featValues)
#去重，得到該數(shù)組中可能的值
????for value in uniqueVals:
#遍歷所有可能的值
????????subLabels = labels[:]
#復(fù)制出一個label數(shù)組，這個數(shù)組已經(jīng)刪掉了之前的最佳特征項
????????myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
#根據(jù)最優(yōu)的特征進(jìn)行分叉，每一個分叉再去進(jìn)行生成子樹的遞歸操作（這是關(guān)鍵，通過遞歸遍歷生成所有的子節(jié)點，并根據(jù)那兩條要求確定是否終止并直接return）
????return myTree
#返回樹（注意這里的返回，可能是一棵子樹，因為是通過遞歸生成了整棵樹，只有最開始的調(diào)用才是根節(jié)點）
好了，至此，這段代碼結(jié)束。這段代碼不算太容易看懂，原理好懂，但是算法理論要想跟代碼聯(lián)系在一起，還是挺復(fù)雜的。最終生成的樹結(jié)構(gòu)如下：
它是個什么呢？其實就是一開始的最優(yōu)特征項是“no surfacing”，然后進(jìn)行分叉，左邊由于標(biāo)簽一致所以結(jié)束，右邊進(jìn)行再分叉，然后因為特征用完，結(jié)束。
一棵有意思的樹。
