數(shù)據(jù)管理決策樹建模第1頁，共154頁，2023年，2月20日，星期五§4.1決策樹介紹 分類是數(shù)據(jù)挖掘的一個重要課題,它的目的是：

構(gòu)造一個分類函數(shù)或分類模型(也常稱為分類器),該模型能把數(shù)據(jù)庫中的數(shù)據(jù)項映射到給定類別中的某一個。 數(shù)據(jù)分類的過程一般來說主要包含兩個步驟 第一步,建立一個描述已知數(shù)據(jù)集類別或概念的模型 第二步,利用所獲得的模型進行分類操作第2頁，共154頁，2023年，2月20日，星期五§4.1決策樹介紹鏈接 分類是數(shù)據(jù)挖掘的一個重要課題,它的目的是：

構(gòu)造一個分類函數(shù)或分類模型(也常稱為分類器),該模型能把數(shù)據(jù)庫中的數(shù)據(jù)項映射到給定類別中的某一個。 數(shù)據(jù)分類的過程一般來說主要包含兩個步驟 第一步,建立一個描述已知數(shù)據(jù)集類別或概念的模型 第二步,利用所獲得的模型進行分類操作第3頁，共154頁，2023年，2月20日，星期五§4.1 決策樹介紹-2第一步,建立一個描述已知數(shù)據(jù)集類別或概念的模型 該模型是通過對數(shù)據(jù)庫中各數(shù)據(jù)進行內(nèi)容的分析而獲得的。 分類學(xué)習(xí)方法所使用的數(shù)據(jù)集稱為訓(xùn)練樣本集合，每一數(shù)據(jù)行都屬于一個確定的數(shù)據(jù)類別，其類別值是由一個屬性來描述的(被稱為類別標記屬性)。 因此分類學(xué)習(xí)又可稱為監(jiān)督學(xué)習(xí)，它是在已知訓(xùn)練樣本類別情況下，通過學(xué)習(xí)建立相應(yīng)模型。而無監(jiān)督學(xué)習(xí)則是在訓(xùn)練樣本的類別與類別個數(shù)均未知的情況下進行的，如聚類分析。第4頁，共154頁，2023年，2月20日，星期五§4.1 決策樹介紹-2第二步,利用所獲得的模型進行分類操作 首先對模型分類準確率進行估計。

Holdout方法是一種簡單的估計方法，它利用一組帶有類別的樣本(稱為測試樣本)對由訓(xùn)練樣本所構(gòu)造出模型的

準確性進行測試，通常測試樣本是隨機獲得的，且與

訓(xùn)練樣本獨立同分布。 模型的準確性可以通過由該模型所正確分類的測試樣本個數(shù)所占總測試樣本的比例得到。即對于每一個測試樣本，比較其已知的類別與學(xué)習(xí)所獲模型的預(yù)測類別。第5頁，共154頁，2023年，2月20日，星期五§4.1 決策樹介紹-2 若模型的準確率是通過對訓(xùn)練數(shù)據(jù)集本身的測試所獲得，由于學(xué)習(xí)模型傾向于過分逼近訓(xùn)練效據(jù)，從而造成對模型測試準確率的估計過于樂觀。因此需要使用一個測試數(shù)據(jù)集來對學(xué)習(xí)所獲模型的準確率進行測試工作。 如果一個學(xué)習(xí)所獲模型的準確率經(jīng)測試被認為是可以

接受的，那么就可以使用這一模型對未來數(shù)據(jù)行或?qū)ο?/p>

(其類別未知)進行分類，即利用學(xué)習(xí)所獲得的模型

進行預(yù)測，對未知類別的數(shù)據(jù)行或?qū)ο笈袛嗥?/p>

類別(屬性)取值。第6頁，共154頁，2023年，2月20日，星期五由訓(xùn)練數(shù)據(jù)產(chǎn)生分類規(guī)則第7頁，共154頁，2023年，2月20日，星期五由分類規(guī)則對新的樣本數(shù)據(jù)進行分類第8頁，共154頁，2023年，2月20日，星期五§4.1 決策樹介紹-2常用的分類預(yù)測算法：決策樹歸納分類貝葉斯分類基于規(guī)則的分類用后向傳播分類遺傳算法、粗糙集方法、模糊集方法第9頁，共154頁，2023年，2月20日，星期五§4.1 決策樹介紹-24.1.1決策樹的基本知識決策樹方法最早產(chǎn)生于20世紀60年代，是由Hunt等人研究人類概念建模時建立的學(xué)習(xí)系統(tǒng)CLS(conceptlearningsystem)。到了70年代末，

J.RossQuinlan提出ID3算法，引進信息論中的有關(guān)思想，提出用信息

增益(informationgain)作為特征判別能力的度量，來選擇屬性作為決策樹的節(jié)點，并將建樹的方法嵌在一個迭代的程序之中。當(dāng)時他的主要目的在于減少樹的深度，卻忽略了葉子數(shù)目的研究。1975年和1984年，分別有人提出了CHAID和CART算法。1986年，J.C.Schlinner提出ID4算法。1988年，P.E.Utgoff提出ID5R算法。1993年，Quinlan本人以ID3算法為基礎(chǔ)研究出C4.5算法。新算法在對預(yù)測變量的缺失值處理、剪枝技術(shù)、派生規(guī)則等方面作了較大的改進，C5.0是C4.5的商業(yè)改進版。第10頁，共154頁，2023年，2月20日，星期五4.1.1決策樹的基本知識 決策樹技術(shù)發(fā)現(xiàn)數(shù)據(jù)模式和規(guī)則的核心是歸納算法。 歸納是從特殊到一般的過程。 歸納推理從若干個事實表征出的特征、特性或?qū)傩灾?通過比較、總結(jié)、概括而得出一個規(guī)律性的結(jié)論。 歸納學(xué)習(xí)的過程就是尋找一般化描述(歸納斷言)的過程。這種一般化描述能夠解釋給定的輸入數(shù)據(jù)，并可以用來預(yù)測新的數(shù)據(jù)。 歸納學(xué)習(xí)由于依賴于經(jīng)驗數(shù)據(jù)，因此又稱作經(jīng)驗學(xué)習(xí)。第11頁，共154頁，2023年，2月20日，星期五4.1.1決策樹的基本知識-2 歸納學(xué)習(xí)存在一個基本假定:

任一模型如果能在足夠大的訓(xùn)練樣本集中很好地逼近

目標函數(shù)，則它也能在未見樣本中很好地逼近目標函數(shù)。

這個假定是歸納學(xué)習(xí)有效性的前提條件。 歸納過程就是在描述空間中進行搜索的過程。第12頁，共154頁，2023年，2月20日，星期五4.1.1決策樹的基本知識-2 歸納可以分為自下而上、自上而下和雙向搜索三種方式 自下而上法一次處理一個輸入對象，將描述逐步

一般化，直到最終的一般化描述。 自上而下法則對可能的一般化描述集進行搜索，試圖

找到一些滿足一定要求的最優(yōu)的描述。 雙向搜索方式則是這兩者的結(jié)合。第13頁，共154頁，2023年，2月20日，星期五4.1.1決策樹的基本知識-2 決策樹學(xué)習(xí)是應(yīng)用最廣的歸納推理算法之一。它是一種逼近離散函數(shù)值的方法，分類精度高，操作簡單，并且對噪聲數(shù)據(jù)有很好的穩(wěn)健性，因而成為比較實用且比較流行的數(shù)據(jù)挖掘算法。 它的最大優(yōu)點是，在學(xué)習(xí)過程中不需要使用者了解很多背景知識，只要訓(xùn)練樣本集能夠用“屬性-值”的方式表達

出來就能使用決策樹學(xué)習(xí)算法來分類。第14頁，共154頁，2023年，2月20日，星期五4.1.1決策樹的基本知識-2 該方法先根據(jù)訓(xùn)練子集(又稱為窗口)形成決策樹，如果該樹不能對所有對象給出正確的分類，那么選擇一些例外

加入到窗口中，重復(fù)該過程一直到形成正確的決策集。 最終結(jié)果是“一棵樹”，其葉節(jié)點是類名，中間節(jié)點是

帶有分枝的屬性，該分枝對應(yīng)該屬性的某一可能值。第15頁，共154頁，2023年，2月20日，星期五4.1.1決策樹的基本知識-2 決策樹通常有兩大類型，分別為分類決策樹和

回歸決策樹。 分類決策樹用來實現(xiàn)對定類或定序目標變量的分類，

回歸決策樹則完成對定距目標變量取值的預(yù)測。 根據(jù)決策樹各種不同的屬性，可分為以下幾類:

決策樹內(nèi)節(jié)點的測試屬性可能是單變量的，即每個內(nèi)節(jié)點只包含一個

屬性;也可能是多變量的，既存在包含多個屬性的內(nèi)節(jié)點。測試屬性的不同屬性值的個數(shù)，可能使得每個內(nèi)節(jié)點有兩個或多個

分枝。如果一棵決策樹每個內(nèi)節(jié)點只有兩個分枝則稱之為二叉

決策樹，如由CART算法生成的決策樹。每個屬性可能是值類型(連續(xù)值)，也可能是枚舉類型(離散值)。分類結(jié)果既可能是兩類也有可能是多類，如果二叉決策樹的結(jié)果只有

兩類，則稱之為布爾決策樹。第16頁，共154頁，2023年，2月20日，星期五4.1.1決策樹的基本知識-2決策樹方法的(相對)優(yōu)點:可以生成可理解的規(guī)則

數(shù)據(jù)挖掘產(chǎn)生的模式的可理解度是判別數(shù)據(jù)挖掘算法的主要指標之一，相比于一些數(shù)據(jù)挖掘算法，決策樹算法產(chǎn)生的規(guī)則比較容易理解，并且決策樹模型的建立過程也很直觀。計算量較小。可以處理連續(xù)和集合屬性。決策樹的輸出包含屬性的排序

生成決策樹時，按照最大信息增益選擇測試屬性，

因此，在決策樹中可以大致判斷屬性的相對重要性。第17頁，共154頁，2023年，2月20日，星期五4.1.1決策樹的基本知識-2決策樹方法的缺點:對于具有連續(xù)值的屬性預(yù)測比較困難。-對于順序相關(guān)的數(shù)據(jù)，需要很多預(yù)處理的工作。當(dāng)類別太多時，通常會增加誤差分枝間的拆分不夠平滑，進行拆分時，不考慮其對將來拆分的影響。缺值數(shù)據(jù)處理問題:因為決策樹進行分類預(yù)測時，完全基于數(shù)據(jù)的測試屬性，所以對于測試屬性缺失的數(shù)據(jù)，決策樹將無法處理。通常僅根據(jù)單個屬性來分類:決策樹方法根據(jù)單個屬性對數(shù)據(jù)進行

分類，而在實際的分類系統(tǒng)中，類的劃分不僅僅與單個屬性有關(guān)，往往與一個屬性集有關(guān)。因此，將決策樹算法推廣到考慮多屬性

是一個有待研究的課題。第18頁，共154頁，2023年，2月20日，星期五4.1.1決策樹的基本知識-2決策樹學(xué)習(xí)算法適用的問題:樣本可以用“屬性-值”的方式來描述目標函數(shù)的輸出值為離散值訓(xùn)練數(shù)據(jù)中允許包含有錯誤:

樣本的分類錯誤或?qū)傩灾靛e誤都允許訓(xùn)練數(shù)據(jù)中有樣本屬性值缺失第19頁，共154頁，2023年，2月20日，星期五§4.1 決策樹介紹-24.1.2決策樹的應(yīng)用和發(fā)展趨勢 決策樹由于結(jié)構(gòu)簡單、效率高等優(yōu)點而獲得了廣泛的應(yīng)用。在國外，決策樹在商業(yè)、工業(yè)、天文、醫(yī)學(xué)、風(fēng)險分析、社會科學(xué)和分類學(xué)等領(lǐng)域的應(yīng)用已經(jīng)取得了很好的經(jīng)濟和社會效益。

國內(nèi)目前有關(guān)決策樹的研究多是圍繞算法的改進以及決策樹在商業(yè)、工業(yè)等領(lǐng)域的運用。在商業(yè)領(lǐng)域，決策樹方法所能解決的典型商業(yè)問題有:客戶關(guān)系

管理、數(shù)據(jù)庫營銷、客戶群體劃分、交叉銷售等市場分析

行為，以及客戶流失分析、客戶信用計分及欺詐發(fā)現(xiàn)，等等。在工業(yè)領(lǐng)域，決策樹可以用于故障診斷、工業(yè)生產(chǎn)過程控制等。在醫(yī)學(xué)領(lǐng)域，決策樹方法可用于疾病診斷治疔、

基因與高分子序列分析、醫(yī)院信息系統(tǒng)挖掘及醫(yī)療政策分析等。第20頁，共154頁，2023年，2月20日，星期五決策樹方法的需求和發(fā)展：1.決策樹的精度2.決策樹的規(guī)模3.處理大規(guī)模數(shù)據(jù)集4.增量式算法5.與其他方法的結(jié)合6.知識的表示第21頁，共154頁，2023年，2月20日，星期五§4.2樹的建模過程首頁決策樹總體思路第22頁，共154頁，2023年，2月20日，星期五§4.2 樹的建模過程—總體步驟決策樹的構(gòu)造基本可以分為如下兩步:決策樹的生成 決策樹的生成是指由訓(xùn)練樣本數(shù)據(jù)集生成決策樹的過程。一般情況下，訓(xùn)練樣本數(shù)據(jù)集是根據(jù)實際需要由實際的歷史數(shù)據(jù)生成的、有一定綜合程度的、用于數(shù)據(jù)分析處理的

數(shù)據(jù)集。決策樹的剪枝 決策樹剪枝是對上一階段所生成的決策樹進行檢驗、

校正和修正的過程，主要是采用新的樣本數(shù)據(jù)集(稱為

測試數(shù)據(jù)集)中的數(shù)據(jù)檢驗決策樹生成過程中產(chǎn)生的初步

規(guī)則，將那些影響預(yù)測準確性的分枝剪除。一般情況下，根據(jù)測試數(shù)據(jù)集中的每一元組對生成的規(guī)則進行預(yù)測準確性的檢驗，如果預(yù)測準確性過低，則將該分枝剪除。第23頁，共154頁，2023年，2月20日，星期五§4.2 樹的建模過程—總體步驟決策樹的構(gòu)造基本可以分為如下兩步:決策樹的生成 決策樹的生成是指由訓(xùn)練樣本數(shù)據(jù)集生成決策樹的過程。一般情況下，訓(xùn)練樣本數(shù)據(jù)集是根據(jù)實際需要由實際的歷史數(shù)據(jù)生成的、有一定綜合程度的、用于數(shù)據(jù)分析處理的

數(shù)據(jù)集。決策樹的剪枝 決策樹剪枝是對上一階段所生成的決策樹進行檢驗、

校正和修正的過程，主要是采用新的樣本數(shù)據(jù)集(稱為

測試數(shù)據(jù)集)中的數(shù)據(jù)檢驗決策樹生成過程中產(chǎn)生的初步

規(guī)則，將那些影響預(yù)測準確性的分枝剪除。一般情況下，根據(jù)測試數(shù)據(jù)集中的每一元組對生成的規(guī)則進行預(yù)測準確性的檢驗，如果預(yù)測準確性過低，則將該分枝剪除。第24頁，共154頁，2023年，2月20日，星期五§4.2 樹的建模過程 決策樹算法通過構(gòu)造決策樹來發(fā)現(xiàn)數(shù)據(jù)中蘊涵的分類規(guī)則，包含許多種不同的算法，主要可以分為三類:(1)基于統(tǒng)計學(xué)理論的方法，以CART為代表，在這類算法中，對于非終端節(jié)點來說，有兩個分枝

;(2)基于信息理論的方法，以ID3算法為代表，此類算法中，非終端的節(jié)點的分枝由樣本類別個數(shù)決定

;(3)以AID，CHAD為代表的算法，在此類算法中，非終端節(jié)點的分枝數(shù)在2至樣本類別個數(shù)范圍內(nèi)分布。這些算法在分類中應(yīng)用的過程與思想基本上是一致的。如何構(gòu)造精度高、規(guī)模小的決策樹是決策樹算法的核心內(nèi)容第25頁，共154頁，2023年，2月20日，星期五§4.2 樹的建模過程4.2.1數(shù)據(jù)要求(數(shù)據(jù)準備)

在進行分類和預(yù)測挖掘之前，首先必須準備好有關(guān)挖掘數(shù)據(jù)。一般需要對數(shù)據(jù)進行以下預(yù)處理，以幫助提高分類和預(yù)測過程的準確性、有效性和可伸縮性。主要的工作包括：數(shù)據(jù)清洗相關(guān)分析數(shù)據(jù)轉(zhuǎn)換第26頁，共154頁，2023年，2月20日，星期五4.2.1數(shù)據(jù)準備數(shù)據(jù)清洗 這一數(shù)據(jù)預(yù)處理步驟，主要是幫助除去數(shù)據(jù)中的噪聲，并妥善解決缺失數(shù)據(jù)問題，盡管大多數(shù)分類算法都包含一些處理噪聲和缺失數(shù)據(jù)的方法，但這一預(yù)處理步驟可以有效

減少學(xué)習(xí)過程可能出現(xiàn)相互矛盾情況的問題。第27頁，共154頁，2023年，2月20日，星期五4.2.1數(shù)據(jù)準備相關(guān)分析 由于數(shù)據(jù)集中的許多屬性與挖掘任務(wù)本身可能是無關(guān)的，例如記錄銀行貸款申請(單)填寫時的星期數(shù)(屬性)，就可能與申請成功與否的描述無關(guān)。此外，有些屬性也可能是冗余的。因此需要對數(shù)據(jù)進行相關(guān)分析，以使在學(xué)習(xí)階段之前就消除無關(guān)或冗余屬性。在機器學(xué)習(xí)中，這一相關(guān)分析步驟被稱為屬性選擇(featureselection)，包含與挖掘任務(wù)無關(guān)的屬性可能會減緩甚至誤導(dǎo)整個學(xué)習(xí)過程。在理想情況下，相關(guān)分析所花費的時間加上對削減后屬性(子)集進行歸納

學(xué)習(xí)所花費的時間之和，應(yīng)小于從初始屬性集進行學(xué)習(xí)所花費的時間，從而達到幫助改善分類效率和可擴展性的目的。第28頁，共154頁，2023年，2月20日，星期五4.2.1數(shù)據(jù)準備數(shù)據(jù)轉(zhuǎn)換 利用概念層次樹，數(shù)據(jù)能夠被泛化到更高的層次。概念層次樹對連續(xù)數(shù)值的轉(zhuǎn)換非常有效。例如，屬性“收入”的數(shù)值就可以被泛化為若干離散區(qū)間，諸如低、中和高。類似地，像“街道”這樣的屬性也可以被泛化到更高的抽象層次，如泛化到城市。由于泛化操作壓縮了原來的數(shù)據(jù)集，從而可以幫助有效減少學(xué)習(xí)過程所涉及的輸入輸出操作。此外，初始數(shù)據(jù)可能還需要規(guī)格化，特別是在利用距離計算方法實施各種學(xué)習(xí)方法時，如在基于示例學(xué)習(xí)方法中，規(guī)格化處理是不可或缺的重要處理操作。。第29頁，共154頁，2023年，2月20日，星期五§4.2 樹的建模過程4.2.2樹的生長 決策樹算法是一種常用的數(shù)據(jù)挖掘算法，它是從

機器學(xué)習(xí)領(lǐng)域中逐漸發(fā)展起來的一種分類函數(shù)逼近方法。

決策樹學(xué)習(xí)的基本算法是貪心算法，采用自上而下的遞歸

方式構(gòu)造決策樹。Hunt等人于1966年提出的概念學(xué)習(xí)系統(tǒng)

(conceptlearningsystem，CLS)是最早的決策樹算法，以后的許多決策樹算法都是對CLS算法的改進或由CLS衍生而來。目前，利用決策樹進行數(shù)據(jù)分類的方法已經(jīng)被深入研究，并且形成了許多決策樹算法。第30頁，共154頁，2023年，2月20日，星期五§4.2 樹的建模過程 決策樹算法的分類模型是一棵有向無環(huán)樹， 下面將以二叉樹為例說明基本的決策樹算法。 決策樹的每個節(jié)點有0或2個子節(jié)點，除了根節(jié)點以外，每個節(jié)點有且僅有一個父節(jié)點。如果節(jié)點沒有子節(jié)點，則稱它為葉節(jié)點，否則稱為內(nèi)部節(jié)點。第31頁，共154頁，2023年，2月20日，星期五§4.2 樹的建模過程 每個葉節(jié)點對應(yīng)一個類標號，使用決策樹對未知樣本

分類的類標號的值即為葉節(jié)點的值。每個內(nèi)部節(jié)點都對應(yīng)

一個分枝方案，它包括用于節(jié)點分裂的屬性A和分枝的

判斷規(guī)則q。 訓(xùn)練樣本的屬性分為數(shù)值屬性和分類屬性，數(shù)值屬性的取值范圍是一個連續(xù)的區(qū)間，比如實數(shù)集R;而分類屬性的取值范圍則是離散值的集合S(A)，比如性別屬性的取值范圍就是集合{男，女}。 如果屬性A是數(shù)值屬性，那么q的形式是A≤v，其中v是屬于A的取值范圍的一個常量;

如果A是分類屬性，那么q的形式是A∈S’,其中S’是S(A)的子集。第32頁，共154頁，2023年，2月20日，星期五4.2.2樹的生長 決策樹是“一棵樹”，它的根節(jié)點是整個數(shù)據(jù)集合空間，每個分節(jié)點是對一個單一變量(屬性)的測試，該測試將數(shù)據(jù)集合空間分割成兩個或更多塊。每個葉節(jié)點是屬于單一類別的記錄。 首先，通過訓(xùn)練集生成決策樹，再通過測試集對決策樹進行修剪。

決策樹的功能是預(yù)測一個新的記錄屬于哪一類。第33頁，共154頁，2023年，2月20日，星期五4.2.2樹的生長 通常,通過自上而下遞歸分割的過程來構(gòu)建決策樹,分為三個步驟:(1)尋找初始分裂。整個訓(xùn)練集作為產(chǎn)生決策樹的集合，

訓(xùn)練集每個記錄必須是已經(jīng)分好類的。決定哪個屬性(field)域作為目前最好的分類指標。一般的做法是窮盡所有的屬性域，對每個屬性域分裂的好壞做出量化，計算出最好的一個分裂。(2)樹增長到一棵完整的樹。重復(fù)第一步，直至每個葉節(jié)點

內(nèi)的記錄都屬于同一類，或達到其他停止準則。(3)數(shù)據(jù)的修剪。去掉一些可能是噪音或者異常的數(shù)據(jù)或節(jié)點第34頁，共154頁，2023年，2月20日，星期五4.2.2樹的生長其通用的基本算法(貪心算法)為:

以自上而下分而治之的方法，開始時，所有的數(shù)據(jù)都在根節(jié)點;屬性都是種類字段(如果是連續(xù)的，將其離散化);所有記錄用所選屬性遞歸地進行分割;屬性的選擇是基于一個啟發(fā)式規(guī)則或者一個統(tǒng)計的度量(如informationgain)。 停止分割的條件:一個節(jié)點上的數(shù)據(jù)都是屬于同一個

類別或沒有屬性可以再用于對數(shù)據(jù)進行分割。第35頁，共154頁，2023年，2月20日，星期五4.2.2樹的生長—算法的形式描述ProcedureBuildTree(S){

用數(shù)據(jù)集S初始化根節(jié)點R

用根節(jié)點R初始化隊列Q Whi1eQisnotEmpty,do{

取出隊列Q中的第一個節(jié)點N ifN不純(impure){ for每一個屬性A

估計該節(jié)點在A上的信息增益 選出最佳的屬性,將N分裂為N1,N2 } } }第36頁，共154頁，2023年，2月20日，星期五樹的生長—CLS算法示例第37頁，共154頁，2023年，2月20日，星期五樹的生長—CLS算法示例-2分類目標：設(shè)對上述數(shù)據(jù)按人種進行分類， 人員屬性包括眼睛顏色、頭發(fā)顏色和所屬人種，記為:

A={眼睛顏色，頭發(fā)顏色，所屬人種}，其中A3={所屬人種}為分類結(jié)果屬性，分類屬性值集，即分類結(jié)果R={黃種人，白種人，混血人種}，測試屬性為{眼睛顏色，頭發(fā)顏色}。第38頁，共154頁，2023年，2月20日，星期五樹的生長—CLS算法示例-2 假設(shè)首先選擇{眼睛顏色}作為測試屬性，因為眼睛顏色屬性值VA1={黑色，藍色，灰色}，所以從該節(jié)點引出三個分枝，如下圖所示。 這三個分枝將樣本集分成三個子集{1，6}，{2，4，8}和{3，5，7}。因為這三個子集中的元素都不屬于同一個結(jié)果類，因此它們都不是葉節(jié)點，需要繼續(xù)劃分，即需要添加新的測試節(jié)點。第39頁，共154頁，2023年，2月20日，星期五樹的生長—CLS算法示例-2 因此，對這三個子集繼續(xù)添加新的測試節(jié)點

{頭發(fā)顏色}，因為頭發(fā)顏色的屬性值VA2={黑色，金色，紅色}，因此從子集中可以引出新的三個分枝，如下圖示。第40頁，共154頁，2023年，2月20日，星期五§4.2 樹的建模過程-34.2.3有效性和風(fēng)險性 基本的決策樹算法沒有考慮噪聲,生成的決策樹完全與訓(xùn)練例子擬合。 這樣雖然能降低算法的時間復(fù)雜度，但也使算法在

較深層次的樣本劃分中，專注于訓(xùn)練樣本集某個子集的統(tǒng)計信息，而忽視各類樣本的整體分布情況，造成了對噪聲敏感。 所以，雖然一棵完整的決策樹能夠非常準確地反映

訓(xùn)練樣本集中數(shù)據(jù)的特征，但因失去了一般代表性而無法

對新數(shù)據(jù)進行準確的分類或預(yù)測，出現(xiàn)了過匹配現(xiàn)象。第41頁，共154頁，2023年，2月20日，星期五4.2.3有效性和風(fēng)險性

過匹配指的是模型由于過度訓(xùn)練，導(dǎo)致其記住的不是訓(xùn)練數(shù)據(jù)的一般特性，而是訓(xùn)練集的局部特性。 當(dāng)將這個模型應(yīng)用到新的測試集上時就導(dǎo)致預(yù)測結(jié)果的不準確。 因此，一個完整的決策樹構(gòu)造過程將包含決策樹的創(chuàng)建和決策樹的剪枝這兩方面。 剪枝是一種克服噪聲的技術(shù)，用于解決過匹配問題，

同時它也能使樹得到簡化而變得更容易理解。第42頁，共154頁，2023年，2月20日，星期五4.2.3有效性和風(fēng)險性剪枝的原則包括:奧卡姆剃刀原則——“如無必要，勿增實體”。即在與

觀察相容的情況下，應(yīng)當(dāng)選擇最簡單的一棵決策樹。決策樹越小就越容易理解，其存儲與傳輸?shù)拇鷥r也就

越小。決策樹越復(fù)雜，節(jié)點越多，每個節(jié)點包含的訓(xùn)練樣本個數(shù)越少，則支持每個節(jié)點的假設(shè)的樣本個數(shù)就越少，可能導(dǎo)致決策樹在測試集上的分類錯誤率就會增大。

但決策樹過小也會導(dǎo)致錯誤率較大。因此，

需要在樹的大小與正確率之間尋找均衡點第43頁，共154頁，2023年，2月20日，星期五4.2.3有效性和風(fēng)險性 常用的剪枝技術(shù)有預(yù)剪枝(pre-pruning)和后剪枝(post-pruning)兩種。

預(yù)剪枝：在構(gòu)造決策樹時，決定不再對不純的訓(xùn)練子集

進行進一步劃分的剪枝方法

預(yù)剪枝技術(shù)限制了決策樹的過度生長

如CHAID,ID3系列的ID3、C4.5算法等

后剪枝：在樹完全生成之后的剪枝策略

如CART算法等 剪枝的目的就是刪除由于噪聲數(shù)據(jù)而引起的分枝，從而避免決策樹的過匹配。第44頁，共154頁，2023年，2月20日，星期五4.2.3有效性和風(fēng)險性 預(yù)剪枝中最直接而簡單的方法是事先指定決策樹生長的最大深度，使決策樹不能得到充分生長。這種停止標準一般能夠取得比較好的效果。不過指定樹的高度的方法要求用戶對數(shù)據(jù)的取值分布有較為清晰的把握，而且須對參數(shù)值進行反復(fù)嘗試，否則無法給出一個較為合理的樹高度閾值。

更普遍的做法是采用統(tǒng)計意義上的檢驗、信息增益等度量，評估每次節(jié)點分裂對系統(tǒng)性能的增益。如果節(jié)點分裂的增益值小于預(yù)先給定的閾值，則不對該節(jié)點進行擴展。如果在最好情況下的擴展增益都小于閾值，即使有些節(jié)點的樣本不屬于同一類，算法也可以終止。選取閾值是困難的，閾值較高可能導(dǎo)致決策樹過于簡化，而閾值較低可能對樹的化簡不夠充分。第45頁，共154頁，2023年，2月20日，星期五4.2.3有效性和風(fēng)險性 后剪枝技術(shù)允許決策樹過度生長，然后根據(jù)一定的

規(guī)則，剪去決策樹中那些不具有一般代表性的葉節(jié)點或分枝。 后剪枝算法有自上而下和自下而上兩種剪枝策略。 自下而上的算法首先從最底層的內(nèi)節(jié)點開始，剪去滿足一定條件的內(nèi)節(jié)點，在生成的新決策樹上遞歸調(diào)用這個算法，直到?jīng)]有可以剪枝的節(jié)點為止。 自上而下的算法是從根節(jié)點開始向下逐個考慮節(jié)點的剪枝問題，只要節(jié)點滿足剪枝的條件就進行剪枝。第46頁，共154頁，2023年，2月20日，星期五4.2.3有效性和風(fēng)險性 目前，決策樹修剪策略主要有三種:悲觀修剪(pessimisticpruning)，代價復(fù)雜度修剪(cost-complexitypruning)和基于最小描述長度(minimumdescriptionlength，MDL)原理的修剪。 悲觀修剪是Quinlan在1987年提出的，該方法將所有的樣本用于樹的構(gòu)建和修剪，但是這種方法產(chǎn)生的樹太大，并且有時候精度不高。代價復(fù)雜度修剪使用了獨立的樣本用于修剪，這種策略適用于訓(xùn)練樣本比較多的情況。在訓(xùn)練樣本數(shù)目較少的情況下，需要將所有的樣本既用于樹的構(gòu)建，又用于樹的修剪。基于MDL原理的修剪是使用較多并且效果較好的方法。第47頁，共154頁，2023年，2月20日，星期五§4.2 樹的建模過程4.2.4屬性選擇

屬性選擇的統(tǒng)計度量(又稱為分枝指標splittingindex，SI)的計算是決策樹構(gòu)建算法的關(guān)鍵。 不同的決策樹算法采用不同的統(tǒng)計度量，主要有:

信息增益——InformationGain(ID3和C4.5算法使用)，

所有屬性假設(shè)都是種類字段，經(jīng)過修改之后可以適用于

數(shù)值字段;

基尼指數(shù)——Giniindex(即Gini指標)

CART算法、CHAID算法和SLIQ算法使用

適用于種類和數(shù)值字段等等。第48頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇1.ID3算法

ID3算法是Quinlan為了從數(shù)據(jù)中歸納分類模型而構(gòu)造的算法，它是一種經(jīng)典決策樹分類算法。ID3算法的基本概念包括:(1)決策樹的每個內(nèi)部節(jié)點對應(yīng)樣本的一個非類別屬性，該節(jié)點的每棵子樹代表這個屬性的取值范圍的一個子區(qū)間(子集)。一個葉節(jié)點代表從根節(jié)點到該葉節(jié)點的路徑對應(yīng)的樣本所屬的類別。這也是決策樹的定義。(2)決策樹的每個內(nèi)部節(jié)點都與具有最大信息量的非類別屬性相關(guān)聯(lián)，這決定什么是一棵好的決策樹。(3)通常用“熵”來衡量一個內(nèi)部節(jié)點的信息量，熵的定義使用信息論中的定義。第49頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-2

ID3的基本思想是自上而下地使用貪心算法搜索

訓(xùn)練樣本集，在每個節(jié)點處測試每一個屬性,從而構(gòu)建決策樹。 為了選擇訓(xùn)練樣本的最優(yōu)分枝屬性，ID3使用信息增益作為分枝指標。 下面將首先介紹信息增益的概念，然后給出ID3算法的

步驟，最后對ID3算法做一個簡單的評價。第50頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-2熵和信息增益 為了尋找對樣本進行分類的最優(yōu)方法，我們要做的工作就是使對一個樣本進行分類時需要問的問題最少(即樹的深度最小)。因此，需要某種函數(shù)來衡量哪些問題將提供最為平衡的劃分，信息增益就是這樣的函數(shù)之一。第51頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-2 設(shè)S是訓(xùn)練樣本集，它包含n

個類別的樣本，這些類別分別用Cl，C2，…，Cn

表示，那么S的熵(entropy)或者

期望信息為:式中，pi

表示類Ci的概率。 如果將S中的n

類訓(xùn)練樣本看成n

種不同的消息，那么S的熵表示對每一種消息編碼平均需要的比特數(shù)。第52頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-2

|S|*entropy(S)就表示對S進行編碼需要的比特數(shù)，

其中，|S|表示S中的樣本數(shù)目。e.g.

如果n=2，p1=p2=0.5，那么

entropy(S)=－0.51og20.5－0.51og20.5=1

如果n=2，p1=0.67，p2=0.33，那么

entropy(S)=－0.67log20.67－0.33log20.33=0.92第53頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-2 可見，樣本的概率分布越均勻，它的信息量(熵)就

越大，樣本集的混雜程度也越高。因此，熵可以作為訓(xùn)練集的不純度(Impurity)的一個度量，熵越大，不純度就越高。 這樣，決策樹的分枝原則就是使劃分后的樣本的子集

越純越好，即它們的熵越小越好。第54頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-2 當(dāng)樣本屬于每個類的概率相等時，即對任意i

有

pi=1/n時，上述的熵取到最大值log2n。而當(dāng)所有樣本屬于同一類時，S的熵為0。其他情況的熵介于0~log2n之間。第55頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-2 設(shè)屬性A將

S劃分成m份，根據(jù)A劃分的子集的熵或

期望信息由下式給出： 式中，Si表示根據(jù)屬性A劃分的S的第i

個子集，|S|和|Si|分別表示S和Si

中的樣本數(shù)目。 信息增益用來衡量熵的期望減少值，因此，使用屬性A對S進行劃分獲得的信息增益為: gain(S，A)=entropy(S)－entropy(S，A)第56頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-2

gain(S，A)是指因為知道屬性A的值后導(dǎo)致的熵的期望壓縮。

gain(S，A)越大，說明選擇測試屬性A對分類提供的信息越多。

因為熵越小代表節(jié)點越純，按照信息增益的定義，信息增益越大，熵的減少量也越大，節(jié)點就趨向于更純。 因此，可以對每個屬性按照它們的信息增益大小排序，獲得

最大信息增益的屬性被選擇為分枝屬性。 即熵值反映了對樣本集合S分類的不確定性，也是對樣本分類的期望信息。熵值越小，劃分的純度越高，對樣本分類的不確定性越低。一個屬性的信息增益，就是用這個屬性對樣本分類而導(dǎo)致的熵的期望值下降。因此，ID3算法在每一個節(jié)點選擇取得最大信息增益的屬性。第57頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-2

ID3算法在每一個節(jié)點選擇取得

最大信息增益gain(S，A)的屬性作為

分枝屬性第58頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-2

ID3算法

ID3算法在每個節(jié)點處評估每個屬性的信息增益，選擇獲得最大信息增益的屬性作為分枝屬性。值得注意的是，

ID3算法在計算最優(yōu)分枝屬性時不考慮已經(jīng)使用過的屬性，即在從

決策樹的根節(jié)點到葉節(jié)點的一條路徑中，所有內(nèi)部節(jié)點選擇的分枝屬性都是不同的。最初的ID3算法不能處理數(shù)值屬性，在根據(jù)分枝屬性劃分樣本時，

對該屬性的每一個不同取值都產(chǎn)生一個新的節(jié)點，并將訓(xùn)練樣本按照它們在該屬性上的取值分配到這些新的子節(jié)點中。顯然，ID3算法的決策樹模型是一棵多叉樹。

ID3算法是一種典型的決策樹分類算法，后來發(fā)展的

許多決策樹算法都是以ID3算法為基礎(chǔ)的，第59頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-2例子：使用信息增益進行決策樹的分枝生長。 如下頁訓(xùn)練數(shù)據(jù)集，反映了不同的顧客購買計算機的情況，其分類屬性為buys_computer，即是否購買，分為二類。 求出該訓(xùn)練集在根節(jié)點的最佳分類。第60頁，共154頁，2023年，2月20日，星期五信息增益計算示例表第61頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-2解：首先計算該訓(xùn)練集的熵， 根據(jù)熵公式，需知道各分類的概率，

buys_computer=yes的記錄有9條，其概率為9/14,

記該集合為C1

buys_computer=no的記錄有5條，其概率為5/14,

記該集合為C2

則，

entropy(S)=信息增益表第62頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-2接下來計算根據(jù)每個非類別屬性劃分子集時的熵， 首先考察age

這一分類屬性，需要知道按age分類后的各子集的目標屬性集的概率，

age的youth類有5個樣本，其中有2個屬于C1

類，即buys_computer=yes，3個屬于C2類，即buys_computer=no age的middle_aged類有4個樣本，4個屬于C1

類，0個屬于C2類

age的senior類有5個樣本，3個屬于C1

類，2個屬于

C2類于是，有entropy(S,age)=信息增益表第63頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-2因此，屬性age的增益為：gain(S,age)=entropy(S)－entropy(S,age)

=0.940－0.694=0.246位同理，可計算得：

gain(S,income)=0.029位gain(S,student)=0.151位

gain(S,credit_rating)=0.048位 可見，按屬性age分類具有最高的增益，因此選擇其為分枝屬性。其分枝結(jié)果如下圖示。 繼續(xù)在每個節(jié)點迭代進行下去，可得到進一步生長的樹，如下下頁圖示。第64頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-2第65頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-2age?student?credit_rating?yesnoyesnoyesyouthmiddle_agedseniornoyesfairexcellent第66頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-2ID3算法本身還存在著許多需要改進的地方：(1)ID3算法只能處理分類屬性，而不能處理數(shù)值屬性。一個改進的辦法是事先將數(shù)值屬性劃分為多個區(qū)間，形成新的分類屬性。劃分區(qū)間的主要問題是閾值的計算，即區(qū)間

端點的選取，這將包含大量的計算。(2)每個節(jié)點的合法分類數(shù)比較少，并且只能用單一屬性

作為分枝測試屬性。(3)ID3對訓(xùn)練樣本質(zhì)量的依賴性很強。訓(xùn)練樣本的質(zhì)量主要是指是否存在噪聲和是否存在足夠的樣本。(4)ID3的決策樹模型是多叉樹，節(jié)點的子樹個數(shù)取決于分枝屬性的不同取值個數(shù)，這不利于處理分枝屬性的取值數(shù)目較多的情況。目前流行的決策樹算法大都采用二叉樹模型。第67頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-2(5)ID3算法不包括樹的修剪，這樣模型受噪聲數(shù)據(jù)和

統(tǒng)計波動的影響比較大。(6)在不重建整棵樹的條件下，不能方便地對決策樹做更改。也就是說，當(dāng)一個新樣本不能被正確分類時，我們就

需要對樹進行修改以適用于這一新樣本。可以通過局部修補來實現(xiàn)這一點，但是在這種情況下，決策樹卻會

逐漸地失掉它作為某些重要概念的最有效表達的作用。或者也可以從頭開始建立一棵新樹，但是這樣做必須

記住所有遇見過的樣本。顯然，這樣做不是一個好辦法。第68頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-22.C4.5算法

ID3算法還存在著許多需要改進的地方，為此，Quinlan在1993年提出了ID3算法的改進版本C4.5算法。它與ID3算法的不同點包括:(1)分枝指標采用增益比例，而不是ID3算法所使用的信息增益。(2)按照數(shù)值屬性值的大小對樣本排序，從中選擇一個分割點，劃分數(shù)值

屬性的取值區(qū)間，從而將ID3算法的處理能力擴充到數(shù)值屬性上來。(3)將訓(xùn)練樣本集中的未知屬性值用最常用的值代替，或者用該屬性的

所有取值的平均值代替,從而處理缺少屬性值的訓(xùn)練樣本。(4)使用Κ次迭代交叉驗證,評估模型的優(yōu)劣程度。(5)根據(jù)生成的決策樹，可以產(chǎn)生一個if-then規(guī)則的集合，每一個規(guī)則

代表從根節(jié)點到葉節(jié)點的一條路徑。第69頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-2增益比例 信息增益是一種衡量最優(yōu)分枝屬性的有效函數(shù)，但是它傾向于選擇具有大量不同取值的屬性，從而產(chǎn)生許多

小而純的子集。例如病人的ID、姓名和就診日期等，特別是作為關(guān)系數(shù)據(jù)庫中記錄的主碼屬性，根據(jù)這樣的屬性劃分的子集都是單元集，對應(yīng)的決策樹節(jié)點當(dāng)然是純節(jié)點。因此，需要新的指標來降低這種情況下的增益。Quinlan提出使用增益比例來代替信息增益。第70頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-2 首先定義訓(xùn)練樣本關(guān)于屬性值的信息量(熵)split_info(S，A)，其中，S代表訓(xùn)練樣本集，A代表屬性，這個信息量是與樣本的類別無關(guān)的，它的計算公式如下:式中，Si

表示根據(jù)屬性A劃分的第i個樣本子集。 樣本在A上的取值分布越均勻，split_info的值也就越大。split_info用來衡量屬性分裂數(shù)據(jù)的廣度和均勻性。 屬性A的增益比例計算如下:第71頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-2 當(dāng)存在i

使得|Si|≈|S|時，split_info將非常小，從而導(dǎo)致增益比例異常的大，C4.5為解決此問題，進行了改進，它計算每個屬性的信息增益，對于超過平均信息增益的屬性，再進一步根據(jù)增益比例來選取屬性。 一個屬性分割樣本的廣度越大，均勻性越強，該屬性的split_info越大，增益比例就越小。因此，split_info降低了

選擇那些值較多且均勻分布的屬性的可能性。

大于平均信息增益的增益率最大的屬性即為所選分枝屬性。

第72頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-2

數(shù)值屬性的處理C4.5處理數(shù)值屬性的過程如下:l按照屬性值對訓(xùn)練樣本進行排序。2用不同的閾值對訓(xùn)練數(shù)據(jù)進行動態(tài)劃分。3當(dāng)輸入改變時確定一個閾值.4取當(dāng)前樣本的屬性值和前一個樣本的屬性值的中點作為

新的閾值。5生成兩個劃分，所有樣本分布到這兩個劃分中;6得到所有可能的閾值、增益和增益比例。 每一個數(shù)值屬性劃分為兩個區(qū)間，即大于閾值或小于等于閾值。第73頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-2

未知屬性值的處理

C4.5處理樣本中未知屬性值的方法是將未知值用最常用的值代替，或者用該屬性的所有取值的平均值代替。另一種解決辦法是采用概率的辦法，對屬性的每一個取值賦予一個概率，在劃分樣本集時，將未知屬性值的樣本按照屬性值的概率分配到子節(jié)點中去，這些概率的獲取依賴于已知的

屬性值的分布。第74頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-2

k

次交叉驗證 交叉驗證是一種模型評估方法，它將使用學(xué)習(xí)樣本產(chǎn)生的決策樹模型應(yīng)用于獨立的測試樣本，從而對學(xué)習(xí)的結(jié)果進行驗證。如果對學(xué)習(xí)樣本進行分析產(chǎn)生的大多數(shù)或者全部分枝都是基于隨機噪聲的，那么使用測試樣本進行分類的結(jié)果將非常糟糕。 如果將上述的學(xué)習(xí)-驗證過程重復(fù)k次，就稱為

k

次迭代交叉驗證。 首先將所有的訓(xùn)練樣本平均分成k份，每次使用其中的一份作為測試樣本，使用其余的k－1份作為學(xué)習(xí)樣本，

然后選擇平均分類精度最高的樹作為最后的結(jié)果。第75頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-2 通常，分類精度最高的樹并不是節(jié)點最多的樹。除了用于選擇規(guī)模較小的樹，交叉驗證還用于決策樹的修剪。

k

次迭代交叉驗證非常適用于訓(xùn)練樣本數(shù)目比較少的情形。

但是，由于要構(gòu)建k棵決策樹,它的計算量非常大。第76頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-2

規(guī)則的產(chǎn)生

C4.5還提供了將決策樹模型轉(zhuǎn)換為if-then規(guī)則的算法。 規(guī)則存儲于一個二維數(shù)組中，每一行代表一個規(guī)則。

表的每一列代表樣本的一個屬性，列的值代表了屬性的不同取值，例如，對于分類屬性來說，0,1分別代表取屬性的第一、二個值，對于數(shù)值屬性來說，0,1分別代表小于等于和大于閾值。如果列值為-1，則代表規(guī)則中不包含該屬性。第77頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-23.CART算法

生成的是二叉樹，用gini指標作為分枝度量，用

代價復(fù)雜度指標進行修剪，是一種后剪枝算法

CART算法更準確的應(yīng)記為“C&RT算法”

(ClassificationandRegressionTrees，分類與回歸樹) CART算法是由Brieman等人在1984年提出的。在他們1984年出版的ClassificationandRegressionTrees

一書中有對算法的詳盡介紹。這些來自斯坦福和加州大學(xué)伯克利分校的研究者們演示了如何將這一新算法用到各種不同的問題中，如從包含大量光譜的數(shù)據(jù)中發(fā)現(xiàn)氯元素。第78頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-2

CART的一大優(yōu)點是它將模型的驗證和最優(yōu)通用樹的發(fā)現(xiàn)嵌在了

算法中。

CART是這樣實現(xiàn)這一目標的:它先生成一棵非常復(fù)雜的樹，再根據(jù)交叉驗證和測試集驗證的結(jié)果對樹進行剪枝，從而得到最優(yōu)通用樹。這棵樹是根據(jù)剪枝后不同版本的樹在測試集數(shù)據(jù)上的性能得到的。復(fù)雜的樹很少能在備用數(shù)據(jù)上表現(xiàn)出好的性能，因為對訓(xùn)練數(shù)據(jù)來說它是

過適應(yīng)的。使用交叉驗證，可能選擇到最適應(yīng)未來數(shù)據(jù)的樹。 相對來說，CART算法對缺少數(shù)據(jù)的情況是比較穩(wěn)健的。如果某條記錄中缺少某個非類別屬性的值，生成樹時將不用這條記錄來決定

最優(yōu)分裂。實際上，CART是用它手頭上所有可用的信息來決定可能的最優(yōu)分裂。第79頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-2 當(dāng)在新數(shù)據(jù)上用CART進行分類時，可以用替代屬性來處理缺少的值。替代屬性是模擬樹中實際分類的分裂值和非類別屬性，當(dāng)首選非類別屬性的數(shù)據(jù)缺失時可以用它來代替。 例如,盡管把鞋的大小作為分類屬性不如用身高作為

分類屬性好，但當(dāng)用CART模型進行分裂，而某條記錄的

身高信息缺失時，可以試著用鞋的大小作為替代屬性來模擬基于身高的分裂。第80頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2根據(jù)給定樣本集S構(gòu)建分類樹由以下三步組成:(1)使用S構(gòu)建最大樹Tmax，使得Tmax中每一個葉節(jié)點要么

很小(節(jié)點內(nèi)部所包含的樣本數(shù)小于給定值)，要么是

純節(jié)點(節(jié)點內(nèi)部樣本屬于同一個類)，要么不存在

非類別屬性作為分枝屬性。(2)使用修剪算法構(gòu)建一個有限的、節(jié)點數(shù)目遞減的

有序子樹序列。(3)使用評估算法從子樹序列中選出一棵最優(yōu)樹，作為

最終的決策樹。第81頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2上面的過程簡單說來，即是：構(gòu)建最大決策樹

數(shù)據(jù)準備、gini指標、構(gòu)建最大樹修剪決策樹

代價復(fù)雜度修剪子樹評估

重替代評估、測試樣本評估、交叉驗證評估第82頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2構(gòu)建最大樹 給定訓(xùn)練樣本集，構(gòu)建最大樹就是使決策樹充分生長，最終產(chǎn)生描述訓(xùn)練樣本的最大二叉樹。

CART能夠處理數(shù)值屬性和分類屬性，在構(gòu)建決策樹之前，CART首先要對這些屬性數(shù)據(jù)進行數(shù)據(jù)準備工作，包括降低屬性的勢和構(gòu)造屬性的標準問題集。與上面介紹的算法不同，CART使用的分枝指標是gini指標，而不是信息增益。 其主要工作包括：

數(shù)據(jù)準備計算gini指標構(gòu)建最大樹第83頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2(l)數(shù)據(jù)準備

CART的數(shù)據(jù)準備工作包括降低屬性的勢和構(gòu)造屬性的標準問題集。

屬性的勢(cardinality)又稱為屬性的基數(shù)，樣本的每個

屬性的所有取值構(gòu)成了一個有限集合，對于有限集來說，

集合的勢就是集合中元素的個數(shù)。 因此，降低屬性的勢就是為每一個屬性分配一組

離散值，按照業(yè)務(wù)需求，將屬性的實際值映射到這組離散值上，通常選定的這組離散值的個數(shù)要少于屬性的實際取值的個數(shù)。

屬性的標準問題集是所有候選的分枝方案的集合，數(shù)值屬性和分類屬性的標準問題的形式是不一樣的。第84頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2 若屬性A是數(shù)值屬性，那么A的標準問題集是由形如

“IsA≤d?”的分枝測試構(gòu)成的集合。

首先取出訓(xùn)練樣本中屬性A的所有不同取值，將這些值按照

從小到大的順序排序，然后計算排序后的數(shù)值序列中每相鄰兩個數(shù)值的中間值，得到一個新的序列A’，最后根據(jù)A’生成屬性A的標準問題集。 例如，假設(shè)屬性A所有不同取值在排序后得到的序列為:

(1，1.5，1.7,1.9，2，2.6，2.9，3.3，3.8,4.2，5)那么中間值序列為:

A’=(1.25，1.6,1.8，1.95，2.3，2.75，3.1，3.55,4,4.6)于是，屬性A的標準問題集為:

{IsA≤1.25，IsA≤1.6,IsA≤1.8，IsA≤1.95，IsA≤2.3，IsA≤2.75，IsA≤3.1，IsA≤3.55,IsA≤4,IsA≤4.6}第85頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2 若屬性A是分類屬性，那么A的標準問題集是由形如

“IsA∈s?”的分枝測試構(gòu)成的集合，其中s是屬性A的所有不同取值構(gòu)成的集合S(A)的非空子集。 首先取出訓(xùn)練樣本中屬性A中所有不同取值構(gòu)成集合S(A)，然后計算一個由S(A)的子集構(gòu)成的集合subsets(A),最后根據(jù)subsets(A)生成屬性A的標準問題集。

subsets(A)的元素滿足以下兩個條件:1)如果s∈subsets(A)，那么s≠S(A)，并且s不為空;2)如果s1,s2∈subsets(A)，那么s1∪s2≠S(A)。第86頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2 例如：S(A)={a1,a2,a3,a4}，根據(jù)既定算法得出subsets(A)={{a1},{a1,a2},{a2},{a1,a3},{a1,a2,a3},{a2,a3},{a3}},

于是，得到問題A的標準問題集為：{IsA∈{a1},IsA∈{a1,a2},IsA∈{a2},IsA∈{a1,a3},IsA∈{a1,a2,a3},{a2,a3},{a3}},第87頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2(2)gini指標 假設(shè)S是用來劃分的樣本集合，我們選擇的劃分方法

必須使S的子集比它本身更“純”，可以用一個不純函數(shù)χ

來評估各種劃分方法的優(yōu)劣。 如果我們用χ(t)

來表示任意節(jié)點t的不純度，那么χ(t)可以表示為:式中，p(ci|t)表示類ci

在數(shù)據(jù)集t

中的概率。第88頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2 根據(jù)這個定義，分枝方案s的優(yōu)劣度可以用不純度的

減少量△χs(t)

來定義.

如果測試s將樣本集合t分為n個子集t1,t2,…,tn,那么分枝優(yōu)劣度可以定義為:第89頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2如果用gini指標，那么函數(shù)χ的定義為:這時，在測試s下gini(s)可以用不純度的減少量△χs(t)

表示為:如果某個測試s使gini(s)最大，那么表示在測試s下不純度的減少量最大，則s就是最優(yōu)的分枝方案。第90頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2(3)構(gòu)建最大樹Tmax

當(dāng)數(shù)據(jù)準備完成后，就可以根據(jù)訓(xùn)練樣本構(gòu)建

最大樹Tmax。 首先初始化決策樹的根節(jié)點，并將所有的訓(xùn)練樣本分配給根節(jié)點;然后通過遞歸來劃分訓(xùn)練樣本，將之分配給

新生成的子節(jié)點;最終產(chǎn)生一棵完全生長的決策樹，遞歸

結(jié)束的條件是所有的葉節(jié)點要么很小，要么是純節(jié)點，要么不存在非類別屬性作為分枝屬性。

CART的決策樹模型是二叉樹，在對某個節(jié)點執(zhí)行分裂時，將節(jié)點中的樣本劃分成tL和tR兩部分，樣本的概率分別為pL

和pR，然后將tL和tR的樣本分別分配到該節(jié)點的左右子節(jié)點中。第91頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2 在劃分訓(xùn)練樣本、執(zhí)行節(jié)點分裂之前，首先要計算節(jié)點的分枝方案，分枝方案是從數(shù)據(jù)準備階段生成的屬性的標準問題集中挑選出來的。

在每個節(jié)點處評估所有屬性的每個標準問題的

gini指標，然后選擇gini指標最大的標準問題作為分枝方案。第92頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2 設(shè)樣本有n個屬性，分別為A1，A2，…,An，對應(yīng)的

標準問題集為Ql，Q2，…，Qn，標準問題集Qi

的第j個標準問題用Qi，tj

表示。 在節(jié)點N中，屬性Ai

的第j

個標準問題的gini指標用gini(i,j,N)表示，使用屬性Ai

執(zhí)行分裂的最大gini指標用gini(i，N)表示，最優(yōu)分枝方案(gini指標最大的分枝方案)的gini指標用gini(N)表示，顯然有

gini指標為gini(N)的標準問題Qi,tj

被選為節(jié)點N的分枝方案。第93頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2上面的過程簡單說來，即是：構(gòu)建最大決策樹

數(shù)據(jù)準備、gini指標、構(gòu)建最大樹

修剪決策樹

代價復(fù)雜度修剪子樹評估

重替代評估、測試樣本評估、交叉驗證評估第94頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2

修剪決策樹

CART的決策樹修剪采用一種稱為代價復(fù)雜度修剪的

策略，產(chǎn)生一個節(jié)點數(shù)目遞減的子樹序列。在生成子樹序列之后，還要確定葉節(jié)點對應(yīng)的類別。其主要工作包括：

1）生成有序子樹序列

2）確定葉節(jié)點的類別第95頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2(l)生成有序子樹序列 采用代價復(fù)雜度修剪策略是基于以下兩個事實: 1)復(fù)雜決策樹(節(jié)點多)對訓(xùn)練樣本有很高的分類精度，但是當(dāng)將它應(yīng)用于新的測試樣本時，分類精度并不高;

2)理解和解釋具有大量葉節(jié)點的決策樹是一個復(fù)雜的

過程。 因此，決策樹的復(fù)雜度可以用葉節(jié)點的數(shù)目來衡量，而決策樹的代價則以分類精度來衡量，一個好的決策樹

分類模型應(yīng)該在復(fù)雜度與代價之間進行權(quán)衡。第96頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2樹T的代價復(fù)雜度可以用下面的公式計算:Rα(T)=R(T)+α|~T|其中，Rα(T)

表示樹T的代價復(fù)雜度;

R(T)

表示T的重替代評估，它是將T用于學(xué)習(xí)樣本時的分類錯誤率;

|~T|表示T的葉節(jié)點數(shù);

α

稱為復(fù)雜度參數(shù)，它定義為每增加一個葉節(jié)點所

提高的代價復(fù)雜度。第97頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2

α越大，復(fù)雜度因素對考察決策樹的代價復(fù)雜度的影響也越大。 當(dāng)α=0時，表示不考慮復(fù)雜度因素對代價復(fù)雜度的影響，這時算法傾向于選擇葉節(jié)點最多的決策樹，因為它對

訓(xùn)練樣本的分類錯誤率最低;

當(dāng)α足夠大時，重替代評估的影響可以忽略，算法傾向于選擇只有一個葉節(jié)點的決策樹。

正確衡量決策樹的α值應(yīng)該介于上述兩個極端情況之間第98頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2 為了得到有序子樹序列，還需要提出節(jié)點的代價復(fù)雜度概念，節(jié)點t的代價復(fù)雜度實際上就是將t看作葉子節(jié)點

(修剪掉t的子樹Tt)時的代價復(fù)雜度，因此，t的代價復(fù)雜度可以用如下公式計算:

Rα({t})=R(t)+α其中，{t}表示由節(jié)點t構(gòu)成的子樹;

R(t)表示節(jié)點t的重替代評估，即將決策樹用于學(xué)習(xí)樣本時節(jié)點t上的分類錯誤率;α為復(fù)雜度參數(shù)。 可見節(jié)點t的代價復(fù)雜度可以看作只有一個節(jié)點的決策樹{t}的代價復(fù)雜度。第99頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2 如果用Rα(Tt)表示t的子樹Tt

的代價復(fù)雜度，那么

Rα(Tt)=R(Tt)+α|~Tt|

根據(jù)代價復(fù)雜度修剪策略，如果節(jié)點t的代價復(fù)雜度

大于它的子樹的代價復(fù)雜度，即Rα({t})>Rα(Tt)

，則

應(yīng)該保留子樹Tt，否則就有理由修剪此子樹將上面的Rα({t})

和Rα(Tt)代入，得到第100頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2 當(dāng)時，節(jié)點t和子樹Tt

具有相同的

代價復(fù)雜度，但{t}比Tt的節(jié)點少，因此，{t}比Tt更可取 當(dāng)時，節(jié)點t的代價復(fù)雜度比子樹Tt

更小，因此，{t}也比Tt更可取；這就是CART算法逐步修剪生成有序子樹序列的主要思想。 當(dāng)復(fù)雜度參數(shù)α給定時，的值越小，

表示t的代價復(fù)雜度比Tt的代價復(fù)雜度小的程度越大，

于是，Tt被修剪的理由越充分。為描述方便，我們稱此

計算值為β。第101頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2CART產(chǎn)生有序子樹序列的步驟 假設(shè)生成的子樹序列以節(jié)點數(shù)目遞減的順序排列為T1>T2>T3>…>{tl}，其中{tl}表示只有一個根節(jié)點的子樹。 生成T1

的方法是減去Tmax所有滿足R(T)=R(tL)+R(tR)的子樹，其中tL和tR分別表示節(jié)點t

的左右子節(jié)點，修剪得到的子樹即為T1。第102頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2 為了構(gòu)建T2

，首先給出T1的最弱聯(lián)系節(jié)點的定義，對任意

t∈T1，令其中，~T1表示T1葉節(jié)點集合。 定義T1的最弱聯(lián)系節(jié)點滿足第103頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2 將t1從T1中剪去就得到樹T2

，如果存在多個最弱

聯(lián)系點，則將它們?nèi)考羧ァ?從T2

得到T3的過程與從T1得到T2的過程相同，即剪去T2的最弱聯(lián)系節(jié)點。重復(fù)上述過程，直到修剪后的子樹

只剩下一個節(jié)點，將它作為有序子樹序列的最后一個

子樹{tl}。第104頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2(2)確定葉節(jié)點的類別 根據(jù)決策樹的定義，每個葉節(jié)點對應(yīng)一個類標號，最簡單的類別分配方法就是指定節(jié)點中樣本數(shù)目最多的類為

該葉節(jié)點的類， 如果存在多個類的樣本個數(shù)都為最大值，那么就任意指定一個類作為該葉節(jié)點的類。

第105頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2 如果對任意類i

和j

，將類j

的樣本誤分為類i

的代價是相同的，那么這樣的分配方法是合理的，但是在很多領(lǐng)域中，各個類之間誤分的代價往往是不同的，例如在信用評分系統(tǒng)中，將一個低信用度客戶誤分為高信用度客戶的代價可能大于將高信用度客戶誤分為低信用度客戶的代價，因此，我們可以對節(jié)點t中每一個類i

計算它的誤分代價期望 其中c(i|j)表示將類j

分為類i的代價，當(dāng)i=j

時,c(i|j)=0;p(j|t)表示節(jié)點t

中屬于類j

的樣本的概率。將取得最小誤分代價期望的類i

指定為節(jié)點t

的類。第106頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2上面的過程簡單說來，即是：構(gòu)建最大決策樹

數(shù)據(jù)準備、gini指標、構(gòu)建最大樹修剪決策樹

代價復(fù)雜度修剪

子樹評估

重替代評估、測試樣本評估、交叉驗證評估第107頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2

子樹評估 子樹評估的目的是從有序子樹序列中選取一棵“最優(yōu)”子樹作為最終的分類模型。

CART的子樹評估方法有重替代評估、測試樣本評估和交叉驗證評估，這三種評估方法都是根據(jù)子樹的代價來評估的，

Brieman等提出了子樹評估的1SE(onestandarderror)

規(guī)則，考慮了決策樹復(fù)雜度的因素。 以下簡介幾種評估：重替代評估、測試樣本評估、

交叉驗證評估、及1SE(onestandarderror)規(guī)則第108頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2(1)重替代評估 重替代評估使用構(gòu)建決策樹的樣本來評估決策樹的

誤分代價。 將學(xué)習(xí)樣本應(yīng)用于每個子樹，子樹的重替代評估定義為:

其中，N為訓(xùn)練樣本的個數(shù)，

c(i|j)表示將類j

誤分為類

i

的代價;

Nij表示將類j

誤分為類i的樣本個數(shù)。

R(T)值最小的子樹即為“最優(yōu)”子樹。

重替代評估最主要的缺點在于它得自(來自)學(xué)習(xí)樣本，因此它低估了實際的分類錯誤，而通常傾向于選擇更為“枝繁葉茂”的子樹。第109頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2(2)測試樣本評估 測試樣本評估的計算方法與重替代評估一樣，不同的是它使用獨立于學(xué)習(xí)樣本的測試樣本來評估決策樹的誤分代價Rts(T)，測試樣本的數(shù)目一般小于學(xué)習(xí)樣本的數(shù)目。

這種評估方法適用于訓(xùn)練樣本數(shù)目比較多的情況。第110頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2(3)交叉驗證評估

k

次迭代交叉驗證評估首先將訓(xùn)練樣本S

盡量平均劃分為k

份，分別表示為S1，S2，…,Sk， 令Sv=S－Sv，l≤v≤k， 對S和每一個

Sv使用決策樹的構(gòu)建算法生成一系列

最大樹Tmax

和Tmaxv， 對每一個α值，令T(α)和Tv(α)

分別

表示Tmax和Tmaxv

的代價復(fù)雜度最小的子樹，然后將每一個

Tv(α)

應(yīng)用于Sv，第111頁，共154頁，2023年，2月20日，星期五4.2.4屬性選擇-CART算法-2 設(shè)Sv

中類j

的樣本被誤分為類

i的樣本個數(shù)為Nijv

，那么類