前面是做了一輪決策，按照信息論的方式指蚁，對(duì)各特征做了分析菱父，確定了能夠帶來最大信息增益（注意是熵減）的特征颈娜。但僅這一步是不夠的，我們需要繼續(xù)對(duì)葉子節(jié)點(diǎn)進(jìn)行同樣的操作浙宜，直到完成如下的目標(biāo)：
[if !supportLists]1）[endif]程序遍歷完所有劃分?jǐn)?shù)據(jù)集的屬性官辽；
[if !supportLists]2）[endif]每個(gè)分支下的所有實(shí)例都具有相同的分類；
如果程序已經(jīng)遍歷完所有劃分?jǐn)?shù)據(jù)集的屬性粟瞬，葉子節(jié)點(diǎn)下的實(shí)例仍然不具備相同的分類同仆，那就采用多數(shù)表決的方法（有點(diǎn)像KNN）來決定該葉子節(jié)點(diǎn)的分類。
好裙品，上代碼俗批。
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í)就是把一個(gè)數(shù)組中的標(biāo)簽項(xiàng)數(shù)一下數(shù)市怎，然后找到哪一個(gè)標(biāo)簽出現(xiàn)的次數(shù)最多岁忘，和KNN中相關(guān)的排序方式類似。
我們?cè)賮砜纯囱媲幔脴涞谋闅v：
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實(shí)際上是帶了標(biāo)簽值的數(shù)據(jù)集，labels其實(shí)是標(biāo)簽值的意義定義揩懒，詳見前面的數(shù)據(jù)集定義
????classList = [example[-1] for example in dataSet]
#classList實(shí)際上就是標(biāo)簽值的數(shù)組什乙，標(biāo)簽值位于數(shù)據(jù)集的最后一列
????if classList.count(classList[0]) == len(classList):
#這里做了一個(gè)判斷，count方法的作用就是數(shù)出數(shù)組中某個(gè)元素值的個(gè)數(shù)已球，在這里就是對(duì)classList[0]做了計(jì)數(shù)臣镣，當(dāng)它的數(shù)量等同于數(shù)組的長(zhǎng)度時(shí)辅愿，說明這個(gè)數(shù)組里沒有別的標(biāo)簽了，即已經(jīng)分到了標(biāo)簽唯一的狀態(tài)忆某；按決策樹葉子節(jié)點(diǎn)是否達(dá)到不可分的條件2点待，已經(jīng)完成
????????return classList[0]
#返回classList[0]，即當(dāng)前葉子節(jié)點(diǎn)唯一的標(biāo)簽值
????if len(dataSet[0]) == 1:
????????return majorityCnt(classList)
#如果dataSet的長(zhǎng)度為1弃舒，那就等于是葉子節(jié)點(diǎn)中特征值只有1個(gè)癞埠，這個(gè)時(shí)候就滿足了決策樹葉子節(jié)點(diǎn)是否達(dá)到不可分的條件1，程序遍歷完所有劃分?jǐn)?shù)據(jù)集的屬性聋呢，這個(gè)時(shí)候我們要對(duì)葉子節(jié)點(diǎn)中的標(biāo)簽進(jìn)行統(tǒng)計(jì)苗踪，通過多數(shù)表決的方法確定并返回這一分支的標(biāo)簽值。
????bestFeat = chooseBestFeatureToSplit(dataSet)
????bestFeatLabel = labels[bestFeat]
#如果不是上述的兩種情況削锰，即節(jié)點(diǎn)還可分通铲，那么就用chooseBestFeatureToSplit方法找到最佳的特征項(xiàng)，并對(duì)節(jié)點(diǎn)進(jìn)行分解器贩。
????myTree = {bestFeatLabel:{}}
#建立一個(gè)字典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ù)制出一個(gè)label數(shù)組蛹稍，這個(gè)數(shù)組已經(jīng)刪掉了之前的最佳特征項(xiàng)
????????myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
#根據(jù)最優(yōu)的特征進(jìn)行分叉碗啄，每一個(gè)分叉再去進(jìn)行生成子樹的遞歸操作（這是關(guān)鍵，通過遞歸遍歷生成所有的子節(jié)點(diǎn)稳摄，并根據(jù)那兩條要求確定是否終止并直接return）
????return myTree
#返回樹（注意這里的返回稚字，可能是一棵子樹，因?yàn)槭峭ㄟ^遞歸生成了整棵樹厦酬，只有最開始的調(diào)用才是根節(jié)點(diǎn)）
好了胆描，至此，這段代碼結(jié)束仗阅。這段代碼不算太容易看懂昌讲，原理好懂，但是算法理論要想跟代碼聯(lián)系在一起减噪，還是挺復(fù)雜的短绸。最終生成的樹結(jié)構(gòu)如下：
它是個(gè)什么呢？其實(shí)就是一開始的最優(yōu)特征項(xiàng)是“no surfacing”筹裕，然后進(jìn)行分叉醋闭，左邊由于標(biāo)簽一致所以結(jié)束，右邊進(jìn)行再分叉朝卒，然后因?yàn)樘卣饔猛曛ぢ撸Y(jié)束。
一棵有意思的樹抗斤。
