3.1推沸、摘要

在前面兩篇文章中涩蜘，分別介紹和討論了樸素貝葉斯分類與貝葉斯網(wǎng)絡(luò)兩種分類算法。這兩種算法都以貝葉斯定理為基礎(chǔ)驮配，可以對分類及決策問題進(jìn)行概率推斷娘扩。在這一篇文章中着茸，將討論另一種被廣泛使用的分類算法——決策樹（decision tree）。相比貝葉斯算法琐旁，決策樹的優(yōu)勢在于構(gòu)造過程不需要任何領(lǐng)域知識或參數(shù)設(shè)置涮阔，因此在實(shí)際應(yīng)用中，對于探測式的知識發(fā)現(xiàn)灰殴，決策樹更加適用敬特。

3.2、決策樹引導(dǎo)

通俗來說牺陶，決策樹分類的思想類似于找對象∥袄現(xiàn)想象一個(gè)女孩的母親要給這個(gè)女孩介紹男朋友，于是有了下面的對話：

女兒：多大年紀(jì)了掰伸？

母親：26皱炉。

女兒：長的帥不帥？

母親：挺帥的狮鸭。

女兒：收入高不娃承？

母親：不算很高，中等情況怕篷。

女兒：是公務(wù)員不历筝？

母親：是，在稅務(wù)局上班呢廊谓。

女兒：那好梳猪，我去見見。

這個(gè)女孩的決策過程就是典型的分類樹決策蒸痹。相當(dāng)于通過年齡春弥、長相、收入和是否公務(wù)員對將男人分為兩個(gè)類別：見和不見叠荠。假設(shè)這個(gè)女孩對男人的要求是：30歲以下匿沛、長相中等以上并且是高收入者或中等以上收入的公務(wù)員，那么這個(gè)可以用下圖表示女孩的決策邏輯（聲明：此決策樹純屬為了寫文章而YY的產(chǎn)物榛鼎，沒有任何根據(jù)逃呼，也不代表任何女孩的擇偶傾向，請各位女同胞莫質(zhì)問我^_^）：

上圖完整表達(dá)了這個(gè)女孩決定是否見一個(gè)約會對象的策略者娱，其中綠色節(jié)點(diǎn)表示判斷條件抡笼，橙色節(jié)點(diǎn)表示決策結(jié)果，箭頭表示在一個(gè)判斷條件在不同情況下的決策路徑黄鳍，圖中紅色箭頭表示了上面例子中女孩的決策過程推姻。

這幅圖基本可以算是一顆決策樹，說它“基本可以算”是因?yàn)閳D中的判定條件沒有量化框沟，如收入高中低等等藏古，還不能算是嚴(yán)格意義上的決策樹增炭，如果將所有條件量化，則就變成真正的決策樹了拧晕。

有了上面直觀的認(rèn)識隙姿，我們可以正式定義決策樹了：

決策樹（decision tree）是一個(gè)樹結(jié)構(gòu)（可以是二叉樹或非二叉樹）。其每個(gè)非葉節(jié)點(diǎn)表示一個(gè)特征屬性上的測試防症，每個(gè)分支代表這個(gè)特征屬性在某個(gè)值域上的輸出孟辑，而每個(gè)葉節(jié)點(diǎn)存放一個(gè)類別。使用決策樹進(jìn)行決策的過程就是從根節(jié)點(diǎn)開始蔫敲，測試待分類項(xiàng)中相應(yīng)的特征屬性饲嗽，并按照其值選擇輸出分支，直到到達(dá)葉子節(jié)點(diǎn)奈嘿，將葉子節(jié)點(diǎn)存放的類別作為決策結(jié)果貌虾。

可以看到，決策樹的決策過程非常直觀裙犹，容易被人理解尽狠。目前決策樹已經(jīng)成功運(yùn)用于醫(yī)學(xué)、制造產(chǎn)業(yè)叶圃、天文學(xué)袄膏、分支生物學(xué)以及商業(yè)等諸多領(lǐng)域。知道了決策樹的定義以及其應(yīng)用方法掺冠，下面介紹決策樹的構(gòu)造算法沉馆。

3.3、決策樹的構(gòu)造

不同于貝葉斯算法德崭，決策樹的構(gòu)造過程不依賴領(lǐng)域知識斥黑，它使用屬性選擇度量來選擇將元組最好地劃分成不同的類的屬性。所謂決策樹的構(gòu)造就是進(jìn)行屬性選擇度量確定各個(gè)特征屬性之間的拓?fù)浣Y(jié)構(gòu)眉厨。

構(gòu)造決策樹的關(guān)鍵步驟是分裂屬性锌奴。所謂分裂屬性就是在某個(gè)節(jié)點(diǎn)處按照某一特征屬性的不同劃分構(gòu)造不同的分支，其目標(biāo)是讓各個(gè)分裂子集盡可能地“純”憾股。盡可能“純”就是盡量讓一個(gè)分裂子集中待分類項(xiàng)屬于同一類別鹿蜀。分裂屬性分為三種不同的情況：

1、屬性是離散值且不要求生成二叉決策樹荔燎。此時(shí)用屬性的每一個(gè)劃分作為一個(gè)分支耻姥。

2、屬性是離散值且要求生成二叉決策樹有咨。此時(shí)使用屬性劃分的一個(gè)子集進(jìn)行測試，按照“屬于此子集”和“不屬于此子集”分成兩個(gè)分支蒸健。

3座享、屬性是連續(xù)值婉商。此時(shí)確定一個(gè)值作為分裂點(diǎn)split_point，按照>split_point和<=split_point生成兩個(gè)分支渣叛。

構(gòu)造決策樹的關(guān)鍵性內(nèi)容是進(jìn)行屬性選擇度量丈秩，屬性選擇度量是一種選擇分裂準(zhǔn)則，是將給定的類標(biāo)記的訓(xùn)練集合的數(shù)據(jù)劃分D“最好”地分成個(gè)體類的啟發(fā)式方法淳衙，它決定了拓?fù)浣Y(jié)構(gòu)及分裂點(diǎn)split_point的選擇蘑秽。

屬性選擇度量算法有很多，一般使用自頂向下遞歸分治法箫攀，并采用不回溯的貪心策略肠牲。這里介紹ID3和C4.5兩種常用算法。

3.3.1靴跛、ID3算法

從信息論知識中我們直到缀雳，期望信息越小，信息增益越大梢睛，從而純度越高肥印。所以ID3算法的核心思想就是以信息增益度量屬性選擇，選擇分裂后信息增益最大的屬性進(jìn)行分裂绝葡。下面先定義幾個(gè)要用到的概念深碱。

設(shè)D為用類別對訓(xùn)練元組進(jìn)行的劃分，則D的熵（entropy）表示為：

其中pi表示第i個(gè)類別在整個(gè)訓(xùn)練元組中出現(xiàn)的概率藏畅，可以用屬于此類別元素的數(shù)量除以訓(xùn)練元組元素總數(shù)量作為估計(jì)敷硅。熵的實(shí)際意義表示是D中元組的類標(biāo)號所需要的平均信息量。

現(xiàn)在我們假設(shè)將訓(xùn)練元組D按屬性A進(jìn)行劃分墓赴，則A對D劃分的期望信息為：

而信息增益即為兩者的差值：

ID3算法就是在每次需要分裂時(shí)竞膳，計(jì)算每個(gè)屬性的增益率，然后選擇增益率最大的屬性進(jìn)行分裂诫硕。下面我們繼續(xù)用SNS社區(qū)中不真實(shí)賬號檢測的例子說明如何使用ID3算法構(gòu)造決策樹坦辟。為了簡單起見，我們假設(shè)訓(xùn)練集合包含10個(gè)元素：

其中s章办、m和l分別表示小锉走、中和大。

設(shè)L藕届、F挪蹭、H和R表示日志密度、好友密度休偶、是否使用真實(shí)頭像和賬號是否真實(shí)梁厉，下面計(jì)算各屬性的信息增益。

因此日志密度的信息增益是0.276。

用同樣方法得到H和F的信息增益分別為0.033和0.553词顾。

因?yàn)镕具有最大的信息增益八秃，所以第一次分裂選擇F為分裂屬性，分裂后的結(jié)果如下圖表示：

在上圖的基礎(chǔ)上肉盹，再遞歸使用這個(gè)方法計(jì)算子節(jié)點(diǎn)的分裂屬性昔驱，最終就可以得到整個(gè)決策樹。

上面為了簡便上忍，將特征屬性離散化了骤肛，其實(shí)日志密度和好友密度都是連續(xù)的屬性。對于特征屬性為連續(xù)值窍蓝，可以如此使用ID3算法：

先將D中元素按照特征屬性排序腋颠，則每兩個(gè)相鄰元素的中間點(diǎn)可以看做潛在分裂點(diǎn)，從第一個(gè)潛在分裂點(diǎn)開始它抱，分裂D并計(jì)算兩個(gè)集合的期望信息秕豫，具有最小期望信息的點(diǎn)稱為這個(gè)屬性的最佳分裂點(diǎn)，其信息期望作為此屬性的信息期望观蓄。

3.3.2混移、C4.5算法

ID3算法存在一個(gè)問題，就是偏向于多值屬性侮穿，例如歌径，如果存在唯一標(biāo)識屬性ID，則ID3會選擇它作為分裂屬性亲茅，這樣雖然使得劃分充分純凈回铛，但這種劃分對分類幾乎毫無用處。ID3的后繼算法C4.5使用增益率（gain ratio）的信息增益擴(kuò)充克锣，試圖克服這個(gè)偏倚茵肃。

C4.5算法首先定義了“分裂信息”，其定義可以表示成：

其中各符號意義與ID3算法相同袭祟，然后验残，增益率被定義為：

C4.5選擇具有最大增益率的屬性作為分裂屬性，其具體應(yīng)用與ID3類似巾乳，不再贅述您没。

3.4、關(guān)于決策樹的幾點(diǎn)補(bǔ)充說明

3.4.1胆绊、如果屬性用完了怎么辦

在決策樹構(gòu)造過程中可能會出現(xiàn)這種情況：所有屬性都作為分裂屬性用光了玷室，但有的子集還不是純凈集寓辱，即集合內(nèi)的元素不屬于同一類別康嘉。在這種情況下甫窟，由于沒有更多信息可以使用了，一般對這些子集進(jìn)行“多數(shù)表決”，即使用此子集中出現(xiàn)次數(shù)最多的類別作為此節(jié)點(diǎn)類別肢础，然后將此節(jié)點(diǎn)作為葉子節(jié)點(diǎn)还栓。

3.4.2碌廓、關(guān)于剪枝

在實(shí)際構(gòu)造決策樹時(shí)传轰，通常要進(jìn)行剪枝，這時(shí)為了處理由于數(shù)據(jù)中的噪聲和離群點(diǎn)導(dǎo)致的過分?jǐn)M合問題谷婆。剪枝有兩種：

先剪枝——在構(gòu)造過程中慨蛙，當(dāng)某個(gè)節(jié)點(diǎn)滿足剪枝條件，則直接停止此分支的構(gòu)造纪挎。

后剪枝——先構(gòu)造完成完整的決策樹期贫，再通過某些條件遍歷樹進(jìn)行剪枝。

關(guān)于剪枝的具體算法這里不再詳述异袄，有興趣的可以參考相關(guān)文獻(xiàn)通砍。