決策樹一句話概括
通過信息增益屁使,采用遞歸的方式生成樹(找出最合適的節(jié)點順序以及葉子對應(yīng)的類標(biāo)簽)
舉個栗子: 是否買計算機
問題描述:已知1024個人的年齡隘梨、收入焕济、職業(yè)是否為學(xué)生萌壳、信譽是否良好及是否會有買計算機的行為澈蚌,若已知一個新人的年齡摹芙、收入等信息,請判斷該新人是否會買計算機宛瞄。
數(shù)學(xué)表達(dá):已知 1024 個樣本的特征向量 ( x(1), x(2), x(4), x(4)) 和預(yù)測值Y以及新樣本的特征向量浮禾,計算新樣本預(yù)測值Y。
如圖所示:
人數(shù) 年齡 收入 是否學(xué)生 信譽 標(biāo)簽:是否買計算機 64 青 高 否 良 不買 64 青 高 否 優(yōu) 不買 128 中 高 否 良 買 60 老 中 否 良 買 64 老 低 是 良 買 64 老 低 是 優(yōu) 不買 64 中 低 是 優(yōu) 買 128 青 中 否 良 不買 64 青 低 是 良 買 132 老 中 是 良 買 64 青 中 是 優(yōu) 買 32 中 中 否 優(yōu) 買 32 中 高 是 良 買 63 老 中 否 優(yōu) 不買 1 老 中 否 優(yōu) 買 新樣本 青 低 否 良 份汗?
- 總?cè)藬?shù):1024
買的人數(shù):641
不買的人數(shù):383 - 青年:384
青年中買的人數(shù):128
青年中不買的人數(shù):256 - 中年:256
中年買:256
中年不買: 0 - 老年: 252
老年買: 125
老年不買: 127 - 學(xué)生:略
- 非學(xué)生: 略
決策樹步驟
一盈电、總覽
def createBranch():
#判斷邊界
if 數(shù)據(jù)集中的每個子項是否屬于同一分類(是):
return 類標(biāo)簽(葉子)
#遞歸生成樹
else:
尋找劃分?jǐn)?shù)據(jù)集的最好特征
劃分?jǐn)?shù)據(jù)集
創(chuàng)建分支結(jié)點
for 每個劃分的子集:
createBranch()
return 分支結(jié)點
二、尋找劃分?jǐn)?shù)據(jù)集的最好特征
ID3:信息增益
C4.5:信息增益率
CART:基尼系數(shù)
三杯活、具體過程——以ID3算法為例
- 基本數(shù)學(xué)符號:
m 個樣本 —— m 個人
n 個特征向量 ( X(1), X(2), ... , X(n)) —— ( X(1), X(2), X(4), X(4) )
預(yù)測值 { Y1, Y2, ..., Yk } —— { Y1: 買, Y2: 不買 }
新樣本X = ( x(1), x(2), ... , x(n)) —— 新人X= ( x(1), x(2), x(3), x(4) )
- 概率計算
X 為買時概率為:
p(Y_1) = 641 / 1024
不買時概率為:
p(Y_2) = 383 / 1024
X在年齡為青年的條件下買電腦的概率為 :
p(Y_1|youth) = 128 / 384
X在年齡為青年的條件下不買電腦的概率為:
p(Y_2|youth) = 256 / 384
X在年齡為中年的條件下買電腦的概率為:
p(Y_1|middle) = 256 / 256
X在年齡為中年的條件下不買電腦的概率為:
p(Y_2|middle) = 0 / 256
X在年齡為老年的條件下買電腦的概率為:
p(Y_1|old) = 125 / 252
X在年齡為老年的條件下不買電腦的概率為:
p(Y_2|old) = 127 / 252
- 尋找劃分?jǐn)?shù)據(jù)集的最好特征——信息增益
信息熵的大小指的是了解一件事情所需要付出的信息量是多少匆帚,這件事的不確定性越大,要搞清它所需要的信息量也就越大旁钧,也就是它的信息熵越大吸重,信息熵:
H(Y) = -\sum_{i=1}^{i=k}{p(Y_i)log_2(Y_i)}= -p(Y_1)log_2(p(Y_1))-p(Y_2)log_2(p(Y_2)) = 0.9537
條件熵:
H(Y|age) = p(youth)H(Y|youth) + p(middle)H(Y|middle) + p(old)H(Y|old)=0.6877
其中:
H(Y|youth) = -\sum_{i=1}^{i=k}{p(Y_i|youth)}log_2(p(Y_i|youth)) = p(Y_1|youth)log_2(p(Y_1|youth)+p(Y_2|youth)log_2(p(Y_2|youth) = 0.9183
H(Y|middle) = 0
H(Y|old) = 0.9157
信息增益:
IG(age) = H(Y) - H(Y|age) = 0.9537 - 0.6877 = 0.2660
同理:
IG(income) = H(Y) - H(Y|income) = 0.0176
IG(Student) = H(Y) - H(Y|Student) = 0.01726
IG(credit) = H(Y) - H(Y|credit) = 0.0453
- 劃分?jǐn)?shù)據(jù)集,創(chuàng)建分支節(jié)點
年齡的信息增益最大歪今,因此第一個結(jié)點為年齡嚎幸,即:
將樣本劃分為青年、中年和老年三個數(shù)據(jù)集彤委,在青年這個數(shù)據(jù)集中:
H(youth) = H(Y|youth)= 0.9183
IG(income)= H(youth) - H(youth|income)
IG(student)= H(youth) - H(youth|student)
IG(credit) = H(youth) - H(youth|redit)
其中是否為學(xué)生的信息增益最大鞭铆,因此選擇是否為學(xué)生作為青年集的結(jié)點,將青年數(shù)據(jù)集劃分為學(xué)生集與非學(xué)生集,即:
在中年這個數(shù)據(jù)集中车遂,所有人都會買電腦凤薛,屬于同一個類別牺氨,返回類標(biāo)簽即可:
在老年這個數(shù)據(jù)集中,信譽的增益最大,因此選擇將信譽作為老年集的結(jié)點究恤,將其劃分為優(yōu)信譽集與良信譽集,即:
最終生成的決策樹:略
四财饥、補充
剪枝處理
- 預(yù)剪枝
- 后剪枝
連續(xù)與缺失值
連續(xù)值
缺失值
待更新
參考:
《機器學(xué)習(xí)實戰(zhàn)》【美】Peter Harrington