1.什么是決策樹

決策樹是一種基本的分類和回歸方法，本文主要講解用于分類的決策樹。決策樹就是根據(jù)相關(guān)的條件進(jìn)行分類的一種樹形結(jié)構(gòu)，比如某高端約會(huì)網(wǎng)站針對(duì)女客戶約會(huì)對(duì)象見面的安排過程就是一個(gè)決策樹：

根據(jù)給定的數(shù)據(jù)集創(chuàng)建一個(gè)決策樹就是機(jī)器學(xué)習(xí)的課程，創(chuàng)建一個(gè)決策樹可能會(huì)花費(fèi)較多的時(shí)間，但是使用一個(gè)決策樹卻非?？臁?/p>

創(chuàng)建決策樹時(shí)最關(guān)鍵的問題就是選取哪一個(gè)特征作為分類特征，好的分類特征能夠最大化的把數(shù)據(jù)集分開，將無序變?yōu)橛行?。這里就出現(xiàn)了一個(gè)問題，如何描述一個(gè)數(shù)據(jù)集有序的程度？在信息論和概率統(tǒng)計(jì)中，熵表示隨機(jī)變量不確定性的度量，即有序的程度。

現(xiàn)給出一個(gè)集合D，本文所有的討論都以該集合為例：

序號(hào) 不浮出水面是否可以生存 是否有腳蹼 是否為魚類
1?是?是?是?
2?是?是?是?
3?是?否?否?
4?否?是?否?
5?否?是?否

創(chuàng)建該集合的代碼如下：
def create_data_set():
dataSet = [[1,1,'yes'],
[1,1,'yes'],
[1,0,'no'],
[0,1,'no'],
[0,1,'no']]
labels = ['no surfacing', 'flippers'] #不浮出水面是否可以生存，是否有腳蹼
return dataSet, labels

2.熵，信息增益和信息增益比

2.1熵(entropy)

博主第一次接觸“熵”這個(gè)字，是在高中的化學(xué)課上，但是感覺“熵”在化學(xué)課上的含義和信息論中的含義沒什么區(qū)別，都是表示混亂的程度，熵越大，越混亂，比如一杯渾濁水的熵就比一杯純凈的水熵大。

在信息論和概率統(tǒng)計(jì)中，設(shè)X是一個(gè)取有限個(gè)值的離散隨機(jī)變量，其概率分布為：

編寫計(jì)算熵的函數(shù)，其中dataSet是建立決策樹的數(shù)據(jù)集，每行最后一個(gè)元素表示類別：
def cal_Ent(dataSet): #根據(jù)給定數(shù)據(jù)集計(jì)算熵
num = len(dataSet)
labels = {}
for row in dataSet: #統(tǒng)計(jì)所有標(biāo)簽的個(gè)數(shù)
label = row[-1]
if label not in labels.keys():
labels[label] = 0
labels[label] += 1
Ent = 0.0
for key in labels: #計(jì)算熵
prob = float(labels[key]) / num
Ent -= prob * log(prob, 2)
return Ent

2.2信息增益(information gain)

信息增益表示得知特征X的信息而使得類Y的信息的不確定性減少的程度。

當(dāng)熵和條件熵中的概率由數(shù)據(jù)估計(jì)得到時(shí)，所對(duì)應(yīng)的熵與條件熵分別稱為經(jīng)驗(yàn)熵和經(jīng)驗(yàn)條件熵。

決策樹選擇某個(gè)特征作為其分類特征的依據(jù)就是該特征對(duì)于集合的信息增益最大，即去除該特征后，集合變得最有序。仍舊以給定的集合D為例，根據(jù)計(jì)算信息增益準(zhǔn)則選擇最優(yōu)分類特征。

以X1表示“不浮出水面是否可以生存”，則

編寫選擇最佳決策特征的函數(shù)，其中dataSet是建立決策樹的數(shù)據(jù)集，每行最后一個(gè)元素表示類別：
#按照給定特征劃分?jǐn)?shù)據(jù)集，返回第axis個(gè)特征的值為value的所有數(shù)據(jù)
def split_data_set(dataSet, axis, value):
retDataSet = []
for row in dataSet:
if (row[axis]) == value:
reducedRow = row[:axis]
reducedRow.extend(row[axis+1:])
retDataSet.append(reducedRow)
return retDataSet

#選擇最佳決策特征
def choose_best_feature(dataSet):
num = len(dataSet[0]) - 1 #特征數(shù)
baseEnt = cal_Ent(dataSet)
bestInfoGain = 0.0
bestFeature = -1
for i in range(num):
featlist = [example[i] for example in dataSet] #按列遍歷數(shù)據(jù)集，選取一個(gè)特征的所有值
uniqueVals = set(featlist) #一個(gè)特征可以取的值
newEnt = 0.0
for value in uniqueVals:
subDataSet = split_data_set(dataSet, i, value)
prob = len(subDataSet) / float(len(dataSet))
newEnt += prob * cal_Ent(subDataSet)
infoGain = baseEnt - newEnt #信息增益
if (infoGain > bestInfoGain):
bestInfoGain = infoGain
bestFeature = i
return bestFeature

ID3決策樹在生成的過程中，根據(jù)信息增益來選擇特征。

2.3信息增益比(information gain ratio)

以信息增益作為劃分訓(xùn)練數(shù)據(jù)集的特征，存在偏向于選擇取值較多的特征的問題，使用信息增益比可以對(duì)這一問題進(jìn)行校正。

以給定的集合D為例，計(jì)算信息增益比。

根據(jù)信息增益比，選擇X1作為分類的最優(yōu)特征。

C4.5決策樹在生成的過程中，根據(jù)信息增益比來選擇特征。

3.實(shí)現(xiàn)一個(gè)決策樹

3.1創(chuàng)建或載入數(shù)據(jù)集

首先需要?jiǎng)?chuàng)建或載入訓(xùn)練的數(shù)據(jù)集，第一節(jié)用的是創(chuàng)建數(shù)據(jù)集的方法，不過更常用的是利用open()函數(shù)打開文件，載入一個(gè)數(shù)據(jù)集。

3.2生成決策樹

決策樹一般使用遞歸的方法生成。

編寫遞歸函數(shù)有一個(gè)好習(xí)慣，就是先考慮結(jié)束條件。生成決策樹結(jié)束的條件有兩個(gè)：其一是劃分的數(shù)據(jù)都屬于一個(gè)類，其二是所有的特征都已經(jīng)使用了。在第二種結(jié)束情況中，劃分的數(shù)據(jù)有可能不全屬于一個(gè)類，這個(gè)時(shí)候需要根據(jù)多數(shù)表決準(zhǔn)則確定這個(gè)子數(shù)據(jù)集的分類。

在非結(jié)束的條件下，首先選擇出信息增益最大的特征，然后根據(jù)其分類。分類開始時(shí)，記錄分類的特征到?jīng)Q策樹中，然后在特征標(biāo)簽集中刪除該特征，表示已經(jīng)使用過該特征。根據(jù)選中的特征將數(shù)據(jù)集分為若干個(gè)子數(shù)據(jù)集，然后將子數(shù)據(jù)集作為參數(shù)遞歸創(chuàng)建決策樹，最終生成一棵完整的決策樹。

#多數(shù)表決法則
def majorityCnt(classList):
print classList
classCount = {}
for vote in classList: #統(tǒng)計(jì)數(shù)目
if vote not in classCount.keys(): classCount[vote] = 0
classCount += 1
sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
return classCount[0][0]

# 生成決策樹
def create_tree(dataSet, labels):
labelsCloned = labels[:]
classList = [example[-1] for example in dataSet] #[yes,yes,no,no,no]
if classList.count(classList[0]) == len(classList): #只有一種類別，則停止劃分
return classList[0]
if len(dataSet[0]) == 1: #沒有特征，則停止劃分
return majorityCnt(classList)
#print dataSet
bestFeat = choose_best_feature(dataSet)
bestFeatLabel = labelsCloned[bestFeat] #最佳特征的名字
myTree = {bestFeatLabel:{}}
del(labelsCloned[bestFeat])
featValues = [example[bestFeat] for example in dataSet] #獲取最佳特征的所有屬性
uniqueVals = set(featValues)
for value in uniqueVals: #建立子樹
subLabels = labelsCloned[:] #深拷貝，不能改變?cè)剂斜淼膬?nèi)容，因?yàn)槊恳粋€(gè)子樹都要使用
myTree[bestFeatLabel][value] = create_tree(split_data_set(dataSet, bestFeat, value), subLabels)
return myTree

生成的決策樹如下所示：

3.3使用決策樹

使用決策樹對(duì)輸入進(jìn)行分類的函數(shù)也是一個(gè)遞歸函數(shù)。分類函數(shù)需要三個(gè)參數(shù)：決策樹，特征列表，待分類數(shù)據(jù)。特征列表是聯(lián)系決策樹和待分類數(shù)據(jù)的橋梁，決策樹的特征通過特征列表獲得其索引，再通過索引訪問待分類數(shù)據(jù)中該特征的值。
def classify(tree, featLabels, testVec):
firstJudge = tree.keys()[0]
secondDict = tree[firstJudge]
featIndex = featLabels.index(firstJudge) #獲得特征索引
for key in secondDict: #進(jìn)入對(duì)應(yīng)的分類集合
if key == testVec[featIndex]: #按特征分類
if type(secondDict[key]).__name__ == 'dict': #如果分類結(jié)果是一個(gè)字典，則說明還要繼續(xù)分類
classLabel = classify(secondDict[key], featLabels, testVec)
else: #分類結(jié)果不是字典，則分類結(jié)束
classLabel = secondDict[key]
return classLabel

3.4保存或者載入決策樹

生成決策樹是比較花費(fèi)時(shí)間的，所以決策樹生成以后存儲(chǔ)起來，等要用的時(shí)候直接讀取即可。
def store_tree(tree, fileName): #保存樹
import pickle
fw = open(fileName, 'w')
pickle.dump(tree, fw)
fw.close()

def grab_tree(fileName): #讀取樹
import pickle
fr = open(fileName)
return pickle.load(fr)

4.決策樹可視化

使用字典的形式表示決策樹對(duì)于人類來說還是有點(diǎn)抽象，如果能以圖像的方式呈現(xiàn)就很方便了。非常幸運(yùn)，matplotlib中有模塊可以使決策樹可視化，這里就不講解了，直接“拿來使用”。將treePlotter.py拷貝到我們文件的根目錄，直接導(dǎo)入treePlotter，然后調(diào)用treePlotter.createPlot()函數(shù)即可：
import treePlotter
treePlotter.createPlot(tree)

如上面的決策樹可視化后如下：

5.使用決策樹預(yù)測(cè)隱形眼鏡類型

隱形眼鏡數(shù)據(jù)集包含患者的眼睛狀況以及醫(yī)生推薦的隱形眼鏡類型，患者信息有4維，分別表示年齡，視力類型，是否散光，眼睛狀況，隱形眼鏡類型有3種，分別是軟材質(zhì)，硬材質(zhì)和不適合帶隱形眼鏡。

想要把我們編寫的腳本應(yīng)用于別的數(shù)據(jù)集？沒問題，只要修改載入數(shù)據(jù)集的函數(shù)即可，其他的函數(shù)不需要改變，具體如下：
#載入數(shù)據(jù)
def file2matrix():
file = open("lenses.data.txt")
allLines = file.readlines()
row = len(allLines)
dataSet = []
for line in allLines:
line = line.strip()
listFromLine = line.split()
dataSet.append(listFromLine)
labels = ['age', 'prescription', 'astigmatic', 'tear rate'] #年齡，視力類型，是否散光，眼睛狀況
return dataSet, labels

生成的決策樹可視化后如下：

其實(shí)博主還嘗試了其他的數(shù)據(jù)集，不過決策樹實(shí)在是太復(fù)雜了，太大了，密密麻麻根本看不清楚，誰有興趣可以嘗試一下別的數(shù)據(jù)集。