1、決策樹學(xué)習(xí)算法概要簡介決策樹表示法決策樹學(xué)習(xí)的適用問題根本的決策樹學(xué)習(xí)算法決策樹學(xué)習(xí)中的假想空間搜索決策樹學(xué)習(xí)的常見問題.簡介決策樹方法的來源是概念學(xué)習(xí)系統(tǒng)CLS，然后開展到ID3方法而為高潮，最后又演化為能處置延續(xù)屬性的C4.5。有名的決策樹方法還有CART和Assistant。是運用最廣的歸納推理算法之一一種逼近離散值目的函數(shù)的方法對噪聲數(shù)據(jù)有很好的強壯性且能學(xué)習(xí)析取表達式.1.決策樹算法的框架(1/5)斷定樹分類算法output訓(xùn)練集決策樹input.決策樹經(jīng)過把實例從根節(jié)點陳列到某個葉子節(jié)點來分類實例。葉子節(jié)點即為實例所屬的分類每個節(jié)點闡明了對實例的某個屬性的測試節(jié)點的每個后繼分支對應(yīng)

2、于該屬性的一個能夠值正實例：產(chǎn)生正值決策的實例負(fù)實例：產(chǎn)生負(fù)值決策的實例1.決策樹算法的框架(2/5).1.決策樹算法的框架(3/5).決策樹代表實例屬性值約束的合取的析取式(析取范式)。從樹根到樹葉的每一條途徑對應(yīng)一組屬性測試的合取，樹本身對應(yīng)這些合取的析取1.決策樹算法的框架(4/5).1.決策樹算法的框架(5/5).2.決策樹學(xué)習(xí)的適用問題(1/2)適用問題的特征實例是由屬性-值對表示的目的函數(shù)具有離散的輸出值能夠需求析取的描畫訓(xùn)練數(shù)據(jù)可以包含錯誤訓(xùn)練數(shù)據(jù)可以包含短少屬性值的實例.問題舉例根據(jù)疾病分類患者根據(jù)原因分類設(shè)備缺點根據(jù)拖欠支付的能夠性分類貸款懇求分類問題中心義務(wù)是把樣例分類到各

3、能夠的離散值對應(yīng)的類別2.決策樹學(xué)習(xí)的適用問題(2/2).3.根本的決策樹學(xué)習(xí)算法CLS學(xué)習(xí)算法ID3學(xué)習(xí)算法.CLS學(xué)習(xí)算法根本思想： 在CLS的決策樹中，節(jié)點對應(yīng)于待分類對象的屬性，由某一節(jié)點引出的弧對應(yīng)于這一屬性能夠去的屬性值，葉節(jié)點對應(yīng)于分類的結(jié)果。.CLS算法描畫假設(shè)訓(xùn)練集TR中一切實例分類結(jié)果均為Ci，那么前往Ci；從屬性表中選擇某一屬性A作為檢測屬性；無妨假定|ValueType(Ai)|=k，根據(jù)A取值不同，將TR劃分為k個集TR1, TRk, ；從屬性表中去掉已檢驗的屬性A ；對每個i，用TRi和新的屬性表遞歸調(diào)用CLS生成TRi的決策樹；前往以屬性A為根，為子樹的決策樹。.

4、例1：鳥能否能飛的實例InstancesNo. of wingsBroken wings Living statusWing area/ weight Fly120Alive2.5True221Alive2.5False322Alive2.6False420Alive3.0True520Dead3.2False600Alive0False710Alive0False820Alive3.4True920alive2.0False.屬性表: No. of wings， Broken wings， Living status， wing area/ weight 各屬性的取值域分別為： ValueT

5、ype(No. of wings)=0,1,2 ValueType(Broken wings)=0,1,2 ValueType(Living status)=alive, dead ValueType(wing area/ weight).No. of wingsNo. of wingsNoNoNoNostatusNo. of wingsNoyesNo210210alivedead.ID3算法 CLS算法可以產(chǎn)生一切能夠的決策樹，正確分類訓(xùn)練實例。并能選擇最簡單的決策樹。但是，它所面對的學(xué)習(xí)問題不能太大，并且一次對全部訓(xùn)練集構(gòu)造決策的算法效率低。為此，Quinlan提出了逐漸構(gòu)成完好決策樹的迭

6、代思想。.ID3的思想自頂向下構(gòu)造決策樹從“哪一個屬性將在樹的根節(jié)點被測試開場運用統(tǒng)計測試來確定每一個實例屬性單獨分類訓(xùn)練樣例的才干ID3的過程分類才干最好的屬性被選作樹的根節(jié)點根節(jié)點的每個能夠值產(chǎn)生一個分支訓(xùn)練樣例陳列到適當(dāng)?shù)姆种Х磸?fù)上面的過程.信息熵(Information Entropy) 信息熵是一個數(shù)學(xué)上頗為籠統(tǒng)的概念，在這里無妨把信息熵了解成某種特定信息的出現(xiàn)概率離散隨機事件的出現(xiàn)概率。一個系統(tǒng)越是有序，信息熵就越低；反之，一個系統(tǒng)越是混亂，信息熵就越高。信息熵也可以說是系統(tǒng)有序化程度的一個度量。 .熵(Entropy) 原是物理學(xué)中的一個概念，法國物理學(xué)家克勞修斯用熵描畫一個物理

7、系統(tǒng)的無序性。系統(tǒng)的無序程度越高，那么熵越大。.信息論在信息論中信源輸出是隨機量，因此其不定度可以用概率分布來度量。記 H(X)H(P1，P2，Pn)，這里P(i)，i1，2，n為信源取第i個符號的概率。H(X)稱為信源的信息熵。 .可以從數(shù)學(xué)上加以證明，只需H(X)滿足以下三個條件： 延續(xù)性：H(P，1P)是P的延續(xù)函數(shù)(0P1)； 對稱性：H(P1，Pn)與P1，Pn的陳列次序無關(guān)； 可加性：假設(shè)PnQ1+Q20，且Q1，Q20，那么有H(P1，Pn-1，Q1，Q2)H(P1，Pn-1)+PnH；那么一定有以下獨一表達方式：H(P1，Pn)-CP(i)logP(i) 其中C為正整數(shù)，普通取

8、C1，它是信息熵的最根本表達式。.信息熵除了上述三條根本性質(zhì)外，還具有一系列重要性質(zhì)，其中最主要的有： 非負(fù)性：H(P1，Pn)0； 確定性：H(1，0)H(0，1)H(0，1，0，)0； 擴張性：Hn-1(P1，Pn-，)Hn(P1，Pn)； 極值性：P(xi)logP(xi)P(xi)logQ(xi)；這里Q(xi)1； 上凸性：HP +(1-)QH(P)+(1-)H(Q)，式中01。 .屬性選擇熵(entropy)：給定有關(guān)某概念的正例和負(fù)例的集合S。對此BOOLEAN分類的熵為： Entropy(S)= - pos log2(pos) neg log2(neg) “pos和neg分別表

9、示S中正例和負(fù)例的比例。并定義：0log2(0)=0假設(shè)分類器有c個不同的輸出，那么： Entropy(S)= - ci=1pi log2(pi) pi表示S中屬于類i的比例.例1：p1 = p2 = 1/2 H1 = -(1/2)*log2(1/2) - (1/2)*log2(1/2) = 1例2：p1 = 1/4 p2 = 3/4 H2 = -(1/4)* log2(1/4) - (3/4)*log2(3/4)=0.81例3：p1 = 1 p2 = 0 H3 = -1 * log21 = 0.屬性選擇構(gòu)造好的決策樹的關(guān)鍵在于如何選擇好的屬性。對于同樣一組例子，可以有很多決策樹能符合這組例子

10、。人們研討出，普通情況下或具有較大約率地說，樹越小那么樹的預(yù)測才干越強。要構(gòu)造盡能夠小的決策樹，關(guān)鍵在于選擇恰當(dāng)?shù)膶傩?。由于?gòu)造最小的樹是NP-難問題，因此只能采取用啟發(fā)式戰(zhàn)略選擇好的屬性。 .ID3算法的本質(zhì)： 就是構(gòu)造一棵熵值下降平均最快的決策樹。.最正確分類屬性用信息增益度量期望的熵降低屬性的信息增益，由于運用這個屬性分割樣例而導(dǎo)致的期望熵降低Gain(S,A)是在知道屬性A的值后可以節(jié)省的二進制位數(shù).ID3算法創(chuàng)建樹的Root結(jié)點假設(shè)Examples都為正，那么前往label=+中的單結(jié)點Root假設(shè)Examples都為反，那么前往lable=-單結(jié)點樹Root假設(shè)Attributes

11、為空，那么前往單節(jié)點樹Root，lable=Examples中最普遍的目的屬性值否那么開場AAttributes中分類才干最好的屬性Root的決策屬性A對于每個能夠值 在Root下加一個新的分支對應(yīng)測試A=vi令Example-vi為Examples中滿足A屬性值為vi的子集假設(shè)Examples-vi為空在這個新分支下加一個葉子結(jié)點，節(jié)點的lable=Examples中最普遍的 目的屬性值否那么在這個新分支下加一個子樹ID3(example-vi,target-attribute,attributes-|A|終了前往 Root.ID3主算法流程圖訓(xùn)練集PE,NE取子集建窗口窗口PE,NE生成決

12、策樹測試PE,NE此決策樹為最后結(jié)果擴展窗口PE=PE+PENE=NE+NE存在錯誤的PE,NE.例2. .Decision Tree (結(jié)果輸出)age?overcaststudent?credit rating?noyesfairexcellent40nonoyesyesyes30.40.用信息增益度量期望熵最低.舉例.用ID3算法得到的有關(guān)氣候的決策樹.某市屬建筑公司面臨A, B兩項工.本單位資源條件限制，只能選擇其中一項工程招標(biāo)或者這兩項過程均不參與招標(biāo)。根據(jù)過去類似工程招標(biāo)的閱歷數(shù)據(jù)，A工程投高標(biāo)的中標(biāo)概率為0.3,投低標(biāo)的中標(biāo)概率為0.8,編制該工程招標(biāo)文件的費用為4萬元；B工程投

13、高標(biāo)的中標(biāo)概率為0.5,投低標(biāo)的中標(biāo)概率為0.6，編制該工程招標(biāo)文件的費用為2.5 萬元各方案承包的效果、概率、損益值如表1所示 .ID3算法的優(yōu)缺陷ID3算法的優(yōu)點：分類和測試速度快缺陷：1.知識表示沒有規(guī)那么容易了解；2. 兩棵決策樹能否等價的斷定問題是NP問題；3.不能處置未知屬性值的情況。.C4.5C4.5是對ID3的改良算法對延續(xù)值的處置對未知特征值的處置對決策樹進展剪枝規(guī)那么的派生.決策樹學(xué)習(xí)中的假設(shè)空間搜索假設(shè)空間ID3算法中的假設(shè)空間包含一切的決策樹當(dāng)遍歷決策樹空間時，ID3僅維護單一的當(dāng)前假設(shè)。根本的ID3算法在搜索中不進展回溯ID3算法在搜索的每一步都運用當(dāng)前的一切訓(xùn)練樣例

14、.決策樹學(xué)習(xí)的常見問題(1)防止過度擬合數(shù)據(jù)根本的決策樹構(gòu)造算法沒有思索噪聲，生成的決策樹完全與訓(xùn)練例子擬合。有噪聲情況下，完全擬合將導(dǎo)致過分?jǐn)M合overfitting，即對訓(xùn)練數(shù)據(jù)的完全擬合反而不具有很好的預(yù)測性能。 .處理方法剪枝是一種抑制噪聲的技術(shù)，同時它也能使樹得到簡化而變得更容易了解。向前剪枝forward pruning向后剪枝backward pruning 實際上講，向后剪枝好于向前剪枝，但計算復(fù)雜度大。剪枝過程中普通要涉及一些統(tǒng)計參數(shù)或閾值，如停機閾值；有人提出了一種和統(tǒng)計參數(shù)無關(guān)的基于最小描畫長MDL的有效剪枝法 .決策樹學(xué)習(xí)的常見問題2合并延續(xù)值屬性屬性選擇的其他度量規(guī)范信息增益比gain r