1、數(shù)據(jù)分類數(shù)據(jù)分類- -決策樹決策樹目錄目錄v 基本概念基本概念v 決策樹決策樹ID3ID3算法算法v 決策樹決策樹C4.5C4.5算法算法學(xué)習(xí)目標(biāo)學(xué)習(xí)目標(biāo)1.1.掌握數(shù)據(jù)分類的基本原理和評(píng)價(jià)指標(biāo)掌握數(shù)據(jù)分類的基本原理和評(píng)價(jià)指標(biāo)2.2.了解兩種決策樹算法了解兩種決策樹算法定義定義v 數(shù)據(jù)分類數(shù)據(jù)分類 是指把數(shù)據(jù)樣本映射到一個(gè)事先定義的類中的學(xué)習(xí)過程是指把數(shù)據(jù)樣本映射到一個(gè)事先定義的類中的學(xué)習(xí)過程 即給定一組輸入的屬性向量及其對(duì)應(yīng)的類，用基于歸納的學(xué)習(xí)算即給定一組輸入的屬性向量及其對(duì)應(yīng)的類，用基于歸納的學(xué)習(xí)算法得出分類法得出分類 分類問題是數(shù)據(jù)挖掘領(lǐng)域中研究和應(yīng)用最為廣泛的技術(shù)之一，如分類問題是數(shù)

2、據(jù)挖掘領(lǐng)域中研究和應(yīng)用最為廣泛的技術(shù)之一，如何更精確、更有效地分類一直是人們追求的目標(biāo)何更精確、更有效地分類一直是人們追求的目標(biāo)v 數(shù)據(jù)分類的任務(wù)數(shù)據(jù)分類的任務(wù) 通過學(xué)習(xí)得到一個(gè)目標(biāo)函數(shù)通過學(xué)習(xí)得到一個(gè)目標(biāo)函數(shù)f f，把每個(gè)屬性集，把每個(gè)屬性集x x映射到一個(gè)預(yù)先定映射到一個(gè)預(yù)先定義的類標(biāo)號(hào)義的類標(biāo)號(hào)y y分類的示例分類的示例v 兩類分類示例兩類分類示例 銀行業(yè)：區(qū)分高端信用卡和低端信用卡銀行業(yè)：區(qū)分高端信用卡和低端信用卡 醫(yī)療診斷：區(qū)分正常細(xì)胞和癌細(xì)胞醫(yī)療診斷：區(qū)分正常細(xì)胞和癌細(xì)胞 互聯(lián)網(wǎng)：區(qū)分正常郵件和垃圾郵件互聯(lián)網(wǎng)：區(qū)分正常郵件和垃圾郵件v 多類分類示例多類分類示例 油氣傳輸：區(qū)分行人走

3、過、汽車碾過、鎬刨、電鉆等行為油氣傳輸：區(qū)分行人走過、汽車碾過、鎬刨、電鉆等行為 文字識(shí)別：區(qū)分不同的字符文字識(shí)別：區(qū)分不同的字符（其中漢字識(shí)別是一個(gè)大類別問題）（其中漢字識(shí)別是一個(gè)大類別問題） 社會(huì)網(wǎng)絡(luò)：區(qū)分中心用戶、活躍用戶、不活躍用戶、馬甲用戶等社會(huì)網(wǎng)絡(luò)：區(qū)分中心用戶、活躍用戶、不活躍用戶、馬甲用戶等示例數(shù)據(jù)集示例數(shù)據(jù)集v 數(shù)據(jù)集包含多個(gè)描述屬性和一個(gè)類別屬性數(shù)據(jù)集包含多個(gè)描述屬性和一個(gè)類別屬性v 一般來說一般來說 描述屬性：連續(xù)值或離散值描述屬性：連續(xù)值或離散值 類別屬性：只能是離散值類別屬性：只能是離散值（目標(biāo)屬性連續(xù)對(duì)應(yīng)回歸問題）（目標(biāo)屬性連續(xù)對(duì)應(yīng)回歸問題）AgeAgeSalary

4、SalaryClassClass30highc125highc221lowc243highc118lowc233lowc1.分類問題的形式化描述分類問題的形式化描述,m,d,),(d), 2 , 1(, 2 , 1| ),(21212121miiididiiidiiiiiicccyxyAAAxxxxxxxtotalixtotaliyxX個(gè)類別，則假設(shè)給定數(shù)據(jù)集包含的類標(biāo)號(hào)表示數(shù)據(jù)樣本的具體取值個(gè)描述屬性分別對(duì)應(yīng)表示維特征向量用其中數(shù)據(jù)樣本數(shù)據(jù)集分類的過程分類的過程獲取數(shù)據(jù)預(yù)處理分類決策分類器設(shè)計(jì)獲取數(shù)據(jù)獲取數(shù)據(jù)v 數(shù)值型數(shù)據(jù)數(shù)值型數(shù)據(jù) 病例中的各種化驗(yàn)數(shù)據(jù)病例中的各種化驗(yàn)數(shù)據(jù) 空氣質(zhì)量監(jiān)測數(shù)據(jù)

5、空氣質(zhì)量監(jiān)測數(shù)據(jù)v 描述性數(shù)據(jù)描述性數(shù)據(jù) 人事部門檔案資料人事部門檔案資料v 圖片型數(shù)據(jù)圖片型數(shù)據(jù) 指紋、掌紋指紋、掌紋 自然場景圖片自然場景圖片v 很多情況下，需要將上述數(shù)據(jù)統(tǒng)一轉(zhuǎn)換為數(shù)值型數(shù)據(jù)序列很多情況下，需要將上述數(shù)據(jù)統(tǒng)一轉(zhuǎn)換為數(shù)值型數(shù)據(jù)序列，即形成特征向量（，即形成特征向量（特征提取特征提?。╊A(yù)處理預(yù)處理v 為了提高分類的準(zhǔn)確性和有效性，需要對(duì)分類所用的數(shù)據(jù)為了提高分類的準(zhǔn)確性和有效性，需要對(duì)分類所用的數(shù)據(jù)進(jìn)行預(yù)處理進(jìn)行預(yù)處理 去除噪聲數(shù)據(jù)去除噪聲數(shù)據(jù) 對(duì)空缺值進(jìn)行處理對(duì)空缺值進(jìn)行處理 數(shù)據(jù)降維（數(shù)據(jù)降維（特征選擇特征選擇）- -（PCAPCA、LDALDA） 主成分分析主成分分析

6、（ Principal Component Analysis Principal Component Analysis ， PCA PCA ） 線性鑒別分析線性鑒別分析(LinearDiscriminantAnalysis,LDA)(LinearDiscriminantAnalysis,LDA)，有時(shí)也稱，有時(shí)也稱FisherFisher線性線性判別判別(FisherLinearDiscriminant,FLD)(FisherLinearDiscriminant,FLD)， 這種算法是這種算法是RonaldFisherRonaldFisher于于 19361936年發(fā)明的，是模式識(shí)別的經(jīng)典算法

7、。年發(fā)明的，是模式識(shí)別的經(jīng)典算法。分類器設(shè)計(jì)分類器設(shè)計(jì)1-1-劃分?jǐn)?shù)據(jù)集劃分?jǐn)?shù)據(jù)集v 給定帶有類標(biāo)號(hào)的數(shù)據(jù)集，并且將數(shù)據(jù)集劃分為兩個(gè)部分給定帶有類標(biāo)號(hào)的數(shù)據(jù)集，并且將數(shù)據(jù)集劃分為兩個(gè)部分 訓(xùn)練集（訓(xùn)練集（training settraining set） 測試集（測試集（testing settesting set）v 劃分策略劃分策略1.1.當(dāng)數(shù)據(jù)集當(dāng)數(shù)據(jù)集D D的的規(guī)模較大規(guī)模較大時(shí)時(shí) 訓(xùn)練集訓(xùn)練集2|D|/32|D|/3，測試集是，測試集是1|D|/31|D|/32.2.當(dāng)數(shù)據(jù)集當(dāng)數(shù)據(jù)集D D的的規(guī)模不大規(guī)模不大時(shí)時(shí) n n交叉驗(yàn)證法（交叉驗(yàn)證法（n-fold validationn-f

8、old validation） 將數(shù)據(jù)集隨機(jī)地劃分為將數(shù)據(jù)集隨機(jī)地劃分為n n組組 之后執(zhí)行之后執(zhí)行n n次循環(huán)，在第次循環(huán)，在第i i次循環(huán)中，將第次循環(huán)中，將第i i組數(shù)據(jù)樣本作為測試集，其余的組數(shù)據(jù)樣本作為測試集，其余的n-1n-1組數(shù)據(jù)樣本作為訓(xùn)練集組數(shù)據(jù)樣本作為訓(xùn)練集, ,最終的精度為最終的精度為n n個(gè)精度的平均值。個(gè)精度的平均值。當(dāng)數(shù)據(jù)集當(dāng)數(shù)據(jù)集D D的的規(guī)模非常小時(shí)規(guī)模非常小時(shí)v每次交叉驗(yàn)證時(shí)，只選擇一條測試數(shù)據(jù)，剩余的數(shù)每次交叉驗(yàn)證時(shí)，只選擇一條測試數(shù)據(jù)，剩余的數(shù)據(jù)均作為訓(xùn)練集。據(jù)均作為訓(xùn)練集。v原始數(shù)據(jù)集有原始數(shù)據(jù)集有mm條數(shù)據(jù)時(shí)，相當(dāng)于條數(shù)據(jù)時(shí)，相當(dāng)于mm- -次交叉驗(yàn)證

9、。次交叉驗(yàn)證。v是是N-N-次交叉驗(yàn)證的一個(gè)特例。次交叉驗(yàn)證的一個(gè)特例。 分類器設(shè)計(jì)分類器設(shè)計(jì)2-2-分類器構(gòu)造分類器構(gòu)造v 利用訓(xùn)練集構(gòu)造分類器（分類模型）利用訓(xùn)練集構(gòu)造分類器（分類模型）v 通過分析由屬性描述的每類樣本的數(shù)據(jù)信息，從中總結(jié)出通過分析由屬性描述的每類樣本的數(shù)據(jù)信息，從中總結(jié)出分類的規(guī)律性，建立判別公式或判別規(guī)則分類的規(guī)律性，建立判別公式或判別規(guī)則v 在分類器構(gòu)造過程中，由于提供了每個(gè)訓(xùn)練樣本的類標(biāo)號(hào)在分類器構(gòu)造過程中，由于提供了每個(gè)訓(xùn)練樣本的類標(biāo)號(hào)，這一步也稱作監(jiān)督學(xué)習(xí)（，這一步也稱作監(jiān)督學(xué)習(xí)（supervised learningsupervised learning）分類

10、器設(shè)計(jì)分類器設(shè)計(jì)3-3-分類器測試分類器測試v 利用測試集對(duì)分類器的分類性能進(jìn)行評(píng)估，具體方式是利用測試集對(duì)分類器的分類性能進(jìn)行評(píng)估，具體方式是 首先，利用分類器對(duì)測試集中的每一個(gè)樣本進(jìn)行分類首先，利用分類器對(duì)測試集中的每一個(gè)樣本進(jìn)行分類 其次，將分類得到的類標(biāo)號(hào)和測試集中數(shù)據(jù)樣本的原始類標(biāo)號(hào)進(jìn)其次，將分類得到的類標(biāo)號(hào)和測試集中數(shù)據(jù)樣本的原始類標(biāo)號(hào)進(jìn)行對(duì)比行對(duì)比 由上述過程得到分類器的分類性能（由上述過程得到分類器的分類性能（如何評(píng)價(jià)？如何評(píng)價(jià)？）分類決策分類決策v 在構(gòu)造成功分類器之后（通過測試），則可以利用該分類在構(gòu)造成功分類器之后（通過測試），則可以利用該分類器實(shí)際執(zhí)行分類器實(shí)際執(zhí)行分類

11、分類的評(píng)價(jià)準(zhǔn)則分類的評(píng)價(jià)準(zhǔn)則- -約定和假設(shè)約定和假設(shè)jjjmiiiiiitestFPFNTPjcccyxyxNiyxX該類的樣本數(shù)量是其他類別被錯(cuò)誤分類為是被錯(cuò)誤分類的樣本數(shù)量是被正確分類的樣本數(shù)量個(gè)類別，設(shè)定：對(duì)于測試集的第個(gè)類別，則假設(shè)分類問題含有的類標(biāo)號(hào)；表示數(shù)據(jù)樣本本；表示測試集中的數(shù)據(jù)樣數(shù)；表示測試集中的樣本個(gè)其中給定測試集,mN, 2 , 1| ),(21分類的評(píng)價(jià)準(zhǔn)則分類的評(píng)價(jià)準(zhǔn)則- -指標(biāo)指標(biāo)1 1v 精確度（精確度（accuracyaccuracy） 是最常用的評(píng)價(jià)準(zhǔn)則是最常用的評(píng)價(jià)準(zhǔn)則 代表測試集中被正確分類的數(shù)據(jù)樣本所占的比例代表測試集中被正確分類的數(shù)據(jù)樣本所占的比例

12、反映了分類器對(duì)于數(shù)據(jù)集的整體分類性能反映了分類器對(duì)于數(shù)據(jù)集的整體分類性能NTPAccuracymjj1分類的評(píng)價(jià)準(zhǔn)則分類的評(píng)價(jià)準(zhǔn)則- -指標(biāo)指標(biāo)2 2v 查全率（查全率（recallrecall） 第第j j個(gè)類別的查全率（召回率）表示在本類樣本中，被正確分類的個(gè)類別的查全率（召回率）表示在本類樣本中，被正確分類的樣本占的比例樣本占的比例 代表該類別的代表該類別的分類精度分類精度jjjjFNTPTPRecalljjjFPFNTP該類的樣本數(shù)量是其他類別被錯(cuò)誤分類為是被錯(cuò)誤分類的樣本數(shù)量是被正確分類的樣本數(shù)量分類的評(píng)價(jià)準(zhǔn)則分類的評(píng)價(jià)準(zhǔn)則- -指標(biāo)指標(biāo)3 3v 查準(zhǔn)率（查準(zhǔn)率（precisionp

13、recision） 第第j j個(gè)類別的查準(zhǔn)率表示被分類為該類的樣本中，真正屬于該類的個(gè)類別的查準(zhǔn)率表示被分類為該類的樣本中，真正屬于該類的樣本所占的比例樣本所占的比例 代表該類別的代表該類別的分類純度分類純度jjjjFPTPTPPrecisionjjjFPFNTP該類的樣本數(shù)量是其他類別被錯(cuò)誤分類為是被錯(cuò)誤分類的樣本數(shù)量是被正確分類的樣本數(shù)量分類的評(píng)價(jià)準(zhǔn)則分類的評(píng)價(jià)準(zhǔn)則- -指標(biāo)指標(biāo)4 4v F-measureF-measure 可以比較合理地評(píng)價(jià)分類器對(duì)每一類樣本的分類性能可以比較合理地評(píng)價(jià)分類器對(duì)每一類樣本的分類性能 它是查全率和查準(zhǔn)率的組合表達(dá)式它是查全率和查準(zhǔn)率的組合表達(dá)式 其中參數(shù)其

14、中參數(shù) 是可以調(diào)節(jié)的，通常取值為是可以調(diào)節(jié)的，通常取值為1 1jjjjjPrecisionRecallPrecisionRecallmeasureF22)1 (分類的評(píng)價(jià)準(zhǔn)則分類的評(píng)價(jià)準(zhǔn)則- -指標(biāo)指標(biāo)5 5v 幾何均值（幾何均值（G-meanG-mean） 它能合理地評(píng)價(jià)數(shù)據(jù)集的整體分類性能它能合理地評(píng)價(jià)數(shù)據(jù)集的整體分類性能 是各個(gè)類別查全率的平方根，當(dāng)各個(gè)類別的查全率都大時(shí)才增大是各個(gè)類別查全率的平方根，當(dāng)各個(gè)類別的查全率都大時(shí)才增大 同時(shí)兼顧了各個(gè)類別的分類精度同時(shí)兼顧了各個(gè)類別的分類精度mjjRecallmeanG1延伸閱讀延伸閱讀v Jin-Mao Wei, Xiao-Jie Yua

15、n, et al. A novel measure Jin-Mao Wei, Xiao-Jie Yuan, et al. A novel measure for evaluating classifiers, Expert Systems with for evaluating classifiers, Expert Systems with Applications, 37(2010):3799-3809Applications, 37(2010):3799-3809關(guān)于數(shù)據(jù)分類的小結(jié)關(guān)于數(shù)據(jù)分類的小結(jié)v 所謂分類即是使用某種分類模型，以對(duì)象的若干維描述屬所謂分類即是使用某種分類模型，以對(duì)象

16、的若干維描述屬性為輸入，經(jīng)過計(jì)算輸出該對(duì)象所屬類別的過程性為輸入，經(jīng)過計(jì)算輸出該對(duì)象所屬類別的過程v 數(shù)據(jù)分類的兩個(gè)關(guān)鍵步驟是數(shù)據(jù)分類的兩個(gè)關(guān)鍵步驟是 分類器訓(xùn)練：選定合適的分類模型及參數(shù)分類器訓(xùn)練：選定合適的分類模型及參數(shù) 分類器測試：利用合適的指標(biāo)檢驗(yàn)分類器有效性分類器測試：利用合適的指標(biāo)檢驗(yàn)分類器有效性v 目前已有一些成熟的分類器可供使用目前已有一些成熟的分類器可供使用 決策樹決策樹 支持向量機(jī)支持向量機(jī) 最近鄰最近鄰/k-/k-近鄰近鄰決策樹決策樹v 是一種以給定的數(shù)據(jù)樣本為基礎(chǔ)的歸納學(xué)習(xí)方法是一種以給定的數(shù)據(jù)樣本為基礎(chǔ)的歸納學(xué)習(xí)方法v 在給定已知類標(biāo)號(hào)的數(shù)據(jù)集的情況下，采用自頂向下的

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

18、公司職員公司職員A2-A2-年齡年齡A3-A3-收入收入A4-A4-信譽(yù)度信譽(yù)度C-C-買保險(xiǎn)買保險(xiǎn)否=40高良c2否50中良c1是50低良c1是50低優(yōu)c2是4150低優(yōu)c1否=40中良c2是50中良c1是50中優(yōu)c2保險(xiǎn)決策樹保險(xiǎn)決策樹v 解決了哪類人更傾向于購買保險(xiǎn)的問題解決了哪類人更傾向于購買保險(xiǎn)的問題年齡信譽(yù)度公司職員c1c1c2c1c250是否良優(yōu)決策樹向程序語言的轉(zhuǎn)化決策樹向程序語言的轉(zhuǎn)化v if (if (年齡年齡=40 & =40 & 是公司職員是公司職員) )買保險(xiǎn)買保險(xiǎn)v if (if (年齡年齡=40 & 50 & 50 & 信譽(yù)

19、度為良信譽(yù)度為良) )買保險(xiǎn)買保險(xiǎn)v if (if (年齡年齡50 & 50 & 信譽(yù)度為優(yōu)信譽(yù)度為優(yōu)) )不買保險(xiǎn)不買保險(xiǎn)基本決策樹方法基本決策樹方法v 基本算法基本算法 ( (貪婪算法貪婪算法) ) 自頂向下的分治算法構(gòu)造樹自頂向下的分治算法構(gòu)造樹 開始開始, , 所有的訓(xùn)練樣本和樹根相連所有的訓(xùn)練樣本和樹根相連 屬性為分類屬性屬性為分類屬性 ( (若是連續(xù)值，則離散化若是連續(xù)值，則離散化) ) 根據(jù)選定的屬性遞歸地劃分樣本根據(jù)選定的屬性遞歸地劃分樣本? ?如何選擇如何選擇 基于啟發(fā)式或統(tǒng)計(jì)度量選取測試屬性基于啟發(fā)式或統(tǒng)計(jì)度量選取測試屬性 (e.g., (e.g., 信息增

20、益信息增益) )v 停止劃分的準(zhǔn)則停止劃分的準(zhǔn)則 所有樣本均和屬于同一類的節(jié)點(diǎn)連接所有樣本均和屬于同一類的節(jié)點(diǎn)連接 無剩下的屬性用于繼續(xù)劃分樣本無剩下的屬性用于繼續(xù)劃分樣本 葉節(jié)點(diǎn)分類應(yīng)用葉節(jié)點(diǎn)分類應(yīng)用多數(shù)表決法多數(shù)表決法 無剩余的樣本無剩余的樣本 其它的提前中止法其它的提前中止法屬性選擇度量屬性選擇度量v 屬性選擇度量劃分規(guī)則屬性選擇度量劃分規(guī)則 劃分屬性：度量得分高的屬性劃分屬性：度量得分高的屬性v 流行的屬性選擇度量流行的屬性選擇度量 信息增益信息增益(ID3(ID3， C4.5)C4.5) 選取時(shí)，偏向于多值屬性選取時(shí)，偏向于多值屬性 增益率增益率(C4.5)(C4.5) 偏向不平衡劃

21、分偏向不平衡劃分 GiniGini指標(biāo)指標(biāo)( CART, SLIQ, SPRINT)( CART, SLIQ, SPRINT) 偏向于多值屬性偏向于多值屬性 類的數(shù)量很大時(shí)，計(jì)算較困難類的數(shù)量很大時(shí)，計(jì)算較困難信息增益信息增益(Information Gain)(Information Gain)v 基于信息論基于信息論“熵熵”，選取具有最大信息增益的屬性劃分，選取具有最大信息增益的屬性劃分v 在屬性節(jié)點(diǎn)在屬性節(jié)點(diǎn)A A處，樣本集處，樣本集D D所具有的熵所具有的熵 ( (p( j | D) 為類為類 j j 在節(jié)點(diǎn)在節(jié)點(diǎn) t t處的概率處的概率). ).v 度量節(jié)點(diǎn)的均質(zhì)性度量節(jié)點(diǎn)的均質(zhì)性

22、當(dāng)所有的類均勻分布時(shí)，最大為當(dāng)所有的類均勻分布時(shí)，最大為 (log n(log nc c) )，具有，具有 最多信息最多信息 當(dāng)只有所有樣本屬于一類時(shí)，最小為當(dāng)只有所有樣本屬于一類時(shí)，最小為 (0.0) (0.0) ，具有最少信息，具有最少信息v 在屬性在屬性A A處，將樣本分為處，將樣本分為v v類的信息量類的信息量v 通過在屬性通過在屬性A A，形成，形成v v個(gè)分支后，信息增益為個(gè)分支后，信息增益為, ,增益最大的選為劃分增益最大的選為劃分屬性屬性()()( |)log( |)jInfo DEntropy Dp j Dp j D 1()()viAiinInfoDInfo Dn()()()

23、AGain AInfo DInfoD信息增益例子信息增益例子類類 P: buys_computer = “yes”P: buys_computer = “yes”類類 N: buys_computer = “no”N: buys_computer = “no” 指 14個(gè)樣本中有5個(gè)“age =30”, 兩個(gè)屬于類p，2個(gè)屬于類N ,因此Similarly,54()(2,3)(4,0)14145(3,2)0.69414ageInfoDIII048. 0)_(151. 0)(029. 0)(ratingcreditGainstudentGainincomeGain246. 0)()()(DInf

24、oDInfoageGainageageincomestudentcredit_ratingbuys_computer=30highnofairno40mediumnofairyes40lowyesfairyes40lowyesexcellentno3140lowyesexcellentyes=30mediumnofairno40mediumyesfairyes40mediumnoexcellentno)3 , 2(145I229955()log ()log ()0.94014141414Info D ()()( |)log( |)jInfo DEntropy Dp j Dp j D 1()()

25、viAiinInfoDInfo Dn決策樹首層決策樹首層age?4030.40增益率增益率(Gain Ratio)(Gain Ratio)v C4.5 (ID3C4.5 (ID3的后繼算法的后繼算法) ) 應(yīng)用增益率克服信息增益的偏斜性應(yīng)用增益率克服信息增益的偏斜性 ( (信信息增益的規(guī)范化息增益的規(guī)范化) )v Ex.Ex. GainRatio(income) = 0.029/0.926 = 0.031GainRatio(income) = 0.029/0.926 = 0.031v 具有最大增益率的屬性選為劃分屬性具有最大增益率的屬性選為劃分屬性21()log ()vjjAjnnSplitI

26、nfoDnn 926. 0)144(log144)146(log146)144(log144)(222DSplitInfoA( )( )( )Gain AGainRatio ASplitInfo A信息增益缺點(diǎn): 傾向于選擇分割數(shù)目多的屬性。GiniGini指數(shù)指數(shù)v GiniGini指數(shù)指數(shù): :節(jié)點(diǎn)屬性節(jié)點(diǎn)屬性 A A劃分樣本的不純度，設(shè)樣本集為劃分樣本的不純度，設(shè)樣本集為D D(NOTE: (NOTE: p( j | D) p( j | D) 類類 j j 在樣本在樣本D D中的概率中的概率). ). 當(dāng)所有樣本均勻分布在不同類時(shí)，最大為當(dāng)所有樣本均勻分布在不同類時(shí)，最大為(1 - 1/

27、nc), (1 - 1/nc), 表示最小表示最小興趣信息興趣信息 當(dāng)所有的樣本屬于一類時(shí)，最小當(dāng)所有的樣本屬于一類時(shí)，最小 為為(0.0)(0.0)，表示最大興趣信息，表示最大興趣信息2()1 ( |)iGini Dp i D C10C26Gini=0.000C12C24Gini=0.444C13C23Gini=0.500C11C25Gini=0.278GiniGini例子例子C1 0 C2 6 C1 2 C2 4 C1 1 C2 5 P(C1) = 0/6 = 0 P(C2) = 6/6 = 1P(C1) = 0/6 = 0 P(C2) = 6/6 = 1Gini = 1 P(C1)Gin

28、i = 1 P(C1)2 2 P(C2) P(C2)2 2 = 1 0 1 = = 1 0 1 = 0 0 2()1 ( |)jGINI Dp j D P(C1) = 1/6 P(C2) = 5/6P(C1) = 1/6 P(C2) = 5/6Gini = 1 (1/6)Gini = 1 (1/6)2 2 (5/6) (5/6)2 2 = 0.278 = 0.278P(C1) = 2/6 P(C2) = 4/6P(C1) = 2/6 P(C2) = 4/6Gini = 1 (2/6)Gini = 1 (2/6)2 2 (4/6) (4/6)2 2 = 0.444 = 0.444C 13C 23

29、G i n i = 0 . 5 0 0基于基于GiniGini指數(shù)的劃分指數(shù)的劃分v 用于用于CARTCART算法算法v 在節(jié)點(diǎn)在節(jié)點(diǎn)A A，將訓(xùn)練集，將訓(xùn)練集D D劃分為劃分為k k個(gè)子集個(gè)子集( (子節(jié)點(diǎn)子節(jié)點(diǎn)D Dii ) )，則以劃，則以劃分的不純度加權(quán)和度量其優(yōu)劣分的不純度加權(quán)和度量其優(yōu)劣 n nii = = 子樹子樹 的訓(xùn)練樣本個(gè)數(shù)的訓(xùn)練樣本個(gè)數(shù)i, i, n n = = 節(jié)點(diǎn)節(jié)點(diǎn)p p處訓(xùn)練樣本個(gè)數(shù)處訓(xùn)練樣本個(gè)數(shù). .1()()kiAiinGiniDGini Dn二值屬性的二值屬性的GiniGini指數(shù)指數(shù)v 劃分為兩個(gè)子集劃分為兩個(gè)子集v 帶權(quán)劃分的效果帶權(quán)劃分的效果: Gin

30、i: Gini指數(shù)越小越好指數(shù)越小越好 尋求更大和更純的劃分尋求更大和更純的劃分B?YesNoNode N1Node N2Gini(D1) Gini(D1) = 1 (5/7)= 1 (5/7)2 2 (2/7)(2/7)2 2 = 0.174 = 0.174 Gini(D2) Gini(D2) = 1 (1/5)= 1 (1/5)2 2 (4/5)(4/5)2 2 = 0.32= 0.32Gini(Children) Gini(Children) = 7/12 = 7/12 * * 0.174 + 0.174 + 5/12 5/12 * * 0.32 0.32= 0.204= 0.204決策

31、樹歸納算法決策樹歸納算法v 算法種類多算法種類多 Hunts Algorithm (one of Hunts Algorithm (one of the earliest)the earliest) CARTCART ID3, ID3, C4.5C4.5 SLIQ,SPRINTSLIQ,SPRINTID3ID3算法原理算法原理v 選擇具有較高信息增益的描述屬性作為給定數(shù)據(jù)集選擇具有較高信息增益的描述屬性作為給定數(shù)據(jù)集X X的分的分支屬性，從而創(chuàng)建決策樹中的一個(gè)節(jié)點(diǎn)支屬性，從而創(chuàng)建決策樹中的一個(gè)節(jié)點(diǎn)v 根據(jù)該描述屬性的不同取值再創(chuàng)建分支根據(jù)該描述屬性的不同取值再創(chuàng)建分支v 之后對(duì)各個(gè)分支中的樣本

32、子集遞歸調(diào)用上述方法建立下一之后對(duì)各個(gè)分支中的樣本子集遞歸調(diào)用上述方法建立下一級(jí)子節(jié)點(diǎn)級(jí)子節(jié)點(diǎn)v 當(dāng)某個(gè)分支上的所有數(shù)據(jù)樣本都屬于同一個(gè)類別時(shí)劃分停當(dāng)某個(gè)分支上的所有數(shù)據(jù)樣本都屬于同一個(gè)類別時(shí)劃分停止，形成葉節(jié)點(diǎn)止，形成葉節(jié)點(diǎn)v 或者當(dāng)某個(gè)分支上的樣本不屬于同一個(gè)類別，但是又沒有或者當(dāng)某個(gè)分支上的樣本不屬于同一個(gè)類別，但是又沒有剩余的描述屬性可以進(jìn)一步劃分?jǐn)?shù)據(jù)集時(shí)也形成葉節(jié)點(diǎn)，剩余的描述屬性可以進(jìn)一步劃分?jǐn)?shù)據(jù)集時(shí)也形成葉節(jié)點(diǎn)，并且用多數(shù)樣本所屬的類別來標(biāo)記這個(gè)葉節(jié)點(diǎn)并且用多數(shù)樣本所屬的類別來標(biāo)記這個(gè)葉節(jié)點(diǎn)ID3ID3算法示例算法示例該樣本集中共該樣本集中共包含包含4 4個(gè)描述個(gè)描述屬性和屬性和

33、1 1個(gè)類別個(gè)類別屬性，空間容量屬性，空間容量為為1414目標(biāo)是利用目標(biāo)是利用ID3ID3思想構(gòu)建一棵思想構(gòu)建一棵可用于新樣本可用于新樣本分類的決策樹分類的決策樹A1-A1-公司職員公司職員A2-A2-年齡年齡A3-A3-收入收入A4-A4-信譽(yù)度信譽(yù)度C-C-買保險(xiǎn)買保險(xiǎn)否=40高良c2否50中良c1是50低良c1是50低優(yōu)c2是4150低優(yōu)c1否=40中良c2是50中良c1是50中優(yōu)c2第第1 1步：計(jì)算對(duì)訓(xùn)練集分類所需的期望信息步：計(jì)算對(duì)訓(xùn)練集分類所需的期望信息v 已知已知 total=14total=14 c1(c1(買保險(xiǎn)買保險(xiǎn)) )的樣本數(shù)量是的樣本數(shù)量是n1=9n1=9 c2(c

34、2(不買保險(xiǎn)不買保險(xiǎn)) )的樣本數(shù)量是的樣本數(shù)量是n2=5n2=5v 所以所以 P(c1)=9/14P(c1)=9/14 P(c2)=5/14P(c2)=5/14v 根據(jù)期望信息公式可得根據(jù)期望信息公式可得94. 0)145(log145)149(log149()(log)(),(2221221jjjcPcPnnI第第2 2步：計(jì)算步：計(jì)算A1A1（公司職員）的熵（公司職員）的熵v A1A1包含兩種取值：包含兩種取值：“是是”和和“否否”v 利用利用A1A1可將可將X X劃分為兩個(gè)子集劃分為兩個(gè)子集X1X1和和X2X2 X1X1中的數(shù)據(jù)樣本都是公司職員（中的數(shù)據(jù)樣本都是公司職員（7 7個(gè)）個(gè)）

35、 標(biāo)號(hào)為標(biāo)號(hào)為c1c1的有的有6 6個(gè)，個(gè)，n11=6n11=6 標(biāo)號(hào)為標(biāo)號(hào)為c2c2的有的有1 1個(gè)，個(gè)，n21=1n21=1 則可得則可得 p11=6/7p11=6/7 p21=1/7p21=1/7A1-A1-公司職員公司職員C-C-買保險(xiǎn)買保險(xiǎn)否c2否c2否c1否c1是c1是c2是c1否c2是c1是c1是c1否c1是c1否c2592. 0)71(log71)76(log76()(log),(22211212111jjjppnnI第第2 2步：計(jì)算步：計(jì)算A1A1（公司職員）的熵（公司職員）的熵v 利用利用A1A1可將可將X X劃分為兩個(gè)子集劃分為兩個(gè)子集X1X1和和X2X2 X2X2中的

36、數(shù)據(jù)樣本都不是公司職員（中的數(shù)據(jù)樣本都不是公司職員（7 7個(gè)）個(gè)） 標(biāo)號(hào)為標(biāo)號(hào)為c1c1的有的有3 3個(gè)，個(gè)，n12=3n12=3 標(biāo)號(hào)為標(biāo)號(hào)為c2c2的有的有4 4個(gè)，個(gè)，n22=4n22=4 則可得則可得 p12=3/7p12=3/7 p22=4/7p22=4/7A1-A1-公司職員公司職員C-C-買保險(xiǎn)買保險(xiǎn)否c2否c2否c1否c1是c1是c2是c1否c2是c1是c1是c1否c1是c1否c2985. 0)74(log74)73(log73()(log),(22212222212jjjppnnI第第2 2步：計(jì)算步：計(jì)算A1A1（公司職員）的熵（公司職員）的熵v 則計(jì)算出則計(jì)算出A1A1劃

37、分訓(xùn)練集所得的熵為劃分訓(xùn)練集所得的熵為789. 0985. 0147592. 0147),()(2121211sssssnnItotalnnAE第第3 3步：計(jì)算步：計(jì)算A1A1（公司職員）的信息增益（公司職員）的信息增益151. 0789. 094. 0)(),()(12111AEnnIAGainA益為：劃分?jǐn)?shù)據(jù)集時(shí)的信息增利用描述屬性第第4 4步：求出其他描述屬性的信息增益步：求出其他描述屬性的信息增益v Gain(A2)=0.246Gain(A2)=0.246v Gain(A3)=0.029Gain(A3)=0.029v Gain(A4)=0.048Gain(A4)=0.048v 經(jīng)比較

38、可知經(jīng)比較可知Gain(A2)Gain(A2)最大，所以選擇最大，所以選擇A2A2（年齡）作為決（年齡）作為決策樹的根節(jié)點(diǎn)策樹的根節(jié)點(diǎn)v 進(jìn)一步將樹劃分為進(jìn)一步將樹劃分為3 3個(gè)分支個(gè)分支第第5 5步：根據(jù)根節(jié)點(diǎn)劃分?jǐn)?shù)據(jù)集步：根據(jù)根節(jié)點(diǎn)劃分?jǐn)?shù)據(jù)集年齡年齡=405050的子集的子集在此子集內(nèi)繼續(xù)檢查在此子集內(nèi)繼續(xù)檢查Gain(A1)Gain(A1)、Gain(A3)Gain(A3)、Gain(A4)Gain(A4)選取信息增益最大的描述屬性作為內(nèi)部節(jié)點(diǎn)選取信息增益最大的描述屬性作為內(nèi)部節(jié)點(diǎn)A1-A1-公司職員公司職員A3-A3-收入收入A4-A4-信譽(yù)度信譽(yù)度C-C-買保險(xiǎn)買保險(xiǎn)否中良c1是低良

39、c1是低優(yōu)c2是中良c1否中優(yōu)c2ID3ID3算法小結(jié)算法小結(jié)v 使用使用ID3ID3算法的基本思想是算法的基本思想是 采用自頂向下的遞歸方式，將原始樣本空間劃分成若干更小的樣采用自頂向下的遞歸方式，將原始樣本空間劃分成若干更小的樣本空間本空間 再對(duì)他們單獨(dú)進(jìn)行處理再對(duì)他們單獨(dú)進(jìn)行處理 其中，選擇哪一個(gè)描述屬性作為新建節(jié)點(diǎn)，依據(jù)是考察該描述屬其中，選擇哪一個(gè)描述屬性作為新建節(jié)點(diǎn)，依據(jù)是考察該描述屬性的信息增益是否最大性的信息增益是否最大下載地址http:/ 使用信息增益作為屬性選擇依據(jù)使用信息增益作為屬性選擇依據(jù) 帶有傾向性，傾向于選擇取值較多的屬性帶有傾向性，傾向于選擇取值較多的屬性 為什么

40、？為什么？ 一種可能的解釋是：對(duì)于較難分類的集合，優(yōu)先將樣本分割到盡一種可能的解釋是：對(duì)于較難分類的集合，優(yōu)先將樣本分割到盡可能多的分支中將極大簡化分類工作可能多的分支中將極大簡化分類工作ID3ID3的不足（的不足（2/22/2）v 無法處理未知值的樣本無法處理未知值的樣本 對(duì)于個(gè)別樣本缺失了某項(xiàng)描述屬性的情況，無法處理對(duì)于個(gè)別樣本缺失了某項(xiàng)描述屬性的情況，無法處理v 無法處理連續(xù)值的樣本無法處理連續(xù)值的樣本 對(duì)于描述屬性是連續(xù)值的情況，無法處理對(duì)于描述屬性是連續(xù)值的情況，無法處理變化一：使用信息增益比變化一：使用信息增益比qsssfffffjsjssssffsqfqfffftotalntot

41、alnAsplitAsplitAGainAratioGainXAcXnXnaAXXXXqXAaaadfA122121)(log)()()()(_,q), 2 , 1(其中所得的信息增益比為：劃分則描述屬性的樣本數(shù)量中屬于類別表示子集中的樣本數(shù)量表示子集設(shè)上具有相同取值中的樣本在其中個(gè)子集劃分為可以將利用個(gè)不同的取值具有設(shè)描述屬性變化二：處理未知值的訓(xùn)練樣本（變化二：處理未知值的訓(xùn)練樣本（1/21/2）v 思想思想 將未知值用最常用的值來替代（較將未知值用最常用的值來替代（較容易）容易） 或，依據(jù)現(xiàn)有取值的概率分布來估或，依據(jù)現(xiàn)有取值的概率分布來估計(jì)未知值（較真實(shí)）計(jì)未知值（較真實(shí)）v 顯然：依

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

43、在已知樣本顯然：依據(jù)思想二，在已知樣本中年齡的三個(gè)區(qū)間分布是中年齡的三個(gè)區(qū)間分布是 =405050，5 5人人v 考慮未知值樣本后，分布更新為考慮未知值樣本后，分布更新為 =405050，5+5/135+5/13人人A2-A2-年齡年齡C-C-買保險(xiǎn)買保險(xiǎn)=40c250c150c150c24150c1=40c250c1？c14150c14150c150c2變化三：處理連續(xù)值的訓(xùn)練樣本（變化三：處理連續(xù)值的訓(xùn)練樣本（1/101/10）v 思想思想 將所有數(shù)據(jù)樣本按照連續(xù)型描述屬性將所有數(shù)據(jù)樣本按照連續(xù)型描述屬性AcAc的具體取值，由小到大進(jìn)的具體取值，由小到大進(jìn)行升序排列，得到的屬性值取值序列行

44、升序排列，得到的屬性值取值序列AA1c1c,A,A2c2c,.,A,.,Atotalctotalc 在在AA1c1c,A,A2c2c,.,A,.,Atotalctotalc 中生成中生成total-1total-1個(gè)分割點(diǎn)，第個(gè)分割點(diǎn)，第i i個(gè)分割點(diǎn)的取值個(gè)分割點(diǎn)的取值設(shè)置為設(shè)置為v vii=(A=(Aicic+A+A(i+1)c(i+1)c)/2)/2或者或者v vii=A=Aicic 該分割點(diǎn)將數(shù)據(jù)集劃分為兩個(gè)子集，即描述屬性該分割點(diǎn)將數(shù)據(jù)集劃分為兩個(gè)子集，即描述屬性A Ac c的取值在區(qū)間的取值在區(qū)間AA1c1c,v,vii 的數(shù)據(jù)樣本和在區(qū)間的數(shù)據(jù)樣本和在區(qū)間(v(vii,A,Ato

45、talctotalc 的數(shù)據(jù)樣本，顯然劃分共有的數(shù)據(jù)樣本，顯然劃分共有total-1total-1種方式種方式 從從total-1total-1個(gè)分割點(diǎn)中選擇最佳分割點(diǎn)。對(duì)于每一個(gè)分割點(diǎn)劃分?jǐn)?shù)個(gè)分割點(diǎn)中選擇最佳分割點(diǎn)。對(duì)于每一個(gè)分割點(diǎn)劃分?jǐn)?shù)據(jù)集的方式，計(jì)算其信息增益比，從中選擇信息增益比最大的分據(jù)集的方式，計(jì)算其信息增益比，從中選擇信息增益比最大的分割點(diǎn)來劃分?jǐn)?shù)據(jù)集割點(diǎn)來劃分?jǐn)?shù)據(jù)集變化三：處理連續(xù)值的訓(xùn)練樣本（變化三：處理連續(xù)值的訓(xùn)練樣本（2/102/10）v 示例示例 求利用求利用C4.5C4.5算法在連續(xù)值描述屬性算法在連續(xù)值描述屬性A A上的上的最佳分割點(diǎn)最佳分割點(diǎn)v 解：解： 第第0

46、0步，將步，將A A的取值升序排列的取值升序排列65,70,70,70,75,78,80,80,80,85,90,90,95,9665,70,70,70,75,78,80,80,80,85,90,90,95,96 第第1 1步，計(jì)算步，計(jì)算vi=65vi=65時(shí)的信息增益比時(shí)的信息增益比A AC C85c290c278c196c180c170c26565c1c195c270c180c170c190c175c180c294. 0)145(log145)149(log149()(log)(),(2221221jjjcPcPnnI變化三：處理連續(xù)值的訓(xùn)練樣本（變化三：處理連續(xù)值的訓(xùn)練樣本（3/103

47、/10）v 解：解： 第第1 1步，計(jì)算步，計(jì)算vi=65vi=65時(shí)的信息增益比時(shí)的信息增益比A AC C85c290c278c196c180c170c26565c1c195c270c180c170c190c175c180c20)10(log10)11(log11()(log),(22211212111jjjppnnI961. 0)135(log135)138(log138()(log),(22212222212jjjppnnI892. 0961. 014130141),()(2121211sssssnnItotalnnAE變化三：處理連續(xù)值的訓(xùn)練樣本（變化三：處理連續(xù)值的訓(xùn)練樣本（4/10

48、4/10）v 解：解： 第第1 1步，計(jì)算步，計(jì)算vi=65vi=65時(shí)的信息增益比時(shí)的信息增益比A AC C85c290c278c196c180c170c26565c1c195c270c180c170c190c175c180c2371. 01413log1413141log141)(log)(222121ssstotalntotalnAsplit129. 0371. 0892. 094. 0)()()(_1111AsplitAGainAratioGainX所得的信息增益比為：劃分在分割點(diǎn)變化三：處理連續(xù)值的訓(xùn)練樣本（變化三：處理連續(xù)值的訓(xùn)練樣本（5/105/10）v 解：解： 第第2 2步，

49、計(jì)算步，計(jì)算vi=70vi=70時(shí)的信息增益比時(shí)的信息增益比A AC C85c290c278c196c180c17070c2c26565c1c195c27070c1c180c17070c1c190c175c180c294. 0)145(log145)149(log149()(log)(),(2221221jjjcPcPnnI變化三：處理連續(xù)值的訓(xùn)練樣本（變化三：處理連續(xù)值的訓(xùn)練樣本（6/106/10）v 解：解： 第第2 2步，計(jì)算步，計(jì)算vi=70vi=70時(shí)的信息增益比時(shí)的信息增益比A AC C85c290c278c196c180c17070c2c26565c1c195c27070c1c1

50、80c17070c1c190c175c180c2811. 0)41(log41)43(log43()(log),(22211212111jjjppnnI971. 0)104(log104)106(log106()(log),(22212222212jjjppnnI926. 0971. 01410811. 0144),()(2121211sssssnnItotalnnAE變化三：處理連續(xù)值的訓(xùn)練樣本（變化三：處理連續(xù)值的訓(xùn)練樣本（7/107/10）v 解：解： 第第2 2步，計(jì)算步，計(jì)算vi=70vi=70時(shí)的信息增益比時(shí)的信息增益比A AC C85c290c278c196c180c17070c2c26565c1c195c27070c1c180c17070c1c190c175c180c2863. 01410log1410144log144)(log)(2