決策樹還可以表示給定特征條件下類的條件機率分布。下圖中(a)的大正方形表示特征空間，每個小矩形表示一個單元。假設 Y Y Y的取值隻有-1和+1,小矩形中的式子表示單元的類。(b)圖表示特征空間劃分确定時，特征單元給定下的條件機率分布。當某個單元 c c c的條件機率滿足 P ( Y = + 1 ∣ X = c ) > 0.5 P(Y=+1|X=c)>0.5 P(Y=+1∣X=c)>0.5時，落在這個單元的執行個體都被視為+1。
P ( X = x i ) = p i i = 1 , 2 , . . . . n H ( X ) = − ∑ i = 1 n p i log p i P(X=x_i)=p_i\ \ \ i=1,2,....n\\ H(X)=-\sum\limits_{i=1}^{n}p_i\log p_i P(X=xi)=pi i=1,2,....nH(X)=−i=1∑npilogpi
H ( X ) H(X) H(X)即為随機變量X的熵。
P ( X = x i , Y = y i ) = p i j i = 1 , 2 , . . . , n ; j = 1 , 2 , . . . , m H ( Y ∣ X ) = ∑ i = 1 n p i H ( Y ∣ X = x i ) P(X=x_i,Y=y_i)=p_{ij} \ \ \ i=1,2,...,n;\ j=1,2,...,m\\ H(Y|X)=\sum\limits_{i=1}^np_iH(Y|X=x_i) P(X=xi,Y=yi)=pij i=1,2,...,n; j=1,2,...,mH(Y∣X)=i=1∑npiH(Y∣X=xi)
H ( Y ∣ X ) H(Y|X) H(Y∣X)表示随機變量X給定條件下随機變量Y的條件熵，換句話說，為X給定條件下Y的條件機率分布的熵對X的數學期望。
資訊增益比：資訊增益 g ( D , A ) g(D,A) g(D,A)與訓練資料集D關于特征A的值的熵 H A ( D ) H_A(D) HA(D)d的比值為資訊增益比 g R ( D , A ) g_R(D,A) gR(D,A)。
g R ( D , A ) = g ( D , A ) H A ( D ) H A ( D ) = − ∑ i = 1 n ∣ D i ∣ ∣ D ∣ l o g 2 ∣ D i ∣ ∣ D ∣ n 為 A 的 特 征 取 值 個 數 g_R(D,A)=\frac{g(D,A)}{H_A(D)}\\ H_A(D)=-\sum\limits_{i=1}^n\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|} \ \ \ n為A的特征取值個數 gR(D,A)=HA(D)g(D,A)HA(D)=−i=1∑n∣D∣∣Di∣log2∣D∣∣Di∣ n為A的特征取值個數
python代碼實作例題：資訊增益與資訊增益比
import numpy as np
import math
#直接更改x,y即可
x = [[1, 0, 0, 1],
[0, 1, 1, 1],
[0, 0, 1, 0]]
y = [0, 0, 1]
feature_num = np.shape(x)[1]
y_len = len(y)
feature = np.array(x)
for i in range(feature_num):
_feature = feature[:, i]
temp_condition_ent = 0
temp_ent_i = 0
HA_D = 0
print(_feature)
for j in set(_feature):
D_i = _feature.tolist().count(j)
temp_ent = 0
for k in set(y):
temp_ent += -(y.count(k) / y_len) * math.log(y.count(k) / y_len)#H(D)
D_ik = 0
for index in range(len(y)):
if y[index] == k and _feature[index] == j:
D_ik = D_ik + 1
if D_ik != 0:
temp_ent_i += -(D_ik / D_i) * math.log(D_ik / D_i)
else:
temp_ent_i = 0
temp_condition_ent += (D_i / y_len) * temp_ent_i#H(D|A)
conditon_ent = temp_ent - temp_condition_ent#g(D|A)
HA_D += -(D_i / y_len) * math.log(D_i / y_len)#H_A(D)
conditon_ent_ratio = conditon_ent / HA_D #g_R(D,A)
print(conditon_ent)
print(conditon_ent_ratio)
C α ( T ) = ∑ t = 1 ∣ T ∣ N t H t ( T ) + α ∣ T ∣ C_\alpha(T)=\sum\limits_{t=1}^{|T|}N_tH_t(T)+\alpha|T| Cα(T)=t=1∑∣T∣NtHt(T)+α∣T∣
這種剪枝方法在ISLR書中也稱為：Cost complexity pruning (or weakest link pruning)
采用的損失函數為：
C α ( T ) = ∑ m = 1 ∣ T ∣ ∑ x i ∈ R m ( y i − y R m ^ ) 2 + α ∣ T ∣ C_\alpha(T)=\sum\limits_{m=1}^{|T|}\sum\limits_{x_i\in R_m}(y_i-\hat{y_{Rm}})^2+\alpha|T| Cα(T)=m=1∑∣T∣xi∈Rm∑(yi−yRm^)2+α∣T∣
其中 R m R_m Rm表示葉子節點中的樣本集。
其中 ∣ T ∣ |T| ∣T∣為樹T的葉子節點個數，t為葉子節點，該葉節點含有 N t N_t Nt個樣本點，其中 k k k類的樣本點有 N t k N_{tk} Ntk個， H t ( T ) H_t(T) Ht(T)為葉節點t的經驗上， α > = 0 \alpha>=0 α>=0為參數。其中：
H t ( T ) = − ∑ k K N t k N t log N t k N t H_t(T)=-\sum\limits_k^K\frac{N_{tk}}{N_t}\log\frac{N_{tk}}{N_t} Ht(T)=−k∑KNtNtklogNtNtk
把該式子帶入損失函數中，第一項記作：
C ( T ) = ∑ t = 1 ∣ T ∣ N t H t ( T ) = − ∑ t = 1 ∣ T ∣ ∑ k K N t k N t log N t k N t C_(T)=\sum\limits_{t=1}^{|T|}N_tH_t(T)=-\sum\limits_{t=1}^{|T|}\sum\limits_k^K\frac{N_{tk}}{N_t}\log\frac{N_{tk}}{N_t} C(T)=t=1∑∣T∣NtHt(T)=−t=1∑∣T∣k∑KNtNtklogNtNtk
這時，決策樹的損失函數又可表示為
C α ( T ) = C ( T ) + α ∣ T ∣ C_\alpha(T) = C(T) + \alpha|T| Cα(T)=C(T)+α∣T∣
其中 C ( T ) C(T) C(T)表示模型對訓練資料的預測誤差，即模型與訓練資料的拟合程度，|T|表示葉子節點的個數（即模型的複雜度）， α \alpha α作為懲罰系數，負責調節拟合程度與複雜度之間的權衡關系。 α = 0 \alpha=0 α=0即不考慮複雜度， α \alpha α越大，模型的複雜度越低。
假設已經将輸入空間劃分為M個單元, R 1 , R 2 . . . R M R_1,R_2...R_M R1,R2...RM,并且在每個單元上有固定的輸出值 c m c_m cm，則模型表示為
f ( x ) = ∑ m = 1 M c m I ( x ∈ R m ) f(x)=\sum\limits_{m=1}^Mc_mI(x \in R_m) f(x)=m=1∑McmI(x∈Rm)
當輸入空間的劃分确定時，可以用平方誤差 ∑ x ∈ R m ( y i − f ( x i ) ) 2 \sum\limits_{x\in R_m}(y_i-f(x_i))^2 x∈Rm∑(yi−f(xi))2來表示回歸樹對于訓練資料的預測誤差，用平方誤差準則求解每個單元上的最優輸出值。已知，單元 R m R_m Rm上的 c m c_m cm的最優值 c m ^ \hat{c_m} cm^是 R m R_m Rm上所有輸入執行個體 x i x_i xi對應的輸出 y i y_i yi的均值：
c m ^ = a v e ( y i ∣ x i ∈ R m ) \hat{c_m} =ave({y_i}|x_i \in R_m) cm^=ave(yi∣xi∈Rm)
輸入空間劃分方法：
假設第j個變量 x ( j ) x^{(j)} x(j)和它取的值s，作為切分變量和切分點，則
R 1 ( j , s ) = { x ∣ x ( j ) ≤ s } a n d R 2 ( j , s ) = { x ∣ x ( j ) > s } R_1(j,s)=\{x|x^{(j)} \leq s \} \ \ and\ \ R_2(j,s)=\{x|x^{(j)} > s \} R1(j,s)={x∣x(j)≤s} and R2(j,s)={x∣x(j)>s}
其中最優切分變量與最優切分點的求解：
min j , s [ min c 1 ∑ x i ∈ R 1 ( j , s ) ( y i − c 1 ) 2 + min c 1 ∑ x i ∈ R 2 ( j , s ) ( y i − c 2 ) 2 ] \min\limits_{j,s}\left [ \min\limits_{c_1}\sum\limits_{x_i \in R_1(j,s)}(y_i-c_1)^2 + \min\limits_{c_1}\sum\limits_{x_i \in R_2(j,s)}(y_i-c_2)^2 \right ] j,smin⎣⎡c1minxi∈R1(j,s)∑(yi−c1)2+c1minxi∈R2(j,s)∑(yi−c2)2⎦⎤
這樣就可以得到切分後區域内的最優輸出值：
c 1 ^ = a v e ( y i ∣ x i ∈ R 1 ( j , s ) ) a n d c 2 ^ = a v e ( y i ∣ x i ∈ R 2 ( j , s ) ) \hat{c_1} =ave({y_i}|x_i \in R_1(j,s)) \ \ and\ \ \hat{c_2} =ave({y_i}|x_i \in R_2(j,s)) c1^=ave(yi∣xi∈R1(j,s)) and c2^=ave(yi∣xi∈R2(j,s))
對每個區域重複上述的劃分過程，直到滿足停止條件。
5.5 最小二乘回歸樹生成算法
輸入：訓練資料集D;
輸出：回歸樹f(x)。
(1)求解最優切分變量j與最優切分點s.（類似決策樹中的特征選擇和劃分資料集）
min j , s [ min c 1 ∑ x i ∈ R 1 ( j , s ) ( y i − c 1 ) 2 + min c 1 ∑ x i ∈ R 2 ( j , s ) ( y i − c 2 ) 2 ] \min\limits_{j,s}\left [ \min\limits_{c_1}\sum\limits_{x_i \in R_1(j,s)}(y_i-c_1)^2 + \min\limits_{c_1}\sum\limits_{x_i \in R_2(j,s)}(y_i-c_2)^2 \right ] j,smin⎣⎡c1minxi∈R1(j,s)∑(yi−c1)2+c1minxi∈R2(j,s)∑(yi−c2)2⎦⎤
(2)劃分區域，決定對應的輸出值
R 1 ( j , s ) = { x ∣ x ( j ) ≤ s } a n d R 2 ( j , s ) = { x ∣ x ( j ) > s } c m ^ = a v e ( y i ∣ x i ∈ R m ) m = 1 , 2 R_1(j,s)=\{x|x^{(j)} \leq s \} \ \ and\ \ R_2(j,s)=\{x|x^{(j)} > s \}\\ \hat{c_m} =ave({y_i}|x_i \in R_m) \ \ m=1,2 R1(j,s)={x∣x(j)≤s} and R2(j,s)={x∣x(j)>s}cm^=ave(yi∣xi∈Rm) m=1,2
(3)繼續對兩子區域調用步驟(1)(2),直至滿足停止條件
(4)将輸入空間劃分為M個區域，生成決策樹：
f ( x ) = ∑ m = 1 M c m I ( x ∈ R m ) f(x)=\sum\limits_{m=1}^Mc_mI(x \in R_m) f(x)=m=1∑McmI(x∈Rm)
分類樹的生成
與決策樹不同，分類樹中采用基尼指數選擇最優特征，确定最優二值切分點：
G i n i ( D ) = 1 − ∑ k = 1 K ( ∣ C k ∣ ∣ D ∣ ) 2 G i n i ( D , A ) = ∣ D 1 ∣ ∣ D ∣ G i n i ( D 1 ) + ∣ D 2 ∣ ∣ D ∣ G i n i ( D 2 ) Gini(D)=1-\sum\limits_{k=1}^K(\frac{|C_k|}{|D|})^2 \\ Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2) Gini(D)=1−k=1∑K(∣D∣∣Ck∣)2Gini(D,A)=∣D∣∣D1∣Gini(D1)+∣D∣∣D2∣Gini(D2)
C k C_k Ck是D中屬于第k類的樣本子集，K是類的個數。D1和D2為經特征值A的某一可能值a劃分的訓練集。
C α ( T t ) < C α ( t ) C_\alpha(T_t)<C_\alpha(t) Cα(Tt)<Cα(t)
(2)當 α \alpha α增大時,在某 α \alpha α時
C α ( T t ) = C α ( t ) α = C ( t ) − C ( T t ) ∣ T t ∣ − 1 C_\alpha(T_t)=C_\alpha(t)\\ \alpha=\frac{C(t)-C(T_t)}{|T_t|-1} Cα(Tt)=Cα(t)α=∣Tt∣−1C(t)−C(Tt)
(3)當 α \alpha α繼續增大時
C α ( T t ) > C α ( t ) C_\alpha(T_t)>C_\alpha(t) Cα(Tt)>Cα(t)
通過以上規律可以發現，當（2）情況發生時， T t T_t Tt與t有相同的損失函數，而t的節點少，是以t比 T t T_t Tt更可取，對 T t T_t Tt進行剪枝。
是以，對 T 0 T_0 T0中的每一内部結點t,計算對應 α = g ( t ) \alpha=g(t) α=g(t):
g ( t ) = C ( t ) − C ( T t ) ∣ T t ∣ − 1 g(t)=\frac{C(t)-C(T_t)}{|T_t|-1} g(t)=∣Tt∣−1C(t)−C(Tt)
表示剪枝後整體損失函數減少的程度。在 T 0 T_0 T0中剪去g(t)最小的 T t T_t Tt
假設所有結點中 g ( t 1 ) g(t_1) g(t1)最小， g ( t 2 ) g(t_2) g(t2)最大。若對結點2進行剪枝，此時結點1中 C α 1 ( T 1 ) > C α 1 ( t 1 ) C_{\alpha_1}(T_1)>C_{\alpha_1}(t_1) Cα1(T1)>Cα1(t1),不剪枝就會造成樹的損失變大，以此類推，其他結點也是如此，最終導緻整體累計的損失更大。若對結點1進行剪枝，其餘節點不剪枝的損失要小于剪枝後的損失，是以不應該修剪，這是整體的損失最小，是以應該剪掉g(t)最小的結點
（3）自上而下的對内部節點t計算 C ( T t ) , ∣ T t ∣ , C(T_t),|T_t|, C(Tt),∣Tt∣,以及
g ( t ) = C ( t ) − C ( T t ) ∣ T t ∣ − 1 α = min ( α , g ( t ) ) g(t)=\frac{C(t)-C(T_t)}{|T_t|-1}\\ \alpha=\min(\alpha,g(t)) g(t)=∣Tt∣−1C(t)−C(Tt)α=min(α,g(t))
（4）對 g ( t ) = α g(t)=\alpha g(t)=α的内部節點t進行剪枝，并對葉子節點t以多數表決決定其類，得到樹T;
（5）設 k = k + 1 , α k = α , T k = T k=k+1,\alpha_k=\alpha,T_k=T k=k+1,αk=α,Tk=T;
（6）如果 T k T_k Tk不是由根節點及兩個葉子結點構成的樹，則傳回步驟二；否則令 T k = T n T_k=T_n Tk=Tn;
（7）采用交叉驗證法在子樹序列中選取最優子樹 T α T_\alpha Tα.
習題5.1(python實作）
該題代碼與5.3.2中寫的代碼相同，完整代碼如下：
from math import log
import operator
def calcShannonEnt(dataSet):
numEntries = len(dataSet)
labelCounts = {}
for featVec in dataSet:
currentLabel = featVec[-1]
if currentLabel not in labelCounts.keys():
labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1
shannonEnt = 0.0
for key in labelCounts:
prob = float(labelCounts[key]) / numEntries
shannonEnt -= prob * log(prob, 2)
return shannonEnt
def splitDataSet(dataSet, axis, value):
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value:
reducedFeatVec = featVec[:axis]
reducedFeatVec.extend(featVec[axis + 1:])
retDataSet.append(reducedFeatVec)
return retDataSet
def chooseBestFeatureToSplit(dataSet):
numFeatures = len(dataSet[0]) - 1
baseEntropy = calcShannonEnt(dataSet)
bestInfoGainRatio= 0.0
bestFeature = -1
for i in range(numFeatures):
featList = [example[i] for example in dataSet]
uniqueVals = set(featList)
newEntropy = 0.0
for value in uniqueVals:
subDataSet = splitDataSet(dataSet, i, value)
prob = len(subDataSet) / float(len(dataSet))
newEntropy += prob * calcShannonEnt(subDataSet)
infoGainRatio = (baseEntropy - newEntropy) / baseEntropy
if (infoGainRatio > bestInfoGainRatio):
bestInfoGainRatio = infoGainRatio
bestFeature = i
return bestFeature
def majorityCnt(classList):
classCount = {}
for vote in classList:
if vote not in classCount.keys():
classCount[vote] = 0
classCount[vote] += 1
sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
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
dataSet = [[1, 0, 0, 1, 0],
[1, 0, 0, 2, 0],
[1, 1, 0, 2, 1],
[1, 1, 1, 1, 1],
[1, 0, 0, 1, 0],
[2, 0, 0, 1, 0],
[2, 0, 0, 2, 0],
[2, 1, 1, 2, 1],
[2, 0, 1, 3, 1],
[2, 0, 1, 3, 1],
[3, 0, 1, 3, 1],
[3, 0, 1, 2, 1],
[3, 1, 0, 2, 1],
[3, 1, 0, 3, 1],
[3, 0, 0, 1, 0] ]
labels = ['age', 'job', 'house', 'creadit']
mytree = createTree(dataSet,labels)
print (mytree)
習題5.2(python實作）
import numpy as np
# 計算資料集的平方誤差
def calcMSE(dataSet):
means = np.mean(dataSet)
sums = sum([(i - means) * (i - means) for i in dataSet]) * 1.0
return sums
# 選擇最優的劃分點
def chooseBestFeatureToSplit(dataSet):
nums = len(dataSet) - 1
if nums == 0:
return 0
best = 0
bestMES = 100000
for i in range(nums):
temp = calcMSE(dataSet[:i + 1]) + calcMSE(dataSet[i + 1:])
if temp <= bestMES:
bestMES = temp
best = i
return best
# 建樹過程
def createTree(dataSet, datalabel, left, right):
if right - left == 1:
# return dataSet[left]
return datalabel[left]
if left >= right:
return -1
# 最優劃分函數加上left為原資料集上的最優劃分下标
bestchoose = left + chooseBestFeatureToSplit(dataSet[left:right])
# print bestchoose+1
mytree = {datalabel[bestchoose]: {}}
mytree[datalabel[bestchoose]]['left'] = createTree(dataSet, datalabel, left, bestchoose)
mytree[datalabel[bestchoose]]['right'] = createTree(dataSet, datalabel, bestchoose + 1, right)
return mytree
dataSet = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
datalabel = [4.5, 4.75, 4.91, 5.34, 5.8, 7.05, 7.9, 8.23, 8.7, 9]
mytree = createTree(dataSet,datalabel,0,len(dataSet))
print (mytree)
習題5.3
證明：CART剪枝算法中，當 α \alpha α确定時，存在唯一的最小子樹 T α T_\alpha Tα使損失函數 C α ( T ) C_\alpha(T) Cα(T)最小。
