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

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

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

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

序號 不浮出水面是否可以生存 是否有腳蹼 是否為魚類
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.1熵(entropy)

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

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

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

2.2信息增益(informaTIon gain)

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

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

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

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

編寫選擇最佳決策特征的函數(shù)，其中dataSet是建立決策樹的數(shù)據(jù)集，每行最后一個元素表示類別：
#按照給定特征劃分數(shù)據(jù)集，返回第axis個特征的值為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ù)集，選取一個特征的所有值
uniqueVals = set(featlist) #一個特征可以取的值
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)