1、2022/8/3Guilin1決策樹分類器朱曉峰2022/8/3Guilin2數(shù)據(jù)庫知識發(fā)現(xiàn)技術(shù)數(shù)據(jù)預(yù)處理：屬性約簡，缺失值填充關(guān)聯(lián)規(guī)則分類或預(yù)測聚類可視化分析2022/8/3Guilin3什么叫分類？分類是一個古老的方法、現(xiàn)代熱門的課題已知數(shù)據(jù)的集合D：數(shù)據(jù)被標記學(xué)習(xí)：從數(shù)據(jù)集合中歸納出規(guī)則、規(guī)律等，通常稱為分類器，或模型預(yù)測：用分類器預(yù)測新數(shù)據(jù)的類這種從有標記的數(shù)據(jù)種歸納分類器的方法叫監(jiān)督學(xué)習(xí)決策樹、回歸是最常用的分類器分類任務(wù)圖例分類任務(wù)例子Predicting tumor cells as benign or malignantClassifying credit card trans

2、actions as legitimate or fraudulentClassifying secondary structures of protein as alpha-helix, beta-sheet, or random coilCategorizing news stories as finance, weather, entertainment, sports, etc分類技術(shù)Decision Tree based MethodsRule-based MethodsMemory based reasoningNeural NetworksNave Bayes and Bayes

3、ian Belief NetworksSupport Vector Machines2022/8/3Guilin7決策樹分類器/模型學(xué)習(xí)將已知數(shù)據(jù)集合分成訓(xùn)練數(shù)據(jù)集合測試集合學(xué)習(xí)：從一個訓(xùn)練數(shù)據(jù)集合歸納出一棵決策樹：從完全空間搜索一棵最佳樹的過程預(yù)測：用決策樹分類新數(shù)據(jù)決策樹是最常用的分類器之一不要求任何知識或參數(shù)設(shè)定它是一種監(jiān)督學(xué)習(xí)方法一棵決策樹可以表示成一組規(guī)則2022/8/3Guilin8決策樹的結(jié)構(gòu)決策樹是層次的樹結(jié)構(gòu)由一些節(jié)點和枝（邊）組成，一棵決策樹至少有一個節(jié)點枝的兩端是節(jié)點一棵決策樹通常是從左到右，或從上到下畫圖樹的第一個節(jié)點稱為根節(jié)點，“根-枝-節(jié)點-.節(jié)點”的最后一個節(jié)點是

4、葉節(jié)點，其它節(jié)點叫中間節(jié)點非葉節(jié)點至少有一條枝2022/8/3Guilin9決策樹分類器的解釋一棵決策樹是訓(xùn)練數(shù)據(jù)的一個劃分樹的一個非葉節(jié)點是對一個屬性上的測試一個屬性的一條枝是測試該屬性的一個結(jié)果一個葉節(jié)點是一個類標記在每個非葉節(jié)點，一個屬性被選中，它將訓(xùn)練數(shù)據(jù)分裂成盡可能不同類的子集合（劃分）對于一個新數(shù)據(jù)，根據(jù)它的每個屬性值從根節(jié)點一直匹配到葉節(jié)點，這個葉節(jié)點的標記就用來預(yù)測新數(shù)據(jù)的類2022/8/3Guilin10構(gòu)造決策樹分類器的原則目標：最大化預(yù)測新數(shù)據(jù)的精度（實現(xiàn)困難）通常將給定的已知數(shù)據(jù)隨機分成訓(xùn)練集合和測試集合。訓(xùn)練數(shù)據(jù)用于歸納分類器，測試數(shù)據(jù)用來評估分類器訓(xùn)練分類器時的目標

5、是最大化預(yù)測測試數(shù)據(jù)的精度，即，該分類器基本上體現(xiàn)兩個（訓(xùn)練和測試）集合的共同結(jié)構(gòu)過度擬合（overfitting）問題：擬合訓(xùn)練數(shù)據(jù)的效果很好，擬合測試數(shù)據(jù)的效果很差2022/8/3Guilin11舉例說明（訓(xùn)練數(shù)據(jù)）2022/8/3Guilin12舉例說明（決策樹）2022/8/3Guilin13舉例說明（測試數(shù)據(jù)）決策樹是用于預(yù)測一個數(shù)據(jù)的類問題：Alex, Buddy and Cheery使用哪種交通工具？2022/8/3Guilin14舉例說明（決策樹的運用）從根節(jié)點Travel cost per km開始如果Travel Cost = expensive，Transportatio

6、n mode = car如果Travel Cost = standard，Transportation mode = train如果Travel Cost = cheap，決策樹需要檢查下一個節(jié)點Gender如果Gender = male，Transportation mode = bus如果Gender = female，決策樹需要檢查下一個節(jié)點Car ownership如果Car ownership = 0，Transportation mode = bus，否則Transportation mode = train 2022/8/3Guilin15舉例說明（決策樹）2022/8/3Gui

7、lin16舉例說明（決策樹產(chǎn)生的規(guī)則）每個葉節(jié)點產(chǎn)生一條規(guī)則Rule 1：If Travel cost = expensive then Mode = car Rule 2：If Travel cost = standard then Mode = train Rule 3：If Travel cost = cheap Gender = male then Mode = bus Rule 4：If Travel cost = cheap Gender = female Car ownership = 0 then Mode = bus Rule 5：If Travel cost = cheap

8、 Gender = female Car ownership = 1 then Mode = train2022/8/3Guilin17舉例說明（預(yù)測）根據(jù)上面的決策樹或者規(guī)則，回答前面的問題就很簡單、直接Alex：Travel cost = standard，所以，無論其它屬性取什么值，可以預(yù)測他的交通工具是trainBuddy：Travel cost = cheap并且Gender = male，則可以預(yù)測他的交通工具是bus Cherry：Travel cost = cheap并且Gender = female 并且Car ownership = 1，則可以預(yù)測他的交通工具是train2

9、022/8/3Guilin18決策樹的缺點多數(shù)決策樹算法采用貪心策略：按照設(shè)定的啟發(fā)式信息搜索最佳樹無回溯非窮近搜索，但可能剪枝2022/8/3Guilin19如何建構(gòu)決策樹？決策樹很簡單，但實現(xiàn)建構(gòu)一棵好的樹是很困難的在上面的例子中，屬性Income level沒有用于交通工具的分類建構(gòu)一棵樹通常的辦法（啟發(fā)式信息）是度量數(shù)據(jù)集的不純度（impurity）EntropyGini indexClassification error 2022/8/3Guilin20不純度的定義給定一個訓(xùn)練數(shù)據(jù)集（決策表），我們能根據(jù)類屬性度量它的同構(gòu)性（或異構(gòu)性heterogeneity）如果一個訓(xùn)練數(shù)據(jù)集的類

10、屬性只取一個類值，它是純的或者同構(gòu)的如果一個訓(xùn)練數(shù)據(jù)集的類屬性取多個類值，它是不純的或者異構(gòu)的2022/8/3Guilin21如何度量不純度有多種量化方法度量不純度最常用的三種方法如下 上面所有的度量方法都含有類j的概率pj2022/8/3Guilin22舉例說明（訓(xùn)練數(shù)據(jù)）2022/8/3Guilin23舉例說明（類的頻率）在訓(xùn)練數(shù)據(jù)集合中，類屬性Transportation mode有三個類值Bus、Car和Train我們的例子中，每個值出現(xiàn)的次數(shù)如下 4 buses3 cars 3 trains 簡單記為4B, 3C, 3T總數(shù)據(jù)量是10個標記的例子 2022/8/3Guilin24舉例

11、說明（計算概率）根據(jù)上面的數(shù)據(jù)，每個類的概率如下：p(Bus) = 4 / 10 = 0.4 p(Car) = 3 / 10 = 0.3 p(Train) = 3 / 10 = 0.3注意，在上面的概率計算中，我們只考慮了類屬性Transportation mode，其它屬性都不考慮有了每個類的概率，我們就可以用前面的方法計算訓(xùn)練數(shù)據(jù)集合的不純度2022/8/3Guilin25舉例說明（用熵計算概率） 計算訓(xùn)練數(shù)據(jù)集合的不純度的一個方法就是采用熵（entropy）已知p(Bus) = 0.4, p(Car) = 0.3和p(Train) = 0.3，熵的計算如下：Entropy = 0.4 l

12、og (0.4) 0.3 log (0.3) 0.3 log (0.3) = 1.571 對數(shù)的底是22022/8/3Guilin26熵的性質(zhì)一個純的訓(xùn)練數(shù)據(jù)集合（只有一個類）的熵是0，這是因為概率1的對數(shù)log (1) = 0在多個類的情況下，熵在每個類的概率相等時達到最大值下面的圖描出了不同的類個數(shù)n的熵的最大值，這里，p=1/n熵的最大值是-n*p*log p注意：當類個數(shù)n2時，熵12022/8/3Guilin27圖示熵的性質(zhì)2022/8/3Guilin28舉例說明（用Gini索引計算概率）計算訓(xùn)練數(shù)據(jù)集合的不純度的第二個方法是采用Gini索引（Gini index） 已知p(Bus)

13、 = 0.4, p(Car) = 0.3和p(Train) = 0.3， Gini索引值的計算如下：Gini Index = 1 (0.42 + 0.32 + 0.32) = 0.660 2022/8/3Guilin29Gini索引的性質(zhì)一個純的訓(xùn)練數(shù)據(jù)集合（只有一個類）的Gini索引值是0，這是因為概率1的Gini索引值是1-(1)2 = 0與熵一樣， Gini索引在每個類的概率相等時達到最大值下面的圖描出了不同的類個數(shù)n的Gini索引的最大值，這里，p=1/n注意：無論有多少個類值，Gini索引值總是在0和1之間2022/8/3Guilin30圖示Gini索引的性質(zhì)2022/8/3Guil

14、in31舉例說明（用分類誤差計算概率）計算訓(xùn)練數(shù)據(jù)集合的不純度的第三個方法是采用分類誤差（classification error）已知p(Bus) = 0.4, p(Car) = 0.3和p(Train) = 0.3，分類誤差值的計算如下：Classification_Error = 1 Max0.4, 0.3, 0.3 = 1 - 0.4 = 0.60 2022/8/3Guilin32分類誤差的性質(zhì)與熵和Gini索引一樣，一個純的訓(xùn)練數(shù)據(jù)集合（只有一個類）的分類誤差值是0，這是因為概率1的分類誤差值是1-max(1) = 0分類誤差值總是在0和1之間對于給定類的個數(shù)， Gini索引的最大值

15、總是與分類誤差的最大值相等設(shè)每個類的概率為p=1/n，Gini索引的最大值是1-n*(1/n)2 = 1-1/n，而分類誤差的最大值也是1-max1/n =1-1/n 2022/8/3Guilin33決策樹算法的運行方式這里解釋決策樹算法的運行方式設(shè)一個訓(xùn)練數(shù)據(jù)集合D有多個屬性和一個類屬性對于D，取出每個屬性和類屬性形成一個子集合如果有m個屬性，我們就從D構(gòu)造出m個子集合 設(shè)第i個屬性的子集合為Si 這里，D 是Si的父親2022/8/3Guilin34舉例說明（訓(xùn)練數(shù)據(jù)）2022/8/3Guilin35舉例說明（訓(xùn)練數(shù)據(jù)的子集合）S1 S2 S3 S42022/8/3Guilin36取多值的

16、屬性對于屬性i的 Si表（子集合），我們需要分別計算每個屬性i的不純度 例如，屬性Travel cost有三個值：Cheap, Standard和Expensive 它應(yīng)該分成三個表（子集合）2022/8/3Guilin37屬性Travel cost與三個表Travel Costs: Cheap Standard Expensive 2022/8/3Guilin38信息增益（information gain） 選擇分裂數(shù)據(jù)集D的屬性，需要比較D和各個子集合Si之間的不純度差異數(shù)據(jù)集D和子集合Si的不純度之差異被稱為信息增益（information gain）所以，需要計算每個屬性的信息增益值2

17、022/8/3Guilin39信息增益計算方法一個屬性的信息增益是它產(chǎn)生的子集合的父集合的不純度與該子集合的不純度之差該子集合的不純度是它分解的表的不純度的加權(quán)之和，權(quán)值一般是每個表所占的比例對于熵方法，屬性i的信息增益計算如下Information gain(i) = i的父集合的熵 (ki/n * Si產(chǎn)生的表ki的熵) 2022/8/3Guilin40屬性Travel Cost的信息增益對于訓(xùn)練數(shù)據(jù)集D，我們有三個類4B、3C、3T，D的熵是1.571對于屬性Travel Cost，它產(chǎn)生的子集合可以分成如下三個表 值Cheap有兩個類4B, 1T，它的熵是0.722值Standard有

18、一個類2T，它的熵是0值Expensive有一個類，它的熵是0屬性Travel Cost的信息增益是1.571 (5/10 * 0.722+2/10*0+3/10*0) = 1.210 2022/8/3Guilin41屬性Travel Cost按三種方法計算的信息增益同樣，我們也可以用Gini索引和分類誤差計算屬性Travel Cost的信息增益采用三種方法計算出屬性Travel Cost的信息增益如下Entropy: 1.210Gini Index: 0.500Classification Error: 0.500 2022/8/3Guilin42屬性Gender按三種方法計算的信息增益采用

19、三種方法計算出屬性Gender的信息增益如下Entropy: 0.125Gini Index: 0.060Classification Error: 0.100 2022/8/3Guilin43屬性Car Ownership按三種方法計算的信息增益采用三種方法計算出屬性Car Ownership的信息增益如下Entropy:0.534Gini Index:0.207Classification Error:0.200 2022/8/3Guilin44屬性Income Level按三種方法計算的信息增益采用三種方法計算出屬性Income Level的信息增益如下Entropy:0.695Gini

20、 Index:0.293Classification Error:0.300 2022/8/3Guilin45分裂屬性選擇的標準在決策樹構(gòu)建中，哪個屬性是目前最好的？產(chǎn)生最小樹的屬性啟發(fā)式: 選擇產(chǎn)生最純的屬性常用的度量：信息增益策略：選擇信息增益最大的屬性為分裂數(shù)據(jù)集合的屬性2022/8/3Guilin46選擇第一個分裂屬性有了所有屬性的信息增益后，我們就可以找出信息增益最大的那個屬性：i* = argmax information gain of attribute i在我們的例子中，屬性Travel Cost產(chǎn)生的信息增益最大該屬性作為決策樹的當前節(jié)點因為它是第一個節(jié)點，它就是決策樹的根

21、節(jié)點一棵決策樹可以只有一個節(jié)點 2022/8/3Guilin47用屬性Travel Cost分裂訓(xùn)練數(shù)據(jù)集 一個分裂屬性選定后，我們可以根據(jù)該屬性將當前的數(shù)據(jù)集合分裂成多個子集合在我們的例子中，我們根據(jù)Travel Cost的取值分列D訓(xùn)練數(shù)據(jù)集合D被分裂成三個子集合2022/8/3Guilin48用屬性Travel Cost分裂訓(xùn)練數(shù)據(jù)集的結(jié)果數(shù)據(jù)被分裂后，我們有 Travel Cost = Expensive只有一個類CarTravel Cost = Standard只有一個類TrainTravel Cost = Cheap需要進一步分裂產(chǎn)生純類（只含一個類）的屬性值總是作為決策樹的葉節(jié)點

22、這樣就完成了決策樹構(gòu)造的第一個循環(huán) 2022/8/3Guilin49訓(xùn)練數(shù)據(jù)集的三個子集合2022/8/3Guilin50用屬性Travel Cost產(chǎn)生的樹2022/8/3Guilin51第二次循環(huán)屬性值Expensive和Standard是純類，不再需要分裂當Travel Cost = Cheap，它有多個類，需要繼續(xù)分裂將相應(yīng)的表中的數(shù)據(jù)作為待分裂的數(shù)據(jù)，開始第二次循環(huán) 2022/8/3Guilin52為第二次循環(huán)產(chǎn)生數(shù)據(jù)集合2022/8/3Guilin53Cheap連接的節(jié)點的數(shù)據(jù)集合的不純度現(xiàn)在只有三個屬性 Gender、car ownership、Income levelCheap

23、連接的節(jié)點的數(shù)據(jù)集合的不純度如下2022/8/3Guilin54屬性Gender按三種方法計算的信息增益采用三種方法計算出屬性Gender的信息增益如下Entropy:0.322Gini Index:0.120Classification Error:0.0002022/8/3Guilin55其它屬性按三種方法計算的信息增益采用三種方法計算出屬性Car Ownership的信息增益如下Entropy:0.171Gini Index:0.053Classification Error:0.000采用三種方法計算出屬性Income Level的信息增益如下Entropy:0.171Gini Ind

24、ex:0.053Classification Error:0.0002022/8/3Guilin56為第二次循環(huán)選擇分裂屬性通過比較屬性Gender的信息增益最大當前的數(shù)據(jù)集合將按照屬性Gender的取值分裂在我們的例子中，屬性值Male 只有一個類Bus，屬性值Female有多個類，需要繼續(xù)分裂 2022/8/3Guilin57第二次循環(huán)的數(shù)據(jù)集合分裂2022/8/3Guilin58第二次循環(huán)產(chǎn)生的樹2022/8/3Guilin59用屬性Gender分裂子數(shù)據(jù)集的結(jié)果節(jié)點Gender有兩個值 MaleFemale屬性值Male是純的類，是葉節(jié)點屬性值Female有多個類，需要在下一個循環(huán)繼續(xù)

25、分裂2022/8/3Guilin60第三次循環(huán)第三次循環(huán)的數(shù)據(jù)是第二次循環(huán)留待分的數(shù)據(jù)集合屬性值Female的數(shù)據(jù)剩下可以考慮的屬性只有兩個 Car ownership Income level 2022/8/3Guilin61為第三次循環(huán)產(chǎn)生數(shù)據(jù)集合2022/8/3Guilin62Female連接的節(jié)點的數(shù)據(jù)集合的不純度只有兩個記錄兩個記錄有不同的類如果選用屬性car ownership作為分裂屬性，我們將得到兩個純類的子集合同樣，如果選用屬性income level作為分裂屬性，我們也將得到兩個純類的子集合所以，任意選一個即可，不需要計算信息增益值假設(shè)我們選用屬性car ownership

26、，我們得到一顆決策樹，循環(huán)結(jié)束 2022/8/3Guilin63建立的決策樹2022/8/3Guilin64評估技術(shù)Holdout: 訓(xùn)練集合/測試集合 數(shù)據(jù)集合很大時較好k-fold交叉驗證: 將數(shù)據(jù)集合分成k子集合在每次建樹時，使用一個子集合作為測試集合，其它k-1子集合一起作為訓(xùn)練集合 用這k次結(jié)果的均值作為參照它消除了訓(xùn)練集合/測試集合方法的隨機性2022/8/3Guilin6565 交叉驗證圖解數(shù)據(jù)集合分成k段 一個做測試，其它的用來訓(xùn)練分類器 重復(fù)到Testiteration2022/8/3Guilin66增益率增益率（Gain ratio）：是信息增益的一個改良版，它可以減少信息

27、增益偏好于取值較多的屬性增益率考慮分支數(shù)目和分枝的大小它通過內(nèi)在信息改良信息增益值也稱為分裂率內(nèi)在信息：分支里的記錄分布的熵2022/8/3Guilin67增益率的定義增益率一般是數(shù)據(jù)均勻分布時很大數(shù)據(jù)集中于某個枝時很小增益率（Quinlan86)）標準化信息增益2022/8/3Guilin68有關(guān)決策樹分類器的研究問題分裂屬性選擇標準過度擬合（Overfitting）低度擬合（Underfitting）評估技術(shù)非均勻數(shù)據(jù)/類（Imbalanced data/classes）多標記學(xué)習(xí)半監(jiān)督分類2022/8/3Guilin69Summary決策樹的定義決策樹的使用如何建樹分裂屬性選擇不純度信息

28、增益評估技術(shù)相關(guān)的研究問題2022/8/3Guilin70參考目錄D. LU and Q. WENG，（2007），A survey of image classification methods and techniques for improving classification performance，International Journal of Remote Sensing，Vol. 28, No. 5, 10 March 2007, 823870。F. Zeng and Z. Qiu (2004) A survey of classification learning algor

29、ithm, ICSP 04. Thair Nu Phyu （2009）Survey of Classification Techniques in Data Mining，IMECS 2009, C. Aggarwal and C. Zhai （2012） A Survey of Text Classification Algorithms，Mining Text Data，2012, pp 163-222Zhengzheng Xing, Jian Pei, Eamonn J. Keogh: A brief survey on sequence classification. SIGKDD Explorations 12(1): 40-48 (2010)Shehroz S. Khan,