決策樹簡介ppt課件

1、 決策樹第十組： 郭浩 韓學成 何珺 何軍 黃安迪.4.1 數(shù)據(jù)分類引見分類是數(shù)據(jù)發(fā)掘的一個重要課題, 它的目的是：構(gòu)造一個分類函數(shù)或分類模型, 該模型能把數(shù)據(jù)庫中的數(shù)據(jù)項映射到給定類別中的某一個。數(shù)據(jù)分類的過程普通來說主要包含兩個步驟第一步, 建立一個描畫知數(shù)據(jù)集類別或概念的模型第二步, 利用所獲得的模型進展分類操作.4.1 數(shù)據(jù)分類引見-2第一步, 建立一個描畫知數(shù)據(jù)集類別或概念的模型該模型是經(jīng)過對數(shù)據(jù)庫中各數(shù)據(jù)進展內(nèi)容的分析而獲得的。分類學習方法所運用的數(shù)據(jù)集稱為訓練樣本集合，每一數(shù)據(jù)行都屬于一個確定的數(shù)據(jù)類別，其類別值是由一個屬性來描畫的(被稱為類別標志屬性)。因此分類學習又可稱為監(jiān)視

2、學習，它是在知訓練樣本類別情況下，經(jīng)過學習建立相應模型。而無監(jiān)視學習那么是在訓練樣本的類別與類別個數(shù)均未知的情況下進展的，如聚類分析。.4.1 數(shù)據(jù)分類引見-2第二步, 利用所獲得的模型進展分類操作首先對模型分類準確率進展估計。模型的準確性可以經(jīng)過由該模型所正確分類的測試樣本個數(shù)所占總測試樣本的比例得到。即對于每一個測試樣本，比較其知的類別與學習所獲模型的預測類別。 假設一個學習所獲模型的準確率經(jīng)測試被以為是可以接受的，那么就可以運用這一模型對未來數(shù)據(jù)行或?qū)ο?其類別未知)進展分類，即利用學習所獲得的模型進展預測，對未知類別的數(shù)據(jù)行或?qū)ο笈袆e其類別(屬性)取值。 .由訓練數(shù)據(jù)產(chǎn)生分類規(guī)那么.由

3、分類規(guī)那么對新的樣本數(shù)據(jù)進展分類.4.1 決策樹引見-2常用的分類預測算法： 決策樹歸納分類 貝葉斯分類 基于規(guī)那么的分類 用后向傳播分類 遺傳算法、粗糙集方法、模糊集方法.4.1 決策樹引見-24.1.1 決策樹的根本知識 決策樹方法最早產(chǎn)生于20世紀60年代，是由Hunt等人研討人類概念建模時建立的學習系統(tǒng)CLS(concept learning system)。到了70年代末，J. Ross Quinlan提出ID3算法，引進信息論中的有關思想，提出用信息增益(information gain)作為特征判別才干的度量，來選擇屬性作為決策樹的節(jié)點，并將建樹的方法嵌在一個迭代的程序之中。當時

4、他的主要目的在于減少樹的深度，卻忽略了葉子數(shù)目的研討。1975年和1984年，分別有人提出了CHAID和CART算法。1986年，J. C. Schlinner提出ID4算法。1988年，P. E. Utgoff 提出ID5R算法。1993年，Quinlan本人以ID3算法為根底研討出C4.5算法。新算法在對預測變量的缺失值處置、剪枝技術、派生規(guī)那么等方面作了較大的改良，C5.0是C4.5的商業(yè)改良版。.例子關于上mooc的例子.例子.4.1.1 決策樹的根本知識決策樹技術發(fā)現(xiàn)數(shù)據(jù)方式和規(guī)那么的中心是歸納算法。歸納是從特殊到普通的過程。歸納推理從假設干個現(xiàn)實表征出的特征、特性或?qū)傩灾? 經(jīng)過比

5、較、總結(jié)、概括而得出一個規(guī)律性的結(jié)論。歸納學習的過程就是尋覓普通化描畫(歸納斷言)的過程。這種普通化描畫可以解釋給定的輸入數(shù)據(jù)，并可以用來預測新的數(shù)據(jù)。歸納學習由于依賴于閱歷數(shù)據(jù)，因此又稱作閱歷學習。.4.1.1 決策樹的根本知識-2歸納學習存在一個根本假定: 任一模型假設能在足夠大的訓練樣本集中很好地逼近目的函數(shù)，那么它也能在未見樣本中很好地逼近目的函數(shù)。這個假定是歸納學習有效性的前提條件。.4.1.1 決策樹的根本知識-2歸納可以分為自下而上、自上而下和雙向搜索三種方式自下而上法一次處置一個輸入對象，將描畫逐漸普通化，直到最終的普通化描畫。自上而下法那么對能夠的普通化描畫集進展搜索，試圖找

6、到一些滿足一定要求的最優(yōu)的描畫。雙向搜索方式那么是這兩者的結(jié)合。.4.1.1 決策樹的根本知識-2先根據(jù)訓練子集構(gòu)成決策樹，假設該樹不能對一切對象給出正確的分類，那么選擇一些例外參與到訓練集中，反復該過程不斷到構(gòu)成正確的決策集。最終結(jié)果是“一棵樹，各分枝對應某種屬性的某一能夠值。.4.1.1 決策樹的根本知識決策樹通常有兩大類型，分別為分類決策樹和回歸決策樹。分類決策樹用來實現(xiàn)對定類或定序目的變量的分類，回歸決策樹那么完成對定距目的變量取值的預測。根據(jù)決策樹各種不同的屬性，可分為以下幾類: 決策樹內(nèi)節(jié)點的測試屬性能夠是單變量的，即每個內(nèi)節(jié)點只包含一個 屬性; 也能夠是多變量的，既存在包含多個屬

7、性的內(nèi)節(jié)點。 測試屬性的不同屬性值的個數(shù)，能夠使得每個內(nèi)節(jié)點有兩個或多個 分枝。假設一棵決策樹每個內(nèi)節(jié)點只需兩個分枝那么稱之為二叉 決策樹，如由CART算法生成的決策樹。 每個屬性能夠是值類型(延續(xù)值)，也能夠是枚舉類型(離散值)。 分類結(jié)果既能夠是兩類也有能夠是多類，假設二叉決策樹的結(jié)果只需 兩類，那么稱之為布爾決策樹。.4.1.1 決策樹的根本知識決策樹學習是運用最廣的歸納推理算法之一。它是一種逼近離散函數(shù)值的方法，分類精度高，操作簡單，并且對噪聲數(shù)據(jù)有很好的穩(wěn)健性，因此成為比較適用且比較流行的數(shù)據(jù)發(fā)掘算法。它的最大優(yōu)點是，在學習過程中不需求運用者了解很多背景知識，只需訓練樣本集可以用“屬

8、性-值的方式表達出來就能運用決策樹學習算法來分類。.4.1.1 決策樹的根本知識4.2.4 屬性選擇屬性選擇的統(tǒng)計度量(又稱為分枝目的splitting index，SI )的計算是決策樹構(gòu)建算法的關鍵。不同的決策樹算法采用不同的統(tǒng)計度量，主要有: 信息增益Information Gain ( ID3和C4.5算法運用)， 一切屬性假設都是種類字段，經(jīng)過修正之后可以適用于 數(shù)值字段; 基尼指數(shù)Gini index(即Gini目的) CART算法、CHAID算法和SLIQ算法運用 適用于種類和數(shù)值字段等等。.4.1.1 決策樹的根本知識-2決策樹方法的(相對)優(yōu)點:可以生成可了解的規(guī)那么數(shù)據(jù)發(fā)掘

9、產(chǎn)生的方式的可了解度是判別數(shù)據(jù)發(fā)掘算法的主要目的之一，相比于一些數(shù)據(jù)發(fā)掘算法，決策樹算法產(chǎn)生的規(guī)那么比較容易了解，并且決策樹模型的建立過程也很直觀。計算量較小。可以處置延續(xù)和集合屬性。決策樹的輸出包含屬性的排序生成決策樹時，按照最大信息增益選擇測試屬性，因此，在決策樹中可以大致判別屬性的相對重要性。.4.1.1 決策樹的根本知識-2決策樹方法的缺陷:對于具有延續(xù)值的屬性預測比較困難。 -對于順序相關的數(shù)據(jù)，需求很多預處置的任務。當類別太多時，通常會添加誤差分枝間的拆分不夠平滑，進展拆分時，不思索其對未來拆分的影響。缺值數(shù)據(jù)處置問題: 由于決策樹進展分類預測時，完全基于數(shù)據(jù)的測試屬性，所以對于測

10、試屬性缺失的數(shù)據(jù)，決策樹將無法處置。通常僅根據(jù)單個屬性來分類: 決策樹方法根據(jù)單個屬性對數(shù)據(jù)進展分類，而在實踐的分類系統(tǒng)中，類的劃分不僅僅與單個屬性有關，往往與一個屬性集有關。因此，將決策樹算法推行到思索多屬性是一個有待研討的課題。.4.1.1 決策樹的根本知識-2決策樹學習算法適用的問題:樣本可以用“屬性-值的方式來描畫目的函數(shù)的輸出值為離散值訓練數(shù)據(jù)中允許包含有錯誤: 樣本的分類錯誤或?qū)傩灾靛e誤都允許訓練數(shù)據(jù)中有樣本屬性值缺失.4.1 決策樹引見-24.1.2 決策樹的運用和開展趨勢決策樹由于構(gòu)造簡單、效率高等優(yōu)點而獲得了廣泛的運用。決策樹在商業(yè)、工業(yè)、天文、醫(yī)學、風險分析、社會科學和分類

11、學等領域的運用曾經(jīng)獲得了很好的經(jīng)濟和社會效益。國內(nèi)目前有關決策樹的研討多是圍繞算法的改良以及決策樹在商業(yè)、工業(yè)等領域的運用。 在商業(yè)領域，決策樹方法所能處理的典型商業(yè)問題有:客戶關系 管理、數(shù)據(jù)庫營銷、客戶群體劃分、交叉銷售等市場分析 行為，以及客戶流失分析、客戶信譽計分及欺詐發(fā)現(xiàn)，等等。 在工業(yè)領域，決策樹可以用于缺點診斷、工業(yè)消費過程控制等。 在醫(yī)學領域，決策樹方法可用于疾病診斷治疔、 基因與高分子序列分析、醫(yī)院信息系統(tǒng)發(fā)掘及醫(yī)療政策分析等。.4.2 樹的建模過程.4.2 樹的建模過程決策樹算法經(jīng)過構(gòu)造決策樹來發(fā)現(xiàn)數(shù)據(jù)中蘊涵的分類規(guī)那么，包含許多種不同的算法，主要可以分為三類:(1)基于統(tǒng)

12、計學實際的方法，以CART為代表，在這類算法中，對于非終端節(jié)點來說，有兩個分枝;(2)基于信息實際的方法，以ID3算法為代表，此類算法中，非終端的節(jié)點的分枝由樣本類別個數(shù)決議;(3)以AID，CHAD為代表的算法，在此類算法中，非終端節(jié)點的分枝數(shù)在2至樣本類別個數(shù)范圍內(nèi)分布。這些算法在分類中運用的過程與思想根本上是一致的。如何構(gòu)造精度高、規(guī)模小的決策樹是決策樹算法的中心內(nèi)容.4.2 樹的建模過程總體步驟決策樹的構(gòu)造根本可以分為如下兩步:決策樹的生成決策樹的生成是指由訓練樣本數(shù)據(jù)集生成決策樹的過程。普通情況下，訓練樣本數(shù)據(jù)集是根據(jù)實踐需求由實踐的歷史數(shù)據(jù)生成的、有一定綜合程度的、用于數(shù)據(jù)分析處置

13、的數(shù)據(jù)集。決策樹的剪枝決策樹剪枝是對上一階段所生成的決策樹進展檢驗、校正和修正的過程，主要是采用新的樣本數(shù)據(jù)集(測試數(shù)據(jù)集)中的數(shù)據(jù)檢驗決策樹生成過程中產(chǎn)生的初步規(guī)那么，將那些影響預測準確性的分枝剪除。普通情況下，根據(jù)測試數(shù)據(jù)集中的每一元組對生成的規(guī)那么進展預測準確性的檢驗，假設預測準確性過低，那么將該分枝剪除。.4.2 樹的建模過程4.2.1 數(shù)據(jù)要求(數(shù)據(jù)預備)在進展分類和預測發(fā)掘之前，首先必需預備好有關發(fā)掘數(shù)據(jù)。普通需求對數(shù)據(jù)進展以下預處置，以協(xié)助提高分類和預測過程的準確性、有效性和可伸縮性。主要的任務包括： 數(shù)據(jù)清洗 相關分析 數(shù)據(jù)轉(zhuǎn)換.4.2.1 數(shù)據(jù)預備數(shù)據(jù)清洗這一數(shù)據(jù)預處置步驟，

14、主要是協(xié)助除去數(shù)據(jù)中的噪聲，并妥善處理缺失數(shù)據(jù)問題，雖然大多數(shù)分類算法都包含一些處置噪聲和缺失數(shù)據(jù)的方法，但這一預處置步驟可以有效減少學習過程能夠出現(xiàn)相互矛盾情況的問題。 .4.2.1 數(shù)據(jù)預備相關分析由于數(shù)據(jù)集中的許多屬性與發(fā)掘義務本身能夠是無關的，例如記錄銀行貸款懇求(單)填寫時的星期數(shù)(屬性)，就能夠與懇求勝利與否的描畫無關。此外，有些屬性也能夠是冗余的。因此需求對數(shù)據(jù)進展相關分析，以使在學習階段之前就消除無關或冗余屬性。在機器學習中，這一相關分析步驟被稱為屬性選擇(feature selection) ，包含與發(fā)掘義務無關的屬性能夠會減緩甚至誤導整個學習過程。.4.2.1 數(shù)據(jù)預備數(shù)據(jù)

15、轉(zhuǎn)換利用概念層次樹，數(shù)據(jù)可以被泛化到更高的層次。概念層次樹對延續(xù)數(shù)值的轉(zhuǎn)換非常有效。例如，屬性“收入的數(shù)值就可以被泛化為假設干離散區(qū)間，諸如低、中和高。由于泛化操作緊縮了原來的數(shù)據(jù)集，從而可以協(xié)助有效減少學習過程所涉及的輸入輸出操作。.4.2 樹的建模過程4.2.2 樹的生長決策樹算法是一種常用的數(shù)據(jù)發(fā)掘算法，它是從機器學習領域中逐漸開展起來的一種分類函數(shù)逼近方法。決策樹學習的根本算法是貪婪算法，采用自上而下的遞歸方式構(gòu)造決策樹。Hunt等人于1966年提出的概念學習系統(tǒng)(concept learning system ，CLS)是最早的決策樹算法，以后的許多決策樹算法都是對CLS算法的改良或

16、由CLS衍生而來。目前，利用決策樹進展數(shù)據(jù)分類的方法曾經(jīng)被深化研討，并且構(gòu)成了許多決策樹算法。.4.2.2 樹的生長決策樹是“一棵樹，它的根節(jié)點是整個數(shù)據(jù)集合空間，每個分節(jié)點是對一個單一變量(屬性)的測試，該測試將數(shù)據(jù)集合空間分割成兩個或更多塊。每個葉節(jié)點是屬于單一類別的記錄。.4.2.2 樹的生長通常, 經(jīng)過自上而下遞歸分割的過程來構(gòu)建決策樹, 分為三個步驟:(1) 尋覓初始分裂。整個訓練集作為產(chǎn)生決策樹的集合， 訓練集每個記錄必需是曾經(jīng)分好類的。決議哪個屬性(field)域作為目前最好的分類目的。普通的做法是窮盡一切的屬性域，對每個屬性域分裂的好壞做出量化，計算出最好的一個分裂。(2) 樹

17、增長到一棵完好的樹。反復第一步，直至每個葉節(jié)點 內(nèi)的記錄都屬于同一類，或到達其他停頓準那么。(3)數(shù)據(jù)的修剪。去掉一些能夠是噪音或者異常的數(shù)據(jù)或節(jié)點.4.2.2 樹的生長其通用的根本算法(貪婪算法)為:以自上而下分而治之的方法，開場時，一切的數(shù)據(jù)都在根節(jié)點;屬性都是種類字段(假設是延續(xù)的，將其離散化); 一切記錄用所選屬性遞歸地進展分割; 屬性的選擇是基于一個啟發(fā)式規(guī)那么或者一個統(tǒng)計的度量(如information gain)。停頓分割的條件: 一個節(jié)點上的數(shù)據(jù)都是屬于同一個類別或沒有屬性可以再用于對數(shù)據(jù)進展分割。 .4.2.2 樹的生長算法的方式描畫Procedure BuildTree(S

18、)用數(shù)據(jù)集S 初始化根節(jié)點 R用根節(jié)點R 初始化隊列 QWhi1e Q is not Empty, do取出隊列Q中的第一個節(jié)點Nif N 不純(impure)for 每一個屬性 A估計該節(jié)點在A上的信息增益選出最正確的屬性, 將N分裂為N1,N2.4.2 樹的建模過程-34.2.3 有效性和風險性根本的決策樹算法沒有思索噪聲, 生成的決策樹完全與訓練例子擬合。這樣雖然能降低算法的時間復雜度，但也使算法在較深層次的樣本劃分中，專注于訓練樣本集某個子集的統(tǒng)計信息，而忽視各類樣本的整體分布情況，呵斥了對噪聲敏感。所以，雖然一棵完好的決策樹可以非常準確地反映訓練樣本集中數(shù)據(jù)的特征，但因失去了普通代表

19、性而無法對新數(shù)據(jù)進展準確的分類或預測，出現(xiàn)了過匹配景象。.4.2.3 樹的剪枝過匹配指的是模型由于過度訓練，導致其記住的不是訓練數(shù)據(jù)的普通特性，而是訓練集的部分特性。當將這個模型運用到新的測試集上時就導致預測結(jié)果的不準確。因此，一個完好的決策樹構(gòu)造過程將包含決策樹的創(chuàng)建和決策樹的剪枝這兩方面。剪枝是一種抑制噪聲的技術，用于處理過匹配問題，同時它也能使樹得到簡化而變得更容易了解。.4.2.3 樹的剪枝剪枝的原那么包括:奧卡姆剃刀原那么“如無必要，勿增實體。即在與察看相容的情況下，應中選擇最簡單的一棵決策樹。決策樹越小就越容易了解，其存儲與傳輸?shù)拇鷥r也就越小。決策樹越復雜，節(jié)點越多，每個節(jié)點包含的訓練樣本個數(shù)越少，那么支持每個節(jié)點的假設的樣本個數(shù)就越少，能夠?qū)е聸Q策樹在測試集上的分類錯誤率就會增大。但決策樹過小也會導致錯誤率較大。因此，需求在樹的大小與正確率之間尋覓平衡點.4.2.3 樹的剪枝常用的剪枝技術有預剪枝(pre-pruning