決策樹一句話概括
通過信息增益屁使，采用遞歸的方式生成樹（找出最合適的節(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
