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

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

3、能夠的離散值對應的類別2.決策樹學習的適用問題(2/2).3.根本的決策樹學習算法CLS學習算法ID3學習算法.CLS學習算法根本思想： 在CLS的決策樹中，節點對應于待分類對象的屬性，由某一節點引出的弧對應于這一屬性能夠去的屬性值，葉節點對應于分類的結果。.CLS算法描畫假設訓練集TR中一切實例分類結果均為Ci，那么前往Ci；從屬性表中選擇某一屬性A作為檢測屬性；無妨假定|ValueType(Ai)|=k，根據A取值不同，將TR劃分為k個集TR1, TRk, ；從屬性表中去掉已檢驗的屬性A ；對每個i，用TRi和新的屬性表遞歸調用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算法可以產生一切能夠的決策樹，正確分類訓練實例。并能選擇最簡單的決策樹。但是，它所面對的學習問題不能太大，并且一次對全部訓練集構造決策的算法效率低。為此，Quinlan提出了逐漸構成完好決策樹的迭

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

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

8、C1，它是信息熵的最根本表達式。.信息熵除了上述三條根本性質外，還具有一系列重要性質，其中最主要的有： 非負性：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)：給定有關某概念的正例和負例的集合S。對此BOOLEAN分類的熵為： Entropy(S)= - pos log2(pos) neg log2(neg) “pos和neg分別表

9、示S中正例和負例的比例。并定義：0log2(0)=0假設分類器有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.屬性選擇構造好的決策樹的關鍵在于如何選擇好的屬性。對于同樣一組例子，可以有很多決策樹能符合這組例子

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

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

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

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

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