一副签、決策樹簡介
在介紹決策樹之前，先了解一下決策樹的處理流程基矮。如下圖所示淆储，有三個屬性值，分別為Outlook家浇、Humidity本砰、Wind，對應(yīng)的最終分類為Yes和No钢悲。當(dāng)一條新數(shù)據(jù)過來時点额，根據(jù)新數(shù)據(jù)中Outlook舔株、Humidity和Wind就能確定該數(shù)據(jù)的輸出結(jié)果是Yes還是No。而Outlook还棱、Humidity载慈、Wind這三個屬性值的選擇，需要從已標(biāo)記好的訓(xùn)練數(shù)據(jù)集中選擇珍手。
二办铡、構(gòu)建決策樹
決策樹是一層層構(gòu)建的，在每一層就要選擇一個屬性琳要，然后根據(jù)它的屬性值將數(shù)據(jù)集進(jìn)行分裂寡具。如何選擇屬性作為節(jié)點(diǎn)以測試實(shí)例是最為關(guān)鍵的一步。不同的算法采取了不同的方法稚补，主要的決策樹算法有這樣幾個：
- ID3
- C4.5 （數(shù)據(jù)挖掘十大算法之一童叠，也是ID3算法的改進(jìn)）
- C5.0 （C4.5的改進(jìn)，適用于處理大數(shù)據(jù)集课幕，采用Boosting方式提高模型準(zhǔn)確率拯钻，因而又稱BoostingTrees。）
- CART（數(shù)據(jù)挖掘十大算法之一）
三撰豺、ID3
ID3算法的核心就是要選取分類能力最好的屬性粪般，那么怎么去確定哪個屬性是分類能力最好的呢？ID3算法中污桦，使用信息增益作為評判標(biāo)準(zhǔn)亩歹。
1. 信息熵
信息熵又稱為香農(nóng)熵，簡稱熵凡橱。信息熵簡單說就是信息不確定性的大小小作。
若用xi，i=1,2,…,n來表示數(shù)據(jù)集所包含的分類結(jié)果稼钩，那么這個數(shù)據(jù)集的熵為：
其中顾稀，p(xi)表示選取xi作為分類的最終類別的概率；l(xi)為xi的信息坝撑，定義為：l(xi)=?log2p(xi)
2. 信息增益
簡單來說静秆，一個屬性的信息增益就是：使用這個屬性分割樣例集合進(jìn)一步導(dǎo)致熵值降低。那么要選取分類能力最好的屬性巡李，就是要選取使得信息增益最大的那個屬性抚笔。
假設(shè)數(shù)據(jù)集D，按照屬性A將數(shù)據(jù)進(jìn)行分割侨拦，分割成v類殊橙，則分割后的信息熵為：
其中|D|為樣本的總數(shù)，|Dj|為A屬性值為j類的總樣本數(shù)，info(Dj)為以Dj為數(shù)據(jù)集的信息熵膨蛮，顧名思義叠纹，就是樣本數(shù)據(jù)集D按照屬性A進(jìn)行分割成V類，將所有類別的信息熵求和敞葛，即可誉察。那么數(shù)據(jù)集D按照A屬性進(jìn)行分割后的信息增益為：
依次計(jì)算數(shù)據(jù)D按照各個屬性的分割后的信息增益，選擇信息增益最大的作為分割屬性制肮，依次進(jìn)行冒窍。
3. 簡單例子
4. 信息增益的理解
一般說來递沪，對于一個具有多個屬性的元組豺鼻，用一個屬性就將它們完全分開幾乎不可能，否則的話款慨，決策樹的深度就只能是2了儒飒。從這里可以看出，一旦我們選擇一個屬性A檩奠，假設(shè)將元組分成了兩個部分A1和A2桩了，由于A1和A2還可以用其它屬性接著再分，所以又引出一個新的問題：接下來我們要選擇哪個屬性來分類埠戳？對D中元組分類所需的期望信息(信息熵)是Info(D) ,那么同理井誉，當(dāng)我們通過A將D劃分成v個子集Dj(j=1,2,…,v)之后，我們要對Dj的元組進(jìn)行分類整胃，需要的期望信息就是Info(Dj),而一共有v個類颗圣，所以對v個集合再分類，需要的信息就是公式（2）了屁使。由此可知在岂，如果公式（2）越小，是不是意味著我們接下來對A分出來的幾個集合再進(jìn)行分類所需要的信息就越新拧蔽午？而對于給定的訓(xùn)練集，實(shí)際上Info(D)已經(jīng)固定了酬蹋，所以選擇信息增益最大的屬性作為分裂點(diǎn)及老。
但是，使用信息增益的話其實(shí)是有一個缺點(diǎn)范抓，那就是它偏向于具有大量值的屬性写半。什么意思呢？就是說在訓(xùn)練集中尉咕，某個屬性所取的不同值的個數(shù)越多叠蝇，那么越有可能拿它來作為分裂屬性。例如一個訓(xùn)練集中有10個元組，對于某一個屬相A悔捶，它分別取1-10這十個數(shù)铃慷，如果對A進(jìn)行分裂將會分成10個類，那么對于每一個類Info(Dj)=0蜕该，從而式（2）為0犁柜，該屬性劃分所得到的信息增益（3）最大，但是很顯然堂淡，這種劃分沒有意義
