決策樹一句話概括

通過信息增益，采用遞歸的方式生成樹（找出最合適的節(jié)點(diǎn)順序以及葉子對(duì)應(yīng)的類標(biāo)簽）

舉個(gè)栗子: 是否買計(jì)算機(jī)

問題描述：已知1024個(gè)人的年齡、收入、職業(yè)是否為學(xué)生、信譽(yù)是否良好及是否會(huì)有買計(jì)算機(jī)的行為，若已知一個(gè)新人的年齡、收入等信息，請(qǐng)判斷該新人是否會(huì)買計(jì)算機(jī)。

數(shù)學(xué)表達(dá)：已知 1024 個(gè)樣本的特征向量 ( x⁽¹⁾, x⁽²⁾, x⁽⁴⁾, x⁽⁴⁾) 和預(yù)測(cè)值Y以及新樣本的特征向量，計(jì)算新樣本預(yù)測(cè)值Y。

如圖所示：

人數(shù)	年齡	收入	是否學(xué)生	信譽(yù)	標(biāo)簽：是否買計(jì)算機(jī)
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ù)集中的每個(gè)子項(xiàng)是否屬于同一分類(是):
        return 類標(biāo)簽(葉子)    
    #遞歸生成樹
    else：
        尋找劃分?jǐn)?shù)據(jù)集的最好特征         
        劃分?jǐn)?shù)據(jù)集                  
        創(chuàng)建分支結(jié)點(diǎn)    
            for 每個(gè)劃分的子集：    
                createBranch()    
            return 分支結(jié)點(diǎn)

二、尋找劃分?jǐn)?shù)據(jù)集的最好特征

ID3：信息增益

C4.5：信息增益率

CART：基尼系數(shù)

三、具體過程——以ID3算法為例

• 基本數(shù)學(xué)符號(hào)：

m 個(gè)樣本 —— m 個(gè)人

n 個(gè)特征向量 ( X⁽¹⁾, X⁽²⁾, ... , X⁽ⁿ⁾) —— ( X⁽¹⁾, X⁽²⁾, X⁽⁴⁾, X⁽⁴⁾ )

預(yù)測(cè)值 { Y₁, Y₂, ..., Y_k } —— { Y₁: 買, Y₂: 不買 }

新樣本X = ( x⁽¹⁾, x⁽²⁾, ... , x⁽ⁿ⁾) —— 新人X= ( x⁽¹⁾, x⁽²⁾, x⁽³⁾, x⁽⁴⁾ )

• 概率計(jì)算

X 為買時(shí)概率為：
p(Y_1) = 641 / 1024

不買時(shí)概率為：
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é)點(diǎn)

年齡的信息增益最大，因此第一個(gè)結(jié)點(diǎn)為年齡，即：

IG(income)= H(youth) - H(youth|income)

IG(student)= H(youth) - H(youth|student)

IG(credit) = H(youth) - H(youth|redit)

其中是否為學(xué)生的信息增益最大，因此選擇是否為學(xué)生作為青年集的結(jié)點(diǎn)，將青年數(shù)據(jù)集劃分為學(xué)生集與非學(xué)生集，即：

在中年這個(gè)數(shù)據(jù)集中，所有人都會(huì)買電腦，屬于同一個(gè)類別，返回類標(biāo)簽即可：

最終生成的決策樹：略

四、補(bǔ)充

剪枝處理

• 預(yù)剪枝
• 后剪枝

連續(xù)與缺失值

• 連續(xù)值

• 缺失值

• 待更新

參考：
《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》【美】Peter Harrington