第講數(shù)據(jù)分類決策樹

1、第第4 4講講數(shù)據(jù)分類數(shù)據(jù)分類- -決策樹決策樹目錄目錄? 基本概念? 決策樹ID3算法? 決策樹C4.5算法2本周學(xué)習(xí)目標(biāo)本周學(xué)習(xí)目標(biāo)1.掌握數(shù)據(jù)分類的基本原理和評價指標(biāo)2.了解兩種決策樹算法34定義定義? 數(shù)據(jù)分類? 是指把數(shù)據(jù)樣本映射到一個事先定義的類中的學(xué)習(xí)過程? 即給定一組輸入的屬性向量及其對應(yīng)的類，用基于歸納的學(xué)習(xí)算法得出分類? 分類問題是數(shù)據(jù)挖掘領(lǐng)域中研究和應(yīng)用最為廣泛的技術(shù)之一，如何更精確、更有效地分類一直是人們追求的目標(biāo)? 數(shù)據(jù)分類的任務(wù)? 通過學(xué)習(xí)得到一個目標(biāo)函數(shù)f，把每個屬性集x映射到一個預(yù)先定義的類標(biāo)號y5分類的示例分類的示例? 兩類分類示例? 銀行業(yè)：區(qū)分高端信用卡和

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

3、形式化描述分類問題的形式化描述8,m,d,),(d), 2 , 1(, 2 , 1| ),(21212121miiididiiidiiiiiicccyxyAAAxxxxxxxtotalixtotaliyxX?個類別，則假設(shè)給定數(shù)據(jù)集包含的類標(biāo)號表示數(shù)據(jù)樣本的具體取值個描述屬性分別對應(yīng)表示維特征向量用其中數(shù)據(jù)樣本數(shù)據(jù)集分類的過程分類的過程9獲取數(shù)據(jù)預(yù)處理分類決策分類器設(shè)計獲取數(shù)據(jù)獲取數(shù)據(jù)? 數(shù)值型數(shù)據(jù)? 病例中的各種化驗數(shù)據(jù)? 空氣質(zhì)量監(jiān)測數(shù)據(jù)? 描述性數(shù)據(jù)? 人事部門檔案資料? 圖片型數(shù)據(jù)? 指紋、掌紋指紋、掌紋? 自然場景圖片? 很多情況下，需要將上述數(shù)據(jù)統(tǒng)一轉(zhuǎn)換為數(shù)值型數(shù)據(jù)序列，即形成特征

4、向量（特征提取）10預(yù)處理預(yù)處理? 為了提高分類的準(zhǔn)確性和有效性，需要對分類所用的數(shù)據(jù)進行預(yù)處理? 去除噪聲數(shù)據(jù)? 對空缺值進行處理對空缺值進行處理? 數(shù)據(jù)降維（特征選擇）-（PCA、LDA）11分類器設(shè)計分類器設(shè)計1-1-劃分數(shù)據(jù)集劃分數(shù)據(jù)集? 給定帶有類標(biāo)號的數(shù)據(jù)集，并且將數(shù)據(jù)集劃分為兩個部分? 訓(xùn)練集（training set）? 測試集（testing set）? 劃分策略? 隨機抽取法? 2/1訓(xùn)練集/測試集8/1? 十交叉驗證法（10-fold validation）? 將數(shù)據(jù)集隨機地劃分為 10組? 之后執(zhí)行 10次循環(huán)，在第 i次循環(huán)中，將第 i組數(shù)據(jù)樣本作為測試集，其余的 9

5、組數(shù)據(jù)樣本作為訓(xùn)練集12分類器設(shè)計分類器設(shè)計2-2-分類器構(gòu)造分類器構(gòu)造? 利用訓(xùn)練集構(gòu)造分類器（分類模型）? 通過分析由屬性描述的每類樣本的數(shù)據(jù)信息，從中總結(jié)出分類的規(guī)律性，建立判別公式或判別規(guī)則? 在分類器構(gòu)造過程中，由于提供了每個訓(xùn)練樣本的類標(biāo)號，這一步也稱作監(jiān)督學(xué)習(xí)（supervised learning）13分類器設(shè)計分類器設(shè)計3-3-分類器測試分類器測試? 利用測試集對分類器的分類性能進行評估，具體方式是? 首先，利用分類器對測試集中的每一個樣本進行分類? 其次，將分類得到的類標(biāo)號和測試集中數(shù)據(jù)樣本的原始類標(biāo)號進行對比? 由上述過程得到分類器的分類性能（如何評價？）14分類決策分類

6、決策? 在構(gòu)造成功分類器之后（通過測試），則可以利用該分類器實際執(zhí)行分類15分類的評價準(zhǔn)則分類的評價準(zhǔn)則- -約定和假設(shè)約定和假設(shè)16jjjmiiiiiitestFPFNTPjcccyxyxNiyxX該類的樣本數(shù)量是其他類別被錯誤分類為是被錯誤分類的樣本數(shù)量是被正確分類的樣本數(shù)量個類別，設(shè)定：對于測試集的第個類別，則假設(shè)分類問題含有的類標(biāo)號；表示數(shù)據(jù)樣本本；表示測試集中的數(shù)據(jù)樣數(shù)；表示測試集中的樣本個其中給定測試集,mN, 2 , 1| ),(21?分類的評價準(zhǔn)則分類的評價準(zhǔn)則- -指標(biāo)指標(biāo)1 1? 精確度（accuracy）? 是最常用的評價準(zhǔn)則? 代表測試集中被正確分類的數(shù)據(jù)樣本所占的比例

7、? 反映了分類器對于數(shù)據(jù)集的整體分類性能反映了分類器對于數(shù)據(jù)集的整體分類性能17NTPAccuracymjj?1分類的評價準(zhǔn)則分類的評價準(zhǔn)則- -指標(biāo)指標(biāo)2 2? 查全率（recall）? 第j個類別的查全率（召回率）表示在本類樣本中，被正確分類的樣本占的比例? 代表該類別的分類精度18jjjjFNTPTPRecall?分類的評價準(zhǔn)則分類的評價準(zhǔn)則- -指標(biāo)指標(biāo)3 3? 查準(zhǔn)率（precision）? 第j個類別的查準(zhǔn)率表示被分類為該類的樣本中，真正屬于該類的樣本所占的比例? 代表該類別的分類純度19jjjjFPTPTPPrecision?分類的評價準(zhǔn)則分類的評價準(zhǔn)則- -指標(biāo)指標(biāo)4 4? F

8、-measure? 可以比較合理地評價分類器對每一類樣本的分類性能? 它是查全率和查準(zhǔn)率的組合表達式? 其中參數(shù)是可以調(diào)節(jié)的，通常取值為120jjjjjPrecisionRecallPrecisionRecallmeasureF?22)1 (?分類的評價準(zhǔn)則分類的評價準(zhǔn)則- -指標(biāo)指標(biāo)5 5? 幾何均值（G-mean）? 它能合理地評價數(shù)據(jù)集的整體分類性能? 是各個類別查全率的平方根，當(dāng)各個類別的查全率都大時才增大? 同時兼顧了各個類別的分類精度同時兼顧了各個類別的分類精度21?mjjRecallmeanG1延伸閱讀延伸閱讀? Jin-Mao Wei, Xiao-Jie Yuan, et al

9、. A novel measure for evaluating classifiers, Expert Systems with Applications, 37(2010):3799-380922關(guān)于數(shù)據(jù)分類的小結(jié)關(guān)于數(shù)據(jù)分類的小結(jié)? 所謂分類即是使用某種分類模型，以對象的若干維描述屬性為輸入，經(jīng)過計算輸出該對象所屬類別的過程? 數(shù)據(jù)分類的兩個關(guān)鍵步驟是? 分類器訓(xùn)練：選定合適的分類模型及參數(shù)? 分類器測試：利用合適的指標(biāo)檢驗分類器有效性? 目前已有一些成熟的分類器可供使用? 決策樹? 支持向量機? 最近鄰/k-近鄰2324決策樹決策樹? 是一種以給定的數(shù)據(jù)樣本為基礎(chǔ)的歸納學(xué)習(xí)方法? 在給

10、定已知類標(biāo)號的數(shù)據(jù)集的情況下，采用自頂向下的遞歸方式來產(chǎn)生一個類似于流程圖的樹結(jié)構(gòu)? 樹的最頂層節(jié)點是根節(jié)點樹的最頂層節(jié)點是根節(jié)點? 最底層節(jié)點是葉節(jié)點：代表樣本的類別? 根節(jié)點和葉節(jié)點之間的節(jié)點是內(nèi)部節(jié)點? 決策樹方法在根節(jié)點和內(nèi)部節(jié)點上根據(jù)給定的度量標(biāo)準(zhǔn)來選擇最適合的描述屬性作為分支屬性? 并根據(jù)該屬性的不同取值向下建立分支25決策樹示例決策樹示例- -購買保險購買保險26A1-公司職員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保險決策樹保險決策樹? 解決了哪類人更傾向于

11、購買保險的問題解決了哪類人更傾向于購買保險的問題27年齡信譽度公司職員c1c1c2c1c250是否良優(yōu)決策樹向程序語言的轉(zhuǎn)化決策樹向程序語言的轉(zhuǎn)化? if (年齡=40 & 是公司職員)買保險? if (年齡50 & 信譽度為良)買保險? if (年齡50 & 信譽度為優(yōu))不買保險28ID3ID3算法的原理算法的原理? 核心思想? 在選擇根節(jié)點和各個內(nèi)部節(jié)點上的分支屬性時，采用信息增益（information gain）作為度量標(biāo)準(zhǔn)? 特別說明特別說明? 創(chuàng)建根節(jié)點時，X是最初給定的所有數(shù)據(jù)? 創(chuàng)建內(nèi)部節(jié)點時，X是上層節(jié)點的某個分支對應(yīng)的數(shù)據(jù)集29,m,d,),(d),

12、 2 , 1(, 2 , 1| ),(21212121miiididiiidiiiiiicccyxyAAAxxxxxxxtotalixtotaliyxX?個類別，則假設(shè)給定數(shù)據(jù)集包含的類標(biāo)號表示數(shù)據(jù)樣本的具體取值個描述屬性分別對應(yīng)表示維特征向量用其中數(shù)據(jù)樣本數(shù)據(jù)集ID3ID3算法的原理算法的原理? 期望信息期望信息30?mjjjmjjjjcPcPnnnIXtotalncPcXn1221)(log)(),()(?：分類所需的期望信息為對給定數(shù)據(jù)集則各類別的先驗概率為的樣本數(shù)量，中屬于是數(shù)據(jù)集假設(shè)ID3ID3算法的原理算法的原理? 熵? 熵值E(Af)越小，表示屬性Af對數(shù)據(jù)集劃分的純度越高31的

13、數(shù)據(jù)樣本所占的比例中類別為表示在子集且其中所得的熵為：劃分則描述屬性的樣本數(shù)量中屬于類別表示子集中的樣本數(shù)量表示子集設(shè)上具有相同取值中的樣本在其中個子集劃分為可以將利用個不同的取值具有設(shè)描述屬性jssjsjsmjjsjsmssmssqsmssffjsjssssffsqfqffffcXnnpppnnInnItotalnnAEXAcXnXnaAXXXXqXAaaadfA?1211112121)(log),(),()(,q), 2 , 1(?ID3ID3算法的原理算法的原理? 信息增益信息增益32)(),()(21fmffAEnnnIAGainA?益為：劃分數(shù)據(jù)集時的信息增利用描述屬性ID3ID3算

14、法原理算法原理? 選擇具有較高信息增益的描述屬性作為給定數(shù)據(jù)集X的分支屬性，從而創(chuàng)建決策樹中的一個節(jié)點? 根據(jù)該描述屬性的不同取值再創(chuàng)建分支? 之后對各個分支中的樣本子集遞歸調(diào)用上述方法建立下一級子節(jié)點? 當(dāng)某個分支上的所有數(shù)據(jù)樣本都屬于同一個類別時劃分停止，形成葉節(jié)點? 或者當(dāng)某個分支上的樣本不屬于同一個類別，但是又沒有剩余的描述屬性可以進一步劃分數(shù)據(jù)集時也形成葉節(jié)點，并且用多數(shù)樣本所屬的類別來標(biāo)記這個葉節(jié)點33ID3ID3算法示例算法示例該樣本集中共包含4個描述屬性和1個類別屬性，空間容量屬性，空間容量為14目標(biāo)是利用ID3思想構(gòu)建一棵可用于新樣本分類的決策樹34A1-公司職員A2-年齡A

15、3-收入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 1步：計算對訓(xùn)練集分類所需的期望信息步：計算對訓(xùn)練集分類所需的期望信息? 已知? total=14? c1(買保險)的樣本數(shù)量是n1=9? c2(不買保險)的樣本數(shù)量是n2=5? 所以? P(c1)=9/14? P(c2)=5/14? 根據(jù)期望信息公式可得3594. 0)145(log145)149(log149()(log)(),(2221221?jjjcPcPnnI第2步：計算A1（公司職員）的熵? A1包含兩種取值：“是”和“否”?

16、 利用A1可將X劃分為兩個子集X1和X2? X1中的數(shù)據(jù)樣本都是公司職員（7個）? 標(biāo)號為c1的有6個，n11=6? 標(biāo)號為c2的有1個，n21=1? 則可得? p11=6/7? p21=1/736A1-公司職員C-買保險否c2否c2否c1否c1是c1是c2是c1否c2是c1是c1是c1否c1是c1否c2592. 0)71(log71)76(log76()(log),(22211212111?jjjppnnI第2步：計算A1（公司職員）的熵? 利用A1可將X劃分為兩個子集X1和X2? X2中的數(shù)據(jù)樣本都不是公司職員（7個）? 標(biāo)號為c1的有3個，n12=3? 標(biāo)號為c2的有4個，n22=4?

17、則可得? p12=3/7? p22=4/737A1-公司職員C-買保險否c2否c2否c1否c1是c1是c2是c1否c2是c1是c1是c1否c1是c1否c2985. 0)74(log74)73(log73()(log),(22212222212?jjjppnnI第第2 2步：計算步：計算A1A1（公司職員）的熵（公司職員）的熵? 則計算出A1劃分訓(xùn)練集所得的熵為38789. 0985. 0147592. 0147),()(2121211?sssssnnItotalnnAE第第3 3步：計算步：計算A1A1（公司職員）的信息增益（公司職員）的信息增益39151. 0789. 094. 0)(),(

18、)(12111?AEnnIAGainA益為：劃分數(shù)據(jù)集時的信息增利用描述屬性第第4 4步：求出其他描述屬性的信息增益步：求出其他描述屬性的信息增益? Gain(A2)=0.246? Gain(A3)=0.029? Gain(A4)=0.048? 經(jīng)比較可知Gain(A2)最大，所以選擇A2（年齡）作為決策樹的根節(jié)點? 進一步將樹劃分為3個分支40第5步：根據(jù)根節(jié)點劃分數(shù)據(jù)集年齡50的子集在此子集內(nèi)繼續(xù)檢查Gain(A1)、Gain(A3)、Gain(A4)選取信息增益最大的描述屬性作為內(nèi)部節(jié)點43A1-公司職員A3-收入A4-信譽度C-買保險否中良c1是低良c1是低優(yōu)c2是中良c1否中優(yōu)c2I

19、D3ID3算法小結(jié)算法小結(jié)? 使用ID3算法的基本思想是? 采用自頂向下的遞歸方式，將原始樣本空間劃分成若干更小的樣本空間? 再對他們單獨進行處理再對他們單獨進行處理? 其中，選擇哪一個描述屬性作為新建節(jié)點，依據(jù)是考察該描述屬性的信息增益是否最大4445ID3ID3的不足（的不足（1/21/2）? 使用信息增益作為屬性選擇依據(jù)? 帶有傾向性，傾向于選擇取值較多的屬性 ?為什么？? 一種可能的解釋是：對于較難分類的集合，優(yōu)先將樣本分割到盡可能多的分支中將極大簡化分類工作46ID3ID3的不足（的不足（2/22/2）? 無法處理未知值的樣本? 對于個別樣本缺失了某項描述屬性的情況，無法處理? 無法

20、處理連續(xù)值的樣本無法處理連續(xù)值的樣本? 對于描述屬性是連續(xù)值的情況，無法處理47變化一：使用信息增益比變化一：使用信息增益比48?qsssfffffjsjssssffsqfqfffftotalntotalnAsplitAsplitAGainAratioGainXAcXnXnaAXXXXqXAaaadfA122121)(log)()()()(_,q), 2 , 1(其中所得的信息增益比為：劃分則描述屬性的樣本數(shù)量中屬于類別表示子集中的樣本數(shù)量表示子集設(shè)上具有相同取值中的樣本在其中個子集劃分為可以將利用個不同的取值具有設(shè)描述屬性?變化二：處理未知值的訓(xùn)練樣本（ 1/2）? 思想? 將未知值用最常用

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

22、 50，5+5/13人50A2-年齡C-買保險=40c250c150c150c24150c1=40c250c1？c14150c14150c150c2變化三：處理連續(xù)值的訓(xùn)練樣本（變化三：處理連續(xù)值的訓(xùn)練樣本（ 1/101/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ù)集劃分為兩個子集，即描述屬性Ac的取值在區(qū)間AA1c,vi的數(shù)據(jù)樣本和在

23、區(qū)間(vi,Atotalc的數(shù)據(jù)樣本，顯然劃分共有total-1種方式? 從total-1個分割點中選擇最佳分割點。對于每一個分割點劃分數(shù)據(jù)集的方式，計算其信息增益比，從中選擇信息增益比最大的分割點來劃分數(shù)據(jù)集51變化三：處理連續(xù)值的訓(xùn)練樣本（ 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時的信息增益比52A AC C85c290c278c196c180c170c265c195c270c180c170c190c175c18

24、0c294. 0)145(log145)149(log149()(log)(),(2221221?jjjcPcPnnI變化三：處理連續(xù)值的訓(xùn)練樣本（ 3/10）? 解：? 第1步，計算vi=65時的信息增益比53A AC C85c290c278c196c180c170c265c195c270c180c170c190c175c180c20)10(log10)11(log11()(log),(22211212111?jjjppnnI961. 0)135(log135)138(log138()(log),(22212222212?jjjppnnI892. 0961. 014130141),()(21

25、21211?sssssnnItotalnnAE變化三：處理連續(xù)值的訓(xùn)練樣本（ 4/10）? 解：? 第1步，計算vi=65時的信息增益比54A AC C85c290c278c196c180c170c265c195c270c180c170c190c175c180c2371. 01413log1413141log141)(log)(222121?ssstotalntotalnAsplit129. 0371. 0892. 094. 0)()()(_1111?AsplitAGainAratioGainX所得的信息增益比為：劃分在分割點變化三：處理連續(xù)值的訓(xùn)練樣本（ 5/10）? 解：? 第2步，計算v

26、i=70時的信息增益比55A AC C85c290c278c196c180c170c265c195c270c180c170c190c175c180c294. 0)145(log145)149(log149()(log)(),(2221221?jjjcPcPnnI變化三：處理連續(xù)值的訓(xùn)練樣本（ 6/10）? 解：? 第2步，計算vi=70時的信息增益比56A AC C85c290c278c196c180c170c265c195c270c180c170c190c175c180c2811. 0)41(log41)43(log43()(log),(22211212111?jjjppnnI971. 0)104(log104)106(log106()(log),(22212222212?jjjppnnI926. 0971. 01410811. 0144),()(2121211?sssssnnItotalnnAE變化三：處理連續(xù)值的訓(xùn)練樣本（ 7/10）? 解：? 第2步，計算vi=7