分類與決策樹(shù)

分類與決策樹(shù)第1頁(yè)，共91頁(yè)，2023年，2月20日，星期三主要內(nèi)容分類與決策樹(shù)概述ID3、C4.5與C5.0CART第2頁(yè)，共91頁(yè)，2023年，2月20日，星期三分類VS.預(yù)測(cè)分類和預(yù)測(cè)是兩種數(shù)據(jù)分析形式，用于提取描述重要數(shù)據(jù)類或預(yù)測(cè)未來(lái)的數(shù)據(jù)趨勢(shì)的模型分類：預(yù)測(cè)類對(duì)象的分類標(biāo)號(hào)（或離散值）根據(jù)訓(xùn)練數(shù)據(jù)集和類標(biāo)號(hào)屬性，構(gòu)建模型來(lái)分類現(xiàn)有數(shù)據(jù)，并用來(lái)分類新數(shù)據(jù)預(yù)測(cè)：建立連續(xù)函數(shù)值模型比如預(yù)測(cè)空缺值，或者預(yù)測(cè)顧客在計(jì)算機(jī)設(shè)備上的花費(fèi)典型應(yīng)用欺詐檢測(cè)、市場(chǎng)定位、性能預(yù)測(cè)、醫(yī)療診斷分類是一種應(yīng)用非常廣泛的數(shù)據(jù)挖掘技術(shù)分類與預(yù)測(cè)的區(qū)別：當(dāng)估計(jì)的屬性值是離散值時(shí)，這就是分類；當(dāng)估計(jì)的屬性值是連續(xù)值時(shí)，這就是預(yù)測(cè)。第3頁(yè)，共91頁(yè)，2023年，2月20日，星期三分類和預(yù)測(cè)---示例分類銀行貸款員需要分析數(shù)據(jù)，來(lái)弄清哪些貸款申請(qǐng)者是安全的，哪些是有風(fēng)險(xiǎn)的（將貸款申請(qǐng)者分為“安全”和“有風(fēng)險(xiǎn)”兩類）我們需要構(gòu)造一個(gè)分類器來(lái)預(yù)測(cè)類屬編號(hào)，比如預(yù)測(cè)顧客屬類預(yù)測(cè)銀行貸款員需要預(yù)測(cè)貸給某個(gè)顧客多少錢是安全的構(gòu)造一個(gè)預(yù)測(cè)器，預(yù)測(cè)一個(gè)連續(xù)值函數(shù)或有序值，常用方法是回歸分析第4頁(yè)，共91頁(yè)，2023年，2月20日，星期三數(shù)據(jù)分類——一個(gè)兩步過(guò)程(1)第一步，也成為學(xué)習(xí)步，目標(biāo)是建立描述預(yù)先定義的數(shù)據(jù)類或概念集的分類器分類算法通過(guò)分析或從訓(xùn)練集“學(xué)習(xí)”來(lái)構(gòu)造分類器。訓(xùn)練集由數(shù)據(jù)庫(kù)元組（用n維屬性向量表示）和他們相對(duì)應(yīng)的類編號(hào)組成；假定每個(gè)元組屬于一個(gè)預(yù)定義的類訓(xùn)練元組：訓(xùn)練數(shù)據(jù)集中的單個(gè)元組學(xué)習(xí)模型可以用分類規(guī)則、決策樹(shù)或數(shù)學(xué)公式的形式提供第5頁(yè)，共91頁(yè)，2023年，2月20日，星期三數(shù)據(jù)分類——一個(gè)兩步過(guò)程(2)第二步，使用模型，對(duì)將來(lái)的或未知的對(duì)象進(jìn)行分類首先評(píng)估模型的預(yù)測(cè)準(zhǔn)確率對(duì)每個(gè)測(cè)試樣本，將已知的類標(biāo)號(hào)和該樣本的學(xué)習(xí)模型類預(yù)測(cè)比較模型在給定測(cè)試集上的準(zhǔn)確率是正確被模型分類的測(cè)試樣本的百分比測(cè)試集要獨(dú)立于訓(xùn)練樣本集，否則會(huì)出現(xiàn)“過(guò)分?jǐn)M合”的情況第6頁(yè)，共91頁(yè)，2023年，2月20日，星期三第一步——建立模型訓(xùn)練數(shù)據(jù)集分類算法IFrank=‘professor’ORyears>6THENtenured=‘yes’分類規(guī)則第7頁(yè)，共91頁(yè)，2023年，2月20日，星期三第二步——用模型進(jìn)行分類分類規(guī)則測(cè)試集未知數(shù)據(jù)(Jeff,Professor,4)Tenured?第8頁(yè)，共91頁(yè)，2023年，2月20日，星期三監(jiān)督學(xué)習(xí)VS.無(wú)監(jiān)督學(xué)習(xí)監(jiān)督學(xué)習(xí)（用于分類）模型的學(xué)習(xí)在被告知每個(gè)訓(xùn)練樣本屬于哪個(gè)類的“指導(dǎo)”下進(jìn)行新數(shù)據(jù)使用訓(xùn)練數(shù)據(jù)集中得到的規(guī)則進(jìn)行分類無(wú)監(jiān)督學(xué)習(xí)（用于聚類）每個(gè)訓(xùn)練樣本的類編號(hào)是未知的，要學(xué)習(xí)的類集合或數(shù)量也可能是事先未知的通過(guò)一系列的度量、觀察來(lái)建立數(shù)據(jù)中的類編號(hào)或進(jìn)行聚類第9頁(yè)，共91頁(yè)，2023年，2月20日，星期三數(shù)據(jù)預(yù)測(cè)的兩步過(guò)程數(shù)據(jù)預(yù)測(cè)也是一個(gè)兩步的過(guò)程，類似于前面描述的數(shù)據(jù)分類對(duì)于預(yù)測(cè)，沒(méi)有“類標(biāo)號(hào)屬性”要預(yù)測(cè)的屬性是連續(xù)值，而不是離散值，該屬性可簡(jiǎn)稱“預(yù)測(cè)屬性”E.g.銀行貸款員需要預(yù)測(cè)貸給某個(gè)顧客多少錢是安全的預(yù)測(cè)器可以看作一個(gè)映射或函數(shù)y=f(X)其中X是輸入；y是輸出，是一個(gè)連續(xù)或有序的值與分類類似，準(zhǔn)確率的預(yù)測(cè)，也要使用單獨(dú)的測(cè)試集第10頁(yè)，共91頁(yè)，2023年，2月20日，星期三3.1決策樹(shù)概述決策樹(shù)(DecisionTree)

一種描述概念空間的有效的歸納推理辦法?；跊Q策樹(shù)的學(xué)習(xí)方法可以進(jìn)行不相關(guān)的多概念學(xué)習(xí)，具有簡(jiǎn)單快捷的優(yōu)勢(shì)，已經(jīng)在各個(gè)領(lǐng)域取得廣泛應(yīng)用。決策樹(shù)是一種樹(shù)型結(jié)構(gòu)，其中每個(gè)內(nèi)部結(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試，每個(gè)分支代表一個(gè)測(cè)試輸出，每個(gè)葉結(jié)點(diǎn)代表一種類別。第11頁(yè)，共91頁(yè)，2023年，2月20日，星期三決策樹(shù)學(xué)習(xí)是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)。從一類無(wú)序、無(wú)規(guī)則的事物（概念）中推理出決策樹(shù)表示的分類規(guī)則。概念分類學(xué)習(xí)算法：來(lái)源于Hunt,Marin和Stone于1966年研制的CLS學(xué)習(xí)系統(tǒng)，用于學(xué)習(xí)單個(gè)概念。1979年,J.R.Quinlan給出ID3算法，并在1983年和1986年對(duì)ID3進(jìn)行了總結(jié)和簡(jiǎn)化，使其成為決策樹(shù)學(xué)習(xí)算法的典型。Schlimmer和Fisher于1986年對(duì)ID3進(jìn)行改造，在每個(gè)可能的決策樹(shù)節(jié)點(diǎn)創(chuàng)建緩沖區(qū)，使決策樹(shù)可以遞增式生成，得到ID4算法。1988年，Utgoff在ID4基礎(chǔ)上提出了ID5學(xué)習(xí)算法，進(jìn)一步提高了效率。1993年，Quinlan進(jìn)一步發(fā)展了ID3算法，改進(jìn)成C4.5算法。另一類決策樹(shù)算法為CART，與C4.5不同的是，CART的決策樹(shù)由二元邏輯問(wèn)題生成，每個(gè)樹(shù)節(jié)點(diǎn)只有兩個(gè)分枝，分別包括學(xué)習(xí)實(shí)例的正例與反例。其基本思想是以信息熵為度量構(gòu)造一棵熵值下降最快的樹(shù)，到葉子節(jié)點(diǎn)處的熵值為零，此時(shí)每個(gè)葉節(jié)點(diǎn)中的實(shí)例都屬于同一類。第12頁(yè)，共91頁(yè)，2023年，2月20日，星期三決策樹(shù)學(xué)習(xí)采用的是自頂向下的遞歸方法。決策樹(shù)的每一層節(jié)點(diǎn)依照某一屬性值向下分為子節(jié)點(diǎn)，待分類的實(shí)例在每一節(jié)點(diǎn)處與該節(jié)點(diǎn)相關(guān)的屬性值進(jìn)行比較，根據(jù)不同的比較結(jié)果向相應(yīng)的子節(jié)點(diǎn)擴(kuò)展，這一過(guò)程在到達(dá)決策樹(shù)的葉節(jié)點(diǎn)時(shí)結(jié)束，此時(shí)得到結(jié)論。從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每一條路經(jīng)都對(duì)應(yīng)著一條合理的規(guī)則，規(guī)則間各個(gè)部分（各個(gè)層的條件）的關(guān)系是合取關(guān)系。整個(gè)決策樹(shù)就對(duì)應(yīng)著一組析取的規(guī)則。決策樹(shù)學(xué)習(xí)算法的最大優(yōu)點(diǎn)是，它可以自學(xué)習(xí)。在學(xué)習(xí)的過(guò)程中，不需要使用者了解過(guò)多背景知識(shí)，只需要對(duì)訓(xùn)練例子進(jìn)行較好的標(biāo)注，就能夠進(jìn)行學(xué)習(xí)。如果在應(yīng)用中發(fā)現(xiàn)不符合規(guī)則的實(shí)例，程序會(huì)詢問(wèn)用戶該實(shí)例的正確分類，從而生成新的分枝和葉子，并添加到樹(shù)中。第13頁(yè)，共91頁(yè)，2023年，2月20日，星期三樹(shù)是由節(jié)點(diǎn)和分枝組成的層次數(shù)據(jù)結(jié)構(gòu)。節(jié)點(diǎn)用于存貯信息或知識(shí)，分枝用于連接各個(gè)節(jié)點(diǎn)。樹(shù)是圖的一個(gè)特例，圖是更一般的數(shù)學(xué)結(jié)構(gòu)，如貝葉斯網(wǎng)絡(luò)。

決策樹(shù)是描述分類過(guò)程的一種數(shù)據(jù)結(jié)構(gòu)，從上端的根節(jié)點(diǎn)開(kāi)始，各種分類原則被引用進(jìn)來(lái)，并依這些分類原則將根節(jié)點(diǎn)的數(shù)據(jù)集劃分為子集，這一劃分過(guò)程直到某種約束條件滿足而結(jié)束。

根結(jié)點(diǎn)個(gè)子大可能是松鼠可能是老鼠可能是大象在水里會(huì)吱吱叫鼻子長(zhǎng)脖子長(zhǎng)個(gè)子小不會(huì)吱吱叫鼻子短脖子短可能是長(zhǎng)頸鹿在陸地上可能是犀牛可能是河馬第14頁(yè)，共91頁(yè)，2023年，2月20日，星期三可以看到，一個(gè)決策樹(shù)的內(nèi)部結(jié)點(diǎn)包含學(xué)習(xí)的實(shí)例，每層分枝代表了實(shí)例的一個(gè)屬性的可能取值，葉節(jié)點(diǎn)是最終劃分成的類。如果判定是二元的，那么構(gòu)造的將是一棵二叉樹(shù)，在樹(shù)中每回答一個(gè)問(wèn)題就降到樹(shù)的下一層，這類樹(shù)一般稱為CART（ClassificationAndRegressionTree）。判定結(jié)構(gòu)可以機(jī)械的轉(zhuǎn)變成產(chǎn)生式規(guī)則。可以通過(guò)對(duì)結(jié)構(gòu)進(jìn)行廣度優(yōu)先搜索，并在每個(gè)節(jié)點(diǎn)生成“IF…THEN”規(guī)則來(lái)實(shí)現(xiàn)。如圖6-13的決策樹(shù)可以轉(zhuǎn)換成下規(guī)則：

IF“個(gè)子大”THENIF“脖子短”THENIF“鼻子長(zhǎng)”THEN可能是大象形式化表示成

根結(jié)點(diǎn)個(gè)子大可能是松鼠可能是老鼠可能是大象在水里會(huì)吱吱叫鼻子長(zhǎng)脖子長(zhǎng)個(gè)子小不會(huì)吱吱叫鼻子短脖子短可能是長(zhǎng)頸鹿在陸地上可能是犀?？赡苁呛玉R第15頁(yè)，共91頁(yè)，2023年，2月20日，星期三構(gòu)造一棵決策樹(shù)要解決四個(gè)問(wèn)題：收集待分類的數(shù)據(jù)，這些數(shù)據(jù)的所有屬性應(yīng)該是完全標(biāo)注的。設(shè)計(jì)分類原則，即數(shù)據(jù)的哪些屬性可以被用來(lái)分類，以及如何將該屬性量化。分類原則的選擇，即在眾多分類準(zhǔn)則中，每一步選擇哪一準(zhǔn)則使最終的樹(shù)更令人滿意。設(shè)計(jì)分類停止條件，實(shí)際應(yīng)用中數(shù)據(jù)的屬性很多，真正有分類意義的屬性往往是有限幾個(gè)，因此在必要的時(shí)候應(yīng)該停止數(shù)據(jù)集分裂：該節(jié)點(diǎn)包含的數(shù)據(jù)太少不足以分裂，繼續(xù)分裂數(shù)據(jù)集對(duì)樹(shù)生成的目標(biāo)(例如ID3中的熵下降準(zhǔn)則)沒(méi)有貢獻(xiàn)，樹(shù)的深度過(guò)大不宜再分。通用的決策樹(shù)分裂目標(biāo)是整棵樹(shù)的熵總量最小，每一步分裂時(shí)，選擇使熵減小最大的準(zhǔn)則，這種方案使最具有分類潛力的準(zhǔn)則最先被提取出來(lái)第16頁(yè)，共91頁(yè)，2023年，2月20日，星期三預(yù)測(cè)變量目標(biāo)變量記錄樣本類標(biāo)號(hào)屬性類別集合：Class={“優(yōu)”，“良”，“差”}決策樹(shù)的基本原理第17頁(yè)，共91頁(yè)，2023年，2月20日，星期三根節(jié)點(diǎn)葉子節(jié)點(diǎn)分裂屬性分裂謂詞每一個(gè)葉子節(jié)點(diǎn)都被確定一個(gè)類標(biāo)號(hào)第18頁(yè)，共91頁(yè)，2023年，2月20日，星期三每一個(gè)節(jié)點(diǎn)都代表了一個(gè)數(shù)據(jù)集。根節(jié)點(diǎn)1代表了初始數(shù)據(jù)集D其它節(jié)點(diǎn)都是數(shù)據(jù)集D的子集。例如，節(jié)點(diǎn)2代表數(shù)據(jù)集D中年齡小于40歲的那部分樣本組成的數(shù)據(jù)集。子節(jié)點(diǎn)是父節(jié)點(diǎn)的子集。

If(年齡<40)and(職業(yè)=“學(xué)生”or職業(yè)=“教師”)Then信用等級(jí)=“優(yōu)”If(年齡<40)and(職業(yè)!=“學(xué)生”and職業(yè)!=“教師”)Then信用等級(jí)=“良”If(年齡≥40)and(月薪<1000)Then信用等級(jí)=“差”If(年齡≥40)and(月薪≥1000and月薪≤3000)Then信用等級(jí)=“良”If(年齡≥40)and(月薪>3000)Then信用等級(jí)=“優(yōu)”第19頁(yè)，共91頁(yè)，2023年，2月20日，星期三決策樹(shù)是指具有下列三個(gè)性質(zhì)的樹(shù)：每個(gè)非葉子節(jié)點(diǎn)都被標(biāo)記一個(gè)分裂屬性Ai；每個(gè)分支都被標(biāo)記一個(gè)分裂謂詞，這個(gè)分裂謂詞是分裂父節(jié)點(diǎn)的具體依據(jù)；每個(gè)葉子節(jié)點(diǎn)都被標(biāo)記一個(gè)類標(biāo)號(hào)Cj∈C。任何一個(gè)決策樹(shù)算法，其核心步驟都是為每一次分裂確定一個(gè)分裂屬性，即究竟按照哪一個(gè)屬性來(lái)把當(dāng)前數(shù)據(jù)集劃分為若干個(gè)子集，從而形成若干個(gè)“樹(shù)枝”。第20頁(yè)，共91頁(yè)，2023年，2月20日，星期三熵，是數(shù)據(jù)集中的不確定性、突發(fā)性或隨機(jī)性的程度的度量。當(dāng)一個(gè)數(shù)據(jù)集中的記錄全部都屬于同一類的時(shí)候，則沒(méi)有不確定性，這種情況下的熵就為0。決策樹(shù)分裂的基本原則是，數(shù)據(jù)集被分裂為若干個(gè)子集后，要使每個(gè)子集中的數(shù)據(jù)盡可能的“純”，也就是說(shuō)子集中的記錄要盡可能屬于同一個(gè)類別。如果套用熵的概念，即要使分裂后各子集的熵盡可能的小。3.2ID3、C4.5與C5.0第21頁(yè)，共91頁(yè)，2023年，2月20日，星期三數(shù)據(jù)集D被按照分裂屬性“年齡”分裂為兩個(gè)子集D1和D2

信息增益:Gain(D,年齡)=H(D)–[P(D1)×H(D1)+P(D2)×H(D2)]第22頁(yè)，共91頁(yè)，2023年，2月20日，星期三顯然，如果D1和D2中的數(shù)據(jù)越“純”，H(D1)和H(D2)就越小，信息增益就越大，或者說(shuō)熵下降得越多。按照這個(gè)方法，測(cè)試每一個(gè)屬性的信息增益，選擇增益值最大的屬性作為分裂屬性。第23頁(yè)，共91頁(yè)，2023年，2月20日，星期三信息熵計(jì)算舉例令C1對(duì)應(yīng)“是”，C2對(duì)應(yīng)“否”。那么C1有9個(gè)樣本，C2有5個(gè)樣本，所以數(shù)據(jù)集D的熵為：第24頁(yè)，共91頁(yè)，2023年，2月20日，星期三決策樹(shù)歸納策略(1)輸入數(shù)據(jù)劃分D是訓(xùn)練元組和對(duì)應(yīng)類標(biāo)號(hào)的集合attribute_list,候選屬性的集合Attribute_selection_method，指定選擇屬性的啟發(fā)性過(guò)程算法步驟樹(shù)以代表訓(xùn)練樣本的單個(gè)節(jié)點(diǎn)（N）開(kāi)始如果樣本都在同一個(gè)類，則該節(jié)點(diǎn)成為樹(shù)葉，并用該類標(biāo)記否則，算法調(diào)用Attribute_selection_method，選擇能夠最好的將樣本分類的屬性；確定“分裂準(zhǔn)則”，指出“分裂點(diǎn)”或“分裂子集”。第25頁(yè)，共91頁(yè)，2023年，2月20日，星期三決策樹(shù)歸納策略(2)對(duì)測(cè)試屬性每個(gè)已知的值，創(chuàng)建一個(gè)分支，并以此劃分元組算法使用同樣的過(guò)程，遞歸的形成每個(gè)劃分上的元組決策樹(shù)。一旦一個(gè)屬性出現(xiàn)在一個(gè)節(jié)點(diǎn)上，就不在該節(jié)點(diǎn)的任何子節(jié)點(diǎn)上出現(xiàn)遞歸劃分步驟停止的條件劃分D（在N節(jié)點(diǎn)提供）的所有元組屬于同一類沒(méi)有剩余屬性可以用來(lái)進(jìn)一步劃分元組——使用多數(shù)表決沒(méi)有剩余的樣本給定分支沒(méi)有元組，則以D中多數(shù)類創(chuàng)建一個(gè)樹(shù)葉第26頁(yè)，共91頁(yè)，2023年，2月20日，星期三屬性選擇度量屬性選擇度量是一種選擇分裂準(zhǔn)則，將給定類標(biāo)號(hào)的訓(xùn)練元組最好的進(jìn)行劃分的方法理想情況，每個(gè)劃分都是“純”的，即落在給定劃分內(nèi)的元組都屬于相同的類屬性選擇度量又稱為分裂準(zhǔn)則常用的屬性選擇度量信息增益增益率Gini指標(biāo)第27頁(yè)，共91頁(yè)，2023年，2月20日，星期三信息增益(1)S是一個(gè)訓(xùn)練樣本的集合，該樣本中每個(gè)集合的類編號(hào)已知。每個(gè)樣本為一個(gè)元組。有個(gè)屬性用來(lái)判定某個(gè)訓(xùn)練樣本的類編號(hào)假設(shè)S中有m個(gè)類，總共s個(gè)訓(xùn)練樣本，每個(gè)類Ci有si個(gè)樣本(i＝1,2,3...m)，那么任意一個(gè)樣本屬于類Ci的概率是si/s，那么用來(lái)分類一個(gè)給定樣本的期望信息是：第28頁(yè)，共91頁(yè)，2023年，2月20日，星期三信息增益(2)一個(gè)有v個(gè)值的屬性A{a1,a2,...,av}可以將S分成v個(gè)子集{S1,S2,...,Sv}，其中Sj包含S中屬性A上的值為aj的樣本。假設(shè)Sj包含類Ci的sij個(gè)樣本。根據(jù)A的這種劃分的期望信息稱為A的熵A上該劃分的獲得的信息增益定義為：具有高信息增益的屬性，是給定集合中具有高區(qū)分度的屬性。所以可以通過(guò)計(jì)算S中樣本的每個(gè)屬性的信息增益，來(lái)得到一個(gè)屬性的相關(guān)性的排序。第29頁(yè)，共91頁(yè)，2023年，2月20日，星期三若以“年齡”作為分裂屬性，則產(chǎn)生三個(gè)子集（因?yàn)樵搶傩杂腥齻€(gè)不同的取值），所以D按照屬性“年齡”劃分出的三個(gè)子集的熵的加權(quán)和為：其中有一個(gè)子集的熵為0第30頁(yè)，共91頁(yè)，2023年，2月20日，星期三同理，若以“收入水平”為分裂屬性：第31頁(yè)，共91頁(yè)，2023年，2月20日，星期三若以“有固定收入”為分裂屬性：若以“VIP”為分裂屬性：第32頁(yè)，共91頁(yè)，2023年，2月20日，星期三以“年齡”作為分裂屬性，所得信息增益最大。葉子節(jié)點(diǎn)第33頁(yè)，共91頁(yè)，2023年，2月20日，星期三第34頁(yè)，共91頁(yè)，2023年，2月20日，星期三ID3的主要缺點(diǎn)ID3算法只能處理分類屬性（離散屬性），而不能處理連續(xù)屬性（數(shù)值屬性）。在處理連續(xù)屬性時(shí)，一般要先將連續(xù)屬性劃分為多個(gè)區(qū)間，轉(zhuǎn)化為分類屬性。例如“年齡”，要把數(shù)值事先轉(zhuǎn)換為諸如“小于30歲”、“30至50歲”、“大于50歲”這樣的區(qū)間，再根據(jù)年齡值落入了某一個(gè)區(qū)間取相應(yīng)的類別值。通常，區(qū)間端點(diǎn)的選取包含著一定的主觀因素。ID3生成的決策樹(shù)是一棵多叉樹(shù)，分支的數(shù)量取決于分裂屬性有多少個(gè)不同的取值。這不利于處理分裂屬性取值數(shù)目較多的情況。因此目前流行的決策樹(shù)算法大多采用二叉樹(shù)模型。第35頁(yè)，共91頁(yè)，2023年，2月20日，星期三ID3是采用“信息增益”來(lái)選擇分裂屬性的。雖然這是一種有效的方法，但其具有明顯的傾向性，即它傾向于選擇具有大量不同取值的屬性，從而產(chǎn)生許多小而純的子集。尤其是關(guān)系數(shù)據(jù)庫(kù)中作為主鍵的屬性，每一個(gè)樣本都有一個(gè)不同的取值。如果以這樣的屬性作為分裂屬性，那么將產(chǎn)生非常多的分支，而且每一個(gè)分支產(chǎn)生的子集的熵均為0（因?yàn)樽蛹兄挥幸粋€(gè)樣本?。?。顯然，這樣的決策樹(shù)是沒(méi)有實(shí)際意義的。因此，Quinlan提出使用增益比例來(lái)代替信息增益。3.2.2C4.5第36頁(yè)，共91頁(yè)，2023年，2月20日，星期三設(shè)S代表訓(xùn)練數(shù)據(jù)集，由s個(gè)樣本組成。A是S的某個(gè)屬性，有m個(gè)不同的取值，根據(jù)這些取值可以把S劃分為m個(gè)子集，Si表示第i個(gè)子集（i=1,2,…,m），|Si|表示子集Si中的樣本數(shù)量。那么：稱為“數(shù)據(jù)集S關(guān)于屬性A的熵”。第37頁(yè)，共91頁(yè)，2023年，2月20日，星期三用來(lái)衡量屬性A分裂數(shù)據(jù)集的廣度和均勻性。樣本在屬性A上的取值分布越均勻，Split_Info(S,A)的值就越大。增益比例的定義為：增益比例消除了選擇那些值較多且均勻分布的屬性作為分裂屬性的傾向性。第38頁(yè)，共91頁(yè)，2023年，2月20日，星期三連續(xù)屬性的處理

設(shè)屬性Y有m個(gè)不同的取值，按大小順序升序排列為v1<v2<,…,<vm。從{v1,v2,…,vm-1}中選擇一個(gè)vi作為閾值，則可以根據(jù)“Y≤vi”和“Y>vi”將數(shù)據(jù)集劃分為兩個(gè)部分，形成兩個(gè)分支。顯然，{v1,v2,…,vm-1}就是可能的閾值的集合，共(m-1)個(gè)元素。把這些閾值一一取出來(lái)，并根據(jù)“Y≤vi”和“Y>vi”把訓(xùn)練數(shù)據(jù)集劃分為兩個(gè)子集，并計(jì)算每一種劃分方案下的信息增益或增益比例，選擇最大增益或增益比例所對(duì)應(yīng)的那個(gè)閾值，作為最優(yōu)的閾值?？梢钥闯?，如果選擇連續(xù)屬性作為分裂屬性，則分裂后只有兩個(gè)分支，而不象離散屬性那樣可能會(huì)有多個(gè)分支（由離散屬性的取值個(gè)數(shù)決定）。

第39頁(yè)，共91頁(yè)，2023年，2月20日，星期三第40頁(yè)，共91頁(yè)，2023年，2月20日，星期三如果要計(jì)算“年齡”屬性的信息增益，則首先將不同的屬性值排序{20,25,28,40,46,55,56,58,60,65,70}那么可能的閾值集合為{20,25,28,40,46,55,56,58,60,65,70}，從中一一取出，并形成分裂謂詞，例如取出“20”，形成謂詞“≤20”和“>20”，用它們劃分訓(xùn)練數(shù)據(jù)集，然后計(jì)算信息增益或增益比例。第41頁(yè)，共91頁(yè)，2023年，2月20日，星期三處理有缺失值的樣本

C4.5并不會(huì)武斷地將一個(gè)有缺失值的樣本拋棄,也不會(huì)隨意地將它分配到某個(gè)類別中去?！笆杖胨健钡闹担椤案摺钡母怕蕿?/12，取為“中”的概率為5/12，取為“低”的概率為4/12。S1（收入水平=“高”）的樣本數(shù)量為：3+2×(3/12)；第42頁(yè)，共91頁(yè)，2023年，2月20日，星期三3.2.4C5.0算法C5.0是經(jīng)典的決策樹(shù)模型的算法之一，可生成多分支的決策樹(shù)，目標(biāo)變量為分類變量使用c5.0算法可以生成決策樹(shù)（decisiontree）或者規(guī)則集（rulesets）。C5.0模型根據(jù)能夠帶來(lái)最大信息增益（informationgain）的字段拆分樣本。第一次拆分確定的樣本子集隨后再次拆分，通常是根據(jù)另一個(gè)字段進(jìn)行拆分，這一過(guò)程重復(fù)進(jìn)行直到樣本子集不能再被拆分為止。最后，重新檢驗(yàn)最低層次的拆分，那些對(duì)模型值沒(méi)有顯著貢獻(xiàn)的樣本子集被剔除或者修剪。

第43頁(yè)，共91頁(yè)，2023年，2月20日，星期三C5.0的優(yōu)點(diǎn)優(yōu)點(diǎn)：C5.0模型在面對(duì)數(shù)據(jù)遺漏和輸入字段很多的問(wèn)題時(shí)非常穩(wěn)健。C5.0模型通常不需要很長(zhǎng)的訓(xùn)練次數(shù)進(jìn)行估計(jì)。C5.0模型比一些其他類型的模型易于理解，模型推出的規(guī)則有非常直觀的解釋。C5.0也提供強(qiáng)大的增強(qiáng)技術(shù)以提高分類的精度。C5.0算法選擇分支變量的依據(jù)以信息熵的下降速度作為確定最佳分支變量和分割閥值的依據(jù)。信息熵的下降意味著信息的不確定性下降第44頁(yè)，共91頁(yè)，2023年，2月20日，星期三舉例：在Clementine中應(yīng)用C5.0這里，以學(xué)生參加某次社會(huì)公益活動(dòng)的數(shù)據(jù)（文件名為Students.xls）為例，講解C5.0算法的具體實(shí)現(xiàn)操作。分析目標(biāo)是，研究哪些因素將顯著影響到學(xué)生參與社會(huì)公益活動(dòng)。其中，是否參加為輸出變量，除編號(hào)以外的變量均為輸入變量。第45頁(yè)，共91頁(yè)，2023年，2月20日，星期三數(shù)據(jù)流如下：第46頁(yè)，共91頁(yè)，2023年，2月20日，星期三一、建立模型第一步建立數(shù)據(jù)源，第二步選擇Modeling卡中的C5.0節(jié)點(diǎn)并將其連接到恰當(dāng)位置，鼠標(biāo)右擊該節(jié)點(diǎn)，彈出下面窗口。模型名稱（Modelname）輸出類型（Outputtype）：此處指定希望最終生成的模型是決策樹(shù)還是規(guī)則集。群體字符（Groupsymbolics）。如果選擇該選項(xiàng)，C5.0會(huì)嘗試將所有與輸出字段格式相似的字符值合并。如果沒(méi)有選擇該選項(xiàng)，C5.0會(huì)為用于拆分母節(jié)點(diǎn)的字符字段的每個(gè)值創(chuàng)建一個(gè)子節(jié)點(diǎn)。使用自舉法（Useboosting）：提高其精確率。這種方法按序列建立多重模型。第一個(gè)模型以通常的方式建立。隨后，建立第二個(gè)模型，聚焦于被第一個(gè)模型錯(cuò)誤分類的記錄。以此類推，最后應(yīng)用整個(gè)模型集對(duì)樣本進(jìn)行分類，使用加權(quán)投票過(guò)程把分散的預(yù)測(cè)合并成綜合預(yù)測(cè)。TheNumberoftrials選項(xiàng)允許控制用于助推的模型數(shù)量。第47頁(yè)，共91頁(yè)，2023年，2月20日，星期三交叉驗(yàn)證（Cross－validate）：如果選擇了該選項(xiàng)，C5.0將使用一組基于訓(xùn)練數(shù)據(jù)子集建立的模型，來(lái)估計(jì)基于全部數(shù)據(jù)建立的模型的精確度。如果數(shù)據(jù)集過(guò)小，不能拆分成傳統(tǒng)意義上的訓(xùn)練集和測(cè)試集，這將非常有用。或用于交叉驗(yàn)證的模型數(shù)目。模式（Mode）：對(duì)于簡(jiǎn)單的訓(xùn)練，絕大多數(shù)C5.0參數(shù)是自動(dòng)設(shè)置。高級(jí)訓(xùn)練模式選項(xiàng)允許對(duì)訓(xùn)練參數(shù)更多的直接控制。第48頁(yè)，共91頁(yè)，2023年，2月20日，星期三簡(jiǎn)單模式選項(xiàng)（simple）偏好（Favor）：在accuracy下，C5.0會(huì)生成盡可能精確的決策樹(shù)。在某些情況下，這會(huì)導(dǎo)致過(guò)度擬和。選擇Generality（一般化）項(xiàng)以使用不易受該問(wèn)題影響的算法設(shè)置。期望噪聲百分?jǐn)?shù)（Expectednoise（%））：指定訓(xùn)練集中的噪聲或錯(cuò)誤數(shù)據(jù)期望比率。第49頁(yè)，共91頁(yè)，2023年，2月20日，星期三高級(jí)模式選項(xiàng)修剪純度（pruningseverity）：決定生成決策樹(shù)或規(guī)則集被修剪的程度。提高純度值將獲得更小，更簡(jiǎn)潔的決策樹(shù)。降低純度值將獲得更加精確的決策樹(shù)。子分支最少記錄數(shù)（Minimumrecordsperchildbranch）：子群大小可以用于限制決策樹(shù)任一分支的拆分?jǐn)?shù)。只有當(dāng)兩個(gè)或以上的后序子分支包括來(lái)自訓(xùn)練集的記錄不少于最小記錄數(shù)，決策樹(shù)才會(huì)繼續(xù)拆分。默認(rèn)值為2，提高該值將有助于避免噪聲數(shù)據(jù)的過(guò)度訓(xùn)練。全局修剪（Useglobalpruning）：第一階段：局部修建第二階段：全局修剪排除屬性（Winnowattributes）：如果選擇了該選項(xiàng)，C5.0會(huì)在建立模型前檢驗(yàn)預(yù)測(cè)字段的有用性。被發(fā)現(xiàn)與分析無(wú)關(guān)的預(yù)測(cè)字段將不參與建模過(guò)程。這一選項(xiàng)對(duì)有許多預(yù)測(cè)字段元的模型非常有用，并且有助于避免過(guò)度擬和。第50頁(yè)，共91頁(yè)，2023年，2月20日，星期三圖1指定錯(cuò)誤歸類損失錯(cuò)誤歸類損失允許指定不同類型預(yù)測(cè)錯(cuò)誤之間的相對(duì)重要性。錯(cuò)誤歸類損失矩陣顯示預(yù)測(cè)類和實(shí)際類每一可能組合的損失。所有的錯(cuò)誤歸類損失都預(yù)設(shè)設(shè)置為1.0。要輸入自定義損失值，選擇Usemisclassificationcosts，然后把自定義值輸入到損失矩陣中。第51頁(yè)，共91頁(yè)，2023年，2月20日，星期三具體設(shè)置第52頁(yè)，共91頁(yè)，2023年，2月20日，星期三執(zhí)行結(jié)果第53頁(yè)，共91頁(yè)，2023年，2月20日，星期三二、預(yù)測(cè)結(jié)果為觀測(cè)C5.0對(duì)每個(gè)樣本的預(yù)測(cè)結(jié)果，可在流管理器的Models卡中，鼠標(biāo)右擊C5.0模型結(jié)果，選擇彈出菜單中的AddToStream，并將模型結(jié)果連接到數(shù)據(jù)流中，然后連接Table節(jié)點(diǎn)查看預(yù)測(cè)結(jié)果，如下圖所示：第54頁(yè)，共91頁(yè)，2023年，2月20日，星期三三、C5.0模型評(píng)價(jià)第55頁(yè)，共91頁(yè)，2023年，2月20日，星期三3.3CART分類和回歸樹(shù)（ClassificationandRegressionTrees，CART,在Clementine中簡(jiǎn)寫為C&RT）CART算法中的每一次分裂把數(shù)據(jù)分為兩個(gè)子集，每個(gè)子集中的樣本比被劃分之前具有更好的一致性。它是一個(gè)遞歸的過(guò)程，也就是說(shuō)，這些子集還會(huì)被繼續(xù)劃分，這個(gè)過(guò)程不斷重復(fù)，直到滿足終止準(zhǔn)則，然后通過(guò)修剪和評(píng)估，得到一棵最優(yōu)的決策樹(shù)。第56頁(yè)，共91頁(yè)，2023年，2月20日，星期三三個(gè)步驟生成最大樹(shù)生成一棵充分生長(zhǎng)的最大樹(shù)樹(shù)的修剪根據(jù)修剪算法對(duì)最大樹(shù)進(jìn)行修剪，生成由許多子樹(shù)組成的子樹(shù)序列子樹(shù)評(píng)估從子樹(shù)序列中選擇一棵最優(yōu)的子樹(shù)作為最后的結(jié)果。

第57頁(yè)，共91頁(yè)，2023年，2月20日，星期三3.3.1生成最大樹(shù)標(biāo)準(zhǔn)問(wèn)題集

就某個(gè)給定的屬性來(lái)說(shuō)，由于屬性的取值可能有很多個(gè)，所以按照這個(gè)屬性來(lái)分裂數(shù)據(jù)集的方式也有很多種，屬性的標(biāo)準(zhǔn)問(wèn)題集就是所有候選分支方案的集合。連續(xù)屬性的標(biāo)準(zhǔn)問(wèn)題集離散屬性的標(biāo)準(zhǔn)問(wèn)題集第58頁(yè)，共91頁(yè)，2023年，2月20日，星期三雜度

在ID3算法中，用“熵”來(lái)度量數(shù)據(jù)集隨機(jī)性的程度。在CART中我們把這種隨機(jī)性的程度稱為“雜度”（impurity，也稱為“不純度”），并且用“吉尼”(gini)指標(biāo)來(lái)衡量它。第59頁(yè)，共91頁(yè)，2023年，2月20日，星期三吉尼指標(biāo)設(shè)t是決策樹(shù)上的某個(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)這樣來(lái)計(jì)算：第60頁(yè)，共91頁(yè)，2023年，2月20日，星期三雜度削減

由于CART算法生成的是一棵二叉樹(shù)，所以對(duì)于節(jié)點(diǎn)t來(lái)說(shuō)，分裂后將產(chǎn)生兩個(gè)子節(jié)點(diǎn)tL和tR，設(shè)這兩個(gè)子節(jié)點(diǎn)的雜度分別為gini(tL)和gini(tR)，那么，在此次分裂過(guò)程中的雜度削減為：第61頁(yè)，共91頁(yè)，2023年，2月20日，星期三計(jì)算雜度削減第62頁(yè)，共91頁(yè)，2023年，2月20日，星期三停止準(zhǔn)則

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

第63頁(yè)，共91頁(yè)，2023年，2月20日，星期三樹(shù)的修剪葉子節(jié)點(diǎn)過(guò)多，則樹(shù)的復(fù)雜度高。葉子節(jié)點(diǎn)過(guò)少，則誤分類損失大。代價(jià)復(fù)雜度

第64頁(yè)，共91頁(yè)，2023年，2月20日，星期三樹(shù)的修剪過(guò)程令α=0，從T1=T(0)開(kāi)始，這里的T(0)就是最大樹(shù)Tmax；逐漸增大α

，直到某個(gè)節(jié)點(diǎn)使得成立，將它的分支刪除，得到T2；重復(fù)上一步驟，直到被修剪到只有一個(gè)根節(jié)點(diǎn)，從而得到一個(gè)樹(shù)的序列T1,T2,…,Tk。第65頁(yè)，共91頁(yè)，2023年，2月20日，星期三子樹(shù)評(píng)估要找到一棵分類準(zhǔn)確性最好、同時(shí)節(jié)點(diǎn)數(shù)量盡量少的樹(shù)計(jì)算每一棵子樹(shù)的誤分類損失：第66頁(yè)，共91頁(yè)，2023年，2月20日，星期三3.3.4在Clementine中應(yīng)用CART這里，以電信客戶數(shù)據(jù)（文件名為Telephone.sav）為例，討論分類回歸樹(shù)的具體操作以及如何通過(guò)交互操作控制決策樹(shù)的生長(zhǎng)和剪枝過(guò)程。分析目標(biāo)是，找到影響客戶流失的重要因素，以實(shí)現(xiàn)客戶流失的事前控制。第67頁(yè)，共91頁(yè)，2023年，2月20日，星期三數(shù)據(jù)流第68頁(yè)，共91頁(yè)，2023年，2月20日，星期三建模第69頁(yè)，共91頁(yè)，2023年，2月20日，星期三分類結(jié)果第70頁(yè)，共91頁(yè)，2023年，2月20日，星期三

分析結(jié)論1在流管理器的Models卡中，鼠標(biāo)右擊所得到的CART模型，選擇彈出菜單中的Brower項(xiàng)瀏覽默寫結(jié)果并選擇Generate菜單下的FilterNode項(xiàng)。于是，會(huì)在數(shù)據(jù)流編輯區(qū)自動(dòng)生成一個(gè)Filter節(jié)點(diǎn)，將它連到數(shù)據(jù)流的恰當(dāng)位置，可看到下圖結(jié)果：從圖中可知，只有性別對(duì)客戶流失的影響不大，其他因素都有影響。應(yīng)該注意到，這棵決策樹(shù)是代價(jià)復(fù)雜度最小的，但針對(duì)本例的分析目標(biāo)，可適當(dāng)減少?gòu)?fù)雜性、降低精度，以找到更主要的影響因素。第71頁(yè)，共91頁(yè)，2023年，2月20日，星期三Chi-SquareAutomaticInteractionDetectionCHAID提供了一種在多個(gè)自變量中自動(dòng)搜索能產(chǎn)生最大差異的變量方案。不同于C＆R樹(shù)和QUEST節(jié)點(diǎn)，CHAID分析可以生成非二叉樹(shù)，即有些分割有兩個(gè)以上的分支。CHAID模型需要一個(gè)單一的目標(biāo)和一個(gè)或多個(gè)輸入字段。CHAID分析，是一種用卡方統(tǒng)計(jì)，以確定最佳的分割，建立決策樹(shù)的分類方法。3.4CHAID算法（卡方自動(dòng)交叉檢驗(yàn)）第72頁(yè)，共91頁(yè)，2023年，2月20日，星期三CHAID方法CHAID根據(jù)細(xì)分變量區(qū)分群體差異的顯著性程度（卡方值）的大小順序，將消費(fèi)者分為不同的細(xì)分群體，最終的細(xì)分群體是由多個(gè)變量屬性共同描述的，因此屬于多變量分析。在形式上，CHAID非常直觀，它輸出的是一個(gè)樹(shù)狀的圖形。

它以因變量為根結(jié)點(diǎn)，對(duì)每個(gè)自變量（只能是分類或有序變量，也就是離散性的，如果是連續(xù)變量，如年齡，收入要定義成分類或有序變量）進(jìn)行分類，計(jì)算分類的卡方值(Chi-Square-Test)。如果幾個(gè)變量的分類均顯著，則比較這些分類的顯著程度（P值的大?。?，然后選擇最顯著的分類法作為子節(jié)點(diǎn)。第73頁(yè)，共91頁(yè)，2023年，2月20日，星期三CHAID過(guò)程

建立細(xì)分模型，根據(jù)卡方值最顯著的細(xì)分變量將群體分出兩個(gè)或多個(gè)群體，對(duì)于這些群體再根據(jù)其它的卡方值相對(duì)最顯著的細(xì)分變量繼續(xù)分出子群體，直到?jīng)]有統(tǒng)計(jì)意義上顯著的細(xì)分變量可以將這些子群體再繼續(xù)分開(kāi)為止。第74頁(yè)，共91頁(yè)，2023年，2月20日，星期三CHAID的適用范圍

當(dāng)預(yù)測(cè)變量是分類變量時(shí)，CHAID方法最適宜。對(duì)于連續(xù)型變量，CHAID在缺省狀態(tài)下將連續(xù)變量自動(dòng)分為10段處理，但是可能有遺漏。第75頁(yè)，共91頁(yè)，2023年，2月20日，星期三CHAID模塊的優(yōu)點(diǎn)-不像CART和QUEST模塊，CHAID可產(chǎn)生多分枝的決策樹(shù)-目標(biāo)變量可以定距或定類的-從統(tǒng)計(jì)顯著性角度確定分支變量和分隔值，進(jìn)而優(yōu)化樹(shù)的分枝過(guò)程-CHAID是建立在因果關(guān)系的探討中的，依據(jù)目標(biāo)變量實(shí)現(xiàn)對(duì)輸入變量眾多水平的劃分第76頁(yè)，共91頁(yè)，2023年，2月20日，星期三實(shí)例：以電信客戶數(shù)據(jù)Telephone.sav為例,討論CHAID具體操作。第77頁(yè)，共91頁(yè)，2023年，2月20日，星期三Clementine決策樹(shù)算法

C&RT、CHAID、C5.0的區(qū)別第78頁(yè)，共91頁(yè)，2023年，2月20日，星期三決策樹(shù)(decisiontree)