《數(shù)據(jù)分類決策樹》PPT課件

2020/5/16,1,數(shù)據(jù)倉庫與數(shù)據(jù)挖掘技術,五邑大學信息學院2009.06,何國輝教授,2020/5/16,2,第5章決策樹和決策規(guī)則,5.1引例,分類的定義分類是指把數(shù)據(jù)樣本映射到一個事先定義的類中的學習過程，即給定一組輸入的屬性向量及其對應的類，用基于歸納的學習算法得出分類。,2020/5/16,3,描述屬性,類別屬性,分類問題使用的數(shù)據(jù)集格式：,2020/5/16,4,5.1引例,分類問題使用的數(shù)據(jù)集格式描述屬性可以是連續(xù)型屬性，也可以是離散型屬性；而類別屬性必須是離散型屬性。連續(xù)型屬性是指在某一個區(qū)間或者無窮區(qū)間內該屬性的取值是連續(xù)的，例如屬性“Age”離散型屬性是指該屬性的取值是不連續(xù)的，例如屬性“Salary”和“Class”,2020/5/16,5,5.1引例,分類問題使用的數(shù)據(jù)集格式分類問題中使用的數(shù)據(jù)集可以表示為X=(xi,yi)|i=1,2,totalxi=(xi1,xi2,xid)，其中xi1,xi2,xid分別對應d個描述屬性A1,A2,Ad的具體取值yi表示數(shù)據(jù)樣本xi的類標號，假設給定數(shù)據(jù)集包含m個類別，則yic1,c2,cm，其中c1,c2,cm是類別屬性C的具體取值未知類標號的數(shù)據(jù)樣本x用d維特征向量x=(x1,x2,xd)來表示,2020/5/16,6,5.2分類問題概述,5.2.1分類的過程5.2.2分類的評價準則,2020/5/16,7,5.2.1分類的過程,2020/5/16,8,5.2.1分類的過程,獲取數(shù)據(jù)輸入數(shù)據(jù)、對數(shù)據(jù)進行量化預處理去除噪聲數(shù)據(jù)、對空缺值進行處理數(shù)據(jù)集成或者變換分類器設計劃分數(shù)據(jù)集、分類器構造、分類器測試分類決策對未知類標號的數(shù)據(jù)樣本進行分類,2020/5/16,9,5.2.2分類的評價準則,給定測試集Xtest=(xi,yi)|i=1,2,NN表示測試集中的樣本個數(shù)xi表示測試集中的數(shù)據(jù)樣本yi表示數(shù)據(jù)樣本xi的類標號對于測試集的第j個類別，假設被正確分類的樣本數(shù)量為TPj被錯誤分類的樣本數(shù)量為FNj其他類別被錯誤分類為該類的樣本數(shù)據(jù)量為FPj,2020/5/16,10,5.2.2分類的評價準則,精確度：代表測試集中被正確分類的數(shù)據(jù)樣本所占的比例,2020/5/16,11,5.2.2分類的評價準則,查全率：表示在本類樣本中被正確分類的樣本所占的比例查準率：表示被分類為該類的樣本中，真正屬于該類的樣本所占的比例,2020/5/16,12,5.2.2分類的評價準則,F-measure(加權調合平均數(shù))：是查全率和查準率的組合表達式是可以調節(jié)的，通常取值為1,2020/5/16,13,5.2.2分類的評價準則,幾何均值：是各個類別的查全率的平方根,2020/5/16,14,決策樹方法的起源是亨特（Hunt，1966）的概念學習系統(tǒng)CLS方法，然后發(fā)展到由Quinlan研制ID3方法，然后到著名的C4.5算法，C4.5算法的一個優(yōu)點是它能夠處理連續(xù)屬性。還有CART算法和Assistant算法也是比較有名的決策樹方法。,5.3決策樹,2020/5/16,15,決策樹的優(yōu)點：進行分類器設計時，決策樹分類方法所需時間相對較少決策樹的分類模型是樹狀結構，簡單直觀，比較符合人類的理解方式可以將決策樹中到達每個葉節(jié)點的路徑轉換為IFTHEN形式的分類規(guī)則，這種形式更有利于理解,2020/5/16,16,1.什么是決策樹決策樹（DecisionTree）又稱為判定樹，是運用于分類的一種樹結構。其中的每個內部結點（internalnode）代表對某個屬性的一次測試，每條邊代表一個測試結果，葉結點（leaf）代表某個類（class）或者類的分布（classdistribution），最上面的結點是根結點。決策樹提供了一種展示類似在什么條件下會得到什么值這類規(guī)則的方法。下例是為了解決這個問題而建立的一棵決策樹，從中可以看到?jīng)Q策樹的基本組成部分：決策結點、分支和葉結點。,2020/5/16,17,例圖5-2給出了一個商業(yè)上使用的決策樹的例子。它表示了一個關心電子產(chǎn)品的用戶是否會購買PC（buys_computer）的知識，用它可以預測某條記錄（某個人）的購買意向。,圖5-2buys_computer的決策樹,2020/5/16,18,這棵決策樹對銷售記錄進行分類，指出一個電子產(chǎn)品消費者是否會購買一臺計算機“buys_computer”。每個內部結點（方形框）代表對某個屬性的一次檢測。每個葉結點（橢圓框）代表一個類：buys_computers=yes或者buys_computers=no在這個例子中，樣本向量為：（age,student,credit_rating;buys_computers）被決策數(shù)據(jù)的格式為:（age,student,credit_rating）輸入新的被決策的記錄，可以預測該記錄隸屬于哪個類。,2020/5/16,19,2.使用決策樹進行分類構造決策樹是采用自上而下的遞歸構造方法。以多叉樹為例，如果一個訓練數(shù)據(jù)集中的數(shù)據(jù)有幾種屬性值，則按照屬性的各種取值把這個訓練數(shù)據(jù)集再劃分為對應的幾個子集（分支），然后再依次遞歸處理各個子集。反之，則作為葉結點。決策樹構造的結果是一棵二叉或多叉樹，它的輸入是一組帶有類別標記的訓練數(shù)據(jù)。二叉樹的內部結點（非葉結點）一般表示為一個邏輯判斷，如形式為(a=b)的邏輯判斷，其中a是屬性，b是該屬性的某個屬性值；樹的邊是邏輯判斷的分支結果。多叉樹（ID3）的內部結點是屬性，邊是該屬性的所有取值，有幾個屬性值，就有幾條邊。樹的葉結點都是類別標記。,2020/5/16,20,使用決策樹進行分類分為兩步：第1步：利用訓練集建立并精化一棵決策樹，建立決策樹模型。這個過程實際上是一個從數(shù)據(jù)中獲取知識，進行機器學習的過程。第2步：利用生成完畢的決策樹對輸入數(shù)據(jù)進行分類。對輸入的記錄，從根結點依次測試記錄的屬性值，直到到達某個葉結點，從而找到該記錄所在的類。,2020/5/16,21,問題的關鍵是建立一棵決策樹。這個過程通常分為兩個階段：建樹（TreeBuilding）：決策樹建樹算法見下，這是一個遞歸的過程，最終將得到一棵樹。剪枝（TreePruning）：剪枝的目的是降低由于訓練集存在噪聲而產(chǎn)生的起伏。,2020/5/16,22,由Quinlan在80年代中期提出的ID3算法是分類規(guī)則挖掘算法中最有影響的算法。ID3即決策樹歸納（InductionofDecisionTree）。早期的ID算法只能就兩類數(shù)據(jù)進行挖掘（如正類和反類）；經(jīng)過改進后，現(xiàn)在ID算法可以挖掘多類數(shù)據(jù)。待挖掘的數(shù)據(jù)必須是不矛盾的、一致的，也就是說，對具有相同屬性的數(shù)據(jù)，其對應的類必須是唯一的。在ID3算法挖掘后，分類規(guī)則由決策樹來表示。,5.4分類規(guī)則挖掘的ID3算法,2020/5/16,23,1.ID3算法的基本思想由訓練數(shù)據(jù)集中全體屬性值生成的所有決策樹的集合稱為搜索空間，該搜索空間是針對某一特定問題而提出的。系統(tǒng)根據(jù)某個評價函數(shù)決定搜索空間中的哪一個決策樹是“最好”的。評價函數(shù)一般依據(jù)分類的準確度和樹的大小來決定決策樹的質量。如果兩棵決策樹都能準確地在測試集進行分類，則選擇較簡單的那棵。相對而言，決策樹越簡單，則它對未知數(shù)據(jù)的預測性能越佳。尋找一棵“最好”的決策樹是一個NP完全問題。,NP完全問題是這樣的問題：用確定性的算法在多項式時間內無法解決的問題。實際之中，解決這樣的問題，往往是根據(jù)用啟發(fā)式算法，求出近似的解。,2020/5/16,24,ID3使用一種自頂向下的方法在部分搜索空間創(chuàng)建決策樹，同時保證找到一棵簡單的決策樹可能不是最簡單的。ID3算法的基本思想描述如下：step1任意選取一個屬性作為決策樹的根結點，然后就這個屬性所有的取值創(chuàng)建樹的分支；step2用這棵樹來對訓練數(shù)據(jù)集進行分類，如果一個葉結點的所有實例都屬于同一類，則以該類為標記標識此葉結點；如果所有的葉結點都有類標記，則算法終止；step3否則，選取一個從該結點到根路徑中沒有出現(xiàn)過的屬性為標記標識該結點，然后就這個屬性所有的取值繼續(xù)創(chuàng)建樹的分支；重復算法步驟step2；,2020/5/16,25,這個算法一定可以創(chuàng)建一棵基于訓練數(shù)據(jù)集的正確的決策樹，然而，這棵決策樹不一定是簡單的。顯然，不同的屬性選取順序將生成不同的決策樹。因此，適當?shù)剡x取屬性將生成一棵簡單的決策樹。在ID3算法中，采用了一種基于信息的啟發(fā)式的方法來決定如何選取屬性。啟發(fā)式方法選取具有最高信息量的屬性，也就是說，生成最少分支決策樹的那個屬性。,2020/5/16,26,算法：Generate_decision_tree由給定的訓練數(shù)據(jù)產(chǎn)生一棵決策樹輸入：訓練數(shù)據(jù)集samples，用離散值屬性表示；候選屬性的集合attribute_list。輸出：一棵決策樹方法：（1）創(chuàng)建結點N；（2）ifsamples都在同一個類Cthen（3）返回N作為葉結點，用類C標記；（4）ifattribute_list為空then（5）返回N作為葉結點，標記samples中最普通的類；/多數(shù)表決（6）選擇attribute_list中具有最高信息增益的屬性test_attribute；/用信息增益作為屬性選擇度量（7）標記結點N為test_attribute；（8）foreachtest_attribute中的已知值ai/劃分samples（9）由結點N生長出一個條件為test_attributeai的分枝；（10）設si為samples中test_attributeai的樣本集合；/一個劃分（11）ifsi為空then（12）加上一個葉結點，標記為標記samples中最普通的類；/多數(shù)表決（13）else加上一個由Generate_decision_tree（si,attribute_list-test_attribute）返回的結點；,2020/5/16,27,2.屬性選擇度量在Generate_decision_tree算法的Step6，算法需選擇attribute_list中具有最高信息增益的屬性test_attribute。ID3算法在樹的每個結點上以信息增益（informationgain）作為度量來選擇測試屬性。這種度量稱為屬性選擇度量或分裂的優(yōu)良性度量。選擇具有最高信息增益（或最大熵壓縮）的屬性作為當前結點的測試屬性。該屬性使得對結果劃分中的樣本分類所需要的信息量最小，并確保找到一棵簡單的（但不一定是最簡單的）決策樹。,2020/5/16,28,InformationGain指標的原理來自于信息論。1948年，香農(nóng)（C.E.Shannon）提出了信息論。其中給出了關于信息量（Information）和熵（Entropy）的定義，熵實際上是系統(tǒng)信息量的加權平均，也就是系統(tǒng)的平均信息量。,2020/5/16,29,假設要選擇有n個輸出（所給屬性的n個值）的檢驗，把訓練樣本集T分區(qū)成子集T1，T2，Tn。僅有的指導信息是在T和它的子集Ti中的類的分布。如果S是任意樣本集，設freq(Ci,S)代表S中屬于類Ci（k個可能的類中的一個）的樣本數(shù)量，|S|表示集合S中的樣本數(shù)量。下面給出了集合S（單位為比特）的熵計算：,以2為底的原因是：信息按二進制位編碼,2020/5/16,30,熵是一個衡量系統(tǒng)混亂程度的統(tǒng)計量。熵越大，表示系統(tǒng)越混亂。分類的目的是提取系統(tǒng)信息，使系統(tǒng)向更加有序、有規(guī)則組織的方向發(fā)展。所以最佳的分裂方案是使熵減少量最大的分裂方案。熵減少量就是InformationGain（信息增益），所以，最佳分裂就是使Gain(A)最大的分裂方案。通常，這個最佳方案是用“貪心算法+深度優(yōu)先搜索”得到的。,2020/5/16,31,現(xiàn)在考慮T被分區(qū)之后的一個相似度量標準，T按照一個屬性檢驗X的幾個輸出進行分區(qū)。所需信息可通過這些子集的熵的加權和求得：,信息增益的計算公式：Gain(X)=Info(T)-Infox(T)通過計算求出具有最高增益的屬性。,2020/5/16,32,以下分析有關度量標準的應用和創(chuàng)建決策樹的一個簡單例子，假設以平面文件形式給出的數(shù)據(jù)集T，其中有14個樣本，通過3個輸入屬性描述且屬于所給的兩個類之一：類1或類2。,2020/5/16,33,2020/5/16,34,其中：9個樣本屬于類1，5個樣本屬于類2，因此分區(qū)前的熵為：info(T)-9/14.log2(9/14)-5/14.log2(5/14)=0.940比特根據(jù)屬性1把初始樣本集分區(qū)成3個子集（檢驗x1表示從3個值A，B或C中選擇其一）后，得出結果：Infox1(T)5/14（-2/5log2(2/5)-3/5log2(3/5)）+4/14（-4/4log2(4/4)-0/4log2(0/4)）+5/14（-3/5log2(3/5)-2/5log2(2/5)）=0.694比特通過檢驗x1獲得的信息增益是：Gain(x1)=0.9400.694=0.246比特,2020/5/16,35,如果該檢驗和分區(qū)是基于屬性3的（檢驗x2表示從真或假兩個值選擇其一），類似地有：Infox2(T)6/14（-3/6log2(3/6)-3/6log2(3/6)）+8/14（-6/8log2(6/8)-2/8log2(2/8)）=0.892比特通過檢驗x2獲得的增益是：Gain(x2)=0.9400.892=0.048比特按照增益準則，將選擇x1作為分區(qū)數(shù)據(jù)庫T的最初檢驗。為了求得最優(yōu)檢驗還必須分析關于屬性2的檢驗，它是連續(xù)取值的數(shù)值型屬性。,2020/5/16,36,3.ID3算法的改進（1）離散化為了解決該問題，在用ID3算法挖掘具有連續(xù)性屬性的知識時，應該首先把該連續(xù)性屬性離散化。最簡單的方法就是把屬性值分成和兩段。如身高可以分為1米以下，1米以上或者分為1.5米以下，1.5米以上。如何選擇最佳的分段值呢？對任何一個屬性，其所有的取值在一個數(shù)據(jù)集中是有限的。假設該屬性取值為，則在這個集合中，一共存在m-1個分段值，ID3算法采用計算信息量的方法計算最佳的分段值，然后進一步構建決策樹。ID3算法的擴展是C4.5算法，C4.5算法把分類范圍從分類屬性擴展到數(shù)字屬性。,2020/5/16,37,1.C4.5算法概述C4.5算法是ID3算法的擴展，它的改進部分是：能夠處理連續(xù)型的屬性。首先將連續(xù)型屬性離散化，把連續(xù)型屬性的值分成不同的區(qū)間，依據(jù)是比較各個屬性Gian值的大小。缺失數(shù)據(jù)的考慮：在構建決策樹時，可以簡單地忽略缺失數(shù)據(jù)，即在計算增益時，僅考慮具有屬性值的記錄。提供兩種基本的剪枝策略：子樹替代法：用葉結點替代子樹。子樹上升法：用一棵子樹中最常用的子樹來代替這棵子樹。,5.5分類規(guī)則挖掘的C4.5算法,剪枝目的是降低由于訓練集存在噪聲而產(chǎn)生的起伏。,2020/5/16,38,2.離散化的方法把連續(xù)型屬性值離散化的具體方法是：1）尋找該連續(xù)型屬性的最小值，并把它賦值給MIN，尋找該連續(xù)型屬性的最大值，并把它賦值給MAX；2）設置區(qū)間MIN，MAX中的N個等分斷點Ai，它們分別是Ai=MIN+（MAXMIN）/N）*i其中，i=1,2,.,N3）分別計算把MIN，Ai和（Ai，MAX）（i=1,2,.,N）作為區(qū)間值時的Gain值，并進行比較。4）選取Gain值最大的Ak做為該連續(xù)型屬性的斷點，把屬性值設置為MIN，Ak和（Ak，MAX）兩個區(qū)間值。,2020/5/16,39,對于前面例子中的數(shù)據(jù)庫T，分析屬性2分區(qū)的可能結果，分類后得出屬性2的值的集合是：65,70,75,78,80,85,90,95,96按照C4.5算法，選擇每個區(qū)間的最小值作為閾值，即：65,70,75,78,80,85,90,95共8個值，從中選取最優(yōu)的閾值。按照前述方法選取兩區(qū)間，并分別計算其Gain值：6570757880859095如以第二種分段為例計算，計算其Gain值：,2020/5/16,40,2020/5/16,41,Infox2(T)4/14（-3/4log2(3/4)-1/4log2(1/4)）+10/14（-6/10log2(6/10)-4/10log2(4/10)）=比特Gain(x2)=0.940Infox2(T)=比特,2020/5/16,42,找到最優(yōu)的閾值（具有最高信息增益）Z=80相應的檢驗3（屬性280)的信息增益計算為：Infox3(T)9/14（-7/9log2(7/9)-2/9log2(2/9)）+5/14（-2/5log2(2/5)-3/5log2(3/5)）=0.837比特通過檢驗x3獲得的增益是：Gain(x3)=0.9400.837=0.103比特比較本例中3個屬性的信息增益，可以看出屬性1具有最高增益，選擇該屬性對決策樹的結構進行首次分區(qū)。,2020/5/16,43,T1,檢驗X1:屬性1=？,T2,T3,A,B,C,葉結點,2020/5/16,44,對于剩下的子結點T1、T3進行分析：對T1的屬性進行檢驗：最優(yōu)檢驗（具有最高的信息增益）有兩個選擇：屬性270，定義為x4。Info(T1)-2/14log2(2/5)-3/14log2(3/5)=0.940比特用屬性2把T1分成兩個子集（檢驗x4），結果信息是：Infox4(T)2/5（-2/2log2(2/2)-0/2log2(0/2)）+3/5（-0/3log2(0/3)-3/3log2(3/3)）=0比特該檢驗的信息增益最大：Gain(x4)=0.9400=0.940比特這兩個分枝將生成最終葉結點。,2020/5/16,45,對于剩下的子結點T3進行分析：對T3的屬性進行檢驗：選擇的最優(yōu)檢驗為x5對屬性3的值進行檢驗，樹的分枝是屬性3=真和屬性3=假。最終決策樹為：,2020/5/16,46,決策樹可以用偽代碼的形式表示，這種偽代碼用IF-THEN結構對決策樹進行分枝。,If屬性1=Athenif屬性2=70then類別=類1;else類別=類2;Elseif屬性1=Bthen類別=類1;elseif屬性1=Cthenif屬性3=真then類別=類2;else類別=類1.,結果,2020/5/16,47,增益標準對緊湊型決策樹的構造有很好的效果，但也存在一個嚴重缺陷：對具有多輸出的檢驗有嚴重的偏差。解決方法：根據(jù)info(S)的定義，指定一個附加的參數(shù)：,含義：通過把集T分區(qū)成n個子集Ti而生成的潛在信息。新的增益標準-增益率：Gain_ratio(X)=Gain(X)/Split_Info(X),新的增益標準表示分區(qū)所生成的有用信息的比例,2020/5/16,48,根據(jù)前面實例，求檢驗X1的增益比例。計算Split_Info(X1)Split_Info(X1)-5/14log2(5/14)-4/14log2(4/14)-5/14log2(5/14)=1.577比特計算Gain_ratio(X1)Gain_ratio(X1)=0.246/1.577=0.156檢驗過程，將采用最大增益率代替增益標準值,2020/5/16,49,在實際應用過程中，大量的現(xiàn)實世界中的數(shù)據(jù)都不是以人的意愿來定的，可能某些字段上缺值（missingvalues）；可能數(shù)據(jù)不準確含有噪聲或者是錯誤的；可能是缺少必須的數(shù)據(jù)造成了數(shù)據(jù)的不完整。解決丟失值問題有兩種選擇：拋棄數(shù)據(jù)庫中有丟失數(shù)據(jù)的樣本。定義一個新的算法或改進現(xiàn)有的算法來處理。,3.未知屬性值問題,如存在大量丟失數(shù)據(jù)?,2020/5/16,50,按照第二種選擇，必須回答幾個問題：怎樣比較具有不同數(shù)目未知值的兩個樣本？具有未知值的訓練樣本和檢驗的具體值之間沒有聯(lián)系，它們不能被分配給任何子集，該如何處理這些樣本？在分類的檢驗階段，如果檢驗有丟失值的屬性時，該怎樣處理丟失值？C4.5算法中：有未知值的樣本是按照已知值的相對頻率隨機分布的。除考慮到僅有的幾個有已知屬性值的樣本以外用系數(shù)F修正增益參數(shù)F=數(shù)據(jù)庫中一個給出的屬性值具有已知值的樣本數(shù)量/數(shù)據(jù)集中樣本數(shù)量總和,通過一些方法補充數(shù)據(jù)？,2020/5/16,51,新的增益標準：Gain(X)=F*(info(T)infox(T)同時，通過把具有未知值的樣本看作分區(qū)的一個附加組來修改Split_Info(X)。如果檢驗x有n個輸出，Split_Info(X)按照檢驗把數(shù)據(jù)集分區(qū)成n+1個子集計算。該值Split_Info(X)對修改后的標準Gain_ratio(X)的最終值有直接影響。,2020/5/16,52,2020/5/16,53,屬性1的增益計算考慮13個數(shù)據(jù)，丟失的樣本僅用來作修正，屬性1中有8個屬于類1，5個屬于類2，因此分區(qū)前的熵為：Info(T)-8/13log2(8/13)-5/13log2(5/13)=0.961比特用屬性1把T分區(qū)成3個子集（A、B、C）后，得到的信息是：Infox1(T)5/13（-2/