1. 決策
我理解的決策就是根據(jù)當前已有的條件喷舀，得出一個結果。
如以下這個簡單的例子：
| ID | Leg | Color | Bite | Type |
|---|---|---|---|---|
| 1 | short | yellow | yes | cat |
| 2 | long | black | yes | cat |
| 3 | long | yellow | yes | cat |
| 4 | short | yellow | no | cat |
| -1 | long | yellow | no | dog |
| -2 | short | white | yes | dog |
| -3 | long | white | yes | dog |
| -4 | long | white | no | dog |
| -5 | short | black | no | dog |
以上這個也叫做決策表淋肾。通過 腿長硫麻，顏色，是否咬人 來判斷是 貓 還是 狗樊卓。
2. 決策樹
我們可以將以上的表格轉換成一棵樹：
每次決策的時候從根節(jié)點出發(fā)拿愧，根據(jù)屬性值選擇子樹，直到葉子節(jié)點就是一個決策碌尔。
3. ID3算法
構建樹的時候浇辜，把哪個屬性放在根節(jié)點，哪個屬性放在第二層節(jié)點唾戚，就值得我們思考了柳洋。可以預想到叹坦，根據(jù)不同的順序熊镣，構建出來的決策樹的構造可能是不一樣的。如果樹中的節(jié)點越少募书，那么平均每次決策所需要的判斷次數(shù)也就越少绪囱，算法的效率就越高。
ID3算法就是為了構造出一棵較優(yōu)的（注意莹捡，不一定最優(yōu)）的樹鬼吵，使得每次決策的平均判斷次數(shù)更少。
3.1 信息熵
在高中學過篮赢，熵 表示一個系統(tǒng)的無序程度齿椅。比如剛整理好的房間的熵值就比你住過兩周不收拾以后的房間的熵值要小。
而 信息熵 是類似的启泣，其定義為離散隨機事件出現(xiàn)的概率媒咳，一個系統(tǒng)越是有序，信息熵就越低种远，反之一個系統(tǒng)越是混亂，它的信息熵就越高顽耳。
假設一個隨機變量 的取值為
坠敷，每一種取到的概率為
妙同，那么
的熵值為：
注意，雖然前面有個負號膝迎，但是熵值是正的粥帚。
以上面的決策為例，限次，其概率分別是
，那么其熵值為：
3.2 條件熵
還是以上的例子卖漫，如果把所有的樣本僅按照 Leg 進行分類的話费尽，可以分成兩類：
分別計算熵值，可得：
因此羊始，劃分后的熵值為：
因此信息增益為：
3.3 ID3 算法
ID3 算法就是找出信息增益最大的屬性旱幼，然后將其當成根節(jié)點，然后對于由此劃分得到的子數(shù)據(jù)突委，重復以上的步驟柏卤。
同樣的方法計算 Color 屬性的信息增益：
再算Bite 屬性的信息增益：
很明顯，Color 屬性以絕對的優(yōu)勢勝出匀油，當選根節(jié)點缘缚。
于是數(shù)據(jù)被 Color 分成了三部分，對每一部分數(shù)據(jù) 敌蚜，去除 Color 屬性的影響桥滨，按以上的方法遞歸生成決策樹，這里就不贅述了钝侠。
但是ID3算法的缺點是很明顯的（雖然我自己不覺得明顯该园，但是書上都這么說）：
-
ID3算法不能處理連續(xù)的數(shù)據(jù)
這個很好理解，假設有一個屬性是精確到小數(shù)點后三位的體重值帅韧，那么可能所有樣本的值都不一樣里初，則該屬性的信息增益最大。ID3算法就會僅使用該屬性忽舟，把每個樣本都分到單獨的一類中双妨。即，反正體重都不一樣叮阅，那根據(jù)體重來判斷就完事了~
-
ID3算法傾向于選擇取值較多的屬性
信息增益反映的給定一個條件以后不確定性減少的程度刁品，必然是分得越細的數(shù)據(jù)集確定性更高，也就是條件熵越小浩姥，信息增益越大挑随。
4. C4.5算法
為了克服 “ID3算法傾向于選擇取值較多的屬性” 的缺點志群，C.45算法使用了信息增益率來代替信息增益笛园。其思想就是库继，增加一個懲罰葬燎，取值越多的屬性懲罰越大，以此來平衡其選擇拌汇。
如果使用C.45的話柒桑，上面的公式就變成：
復習一下， 就是將樣本按照屬性
Leg 劃分以后的信息熵噪舀。
可以得到：
同樣的方法計算 Color 屬性的信息增益率：
再算Bite 屬性的信息增益率：
可以看到魁淳，雖然還是 Color 屬性的信息增益率最高，但是值已經(jīng)被壓縮了与倡，而另外兩個屬性的值得到了小幅度的上升界逛，各個屬性之間的差異更小了。
5. CART 算法
上述兩個算法生成的樹中蒸走，一個節(jié)點有幾個子節(jié)點取決于該屬性的取值數(shù)量仇奶，而CART算法生成的則是二叉樹。
Chart算法則使用了一個叫做 Gini系數(shù) 的東西比驻，假設一個隨機變量 的取值為
该溯，每一種取到的概率為
，那么
的為：
如果根據(jù)屬性 把數(shù)據(jù)
劃分為
别惦，則：
則Gini系數(shù)增益為：
按照慣例狈茉，使用上面的例子計算一下：
首先算出整個數(shù)據(jù)集的 Gini 系數(shù)：
對于 Leg 屬性：
對于 Color 屬性，就比較麻煩了掸掸，因為有三個取值氯庆，但是CART生成的是二叉樹，因此就會有三種情況扰付。
- case 1：
- case 2：
- case 3：
對于 Bite 屬性：
可以看出堤撵，當根節(jié)點為 Color 屬性并且左邊是 white，右邊是 yellow & black 時羽莺，Gini系數(shù)增益最大实昨。
