數(shù)據(jù)挖掘最新精品課程完整課件數(shù)據(jù)分類決策樹

1、數(shù)據(jù)(shj)分類-決策樹共七十二頁目錄(ml)基本概念決策樹ID3算法(sun f)決策樹C4.5算法2共七十二頁學習(xux)目標1.掌握(zhngw)數(shù)據(jù)分類的基本原理和評價指標2.了解兩種決策樹算法3共七十二頁4Part I數(shù)據(jù)(shj)分類的基本概念共七十二頁定義(dngy)數(shù)據(jù)分類是指把數(shù)據(jù)樣本映射到一個事先定義的類中的學習過程即給定一組輸入的屬性向量及其對應(yīng)的類，用基于歸納的學習算法得出分類分類問題是數(shù)據(jù)挖掘領(lǐng)域中研究和應(yīng)用最為廣泛的技術(shù)之一，如何更精確、更有效地分類一直是人們追求的目標數(shù)據(jù)分類的任務(wù)(rn wu)通過學習得到一個目標函數(shù)f，把每個屬性集x映射到一個預(yù)先定義的類標

2、號y5共七十二頁分類(fn li)的示例兩類分類示例銀行業(yè)：區(qū)分高端信用卡和低端信用卡醫(yī)療診斷：區(qū)分正常細胞和癌細胞互聯(lián)網(wǎng)：區(qū)分正常郵件和垃圾郵件多類分類示例油氣傳輸：區(qū)分行人走過、汽車碾過、鎬刨、電鉆等行為文字識別：區(qū)分不同(b tn)的字符（其中漢字識別是一個大類別問題）社會網(wǎng)絡(luò)：區(qū)分中心用戶、活躍用戶、不活躍用戶、馬甲用戶等6共七十二頁示例(shl)數(shù)據(jù)集數(shù)據(jù)集包含多個描述屬性和一個類別屬性一般來說描述屬性：連續(xù)值或離散值類別屬性：只能(zh nn)是離散值（目標屬性連續(xù)對應(yīng)回歸問題）7AgeSalaryClass30highc125highc221lowc243highc118lowc

3、233lowc1.共七十二頁分類(fn li)問題的形式化描述8共七十二頁分類(fn li)的過程9獲取數(shù)據(jù)預(yù)處理分類(fn li)決策分類器設(shè)計共七十二頁獲取數(shù)據(jù)數(shù)值型數(shù)據(jù)病例中的各種化驗數(shù)據(jù)空氣質(zhì)量監(jiān)測數(shù)據(jù)描述性數(shù)據(jù)人事部門檔案資料圖片型數(shù)據(jù)指紋、掌紋自然場景圖片很多情況下，需要(xyo)將上述數(shù)據(jù)統(tǒng)一轉(zhuǎn)換為數(shù)值型數(shù)據(jù)序列，即形成特征向量（特征提?。?0共七十二頁預(yù)處理為了提高分類的準確性和有效性，需要對分類所用的數(shù)據(jù)進行預(yù)處理去除(q ch)噪聲數(shù)據(jù)對空缺值進行處理數(shù)據(jù)降維（特征選擇）-（PCA、LDA） 主成分分析 （ Principal Component Analysis ， PC

4、A ） 線性鑒別分析(LinearDiscriminantAnalysis,LDA)，有時也稱Fisher線性判別(FisherLinearDiscriminant,FLD)，這種算法是RonaldFisher于1936年發(fā)明的，是模式識別的經(jīng)典算法。11共七十二頁分類器設(shè)計(shj)1-劃分數(shù)據(jù)集給定帶有類標號的數(shù)據(jù)集，并且(bngqi)將數(shù)據(jù)集劃分為兩個部分訓練集（training set）測試集（testing set）劃分策略1.當數(shù)據(jù)集D的規(guī)模較大時 訓練集2|D|/3，測試集是1|D|/32.當數(shù)據(jù)集D的規(guī)模不大時 n交叉驗證法（n-fold validation）將數(shù)據(jù)集隨機地劃

5、分為n組之后執(zhí)行n次循環(huán)，在第i次循環(huán)中，將第i組數(shù)據(jù)樣本作為測試集，其余的n-1組數(shù)據(jù)樣本作為訓練集,最終的精度為n個精度的平均值。12共七十二頁3.當數(shù)據(jù)集D的規(guī)模非常(fichng)小時每次交叉驗證時，只選擇一條測試數(shù)據(jù)(shj)，剩余的數(shù)據(jù)(shj)均作為訓練集。原始數(shù)據(jù)集有m條數(shù)據(jù)時，相當于m-次交叉驗證。是N-次交叉驗證的一個特例。 共七十二頁分類器設(shè)計(shj)2-分類器構(gòu)造利用訓練集構(gòu)造分類器（分類模型）通過分析由屬性描述的每類樣本的數(shù)據(jù)信息，從中總結(jié)出分類的規(guī)律性，建立(jinl)判別公式或判別規(guī)則在分類器構(gòu)造過程中，由于提供了每個訓練樣本的類標號，這一步也稱作監(jiān)督學習（su

6、pervised learning）14共七十二頁分類器設(shè)計(shj)3-分類器測試利用測試(csh)集對分類器的分類性能進行評估，具體方式是首先，利用分類器對測試集中的每一個樣本進行分類其次，將分類得到的類標號和測試集中數(shù)據(jù)樣本的原始類標號進行對比由上述過程得到分類器的分類性能（如何評價？）15共七十二頁分類(fn li)決策在構(gòu)造成功分類器之后（通過測試），則可以利用該分類器實際(shj)執(zhí)行分類16共七十二頁分類的評價準則(zhnz)-約定和假設(shè)17共七十二頁分類的評價準則(zhnz)-指標1精確度（accuracy）是最常用的評價準則代表測試(csh)集中被正確分類的數(shù)據(jù)樣本所占的比例

7、反映了分類器對于數(shù)據(jù)集的整體分類性能18共七十二頁分類的評價準則(zhnz)-指標2查全率（recall）第j個類別的查全率（召回率）表示在本類樣本中，被正確(zhngqu)分類的樣本占的比例代表該類別的分類精度19共七十二頁分類的評價準則(zhnz)-指標3查準率（precision）第j個類別的查準率表示被分類為該類的樣本中，真正屬于(shy)該類的樣本所占的比例代表該類別的分類純度20共七十二頁分類的評價(pngji)準則-指標4F-measure可以比較合理地評價(pngji)分類器對每一類樣本的分類性能它是查全率和查準率的組合表達式其中參數(shù)是可以調(diào)節(jié)的，通常取值為121共七十二頁分類

8、的評價(pngji)準則-指標5幾何均值（G-mean）它能合理地評價數(shù)據(jù)集的整體分類性能(xngnng)是各個類別查全率的平方根，當各個類別的查全率都大時才增大同時兼顧了各個類別的分類精度22共七十二頁延伸(ynshn)閱讀Jin-Mao Wei, Xiao-Jie Yuan, et al. A novel measure for evaluating classifiers, Expert Systems with Applications, 37(2010):3799-380923共七十二頁關(guān)于(guny)數(shù)據(jù)分類的小結(jié)所謂分類即是使用某種分類模型，以對象的若干維描述屬性為輸入，經(jīng)過計算

9、輸出該對象所屬類別的過程數(shù)據(jù)分類的兩個關(guān)鍵步驟是分類器訓練(xnlin)：選定合適的分類模型及參數(shù)分類器測試：利用合適的指標檢驗分類器有效性目前已有一些成熟的分類器可供使用決策樹支持向量機最近鄰/k-近鄰24共七十二頁25Part II決策樹算法(sun f)共七十二頁決策樹是一種以給定的數(shù)據(jù)樣本為基礎(chǔ)(jch)的歸納學習方法在給定已知類標號的數(shù)據(jù)集的情況下，采用自頂向下的遞歸方式來產(chǎn)生一個類似于流程圖的樹結(jié)構(gòu)樹的最頂層節(jié)點是根節(jié)點最底層節(jié)點是葉節(jié)點：代表樣本的類別根節(jié)點和葉節(jié)點之間的節(jié)點是內(nèi)部節(jié)點決策樹方法在根節(jié)點和內(nèi)部節(jié)點上根據(jù)給定的度量標準來選擇最適合的描述屬性作為分支屬性并根據(jù)該屬性的

10、不同取值向下建立分支26共七十二頁決策樹示例(shl)-購買保險27A1-公司職員A2-年齡A3-收入A4-信譽度C-買保險否=40高良c2否50中良c1是50低良c1是50低優(yōu)c2是4150低優(yōu)c1否=40中良c2是50中良c1是50中優(yōu)c2共七十二頁保險(boxin)決策樹解決了哪類人更傾向于購買保險(boxin)的問題28年齡信譽度公司職員c1c1c2c1c250是否良優(yōu)共七十二頁決策樹向程序語言的轉(zhuǎn)化(zhunhu)if (年齡=40 & 是公司(n s)職員)買保險if (年齡50 & 信譽度為良)買保險if (年齡50 & 信譽度為優(yōu))不買保險29共七十二頁基本(jbn)決策樹方法

11、基本算法 (貪婪算法)自頂向下的分治算法構(gòu)造樹開始, 所有的訓練樣本和樹根相連屬性為分類屬性 (若是連續(xù)值，則離散化)根據(jù)選定的屬性遞歸地劃分樣本?如何選擇基于啟發(fā)式或統(tǒng)計度量選取測試屬性 (e.g., 信息增益)停止劃分的準則所有樣本均和屬于同一類的節(jié)點連接無剩下的屬性用于繼續(xù)劃分樣本 葉節(jié)點分類應(yīng)用多數(shù)表決法無剩余的樣本其它的提前(tqin)中止法30共七十二頁屬性(shxng)選擇度量屬性選擇度量劃分規(guī)則劃分屬性：度量得分高的屬性流行(lixng)的屬性選擇度量信息增益(ID3， C4.5)選取時，偏向于多值屬性增益率(C4.5)偏向不平衡劃分Gini指標( CART, SLIQ, SP

12、RINT)偏向于多值屬性類的數(shù)量很大時，計算較困難共七十二頁信息(xnx)增益(Information Gain)基于信息論“熵”，選取具有最大信息增益的屬性劃分在屬性節(jié)點(ji din)A處，樣本集D所具有的熵 (p( j | D) 為類 j 在節(jié)點 t處的概率).度量節(jié)點的均質(zhì)性當所有的類均勻分布時，最大為 (log nc)，具有 最多信息當只有所有樣本屬于一類時，最小為 (0.0) ，具有最少信息在屬性A處，將樣本分為v類的信息量通過在屬性A，形成v個分支后，信息增益為,增益最大的選為劃分屬性共七十二頁信息增益(zngy)例子類 P: buys_computer = “yes”類 N:

13、buys_computer = “no” 指 14個樣本中有5個“age =30”, 兩個屬于(shy)類p，2個屬于類N ,因此Similarly,共七十二頁決策樹首層age?4030.40共七十二頁增益(zngy)率(Gain Ratio)C4.5 (ID3的后繼算法) 應(yīng)用增益率克服(kf)信息增益的偏斜性 (信息增益的規(guī)范化)Ex.GainRatio(income) = 0.029/0.926 = 0.031具有最大增益率的屬性選為劃分屬性信息增益缺點: 傾向于選擇分割數(shù)目多的屬性。共七十二頁Gini指數(shù)(zhsh)Gini指數(shù):節(jié)點屬性 A劃分樣本的不純度，設(shè)樣本集為D(NOTE:

14、p( j | D) 類 j 在樣本D中的概率).當所有樣本均勻分布在不同類時，最大為(1 - 1/nc), 表示(biosh)最小興趣信息當所有的樣本屬于一類時，最小 為(0.0)，表示最大興趣信息共七十二頁Gini例子(l zi)P(C1) = 0/6 = 0 P(C2) = 6/6 = 1Gini = 1 P(C1)2 P(C2)2 = 1 0 1 = 0 P(C1) = 1/6 P(C2) = 5/6Gini = 1 (1/6)2 (5/6)2 = 0.278P(C1) = 2/6 P(C2) = 4/6Gini = 1 (2/6)2 (4/6)2 = 0.444共七十二頁基于Gini指

15、數(shù)(zhsh)的劃分用于CART算法在節(jié)點A，將訓練集D劃分為k個子集(子節(jié)點Di )，則以劃分的不純度加權(quán)和度量(dling)其優(yōu)劣 ni = 子樹 的訓練樣本個數(shù)i, n = 節(jié)點p處訓練樣本個數(shù).共七十二頁二值屬性(shxng)的Gini指數(shù)劃分為兩個子集帶權(quán)劃分的效果: Gini指數(shù)(zhsh)越小越好尋求更大和更純的劃分B?YesNoNode N1Node N2Gini(D1) = 1 (5/7)2 (2/7)2 = 0.174 Gini(D2) = 1 (1/5)2 (4/5)2 = 0.32Gini(Children) = 7/12 * 0.174 + 5/12 * 0.32=

16、0.204共七十二頁決策樹歸納(gun)算法算法(sun f)種類多Hunts Algorithm (one of the earliest)CARTID3, C4.5SLIQ,SPRINT共七十二頁ID3算法(sun f)原理選擇具有較高信息增益的描述屬性作為給定數(shù)據(jù)集X的分支屬性，從而創(chuàng)建決策樹中的一個節(jié)點根據(jù)該描述屬性的不同取值再創(chuàng)建分支之后對各個分支中的樣本子集遞歸調(diào)用上述方法建立下一級子節(jié)點當某個分支上的所有(suyu)數(shù)據(jù)樣本都屬于同一個類別時劃分停止，形成葉節(jié)點或者當某個分支上的樣本不屬于同一個類別，但是又沒有剩余的描述屬性可以進一步劃分數(shù)據(jù)集時也形成葉節(jié)點，并且用多數(shù)樣本所屬的

17、類別來標記這個葉節(jié)點41共七十二頁ID3算法(sun f)示例該樣本(yngbn)集中共包含4個描述屬性和1個類別屬性，空間容量為14目標是利用ID3思想構(gòu)建一棵可用于新樣本分類的決策樹42A1-公司職員A2-年齡A3-收入A4-信譽度C-買保險否=40高良c2否50中良c1是50低良c1是50低優(yōu)c2是4150低優(yōu)c1否=40中良c2是50中良c1是50中優(yōu)c2共七十二頁第1步：計算對訓練集分類所需的期望(qwng)信息已知total=14c1(買保險)的樣本(yngbn)數(shù)量是n1=9c2(不買保險)的樣本數(shù)量是n2=5所以P(c1)=9/14P(c2)=5/14根據(jù)期望信息公式可得43共

18、七十二頁第2步：計算A1（公司(n s)職員）的熵A1包含兩種取值：“是”和“否”利用(lyng)A1可將X劃分為兩個子集X1和X2X1中的數(shù)據(jù)樣本都是公司職員（7個）標號為c1的有6個，n11=6標號為c2的有1個，n21=1則可得p11=6/7p21=1/744A1-公司職員C-買保險否c2否c2否c1否c1是c1是c2是c1否c2是c1是c1是c1否c1是c1否c2共七十二頁第2步：計算A1（公司(n s)職員）的熵利用A1可將X劃分為兩個子集X1和X2X2中的數(shù)據(jù)樣本都不是公司職員(zhyun)（7個）標號為c1的有3個，n12=3標號為c2的有4個，n22=4則可得p12=3/7p2

19、2=4/745A1-公司職員C-買保險否c2否c2否c1否c1是c1是c2是c1否c2是c1是c1是c1否c1是c1否c2共七十二頁第2步：計算(j sun)A1（公司職員）的熵則計算(j sun)出A1劃分訓練集所得的熵為46共七十二頁第3步：計算(j sun)A1（公司職員）的信息增益47共七十二頁第4步：求出其他(qt)描述屬性的信息增益Gain(A2)=0.246Gain(A3)=0.029Gain(A4)=0.048經(jīng)比較可知Gain(A2)最大，所以選擇A2（年齡(ninlng)）作為決策樹的根節(jié)點進一步將樹劃分為3個分支48共七十二頁第5步：根據(jù)根節(jié)點劃分(hu fn)數(shù)據(jù)集年齡

20、50的子集在此子集內(nèi)繼續(xù)檢查Gain(A1)、Gain(A3)、Gain(A4)選取信息(xnx)增益最大的描述屬性作為內(nèi)部節(jié)點51A1-公司職員A3-收入A4-信譽度C-買保險否中良c1是低良c1是低優(yōu)c2是中良c1否中優(yōu)c2共七十二頁ID3算法(sun f)小結(jié)使用ID3算法的基本思想是采用自頂向下的遞歸方式，將原始樣本空間劃分成若干更小的樣本空間再對他們單獨進行處理其中，選擇(xunz)哪一個描述屬性作為新建節(jié)點，依據(jù)是考察該描述屬性的信息增益是否最大52共七十二頁53Part IIIC4.5算法(sun f)下載(xi zi)地址/Personal/共七十二頁ID3的不足(bz)（1/

21、2）使用信息增益作為屬性(shxng)選擇依據(jù)帶有傾向性，傾向于選擇取值較多的屬性 為什么？一種可能的解釋是：對于較難分類的集合，優(yōu)先將樣本分割到盡可能多的分支中將極大簡化分類工作54共七十二頁ID3的不足(bz)（2/2）無法處理未知值的樣本對于個別樣本缺失了某項描述屬性(shxng)的情況，無法處理無法處理連續(xù)值的樣本對于描述屬性是連續(xù)值的情況，無法處理55共七十二頁變化一：使用信息(xnx)增益比56共七十二頁變化(binhu)二：處理未知值的訓練樣本（1/2）思想將未知值用最常用的值來替代（較容易）或，依據(jù)(yj)現(xiàn)有取值的概率分布來估計未知值（較真實）顯然：依據(jù)思想一，在已知樣本中年

22、齡的三個區(qū)間分布是50，5人則可以直接指定未知值為“50”57A2-年齡C-買保險=40c250c150c150c24150c1=40c250c1？c14150c14150c150c2共七十二頁變化(binhu)二：處理未知值的訓練樣本（2/2）思想將未知值用最常用的值來替代（較容易）或，依據(jù)現(xiàn)有取值的概率分布來估計未知值（較真實）顯然：依據(jù)思想二，在已知樣本中年齡的三個區(qū)間分布是50，5人考慮(kol)未知值樣本后，分布更新為50，5+5/13人58A2-年齡C-買保險=40c250c150c150c24150c1=40c250c1？c14150c14150c150c2共七十二頁變化三：處理

23、(chl)連續(xù)值的訓練樣本（1/10）思想將所有數(shù)據(jù)樣本按照連續(xù)型描述屬性Ac的具體取值，由小到大進行升序排列，得到的屬性值取值序列A1c,A2c,.,Atotalc在A1c,A2c,.,Atotalc中生成total-1個分割點，第i個分割點的取值設(shè)置為vi=(Aic+A(i+1)c)/2或者vi=Aic該分割點將數(shù)據(jù)集劃分為兩個子集(z j)，即描述屬性Ac的取值在區(qū)間A1c,vi的數(shù)據(jù)樣本和在區(qū)間(vi,Atotalc的數(shù)據(jù)樣本，顯然劃分共有total-1種方式從total-1個分割點中選擇最佳分割點。對于每一個分割點劃分數(shù)據(jù)集的方式，計算其信息增益比，從中選擇信息增益比最大的分割點來劃

24、分數(shù)據(jù)集59共七十二頁變化(binhu)三：處理連續(xù)值的訓練樣本（2/10）示例求利用C4.5算法在連續(xù)值描述屬性A上的最佳分割點解：第0步，將A的取值升序排列65,70,70,70,75,78,80,80,80,85,90,90,95,96第1步，計算vi=65時的信息(xnx)增益比60AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c2共七十二頁變化三：處理(chl)連續(xù)值的訓練樣本（3/10）解：第1步，計算(j sun)vi=65時的信息增益比61AC85c290c278c196c180c170c265c195c270c

25、180c170c190c175c180c2共七十二頁變化三：處理(chl)連續(xù)值的訓練樣本（4/10）解：第1步，計算(j sun)vi=65時的信息增益比62AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c2共七十二頁變化(binhu)三：處理連續(xù)值的訓練樣本（5/10）解：第2步，計算vi=70時的信息(xnx)增益比63AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c2共七十二頁變化三：處理(chl)連續(xù)值的訓練樣本（6/10）解：第2步，計算(j sun)

26、vi=70時的信息增益比64AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c2共七十二頁變化三：處理(chl)連續(xù)值的訓練樣本（7/10）解：第2步，計算vi=70時的信息(xnx)增益比65AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c2共七十二頁變化(binhu)三：處理連續(xù)值的訓練樣本（8/10）解：第3步，計算vi=75時的信息(xnx)增益比66AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c2共七十二頁變化(binhu)三：處理連續(xù)值的訓練樣本（9/10）解：第3步，計算vi=75時的信息(xnx)增益比67AC85c290c278c196c180c170c265c195c270c180c17