一、前言
上篇文章機器學習實戰(zhàn)教程（二）：決策樹基礎篇講述了機器學習決策樹的原理，以及如何選擇最優(yōu)特征作為分類特征。本篇文章將在此基礎上進行介紹。主要包括：
決策樹構建
決策樹可視化
使用決策樹進行分類預測
決策樹的存儲和讀取
sklearn實戰(zhàn)之預測隱形眼睛類型
二、決策樹構建
上篇文章也粗略提到過，構建決策樹的算法有很多。篇幅原因，本篇文章只使用ID3算法構建決策樹。
1、ID3算法
ID3算法的核心是在決策樹各個結點上對應信息增益準則選擇特征，遞歸地構建決策樹。具體方法是：從根結點(root node)開始，對結點計算所有可能的特征的信息增益，選擇信息增益最大的特征作為結點的特征，由該特征的不同取值建立子節(jié)點；再對子結點遞歸地調(diào)用以上方法，構建決策樹；直到所有特征的信息增益均很小或沒有特征可以選擇為止。最后得到一個決策樹。ID3相當于用極大似然法進行概率模型的選擇。
在使用ID3構造決策樹之前，我們再分析下數(shù)據(jù)。
利用上篇文章求得的結果，由于特征A3(有自己的房子)的信息增益值最大，所以選擇特征A3作為根結點的特征。它將訓練集D劃分為兩個子集D1(A3取值為"是")和D2(A3取值為"否")。由于D1只有同一類的樣本點，所以它成為一個葉結點，結點的類標記為“是”。
對D2則需要從特征A1(年齡)，A2(有工作)和A4(信貸情況)中選擇新的特征，計算各個特征的信息增益：
根據(jù)計算，選擇信息增益最大的特征A2(有工作)作為結點的特征。由于A2有兩個可能取值，從這一結點引出兩個子結點：一個對應"是"(有工作)的子結點，包含3個樣本，它們屬于同一類，所以這是一個葉結點，類標記為"是"；另一個是對應"否"(無工作)的子結點，包含6個樣本，它們也屬于同一類，所以這也是一個葉結點，類標記為"否"。
這樣就生成了一個決策樹，該決策樹只用了兩個特征(有兩個內(nèi)部結點)，生成的決策樹如下圖所示。
這樣我們就使用ID3算法構建出來了決策樹，接下來，讓我們看看如何進行代實現(xiàn)。
2、編寫代碼構建決策樹
我們使用字典存儲決策樹的結構，比如上小節(jié)我們分析出來的決策樹，用字典可以表示為：
# -*- coding: UTF-8 -*-
from math import log
import operator
"""
函數(shù)說明:計算給定數(shù)據(jù)集的經(jīng)驗熵(香農(nóng)熵)
Parameters:
? ? dataSet - 數(shù)據(jù)集
Returns:
? ? shannonEnt - 經(jīng)驗熵(香農(nóng)熵)
Author:
? ? Jack Cui
Modify:
? ? 2017-07-24
"""
def calcShannonEnt(dataSet):
? ? numEntires = len(dataSet)? ? ? ? ? ? ? ? ? ? ? ? #返回數(shù)據(jù)集的行數(shù)
? ? labelCounts = {}? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #保存每個標簽(Label)出現(xiàn)次數(shù)的字典
? ? for featVec in dataSet:? ? ? ? ? ? ? ? ? ? ? ? ? ? #對每組特征向量進行統(tǒng)計
? ? ? ? currentLabel = featVec[-1]? ? ? ? ? ? ? ? ? ? #提取標簽(Label)信息
? ? ? ? if currentLabel not in labelCounts.keys():? ? #如果標簽(Label)沒有放入統(tǒng)計次數(shù)的字典,添加進去
? ? ? ? ? ? labelCounts[currentLabel] = 0
? ? ? ? labelCounts[currentLabel] += 1? ? ? ? ? ? ? ? #Label計數(shù)
? ? shannonEnt = 0.0? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #經(jīng)驗熵(香農(nóng)熵)
? ? for key in labelCounts:? ? ? ? ? ? ? ? ? ? ? ? ? ? #計算香農(nóng)熵
? ? ? ? prob = float(labelCounts[key]) / numEntires? ? #選擇該標簽(Label)的概率
? ? ? ? shannonEnt -= prob * log(prob, 2)? ? ? ? ? ? #利用公式計算
? ? return shannonEnt? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #返回經(jīng)驗熵(香農(nóng)熵)
"""
函數(shù)說明:創(chuàng)建測試數(shù)據(jù)集
Parameters:
? ? 無
Returns:
? ? dataSet - 數(shù)據(jù)集
? ? labels - 特征標簽
Author:
? ? Jack Cui
Modify:
? ? 2017-07-20
"""
def createDataSet():
? ? dataSet = [[0, 0, 0, 0, 'no'],? ? ? ? ? ? ? ? ? ? ? ? #數(shù)據(jù)集
? ? ? ? ? ? [0, 0, 0, 1, 'no'],
? ? ? ? ? ? [0, 1, 0, 1, 'yes'],
? ? ? ? ? ? [0, 1, 1, 0, 'yes'],
? ? ? ? ? ? [0, 0, 0, 0, 'no'],
? ? ? ? ? ? [1, 0, 0, 0, 'no'],
? ? ? ? ? ? [1, 0, 0, 1, 'no'],
? ? ? ? ? ? [1, 1, 1, 1, 'yes'],
? ? ? ? ? ? [1, 0, 1, 2, 'yes'],
? ? ? ? ? ? [1, 0, 1, 2, 'yes'],
? ? ? ? ? ? [2, 0, 1, 2, 'yes'],
? ? ? ? ? ? [2, 0, 1, 1, 'yes'],
? ? ? ? ? ? [2, 1, 0, 1, 'yes'],
? ? ? ? ? ? [2, 1, 0, 2, 'yes'],
? ? ? ? ? ? [2, 0, 0, 0, 'no']]
? ? labels = ['年齡', '有工作', '有自己的房子', '信貸情況']? ? ? ? #特征標簽
? ? return dataSet, labels? ? ? ? ? ? ? ? ? ? ? ? ? ? #返回數(shù)據(jù)集和分類屬性
"""
函數(shù)說明:按照給定特征劃分數(shù)據(jù)集
Parameters:
? ? dataSet - 待劃分的數(shù)據(jù)集
? ? axis - 劃分數(shù)據(jù)集的特征
? ? value - 需要返回的特征的值
Returns:
? ? 無
Author:
? ? Jack Cui
Modify:
? ? 2017-07-24
"""
def splitDataSet(dataSet, axis, value):? ? ?
? ? retDataSet = []? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #創(chuàng)建返回的數(shù)據(jù)集列表
? ? for featVec in dataSet:? ? ? ? ? ? ? ? ? ? ? ? ? ? #遍歷數(shù)據(jù)集
? ? ? ? if featVec[axis] == value:
? ? ? ? ? ? reducedFeatVec = featVec[:axis]? ? ? ? ? ? ? ? #去掉axis特征
? ? ? ? ? ? reducedFeatVec.extend(featVec[axis+1:])? ? #將符合條件的添加到返回的數(shù)據(jù)集
? ? ? ? ? ? retDataSet.append(reducedFeatVec)
? ? return retDataSet? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #返回劃分后的數(shù)據(jù)集
"""
函數(shù)說明:選擇最優(yōu)特征
Parameters:
? ? dataSet - 數(shù)據(jù)集
Returns:
? ? bestFeature - 信息增益最大的(最優(yōu))特征的索引值
Author:
? ? Jack Cui
Modify:
? ? 2017-07-20
"""
def chooseBestFeatureToSplit(dataSet):
? ? numFeatures = len(dataSet[0]) - 1? ? ? ? ? ? ? ? ? ? #特征數(shù)量
? ? baseEntropy = calcShannonEnt(dataSet)? ? ? ? ? ? ? ? #計算數(shù)據(jù)集的香農(nóng)熵
? ? bestInfoGain = 0.0? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #信息增益
? ? bestFeature = -1? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #最優(yōu)特征的索引值
? ? for i in range(numFeatures):? ? ? ? ? ? ? ? ? ? ? ? #遍歷所有特征
? ? ? ? #獲取dataSet的第i個所有特征
? ? ? ? featList = [example[i] for example in dataSet]
? ? ? ? uniqueVals = set(featList)? ? ? ? ? ? ? ? ? ? ? ? #創(chuàng)建set集合{},元素不可重復
? ? ? ? newEntropy = 0.0? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #經(jīng)驗條件熵
? ? ? ? for value in uniqueVals:? ? ? ? ? ? ? ? ? ? ? ? #計算信息增益
? ? ? ? ? ? subDataSet = splitDataSet(dataSet, i, value)? ? ? ? #subDataSet劃分后的子集
? ? ? ? ? ? prob = len(subDataSet) / float(len(dataSet))? ? ? ? ? #計算子集的概率
? ? ? ? ? ? newEntropy += prob * calcShannonEnt(subDataSet)? ? #根據(jù)公式計算經(jīng)驗條件熵
? ? ? ? infoGain = baseEntropy - newEntropy? ? ? ? ? ? ? ? ? ? #信息增益
? ? ? ? # print("第%d個特征的增益為%.3f" % (i, infoGain))? ? ? ? ? ? #打印每個特征的信息增益
? ? ? ? if (infoGain > bestInfoGain):? ? ? ? ? ? ? ? ? ? ? ? ? ? #計算信息增益
? ? ? ? ? ? bestInfoGain = infoGain? ? ? ? ? ? ? ? ? ? ? ? ? ? #更新信息增益，找到最大的信息增益
? ? ? ? ? ? bestFeature = i? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #記錄信息增益最大的特征的索引值
? ? return bestFeature? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #返回信息增益最大的特征的索引值
"""
函數(shù)說明:統(tǒng)計classList中出現(xiàn)此處最多的元素(類標簽)
Parameters:
? ? classList - 類標簽列表
Returns:
? ? sortedClassCount[0][0] - 出現(xiàn)此處最多的元素(類標簽)
Author:
? ? Jack Cui
Modify:
? ? 2017-07-24
"""
def majorityCnt(classList):
? ? classCount = {}
? ? for vote in classList:? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #統(tǒng)計classList中每個元素出現(xiàn)的次數(shù)
? ? ? ? if vote not in classCount.keys():classCount[vote] = 0?
? ? ? ? classCount[vote] += 1
? ? sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1), reverse = True)? ? ? ? #根據(jù)字典的值降序排序
? ? return sortedClassCount[0][0]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #返回classList中出現(xiàn)次數(shù)最多的元素
"""
函數(shù)說明:創(chuàng)建決策樹
Parameters:
? ? dataSet - 訓練數(shù)據(jù)集
? ? labels - 分類屬性標簽
? ? featLabels - 存儲選擇的最優(yōu)特征標簽
Returns:
? ? myTree - 決策樹
Author:
? ? Jack Cui
Modify:
? ? 2017-07-25
"""
def createTree(dataSet, labels, featLabels):
? ? classList = [example[-1] for example in dataSet]? ? ? ? ? ? #取分類標簽(是否放貸:yes or no)
? ? if classList.count(classList[0]) == len(classList):? ? ? ? ? ? #如果類別完全相同則停止繼續(xù)劃分
? ? ? ? return classList[0]
? ? if len(dataSet[0]) == 1 or len(labels) == 0:? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #遍歷完所有特征時返回出現(xiàn)次數(shù)最多的類標簽
? ? ? ? return majorityCnt(classList)
? ? bestFeat = chooseBestFeatureToSplit(dataSet)? ? ? ? ? ? ? ? #選擇最優(yōu)特征
? ? bestFeatLabel = labels[bestFeat]? ? ? ? ? ? ? ? ? ? ? ? ? ? #最優(yōu)特征的標簽
? ? featLabels.append(bestFeatLabel)
? ? myTree = {bestFeatLabel:{}}? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #根據(jù)最優(yōu)特征的標簽生成樹
? ? del(labels[bestFeat])? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #刪除已經(jīng)使用特征標簽
? ? featValues = [example[bestFeat] for example in dataSet]? ? ? ? #得到訓練集中所有最優(yōu)特征的屬性值
? ? uniqueVals = set(featValues)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #去掉重復的屬性值
? ? for value in uniqueVals:? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #遍歷特征，創(chuàng)建決策樹。? ? ? ?
? ? ? ? subLabels = labels[:]? ? ? ? ? ? ?
? ? ? ? myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels, featLabels)
? ? return myTree
if __name__ == '__main__':
? ? dataSet, labels = createDataSet()
? ? featLabels = []
? ? myTree = createTree(dataSet, labels, featLabels)
? ? print(myTree)
遞歸創(chuàng)建決策樹時，遞歸有兩個終止條件：第一個停止條件是所有的類標簽完全相同，則直接返回該類標簽；第二個停止條件是使用完了所有特征，仍然不能將數(shù)據(jù)劃分僅包含唯一類別的分組，即決策樹構建失敗，特征不夠用。此時說明數(shù)據(jù)緯度不夠，由于第二個停止條件無法簡單地返回唯一的類標簽，這里挑選出現(xiàn)數(shù)量最多的類別作為返回值。
運行上述代碼，我們可以看到如下結果：
可見，我們的決策樹已經(jīng)構建完成了。這時候，有的朋友可能會說，這個決策樹看著好別扭，雖然這個能看懂，但是如果多點的結點，就不好看了。能直觀點嗎？完全沒有問題，我們可以使用強大的Matplotlib繪制決策樹。免費視頻教程：www.mlxs.top??
