決策樹(shù)的建立

DecisionTree數(shù)據(jù)挖掘?qū)W習(xí)數(shù)據(jù)挖掘的工具-wekaweka是用Java語(yǔ)言編寫(xiě)的完整的軟件資源Explorer是weka的主要圖形用戶界面weka存儲(chǔ)數(shù)據(jù)的原始方式是ARFF或CSV文件格式ARFF文件是由一組實(shí)例組成，并且每組實(shí)例的屬性值由逗號(hào)分開(kāi)。（屬性的類別）天氣數(shù)據(jù)我們希望從上面的實(shí)例中找出者若干條規(guī)則，使得能夠?qū)@些實(shí)例的類做出判斷（理想情況下）（舉例）ifoutlook=sunnyand=highthenplay=noifhumidity=normalthenplay=yes第二條規(guī)則錯(cuò)分了一個(gè)實(shí)例樣本決策節(jié)點(diǎn)：1.最上面的節(jié)點(diǎn)稱為根節(jié)點(diǎn)，是整個(gè)決策樹(shù)的開(kāi)始。2.每個(gè)節(jié)點(diǎn)子節(jié)點(diǎn)的個(gè)數(shù)與決策樹(shù)在用的算法有關(guān)。（二叉樹(shù)、多叉樹(shù)）分支：判斷過(guò)程，要么是新的決策節(jié)點(diǎn)，要么是葉子樹(shù)葉:樹(shù)的結(jié)尾，每個(gè)葉子代表一個(gè)類別根節(jié)點(diǎn)葉子節(jié)點(diǎn)決策節(jié)點(diǎn)葉子節(jié)點(diǎn)葉子節(jié)點(diǎn)步驟：1.決策樹(shù)的生成：由訓(xùn)練樣本數(shù)據(jù)集（根據(jù)歷史數(shù)據(jù)生成、有一定綜合程度的用于數(shù)據(jù)分析處理的數(shù)據(jù)集）生成2.決策樹(shù)的剪枝：采用新的樣本數(shù)據(jù)集（測(cè)試數(shù)據(jù)集或者訓(xùn)練數(shù)據(jù)修剪集）檢驗(yàn)決策樹(shù)生成過(guò)程中產(chǎn)生的初步規(guī)則，將影響預(yù)測(cè)準(zhǔn)確性的分支剪除。ID3決策樹(shù)算法描述1.試探性地選擇一個(gè)屬性放置在根節(jié)點(diǎn)，并對(duì)該屬性的每個(gè)值產(chǎn)生一個(gè)分支。2.分裂根節(jié)點(diǎn)上的數(shù)據(jù)集，并移到子女節(jié)點(diǎn)，產(chǎn)生一棵局部樹(shù)。3.對(duì)該劃分的信息增益進(jìn)行計(jì)算。4.對(duì)其他屬性重復(fù)該過(guò)程。5.每個(gè)用于劃分的屬性產(chǎn)生一棵局部樹(shù)。6.根據(jù)局部樹(shù)的信息增益值，選擇一棵增益最大的屬性的局部樹(shù)。7.對(duì)選定的局部樹(shù)的每個(gè)子女節(jié)點(diǎn)重復(fù)以上1-6步。8.這是一個(gè)遞歸過(guò)程。如果一個(gè)節(jié)點(diǎn)上的所有實(shí)例都具有相同的類，則停止局部樹(shù)的生長(zhǎng)。選擇屬性作為根產(chǎn)生分支計(jì)算信息增益選擇max增益數(shù)據(jù)進(jìn)一步分裂？結(jié)束否是算法流程圖信息值（熵）、信息增益的概念熵：entropy（p1,p2,...,pn）=-p1logp1-p2logp2????-pnlogpn使用負(fù)號(hào)是因?yàn)榉謹(jǐn)?shù)p1,p2,...,pn的對(duì)數(shù)值是負(fù)數(shù)，而熵是一個(gè)正數(shù)。熵是以位bit位單位的，公式里的p1,p2,...,pn他們的和為1。entropy(p,q,r)=entropy(p,q+r)+(q+r)*entropy(q/(q+r),r/(q+r))我們需要一種度量來(lái)表示節(jié)點(diǎn)的純度，并需要這種度量告訴我們根據(jù)一個(gè)變量的屬性值將一個(gè)不純的節(jié)點(diǎn)上的數(shù)據(jù)劃分到其子女后，純度提高了多少。最為廣泛使用的度量是信息值(熵)。（以天氣數(shù)據(jù)為例）outlook屬性的樹(shù)樁yesyesnononoyesyesyesyesyesyesyesnonooutlooksunnyovercastrainy在葉子節(jié)點(diǎn)上的yes和no類的實(shí)例數(shù)量分別是[2,3]、[4,0]、[3,2]，因此，這些節(jié)點(diǎn)上的信息值分別是：info([2,3])=entropy(2/5,3/5)=0.971bitinfo([4,0])=entropy(1,0)=0bitinfo([3,2])=entropy(3/5,2/5)=0.971bit然后計(jì)算這些葉子節(jié)點(diǎn)的平均信息值，并考慮到達(dá)每個(gè)分支的實(shí)例數(shù)量：有5個(gè)實(shí)例到達(dá)第一和第三個(gè)分支；4個(gè)實(shí)例到達(dá)第二個(gè)分支：那么平均信息值info([2,3],[4,0],[3,2])=(5/14)*0.971+(4/14)*0+(5/14)*0.971=0.693bit在任何初始樹(shù)創(chuàng)建之前，處于根節(jié)點(diǎn)的訓(xùn)練樣本由9個(gè)yes和5個(gè)no組成，與之相對(duì)應(yīng)的信息值：info([9,5])=0.940bit因此樹(shù)樁所獲得的信息增益為：gain(outlook)=info([9,5])-info([2,3],[4,0],[3,2])=0.940-0.693=0.247bittemperature、humidity、wind屬性的樹(shù)樁yesyesnonoyesyesyesyesnonoyesyesyesnotemperaturehotmildcool分別計(jì)算它們的信息增益為：gain(temperature)=0.029bityesyesyesnonononoyesyesyesyesyesyesnohumidityhighnormalyesyesyesyesyesyesnonoyesyesyesnononowindfalsetruegain(humidity)=0.152bitgain(wind)=0.048bit將這些屬性的信息增益的值進(jìn)行比較，信息增益最大的屬性節(jié)點(diǎn)將作為決策樹(shù)的根節(jié)點(diǎn)。所以我們選擇outlook屬性作為根節(jié)點(diǎn)，它是唯一一個(gè)獲得了全純子節(jié)點(diǎn)，這就為超越其他所有屬性贏得了相當(dāng)大的優(yōu)勢(shì)。而濕度屬性是第二個(gè)最佳選擇，因?yàn)樗a(chǎn)生了一個(gè)幾乎是全純且較大的子節(jié)點(diǎn)。根節(jié)點(diǎn)確定了，接著繼續(xù)進(jìn)行這種遞歸過(guò)程。下面是outlook屬性值為sunny時(shí)的節(jié)點(diǎn)進(jìn)一步分支的可能性：outlooksunnyhumiditynononoyesyeshighnormaloutlooksunnywindyesnonoyesnofalsetrueoutlooksunnytemperaturenonoyesnoyeshotmildcool他們的信息增益分別為：gain(temperature)=0.571bitgain(humidity)=0.971bitgain(wind)=0.493bit因此選擇濕度屬性作為在這一個(gè)節(jié)點(diǎn)的分裂屬性，在隨之產(chǎn)生的子節(jié)點(diǎn)上并不需要進(jìn)一步分裂，因?yàn)槿~子節(jié)點(diǎn)都是全純子節(jié)點(diǎn)，所以這個(gè)分支就結(jié)束了。繼續(xù)應(yīng)用這樣的思想方法，將產(chǎn)生關(guān)于天氣數(shù)據(jù)的決策樹(shù)，如下圖所示。理想的停止條件是所有葉子節(jié)點(diǎn)都是純的，也就是當(dāng)葉子節(jié)點(diǎn)包含的實(shí)例擁有相同的類別。然而，也許并不可能達(dá)到這種理想狀態(tài)，因?yàn)楫?dāng)訓(xùn)練集里包含2個(gè)擁有相同屬性值，但是屬于不同類別的樣本時(shí)，遞歸過(guò)程將不可能停止。所以停止條件應(yīng)為當(dāng)數(shù)據(jù)不能被進(jìn)一步分裂時(shí)。outlooksunnyrainyovercasthumiditywindyesnoyesnoyesnormalhighfalsetrue天氣數(shù)據(jù)的決策樹(shù)ID3算法的不足及改進(jìn)當(dāng)一些屬性擁有的可能值得數(shù)量很大，從而使分支的路徑增加，產(chǎn)生出很多子節(jié)點(diǎn)時(shí)，計(jì)算信息增益就會(huì)出現(xiàn)一個(gè)問(wèn)題。用一個(gè)極端的例子來(lái)說(shuō)明：當(dāng)數(shù)據(jù)集的某個(gè)屬性對(duì)于每一個(gè)實(shí)例存在一個(gè)不同屬性值時(shí)，比如，一個(gè)標(biāo)志碼屬性。 標(biāo)志碼outlook temperaturehumidity windy play a sunny hot high FALSE no b sunny hot high TRUE no c overcast hot high FALSE yes d rainy mild high FALSE yes e rainy cool normal FALSE yes f rainy cool normal TRUE no g overcast cool normal TRUE yes h sunny mild high FALSEno i sunny cool normal FALSE yes j rainy mild normal FALSE yes k sunny mild normal TRUE yes l overcast mild high TRUE yes m overcast hot normal FALSE yes n rainy mild high TRUE no對(duì)標(biāo)志碼屬性進(jìn)行分裂而產(chǎn)生的樹(shù)樁如下，這個(gè)屬性值的類別所需的信息量是：info([0,1])+info([0,1])+info([1,0])+......+info([1,0])+info([0,1])=0bit標(biāo)志碼nonoyesnoyesanbcm···標(biāo)志碼屬性的信息增益就是在根節(jié)點(diǎn)上的信息量即：gain(標(biāo)志碼)=info([9,5])=0.940bit它比在其他任何屬性上獲得的信息增益值大，毫無(wú)疑問(wèn)標(biāo)志碼將被選為分裂屬性，但是在標(biāo)志碼屬性上的分支對(duì)預(yù)測(cè)未知實(shí)例的類別沒(méi)有任何幫助，也沒(méi)能夠描述任何有關(guān)決策的結(jié)構(gòu)。由此可見(jiàn)，采用度量信息增益的方法會(huì)傾向于選擇擁有較多可能屬性值的屬性。為了彌補(bǔ)這一缺陷，一個(gè)稱之為增益率(gainratio)的度量修正被廣范的采用。上例所有的計(jì)數(shù)值均為1，因此分裂信后的信息值是：info([1,…,1])=-1/14xlog(1/14)x14=logl4(3.807位)

分支越多，該值越大。

具有較高分支的屬性，該固有的信息值較高。

增益率，由信息增益除以該固有信息值得到。

例：得到標(biāo)志碼的增益率為0.940/3.807=0.247再返回之前的天氣數(shù)據(jù)的樹(shù)樁：屬性outlook將數(shù)據(jù)集分裂成3個(gè)子集，規(guī)模分別為5,4,5，因此不考慮子集中所包含的類別，產(chǎn)生一個(gè)內(nèi)在的信息值：info([5,4,5])=1.577bit得到outlook屬性的增益率為：(0.940-0.693)/1.577=0.157類似的可以計(jì)算出其他屬性樹(shù)樁的增益率：

temperature屬性的增益率為：(0.940-0.911)/info(4,6,4)=0.019humidity屬性的增益率為：(0.940-0.788)/info(7,7)=0.152wind屬性的增益率為：(0.940-0.693)/1.577=0.049

由此可以看出，在上述4個(gè)屬性中outlook屬性的結(jié)果依然排在首位，而humidity屬性以一個(gè)更為接近的值排在第二位，因?yàn)樗鼘?shù)據(jù)集分裂成2個(gè)子集而不是3個(gè)。在這個(gè)例子中，標(biāo)志碼屬性的增益率(0.247)任然是最高的，然而，它的優(yōu)勢(shì)已經(jīng)大大降低了。ID3算法最初的定義是假設(shè)屬性值是離散值，但在實(shí)際環(huán)境中，有很多屬性是連續(xù)的，不能夠用一個(gè)確定的標(biāo)準(zhǔn)來(lái)對(duì)其進(jìn)行劃分。C4.5使用下面的一系列處理過(guò)程來(lái)對(duì)連續(xù)的屬性劃分成離散的屬性，進(jìn)而達(dá)到能夠建立決策樹(shù)的目的。C4.5對(duì)ID3進(jìn)行了一系列改進(jìn)。這些改進(jìn)包括處理數(shù)值屬性、殘缺值、后剪枝的方法。（將訓(xùn)練數(shù)據(jù)分為成長(zhǎng)集和修剪集）C4.5算法做出的改進(jìn)(1)用信息增益率來(lái)選擇屬性(2)可以處理連續(xù)數(shù)值型屬性

在選擇某節(jié)點(diǎn)上的分枝屬性時(shí)，對(duì)于離散型描述屬性，C4.5的處理方法與ID3相同，按照該屬性本身的取值個(gè)數(shù)進(jìn)行計(jì)算；對(duì)于某個(gè)連續(xù)性描述屬性Ac，假設(shè)在某個(gè)結(jié)點(diǎn)上的數(shù)據(jù)集的樣本數(shù)量為t，C4.5將作以下處理。1.將該結(jié)點(diǎn)上的所有數(shù)據(jù)樣本按照連續(xù)型描述屬性的具體數(shù)值，由小到大進(jìn)行排序，得到屬性值的取值序列{A1c，A2c，……Atc}。2.在取值序列中生成t-1個(gè)分割點(diǎn)。第i（0<i<t）個(gè)分割點(diǎn)的取值設(shè)置為Vi=（Aic+A（i+1）c）/2,它可以將該節(jié)點(diǎn)上的數(shù)據(jù)集劃分為兩個(gè)子集。3.從t-1個(gè)分割點(diǎn)中選擇最佳分割點(diǎn)。對(duì)于每一個(gè)分割點(diǎn)劃分?jǐn)?shù)據(jù)集的方式，C4.5計(jì)算它的信息增益率，并且從中選擇信息增益率最大的分割點(diǎn)來(lái)劃分?jǐn)?shù)據(jù)集。(3)采用了一種后剪枝方法在后修剪過(guò)程中考慮兩種完全不同的操作：子樹(shù)置換和子樹(shù)上升ALTpriceyesabcyesyesno4/57/81/2ALTyes12/15子樹(shù)的置換yes子樹(shù)的上升：ABC45123A