一. 背景
1. 適合決策樹應(yīng)用的三個條件
- 訓(xùn)練數(shù)據(jù)記錄形式是attr-value pairs
- 數(shù)據(jù)質(zhì)量: 數(shù)據(jù)可能可能有缺失的值, 有噪音
- 離散型: 目標(biāo)函數(shù)y, 以及特征屬性字段都是離散類型; 如果是數(shù)值型變量, 也可以轉(zhuǎn)化成分類變量
2. 實際應(yīng)用
決策樹生成的if-then規(guī)則容易被人理解, 是一種非常清晰明了的知識. 很多情況下被用來做expert system. 很典型的一個例子是醫(yī)學(xué)上的診斷: 依據(jù)患者的p個癥狀, 給出其屬于哪個類型病癥(離散型)的答案.
3. 算法分類
ID3, 最早的實用算法.
當(dāng)下最常用的: C4.5, C5.0
二. 決策樹的基本
1. 樹的結(jié)構(gòu)
葉子層, 規(guī)則的結(jié)論; 內(nèi)層, 代表一個判斷結(jié)點.
順著一條鏈路下來是conjunction(&&合取關(guān)系), 而同層次之間是disjunction(||析取關(guān)系)的關(guān)系
2. 注意事項
必須把屬性字段收集好, 如果缺失了關(guān)鍵字段, 可能導(dǎo)致做不出一棵比較實用的決策樹.
同樣一批數(shù)據(jù), 可能有不同的正確的決策樹.
奧卡姆剃刀: 簡單的樹更好. 這是因為簡單的樹, 更能抓住一些容易泛化的關(guān)鍵屬性, 通用能力更好, 實用性比較好.
3. 結(jié)點分裂算法
1 A = the best decision attr for next node //tricky part, how to get the best attr? use entropy!!
2 Assign A as decision attr for node
3 For each value of A, create new descendant of node
4 sorting traninng example to leaf nodes
5 if trainnning examples perfectly classified: //all records in a node are in the same category
stop
else:
iterate over new leaf nodes
三. ID3: 使用信息增益info gain分裂結(jié)點
1. 定義
info gain: how well a given attr separates the training examples according to their target classfication
entropy: purty of a Node, 取值總是正數(shù), 越高代表混亂度越大.
Ent(x) = - Σ pi log pi
note: 可以觀察到, pi∈[0, 1], 因此log(pi) <= 0, 所以必須在Σ前面加上負(fù)號, 把取值變成正.
2. 如何計算信息熵
我們找信息增益最大(使得信息熵下降最大的)屬性字段.
某個字段的信息增益 = 沒選這個字段前的信息熵(baseEntropy) - 選了之后的信息熵(newEntropy)
#計算InfoGain的過程
S = [9+, 5-], //S: Sample Set
Value(Wind) = { Weak, Strong } //Unique value set of attribute 'Wind'
Sweak = [6+, 2-] //Samples belongs to 'weak'
Sstrong = [3+, 3-] //Samples belongs to 'strong'
Gain(S;A) = Entropy(S)-(8/14) Entropy(Sweak )-(6/14)Entropy(SStrong ) //記得要寫8/14, 6/14, 這代表的是每個部分的weight. 所以, 第一個weight是依據(jù)結(jié)點的UniqueValue
=[ -(9/14)log(9/14) - (5/14)log(5/14) ] - { (8/14)[ -(6/8)log(6/8) - (2/8)log(2/8) ] } - { (3/6)[ -(3/6)log(3/6) - (3/6)log(3/6) ] }
= 0.940 – (8/14)0.811 – (6/14)1.00
= 0.048
//weight ? [ -p1?log(p1) - p2?log(p2) ] 第二個p1, p2等值, 是依據(jù)cate類在本結(jié)點樣本(Sweak比如)上的占比
Python代碼
def calcShannonEntropy(dataset):
"""Calcuate Shannon Entropy value for a list-form dataset
:param dataset: a list of vectors, with vec[-1] as each 's category
note: cate = category
"""
num = len(dataset)
cateCount = {}
for vec in dataset:
curCate = vec[-1]
if curCate not in cateCount.keys():
cateCount[curCate] = 0 #create a new entry
cateCount[curCate] += 1
entropy = 0.0
for key in cateCount.keys():
prob = cateCount[key]/num
entropy -= prob * log(prob,2)
return entropy
3. 如何分裂結(jié)點
分裂結(jié)點的時候, 我們要做的事, 就是選取出那個使得InfoGain最大, 換句話說使得newEntropy最小的字段bestFeatureName
def splitDataset(dataset, axis, value):
"""Split a dataset by a selected feature.
This will delete the feature in the returnDataset.
:param dataset: a list of vectors. Each vector is also a list.
:param axis: a chosen feature to split.
:param value: the chosen value for return dataset.
vector with other value will not be in the returnDataset
"""
retDataset = [];
for vec in dataset:
if vec[axis]==value:
retVec = vec[:axis]
retVec.extend(vec[axis+1:]) #extend a list with another list
retDataset.append(retVec)
return retDataset #returnDataset
#選取出infoGain最大的feature
def chooseBestSplitFeature(dataset):
p = len(dataset[0])-1 #number of properties
minEntropy = calcShannonEntropy(dataset)
bestFeature = -99
for i in range(p): #compute each feature's result entropy
feaList = [vec[i] for vec in dataset] #tricky! get a whole column
uniqueFeaSet = set(feaList)
newEntropy = 0.0
for value in uniqueFeaSet:
aDataset = splitDataset(dataset, i, value)
prob = len(aDataset)/len(dataset)
newEntropy += prob*calcShannonEntropy(aDataset) #別忘了要乘上prob
if newEntropy < minEntropy:
minEntropy = newEntropy
bestFeature = i
if bestFeature == -99:
print('bestFeature not chosen!!!')
return bestFeature #返回feature的index, 比如2
4. ID3算法偽代碼與實現(xiàn)
Python
#投票法得出某個葉子節(jié)點的最終category
def getMajority(classList):
'''input: a list of class of this node, typically a leaf'''
classCount = {}
for vote in classList: #class關(guān)鍵字得替換成vote, 因為python保留了這個關(guān)鍵字
if vote not in classCount: classCount[vote] = 0
classCount[vote] += 1
aList = list(classCount.items())
sortedClassCount = sorted(aList, key=lambda x:x[1], reverse=True) #key=!
return sortedClassCount[0][0]
#給定list類型的dataset和feats, 創(chuàng)建一棵DecisionTree
def createTree(dataset, feats):
localfeats = list(feats)
classList = [row[-1] for row in dataset]
if classList.count(classList[0])==len(classList):
return classList[0] #return a label as it reaches purity
if len(dataset[0])==1: #no feature left
return getMajority(classList)
#chooseFeature
bestFeat = chooseBestSplitFeature(dataset)
bestFeatKey = localfeats[bestFeat]
del(localfeats[bestFeat]) #delete bestFeat from feats
print('bestFeatureName:',bestFeatKey)
#save the tree
aTree = {bestFeatKey:{}}
#split, create tree for each childnode
uniqueVals = set([row[bestFeat] for row in dataset])
for val in uniqueVals:
subFeats = localfeats[:]
childDataset = splitDataset(dataset, bestFeat, val)
aTree[bestFeatKey][val] = createTree(childDataset, subFeats)
return aTree
4. 從模型空間的角度來評價ID3算法
Hypo space is complete: target function surely in there. 模型假設(shè)的空間是完整的, 因此目標(biāo)函數(shù)(函數(shù)和模型在這里是同義詞)肯定在里面.
Robust to noisy data: statistically based search choices. 統(tǒng)計方法, 因此對噪聲抵御能力較強(qiáng)
No back tracking: local minima. 沒有回朔的手段, 因此可能陷入局部最優(yōu)
inductive bias: the shorter, the better. 喜歡最短的決策樹路徑, 這個是出于實用的考量, 但是卻不一定能得到最"精準(zhǔn)"的決策樹.
note: Restriction Biases & Preferences Biases
Preference bias is more desirable than Restriction biases. Restriction Biases直接把目標(biāo)函數(shù)給排除在了模型空間(Hypothesis Space)之外, 而PreferenceBias是算法使用者的一種傾向性, 比如在決策樹中, 算法使用者傾向使用短一些的決策樹, 這樣可以避免過擬合, 同時也容易理解一些.
一般我們認(rèn)為保留選擇給算法使用者是比較好的.
5. 數(shù)據(jù)的預(yù)先處理
1. 離散化方法
無監(jiān)督(用的多): 等長(從0~100劃分成5個bin), 定數(shù)量(每五個一類)
有監(jiān)督: 人為地, 借助標(biāo)簽地分開數(shù)據(jù). 比如看到45歲前沒什么得心臟病, 45歲后很多人得了, 人為地設(shè)定為分為"年輕人", "老年人"兩段.
2. 數(shù)據(jù)的缺失處理
離散型: 選取最頻繁出現(xiàn)的值(眾數(shù))來代替, 或者寫上缺失, 或者干脆刪除這個屬性(如果缺的太厲害)
6. 過擬合
解決辦法: prun 剪枝
tree size = 一個凸起的函數(shù). 要試圖接近最好的點
forward pruning
Orange框架中的規(guī)則: (Orange是一個實現(xiàn)了決策樹的框架)
如果結(jié)點上只有五個example就停止
如果發(fā)現(xiàn)這個結(jié)點有10個樣例, 有至少7個都已經(jīng)是一類(+/-), 那么可以停了
如果分支下去的兩個葉子中, 有一個只有一個或者兩個例子, 那么表示太具體了, 應(yīng)該剪掉葉子
backward pruning
原理和forward類似, 但是會更好用一些.
三. 使用信息增益率改進(jìn): c4.5算法
1. ID3算法存在的嚴(yán)重問題: 特征取值越多越容易被選取
極端的例子是用戶id, date這種取值極其多的屬性, 這樣屬性的每個獨特取值下, 都只有一個y的類別.
這樣, id, date這種字段的熵就等于0. 因此, 決策樹傾向于直接選取這些取值多的字段作為分裂結(jié)點.
而這樣在實際業(yè)務(wù)中幾乎沒有用的.
2. InfoGain解決特征取值過多問題
C4.5引入了一個SplitInfo的分母來降低取值多的字段的InfoGain.
已知, InfoGain = Ent(S) - Ent(S ; A)
當(dāng)遇到取值很多的字段的時候, Ent(S; A)急劇下降, 趨近于0. 那么, 我們可以對InfoGain整個值進(jìn)行縮小, 來緩解這種問題.
我們選用的是SplitInfo(S, A) = –Σpm?logpm, 其中pm = 字段取某個獨特值的時候, 所擁有的樣本數(shù) ÷ 總的樣本數(shù)(到達(dá)這個分裂結(jié)點的樣本數(shù))
比如Temp = {cold: 5, normal: 10, hot: 8}
SplitInfo = -5/23?lg5/23 - 10/23?lg10/23 - 8/23?lg8/23
顯然, 我們可以看出, 如果一個字段屬性下, 獨特的取值越多的話, 它的熵SplitInfo的值會越大. 由于SplitInfo被放在了分母的位置, 因此獨特取值越多的字段, 會分到一個越小的權(quán)重.
GainRatio(S, A) = Gain(S, A) / SplitInfo(S, A)
3. C4.5算法偽代碼
1 Check for the above base cases. //邊界條件檢查
2 For each attribute a, find the normalized information gain ratio from splitting on a.
3 Let a_best be the attribute with the highest normalized information gain.
4 Create a decision node that splits on a_best.
5 Recur on the sublists obtained by splitting on a_best, and add those nodes as children of node.
四. 最后: 決策樹的評價
評價: 算法原理? 什么時候用? 優(yōu)缺點?
1. 優(yōu)點
健壯性: 統(tǒng)計方法決定了決策樹抗噪聲.
結(jié)果容易被理解: 在醫(yī)療等領(lǐng)域應(yīng)用十分適合, 因為我們需要理解原因.
決策樹的這些優(yōu)點決定了它是一個簡單易用的機(jī)器學(xué)習(xí)方法.
2. 缺點
如果使用C4.5算法, 克服了某個特征屬性下獨特取值過多的問題后,
決策樹模型還是可能存在問題:
no backtracking: local optimal solution not global optimal solution 即無法回朔, 可能無法得到全局最優(yōu)
3. overall
- practical 決策樹是一個簡單又實用的機(jī)器學(xué)習(xí)方法
- overfitting problem: 是做決策樹的時候需要解決的問題;
- id3 searches the whole tree with inductive bias for smaller tree "id3"算法存在著對較小決策樹的偏好.
- 由于決策樹應(yīng)用很多, 因此其的實用算法中會有很多很多的改進(jìn)變種.
遺留一個問題供思考
如果樹的結(jié)點順序的不同, 結(jié)果會有不同嗎?
參考資料
信息增益與信息增益率詳解
c4.5為什么使用信息增益比來選擇特征?
<機(jī)器學(xué)習(xí)實戰(zhàn)> page42
