決策樹技術培訓課程

決策樹技術

DecisionTrees組員：賈小彥鄧蓓蓓戴維第一頁，共三十二頁。內容提要簡介決策樹基本概念決策樹的優(yōu)缺點經(jīng)典算法第二頁，共三十二頁。簡介決策樹和決策規(guī)則是解決實際應用中分類問題的數(shù)據(jù)挖掘方法。一般來說，分類是把數(shù)據(jù)項映射到其中一個事先定義的類中的這樣一個學習函數(shù)的過程。由一組輸入的屬性值向量(也叫屬性向量)和相應的類，用基于歸納學習算法得出分類。學習的目標是構建一個分類模型，通常也叫分類器。它可以根據(jù)有效的屬性輸入值預測一些實體(所給樣本)的類。是一個在樣本其他屬性已知的情況下預測另外一個屬性(樣本的類)的模型(分類的結果)。第三頁，共三十二頁。(a)

決策樹方法的起源是概念學習系統(tǒng)CLS(b)機器學習領域前輩及大牛之一Quinlan,J.R,在1983提出ID3決策樹算法；1993年正式提出了c4.5算法,并公布了源代碼2002年發(fā)表C5.0（See5）商業(yè)版決策樹的另一類家族：CART1984，F(xiàn)riedman&Breiman第四頁，共三十二頁。決策樹基本概念

決策樹是一種典型的分類方法，首先對數(shù)據(jù)進行處理，利用歸納算法生成可讀的規(guī)則和決策樹，然后使用決策對新數(shù)據(jù)進行分析。本質上決策樹是通過一系列規(guī)則對數(shù)據(jù)進行分類的過程。第五頁，共三十二頁。下圖是一個簡單的決策樹。該問題有兩個屬性X,Y。所有屬性值X>1和Y>B的樣本屬于類2。不論屬性Y的值是多少，值X<1的樣本都屬于類1。第六頁，共三十二頁。決策樹的表示決策樹的基本組成部分：決策結點、分支和葉子。決策樹中最上面的結點稱為根結點是整個決策樹的開始。每個分支是一個新的決策結點，或者是樹的葉子。每個決策結點代表一個問題或者決策通常對應待分類對象的屬性。每個葉結點代表一種可能的分類結果第七頁，共三十二頁。

在沿著決策樹從上到下的遍歷過程中，在每個結點都有一個測試。對每個結點上問題的不同測試輸出導致不同的分枝，最后會達到一個葉子結點。這一過程就是利用決策樹進行分類的過程，利用若干個變量來判斷屬性的類別第八頁，共三十二頁。決策樹的優(yōu)點1、推理過程容易理解，決策推理過程可以表示成IfThen形式；2、推理過程完全依賴于屬性變量的取值特點；3、可自動忽略目標變量沒有貢獻的屬性變量，也為判斷屬性變量的重要性，減少變量的數(shù)目提供參考。決策樹的缺點1、對連續(xù)性的字段比較難預測2、當類別太多時，錯誤可能會增加的比較快3、一般的算法分類的時候，只是根據(jù)一個屬性來分類。不是全局最優(yōu)。決策樹的優(yōu)、缺點第九頁，共三十二頁。經(jīng)典算法——ID3學習算法第十頁，共三十二頁。決策樹的生成基本算法自上而下分而治之的方法開始時，所有的數(shù)據(jù)都在根節(jié)點屬性都是種類字段(如果是連續(xù)的，將其離散化)所有記錄用所選屬性遞歸的進行分割屬性的選擇是基于一個啟發(fā)式規(guī)則或者一個統(tǒng)計的度量停止分割的條件一個節(jié)點上的數(shù)據(jù)都是屬于同一個類別沒有屬性可以再用于對數(shù)據(jù)進行分割第十一頁，共三十二頁。重要問題：哪個屬性作為當前的測試節(jié)點第十二頁，共三十二頁。信息論相關內容Shannon1948年提出的信息論理論。事件ai的信息I（ai

）可如下度量：其中p(ai)表示事件ai發(fā)生的概率。假設有n個互不相容的事件a1,a2,a3,….,an,它們中有且僅有一個發(fā)生，則其平均的信息量可如下度量：第十三頁，共三十二頁。上式，對數(shù)底數(shù)可以為任何數(shù)，不同的取值對應了熵的不同單位。通常取2，并規(guī)定當p(ai)=0時=0公式1第十四頁，共三十二頁。在決策樹分類中，假設S是訓練樣本集合，|S|是訓練樣本數(shù)，樣本劃分為n個不同的類C1,C2,….Cn，這些類的大小分別標記為|C1|，|C2|，…..,|Cn|。則任意樣本S屬于類Ci的概率為：Entropy（S，A）=∑（|Sv|/|S|）*Entropy(Sv)

公式2

∑是屬性A的所有可能的值v,Sv是屬性A有v值的S子集|Sv|是Sv中元素的個數(shù)；|S|是S中元素的個數(shù)。第十五頁，共三十二頁。Gain（S，A）是屬性A在集合S上的信息增益Gain（S，A）=Entropy(s)-Entropy（S，A）公式3Gain（S，A）越大，說明選擇測試屬性對分類提供的信息越多第十六頁，共三十二頁。熵的計算Eg1:第十七頁，共三十二頁。Eg2:假定公司收集了左表數(shù)據(jù)，那么對于任意給定的客人（測試樣例），你能幫助公司將這位客人歸類嗎？即：你能預測這位客人是屬于“買”計算機的那一類，還是屬于“不買”計算機的那一類？又：你需要多少有關這位客人的信息才能回答這個問題？第十八頁，共三十二頁。計數(shù)年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1老中否優(yōu)買第1步計算決策屬性的熵決策屬性“買計算機？”。該屬性分兩類：買/不買S1(買)=641S2（不買）=383S=S1+S2=1024P1=641/1024=0.6260P2=383/1024=0.3740I(S1,S2)=I(641,383)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9537第十九頁，共三十二頁。計數(shù)年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1老中否優(yōu)買第2步計算條件屬性的熵條件屬性共有4個。分別是年齡、收入、學生、信譽。分別計算不同屬性的信息增益。第2-1步計算年齡的熵年齡共分三個組：青年、中年、老年青年買與不買比例為128/256S1(買)=128S2（不買）=256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9183第二十頁，共三十二頁。第2-2步計算年齡的熵年齡共分三個組：青年、中年、老年中年買與不買比例為256/0S1(買)=256S2（不買）=0S=S1+S2=256P1=256/256P2=0/256I(S1,S2)=I(256，0)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0第2-3步計算年齡的熵年齡共分三個組：青年、中年、老年老年買與不買比例為125/127S1(買)=125S2（不買）=127S=S1+S2=252P1=125/252P2=127/252I(S1,S2)=I(125，127)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9157第二十一頁，共三十二頁。第2-4步計算年齡的熵年齡共分三個組：青年、中年、老年所占比例青年組384/1025=0.375中年組256/1024=0.25老年組384/1024=0.375計算年齡的平均信息期望E（年齡）=0.375*0.9183+0.25*0+0.375*0.9157=0.6877G（年齡信息增益）

=0.9537-0.6877=0.2660（1）第二十二頁，共三十二頁。計數(shù)年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1老中否優(yōu)買第3步計算收入的熵收入共分三個組：高、中、低E（收入）=0.9361收入信息增益=0.9537-0.9361=0.0176(2)第二十三頁，共三十二頁。第4步計算學生的熵學生共分二個組：學生、非學生E（學生）=0.7811年齡信息增益=0.9537-0.7811=0.1726（3）第5步計算信譽的熵信譽分二個組：良好，優(yōu)秀E（信譽）=0.9048信譽信息增益=0.9537-0.9048=0.0453（4）第二十四頁，共三十二頁。第6步計算選擇節(jié)點年齡信息增益=0.9537-0.6877=0.2660（1）收入信息增益=0.9537-0.9361=0.0176（2）學生信息增益=0.9537-0.7811=0.1726（3）信譽信息增益=0.9537-0.9048=0.0453（4）第二十五頁，共三十二頁。計數(shù)年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128青中否良不買64青低是良買64青中是優(yōu)買年齡買/不買買/不買買青年中年老年葉子第二十六頁，共三十二頁。計數(shù)年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128青中否良不買64青低是良買64青中是優(yōu)買青年買與不買比例為128/256S1(買)=128S2（不買）=256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9183第二十七頁，共三十二頁。計數(shù)年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128青中否良不買64青低是良買64青中是優(yōu)買如果選擇收入作為節(jié)點分高、中、低I(0,128)=0比例:128/384=0.3333I(64,128)=0.9183比例:192/384=0.5I(64,0)=0比例:64/384=0.1667平均信息期望（加權總和）：

E(收入）=0.3333*0+0.5*0.9183+0.1667*0=0.4592Gain(收入)=I(128,256)-E(收入)=0.9183

–0.4592=0.4591第二十八頁，共三十二頁。計數(shù)年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1老中否優(yōu)買第二十九頁，共三十二頁。ID3算法小結ID3算法是一種經(jīng)典的決策