決策樹簡介課件

決策樹第十組：

郭浩韓學(xué)成何珺

何軍黃安迪決策樹第十組：1決策樹簡介課件2決策樹簡介課件3§4.1數(shù)據(jù)分類介紹

分類是數(shù)據(jù)挖掘的一個重要課題,它的目的是：

構(gòu)造一個分類函數(shù)或分類模型,該模型能把數(shù)據(jù)庫中的數(shù)據(jù)項映射到給定類別中的某一個。 數(shù)據(jù)分類的過程一般來說主要包含兩個步驟 第一步,建立一個描述已知數(shù)據(jù)集類別或概念的模型 第二步,利用所獲得的模型進(jìn)行分類操作§4.1數(shù)據(jù)分類介紹 分類是數(shù)據(jù)挖掘的一個重要課題,它4§4.1 數(shù)據(jù)分類介紹-2第一步,建立一個描述已知數(shù)據(jù)集類別或概念的模型 該模型是通過對數(shù)據(jù)庫中各數(shù)據(jù)進(jìn)行內(nèi)容的分析而獲得的。 分類學(xué)習(xí)方法所使用的數(shù)據(jù)集稱為訓(xùn)練樣本集合，每一數(shù)據(jù)行都屬于一個確定的數(shù)據(jù)類別，其類別值是由一個屬性來描述的(被稱為類別標(biāo)記屬性)。 因此分類學(xué)習(xí)又可稱為監(jiān)督學(xué)習(xí)，它是在已知訓(xùn)練樣本類別情況下，通過學(xué)習(xí)建立相應(yīng)模型。而無監(jiān)督學(xué)習(xí)則是在訓(xùn)練樣本的類別與類別個數(shù)均未知的情況下進(jìn)行的，如聚類分析?！?.1 數(shù)據(jù)分類介紹-2第一步,建立一個描述已知數(shù)據(jù)集5§4.1 數(shù)據(jù)分類介紹-2第二步,利用所獲得的模型進(jìn)行分類操作 首先對模型分類準(zhǔn)確率進(jìn)行估計。 模型的準(zhǔn)確性可以通過由該模型所正確分類的測試樣本個數(shù)所占總測試樣本的比例得到。即對于每一個測試樣本，比較其已知的類別與學(xué)習(xí)所獲模型的預(yù)測類別。如果一個學(xué)習(xí)所獲模型的準(zhǔn)確率經(jīng)測試被認(rèn)為是可以

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

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

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

類別(屬性)取值。

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

J.RossQuinlan提出ID3算法，引進(jìn)信息論中的有關(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ī)則等方面作了較大的改進(jìn)，C5.0是C4.5的商業(yè)改進(jìn)版?！?.1 決策樹介紹-24.1.1決策樹的基本知識10例子關(guān)于上mooc的例子例子關(guān)于上mooc的例子11例子例子12決策樹簡介課件134.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í)。4.1.1決策樹的基本知識 決策樹技術(shù)發(fā)現(xiàn)數(shù)據(jù)模式和規(guī)則的144.1.1決策樹的基本知識-2

歸納學(xué)習(xí)存在一個基本假定:

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

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

這個假定是歸納學(xué)習(xí)有效性的前提條件。4.1.1決策樹的基本知識-2 歸納學(xué)習(xí)存在一個基本假定:154.1.1決策樹的基本知識-2

歸納可以分為自下而上、自上而下和雙向搜索三種方式 自下而上法一次處理一個輸入對象，將描述逐步

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

找到一些滿足一定要求的最優(yōu)的描述。 雙向搜索方式則是這兩者的結(jié)合。4.1.1決策樹的基本知識-2 歸納可以分為自下而上、自上164.1.1決策樹的基本知識-2

先根據(jù)訓(xùn)練子集形成決策樹，如果該樹不能對所有對象給出正確的分類，那么選擇一些例外

加入到訓(xùn)練集中，重復(fù)該過程一直到形成正確的決策集。 最終結(jié)果是“一棵樹”，各分枝對應(yīng)某種屬性的某一可能值。4.1.1決策樹的基本知識-2 先根據(jù)訓(xùn)練子集形成決策樹，174.1.1決策樹的基本知識

決策樹通常有兩大類型，分別為分類決策樹和

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

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

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

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

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

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

兩類，則稱之為布爾決策樹。4.1.1決策樹的基本知識 決策樹通常有兩大類型，分別為分184.1.1決策樹的基本知識

決策樹學(xué)習(xí)是應(yīng)用最廣的歸納推理算法之一。它是一種逼近離散函數(shù)值的方法，分類精度高，操作簡單，并且對噪聲數(shù)據(jù)有很好的穩(wěn)健性，因而成為比較實用且比較流行的數(shù)據(jù)挖掘算法。 它的最大優(yōu)點是，在學(xué)習(xí)過程中不需要使用者了解很多背景知識，只要訓(xùn)練樣本集能夠用“屬性-值”的方式表達(dá)

出來就能使用決策樹學(xué)習(xí)算法來分類。4.1.1決策樹的基本知識 決策樹學(xué)習(xí)是應(yīng)用最廣的歸納推理194.1.1決策樹的基本知識4.2.4屬性選擇

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

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

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

數(shù)值字段;

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

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

適用于種類和數(shù)值字段等等。4.1.1決策樹的基本知識4.2.4屬性選擇204.1.1決策樹的基本知識-2決策樹方法的(相對)優(yōu)點:可以生成可理解的規(guī)則

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

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

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

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

是一個有待研究的課題。4.1.1決策樹的基本知識-2決策樹方法的缺點:224.1.1決策樹的基本知識-2決策樹學(xué)習(xí)算法適用的問題:樣本可以用“屬性-值”的方式來描述目標(biāo)函數(shù)的輸出值為離散值訓(xùn)練數(shù)據(jù)中允許包含有錯誤:

樣本的分類錯誤或?qū)傩灾靛e誤都允許訓(xùn)練數(shù)據(jù)中有樣本屬性值缺失4.1.1決策樹的基本知識-2決策樹學(xué)習(xí)算法適用的問題:23§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)濟(jì)和社會效益。

國內(nèi)目前有關(guān)決策樹的研究多是圍繞算法的改進(jì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ī)療政策分析等。§4.1 決策樹介紹-24.1.2決策樹的應(yīng)用和發(fā)展趨勢24§4.2樹的建模過程§4.2樹的建模過程25決策樹簡介課件26§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)容§4.2 樹的建模過程 決策樹算法通過構(gòu)造決策樹來發(fā)現(xiàn)數(shù)據(jù)27§4.2 樹的建模過程—總體步驟決策樹的構(gòu)造基本可以分為如下兩步:決策樹的生成 決策樹的生成是指由訓(xùn)練樣本數(shù)據(jù)集生成決策樹的過程。一般情況下，訓(xùn)練樣本數(shù)據(jù)集是根據(jù)實際需要由實際的歷史數(shù)據(jù)生成的、有一定綜合程度的、用于數(shù)據(jù)分析處理的

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

校正和修正的過程，主要是采用新的樣本數(shù)據(jù)集(測試數(shù)據(jù)集)中的數(shù)據(jù)檢驗決策樹生成過程中產(chǎn)生的初步規(guī)則，將那些影響預(yù)測準(zhǔn)確性的分枝剪除。一般情況下，根據(jù)測試數(shù)據(jù)集中的每一元組對生成的規(guī)則進(jìn)行預(yù)測準(zhǔn)確性的檢驗，如果預(yù)測準(zhǔn)確性過低，則將該分枝剪除?！?.2 樹的建模過程—總體步驟決策樹的構(gòu)造基本可以分為如28§4.2 樹的建模過程4.2.1數(shù)據(jù)要求(數(shù)據(jù)準(zhǔn)備)

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

減少學(xué)習(xí)過程可能出現(xiàn)相互矛盾情況的問題。4.2.1數(shù)據(jù)準(zhǔn)備數(shù)據(jù)清洗304.2.1數(shù)據(jù)準(zhǔn)備相關(guān)分析 由于數(shù)據(jù)集中的許多屬性與挖掘任務(wù)本身可能是無關(guān)的，例如記錄銀行貸款申請(單)填寫時的星期數(shù)(屬性)，就可能與申請成功與否的描述無關(guān)。此外，有些屬性也可能是冗余的。因此需要對數(shù)據(jù)進(jìn)行相關(guān)分析，以使在學(xué)習(xí)階段之前就消除無關(guān)或冗余屬性。在機(jī)器學(xué)習(xí)中，這一相關(guān)分析步驟被稱為屬性選擇(featureselection)，包含與挖掘任務(wù)無關(guān)的屬性可能會減緩甚至誤導(dǎo)整個學(xué)習(xí)過程。4.2.1數(shù)據(jù)準(zhǔn)備相關(guān)分析314.2.1數(shù)據(jù)準(zhǔn)備數(shù)據(jù)轉(zhuǎn)換 利用概念層次樹，數(shù)據(jù)能夠被泛化到更高的層次。概念層次樹對連續(xù)數(shù)值的轉(zhuǎn)換非常有效。例如，屬性“收入”的數(shù)值就可以被泛化為若干離散區(qū)間，諸如低、中和高。由于泛化操作壓縮了原來的數(shù)據(jù)集，從而可以幫助有效減少學(xué)習(xí)過程所涉及的輸入輸出操作。4.2.1數(shù)據(jù)準(zhǔn)備數(shù)據(jù)轉(zhuǎn)換32§4.2 樹的建模過程4.2.2樹的生長 決策樹算法是一種常用的數(shù)據(jù)挖掘算法，它是從

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

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

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

(conceptlearningsystem，CLS)是最早的決策樹算法，以后的許多決策樹算法都是對CLS算法的改進(jìn)或由CLS衍生而來。目前，利用決策樹進(jìn)行數(shù)據(jù)分類的方法已經(jīng)被深入研究，并且形成了許多決策樹算法。§4.2 樹的建模過程4.2.2樹的生長334.2.2樹的生長

決策樹是“一棵樹”，它的根節(jié)點是整個數(shù)據(jù)集合空間，每個分節(jié)點是對一個單一變量(屬性)的測試，該測試將數(shù)據(jù)集合空間分割成兩個或更多塊。每個葉節(jié)點是屬于單一類別的記錄。

4.2.2樹的生長 決策樹是“一棵樹”，它的根節(jié)點是整個數(shù)344.2.2樹的生長

通常,通過自上而下遞歸分割的過程來構(gòu)建決策樹,分為三個步驟:(1)尋找初始分裂。整個訓(xùn)練集作為產(chǎn)生決策樹的集合，

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

內(nèi)的記錄都屬于同一類，或達(dá)到其他停止準(zhǔn)則。(3)數(shù)據(jù)的修剪。去掉一些可能是噪音或者異常的數(shù)據(jù)或節(jié)點4.2.2樹的生長 通常,通過自上而下遞歸分割的過程來構(gòu)354.2.2樹的生長其通用的基本算法(貪心算法)為:

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

類別或沒有屬性可以再用于對數(shù)據(jù)進(jìn)行分割。4.2.2樹的生長其通用的基本算法(貪心算法)為:364.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 } } }4.2.2樹的生長—算法的形式描述ProcedureBu37§4.2 樹的建模過程-34.2.3有效性和風(fēng)險性 基本的決策樹算法沒有考慮噪聲,生成的決策樹完全與訓(xùn)練例子擬合。 這樣雖然能降低算法的時間復(fù)雜度，但也使算法在

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

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

對新數(shù)據(jù)進(jìn)行準(zhǔn)確的分類或預(yù)測，出現(xiàn)了過匹配現(xiàn)象?！?.2 樹的建模過程-34.2.3有效性和風(fēng)險性384.2.3樹的剪枝

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

同時它也能使樹得到簡化而變得更容易理解。4.2.3樹的剪枝 過匹配指的是模型由于過度訓(xùn)練，導(dǎo)致其記394.2.3樹的剪枝剪枝的原則包括:奧卡姆剃刀原則——“如無必要，勿增實體”。即在與

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

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

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

需要在樹的大小與正確率之間尋找均衡點4.2.3樹的剪枝剪枝的原則包括:404.2.3樹的剪枝

常用的剪枝技術(shù)有預(yù)剪枝(pre-pruning)和后剪枝(post-pruning)兩種。

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

進(jìn)行進(jìn)一步劃分的剪枝方法

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

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

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

如CART算法等 剪枝的目的就是刪除由于噪聲數(shù)據(jù)而引起的分枝，從而避免決策樹的過匹配。4.2.3樹的剪枝 常用的剪枝技術(shù)有預(yù)剪枝(pre-pru414.2.3樹的剪枝

預(yù)剪枝中最直接而簡單的方法是事先指定決策樹生長的最大深度，使決策樹不能得到充分生長。這種停止標(biāo)準(zhǔn)一般能夠取得比較好的效果。不過指定樹的高度的方法要求用戶對數(shù)據(jù)的取值分布有較為清晰的把握，而且須對參數(shù)值進(jìn)行反復(fù)嘗試，否則無法給出一個較為合理的樹高度閾值。

4.2.3樹的剪枝 預(yù)剪枝中最直接而簡單的方法是事先指定決424.2.3樹的剪枝

后剪枝技術(shù)允許決策樹過度生長，然后根據(jù)一定的

規(guī)則，剪去決策樹中那些不具有一般代表性的葉節(jié)點或分枝。 后剪枝算法有自上而下和自下而上兩種剪枝策略。 自下而上的算法首先從最底層的內(nèi)節(jié)點開始，剪去滿足一定條件的內(nèi)節(jié)點，在生成的新決策樹上遞歸調(diào)用這個算法，直到?jīng)]有可以剪枝的節(jié)點為止。 自上而下的算法是從根節(jié)點開始向下逐個考慮節(jié)點的剪枝問題，只要節(jié)點滿足剪枝的條件就進(jìn)行剪枝。4.2.3樹的剪枝 后剪枝技術(shù)允許決策樹過度生長，然后根據(jù)434.2.3樹的剪枝

目前，決策樹修剪策略主要有三種:悲觀修剪(pessimisticpruning)，代價復(fù)雜度修剪(cost-complexitypruning)和基于最小描述長度(minimumdescriptionlength，MDL)原理的修剪。

4.2.3樹的剪枝 目前，決策樹修剪策略主要有三種:悲觀44

TOBECONTINUED……

決策樹簡介課件45決策樹第十組：

郭浩韓學(xué)成何珺

何軍黃安迪決策樹第十組：46決策樹簡介課件47決策樹簡介課件48§4.1數(shù)據(jù)分類介紹

分類是數(shù)據(jù)挖掘的一個重要課題,它的目的是：

構(gòu)造一個分類函數(shù)或分類模型,該模型能把數(shù)據(jù)庫中的數(shù)據(jù)項映射到給定類別中的某一個。 數(shù)據(jù)分類的過程一般來說主要包含兩個步驟 第一步,建立一個描述已知數(shù)據(jù)集類別或概念的模型 第二步,利用所獲得的模型進(jìn)行分類操作§4.1數(shù)據(jù)分類介紹 分類是數(shù)據(jù)挖掘的一個重要課題,它49§4.1 數(shù)據(jù)分類介紹-2第一步,建立一個描述已知數(shù)據(jù)集類別或概念的模型 該模型是通過對數(shù)據(jù)庫中各數(shù)據(jù)進(jìn)行內(nèi)容的分析而獲得的。 分類學(xué)習(xí)方法所使用的數(shù)據(jù)集稱為訓(xùn)練樣本集合，每一數(shù)據(jù)行都屬于一個確定的數(shù)據(jù)類別，其類別值是由一個屬性來描述的(被稱為類別標(biāo)記屬性)。 因此分類學(xué)習(xí)又可稱為監(jiān)督學(xué)習(xí)，它是在已知訓(xùn)練樣本類別情況下，通過學(xué)習(xí)建立相應(yīng)模型。而無監(jiān)督學(xué)習(xí)則是在訓(xùn)練樣本的類別與類別個數(shù)均未知的情況下進(jìn)行的，如聚類分析?！?.1 數(shù)據(jù)分類介紹-2第一步,建立一個描述已知數(shù)據(jù)集50§4.1 數(shù)據(jù)分類介紹-2第二步,利用所獲得的模型進(jìn)行分類操作 首先對模型分類準(zhǔn)確率進(jìn)行估計。 模型的準(zhǔn)確性可以通過由該模型所正確分類的測試樣本個數(shù)所占總測試樣本的比例得到。即對于每一個測試樣本，比較其已知的類別與學(xué)習(xí)所獲模型的預(yù)測類別。如果一個學(xué)習(xí)所獲模型的準(zhǔn)確率經(jīng)測試被認(rèn)為是可以

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

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

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

類別(屬性)取值。

§4.1 數(shù)據(jù)分類介紹-2第二步,利用所獲得的模型進(jìn)行分51由訓(xùn)練數(shù)據(jù)產(chǎn)生分類規(guī)則由訓(xùn)練數(shù)據(jù)產(chǎn)生分類規(guī)則52由分類規(guī)則對新的樣本數(shù)據(jù)進(jìn)行分類由分類規(guī)則對新的樣本數(shù)據(jù)進(jìn)行分類53§4.1 決策樹介紹-2常用的分類預(yù)測算法：決策樹歸納分類貝葉斯分類基于規(guī)則的分類用后向傳播分類遺傳算法、粗糙集方法、模糊集方法§4.1 決策樹介紹-2常用的分類預(yù)測算法：54§4.1 決策樹介紹-24.1.1決策樹的基本知識決策樹方法最早產(chǎn)生于20世紀(jì)60年代，是由Hunt等人研究人類概念建模時建立的學(xué)習(xí)系統(tǒng)CLS(conceptlearningsystem)。到了70年代末，

J.RossQuinlan提出ID3算法，引進(jìn)信息論中的有關(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ī)則等方面作了較大的改進(jìn)，C5.0是C4.5的商業(yè)改進(jìn)版?！?.1 決策樹介紹-24.1.1決策樹的基本知識55例子關(guān)于上mooc的例子例子關(guān)于上mooc的例子56例子例子57決策樹簡介課件584.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í)。4.1.1決策樹的基本知識 決策樹技術(shù)發(fā)現(xiàn)數(shù)據(jù)模式和規(guī)則的594.1.1決策樹的基本知識-2

歸納學(xué)習(xí)存在一個基本假定:

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

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

這個假定是歸納學(xué)習(xí)有效性的前提條件。4.1.1決策樹的基本知識-2 歸納學(xué)習(xí)存在一個基本假定:604.1.1決策樹的基本知識-2

歸納可以分為自下而上、自上而下和雙向搜索三種方式 自下而上法一次處理一個輸入對象，將描述逐步

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

找到一些滿足一定要求的最優(yōu)的描述。 雙向搜索方式則是這兩者的結(jié)合。4.1.1決策樹的基本知識-2 歸納可以分為自下而上、自上614.1.1決策樹的基本知識-2

先根據(jù)訓(xùn)練子集形成決策樹，如果該樹不能對所有對象給出正確的分類，那么選擇一些例外

加入到訓(xùn)練集中，重復(fù)該過程一直到形成正確的決策集。 最終結(jié)果是“一棵樹”，各分枝對應(yīng)某種屬性的某一可能值。4.1.1決策樹的基本知識-2 先根據(jù)訓(xùn)練子集形成決策樹，624.1.1決策樹的基本知識

決策樹通常有兩大類型，分別為分類決策樹和

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

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

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

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

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

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

兩類，則稱之為布爾決策樹。4.1.1決策樹的基本知識 決策樹通常有兩大類型，分別為分634.1.1決策樹的基本知識

決策樹學(xué)習(xí)是應(yīng)用最廣的歸納推理算法之一。它是一種逼近離散函數(shù)值的方法，分類精度高，操作簡單，并且對噪聲數(shù)據(jù)有很好的穩(wěn)健性，因而成為比較實用且比較流行的數(shù)據(jù)挖掘算法。 它的最大優(yōu)點是，在學(xué)習(xí)過程中不需要使用者了解很多背景知識，只要訓(xùn)練樣本集能夠用“屬性-值”的方式表達(dá)

出來就能使用決策樹學(xué)習(xí)算法來分類。4.1.1決策樹的基本知識 決策樹學(xué)習(xí)是應(yīng)用最廣的歸納推理644.1.1決策樹的基本知識4.2.4屬性選擇

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

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

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

數(shù)值字段;

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

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

適用于種類和數(shù)值字段等等。4.1.1決策樹的基本知識4.2.4屬性選擇654.1.1決策樹的基本知識-2決策樹方法的(相對)優(yōu)點:可以生成可理解的規(guī)則

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

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

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

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

是一個有待研究的課題。4.1.1決策樹的基本知識-2決策樹方法的缺點:674.1.1決策樹的基本知識-2決策樹學(xué)習(xí)算法適用的問題:樣本可以用“屬性-值”的方式來描述目標(biāo)函數(shù)的輸出值為離散值訓(xùn)練數(shù)據(jù)中允許包含有錯誤:

樣本的分類錯誤或?qū)傩灾靛e誤都允許訓(xùn)練數(shù)據(jù)中有樣本屬性值缺失4.1.1決策樹的基本知識-2決策樹學(xué)習(xí)算法適用的問題:68§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)濟(jì)和社會效益。

國內(nèi)目前有關(guān)決策樹的研究多是圍繞算法的改進(jì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ī)療政策分析等?！?.1 決策樹介紹-24.1.2決策樹的應(yīng)用和發(fā)展趨勢69§4.2樹的建模過程§4.2樹的建模過程70決策樹簡介課件71§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)容§4.2 樹的建模過程 決策樹算法通過構(gòu)造決策樹來發(fā)現(xiàn)數(shù)據(jù)72§4.2 樹的建模過程—總體步驟決策樹的構(gòu)造基本可以分為如下兩步:決策樹的生成 決策樹的生成是指由訓(xùn)練樣本數(shù)據(jù)集生成決策樹的過程。一般情況下，訓(xùn)練樣本數(shù)據(jù)集是根據(jù)實際需要由實際的歷史數(shù)據(jù)生成的、有一定綜合程度的、用于數(shù)據(jù)分析處理的

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

校正和修正的過程，主要是采用新的樣本數(shù)據(jù)集(測試數(shù)據(jù)集)中的數(shù)據(jù)檢驗決策樹生成過程中產(chǎn)生的初步規(guī)則，將那些影響預(yù)測準(zhǔn)確性的分枝剪除。一般情況下，根據(jù)測試數(shù)據(jù)集中的每一元組對生成的規(guī)則進(jìn)行預(yù)測準(zhǔn)確性的檢驗，如果預(yù)測準(zhǔn)確性過低，則將該分枝剪除?！?.2 樹的建模過程—總體步驟決策樹的構(gòu)造基本可以分為如73§4.2 樹的建模過程4.2.1數(shù)據(jù)要求(數(shù)據(jù)準(zhǔn)備)

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

減少學(xué)習(xí)過程可能出現(xiàn)相互矛盾情況的問題。4.2.1數(shù)據(jù)準(zhǔn)備數(shù)據(jù)清洗754.2.1數(shù)據(jù)準(zhǔn)備相關(guān)分析 由于數(shù)據(jù)集中的許多屬性與挖掘任務(wù)本身可能是無關(guān)的，例如記錄銀行貸款申請(單)填寫時的星期數(shù)(屬性)，就可能與申請成功與否的描述無關(guān)。此外，有些屬性也可能是冗余的。因此需要對數(shù)據(jù)進(jìn)行相關(guān)分析，以使在學(xué)習(xí)階段之前就消除無關(guān)或冗余屬性。在機(jī)器學(xué)習(xí)中，這一相關(guān)分析步驟被稱為屬性選擇(featureselection)，包含與挖掘任務(wù)無關(guān)的屬性可能會減緩甚至誤導(dǎo)整個學(xué)習(xí)過程。4.2.1數(shù)據(jù)準(zhǔn)備相關(guān)分析764.2.1數(shù)據(jù)準(zhǔn)備數(shù)據(jù)轉(zhuǎn)換 利用概念層次樹，數(shù)據(jù)能夠被泛化到更高的層次。概念層次樹對連續(xù)數(shù)值的轉(zhuǎn)換非常有效。例如，屬性“收入”的數(shù)值就可以被泛化為若干離散區(qū)間，諸如低、中和高。由于泛化操作壓縮了原來的數(shù)據(jù)集，從而可以幫助有效減少學(xué)習(xí)過程所涉及的輸入輸出操作。4.2.1數(shù)據(jù)準(zhǔn)備數(shù)據(jù)轉(zhuǎn)換77§4.2 樹的建模過程4.2.2樹的生長 決策樹算法是一種常用的數(shù)據(jù)挖掘算法，它是從

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

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

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

(conceptlearningsystem，CLS)是最早的決策樹算法，以后的許多決策樹算法都是對CLS算法的改進(jìn)或由CLS衍生而來。目前，利用決策樹進(jìn)行數(shù)據(jù)分類的方法已經(jīng)被深入研究，并且形成了許多決策樹算法?！?.2 樹的建模過程4.2.2樹的生長784.2.2樹的生長

決策樹是“一棵樹”，它的根節(jié)點是整個數(shù)據(jù)集合空間，每個分節(jié)點是對一個單一變量(屬性)的測試，該測試將數(shù)據(jù)集合空間分割成兩個或更多塊。每個葉節(jié)點是屬于單一類別的記錄。

4.2.2樹的生長 決策樹是“一棵樹”，它的根節(jié)點是整個數(shù)794.2.2樹的生長

通常,通過自上而下遞歸分割的過程來構(gòu)建決策樹,分為三個步驟:(1)尋找初始分裂。整個訓(xùn)練集作為產(chǎn)生決策樹的集合，

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

內(nèi)的記錄都屬于同一類，或達(dá)到其他停止準(zhǔn)則。(3)數(shù)據(jù)的修剪。去掉一些可能是噪音或者異常的數(shù)據(jù)或節(jié)點4.2.2樹的生長 通常,通過自上而下遞歸分割的過程來構(gòu)804.2.2樹的生長其通用的基本算法(貪心算法)為:

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

類別或沒有屬性可以再用于對數(shù)據(jù)進(jìn)行分割。4.2.2樹的生長其通用的基本算法(貪心算法)為:814.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 } } }4.2.2樹的生長—算法的形式描述Procedur