第3章 分類與決策樹

1、第第3章章分類與預(yù)測分類與預(yù)測主要內(nèi)容v分類與決策樹概述分類與決策樹概述vID3、C4.5與與C5.0vCART分類 VS. 預(yù)測v分類和預(yù)測是兩種數(shù)據(jù)分析形式，用于提取描述重要數(shù)據(jù)類或預(yù)測未來分類和預(yù)測是兩種數(shù)據(jù)分析形式，用于提取描述重要數(shù)據(jù)類或預(yù)測未來的數(shù)據(jù)趨勢的數(shù)據(jù)趨勢 的模型的模型分類：分類：v預(yù)測類對(duì)象的分類標(biāo)號(hào)（或離散值）預(yù)測類對(duì)象的分類標(biāo)號(hào)（或離散值）v根據(jù)訓(xùn)練數(shù)據(jù)集和類標(biāo)號(hào)屬性，構(gòu)建模型來分類現(xiàn)有數(shù)據(jù)，并用根據(jù)訓(xùn)練數(shù)據(jù)集和類標(biāo)號(hào)屬性，構(gòu)建模型來分類現(xiàn)有數(shù)據(jù)，并用來分類新數(shù)據(jù)來分類新數(shù)據(jù)預(yù)測：預(yù)測：v建立連續(xù)函數(shù)值模型建立連續(xù)函數(shù)值模型v比如預(yù)測空缺值，或者預(yù)測顧客在計(jì)算機(jī)設(shè)備上

2、的花費(fèi)比如預(yù)測空缺值，或者預(yù)測顧客在計(jì)算機(jī)設(shè)備上的花費(fèi)v典型應(yīng)用典型應(yīng)用欺詐檢測、市場定位、性能預(yù)測、醫(yī)療診斷欺詐檢測、市場定位、性能預(yù)測、醫(yī)療診斷v分類是一種應(yīng)用非常廣泛的數(shù)據(jù)挖掘技術(shù)分類是一種應(yīng)用非常廣泛的數(shù)據(jù)挖掘技術(shù) v分類與預(yù)測的區(qū)別：分類與預(yù)測的區(qū)別：當(dāng)估計(jì)的屬性值是離散值時(shí)，這就是當(dāng)估計(jì)的屬性值是離散值時(shí)，這就是分類分類；當(dāng)估計(jì)的屬性值是連續(xù)值時(shí)，這就是當(dāng)估計(jì)的屬性值是連續(xù)值時(shí)，這就是預(yù)測預(yù)測。分類和預(yù)測分類和預(yù)測-示例示例v分類分類銀行貸款員需要分析數(shù)據(jù)，來弄清哪些貸款申請(qǐng)銀行貸款員需要分析數(shù)據(jù)，來弄清哪些貸款申請(qǐng)者是安全的，哪些是有風(fēng)險(xiǎn)的（將貸款申請(qǐng)者分者是安全的，哪些是有風(fēng)險(xiǎn)

3、的（將貸款申請(qǐng)者分為為“安全安全”和和“有風(fēng)險(xiǎn)有風(fēng)險(xiǎn)”兩類）兩類）v我們需要構(gòu)造一個(gè)分類器來預(yù)測類屬編號(hào)，比如預(yù)測我們需要構(gòu)造一個(gè)分類器來預(yù)測類屬編號(hào)，比如預(yù)測顧客屬類顧客屬類v預(yù)測預(yù)測銀行貸款員需要預(yù)測貸給某個(gè)顧客多少錢是安全銀行貸款員需要預(yù)測貸給某個(gè)顧客多少錢是安全的的v構(gòu)造一個(gè)預(yù)測器，預(yù)測一個(gè)連續(xù)值函數(shù)或有序值，常構(gòu)造一個(gè)預(yù)測器，預(yù)測一個(gè)連續(xù)值函數(shù)或有序值，常用方法是回歸分析用方法是回歸分析數(shù)據(jù)分類數(shù)據(jù)分類一個(gè)兩步過程一個(gè)兩步過程 (1)v第一步，也成為學(xué)習(xí)步，目標(biāo)是建立描述預(yù)先定義的數(shù)第一步，也成為學(xué)習(xí)步，目標(biāo)是建立描述預(yù)先定義的數(shù)據(jù)類或概念集的分類器據(jù)類或概念集的分類器分類算法通過分

4、析或從訓(xùn)練集分類算法通過分析或從訓(xùn)練集“學(xué)習(xí)學(xué)習(xí)”來構(gòu)造分類器。來構(gòu)造分類器。訓(xùn)練集由數(shù)據(jù)庫元組（用訓(xùn)練集由數(shù)據(jù)庫元組（用n維屬性向量表示）和他們相對(duì)維屬性向量表示）和他們相對(duì)應(yīng)的類編號(hào)組成；假定每個(gè)元組屬于一個(gè)預(yù)定義的類應(yīng)的類編號(hào)組成；假定每個(gè)元組屬于一個(gè)預(yù)定義的類v訓(xùn)練元組：訓(xùn)練數(shù)據(jù)集中的單個(gè)元組訓(xùn)練元組：訓(xùn)練數(shù)據(jù)集中的單個(gè)元組學(xué)習(xí)模型可以用分類規(guī)則、決策樹或數(shù)學(xué)公式的形式提學(xué)習(xí)模型可以用分類規(guī)則、決策樹或數(shù)學(xué)公式的形式提供供數(shù)據(jù)分類數(shù)據(jù)分類一個(gè)兩步過程一個(gè)兩步過程 (2)v第二步，使用模型，對(duì)將來的或未知的對(duì)象進(jìn)行分類第二步，使用模型，對(duì)將來的或未知的對(duì)象進(jìn)行分類首先評(píng)估模型的預(yù)測準(zhǔn)確率

5、首先評(píng)估模型的預(yù)測準(zhǔn)確率v對(duì)每個(gè)測試樣本，將已知的類標(biāo)號(hào)和該樣本的學(xué)習(xí)模型類預(yù)測比對(duì)每個(gè)測試樣本，將已知的類標(biāo)號(hào)和該樣本的學(xué)習(xí)模型類預(yù)測比較較v模型在給定測試集上的準(zhǔn)確率是正確被模型分類的測試樣本的百模型在給定測試集上的準(zhǔn)確率是正確被模型分類的測試樣本的百分比分比v測試集要獨(dú)立于訓(xùn)練樣本集，否則會(huì)出現(xiàn)測試集要獨(dú)立于訓(xùn)練樣本集，否則會(huì)出現(xiàn)“過分?jǐn)M合過分?jǐn)M合”的情況的情況第一步建立模型訓(xùn)練數(shù)據(jù)集NAME RANKYEARS TENUREDMikeAssistant Prof3noMaryAssistant Prof7yesBill Professor2yesJimAssociate Prof7ye

6、sDaveAssistant Prof6noAnneAssociate Prof3no分類算法IF rank = professorOR years 6THEN tenured = yes 分類規(guī)則第二步用模型進(jìn)行分類分類規(guī)則測試集NAMERANKYEARS TENUREDTomAssistant Prof2noMerlisa Associate Prof7noGeorge Professor5yesJoseph Assistant Prof7yes未知數(shù)據(jù)(Jeff, Professor, 4)Tenured?監(jiān)督學(xué)習(xí)監(jiān)督學(xué)習(xí) VS. 無監(jiān)督學(xué)習(xí)無監(jiān)督學(xué)習(xí)v監(jiān)督學(xué)習(xí)（用于分類）監(jiān)督學(xué)習(xí)（用于

7、分類）模型的學(xué)習(xí)在被告知每個(gè)訓(xùn)練樣本屬于哪個(gè)類的模型的學(xué)習(xí)在被告知每個(gè)訓(xùn)練樣本屬于哪個(gè)類的“指導(dǎo)指導(dǎo)”下進(jìn)行下進(jìn)行新數(shù)據(jù)使用訓(xùn)練數(shù)據(jù)集中得到的規(guī)則進(jìn)行分類新數(shù)據(jù)使用訓(xùn)練數(shù)據(jù)集中得到的規(guī)則進(jìn)行分類v無監(jiān)督學(xué)習(xí)（用于聚類）無監(jiān)督學(xué)習(xí)（用于聚類）每個(gè)訓(xùn)練樣本的類編號(hào)是未知的，要學(xué)習(xí)的類集每個(gè)訓(xùn)練樣本的類編號(hào)是未知的，要學(xué)習(xí)的類集合或數(shù)量也可能是事先未知的合或數(shù)量也可能是事先未知的通過一系列的度量、觀察來建立數(shù)據(jù)中的類編號(hào)通過一系列的度量、觀察來建立數(shù)據(jù)中的類編號(hào)或進(jìn)行聚類或進(jìn)行聚類數(shù)據(jù)預(yù)測的兩步過程數(shù)據(jù)預(yù)測的兩步過程v數(shù)據(jù)預(yù)測也是一個(gè)兩步的過程，類似于前面描述的數(shù)據(jù)分類數(shù)據(jù)預(yù)測也是一個(gè)兩步的過程，類

8、似于前面描述的數(shù)據(jù)分類對(duì)于預(yù)測，沒有對(duì)于預(yù)測，沒有“類標(biāo)號(hào)屬性類標(biāo)號(hào)屬性”要預(yù)測的屬性是連續(xù)值，而不是離散值，該屬性可簡稱要預(yù)測的屬性是連續(xù)值，而不是離散值，該屬性可簡稱“預(yù)測屬性預(yù)測屬性”vE.g. 銀行貸款員需要預(yù)測貸給某個(gè)顧客多少錢是安全銀行貸款員需要預(yù)測貸給某個(gè)顧客多少錢是安全的的v預(yù)測器可以看作一個(gè)映射或函數(shù)預(yù)測器可以看作一個(gè)映射或函數(shù)y=f(X)其中其中X是輸入；是輸入；y是輸出，是一個(gè)連續(xù)或有序的值是輸出，是一個(gè)連續(xù)或有序的值與分類類似，準(zhǔn)確率的預(yù)測，也要使用單獨(dú)的測試集與分類類似，準(zhǔn)確率的預(yù)測，也要使用單獨(dú)的測試集3.1 決策樹概述決策樹概述v決策樹決策樹(Decision T

9、ree) 一種描述概念空間的有效的歸納推理辦法。一種描述概念空間的有效的歸納推理辦法?；跊Q策樹的學(xué)習(xí)方法可以進(jìn)行不相關(guān)的基于決策樹的學(xué)習(xí)方法可以進(jìn)行不相關(guān)的多概念學(xué)習(xí)，具有簡單快捷的優(yōu)勢，已經(jīng)多概念學(xué)習(xí)，具有簡單快捷的優(yōu)勢，已經(jīng)在各個(gè)領(lǐng)域取得廣泛應(yīng)用。在各個(gè)領(lǐng)域取得廣泛應(yīng)用。v決策樹是一種樹型結(jié)構(gòu)，其中每個(gè)內(nèi)部結(jié)決策樹是一種樹型結(jié)構(gòu)，其中每個(gè)內(nèi)部結(jié)點(diǎn)表示在一個(gè)屬性上的測試，每個(gè)分支代點(diǎn)表示在一個(gè)屬性上的測試，每個(gè)分支代表一個(gè)測試輸出，每個(gè)葉結(jié)點(diǎn)代表一種類表一個(gè)測試輸出，每個(gè)葉結(jié)點(diǎn)代表一種類別。別。v決策樹學(xué)習(xí)是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)。決策樹學(xué)習(xí)是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)。v從一類無序、無規(guī)則的

10、事物（概念）中推理出決策樹表示的分類規(guī)從一類無序、無規(guī)則的事物（概念）中推理出決策樹表示的分類規(guī)則。則。v概念分類學(xué)習(xí)算法：來源于概念分類學(xué)習(xí)算法：來源于Hunt,Marin和和Stone 于于1966年研制的年研制的CLS學(xué)習(xí)系統(tǒng)，用于學(xué)習(xí)學(xué)習(xí)系統(tǒng)，用于學(xué)習(xí)單個(gè)概念。單個(gè)概念。1979年年, J.R. Quinlan 給出給出ID3算法，并在算法，并在1983年和年和1986年對(duì)年對(duì)ID3 進(jìn)行了總結(jié)和簡化，使其成為決策樹學(xué)習(xí)算法的典型。進(jìn)行了總結(jié)和簡化，使其成為決策樹學(xué)習(xí)算法的典型。Schlimmer 和和Fisher 于于1986年對(duì)年對(duì)ID3進(jìn)行改造，在每個(gè)可能的進(jìn)行改造，在每個(gè)可能的

11、決策樹節(jié)點(diǎn)創(chuàng)建緩沖區(qū)，使決策樹可以遞增式生成，得到?jīng)Q策樹節(jié)點(diǎn)創(chuàng)建緩沖區(qū)，使決策樹可以遞增式生成，得到ID4算算法。法。1988年，年，Utgoff 在在ID4基礎(chǔ)上提出了基礎(chǔ)上提出了ID5學(xué)習(xí)算法，進(jìn)一步提高學(xué)習(xí)算法，進(jìn)一步提高了效率。了效率。1993年，年，Quinlan 進(jìn)一步發(fā)展了進(jìn)一步發(fā)展了ID3算法，改進(jìn)成算法，改進(jìn)成C4.5算法。算法。另一類決策樹算法為另一類決策樹算法為CART，與，與C4.5不同的是，不同的是，CART的決策樹的決策樹由二元邏輯問題生成，每個(gè)樹節(jié)點(diǎn)只有兩個(gè)分枝，分別包括學(xué)習(xí)由二元邏輯問題生成，每個(gè)樹節(jié)點(diǎn)只有兩個(gè)分枝，分別包括學(xué)習(xí)實(shí)例的正例與反例。實(shí)例的正例與反例

12、。v其基本思想是以信息熵為度量構(gòu)造一棵熵值下降最快的樹，到葉子其基本思想是以信息熵為度量構(gòu)造一棵熵值下降最快的樹，到葉子節(jié)點(diǎn)處的熵值為零，此時(shí)每個(gè)葉節(jié)點(diǎn)中的實(shí)例都屬于同一類。節(jié)點(diǎn)處的熵值為零，此時(shí)每個(gè)葉節(jié)點(diǎn)中的實(shí)例都屬于同一類。v決策樹學(xué)習(xí)采用的是自頂向下的遞歸方法。決策樹學(xué)習(xí)采用的是自頂向下的遞歸方法。v決策樹的每一層節(jié)點(diǎn)依照某一屬性值向下分為子節(jié)點(diǎn)，待決策樹的每一層節(jié)點(diǎn)依照某一屬性值向下分為子節(jié)點(diǎn)，待分類的實(shí)例在每一節(jié)點(diǎn)處與該節(jié)點(diǎn)相關(guān)的屬性值進(jìn)行比較，分類的實(shí)例在每一節(jié)點(diǎn)處與該節(jié)點(diǎn)相關(guān)的屬性值進(jìn)行比較，根據(jù)不同的比較結(jié)果向相應(yīng)的子節(jié)點(diǎn)擴(kuò)展，這一過程在到根據(jù)不同的比較結(jié)果向相應(yīng)的子節(jié)點(diǎn)擴(kuò)展，

13、這一過程在到達(dá)決策樹的葉節(jié)點(diǎn)時(shí)結(jié)束，此時(shí)得到結(jié)論。達(dá)決策樹的葉節(jié)點(diǎn)時(shí)結(jié)束，此時(shí)得到結(jié)論。v從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每一條路經(jīng)都對(duì)應(yīng)著一條合理的規(guī)則，從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每一條路經(jīng)都對(duì)應(yīng)著一條合理的規(guī)則，規(guī)則間各個(gè)部分（各個(gè)層的條件）的關(guān)系是合取關(guān)系。整規(guī)則間各個(gè)部分（各個(gè)層的條件）的關(guān)系是合取關(guān)系。整個(gè)決策樹就對(duì)應(yīng)著一組析取的規(guī)則。個(gè)決策樹就對(duì)應(yīng)著一組析取的規(guī)則。v決策樹學(xué)習(xí)算法的最大優(yōu)點(diǎn)是，它可以自學(xué)習(xí)。在學(xué)習(xí)的決策樹學(xué)習(xí)算法的最大優(yōu)點(diǎn)是，它可以自學(xué)習(xí)。在學(xué)習(xí)的過程中，不需要使用者了解過多背景知識(shí)，只需要對(duì)訓(xùn)練過程中，不需要使用者了解過多背景知識(shí)，只需要對(duì)訓(xùn)練例子進(jìn)行較好的標(biāo)注，就能夠進(jìn)行學(xué)習(xí)。如果

14、在應(yīng)用中發(fā)例子進(jìn)行較好的標(biāo)注，就能夠進(jìn)行學(xué)習(xí)。如果在應(yīng)用中發(fā)現(xiàn)不符合規(guī)則的實(shí)例，程序會(huì)詢問用戶該實(shí)例的正確分類，現(xiàn)不符合規(guī)則的實(shí)例，程序會(huì)詢問用戶該實(shí)例的正確分類，從而生成新的分枝和葉子，并添加到樹中。從而生成新的分枝和葉子，并添加到樹中。 v樹是由節(jié)點(diǎn)和分枝組成的層樹是由節(jié)點(diǎn)和分枝組成的層次數(shù)據(jù)結(jié)構(gòu)。節(jié)點(diǎn)用于存貯次數(shù)據(jù)結(jié)構(gòu)。節(jié)點(diǎn)用于存貯信息或知識(shí)，分枝用于連接信息或知識(shí)，分枝用于連接各個(gè)節(jié)點(diǎn)。樹是圖的一個(gè)特各個(gè)節(jié)點(diǎn)。樹是圖的一個(gè)特例，圖是更一般的數(shù)學(xué)結(jié)構(gòu)，例，圖是更一般的數(shù)學(xué)結(jié)構(gòu)，如貝葉斯網(wǎng)絡(luò)。如貝葉斯網(wǎng)絡(luò)。v決策樹是描述分類過程的一決策樹是描述分類過程的一種數(shù)據(jù)結(jié)構(gòu)，從上端的根節(jié)種數(shù)據(jù)結(jié)構(gòu)

15、，從上端的根節(jié)點(diǎn)開始，各種分類原則被引點(diǎn)開始，各種分類原則被引用進(jìn)來，并依這些分類原則用進(jìn)來，并依這些分類原則將根節(jié)點(diǎn)的數(shù)據(jù)集劃分為子將根節(jié)點(diǎn)的數(shù)據(jù)集劃分為子集，這一劃分過程直到某種集，這一劃分過程直到某種約束條件滿足而結(jié)束。約束條件滿足而結(jié)束。 根結(jié)點(diǎn)根結(jié)點(diǎn)個(gè)子大個(gè)子大可能是松鼠可能是松鼠可能是老鼠可能是老鼠可能是大象可能是大象在水里在水里會(huì)吱吱叫會(huì)吱吱叫鼻子長鼻子長脖子長脖子長個(gè)子小個(gè)子小不會(huì)吱吱叫不會(huì)吱吱叫鼻子短鼻子短脖子短脖子短可能是長頸鹿可能是長頸鹿在陸地上在陸地上可能是犀?？赡苁窍？赡苁呛玉R可能是河馬v可以看到，一個(gè)決策樹的內(nèi)部結(jié)點(diǎn)包含學(xué)習(xí)的實(shí)例，每層分枝可以看到，一個(gè)決策樹的內(nèi)

16、部結(jié)點(diǎn)包含學(xué)習(xí)的實(shí)例，每層分枝代表了實(shí)例的一個(gè)屬性的可能取值，葉節(jié)點(diǎn)是最終劃分成的類。代表了實(shí)例的一個(gè)屬性的可能取值，葉節(jié)點(diǎn)是最終劃分成的類。如果判定是二元的，那么構(gòu)造的將是一棵二叉樹，在樹中每回如果判定是二元的，那么構(gòu)造的將是一棵二叉樹，在樹中每回答一個(gè)問題就降到樹的下一層，這類樹一般稱為答一個(gè)問題就降到樹的下一層，這類樹一般稱為CART（Classification And Regression Tree）。）。v判定結(jié)構(gòu)可以機(jī)械的轉(zhuǎn)變成產(chǎn)生式規(guī)則。可以通過對(duì)結(jié)構(gòu)進(jìn)行判定結(jié)構(gòu)可以機(jī)械的轉(zhuǎn)變成產(chǎn)生式規(guī)則。可以通過對(duì)結(jié)構(gòu)進(jìn)行廣度優(yōu)先搜索，并在每個(gè)節(jié)點(diǎn)生成廣度優(yōu)先搜索，并在每個(gè)節(jié)點(diǎn)生成“IFTH

17、EN”規(guī)則來實(shí)現(xiàn)。規(guī)則來實(shí)現(xiàn)。如圖如圖6-13的決策樹可以轉(zhuǎn)換成下規(guī)則：的決策樹可以轉(zhuǎn)換成下規(guī)則： IF “個(gè)子大個(gè)子大” THEN IF “脖子短脖子短” THEN IF “鼻子長鼻子長” THEN 可能是大象可能是大象形式化表示成形式化表示成可能是大象鼻子長脖子短個(gè)子大 根結(jié)點(diǎn)根結(jié)點(diǎn)個(gè) 子個(gè) 子大大可 能 是 松可 能 是 松鼠鼠可 能 是 老可 能 是 老鼠鼠可 能 是 大可 能 是 大象象在 水在 水里里會(huì) 吱 吱會(huì) 吱 吱叫叫鼻 子鼻 子長長脖 子脖 子長長個(gè)子小個(gè)子小不會(huì)吱吱不會(huì)吱吱叫叫鼻子鼻子短短脖子脖子短短可能是長頸可能是長頸鹿鹿在 陸 地在 陸 地上上可 能 是 犀可 能 是

18、 犀牛牛可 能 是 河可 能 是 河馬馬v構(gòu)造一棵決策樹要解決四個(gè)問題：構(gòu)造一棵決策樹要解決四個(gè)問題：收集待分類的數(shù)據(jù)，這些數(shù)據(jù)的所有屬性應(yīng)該是完全標(biāo)注的。收集待分類的數(shù)據(jù)，這些數(shù)據(jù)的所有屬性應(yīng)該是完全標(biāo)注的。設(shè)計(jì)分類原則，即數(shù)據(jù)的哪些屬性可以被用來分類，以及如何將該屬性量設(shè)計(jì)分類原則，即數(shù)據(jù)的哪些屬性可以被用來分類，以及如何將該屬性量化?；７诸愒瓌t的選擇，即在眾多分類準(zhǔn)則中，每一步選擇哪一準(zhǔn)則使最終的樹分類原則的選擇，即在眾多分類準(zhǔn)則中，每一步選擇哪一準(zhǔn)則使最終的樹更令人滿意。更令人滿意。設(shè)計(jì)分類停止條件，實(shí)際應(yīng)用中數(shù)據(jù)的屬性很多，真正有分類意義的屬性設(shè)計(jì)分類停止條件，實(shí)際應(yīng)用中數(shù)據(jù)的屬性

19、很多，真正有分類意義的屬性往往是有限幾個(gè)，因此在必要的時(shí)候應(yīng)該停止數(shù)據(jù)集分裂：往往是有限幾個(gè)，因此在必要的時(shí)候應(yīng)該停止數(shù)據(jù)集分裂：v該節(jié)點(diǎn)包含的數(shù)據(jù)太少不足以分裂，該節(jié)點(diǎn)包含的數(shù)據(jù)太少不足以分裂，v繼續(xù)分裂數(shù)據(jù)集對(duì)樹生成的目標(biāo)繼續(xù)分裂數(shù)據(jù)集對(duì)樹生成的目標(biāo)(例如例如ID3中的熵下降準(zhǔn)則中的熵下降準(zhǔn)則)沒有貢獻(xiàn)，沒有貢獻(xiàn)，v樹的深度過大不宜再分。樹的深度過大不宜再分。v通用的決策樹分裂目標(biāo)是整棵樹的熵總量最小，每一步分裂時(shí)，選擇使熵減小通用的決策樹分裂目標(biāo)是整棵樹的熵總量最小，每一步分裂時(shí)，選擇使熵減小最大的準(zhǔn)則，這種方案使最具有分類潛力的準(zhǔn)則最先被提取出來最大的準(zhǔn)則，這種方案使最具有分類潛力的準(zhǔn)

20、則最先被提取出來 預(yù)測變量目標(biāo)變量記錄樣本類標(biāo)號(hào)屬性類別集合：類別集合：Class=“優(yōu)優(yōu)”，“良良”，“差差” 決策樹的基本原理 根節(jié)點(diǎn)根節(jié)點(diǎn)葉子節(jié)點(diǎn)葉子節(jié)點(diǎn)分裂屬性分裂屬性分裂謂詞分裂謂詞 每一個(gè)葉子節(jié)點(diǎn)都被確定一個(gè)類標(biāo)號(hào)每一個(gè)葉子節(jié)點(diǎn)都被確定一個(gè)類標(biāo)號(hào) v每一個(gè)節(jié)點(diǎn)都代表了一個(gè)數(shù)據(jù)集。每一個(gè)節(jié)點(diǎn)都代表了一個(gè)數(shù)據(jù)集。根節(jié)點(diǎn)根節(jié)點(diǎn)1代表了初始數(shù)據(jù)集代表了初始數(shù)據(jù)集D其它節(jié)點(diǎn)都是數(shù)據(jù)集其它節(jié)點(diǎn)都是數(shù)據(jù)集D的子集。的子集。v例如，節(jié)點(diǎn)例如，節(jié)點(diǎn)2代表數(shù)據(jù)集代表數(shù)據(jù)集D中年齡小于中年齡小于40歲的那部分樣本組成歲的那部分樣本組成的數(shù)據(jù)集。的數(shù)據(jù)集。v子節(jié)點(diǎn)是父節(jié)點(diǎn)的子集。子節(jié)點(diǎn)是父節(jié)點(diǎn)的子集。 v

21、If (年齡年齡40) and (職業(yè)職業(yè)=“學(xué)生學(xué)生” or職業(yè)職業(yè)=“教師教師”) Then 信用等級(jí)信用等級(jí)=“優(yōu)優(yōu)”vIf (年齡年齡40) and (職業(yè)職業(yè)!=“學(xué)生學(xué)生”and職業(yè)職業(yè)!=“教師教師”) Then 信用等信用等級(jí)級(jí)=“良良”vIf (年齡年齡40) and (月薪月薪3000) Then 信用等級(jí)信用等級(jí)=“優(yōu)優(yōu)”v決策樹是指具有下列三個(gè)性質(zhì)的樹：決策樹是指具有下列三個(gè)性質(zhì)的樹：每個(gè)非葉子節(jié)點(diǎn)都被標(biāo)記一個(gè)分裂屬性每個(gè)非葉子節(jié)點(diǎn)都被標(biāo)記一個(gè)分裂屬性Ai；每個(gè)分支都被標(biāo)記一個(gè)分裂謂詞，這個(gè)分裂謂每個(gè)分支都被標(biāo)記一個(gè)分裂謂詞，這個(gè)分裂謂詞是分裂父節(jié)點(diǎn)的具體依據(jù)；詞是分裂

22、父節(jié)點(diǎn)的具體依據(jù)；每個(gè)葉子節(jié)點(diǎn)都被標(biāo)記一個(gè)類標(biāo)號(hào)每個(gè)葉子節(jié)點(diǎn)都被標(biāo)記一個(gè)類標(biāo)號(hào)CjC。v任何一個(gè)決策樹算法，其核心步驟都是為任何一個(gè)決策樹算法，其核心步驟都是為每一次分裂確定一個(gè)每一次分裂確定一個(gè)分裂屬性分裂屬性，即究竟按，即究竟按照哪一個(gè)屬性來把當(dāng)前數(shù)據(jù)集劃分為若干照哪一個(gè)屬性來把當(dāng)前數(shù)據(jù)集劃分為若干個(gè)子集，從而形成若干個(gè)個(gè)子集，從而形成若干個(gè)“樹枝樹枝”。v熵，是數(shù)據(jù)集中的不確定性、突發(fā)性或隨機(jī)性的熵，是數(shù)據(jù)集中的不確定性、突發(fā)性或隨機(jī)性的程度的度量。程度的度量。v當(dāng)一個(gè)數(shù)據(jù)集中的記錄全部都屬于同一類的時(shí)候，當(dāng)一個(gè)數(shù)據(jù)集中的記錄全部都屬于同一類的時(shí)候，則沒有不確定性，這種情況下的熵就為則沒

23、有不確定性，這種情況下的熵就為0。v決策樹分裂的基本原則是，數(shù)據(jù)集被分裂為若干決策樹分裂的基本原則是，數(shù)據(jù)集被分裂為若干個(gè)子集后，要使每個(gè)子集中的數(shù)據(jù)盡可能的個(gè)子集后，要使每個(gè)子集中的數(shù)據(jù)盡可能的“純純”，也就是說子集中的記錄要盡可能屬于同，也就是說子集中的記錄要盡可能屬于同一個(gè)類別。如果套用熵的概念，即要使分裂后各一個(gè)類別。如果套用熵的概念，即要使分裂后各子集的熵盡可能的小。子集的熵盡可能的小。3.2 ID3、C4.5與與C5.0ID3=C4.5=C5.0vRoss QuinlanID3 1986年C4.5 1993年C5.0 1998年 2011年獲得KDD創(chuàng)新獎(jiǎng)vhttp:/ 和和D2

24、信息增益信息增益:Gain(D,年齡年齡)= H(D)P(D1)H(D1)+ P(D2)H(D2) v顯然，如果顯然，如果D1和和D2中的數(shù)據(jù)越中的數(shù)據(jù)越“純純”，H(D1)和和H(D2)就越小，信就越小，信息增益就越大，或者說熵下降得越息增益就越大，或者說熵下降得越多。多。v按照這個(gè)方法，測試每一個(gè)屬性的信按照這個(gè)方法，測試每一個(gè)屬性的信息增益，選擇增益值最大的屬性作為息增益，選擇增益值最大的屬性作為分裂屬性。分裂屬性。信息熵計(jì)算舉例信息熵計(jì)算舉例v令令C1對(duì)應(yīng)對(duì)應(yīng)“是是”，C2對(duì)應(yīng)對(duì)應(yīng)“否否”。那么。那么C1有有9個(gè)樣個(gè)樣本，本，C2有有5個(gè)樣本，所以數(shù)據(jù)集個(gè)樣本，所以數(shù)據(jù)集D的熵為：的熵

25、為：9406. 0)145(log145)149(log149)5 , 9(),(2221 IssI決策樹歸納策略 (1)v輸入輸入數(shù)據(jù)劃分?jǐn)?shù)據(jù)劃分D是訓(xùn)練元組和對(duì)應(yīng)類標(biāo)號(hào)的集合是訓(xùn)練元組和對(duì)應(yīng)類標(biāo)號(hào)的集合attribute_list,候選屬性的集合候選屬性的集合Attribute_selection_method，指定選擇屬性的啟發(fā)性過程，指定選擇屬性的啟發(fā)性過程算法步驟算法步驟1.樹以代表訓(xùn)練樣本的單個(gè)節(jié)點(diǎn)（樹以代表訓(xùn)練樣本的單個(gè)節(jié)點(diǎn)（N）開始）開始2.如果樣本都在同一個(gè)類，則該節(jié)點(diǎn)成為樹葉，并用該類標(biāo)記如果樣本都在同一個(gè)類，則該節(jié)點(diǎn)成為樹葉，并用該類標(biāo)記3.否則，算法調(diào)用否則，算法調(diào)用A

26、ttribute_selection_method，選擇能夠最，選擇能夠最好的將樣本分類的屬性；確定好的將樣本分類的屬性；確定“分裂準(zhǔn)則分裂準(zhǔn)則”，指出，指出“分裂點(diǎn)分裂點(diǎn)”或或“分裂子集分裂子集”。決策樹歸納策略 (2)4.對(duì)測試屬性每個(gè)已知的值，創(chuàng)建一個(gè)分支，對(duì)測試屬性每個(gè)已知的值，創(chuàng)建一個(gè)分支，并以此劃分元組并以此劃分元組5.算法使用同樣的過程，遞歸的形成每個(gè)劃分算法使用同樣的過程，遞歸的形成每個(gè)劃分上的元組決策樹。一旦一個(gè)屬性出現(xiàn)在一個(gè)上的元組決策樹。一旦一個(gè)屬性出現(xiàn)在一個(gè)節(jié)點(diǎn)上，就不在該節(jié)點(diǎn)的任何子節(jié)點(diǎn)上出現(xiàn)節(jié)點(diǎn)上，就不在該節(jié)點(diǎn)的任何子節(jié)點(diǎn)上出現(xiàn)6.遞歸劃分步驟停止的條件遞歸劃分步驟

27、停止的條件劃分劃分D（在（在N節(jié)點(diǎn)提供）的所有元組屬于同一類節(jié)點(diǎn)提供）的所有元組屬于同一類沒有剩余屬性可以用來進(jìn)一步劃分元組沒有剩余屬性可以用來進(jìn)一步劃分元組使用多數(shù)表決使用多數(shù)表決沒有剩余的樣本沒有剩余的樣本給定分支沒有元組，則以給定分支沒有元組，則以D中多數(shù)類創(chuàng)建一個(gè)樹葉中多數(shù)類創(chuàng)建一個(gè)樹葉屬性選擇度量v屬性選擇度量是一種選擇分裂準(zhǔn)則，將給定屬性選擇度量是一種選擇分裂準(zhǔn)則，將給定類標(biāo)號(hào)的訓(xùn)練元組最好的進(jìn)行劃分的方法類標(biāo)號(hào)的訓(xùn)練元組最好的進(jìn)行劃分的方法理想情況，每個(gè)劃分都是理想情況，每個(gè)劃分都是“純純”的，即落在給定的，即落在給定劃分內(nèi)的元組都屬于相同的類劃分內(nèi)的元組都屬于相同的類屬性選擇度

28、量又稱為分裂準(zhǔn)則屬性選擇度量又稱為分裂準(zhǔn)則v常用的屬性選擇度量常用的屬性選擇度量信息增益信息增益增益率增益率Gini指標(biāo)指標(biāo)信息增益信息增益 (1)vS是一個(gè)是一個(gè)訓(xùn)練樣本訓(xùn)練樣本的集合，該樣本中每個(gè)集的集合，該樣本中每個(gè)集合的合的類編號(hào)類編號(hào)已知。每個(gè)樣本為一個(gè)已知。每個(gè)樣本為一個(gè)元組元組。有個(gè)屬性用來判定某個(gè)訓(xùn)練樣本的類編號(hào)有個(gè)屬性用來判定某個(gè)訓(xùn)練樣本的類編號(hào)v假設(shè)假設(shè)S中有中有m個(gè)類，總共個(gè)類，總共s個(gè)訓(xùn)練樣本，每個(gè)訓(xùn)練樣本，每個(gè)類個(gè)類Ci有有si個(gè)樣本個(gè)樣本(i1,2,3.m)，那么任意，那么任意一個(gè)樣本屬于類一個(gè)樣本屬于類Ci的概率是的概率是si / s，那么用，那么用來分類一個(gè)給定

29、樣本的來分類一個(gè)給定樣本的期望信息期望信息是：是：sssssssInfoimiim2121log),.,(信息增益信息增益 (2)v一個(gè)有一個(gè)有v個(gè)值的屬性個(gè)值的屬性Aa1,a2,.,av可以將可以將S分成分成v個(gè)子集個(gè)子集S1,S2,.,Sv，其中，其中Sj包含包含S中屬性中屬性A上的值為上的值為aj的樣本的樣本。假設(shè)。假設(shè)Sj包含類包含類Ci的的sij個(gè)樣本。根據(jù)個(gè)樣本。根據(jù)A的這種劃分的期的這種劃分的期望信息稱為望信息稱為A的的熵熵vA上該劃分的獲得的信息增益定義為：上該劃分的獲得的信息增益定義為：v具有高信息增益的屬性，是給定集合中具有高區(qū)分度的具有高信息增益的屬性，是給定集合中具有高

30、區(qū)分度的屬性。所以可以通過計(jì)算屬性。所以可以通過計(jì)算S中樣本的每個(gè)屬性的信息增中樣本的每個(gè)屬性的信息增益，來得到一個(gè)屬性的相關(guān)性的排序。益，來得到一個(gè)屬性的相關(guān)性的排序。),.,(.)(111mjjvjmjjssIsssAE)(),.,()(21AEsssIAGainmv若以若以“年齡年齡”作為分裂屬性，作為分裂屬性，則產(chǎn)生三個(gè)子集（因?yàn)樵搶賱t產(chǎn)生三個(gè)子集（因?yàn)樵搶傩杂腥齻€(gè)不同的取值），所性有三個(gè)不同的取值），所以以D按照屬性按照屬性“年齡年齡”劃分劃分出的三個(gè)子集的熵的加權(quán)和出的三個(gè)子集的熵的加權(quán)和為：為：6936. 03468. 003468. 0)52log5253log53(145)4

31、4log44(144)52log5253log53(145),(22222年齡DE其中有一個(gè)子集的熵為其中有一個(gè)子集的熵為0247. 06936. 09406. 0),(),(),(21年齡年齡DEssIDGain9406. 0)145(log145)149(log149)5 , 9(),(2221 IssIv同理，若以“收入水平”為分裂屬性：9111. 02318. 03936. 08572 . 0)41log4143log43(144)62log6264log64(146)42log4242log42(144),(222222收入水平DE2950 . 09111. 09406. 0),()

32、,(),(21收入水平收入水平DEssIDGainv若以“有固定收入”為分裂屬性：v若以“VIP”為分裂屬性：7886. 02959. 04927. 0)71log7176log76(147)73log7374log74(147),(2222固定收入DE152. 07886. 09406. 0),(),(),(21固定收入固定收入DEssIDGain9228 . 02864 . 04636. 0)63log6363log63(146)82log8286log86(148)VIP,(2222DE0484. 08922. 09406. 0),(),(),(21VIPDEssIVIPDGain以以“

33、年齡年齡”作為分裂屬性，所得信息增益最大。作為分裂屬性，所得信息增益最大。 葉子節(jié)點(diǎn)葉子節(jié)點(diǎn)ID3的主要缺點(diǎn)的主要缺點(diǎn)vID3算法只能處理分類屬性（離散屬性），而不能算法只能處理分類屬性（離散屬性），而不能處理連續(xù)屬性（數(shù)值屬性）。在處理連續(xù)屬性時(shí)，處理連續(xù)屬性（數(shù)值屬性）。在處理連續(xù)屬性時(shí)，一般要先將連續(xù)屬性劃分為多個(gè)區(qū)間，轉(zhuǎn)化為分一般要先將連續(xù)屬性劃分為多個(gè)區(qū)間，轉(zhuǎn)化為分類屬性。例如類屬性。例如“年齡年齡”，要把數(shù)值事先轉(zhuǎn)換為諸，要把數(shù)值事先轉(zhuǎn)換為諸如如“小于小于30歲歲”、“30至至50歲歲”、“大于大于50歲歲”這樣的區(qū)間，再根據(jù)年齡值落入了某一個(gè)區(qū)間取這樣的區(qū)間，再根據(jù)年齡值落入了某

34、一個(gè)區(qū)間取相應(yīng)的類別值。通常，區(qū)間端點(diǎn)的選取包含著一相應(yīng)的類別值。通常，區(qū)間端點(diǎn)的選取包含著一定的主觀因素。定的主觀因素。vID3生成的決策樹是一棵多叉樹，分支的數(shù)量取決生成的決策樹是一棵多叉樹，分支的數(shù)量取決于分裂屬性有多少個(gè)不同的取值。這不利于處理于分裂屬性有多少個(gè)不同的取值。這不利于處理分裂屬性取值數(shù)目較多的情況。因此目前流行的分裂屬性取值數(shù)目較多的情況。因此目前流行的決策樹算法大多采用二叉樹模型。決策樹算法大多采用二叉樹模型。vID3是采用是采用“信息增益信息增益”來選擇分裂屬性的。雖然來選擇分裂屬性的。雖然這是一種有效的方法，但其具有明顯的傾向性，這是一種有效的方法，但其具有明顯的傾

35、向性，即它傾向于選擇具有大量不同取值的屬性，從而即它傾向于選擇具有大量不同取值的屬性，從而產(chǎn)生許多小而純的子集。產(chǎn)生許多小而純的子集。v尤其是關(guān)系數(shù)據(jù)庫中作為主鍵的屬性，每一個(gè)樣尤其是關(guān)系數(shù)據(jù)庫中作為主鍵的屬性，每一個(gè)樣本都有一個(gè)不同的取值。如果以這樣的屬性作為本都有一個(gè)不同的取值。如果以這樣的屬性作為分裂屬性，那么將產(chǎn)生非常多的分支，而且每一分裂屬性，那么將產(chǎn)生非常多的分支，而且每一個(gè)分支產(chǎn)生的子集的熵均為個(gè)分支產(chǎn)生的子集的熵均為0（因?yàn)樽蛹兄挥校ㄒ驗(yàn)樽蛹兄挥幸粋€(gè)樣本?。ｏ@然，這樣的決策樹是沒有實(shí)際一個(gè)樣本?。?。顯然，這樣的決策樹是沒有實(shí)際意義的。因此，意義的。因此，Quinlan提出

36、使用增益比例來代提出使用增益比例來代替信息增益。替信息增益。 3.2.2 C4.5v設(shè)設(shè)S代表訓(xùn)練數(shù)據(jù)集，由代表訓(xùn)練數(shù)據(jù)集，由s個(gè)樣本組成。個(gè)樣本組成。A是是S的某個(gè)屬性，有的某個(gè)屬性，有m個(gè)不同的取值，根據(jù)這個(gè)不同的取值，根據(jù)這些取值可以把些取值可以把S劃分為劃分為m個(gè)子集，個(gè)子集，Si表示第表示第i個(gè)子集（個(gè)子集（i=1,2,m），），|Si|表示子集表示子集Si中的中的樣本數(shù)量。那么：樣本數(shù)量。那么：)|log|(),(_21sSsSASInfoSplitimii稱為“數(shù)據(jù)集數(shù)據(jù)集S關(guān)于屬性關(guān)于屬性A的熵的熵”。 v用來衡量屬性A分裂數(shù)據(jù)集的廣度和均勻性。樣本在屬性A上的取值分布越均勻，

37、Split_Info(S,A)的值就越大。v增益比例的定義為：v增益比例消除了選擇那些值較多且均勻分布的屬性作為分裂屬性的傾向性。),(_ASInfoSplit),(_),(),(ASInfoSplitASGainASGainRatio連續(xù)屬性的處理連續(xù)屬性的處理 v設(shè)屬性設(shè)屬性Y有有m個(gè)不同的取值，按大小順序升序排列個(gè)不同的取值，按大小順序升序排列為為v1v2, vi”將數(shù)據(jù)集劃分為兩個(gè)部分，將數(shù)據(jù)集劃分為兩個(gè)部分，形成兩個(gè)分支。顯然，形成兩個(gè)分支。顯然， v1,v2, vm-1就是可能的就是可能的閾值的集合，共閾值的集合，共(m-1)個(gè)元素。個(gè)元素。v把這些閾值一一取出來，并根據(jù)把這些閾值

38、一一取出來，并根據(jù)“Yvi”和和“Y vi”把訓(xùn)練數(shù)據(jù)集劃分為兩個(gè)子集，并計(jì)算每一種劃把訓(xùn)練數(shù)據(jù)集劃分為兩個(gè)子集，并計(jì)算每一種劃分方案下的信息增益或增益比例，選擇最大增益分方案下的信息增益或增益比例，選擇最大增益或增益比例所對(duì)應(yīng)的那個(gè)閾值，作為最優(yōu)的閾值。或增益比例所對(duì)應(yīng)的那個(gè)閾值，作為最優(yōu)的閾值。v可以看出，如果選擇連續(xù)屬性作為分裂屬性，則可以看出，如果選擇連續(xù)屬性作為分裂屬性，則分裂后只有兩個(gè)分支，而不象離散屬性那樣可能分裂后只有兩個(gè)分支，而不象離散屬性那樣可能會(huì)有多個(gè)分支（由離散屬性的取值個(gè)數(shù)決定）。會(huì)有多個(gè)分支（由離散屬性的取值個(gè)數(shù)決定）。 v如果要計(jì)算如果要計(jì)算“年齡年齡”屬性的信息

39、增益，屬性的信息增益，則首先將不同的屬性值排序則首先將不同的屬性值排序20,25,28,40,46,55,56,58,60,65,70v那么可能的閾值集合為那么可能的閾值集合為20,25,28,40,46,55,56,58,60,65,70，從中一一取出，并形成分裂謂詞，例從中一一取出，并形成分裂謂詞，例如取出如取出“20”，形成謂詞，形成謂詞“20”和和“20”，用它們劃分訓(xùn)練數(shù)據(jù)集，然，用它們劃分訓(xùn)練數(shù)據(jù)集，然后計(jì)算信息增益或增益比例。后計(jì)算信息增益或增益比例。 處理有缺失值的樣本處理有缺失值的樣本 vC4.5并不會(huì)武斷地將一個(gè)有缺失值的樣本并不會(huì)武斷地將一個(gè)有缺失值的樣本拋棄拋棄,也不會(huì)

40、隨意地將它分配到某個(gè)類別中也不會(huì)隨意地將它分配到某個(gè)類別中去。去。 v“收入水平收入水平”的值，取為的值，取為“高高”的概率為的概率為3/12，取為，取為“中中”的概率為的概率為5/12，取為，取為“低低”的概率為的概率為4/12。vS1（收入水平（收入水平=“高高”）的樣本數(shù)量為：）的樣本數(shù)量為：3+2(3/12)； 3.2.4 C5.0算法算法vC5.0C5.0是經(jīng)典的決策樹模型的算法之一，可生成多分支的決是經(jīng)典的決策樹模型的算法之一，可生成多分支的決策樹，目標(biāo)變量為分類變量策樹，目標(biāo)變量為分類變量v使用使用c5.0c5.0算法算法可以可以生成決策樹（生成決策樹（decision tree

41、decision tree）或者規(guī)則）或者規(guī)則集（集（rulerule setssets）。）。C5.0C5.0模型根據(jù)能夠帶來最大信息增益模型根據(jù)能夠帶來最大信息增益（information gaininformation gain）的字段拆分樣本。）的字段拆分樣本。第一次拆分確定第一次拆分確定的樣本子集隨后再次拆分，通常是根據(jù)另一個(gè)字段進(jìn)行拆的樣本子集隨后再次拆分，通常是根據(jù)另一個(gè)字段進(jìn)行拆分，這一過程重復(fù)進(jìn)行直到樣本子集不能再被拆分為止。分，這一過程重復(fù)進(jìn)行直到樣本子集不能再被拆分為止。最后，重新檢驗(yàn)最低層次的拆分，那些對(duì)模型值沒有顯著最后，重新檢驗(yàn)最低層次的拆分，那些對(duì)模型值沒有顯著貢

42、獻(xiàn)的樣本子集被剔除或者修剪。貢獻(xiàn)的樣本子集被剔除或者修剪。 C5.0的優(yōu)點(diǎn)的優(yōu)點(diǎn)v優(yōu)點(diǎn)：優(yōu)點(diǎn)：C5.0C5.0模型在面對(duì)數(shù)據(jù)遺漏和輸入字段很多的問題時(shí)非常模型在面對(duì)數(shù)據(jù)遺漏和輸入字段很多的問題時(shí)非常穩(wěn)健。穩(wěn)健。C5.0C5.0模型通常不需要很長的訓(xùn)練次數(shù)進(jìn)行估計(jì)。模型通常不需要很長的訓(xùn)練次數(shù)進(jìn)行估計(jì)。C5.0C5.0模型比一些其他類型的模型易于理解，模型推出的模型比一些其他類型的模型易于理解，模型推出的規(guī)則有非常直觀的解釋。規(guī)則有非常直觀的解釋。C5.0C5.0也提供強(qiáng)大的增強(qiáng)技術(shù)以提高分類的精度。也提供強(qiáng)大的增強(qiáng)技術(shù)以提高分類的精度。vC5.0C5.0算法選擇分支變量的依據(jù)算法選擇分支變量的

43、依據(jù)以信息熵的下降速度作為確定最佳分支變量和分割閥值以信息熵的下降速度作為確定最佳分支變量和分割閥值的依據(jù)。信息熵的下降意味著信息的不確定性下降的依據(jù)。信息熵的下降意味著信息的不確定性下降舉例：在舉例：在Clementine中應(yīng)用中應(yīng)用C5.0v這里，以學(xué)生參加某次社會(huì)公益活動(dòng)的數(shù)據(jù)（文這里，以學(xué)生參加某次社會(huì)公益活動(dòng)的數(shù)據(jù)（文件名為件名為Students.xls）為例，講解）為例，講解C5.0算法的具算法的具體實(shí)現(xiàn)操作。體實(shí)現(xiàn)操作。v分析目標(biāo)是，研究哪些因素將顯著影響到學(xué)生參分析目標(biāo)是，研究哪些因素將顯著影響到學(xué)生參與社會(huì)公益活動(dòng)。與社會(huì)公益活動(dòng)。 其中，是否參加為輸出變量，除編號(hào)以外的其中

44、，是否參加為輸出變量，除編號(hào)以外的變量均為輸入變量。變量均為輸入變量。數(shù)據(jù)流如下：數(shù)據(jù)流如下：一、建立模型 第一步建立數(shù)據(jù)源，第二步選擇第一步建立數(shù)據(jù)源，第二步選擇Modeling卡中的卡中的C5.0節(jié)點(diǎn)節(jié)點(diǎn)并將其連接到恰當(dāng)位置，鼠標(biāo)右擊該節(jié)點(diǎn)，彈出下面窗口。并將其連接到恰當(dāng)位置，鼠標(biāo)右擊該節(jié)點(diǎn)，彈出下面窗口。模型名稱（模型名稱（Model nameModel name）輸出類型（輸出類型（Output typeOutput type）：此處）：此處指定希望最終生成的模型是決策樹指定希望最終生成的模型是決策樹還是規(guī)則集。還是規(guī)則集。群體字符（群體字符（Group symbolicsGroup

45、symbolics）。）。如果選擇該選項(xiàng)，如果選擇該選項(xiàng)，C5.0C5.0會(huì)嘗試將所會(huì)嘗試將所有與輸出字段格式相似的字符值合有與輸出字段格式相似的字符值合并。如果沒有選擇該選項(xiàng)，并。如果沒有選擇該選項(xiàng)，C5.0C5.0會(huì)會(huì)為用于拆分母節(jié)點(diǎn)的字符字段的每為用于拆分母節(jié)點(diǎn)的字符字段的每個(gè)值創(chuàng)建一個(gè)子節(jié)點(diǎn)。個(gè)值創(chuàng)建一個(gè)子節(jié)點(diǎn)。使用自舉法（使用自舉法（Use boostingUse boosting）：）：提高其精確率。這種方法按序列建提高其精確率。這種方法按序列建立多重模型。第一個(gè)模型以通常的立多重模型。第一個(gè)模型以通常的方式建立。隨后，建立第二個(gè)模型，方式建立。隨后，建立第二個(gè)模型，聚焦于被第一個(gè)

46、模型錯(cuò)誤分類的記聚焦于被第一個(gè)模型錯(cuò)誤分類的記錄。以此類推，最后應(yīng)用整個(gè)模型錄。以此類推，最后應(yīng)用整個(gè)模型集對(duì)樣本進(jìn)行分類，使用加權(quán)投票集對(duì)樣本進(jìn)行分類，使用加權(quán)投票過程把分散的預(yù)測合并成綜合預(yù)測。過程把分散的預(yù)測合并成綜合預(yù)測。The Number of trialsThe Number of trials選項(xiàng)允許控選項(xiàng)允許控制用于助推的模型數(shù)量。制用于助推的模型數(shù)量。v交叉驗(yàn)證（交叉驗(yàn)證（Crossvalidate）：如果選擇了該）：如果選擇了該選項(xiàng)，選項(xiàng)，C5.0將使用一組基于將使用一組基于訓(xùn)練數(shù)據(jù)子集建立的模型，訓(xùn)練數(shù)據(jù)子集建立的模型，來估計(jì)基于全部數(shù)據(jù)建立的來估計(jì)基于全部數(shù)據(jù)建立的模

47、型的精確度。如果數(shù)據(jù)集模型的精確度。如果數(shù)據(jù)集過小，不能拆分成傳統(tǒng)意義過小，不能拆分成傳統(tǒng)意義上的訓(xùn)練集和測試集，這將上的訓(xùn)練集和測試集，這將非常有用?；蛴糜诮徊骝?yàn)證非常有用?；蛴糜诮徊骝?yàn)證的模型數(shù)目。的模型數(shù)目。v模式（模式（Mode）：對(duì)于簡單的）：對(duì)于簡單的訓(xùn)練，絕大多數(shù)訓(xùn)練，絕大多數(shù)C5.0參數(shù)是參數(shù)是自動(dòng)設(shè)置。高級(jí)訓(xùn)練模式選自動(dòng)設(shè)置。高級(jí)訓(xùn)練模式選項(xiàng)允許對(duì)訓(xùn)練參數(shù)更多的直項(xiàng)允許對(duì)訓(xùn)練參數(shù)更多的直接控制。接控制。v簡單模式選項(xiàng)（簡單模式選項(xiàng)（simplesimple）v偏好（偏好（FavorFavor）：）：在在accuracyaccuracy下，下，C5.0C5.0會(huì)生會(huì)生成盡可能精

48、確的決策樹。成盡可能精確的決策樹。在某些情況下，這會(huì)導(dǎo)致在某些情況下，這會(huì)導(dǎo)致過度擬和。選擇過度擬和。選擇GeneralityGenerality（一般化）項(xiàng)（一般化）項(xiàng)以使用不易受該問題影響以使用不易受該問題影響的算法設(shè)置。的算法設(shè)置。v期望噪聲百分?jǐn)?shù)期望噪聲百分?jǐn)?shù)（Expected noise Expected noise （% %）：）：指定訓(xùn)練集中的噪聲或錯(cuò)指定訓(xùn)練集中的噪聲或錯(cuò)誤數(shù)據(jù)期望比率。誤數(shù)據(jù)期望比率。v高級(jí)模式選項(xiàng)高級(jí)模式選項(xiàng)v修剪純度（修剪純度（pruning severity）：決定生）：決定生成決策樹或規(guī)則集被修剪的程度。提高成決策樹或規(guī)則集被修剪的程度。提高純度值將獲

49、得更小，更簡潔的決策樹。純度值將獲得更小，更簡潔的決策樹。降低純度值將獲得更加精確的決策樹。降低純度值將獲得更加精確的決策樹。v子分支最少記錄數(shù)（子分支最少記錄數(shù)（Minimum records per child branch）：子群大小可以用于）：子群大小可以用于限制決策樹任一分支的拆分?jǐn)?shù)。只有當(dāng)限制決策樹任一分支的拆分?jǐn)?shù)。只有當(dāng)兩個(gè)或以上的后序子分支包括來自訓(xùn)練兩個(gè)或以上的后序子分支包括來自訓(xùn)練集的記錄不少于最小記錄數(shù)，決策樹才集的記錄不少于最小記錄數(shù)，決策樹才會(huì)繼續(xù)拆分。默認(rèn)值為會(huì)繼續(xù)拆分。默認(rèn)值為2，提高該值將有，提高該值將有助于避免噪聲數(shù)據(jù)的過度訓(xùn)練。助于避免噪聲數(shù)據(jù)的過度訓(xùn)練。v

50、全局修剪（全局修剪（Use global pruning）：）： 第一階段：局部修建第一階段：局部修建 第二階段：全局修剪第二階段：全局修剪v排除屬性（排除屬性（Winnow attributes）：如果）：如果選擇了該選項(xiàng)，選擇了該選項(xiàng)，C5.0會(huì)在建立模型前檢會(huì)在建立模型前檢驗(yàn)預(yù)測字段的有用性。被發(fā)現(xiàn)與分析無驗(yàn)預(yù)測字段的有用性。被發(fā)現(xiàn)與分析無關(guān)的預(yù)測字段將不參與建模過程。這一關(guān)的預(yù)測字段將不參與建模過程。這一選項(xiàng)對(duì)有許多預(yù)測字段元的模型非常有選項(xiàng)對(duì)有許多預(yù)測字段元的模型非常有用，并且有助于避免過度擬和。用，并且有助于避免過度擬和。 圖圖1 指定錯(cuò)誤歸類損失指定錯(cuò)誤歸類損失錯(cuò)誤歸類損失允許指

51、定不同類錯(cuò)誤歸類損失允許指定不同類型預(yù)測錯(cuò)誤之間的相對(duì)重要性。型預(yù)測錯(cuò)誤之間的相對(duì)重要性。錯(cuò)誤歸類損失矩陣顯示預(yù)測類錯(cuò)誤歸類損失矩陣顯示預(yù)測類和實(shí)際類每一可能組合的損失。和實(shí)際類每一可能組合的損失。所有的錯(cuò)誤歸類損失都預(yù)設(shè)設(shè)所有的錯(cuò)誤歸類損失都預(yù)設(shè)設(shè)置為置為1.01.0。要輸入自定義損失值，。要輸入自定義損失值，選擇選擇Use misclassification Use misclassification costscosts，然后把自定義值輸入到，然后把自定義值輸入到損失矩陣中。損失矩陣中。具體設(shè)置具體設(shè)置執(zhí)行結(jié)果執(zhí)行結(jié)果二、預(yù)測結(jié)果二、預(yù)測結(jié)果 為觀測為觀測C5.0對(duì)每個(gè)樣本的預(yù)測結(jié)果，可

52、在流管理器的對(duì)每個(gè)樣本的預(yù)測結(jié)果，可在流管理器的Models卡中，鼠標(biāo)右擊卡中，鼠標(biāo)右擊C5.0模型結(jié)果，選擇彈出菜單中的模型結(jié)果，選擇彈出菜單中的Add To Stream，并將模型結(jié)果連接到數(shù)據(jù)流中，然后連接，并將模型結(jié)果連接到數(shù)據(jù)流中，然后連接Table節(jié)點(diǎn)查看預(yù)測結(jié)果，如下圖所示：節(jié)點(diǎn)查看預(yù)測結(jié)果，如下圖所示：三、三、C5.0模型評(píng)價(jià)模型評(píng)價(jià)CARTv分類回歸樹CART(Classification and Regression Trees)1984 vL.Breiman，J.Friedman，R.Olshen和C.Stone/br

53、eiman//jhf//olshen/v目標(biāo)變量是類別的 - 分類樹v目標(biāo)變量是連續(xù)的 - 回歸樹CARTv二元?jiǎng)澐侄鏄洳灰桩a(chǎn)生數(shù)據(jù)碎片，精確度往往也會(huì)高于多叉樹，所以在CART算法中，采用了二元?jiǎng)澐講不純性度量分類目標(biāo)：Gini指標(biāo)、Towing、order Towing連續(xù)目標(biāo)：最小平方殘差、最小絕對(duì)殘差v剪枝：用獨(dú)立的驗(yàn)證數(shù)據(jù)集對(duì)訓(xùn)練集生長的樹進(jìn)行剪枝三個(gè)步驟三個(gè)步驟v生成最大樹生成最大樹生成一棵充分生長的最大樹生成一棵充分生長的最大樹v樹的修剪樹的修剪根據(jù)修剪算法對(duì)最大樹進(jìn)行修

54、剪，生成由許多子根據(jù)修剪算法對(duì)最大樹進(jìn)行修剪，生成由許多子樹組成的子樹序列樹組成的子樹序列v子樹評(píng)估子樹評(píng)估從子樹序列中選擇一棵最優(yōu)的子樹作為最后的結(jié)從子樹序列中選擇一棵最優(yōu)的子樹作為最后的結(jié)果。果。 v分類與回歸樹 (Classification And RegressionTrees,CART) 是一種產(chǎn)生二叉決策樹的技術(shù). v分類樹與回歸樹下面有兩個(gè)重要的思想: 第一個(gè):遞歸地劃分自變量空間的想法; 第二個(gè):用驗(yàn)證數(shù)據(jù)進(jìn)行剪枝的想法.v遞歸劃分 用Y表示因變量(分類變量); 用X1,X2,XP表示自變量. 通過遞歸的方式把關(guān)于X的P維空間劃分為 不重疊的矩形.v劃分步驟: 首先: 一個(gè)自

55、變量被選擇,例如Xi和Xi的一個(gè)值Si,若選擇Si把P維空間分為兩部分:一部分包含的點(diǎn)都滿足XiSi.v其次: 再把上步中得到的兩部分中的一個(gè)部分,通過選擇一個(gè)變量和該變量的劃分值以相似的方式再劃分.v重復(fù)上述步驟,直至把整個(gè)X空間劃分成的每個(gè)小矩形都盡可能的是同構(gòu)的.v 例示遞歸劃分的過程v 例1（Johnson和Wichern） v 乘式割草機(jī)制造商意欲發(fā)現(xiàn)一個(gè)把城市中的家庭分成那些愿意購買乘式割草機(jī)和不愿意購買的兩類的方法。在這個(gè)城市的家庭中隨機(jī)抽取12個(gè)擁有者和12個(gè)非擁有者的家庭作為樣本。這些數(shù)據(jù)如表1所示。這里的自變量是收入（X1）和草地面積（X2）。類別變量Y有兩個(gè)類別：擁有者和

56、非擁有者。表1vCART如何選擇劃分點(diǎn)? 對(duì)于一個(gè)變量劃分點(diǎn)是一對(duì)連續(xù)變量值的中點(diǎn). 例如: X1可能劃分點(diǎn)是38.1,45.3,50.1,109.5; X2可能劃分點(diǎn)是14.4,15.4,16.223. 這些劃分點(diǎn)按照能減少雜質(zhì)的多少來分級(jí). 雜質(zhì)度量方法:Gini指標(biāo). 矩形A的Gini不純度可定義為: 其中K=1,2,C,來表示類, Pk是觀測點(diǎn)中屬于類K的比例. 雜度雜度 v在ID3算法中，用“熵”來度量數(shù)據(jù)集隨機(jī)性的程度。v在CART中我們把這種隨機(jī)性的程度稱為“雜度雜度”（impurity，也稱為“不純度”），并且用“吉尼”(gini)指標(biāo)來衡量它。 吉尼指標(biāo) v設(shè)t是決策樹上的某

57、個(gè)節(jié)點(diǎn)，該節(jié)點(diǎn)的數(shù)據(jù)集為S，由s個(gè)樣本組成，其類標(biāo)號(hào)屬性具有m個(gè)不同的取值，即定義了m個(gè)不同的類Ci（i=1,2,m）。設(shè)屬于類Ci的樣本的個(gè)數(shù)為si。那么這個(gè)節(jié)點(diǎn)的吉尼指標(biāo)這樣來計(jì)算：雜度削減雜度削減 v由于CART算法生成的是一棵二叉樹，所以對(duì)于節(jié)點(diǎn)t來說，分裂后將產(chǎn)生兩個(gè)子節(jié)點(diǎn)tL和tR，設(shè)這兩個(gè)子節(jié)點(diǎn)的雜度分別為gini(tL)和gini(tR)，那么，在此次分裂過程中的雜度削雜度削減減為： 計(jì)算雜度削減停止準(zhǔn)則停止準(zhǔn)則 v以下任何一個(gè)規(guī)則被滿足，節(jié)點(diǎn)將不再分裂以下任何一個(gè)規(guī)則被滿足，節(jié)點(diǎn)將不再分裂這個(gè)節(jié)點(diǎn)是這個(gè)節(jié)點(diǎn)是“純純”的，即這個(gè)節(jié)點(diǎn)的所有樣本都屬于同的，即這個(gè)節(jié)點(diǎn)的所有樣本都屬

58、于同一類別；一類別；對(duì)于每一個(gè)屬性（不包括類標(biāo)號(hào)屬性），節(jié)點(diǎn)中的所有對(duì)于每一個(gè)屬性（不包括類標(biāo)號(hào)屬性），節(jié)點(diǎn)中的所有樣本都有相同的值；樣本都有相同的值；當(dāng)前節(jié)點(diǎn)所在的深度已經(jīng)達(dá)到當(dāng)前節(jié)點(diǎn)所在的深度已經(jīng)達(dá)到“最大樹深度最大樹深度”（如果定（如果定義有）；義有）；這個(gè)節(jié)點(diǎn)的樣本數(shù)量小于這個(gè)節(jié)點(diǎn)的樣本數(shù)量小于“父分支中的最小記錄數(shù)父分支中的最小記錄數(shù)” （如果定義有）；（如果定義有）；這個(gè)節(jié)點(diǎn)分裂后產(chǎn)生的子節(jié)點(diǎn)中包含的樣本數(shù)量小于預(yù)這個(gè)節(jié)點(diǎn)分裂后產(chǎn)生的子節(jié)點(diǎn)中包含的樣本數(shù)量小于預(yù)定義的定義的“子分支中的最小記錄數(shù)子分支中的最小記錄數(shù)”（如果定義有）；（如果定義有）；分裂產(chǎn)生的雜度削減小于預(yù)定義的分裂

59、產(chǎn)生的雜度削減小于預(yù)定義的“最小雜度削減最小雜度削減”（如果定義有）（如果定義有） 選擇草地面積變量X2=19做第一次分割,由(X1,X2)組成的空間被分成X219的兩個(gè)矩形.選擇收入變量X1=84.75我們能看到遞歸劃分是如何精煉候選矩形,使之變得更純的算法過程.最后階段的遞歸分析如圖5所示這個(gè)方法被稱為分類樹的原因是每次劃分都可以描述為把一個(gè)節(jié)點(diǎn)分成兩個(gè)后續(xù)節(jié)點(diǎn).第一次分裂表示為樹的根節(jié)點(diǎn)的分支,如圖6樹的前三次劃分如圖7整個(gè)樹如下圖8二用驗(yàn)證數(shù)據(jù)進(jìn)行剪枝vCART過程中第二個(gè)關(guān)鍵的思想是用獨(dú)立的驗(yàn)證數(shù)據(jù)集對(duì)根據(jù)訓(xùn)練集生成的樹進(jìn)行剪枝.vCART剪枝目的:生成一個(gè)具有最小錯(cuò)誤的樹.v為什么要剪枝呢? 因?yàn)? 1 在樹生成過程中可能存在不能提高 分類純度的劃分節(jié)點(diǎn). 2 存在過擬合訓(xùn)練數(shù)據(jù). 樹的修剪 v葉子節(jié)點(diǎn)過多，則樹的復(fù)雜度高。葉子節(jié)點(diǎn)過多，則樹的復(fù)雜度高。v葉子節(jié)點(diǎn)過少，則誤分類損失葉子節(jié)點(diǎn)過少，則誤分類損失大。v代價(jià)復(fù)雜度代價(jià)復(fù)雜度 CART算法仍然使用后剪枝。在樹的生成過程中，多展算法仍然使用后剪枝。在樹的生成過程中，多展開一層就會(huì)有多一些的信息被發(fā)現(xiàn)，開一層就會(huì)有多一些的信息被發(fā)現(xiàn)，CART算法運(yùn)