數(shù)據(jù)挖掘十大算法之決策樹詳解（2）

ID3算法

ID3和C4.5都是由澳大利亞計(jì)算機(jī)科學(xué)家Ross Quinlan開發(fā)的決策樹構(gòu)建算法，其中C4.5是在ID3上發(fā)展而來的。

ID3算法的核心是在決策樹各個(gè)結(jié)點(diǎn)上應(yīng)用信息增益準(zhǔn)則選擇特征，遞歸地構(gòu)建決策樹。具體方法是：從根結(jié)點(diǎn)（root node）開始，對(duì)結(jié)點(diǎn)計(jì)算所有可能的特征的信息增益，選擇信息增益最大的特征作為結(jié)點(diǎn)的特征，由該特征的不同取值建立子結(jié)點(diǎn)；再對(duì)子結(jié)點(diǎn)遞歸地調(diào)用以上方法，構(gòu)建決策樹；直到所有特征的信息增益均很小或沒有特征可以選擇為止。最后得到一棵決策樹。ID3相當(dāng)于用極大似然法進(jìn)行概率模型的選擇。 下面我們給出一個(gè)更加正式的ID3算法的描述：

輸入：訓(xùn)練數(shù)據(jù)集D，特征集A，閾值?； 
輸出：決策樹T。

若D中所有實(shí)例屬于同一類Ck，則T為單結(jié)點(diǎn)樹，并將類Ck作為該結(jié)點(diǎn)的類標(biāo)記，返回T；

若A=?，則T為單結(jié)點(diǎn)樹，并將D中實(shí)例數(shù)最大的類Ck作為該結(jié)點(diǎn)的類標(biāo)記，返回T;

否則，計(jì)算A中各特征對(duì)D的信息增益，選擇信息增益最大的特征Ag；

(1) 如果Ag的信息增益小于閾值?，則置T為單結(jié)點(diǎn)樹，并將D中實(shí)例數(shù)最大的類Ck作為該結(jié)點(diǎn)的類標(biāo)記，返回T；

(2) 否則，對(duì)Ag的每一可能值ai，依Ag=ai將D分割為若干非空子集Di，將Di中實(shí)例數(shù)最大的類作為標(biāo)記，構(gòu)建子結(jié)點(diǎn)，由結(jié)點(diǎn)及其子結(jié)點(diǎn)構(gòu)成樹T，返回T；

對(duì)第i個(gè)子結(jié)點(diǎn)，以Di為訓(xùn)練集，以A?{Ag}為特征集，遞歸地調(diào)用步驟(1)~(3)，得到子樹Ti，返回Ti。

下面我們來看一個(gè)具體的例子，我們的任務(wù)是根據(jù)天氣情況計(jì)劃是否要外出打球： 

首先來算一下根節(jié)點(diǎn)的熵： 

然后再分別計(jì)算每一種劃分的信息熵，比方說我們選擇Outlook這個(gè)特征來做劃分，那么得到的信息熵為

據(jù)此可計(jì)算采用Outlook這個(gè)特征來做劃分時(shí)的信息增益為 

同理，選用其他劃分時(shí)所得到之信息增益如下： 

取其中具有最大信息增益的特征來作為劃分的標(biāo)準(zhǔn)，然后你會(huì)發(fā)現(xiàn)其中一個(gè)分支的熵為零（時(shí)間中閾值可以設(shè)定來懲罰過擬合），所以把它變成葉子，即得 

對(duì)于其他熵不為零（或者大于預(yù)先設(shè)定的閾值）的分支，那么則需要做進(jìn)一步的劃分 

根據(jù)上述的規(guī)則繼續(xù)遞歸地執(zhí)行下去。最終，我們得到了如下一棵決策樹。 

C4.5算法

C4.5是2006年國際數(shù)據(jù)挖掘大會(huì)票選出來的十大數(shù)據(jù)挖掘算法之首，可見它應(yīng)該是非常powerful的！不僅如此，事實(shí)上，C4.5的執(zhí)行也相當(dāng)?shù)膕traightforward。

C4.5算法與ID3算法相似，C4.5算法是由ID3算法演進(jìn)而來的。C4.5在生成的過程中，用信息增益比來選擇特征。下面我們給出一個(gè)更加正式的C4.5算法的描述：

輸入：訓(xùn)練數(shù)據(jù)集D，特征集A，閾值?； 
輸出：決策樹T。

如果D中所有實(shí)例屬于同一類Ck，則置T為單結(jié)點(diǎn)樹，并將Ck作為該結(jié)點(diǎn)的類，返回T；

如果A=?，則置T為單結(jié)點(diǎn)樹，并將D中實(shí)例數(shù)最大的類Ck作為該結(jié)點(diǎn)的類，返回T；

否則，計(jì)算A中各特征對(duì)D的信息增益比，選擇信息增益比最大的特征Ag；

(1) 如果Ag的信息增益比小于閾值?，則置T為單結(jié)點(diǎn)樹，并將D中實(shí)例數(shù)最大的類Ck作為該結(jié)點(diǎn)的類，返回T；

(2) 否則，對(duì)Ag的每一可能值ai，依Ag=ai將D分割為若干非空子集Di，將Di中實(shí)例數(shù)最大的類作為標(biāo)記，構(gòu)建子結(jié)點(diǎn)，由結(jié)點(diǎn)及其子結(jié)點(diǎn)構(gòu)成樹T，返回T；

對(duì)結(jié)點(diǎn)i，以Di為訓(xùn)練集，以A?{Ag}為特征集，遞歸地調(diào)用步驟(1)~(3)，得到子樹Ti，返回Ti。

How to do it in practice?

易見，C4.5跟ID3的執(zhí)行步驟非常類似，只是在劃分時(shí)所采用的準(zhǔn)則不同。我們這里不再贅述。但是這里可以來看看在實(shí)際的數(shù)據(jù)分析中，該如何操作。我們所使用的數(shù)據(jù)是如下所示的一個(gè)csv文件，文件內(nèi)容同本文最初給出的Play Ball例子中的數(shù)據(jù)是完全一致的。 

使用Weka進(jìn)行數(shù)據(jù)挖掘是非常容易的，你不再需要像R語言或者M(jìn)ATLAB那樣編寫代碼或者調(diào)用函數(shù)?；贕UI界面，在Weka中你只需要點(diǎn)點(diǎn)鼠標(biāo)即可！首先我們單擊“Explorer”按鈕來打開操作的主界面，如下圖所示。 

然后我們單擊“Open File…”，并從相應(yīng)的目錄下選擇你要用來進(jìn)行模型訓(xùn)練的數(shù)據(jù)文件，如下圖所示。 

Weka提供了非常易于操作的各種數(shù)據(jù)預(yù)處理功能，你可以自己嘗試探索一下。注意到屬性Day其實(shí)在構(gòu)建決策樹時(shí)是不需要的，我選中該屬性，并將其移除，如下圖所示。 

完成數(shù)據(jù)預(yù)處理后，我們就可以開始進(jìn)行模型訓(xùn)練了。因?yàn)槲覀兪且?a href='/map/jueceshu/' style='color:#000;font-size:inherit;'>決策樹，所以選擇“Classify”選項(xiàng)卡，然后在“Classifier”中選擇J48。你可以能會(huì)疑惑我們不是要使用C4.5算法建立決策樹嗎？為什么要選擇J48呢？其實(shí)J48是一個(gè)開源的C4.5的Java實(shí)現(xiàn)版本（J48 is an open source Java implementation of the C4.5 algorithm），所以J48就是C4.5。 數(shù)據(jù)分析師培訓(xùn)

然后你可以自定義的選擇“Test options”中的一些測(cè)試選項(xiàng)，這里我們不做過多說明。然后單擊“Start”按鈕，Weka就為我們建立了一棵決策樹，你可以從“Classifier output”欄目中看到模型訓(xùn)練的一些結(jié)果。但是對(duì)于決策樹而言，你可以覺得文字看起來還不夠直觀。不要緊，Weka還為你提供了可視化的決策樹建模呈現(xiàn)。為此，你需要右鍵單擊剛剛訓(xùn)練好的模型，然后從右鍵菜單中選擇“Visualize tree”，如下圖所示。 

最后我們得到了一棵與前面例子中相一致的決策樹，如下圖所示。 

在后續(xù)的決策樹系列文章中，我們將繼續(xù)深入探討CART算法等相關(guān)話題。