第4章 1_分類與決策樹

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

2、值，或者預(yù)測顧客在計算機設(shè)備上的花費比如預(yù)測空缺值，或者預(yù)測顧客在計算機設(shè)備上的花費 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)估計的屬性值是離散值時，這就是當(dāng)估計的屬性值是離散值時，這就是分類分類； 當(dāng)估計的屬性值是連續(xù)值時，這就是當(dāng)估計的屬性值是連續(xù)值時，這就是預(yù)測預(yù)測。 分類和預(yù)測分類和預(yù)測-示例示例 v分類分類 銀行貸款員需要分析數(shù)據(jù)，來弄清哪些貸款申請銀行貸款員需要分析數(shù)據(jù)，來弄清哪些貸款申請 者是安全的，哪些是

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

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

5、知的對象進行分類第二步，使用模型，對將來的或未知的對象進行分類 首先評估模型的預(yù)測準(zhǔn)確率首先評估模型的預(yù)測準(zhǔn)確率 v對每個測試樣本，將已知的類標(biāo)號和該樣本的學(xué)習(xí)模型類預(yù)測比對每個測試樣本，將已知的類標(biāo)號和該樣本的學(xué)習(xí)模型類預(yù)測比 較較 v模型在給定測試集上的準(zhǔn)確率是正確被模型分類的測試樣本的百模型在給定測試集上的準(zhǔn)確率是正確被模型分類的測試樣本的百 分比分比 v測試集要獨立于訓(xùn)練樣本集，否則會出現(xiàn)測試集要獨立于訓(xùn)練樣本集，否則會出現(xiàn)“過分?jǐn)M合過分?jǐn)M合”的情況的情況 第一步建立模型 訓(xùn)練數(shù) 據(jù)集 NAME RANKYEARS TENURED MikeAssistant Prof3no MaryA

6、ssistant Prof7yes Bill Professor2yes JimAssociate Prof7yes DaveAssistant Prof6no AnneAssociate Prof3no 分類算法 IF rank = professor OR years 6 THEN tenured = yes 分類規(guī)則 第二步用模型進行分類 分類規(guī)則 測試集 NAMERANKYEARS TENURED TomAssistant Prof2no Merlisa Associate Prof7no George Professor5yes Joseph Assistant Prof7yes 未

7、知數(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í)（用于分類） 模型的學(xué)習(xí)在被告知每個訓(xùn)練樣本屬于哪個類的模型的學(xué)習(xí)在被告知每個訓(xùn)練樣本屬于哪個類的 “指導(dǎo)指導(dǎo)”下進行下進行 新數(shù)據(jù)使用訓(xùn)練數(shù)據(jù)集中得到的規(guī)則進行分類新數(shù)據(jù)使用訓(xùn)練數(shù)據(jù)集中得到的規(guī)則進行分類 v無監(jiān)督學(xué)習(xí)（用于聚類）無監(jiān)督學(xué)習(xí)（用于聚類） 每個訓(xùn)練樣本的類編號是未知的，要學(xué)習(xí)的類集每個訓(xùn)練樣本的類編號是未知的，要學(xué)習(xí)的類集 合或數(shù)量也可能是事先未知的合或數(shù)量也可能是事先未知的 通過一系列的度量、觀察來建立數(shù)據(jù)中的類編號通過一系列的度量

8、、觀察來建立數(shù)據(jù)中的類編號 或進行聚類或進行聚類 數(shù)據(jù)預(yù)測的兩步過程數(shù)據(jù)預(yù)測的兩步過程 v數(shù)據(jù)預(yù)測也是一個兩步的過程，類似于前面描述的數(shù)據(jù)分類數(shù)據(jù)預(yù)測也是一個兩步的過程，類似于前面描述的數(shù)據(jù)分類 對于預(yù)測，沒有對于預(yù)測，沒有“類標(biāo)號屬性類標(biāo)號屬性” 要預(yù)測的屬性是連續(xù)值，而不是離散值，該屬性可簡稱要預(yù)測的屬性是連續(xù)值，而不是離散值，該屬性可簡稱 “預(yù)測屬性預(yù)測屬性” vE.g. 銀行貸款員需要預(yù)測貸給某個顧客多少錢是安全銀行貸款員需要預(yù)測貸給某個顧客多少錢是安全 的的 v預(yù)測器可以看作一個映射或函數(shù)預(yù)測器可以看作一個映射或函數(shù)y=f(X) 其中其中X是輸入；是輸入；y是輸出，是一個連續(xù)或有序的

9、值是輸出，是一個連續(xù)或有序的值 與分類類似，準(zhǔn)確率的預(yù)測，也要使用單獨的測試集與分類類似，準(zhǔn)確率的預(yù)測，也要使用單獨的測試集 3.1 決策樹概述決策樹概述 v決策樹決策樹(Decision Tree) 一種描述概念空間的有效的歸納推理辦法。一種描述概念空間的有效的歸納推理辦法。 基于決策樹的學(xué)習(xí)方法可以進行不相關(guān)的基于決策樹的學(xué)習(xí)方法可以進行不相關(guān)的 多概念學(xué)習(xí)，具有簡單快捷的優(yōu)勢，已經(jīng)多概念學(xué)習(xí)，具有簡單快捷的優(yōu)勢，已經(jīng) 在各個領(lǐng)域取得廣泛應(yīng)用。在各個領(lǐng)域取得廣泛應(yīng)用。 v決策樹是一種樹型結(jié)構(gòu)，其中每個內(nèi)部結(jié)決策樹是一種樹型結(jié)構(gòu)，其中每個內(nèi)部結(jié) 點表示在一個屬性上的測試，每個分支代點表示在一

10、個屬性上的測試，每個分支代 表一個測試輸出，每個葉結(jié)點代表一種類表一個測試輸出，每個葉結(jié)點代表一種類 別。別。 v決策樹學(xué)習(xí)是以實例為基礎(chǔ)的歸納學(xué)習(xí)。決策樹學(xué)習(xí)是以實例為基礎(chǔ)的歸納學(xué)習(xí)。 v從一類無序、無規(guī)則的事物（概念）中推理出決策樹表示的分類規(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í) 單個概念。單個概念。 1979年年, J.R. Quinlan 給出給出ID3算法，并在算法，并在1983年和年和1986

11、年對年對 ID3 進行了總結(jié)和簡化，使其成為決策樹學(xué)習(xí)算法的典型。進行了總結(jié)和簡化，使其成為決策樹學(xué)習(xí)算法的典型。 Schlimmer 和和Fisher 于于1986年對年對ID3進行改造，在每個可能的進行改造，在每個可能的 決策樹節(jié)點創(chuàng)建緩沖區(qū)，使決策樹可以遞增式生成，得到?jīng)Q策樹節(jié)點創(chuàng)建緩沖區(qū)，使決策樹可以遞增式生成，得到ID4算算 法。法。 1988年，年，Utgoff 在在ID4基礎(chǔ)上提出了基礎(chǔ)上提出了ID5學(xué)習(xí)算法，進一步提高學(xué)習(xí)算法，進一步提高 了效率。了效率。 1993年，年，Quinlan 進一步發(fā)展了進一步發(fā)展了ID3算法，改進成算法，改進成C4.5算法。算法。 另一類決策樹算

12、法為另一類決策樹算法為CART，與，與C4.5不同的是，不同的是，CART的決策樹的決策樹 由二元邏輯問題生成，每個樹節(jié)點只有兩個分枝，分別包括學(xué)習(xí)由二元邏輯問題生成，每個樹節(jié)點只有兩個分枝，分別包括學(xué)習(xí) 實例的正例與反例。實例的正例與反例。 v其基本思想是以信息熵為度量構(gòu)造一棵熵值下降最快的樹，到葉子其基本思想是以信息熵為度量構(gòu)造一棵熵值下降最快的樹，到葉子 節(jié)點處的熵值為零，此時每個葉節(jié)點中的實例都屬于同一類。節(jié)點處的熵值為零，此時每個葉節(jié)點中的實例都屬于同一類。 v決策樹學(xué)習(xí)采用的是自頂向下的遞歸方法。決策樹學(xué)習(xí)采用的是自頂向下的遞歸方法。 v決策樹的每一層節(jié)點依照某一屬性值向下分為子節(jié)

13、點，待決策樹的每一層節(jié)點依照某一屬性值向下分為子節(jié)點，待 分類的實例在每一節(jié)點處與該節(jié)點相關(guān)的屬性值進行比較，分類的實例在每一節(jié)點處與該節(jié)點相關(guān)的屬性值進行比較， 根據(jù)不同的比較結(jié)果向相應(yīng)的子節(jié)點擴展，這一過程在到根據(jù)不同的比較結(jié)果向相應(yīng)的子節(jié)點擴展，這一過程在到 達決策樹的葉節(jié)點時結(jié)束，此時得到結(jié)論。達決策樹的葉節(jié)點時結(jié)束，此時得到結(jié)論。 v從根節(jié)點到葉節(jié)點的每一條路經(jīng)都對應(yīng)著一條合理的規(guī)則，從根節(jié)點到葉節(jié)點的每一條路經(jīng)都對應(yīng)著一條合理的規(guī)則， 規(guī)則間各個部分（各個層的條件）的關(guān)系是合取關(guān)系。整規(guī)則間各個部分（各個層的條件）的關(guān)系是合取關(guān)系。整 個決策樹就對應(yīng)著一組析取的規(guī)則。個決策樹就對應(yīng)

14、著一組析取的規(guī)則。 v決策樹學(xué)習(xí)算法的最大優(yōu)點是，它可以自學(xué)習(xí)。在學(xué)習(xí)的決策樹學(xué)習(xí)算法的最大優(yōu)點是，它可以自學(xué)習(xí)。在學(xué)習(xí)的 過程中，不需要使用者了解過多背景知識，只需要對訓(xùn)練過程中，不需要使用者了解過多背景知識，只需要對訓(xùn)練 例子進行較好的標(biāo)注，就能夠進行學(xué)習(xí)。如果在應(yīng)用中發(fā)例子進行較好的標(biāo)注，就能夠進行學(xué)習(xí)。如果在應(yīng)用中發(fā) 現(xiàn)不符合規(guī)則的實例，程序會詢問用戶該實例的正確分類，現(xiàn)不符合規(guī)則的實例，程序會詢問用戶該實例的正確分類， 從而生成新的分枝和葉子，并添加到樹中。從而生成新的分枝和葉子，并添加到樹中。 v樹是由節(jié)點和分枝組成的層樹是由節(jié)點和分枝組成的層 次數(shù)據(jù)結(jié)構(gòu)。節(jié)點用于存貯次數(shù)據(jù)結(jié)構(gòu)。

15、節(jié)點用于存貯 信息或知識，分枝用于連接信息或知識，分枝用于連接 各個節(jié)點。樹是圖的一個特各個節(jié)點。樹是圖的一個特 例，圖是更一般的數(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)，從上端的根節(jié) 點開始，各種分類原則被引點開始，各種分類原則被引 用進來，并依這些分類原則用進來，并依這些分類原則 將根節(jié)點的數(shù)據(jù)集劃分為子將根節(jié)點的數(shù)據(jù)集劃分為子 集，這一劃分過程直到某種集，這一劃分過程直到某種 約束條件滿足而結(jié)束。約束條件滿足而結(jié)束。 根結(jié)點根結(jié)點 個子大個子大 可能是松鼠可能是松鼠可能是老

16、鼠可能是老鼠 可能是大象可能是大象 在水里在水里 會吱吱叫會吱吱叫 鼻子長鼻子長 脖子長脖子長 個子小個子小 不會吱吱叫不會吱吱叫 鼻子短鼻子短 脖子短脖子短 可能是長頸鹿可能是長頸鹿 在陸地上在陸地上 可能是犀?？赡苁窍？赡苁呛玉R可能是河馬 v可以看到，一個決策樹的內(nèi)部結(jié)點包含學(xué)習(xí)的實例，每層分枝可以看到，一個決策樹的內(nèi)部結(jié)點包含學(xué)習(xí)的實例，每層分枝 代表了實例的一個屬性的可能取值，葉節(jié)點是最終劃分成的類。代表了實例的一個屬性的可能取值，葉節(jié)點是最終劃分成的類。 如果判定是二元的，那么構(gòu)造的將是一棵二叉樹，在樹中每回如果判定是二元的，那么構(gòu)造的將是一棵二叉樹，在樹中每回 答一個問題就降到樹

17、的下一層，這類樹一般稱為答一個問題就降到樹的下一層，這類樹一般稱為CART （Classification And Regression Tree）。）。 v判定結(jié)構(gòu)可以機械的轉(zhuǎn)變成產(chǎn)生式規(guī)則?？梢酝ㄟ^對結(jié)構(gòu)進行判定結(jié)構(gòu)可以機械的轉(zhuǎn)變成產(chǎn)生式規(guī)則?？梢酝ㄟ^對結(jié)構(gòu)進行 廣度優(yōu)先搜索，并在每個節(jié)點生成廣度優(yōu)先搜索，并在每個節(jié)點生成“IFTHEN”規(guī)則來實現(xiàn)。規(guī)則來實現(xiàn)。 如圖如圖6-13的決策樹可以轉(zhuǎn)換成下規(guī)則：的決策樹可以轉(zhuǎn)換成下規(guī)則： IF “個子大個子大” THEN IF “脖子短脖子短” THEN IF “鼻子長鼻子長” THEN 可能是大象可能是大象 形式化表示成形式化表示成 可能是大象

18、鼻子長脖子短個子大 根結(jié)點根結(jié)點 個 子個 子 大大 可 能 是 松可 能 是 松 鼠鼠 可 能 是 老可 能 是 老 鼠鼠 可 能 是 大可 能 是 大 象象 在 水在 水 里里 會 吱 吱會 吱 吱 叫叫 鼻 子鼻 子 長長 脖 子脖 子 長長 個子小個子小 不會吱吱不會吱吱 叫叫 鼻子鼻子 短短 脖子脖子 短短 可能是長頸可能是長頸 鹿鹿 在 陸 地在 陸 地 上上 可 能 是 犀可 能 是 犀 牛牛 可 能 是 河可 能 是 河 馬馬 v構(gòu)造一棵決策樹要解決四個問題：構(gòu)造一棵決策樹要解決四個問題： 收集待分類的數(shù)據(jù)，這些數(shù)據(jù)的所有屬性應(yīng)該是完全標(biāo)注的。收集待分類的數(shù)據(jù)，這些數(shù)據(jù)的所有屬

19、性應(yīng)該是完全標(biāo)注的。 設(shè)計分類原則，即數(shù)據(jù)的哪些屬性可以被用來分類，以及如何將該屬性量設(shè)計分類原則，即數(shù)據(jù)的哪些屬性可以被用來分類，以及如何將該屬性量 化?；?分類原則的選擇，即在眾多分類準(zhǔn)則中，每一步選擇哪一準(zhǔn)則使最終的樹分類原則的選擇，即在眾多分類準(zhǔn)則中，每一步選擇哪一準(zhǔn)則使最終的樹 更令人滿意。更令人滿意。 設(shè)計分類停止條件，實際應(yīng)用中數(shù)據(jù)的屬性很多，真正有分類意義的屬性設(shè)計分類停止條件，實際應(yīng)用中數(shù)據(jù)的屬性很多，真正有分類意義的屬性 往往是有限幾個，因此在必要的時候應(yīng)該停止數(shù)據(jù)集分裂：往往是有限幾個，因此在必要的時候應(yīng)該停止數(shù)據(jù)集分裂： v該節(jié)點包含的數(shù)據(jù)太少不足以分裂，該節(jié)點包含的

20、數(shù)據(jù)太少不足以分裂， v繼續(xù)分裂數(shù)據(jù)集對樹生成的目標(biāo)繼續(xù)分裂數(shù)據(jù)集對樹生成的目標(biāo)(例如例如ID3中的熵下降準(zhǔn)則中的熵下降準(zhǔn)則)沒有貢獻，沒有貢獻， v樹的深度過大不宜再分。樹的深度過大不宜再分。 v通用的決策樹分裂目標(biāo)是整棵樹的熵總量最小，每一步分裂時，選擇使熵減小通用的決策樹分裂目標(biāo)是整棵樹的熵總量最小，每一步分裂時，選擇使熵減小 最大的準(zhǔn)則，這種方案使最具有分類潛力的準(zhǔn)則最先被提取出來最大的準(zhǔn)則，這種方案使最具有分類潛力的準(zhǔn)則最先被提取出來 預(yù)測變量 目標(biāo)變量 記錄 樣本 類標(biāo)號屬性 類別集合：類別集合：Class=“優(yōu)優(yōu)”，“良良”，“差差” 決策樹的基本原理 根節(jié)點根節(jié)點 葉子節(jié)點葉子

21、節(jié)點 分裂屬性分裂屬性 分裂謂詞分裂謂詞 每一個葉子節(jié)點都被確定一個類標(biāo)號每一個葉子節(jié)點都被確定一個類標(biāo)號 v每一個節(jié)點都代表了一個數(shù)據(jù)集。每一個節(jié)點都代表了一個數(shù)據(jù)集。 根節(jié)點根節(jié)點1代表了初始數(shù)據(jù)集代表了初始數(shù)據(jù)集D 其它節(jié)點都是數(shù)據(jù)集其它節(jié)點都是數(shù)據(jù)集D的子集。的子集。 v例如，節(jié)點例如，節(jié)點2代表數(shù)據(jù)集代表數(shù)據(jù)集D中年齡小于中年齡小于40歲的那部分樣本組成歲的那部分樣本組成 的數(shù)據(jù)集。的數(shù)據(jù)集。 v子節(jié)點是父節(jié)點的子集。子節(jié)點是父節(jié)點的子集。 vIf (年齡年齡40) and (職業(yè)職業(yè)=“學(xué)生學(xué)生” or職業(yè)職業(yè)=“教師教師”) Then 信用等級信用等級 =“優(yōu)優(yōu)” vIf (年齡

22、年齡40) and (職業(yè)職業(yè)!=“學(xué)生學(xué)生”and職業(yè)職業(yè)!=“教師教師”) Then 信用等信用等 級級=“良良” vIf (年齡年齡40) and (月薪月薪3000) Then 信用等級信用等級=“優(yōu)優(yōu)” v決策樹是指具有下列三個性質(zhì)的樹：決策樹是指具有下列三個性質(zhì)的樹： 每個非葉子節(jié)點都被標(biāo)記一個分裂屬性每個非葉子節(jié)點都被標(biāo)記一個分裂屬性Ai； 每個分支都被標(biāo)記一個分裂謂詞，這個分裂謂每個分支都被標(biāo)記一個分裂謂詞，這個分裂謂 詞是分裂父節(jié)點的具體依據(jù)；詞是分裂父節(jié)點的具體依據(jù)； 每個葉子節(jié)點都被標(biāo)記一個類標(biāo)號每個葉子節(jié)點都被標(biāo)記一個類標(biāo)號CjC。 v任何一個決策樹算法，其核心步驟都是

23、為任何一個決策樹算法，其核心步驟都是為 每一次分裂確定一個每一次分裂確定一個分裂屬性分裂屬性，即究竟按，即究竟按 照哪一個屬性來把當(dāng)前數(shù)據(jù)集劃分為若干照哪一個屬性來把當(dāng)前數(shù)據(jù)集劃分為若干 個子集，從而形成若干個個子集，從而形成若干個“樹枝樹枝”。 v熵，是數(shù)據(jù)集中的不確定性、突發(fā)性或隨機性的熵，是數(shù)據(jù)集中的不確定性、突發(fā)性或隨機性的 程度的度量。程度的度量。 v當(dāng)一個數(shù)據(jù)集中的記錄全部都屬于同一類的時候，當(dāng)一個數(shù)據(jù)集中的記錄全部都屬于同一類的時候， 則沒有不確定性，這種情況下的熵就為則沒有不確定性，這種情況下的熵就為0。 v決策樹分裂的基本原則是，數(shù)據(jù)集被分裂為若干決策樹分裂的基本原則是，數(shù)據(jù)

24、集被分裂為若干 個子集后，要使每個子集中的數(shù)據(jù)盡可能的個子集后，要使每個子集中的數(shù)據(jù)盡可能的 “純純”，也就是說子集中的記錄要盡可能屬于同，也就是說子集中的記錄要盡可能屬于同 一個類別。如果套用熵的概念，即要使分裂后各一個類別。如果套用熵的概念，即要使分裂后各 子集的熵盡可能的小。子集的熵盡可能的小。 3.2 ID3、C4.5與與C5.0 v數(shù)據(jù)集數(shù)據(jù)集D被按照分裂屬性被按照分裂屬性“年齡年齡”分裂為兩分裂為兩 個子集個子集D1 和和D2 信息增益信息增益: Gain(D,年齡年齡)= H(D)P(D1)H(D1)+ P(D2)H(D2) v顯然，如果顯然，如果D 1 和和D 2 中的數(shù)據(jù)越中

25、的數(shù)據(jù)越 “純純”，H(D1)和和H(D2)就越小，信就越小，信 息增益就越大，或者說熵下降得越息增益就越大，或者說熵下降得越 多。多。 v按照這個方法，測試每一個屬性的信按照這個方法，測試每一個屬性的信 息增益，選擇增益值最大的屬性作為息增益，選擇增益值最大的屬性作為 分裂屬性。分裂屬性。 信息熵計算舉例信息熵計算舉例 v令令C1對應(yīng)對應(yīng)“是是”，C2對應(yīng)對應(yīng)“否否”。那么。那么C1有有9個樣個樣 本，本，C2有有5個樣本，所以數(shù)據(jù)集個樣本，所以數(shù)據(jù)集D的熵為：的熵為： 9406. 0) 14 5 (log 14 5 ) 14 9 (log 14 9 )5 , 9(),( 2221 IssI

26、 決策樹歸納策略 (1) v輸入輸入 數(shù)據(jù)劃分?jǐn)?shù)據(jù)劃分D是訓(xùn)練元組和對應(yīng)類標(biāo)號的集合是訓(xùn)練元組和對應(yīng)類標(biāo)號的集合 attribute_list,候選屬性的集合候選屬性的集合 Attribute_selection_method，指定選擇屬性的啟發(fā)性過程，指定選擇屬性的啟發(fā)性過程 算法步驟算法步驟 樹以代表訓(xùn)練樣本的單個節(jié)點（樹以代表訓(xùn)練樣本的單個節(jié)點（N）開始）開始 如果樣本都在同一個類，則該節(jié)點成為樹葉，并用該類標(biāo)記如果樣本都在同一個類，則該節(jié)點成為樹葉，并用該類標(biāo)記 1.否則，算法調(diào)用否則，算法調(diào)用Attribute_selection_method，選擇能夠最，選擇能夠最 好的將樣本分類

27、的屬性；確定好的將樣本分類的屬性；確定“分裂準(zhǔn)則分裂準(zhǔn)則”，指出，指出“分裂點分裂點” 或或“分裂子集分裂子集”。 決策樹歸納策略 (2) v對測試屬性每個已知的值，創(chuàng)建一個分支，對測試屬性每個已知的值，創(chuàng)建一個分支， 并以此劃分元組并以此劃分元組 v算法使用同樣的過程，遞歸的形成每個劃分算法使用同樣的過程，遞歸的形成每個劃分 上的元組決策樹。一旦一個屬性出現(xiàn)在一個上的元組決策樹。一旦一個屬性出現(xiàn)在一個 節(jié)點上，就不在該節(jié)點的任何子節(jié)點上出現(xiàn)節(jié)點上，就不在該節(jié)點的任何子節(jié)點上出現(xiàn) v遞歸劃分步驟停止的條件遞歸劃分步驟停止的條件 劃分劃分D（在（在N節(jié)點提供）的所有元組屬于同一類節(jié)點提供）的所有

28、元組屬于同一類 沒有剩余屬性可以用來進一步劃分元組沒有剩余屬性可以用來進一步劃分元組使用多數(shù)表決使用多數(shù)表決 沒有剩余的樣本沒有剩余的樣本 給定分支沒有元組，則以給定分支沒有元組，則以D中多數(shù)類創(chuàng)建一個樹葉中多數(shù)類創(chuàng)建一個樹葉 屬性選擇度量 v屬性選擇度量是一種選擇分裂準(zhǔn)則，將給定屬性選擇度量是一種選擇分裂準(zhǔn)則，將給定 類標(biāo)號的訓(xùn)練元組最好的進行劃分的方法類標(biāo)號的訓(xùn)練元組最好的進行劃分的方法 理想情況，每個劃分都是理想情況，每個劃分都是“純純”的，即落在給定的，即落在給定 劃分內(nèi)的元組都屬于相同的類劃分內(nèi)的元組都屬于相同的類 屬性選擇度量又稱為分裂準(zhǔn)則屬性選擇度量又稱為分裂準(zhǔn)則 v常用的屬性選

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

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

31、具有高區(qū)分度的 屬性。所以可以通過計算屬性。所以可以通過計算S中樣本的每個屬性的信息增中樣本的每個屬性的信息增 益，來得到一個屬性的相關(guān)性的排序。益，來得到一個屬性的相關(guān)性的排序。 ),.,( . )( 1 1 1 mjj v j mjj ssI s ss AE )(),.,()( 21 AEsssIAGain m v若以若以“年齡年齡”作為分裂屬性，作為分裂屬性， 則產(chǎn)生三個子集（因為該屬則產(chǎn)生三個子集（因為該屬 性有三個不同的取值），所性有三個不同的取值），所 以以D按照屬性按照屬性“年齡年齡”劃分劃分 出的三個子集的熵的加權(quán)和出的三個子集的熵的加權(quán)和 為：為： 6936. 03468.

32、003468. 0 ) 5 2 log 5 2 5 3 log 5 3 ( 14 5 ) 4 4 log 4 4 ( 14 4 ) 5 2 log 5 2 5 3 log 5 3 ( 14 5 ),( 22222 年齡DE 其中有一個子集的熵為其中有一個子集的熵為0 247. 06936. 09406. 0),(),(),( 21 年齡年齡DEssIDGain 9406. 0) 14 5 (log 14 5 ) 14 9 (log 14 9 )5 , 9(),( 2221 IssI v同理，若以“收入水平”為分裂屬性： 9111. 02318. 03936. 08572 . 0) 4 1 lo

33、g 4 1 4 3 log 4 3 ( 14 4 ) 6 2 log 6 2 6 4 log 6 4 ( 14 6 ) 4 2 log 4 2 4 2 log 4 2 ( 14 4 ),( 22 2222 收入水平DE 2950 . 09111. 09406. 0),(),(),( 21 收入水平收入水平DEssIDGain v若以“有固定收入”為分裂屬性： v若以“VIP”為分裂屬性： 7886. 02959. 04927. 0 ) 7 1 log 7 1 7 6 log 7 6 ( 14 7 ) 7 3 log 7 3 7 4 log 7 4 ( 14 7 ),( 2222 固定收入DE

34、152. 07886. 09406. 0),(),(),( 21 固定收入固定收入DEssIDGain 9228 . 02864 . 04636. 0 ) 6 3 log 6 3 6 3 log 6 3 ( 14 6 ) 8 2 log 8 2 8 6 log 8 6 ( 14 8 )VIP,( 2222 DE 0484. 08922. 09406. 0),(),(),( 21 VIPDEssIVIPDGain 以以“年齡年齡”作為分裂屬性，所得信息增益最大。作為分裂屬性，所得信息增益最大。 葉子節(jié)點葉子節(jié)點 ID3的主要缺點的主要缺點 vID3算法只能處理分類屬性（離散屬性），而不能算法只能

35、處理分類屬性（離散屬性），而不能 處理連續(xù)屬性（數(shù)值屬性）。在處理連續(xù)屬性時，處理連續(xù)屬性（數(shù)值屬性）。在處理連續(xù)屬性時， 一般要先將連續(xù)屬性劃分為多個區(qū)間，轉(zhuǎn)化為分一般要先將連續(xù)屬性劃分為多個區(qū)間，轉(zhuǎn)化為分 類屬性。例如類屬性。例如“年齡年齡”，要把數(shù)值事先轉(zhuǎn)換為諸，要把數(shù)值事先轉(zhuǎn)換為諸 如如“小于小于30歲歲”、“30至至50歲歲”、“大于大于50歲歲” 這樣的區(qū)間，再根據(jù)年齡值落入了某一個區(qū)間取這樣的區(qū)間，再根據(jù)年齡值落入了某一個區(qū)間取 相應(yīng)的類別值。通常，區(qū)間端點的選取包含著一相應(yīng)的類別值。通常，區(qū)間端點的選取包含著一 定的主觀因素。定的主觀因素。 vID3生成的決策樹是一棵多叉樹，分

36、支的數(shù)量取決生成的決策樹是一棵多叉樹，分支的數(shù)量取決 于分裂屬性有多少個不同的取值。這不利于處理于分裂屬性有多少個不同的取值。這不利于處理 分裂屬性取值數(shù)目較多的情況。因此目前流行的分裂屬性取值數(shù)目較多的情況。因此目前流行的 決策樹算法大多采用二叉樹模型。決策樹算法大多采用二叉樹模型。 vID3是采用是采用“信息增益信息增益”來選擇分裂屬性的。雖然來選擇分裂屬性的。雖然 這是一種有效的方法，但其具有明顯的傾向性，這是一種有效的方法，但其具有明顯的傾向性， 即它傾向于選擇具有大量不同取值的屬性，從而即它傾向于選擇具有大量不同取值的屬性，從而 產(chǎn)生許多小而純的子集。產(chǎn)生許多小而純的子集。 v尤其是

37、關(guān)系數(shù)據(jù)庫中作為主鍵的屬性，每一個樣尤其是關(guān)系數(shù)據(jù)庫中作為主鍵的屬性，每一個樣 本都有一個不同的取值。如果以這樣的屬性作為本都有一個不同的取值。如果以這樣的屬性作為 分裂屬性，那么將產(chǎn)生非常多的分支，而且每一分裂屬性，那么將產(chǎn)生非常多的分支，而且每一 個分支產(chǎn)生的子集的熵均為個分支產(chǎn)生的子集的熵均為0（因為子集中只有（因為子集中只有 一個樣本?。?。顯然，這樣的決策樹是沒有實際一個樣本?。?。顯然，這樣的決策樹是沒有實際 意義的。因此，意義的。因此，Quinlan提出使用增益比例來代提出使用增益比例來代 替信息增益。替信息增益。 3.2.2 C4.5 v設(shè)設(shè)S代表訓(xùn)練數(shù)據(jù)集，由代表訓(xùn)練數(shù)據(jù)集，由s

38、個樣本組成。個樣本組成。A是是 S的某個屬性，有的某個屬性，有m個不同的取值，根據(jù)這個不同的取值，根據(jù)這 些取值可以把些取值可以把S劃分為劃分為m個子集，個子集，Si表示第表示第i 個子集（個子集（i=1,2,m），），|Si|表示子集表示子集Si中的中的 樣本數(shù)量。那么：樣本數(shù)量。那么： ) | log | (),(_ 2 1 s S s S ASInfoSplit i m i i 稱為“數(shù)據(jù)集數(shù)據(jù)集S關(guān)于屬性關(guān)于屬性A的熵的熵”。 v用來衡量屬性A分裂數(shù)據(jù)集的廣度和均勻性。 樣本在屬性A上的取值分布越均勻， Split_Info(S,A)的值就越大。 v增益比例的定義為： v增益比例消除了

39、選擇那些值較多且均勻分 布的屬性作為分裂屬性的傾向性。 ),(_ASInfoSplit ),(_ ),( ),( ASInfoSplit ASGain ASGainRatio 連續(xù)屬性的處理連續(xù)屬性的處理 v設(shè)屬性設(shè)屬性Y有有m個不同的取值，按大小順序升序排列個不同的取值，按大小順序升序排列 為為v1v2, vi”將數(shù)據(jù)集劃分為兩個部分，將數(shù)據(jù)集劃分為兩個部分， 形成兩個分支。顯然，形成兩個分支。顯然， v1,v2, vm-1就是可能的就是可能的 閾值的集合，共閾值的集合，共(m-1)個元素。個元素。 v把這些閾值一一取出來，并根據(jù)把這些閾值一一取出來，并根據(jù)“Yvi”和和“Y vi” 把訓(xùn)練

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

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

42、別中也不會隨意地將它分配到某個類別中 去。去。 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 treedec

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

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

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

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

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

48、建立。隨后，建立第二個模型，方式建立。隨后，建立第二個模型， 聚焦于被第一個模型錯誤分類的記聚焦于被第一個模型錯誤分類的記 錄。以此類推，最后應(yīng)用整個模型錄。以此類推，最后應(yīng)用整個模型 集對樣本進行分類，使用加權(quán)投票集對樣本進行分類，使用加權(quán)投票 過程把分散的預(yù)測合并成綜合預(yù)測。過程把分散的預(yù)測合并成綜合預(yù)測。 The Number of trialsThe Number of trials選項允許控選項允許控 制用于助推的模型數(shù)量。制用于助推的模型數(shù)量。 v交叉驗證（交叉驗證（Cross validate）：如果選擇了該）：如果選擇了該 選項，選項，C5.0將使用一組基于將使用一組基于 訓(xùn)練

49、數(shù)據(jù)子集建立的模型，訓(xùn)練數(shù)據(jù)子集建立的模型， 來估計基于全部數(shù)據(jù)建立的來估計基于全部數(shù)據(jù)建立的 模型的精確度。如果數(shù)據(jù)集模型的精確度。如果數(shù)據(jù)集 過小，不能拆分成傳統(tǒng)意義過小，不能拆分成傳統(tǒng)意義 上的訓(xùn)練集和測試集，這將上的訓(xùn)練集和測試集，這將 非常有用?；蛴糜诮徊骝炞C非常有用。或用于交叉驗證 的模型數(shù)目。的模型數(shù)目。 v模式（模式（Mode）：對于簡單的）：對于簡單的 訓(xùn)練，絕大多數(shù)訓(xùn)練，絕大多數(shù)C5.0參數(shù)是參數(shù)是 自動設(shè)置。高級訓(xùn)練模式選自動設(shè)置。高級訓(xùn)練模式選 項允許對訓(xùn)練參數(shù)更多的直項允許對訓(xùn)練參數(shù)更多的直 接控制。接控制。 v簡單模式選項（簡單模式選項（simplesimple）

50、v偏好（偏好（FavorFavor）：）： 在在accuracyaccuracy下，下，C5.0C5.0會生會生 成盡可能精確的決策樹。成盡可能精確的決策樹。 在某些情況下，這會導(dǎo)致在某些情況下，這會導(dǎo)致 過度擬和。選擇過度擬和。選擇 GeneralityGenerality（一般化）項（一般化）項 以使用不易受該問題影響以使用不易受該問題影響 的算法設(shè)置。的算法設(shè)置。 v期望噪聲百分?jǐn)?shù)期望噪聲百分?jǐn)?shù) （Expected noise Expected noise （% %）：）： 指定訓(xùn)練集中的噪聲或錯指定訓(xùn)練集中的噪聲或錯 誤數(shù)據(jù)期望比率。誤數(shù)據(jù)期望比率。 v高級模式選項高級模式選項 v修剪

51、純度（修剪純度（pruning severity）：決定生）：決定生 成決策樹或規(guī)則集被修剪的程度。提高成決策樹或規(guī)則集被修剪的程度。提高 純度值將獲得更小，更簡潔的決策樹。純度值將獲得更小，更簡潔的決策樹。 降低純度值將獲得更加精確的決策樹。降低純度值將獲得更加精確的決策樹。 v子分支最少記錄數(shù)（子分支最少記錄數(shù)（Minimum records per child branch）：子群大小可以用于）：子群大小可以用于 限制決策樹任一分支的拆分?jǐn)?shù)。只有當(dāng)限制決策樹任一分支的拆分?jǐn)?shù)。只有當(dāng) 兩個或以上的后序子分支包括來自訓(xùn)練兩個或以上的后序子分支包括來自訓(xùn)練 集的記錄不少于最小記錄數(shù)，決策樹才集

52、的記錄不少于最小記錄數(shù)，決策樹才 會繼續(xù)拆分。默認(rèn)值為會繼續(xù)拆分。默認(rèn)值為2，提高該值將有，提高該值將有 助于避免噪聲數(shù)據(jù)的過度訓(xùn)練。助于避免噪聲數(shù)據(jù)的過度訓(xùn)練。 v全局修剪（全局修剪（Use global pruning）：）： 第一階段：局部修建第一階段：局部修建 第二階段：全局修剪第二階段：全局修剪 v排除屬性（排除屬性（Winnow attributes）：如果）：如果 選擇了該選項，選擇了該選項，C5.0會在建立模型前檢會在建立模型前檢 驗預(yù)測字段的有用性。被發(fā)現(xiàn)與分析無驗預(yù)測字段的有用性。被發(fā)現(xiàn)與分析無 關(guān)的預(yù)測字段將不參與建模過程。這一關(guān)的預(yù)測字段將不參與建模過程。這一 選項對有

53、許多預(yù)測字段元的模型非常有選項對有許多預(yù)測字段元的模型非常有 用，并且有助于避免過度擬和。用，并且有助于避免過度擬和。 圖圖1 指定錯誤歸類損失指定錯誤歸類損失 錯誤歸類損失允許指定不同類錯誤歸類損失允許指定不同類 型預(yù)測錯誤之間的相對重要性。型預(yù)測錯誤之間的相對重要性。 錯誤歸類損失矩陣顯示預(yù)測類錯誤歸類損失矩陣顯示預(yù)測類 和實際類每一可能組合的損失。和實際類每一可能組合的損失。 所有的錯誤歸類損失都預(yù)設(shè)設(shè)所有的錯誤歸類損失都預(yù)設(shè)設(shè) 置為置為1.01.0。要輸入自定義損失值，。要輸入自定義損失值， 選擇選擇Use misclassification Use misclassification

54、 costscosts，然后把自定義值輸入到，然后把自定義值輸入到 損失矩陣中。損失矩陣中。 具體設(shè)置具體設(shè)置 執(zhí)行結(jié)果執(zhí)行結(jié)果 二、預(yù)測結(jié)果二、預(yù)測結(jié)果 為觀測為觀測C5.0對每個樣本的預(yù)測結(jié)果，可在流管理器的對每個樣本的預(yù)測結(jié)果，可在流管理器的 Models卡中，鼠標(biāo)右擊卡中，鼠標(biāo)右擊C5.0模型結(jié)果，選擇彈出菜單中的模型結(jié)果，選擇彈出菜單中的 Add To Stream，并將模型結(jié)果連接到數(shù)據(jù)流中，然后連接，并將模型結(jié)果連接到數(shù)據(jù)流中，然后連接 Table節(jié)點查看預(yù)測結(jié)果，如下圖所示：節(jié)點查看預(yù)測結(jié)果，如下圖所示： 三、三、C5.0模型評價模型評價 3.3 CART v分類和回歸樹（分類

55、和回歸樹（Classification and Regression Trees，CART,在在Clementine中中 簡寫為簡寫為C&RT） vCART算法中的每一次分裂把數(shù)據(jù)分為算法中的每一次分裂把數(shù)據(jù)分為兩個兩個 子集，每個子集中的樣本比被劃分之前具有子集，每個子集中的樣本比被劃分之前具有 更好的一致性。它是一個遞歸的過程，也就更好的一致性。它是一個遞歸的過程，也就 是說，這些子集還會被繼續(xù)劃分，這個過程是說，這些子集還會被繼續(xù)劃分，這個過程 不斷重復(fù)，直到滿足終止準(zhǔn)則，然后通過修不斷重復(fù)，直到滿足終止準(zhǔn)則，然后通過修 剪和評估，得到一棵最優(yōu)的決策樹。剪和評估，得到一棵最優(yōu)的決策樹。 三個步驟三個步驟 v生成最大樹生成最大樹 生成一棵充分生長的最大樹生成一棵充分生長的最大樹 v樹的修剪樹的修剪 根據(jù)修剪算法對最大樹進行修剪，生成由許多子根據(jù)修剪算法對最大樹進行修剪，生成由許多子 樹組成的子樹序列樹組成的子樹序列 v子樹評估子樹評估 從子樹序列中選擇一棵最優(yōu)的子樹作為最后的結(jié)從子樹序列中選擇一棵最優(yōu)的子樹作為最后的結(jié) 果。果。 3.3.1 生成最大樹生成最大樹 v標(biāo)準(zhǔn)