決策樹14基礎知識提要數據挖掘簡介決策樹的用途決策樹的建立（ID3）C4.5示例WekaJ48源碼解析2022/12/132數據挖掘簡介誰加何種類型的油？姓名年齡收入種族信譽電話地址加何種油張三234000亞裔良281-322-03282714Ave.MSupreme李四342800白人優713-239-78305606HollyCrRegular王二701900西班牙優281-242-32222000BellBlvd.Plus趙五18900非洲良281-550-0544100MainStreetSupreme劉蘭342500白人優713-239-7430606HollyCtRegular楊俊278900亞裔優281-355-7990233RiceBlvd.Plus張毅389500亞裔優281-556-0544399SugarRd.Regular……3數據挖掘簡介你能判定他/她買計算機的可能性大不大嗎？姓名年齡收入學生信譽電話地址郵編買計算機張三234000是良281-322-03282714Ave.M77388買李四342800否優713-239-78305606HollyCr78766買王二701900否優281-242-32222000BellBlvd.70244不買趙五18900是良281-550-0544100MainStreet70244買劉蘭342500否優713-239-7430606HollyCt78566買楊俊278900否優281-355-7990233RiceBlvd.70388不買張毅389500否優281-556-0544399SugarRd.78244買……2022/12/134數據挖掘簡介我們擁有什么:Hugeamountofdata(GTE:1TB/day)我們需要什么:Informationandknowledge我們應該怎么辦:Datamining2022/12/135排名挖掘主題算法得票數發表時間作者陳述人1分類C4.5611993Quinlan,J.RHiroshiMotoda2聚類k-Means601967MacQueen,J.BJoydeepGhosh3統計學習SVM581995Vapnik,V.NQiangYang4關聯分析Apriori521994RakeshAgrawalChristosFaloutsos5統計學習EM482000McLachlan,GJoydeepGhosh6鏈接挖掘PageRank461998Brin,S.ChristosFaloutsos7集裝與推進AdaBoost451997Freund,Y.Zhi-HuaZhou8分類kNN451996Hastie,TVipinKumar9分類Na?veBayes452001Hand,D.JQiangYang10分類CART341984L.BreimanDanSteinberg數據挖掘10大算法ICDM2006Panel(會議的專題討論)共有145人選出了數據挖掘10大算法。建立分類模型的一般方法決策樹的用途新顧客（測試樣例），你能幫助公司將這位客人歸類嗎？即：你能預測這位顧客是屬于“買、不買”計算機的那一類？又：你需要多少有關這位客人的信息才能回答這個問題？計數年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優不買128中高否良買60老中否良買64老低是良買64老低是優不買64中低是優買128青中否良不買64青低是良買132老中是良買64青中是優買32中中否優買32中高是良買63老中否優不買1老中否優買2022/12/138決策樹的用途誰在買計算機？他/她會買計算機嗎？年齡？學生？信譽？買青中老否是優良不買買買不買計數年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優不買128中高否良買60老中否良買64老低是良買64老低是優不買64中低是優買128青中否良不買64青低是良買132老中是良買64青中是優買32中中否優買32中高是良買63老中否優不買1老中否優買2022/12/139決策樹的用途一棵很糟糕的決策樹收入？學生？青中否是高低中信譽？良優年齡？不買買買不買計數年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優不買128中高否良買60老中否良買64老低是良買64老低是優不買64中低是優買128青中否良不買64青低是良買132老中是良買64青中是優買32中中否優買32中高是良買63老中否優不買1老中否優買2022/12/1310決策樹的用途什么是決策樹Adecisiontreeisaflow-chart-liketreestructureEachinternalnodedenotesatestonanattributeEachbranchrepresentsanoutcomeofthetestLeafnodesrepresentclassesorclassdistributions.年齡？學生？信譽？買青中老否是優良不買買買不買2022/12/1311決策樹的建立決策樹建立的關鍵對測試樣例的信息期望(信息熵)信息期望的分析與計算平均信息期望信息期望的減少（信息增益）決策樹建立步驟（例）2022/12/1312補充：信息熵例子例如：桌子甲上有10個水果。其中，有2個為蘋果，有8個為橘子。桌子乙上有10個水果。其中，有5個為蘋果，有5個為橘子。從直觀上感覺:桌子甲上的水果分類比較集中于橘子。桌子乙上的水果分類，比較均勻。因此我們說桌子甲上的水果分類比較純。桌子乙上的水果分類比較混亂。2022/12/1313補充：信息熵熵——系統凌亂程度的度量。凌亂程度在同一個集合中，分類越集中于某一類，越不凌亂；分類越均勻分散于不同的類，則越凌亂。通俗說法：不確定性越大，熵也就越大；把它搞清楚所需要的信息量也就越大。2022/12/1314補充：關于某布爾分類的熵函數S為某正反樣例的樣例集（布爾分類）S的所有成員屬于同一類，Entropy(S)=0；S的正反樣例數量相等，Entropy(S)=1；S的正反樣例數量不等，熵介于0和1之間補充：更一般的熵定義更一般地，如果目標屬性具有c個不同的值，那么S相對于c個狀態的分類的熵定義為：其中，pi是S中屬于類別i的比例。如果目標屬性具有c個可能值，那么熵最大可能為log2c。補充：用信息增益度量期望的熵降低信息增益是定義屬性分類訓練數據的能力的度量標準。簡單地說，一個屬性的信息增益就是由于使用這個屬性分割樣例而導致的期望熵降低。更精確地講，一個屬性A相對樣例集合S的信息增益Gain(S,A)，被定義為：其中，Values(A)是屬性A所有可能值的集合，Sv是S中屬性A的值為v的子集。決策樹的建立--決策樹建立的關鍵建立一個好的決策樹的關鍵是決定樹根和子樹根的屬性樹根？計數年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優不買128中高否良買60老中否良買64老低是良買64老低是優不買64中低是優買128青中否良不買64青低是良買132老中是良買64青中是優買32中中否優買32中高是良買63老中否優不買1老中否優買2022/12/1318決策樹的建立--對測試樣例的信息期望信息期望？張三屬于哪一類？為了回答該問題，對張三的信息期望值是多少？年齡計數年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優不買128青中否良不買64青低是良買64青中是優買計數年齡收入學生信譽歸類：買計算機？128中高否良買64中低是優買32中中否優買32中高是良買計數年齡收入學生信譽歸類：買計算機？60老中否良買64老低是良買64老低是優不買132老中是良買63老中否優不買1老中否優買計數年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優不買128中高否良買60老中否良買64老低是良買64老低是優不買64中低是優買128青中否良不買64青低是良買132老中是良買64青中是優買32中中否優買32中高是良買63老中否優不買1老中否優買2022/12/1319決策樹的建立--對測試樣例的信息期望所需要研究的屬性為“分類屬性”假設該屬性共分m類，每一類的個數分別為

s1,s2…,sm令s=s1+s2+…+sm決定測試樣例所屬類別的信息期望：I(s1,s2…,sm)=-pi

log2(pi)其中pi

=si/si=1m2022/12/1320決策樹的建立--例分類屬性：買計算機？該屬性共分兩類(m=2):買/不買s1=641,s2=383

s=s1+s2=1024p1=s1/s=641/1024=0.6260

p2=s2/s=383/1024=0.3740I(s1,s2)=I(641,383)

=-(p1

log2(p1)+p2

log2(p2))

=0.95372022/12/1321決策樹的建立--對測試樣例的信息期望討論：“買”/“不買”計算機的人數之間的比例對于信息期望值的影響I(641,383)=0.9537I(512,512)=I(4,4)=1I(51,973)=I(973,51)=0.2856I(0,1024)=I(256,0)=0I(128,256)=0.9183I(257,127)=0.9157信息期望的數值與分類屬性中各類計數之間的比例有關信息期望的數值與計數總數無關2022/12/1322決策樹的建立--對測試樣例的信息期望例：分類屬性：加何種油？該屬性共分三類(m=3):Regular/Plus/Supremes1=13300,s2=7300,s3=5200

s=s1+s2+s3=25800p1=s1/s=13300/25800=0.5155

p2=s2/s=7300/25800=0.2829

p3=s3/s=5200/25800=0.2016I(s1,s2,s3)=I(13300,7300,5200)

=-(p1log2(p1)+p2log2(p2)+p3log2(p3))

=1.4739計數年齡收入種族信譽加何種油2000老低亞裔良Supreme1500老高白人良Regular3900中中西班牙良Plus3200中低非洲優Supreme5200青高白人優Regular1800青中亞裔優Plus2400青高亞裔良Regular2200青高非洲優Regular1600老中西班牙良Plus2000青高西班牙良Regular2022/12/1323決策樹的建立--對測試樣例的信息期望討論：三種汽油購買人數之間的比例對于需解決的信息量的影響

I(13300,7300,5200)=1.4739

I(25800,0,0)=0

I(0,10,0)=0

I(641,383,0)=0.9537

I(900,100,24)=0.6183

I(64,64,64)=1.5850當分類屬性的種類增加時，對測試樣例的信息期望通常也相應增加。2022/12/1324決策樹的建立--對測試樣例的信息期望信息期望？平均信息期望？年齡計數年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優不買128青中否良不買64青低是良買64青中是優買計數年齡收入學生信譽歸類：買計算機？128中高否良買64中低是優買32中中否優買32中高是良買計數年齡收入學生信譽歸類：買計算機？60老中否良買64老低是良買64老低是優不買132老中是良買63老中否優不買1老中否優買信息期望的減少？計數年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優不買128中高否良買60老中否良買64老低是良買64老低是優不買64中低是優買128青中否良不買64青低是良買132老中是良買64青中是優買32中中否優買32中高是良買63老中否優不買1老中否優買2022/12/1325決策樹的建立--對測試樣例的信息期望信息期望的減少(又稱Gain，信息增益)=信息期望–平均信息期望信息期望基于節點數據表平均信息期望基于該節點的所有直系分支數據表2022/12/1326決策樹的建立--對測試樣例的信息期望平均信息期望E，是節點各直系分支的信息期望值的加權總和。1.假定選擇年齡作樹根節點，則：

青年組:I(128,256)=0.9183

中年組:I(256,0)=0

老年組:I(257,127)=0.9157青年組比例:(128+256)/1024=0.375

中年組比例:256/1024=0.25

老年組比例:(257+127)/1024=0.375平均信息期望（加權總和）：

E(年齡）=0.375*0.9183

+0.25*0+0.375*0.9157=0.6877Gain(年齡)=I(641,383)-E(年齡)

=0.9537–0.6877=0.2660計數年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優不買128青中否良不買64青低是良買64青中是優買計數年齡收入學生信譽歸類：買計算機？128中高否良買64中低是優買32中中否優買32中高是良買計數年齡收入學生信譽歸類：買計算機？60老中否良買64老低是良買64老低是優不買132老中是良買63老中否優不買1老中否優買2022/12/1327決策樹的建立--對測試樣例的信息期望2. 假定選擇收入作樹根節點，則： 高收入組:I(160,128)=0.9911

中收入組:I(289,191)=0.9697

低收入組:I(192,64)=0.8113

高收入組比例:288/1024=0.2813

中收入組比例:480/1024=0.4687

低收入組比例:256/1024=0.25平均信息期望（加權總和）：E(收入）=0.2813*0.9911+0.4687*0.9697+0.25*0.8113=0.9361Gain(收入)：I(641,383)-E(收入)=0.9537–0.9361=0.01762022/12/1328決策樹的建立--對測試樣例的信息期望3. 假定選擇學生作樹根節點，則： 學生組:I(420,64)=0.5635

非學生組:I(221,319)=0.9761

學生組比例:484/1024=0.4727

非學生組比例:540/1024=0.5273平均信息期望（加權總和）：

E(學生）=0.4727*0.5635 +0.5273*0.9761=0.7811Gain(學生)：=I(641,383)-E(學生)=0.9537–0.7811=0.17262022/12/1329決策樹的建立--對測試樣例的信息期望4. 假定選擇信譽作樹根節點，則： 良好組:I(480,192)=0.8631

優秀組:I(161,191)=0.9948

良好組比例:672/1024=0.6563

優秀組比例:352/1024=0.3437平均信息期望（加權總和）：

E(信譽）=0.6563*0.8631+0.3437*0.9948 =0.9048Gain(信譽)：=I(641,383)-E(信譽) =0.9537–0.9048=0.04532022/12/1330決策樹的建立--對測試樣例的信息期望決定樹根節點E(年齡)=0.6877，Gain(年齡)=0.2660E(收入)=0.9361，Gain(收入)=0.0176E(學生)=0.7811，Gain(學生)=0.1726E(信譽)=0.9048，Gain(信譽)=0.04532022/12/1331決策樹的建立--決策樹建立步驟（例）年齡計數收入學生信譽歸類：買計算機？64高否良不買64高否優不買128中否良不買64低是良買64中是優買計數收入學生信譽歸類：買計算機？60中否良買64低是良買64低是優不買132中是良買63中否優不買1中否優買青中老樹葉計數收入學生信譽歸類：買計算機？128高否良買64低是優買32中否優買32高是良買2022/12/1332決策樹的建立--決策樹建立步驟（例）年齡計數收入學生信譽歸類：買計算機？64高否良不買64高否優不買128中否良不買64低是良買64中是優買計數收入學生信譽歸類：買計算機？60中否良買64低是良買64低是優不買132中是良買63中否優不買1中否優買青中老買2022/12/1333決策樹的建立--青年組數據表分析（例）1.假定選擇收入作節點I(128,256)=0.9183E(收入）=0.3333*0+0.5*0.9183+0.1667*0=0.4592Gain(收入)=I(128,256)-E(收入)=0.9183–0.4592=0.4591I(0,128)=0

比例:128/384=0.3333I(64,128)=0.9183

比例:192/384=0.5I(64,0)=0

比例:64/384=0.1667計數收入學生信譽歸類：買計算機？64高否良不買64高否優不買128中否良不買64低是良買64中是優買計數收入學生信譽歸類：買計算機？64高否良不買64高否優不買計數收入學生信譽歸類：買計算機？128中否良不買64中是優買計數收入學生信譽歸類：買計算機？64低是良買2022/12/1334決策樹的建立--青年組數據表分析（例）2.假定選擇學生作節點I(128,256)=0.9183E(學生）=0.3333*0+0.6667*0=0Gain(學生)=I(128,256)-E(學生)=0.9183–0=0.9183I(128,0)=0

比例:128/384=0.3333I(0,256)=0

比例:256/384=0.6667結論:不需要考慮屬性信譽，決定選擇屬性學生計數收入學生信譽歸類：買計算機？64高否良不買64高否優不買128中否良不買64低是良買64中是優買計數收入學生信譽歸類：買計算機？64高否良不買64高否優不買128中否良不買計數收入學生信譽歸類：買計算機？64低是良買64中是優買2022/12/1335決策樹的建立--決策樹建立步驟（例）年齡計數收入信譽歸類：買計算機？64低良買64中優買計數收入學生信譽歸類：買計算機？60中否良買64低是良買64低是優不買132中是良買63中否優不買1中否優買青中老買學生計數收入信譽歸類：買計算機？64高良不買64高優不買128中良不買否是樹葉2022/12/1336決策樹的建立--決策樹建立步驟（例）年齡計數收入學生信譽歸類：買計算機？60中否良買64低是良買64低是優不買132中是良買63中否優不買1中否優買青中老買學生否是買不買2022/12/1337決策樹的建立--老年組數據表分析（例）1.假定選擇收入作節點I(257,127)=0.9157E(收入）=0.3333*1+0.6667*0.8050=0.8700Gain(收入)=I(257,127)-E(收入)=0.9157–0.8700=0.0457I(64,64)=1

比例:128/384=0.3333I(193,63)=0.8050

比例:256/384=0.6667計數收入學生信譽歸類：買計算機？60中否良買64低是良買64低是優不買132中是良買63中否優不買1中否優買計數收入學生信譽歸類：買計算機？60中否良買132中是良買63中否優不買1中否優買計數收入學生信譽歸類：買計算機？64低是良買64低是優不買2022/12/1338決策樹的建立--老年組數據表分析（例）2.假定選擇學生作節點I(257,127)=0.9157E(學生）=0.6771*0.8051+0.3229*0.9998=0.8680Gain(學生)=I(257,127)-E(學生)=0.9157–0.8680=0.0477I(196,64)=0.8051

比例:260/384=0.6771I(61,63)=0.9998

比例:124/384=0.3229計數收入學生信譽歸類：買計算機？60中否良買64低是良買64低是優不買132中是良買63中否優不買1中否優買計數收入學生信譽歸類：買計算機？60中否良買63中否優不買1中否優買計數收入學生信譽歸類：買計算機？64低是良買64低是優不買132中是良買2022/12/1339決策樹的建立--老年組數據表分析（例）3.假定選擇信譽作節點I(257,127)=0.9157E(信譽）=0.6667*0+0.3333*0.0659=0.0220Gain(信譽)=I(257,127)-E(信譽)=0.9157–0.0220=0.8937I(256,0)=0

比例:256/384=0.6667I(1,127)=0.0659

比例:128/384=0.3333結論:決定選擇屬性信譽計數收入學生信譽歸類：買計算機？60中否良買64低是良買64低是優不買132中是良買63中否優不買1中否優買計數收入學生信譽歸類：買計算機？64低是優不買63中否優不買1中否優買計數收入學生信譽歸類：買計算機？60中否良買64低是良買132中是良買2022/12/1340決策樹的建立--決策樹建立步驟（例）年齡計數收入學生歸類：買計算機？60中否買64低是買132中是買青中老買學生否是買不買信譽計數收入學生歸類：買計算機？64低是不買63中否不買1中否買優良樹葉2022/12/1341決策樹的建立--決策樹建立步驟（例）年齡青中老買學生否是買不買信譽計數收入學生歸類：買計算機？64低是不買63中否不買1中否買優良買……2022/12/1342決策樹算法流程（ID3）選擇節點分裂屬性；建立新節點，劃分數據集；判斷節點是否到生長停止條件，如果是，終止生長，如果不是，轉到第1步。樹停止生長條件節點內的數據已經完全屬于同一類別。節點內測數據樣本數低于某一閾值。所有屬性都已經被分裂過。從ID3到C4.5從ID3到C4.5共同之處：通過自頂向下構造決策樹進行學習；構造過程的開始：哪一個屬性將在樹的根節點被測試？區別：選擇測試屬性時的準則ID3:增益準則(Gaincriterion)—衡量給定屬性區分訓練樣例的能力。C4.5:增益率準則(Gainratiocriterion)44ID3信息增益存在的問題由劃分個數引起的偏置問題當某個屬性具有取值越多=>劃分越多=>分塊越小，數據純度可能越高=>進而引起偏置問題當某個屬性具有多個取值時，信息增益度量會賦予該屬性的有用程度一個不適當的指示。ID3信息增益存在的問題在極端情況下，比如在是否打高爾夫球的例子中，“日期”這個屬性。對于每個實例都取得不同的值。這個屬性所形成的劃分，使得每個子集都僅有一個實例。根據信息增益的定義，“日期”這個屬性將會有信息增益度量值會最高。而實際上，這個屬性可能是無關或者無用的。46C4.5信息增益率設樣本集S按離散屬性F的V個不同的取值劃分為S1…Sv共V個子集定義Split(S,F)：則用F對S進行劃分的信息增益率為：C4.5例屬性穿衣指數溫度濕度風力天氣舒適度1較多35701不舒適2較多33787不舒適3較多34804不舒適4正常32850舒適5正常33855舒適6很多25902不舒適7很多24883不舒適8很多30501舒適9很多32606不舒適10較多26860不舒適48C4.5例分類屬性：天氣舒適度？該屬性共分兩類(m=2):舒適/不舒適s1=3,s2=7

s=s1+s2=10p1=s1/s=0.3

p2=s2/s=0.7I(s1,s2)=I(3,7)

=-(p1

log2(p1)+p2

log2(p2))

=0.8812022/12/1349C4.5例假定選擇穿衣指數作樹根節點，則： 較多組:I(4,0)=0

正常組:I(2,0)=0

很多組:I(3,1)=-3/4log2(3/4)-1/4log2(1/4)=0.8113

較多組比例:4/10

正常組比例:2/10

很多組比例:4/10平均信息期望（加權總和）：E(穿衣指數)=0+0+0.4*0.8113=0.3252022/12/1350C4.5例Gain(穿衣指數)I(3,7)–E(穿衣指數)=0.881–0.325=0.556Split_infor(穿衣指數,S)=-4/10log2(4/10)-4/10log2(4/10)-2/10log2(2/10)=1.522GainRatio(穿衣指數,S)=0.556/1.522=0.36532022/12/1351C4.5例－選劃分點24252630323233333435屬性穿衣指數溫度濕度風力天氣舒適度1較多35701不舒適2較多33787不舒適3較多34804不舒適4正常32850舒適5正常33855舒適6很多25902不舒適7很多24883不舒適8很多30501舒適9很多32606不舒適10較多26860不舒適2022/12/1352C4.5例－選劃分點24252630323233333435E(溫度<=24,S)=-9/10*(3/9*log2(3/9)+6/9*log2(6/9))=0.8265Gain(溫度<=24,S)I(3,7)–E(溫度)=0.881-0.8265=0.0545Split_infor(溫度<=24,S)=-9/10*log2(9/10)-1/10*log2(1/10)=0.469GainRatio(溫度<=24,S)=0.0545/0.469

=0.11622022/12/1353C4.5例－選劃分點24252630323233333435屬性穿衣指數溫度濕度風力天氣舒適度1較多35701不舒適2較多33787不舒適3較多34804不舒適4正常32850舒適5正常33855舒適6很多25902不舒適7很多24883不舒適8很多30501舒適9很多31606不舒適10較多26860不舒適2022/12/1354C4.5例－選劃分點24252630323233333435E(溫度<=26,S)=-3/10*(3/3*log2(3/3)+0/3)-7/10*(3/7*log2(3/7)+4/7*log2(4/7))=0.6897Gain(溫度<=26,S)I(3,7)–E(溫度)=0.881-0.6897=0.1913Split_infor(溫度<=26,S)=-3/10*log2(3/10)-7/10*log2(7/10)=0.8813GainRatio(溫度<=26,S)=0.1913/0.8813

=0.21712022/12/1355C4.5例－選劃分點GainRatio(溫度<=24,S)=0.12;GainRatio(溫度<=25,S)=0.16;GainRatio(溫度<=26,S)=0.217;GainRatio(溫度<=30,S)=0.006;GainRatio(溫度<=32,S)=0.0057;GainRatio(溫度<=33,S)=0.16;GainRatio(溫度<=34,S)=0.12;因此，溫度26為溫度的最佳劃分點；信息增益率為0.217.56C4.5例－選屬性屬性“濕度”的信息增益率GainRatio(濕度<=50,S)=0.42.屬性“風力”的信息增益率；GainRatio(風力<=1,S)=0.21.GainRatio(濕度<50,S)最大，所以選擇濕度作為根節點，最佳劃分點為濕度為50%.57C4.5比ID3的改進1)用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足；

2)能夠完成對連續屬性的離散化處理；

3)在樹構造過程中進行剪枝；

4)能夠對不完整數據進行處理。C4.5算法優點：產生的分類規則易于理解，準確率較高。C4.5算法缺點：在構造樹的過程中，需要對數據集進行多次的順序掃描和排序，因而導致算法的低效。福建省粒計算及其應用重點實驗室趙紅2014年9月C4.5示例

WekaJ48C4.5示例數據：weka中的weather數據（字符型、數值型）Arff文件outlook,temperature,humidity,windy,playsunny,hot,high,FALSE,nosunny,hot,high,TRUE,noovercast,hot,high,FALSE,yesrainy,mild,high,FALSE,yesrainy,cool,normal,FALSE,yesrainy,cool,normal,TRUE,noovercast,cool,normal,TRUE,yes