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

數(shù)據(jù)倉庫與數(shù)據(jù)挖掘技術(shù)

五邑大學(xué)信息學(xué)院2009.06何國輝教授12/17/20221數(shù)據(jù)倉庫與數(shù)據(jù)挖掘技術(shù)

五邑大學(xué)信息學(xué)院何國輝教授1第5章決策樹和決策規(guī)則5.1引例

分類的定義分類是指把數(shù)據(jù)樣本映射到一個事先定義的類中的學(xué)習(xí)過程，即給定一組輸入的屬性向量及其對應(yīng)的類，用基于歸納的學(xué)習(xí)算法得出分類。12/17/20222第5章決策樹和決策規(guī)則5.1引例分類的定AgeSalaryClass30highc125highc221lowc243highc118lowc233lowc1………描述屬性類別屬性分類問題使用的數(shù)據(jù)集格式：12/17/20223AgeSalaryClass30highc125highc25.1引例分類問題使用的數(shù)據(jù)集格式描述屬性可以是連續(xù)型屬性，也可以是離散型屬性；而類別屬性必須是離散型屬性。連續(xù)型屬性是指在某一個區(qū)間或者無窮區(qū)間內(nèi)該屬性的取值是連續(xù)的，例如屬性“Age”離散型屬性是指該屬性的取值是不連續(xù)的，例如屬性“Salary”和“Class”12/17/202245.1引例分類問題使用的數(shù)據(jù)集格式12/14/202245.1引例分類問題使用的數(shù)據(jù)集格式分類問題中使用的數(shù)據(jù)集可以表示為X={(xi,yi)|i=1,2,…,total}xi=(xi1,xi2,…,xid)，其中xi1,xi2,…,xid分別對應(yīng)d個描述屬性A1,A2,…,Ad的具體取值yi表示數(shù)據(jù)樣本xi的類標(biāo)號，假設(shè)給定數(shù)據(jù)集包含m個類別，則yi∈{c1,c2,…,cm}，其中c1,c2,…,cm是類別屬性C的具體取值未知類標(biāo)號的數(shù)據(jù)樣本x用d維特征向量x=(x1,x2,…,xd)來表示12/17/202255.1引例分類問題使用的數(shù)據(jù)集格式12/14/202255.2分類問題概述5.2.1分類的過程5.2.2分類的評價準(zhǔn)則12/17/202265.2分類問題概述5.2.1分類的過程12/14/205.2.1分類的過程獲取數(shù)據(jù)預(yù)處理分類器設(shè)計分類決策12/17/202275.2.1分類的過程獲取數(shù)據(jù)預(yù)處理分類器設(shè)計分類決策12/5.2.1分類的過程獲取數(shù)據(jù)輸入數(shù)據(jù)、對數(shù)據(jù)進行量化預(yù)處理去除噪聲數(shù)據(jù)、對空缺值進行處理數(shù)據(jù)集成或者變換分類器設(shè)計劃分?jǐn)?shù)據(jù)集、分類器構(gòu)造、分類器測試分類決策對未知類標(biāo)號的數(shù)據(jù)樣本進行分類12/17/202285.2.1分類的過程獲取數(shù)據(jù)12/14/202285.2.2分類的評價準(zhǔn)則給定測試集Xtest={(xi,yi)|i=1,2,…,N}N表示測試集中的樣本個數(shù)xi表示測試集中的數(shù)據(jù)樣本yi表示數(shù)據(jù)樣本xi的類標(biāo)號對于測試集的第j個類別，假設(shè)被正確分類的樣本數(shù)量為TPj被錯誤分類的樣本數(shù)量為FNj其他類別被錯誤分類為該類的樣本數(shù)據(jù)量為FPj12/17/202295.2.2分類的評價準(zhǔn)則給定測試集Xtest={(xi,y5.2.2分類的評價準(zhǔn)則精確度：代表測試集中被正確分類的數(shù)據(jù)樣本所占的比例12/17/2022105.2.2分類的評價準(zhǔn)則精確度：代表測試集中被正確分類的數(shù)5.2.2分類的評價準(zhǔn)則查全率：表示在本類樣本中被正確分類的樣本所占的比例查準(zhǔn)率：表示被分類為該類的樣本中，真正屬于該類的樣本所占的比例12/17/2022115.2.2分類的評價準(zhǔn)則查全率：表示在本類樣本中被正確分類5.2.2分類的評價準(zhǔn)則F-measure(加權(quán)調(diào)合平均數(shù))：是查全率和查準(zhǔn)率的組合表達式β是可以調(diào)節(jié)的，通常取值為112/17/2022125.2.2分類的評價準(zhǔn)則F-measure(加權(quán)調(diào)合平均數(shù)5.2.2分類的評價準(zhǔn)則幾何均值：是各個類別的查全率的平方根12/17/2022135.2.2分類的評價準(zhǔn)則幾何均值：是各個類別的查全率的平 決策樹方法的起源是亨特（Hunt，1966）的概念學(xué)習(xí)系統(tǒng)CLS方法，然后發(fā)展到由Quinlan研制ID3方法，然后到著名的C4.5算法，C4.5算法的一個優(yōu)點是它能夠處理連續(xù)屬性。還有CART算法和Assistant算法也是比較有名的決策樹方法。

5.3決策樹12/17/202214 決策樹方法的起源是亨特（Hunt，1966）的概念決策樹的優(yōu)點：進行分類器設(shè)計時，決策樹分類方法所需時間相對較少決策樹的分類模型是樹狀結(jié)構(gòu)，簡單直觀，比較符合人類的理解方式可以將決策樹中到達每個葉節(jié)點的路徑轉(zhuǎn)換為IF—THEN形式的分類規(guī)則，這種形式更有利于理解12/17/202215決策樹的優(yōu)點：12/14/2022151.什么是決策樹決策樹（DecisionTree）又稱為判定樹，是運用于分類的一種樹結(jié)構(gòu)。其中的每個內(nèi)部結(jié)點（internalnode）代表對某個屬性的一次測試，每條邊代表一個測試結(jié)果，葉結(jié)點（leaf）代表某個類（class）或者類的分布（classdistribution），最上面的結(jié)點是根結(jié)點。決策樹提供了一種展示類似在什么條件下會得到什么值這類規(guī)則的方法。下例是為了解決這個問題而建立的一棵決策樹，從中可以看到?jīng)Q策樹的基本組成部分：決策結(jié)點、分支和葉結(jié)點。12/17/2022161.什么是決策樹12/14/202216〖例〗圖5-2給出了一個商業(yè)上使用的決策樹的例子。它表示了一個關(guān)心電子產(chǎn)品的用戶是否會購買PC（buys_computer）的知識，用它可以預(yù)測某條記錄（某個人）的購買意向。

圖5-2buys_computer的決策樹

12/17/202217〖例〗圖5-2給出了一個商業(yè)上使用的決策樹的例子。它表示了這棵決策樹對銷售記錄進行分類，指出一個電子產(chǎn)品消費者是否會購買一臺計算機“buys_computer”。每個內(nèi)部結(jié)點（方形框）代表對某個屬性的一次檢測。每個葉結(jié)點（橢圓框）代表一個類： buys_computers=yes或者 buys_computers=no

在這個例子中，樣本向量為：

（age,student,credit_rating;buys_computers）

被決策數(shù)據(jù)的格式為:

（age,student,credit_rating）

輸入新的被決策的記錄，可以預(yù)測該記錄隸屬于哪個類。12/17/202218這棵決策樹對銷售記錄進行分類，指出一個電子產(chǎn)品消費者是否會購2.使用決策樹進行分類 構(gòu)造決策樹是采用自上而下的遞歸構(gòu)造方法。以多叉樹為例，如果一個訓(xùn)練數(shù)據(jù)集中的數(shù)據(jù)有幾種屬性值，則按照屬性的各種取值把這個訓(xùn)練數(shù)據(jù)集再劃分為對應(yīng)的幾個子集（分支），然后再依次遞歸處理各個子集。反之，則作為葉結(jié)點。決策樹構(gòu)造的結(jié)果是一棵二叉或多叉樹，它的輸入是一組帶有類別標(biāo)記的訓(xùn)練數(shù)據(jù)。二叉樹的內(nèi)部結(jié)點（非葉結(jié)點）一般表示為一個邏輯判斷，如形式為(a=b)的邏輯判斷，其中a是屬性，b是該屬性的某個屬性值；樹的邊是邏輯判斷的分支結(jié)果。多叉樹（ID3）的內(nèi)部結(jié)點是屬性，邊是該屬性的所有取值，有幾個屬性值，就有幾條邊。樹的葉結(jié)點都是類別標(biāo)記。12/17/2022192.使用決策樹進行分類12/14/202219使用決策樹進行分類分為兩步：第1步：利用訓(xùn)練集建立并精化一棵決策樹，建立決策樹模型。這個過程實際上是一個從數(shù)據(jù)中獲取知識，進行機器學(xué)習(xí)的過程。第2步：利用生成完畢的決策樹對輸入數(shù)據(jù)進行分類。對輸入的記錄，從根結(jié)點依次測試記錄的屬性值，直到到達某個葉結(jié)點，從而找到該記錄所在的類。12/17/202220使用決策樹進行分類分為兩步：12/14/202220問題的關(guān)鍵是建立一棵決策樹。這個過程通常分為兩個階段：建樹（TreeBuilding）：決策樹建樹算法見下，這是一個遞歸的過程，最終將得到一棵樹。剪枝（TreePruning）：剪枝的目的是降低由于訓(xùn)練集存在噪聲而產(chǎn)生的起伏。12/17/202221問題的關(guān)鍵是建立一棵決策樹。這個過程通常分為兩個階段：12/由Quinlan在80年代中期提出的ID3算法是分類規(guī)則挖掘算法中最有影響的算法。ID3即決策樹歸納（InductionofDecisionTree）。早期的ID算法只能就兩類數(shù)據(jù)進行挖掘（如正類和反類）；經(jīng)過改進后，現(xiàn)在ID算法可以挖掘多類數(shù)據(jù)。待挖掘的數(shù)據(jù)必須是不矛盾的、一致的，也就是說，對具有相同屬性的數(shù)據(jù)，其對應(yīng)的類必須是唯一的。在ID3算法挖掘后，分類規(guī)則由決策樹來表示。

5.4分類規(guī)則挖掘的ID3算法12/17/202222由Quinlan在80年代中期提出的ID3算法是分類規(guī)則挖1.ID3算法的基本思想由訓(xùn)練數(shù)據(jù)集中全體屬性值生成的所有決策樹的集合稱為搜索空間，該搜索空間是針對某一特定問題而提出的。系統(tǒng)根據(jù)某個評價函數(shù)決定搜索空間中的哪一個決策樹是“最好”的。評價函數(shù)一般依據(jù)分類的準(zhǔn)確度和樹的大小來決定決策樹的質(zhì)量。如果兩棵決策樹都能準(zhǔn)確地在測試集進行分類，則選擇較簡單的那棵。相對而言，決策樹越簡單，則它對未知數(shù)據(jù)的預(yù)測性能越佳。尋找一棵“最好”的決策樹是一個NP完全問題。

NP完全問題是這樣的問題：用確定性的算法在多項式時間內(nèi)無法解決的問題。實際之中，解決這樣的問題，往往是根據(jù)用啟發(fā)式算法，求出近似的解。12/17/2022231.ID3算法的基本思想NP完全問題是這樣的問題：用確定性ID3使用一種自頂向下的方法在部分搜索空間創(chuàng)建決策樹，同時保證找到一棵簡單的決策樹—可能不是最簡單的。ID3算法的基本思想描述如下：step1．任意選取一個屬性作為決策樹的根結(jié)點，然后就這個屬性所有的取值創(chuàng)建樹的分支；step2．用這棵樹來對訓(xùn)練數(shù)據(jù)集進行分類，如果一個葉結(jié)點的所有實例都屬于同一類，則以該類為標(biāo)記標(biāo)識此葉結(jié)點；如果所有的葉結(jié)點都有類標(biāo)記，則算法終止；step3．否則，選取一個從該結(jié)點到根路徑中沒有出現(xiàn)過的屬性為標(biāo)記標(biāo)識該結(jié)點，然后就這個屬性所有的取值繼續(xù)創(chuàng)建樹的分支；重復(fù)算法步驟step2；agestudentcredit_ratingbuys_computers25YESexcellantYES35NOfairYES12/17/202224ID3使用一種自頂向下的方法在部分搜索空間創(chuàng)建決策樹，同時保這個算法一定可以創(chuàng)建一棵基于訓(xùn)練數(shù)據(jù)集的正確的決策樹，然而，這棵決策樹不一定是簡單的。顯然，不同的屬性選取順序?qū)⑸刹煌臎Q策樹。因此，適當(dāng)?shù)剡x取屬性將生成一棵簡單的決策樹。在ID3算法中，采用了一種基于信息的啟發(fā)式的方法來決定如何選取屬性。啟發(fā)式方法選取具有最高信息量的屬性，也就是說，生成最少分支決策樹的那個屬性。

12/17/202225這個算法一定可以創(chuàng)建一棵基于訓(xùn)練數(shù)據(jù)集的正確的決策樹，然而，

算法：Generate_decision_tree由給定的訓(xùn)練數(shù)據(jù)產(chǎn)生一棵決策樹輸入：訓(xùn)練數(shù)據(jù)集samples，用離散值屬性表示；候選屬性的集合attribute_list。輸出：一棵決策樹方法：（1）創(chuàng)建結(jié)點N；（2）ifsamples都在同一個類Cthen（3）返回N作為葉結(jié)點，用類C標(biāo)記；（4）ifattribute_list為空then（5）返回N作為葉結(jié)點，標(biāo)記samples中最普通的類； //多數(shù)表決（6）選擇attribute_list中具有最高信息增益的屬性test_attribute；//用信息增益作為屬性選擇度量（7）標(biāo)記結(jié)點N為test_attribute；（8）foreachtest_attribute中的已知值ai//劃分samples（9）由結(jié)點N生長出一個條件為test_attribute＝ai的分枝；（10）設(shè)si為samples中test_attribute＝ai的樣本集合； //一個劃分（11）ifsi為空then（12）加上一個葉結(jié)點，標(biāo)記為標(biāo)記samples中最普通的類； //多數(shù)表決（13）else加上一個由Generate_decision_tree（si,attribute_list-test_attribute）返回的結(jié)點；12/17/202226

12/14/2022262.屬性選擇度量在Generate_decision_tree算法的Step6，算法需選擇attribute_list中具有最高信息增益的屬性test_attribute。ID3算法在樹的每個結(jié)點上以信息增益（informationgain）作為度量來選擇測試屬性。這種度量稱為屬性選擇度量或分裂的優(yōu)良性度量。選擇具有最高信息增益（或最大熵壓縮）的屬性作為當(dāng)前結(jié)點的測試屬性。該屬性使得對結(jié)果劃分中的樣本分類所需要的信息量最小，并確保找到一棵簡單的（但不一定是最簡單的）決策樹。12/17/2022272.屬性選擇度量12/14/202227InformationGain指標(biāo)的原理來自于信息論。1948年，香農(nóng)（C.E.Shannon）提出了信息論。其中給出了關(guān)于信息量（Information）和熵（Entropy）的定義，熵實際上是系統(tǒng)信息量的加權(quán)平均，也就是系統(tǒng)的平均信息量。12/17/202228InformationGain指標(biāo)的原理來自于信息論。19假設(shè)要選擇有n個輸出（所給屬性的n個值）的檢驗，把訓(xùn)練樣本集T分區(qū)成子集T1，T2，…，Tn。僅有的指導(dǎo)信息是在T和它的子集Ti中的類的分布。如果S是任意樣本集，設(shè)freq(Ci,S)代表S中屬于類Ci（k個可能的類中的一個）的樣本數(shù)量，|S|表示集合S中的樣本數(shù)量。下面給出了集合S（單位為比特）的熵計算：kInfo(S)＝－Σi=1((freq(Ci,S)/|S|).log2(freq(Ci,S)/|S|))以2為底的原因是：信息按二進制位編碼12/17/202229假設(shè)要選擇有n個輸出（所給屬性的n個值）的檢驗，把訓(xùn)練樣本集熵是一個衡量系統(tǒng)混亂程度的統(tǒng)計量。熵越大，表示系統(tǒng)越混亂。分類的目的是提取系統(tǒng)信息，使系統(tǒng)向更加有序、有規(guī)則組織的方向發(fā)展。所以最佳的分裂方案是使熵減少量最大的分裂方案。熵減少量就是InformationGain（信息增益），所以，最佳分裂就是使Gain(A)最大的分裂方案。通常，這個最佳方案是用“貪心算法+深度優(yōu)先搜索”得到的。12/17/202230熵是一個衡量系統(tǒng)混亂程度的統(tǒng)計量。熵越大，表示系統(tǒng)越混亂。1現(xiàn)在考慮T被分區(qū)之后的一個相似度量標(biāo)準(zhǔn)，T按照一個屬性檢驗X的幾個輸出進行分區(qū)。所需信息可通過這些子集的熵的加權(quán)和求得：nInfox(T)＝－Σi=1((|Ti|/|T|).info(Ti))信息增益的計算公式：Gain(X)=Info(T)-Infox(T)通過計算求出具有最高增益的屬性。12/17/202231現(xiàn)在考慮T被分區(qū)之后的一個相似度量標(biāo)準(zhǔn)，T按照一個屬性檢驗X以下分析有關(guān)度量標(biāo)準(zhǔn)的應(yīng)用和創(chuàng)建決策樹的一個簡單例子，假設(shè)以平面文件形式給出的數(shù)據(jù)集T，其中有14個樣本，通過3個輸入屬性描述且屬于所給的兩個類之一：類1或類2。12/17/202232以下分析有關(guān)度量標(biāo)準(zhǔn)的應(yīng)用和創(chuàng)建決策樹的一個簡單例子，假設(shè)以訓(xùn)練例子的簡單平面數(shù)據(jù)庫數(shù)據(jù)庫T：屬性1屬性2屬性3屬性4A70真類1A90真類2A85假類2A95假類2A70假類1B90真類1B78假類1B65真類1B75假類1C80真類2C70真類2C80假類1C80假類1C96假類112/17/202233訓(xùn)練例子的簡單平面數(shù)據(jù)庫數(shù)據(jù)庫T：屬性1屬性2屬性3屬性4A其中：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(chǔ)，B或C中選擇其一）后，得出結(jié)果：

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.940–0.694=0.246比特12/17/202234其中：9個樣本屬于類1，5個樣本屬于類2，因此分區(qū)前的熵為：如果該檢驗和分區(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.940–0.892=0.048比特按照增益準(zhǔn)則，將選擇x1作為分區(qū)數(shù)據(jù)庫T的最初檢驗。為了求得最優(yōu)檢驗還必須分析關(guān)于屬性2的檢驗，它是連續(xù)取值的數(shù)值型屬性。12/17/202235如果該檢驗和分區(qū)是基于屬性3的（檢驗x2表示從真或假兩個值選3.ID3算法的改進

（1）離散化為了解決該問題，在用ID3算法挖掘具有連續(xù)性屬性的知識時，應(yīng)該首先把該連續(xù)性屬性離散化。最簡單的方法就是把屬性值分成 和 兩段。如身高可以分為1米以下，1米以上或者分為1.5米以下，1.5米以上。如何選擇最佳的分段值呢？對任何一個屬性，其所有的取值在一個數(shù)據(jù)集中是有限的。假設(shè)該屬性取值為，則在這個集合中，一共存在m-1個分段值，ID3算法采用計算信息量的方法計算最佳的分段值，然后進一步構(gòu)建決策樹。ID3算法的擴展是C4.5算法，C4.5算法把分類范圍從分類屬性擴展到數(shù)字屬性。12/17/2022363.ID3算法的改進 12/14/2022361.C4.5算法概述C4.5算法是ID3算法的擴展，它的改進部分是：能夠處理連續(xù)型的屬性。首先將連續(xù)型屬性離散化，把連續(xù)型屬性的值分成不同的區(qū)間，依據(jù)是比較各個屬性Gian值的大小。缺失數(shù)據(jù)的考慮：在構(gòu)建決策樹時，可以簡單地忽略缺失數(shù)據(jù)，即在計算增益時，僅考慮具有屬性值的記錄。提供兩種基本的剪枝策略：子樹替代法：用葉結(jié)點替代子樹。子樹上升法：用一棵子樹中最常用的子樹來代替這棵子樹。5.5分類規(guī)則挖掘的C4.5算法剪枝目的是降低由于訓(xùn)練集存在噪聲而產(chǎn)生的起伏。12/17/2022371.C4.5算法概述5.5分類規(guī)則挖掘的C4.5算法剪2."離散化"的方法把連續(xù)型屬性值"離散化"的具體方法是：

1）

尋找該連續(xù)型屬性的最小值，并把它賦值給MIN，

尋找該連續(xù)型屬性的最大值，并把它賦值給MAX；

2）

設(shè)置區(qū)間[MIN，MAX]中的N個等分?jǐn)帱cAi，它們分別是

Ai=MIN+（（MAX–MIN）/N）*i

其中，i=1,2,...,N

3）

分別計算把[MIN，Ai]和（Ai，MAX）（i=1,2,...,N）作為區(qū)間值時的Gain值，并進行比較。

4）選取Gain值最大的Ak做為該連續(xù)型屬性的斷點，把屬性值設(shè)置為[MIN，Ak]和（Ak，MAX）兩個區(qū)間值。12/17/2022382."離散化"的方法12/14/202238對于前面例子中的數(shù)據(jù)庫T，分析屬性2分區(qū)的可能結(jié)果，分類后得出屬性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值：<=65和>65<=70和>70<=75和>75<=78和>78<=80和>80<=85和>85<=90和>90<=95和>95如以第二種分段為例計算，計算其Gain值：12/17/202239對于前面例子中的數(shù)據(jù)庫T，分析屬性2分區(qū)的可能結(jié)果，分類后得屬性2化簡后的平面數(shù)據(jù)庫數(shù)據(jù)庫T：屬性1屬性2屬性3屬性4A1真類1A2真類2A2假類2A2假類2A1假類1B2真類1B2假類1B1真類1B2假類1C2真類2C1真類2C2假類1C2假類1C2假類112/17/202240屬性2化簡后的平面數(shù)據(jù)庫數(shù)據(jù)庫T：屬性1屬性2屬性3屬性4AInfox2(T)＝4/14（-3/4log2(3/4)-1/4log2(1/4)） +10/14（-6/10log2(6/10)-4/10log2(4/10)） =……比特Gain(x2)=0.940–Infox2(T)=……比特12/17/202241Infox2(T)＝4/14（-3/4log2(3/4)找到最優(yōu)的閾值（具有最高信息增益）Z=80相應(yīng)的檢驗3（屬性2<=80和屬性2>80)的信息增益計算為：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.940–0.837=0.103比特比較本例中3個屬性的信息增益，可以看出屬性1具有最高增益，選擇該屬性對決策樹的結(jié)構(gòu)進行首次分區(qū)。12/17/202242找到最優(yōu)的閾值（具有最高信息增益）Z=8012/14/202T1檢驗X1:屬性1=？屬性2屬性3類70真類190真類285假類295假類270假類1屬性2屬性3類90真類178假類165真類175假類1屬性2屬性3類80真類270真類280假類180假類196假類1T2T3ABC葉結(jié)點12/17/202243T1檢驗X1:屬性2屬性3類70真類190真類285假類29對于剩下的子結(jié)點T1、T3進行分析：對T1的屬性進行檢驗：最優(yōu)檢驗（具有最高的信息增益）有兩個選擇：屬性2<=70或?qū)傩?>70，定義為x4。Info(T1)＝-2/14log2(2/5)-3/14log2(3/5) =0.940比特用屬性2把T1分成兩個子集（檢驗x4），結(jié)果信息是：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.940–0=0.940比特這兩個分枝將生成最終葉結(jié)點。12/17/202244對于剩下的子結(jié)點T1、T3進行分析：12/14/202244對于剩下的子結(jié)點T3進行分析：對T3的屬性進行檢驗：選擇的最優(yōu)檢驗為x5對屬性3的值進行檢驗，樹的分枝是屬性3=真和屬性3=假。最終決策樹為：X1:屬性1X4:屬性2X5:屬性3類1類2類1類2類1檢驗結(jié)點ABC<=70>70真假葉結(jié)點12/17/202245對于剩下的子結(jié)點T3進行分析：X1:X4:X5:類1類2類1決策樹可以用偽代碼的形式表示，這種偽代碼用IF-THEN結(jié)構(gòu)對決策樹進行分枝。If屬性1=A then if屬性2<=70 then 類別=類1; else 類別=類2;Elseif屬性1=Bthen 類別=類1;elseif屬性1=Cthen if屬性3=真then 類別=類2; else 類別=類1.

結(jié)果12/17/202246決策樹可以用偽代碼的形式表示，這種偽代碼用IF-THEN結(jié)構(gòu)增益標(biāo)準(zhǔn)對緊湊型決策樹的構(gòu)造有很好的效果，但也存在一個嚴(yán)重缺陷：對具有多輸出的檢驗有嚴(yán)重的偏差。解決方法：根據(jù)info(S)的定義，指定一個附加的參數(shù)：nSplit_Info(X)＝－Σi=1((|Ti|/|T|).log2(|Ti|/|T|))含義：通過把集T分區(qū)成n個子集Ti而生成的潛在信息。新的增益標(biāo)準(zhǔn)----增益率：Gain_ratio(X)=Gain(X)/Split_Info(X)新的增益標(biāo)準(zhǔn)表示分區(qū)所生成的有用信息的比例12/17/202247增益標(biāo)準(zhǔn)對緊湊型決策樹的構(gòu)造有很好的效果，但也存在一個嚴(yán)重缺根據(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檢驗過程，將采用最大增益率代替增益標(biāo)準(zhǔn)值12/17/202248根據(jù)前面實例，求檢驗X1的增益比例。12/14/202248在實際應(yīng)用過程中，大量的現(xiàn)實世界中的數(shù)據(jù)都不是以人的意愿來定的，可能某些字段上缺值（missingvalues）；可能數(shù)據(jù)不準(zhǔn)確含有噪聲或者是錯誤的；可能是缺少必須的數(shù)據(jù)造成了數(shù)據(jù)的不完整。

解決丟失值問題有兩種選擇：拋棄數(shù)據(jù)庫中有丟失數(shù)據(jù)的樣本。定義一個新的算法或改進現(xiàn)有的算法來處理。3.未知屬性值問題如存在大量丟失數(shù)據(jù)?12/17/202249在實際應(yīng)用過程中，大量的現(xiàn)實世界中的數(shù)據(jù)都不是以人的意愿來定按照第二種選擇，必須回答幾個問題：怎樣比較具有不同數(shù)目未知值的兩個樣本？具有未知值的訓(xùn)練樣本和檢驗的具體值之間沒有聯(lián)系，它們不能被分配給任何子集，該如何處理這些樣本？在分類的檢驗階段，如果檢驗有丟失值的屬性時，該怎樣處理丟失值？C4.5算法中：有未知值的樣本是按照已知值的相對頻率隨機分布的。除考慮到僅有的幾個有已知屬性值的樣本以外用系數(shù)F修正增益參數(shù)F=數(shù)據(jù)庫中一個給出的屬性值具有已知值的樣本數(shù)量/數(shù)據(jù)集中樣本數(shù)量總和通過一些方法補充數(shù)據(jù)？12/17/202250按照第二種選擇，必須回答幾個問題：通過一些方法補充數(shù)據(jù)？12新的增益標(biāo)準(zhǔn)： Gain(X)=F*(info(T)–infox(T))同時，通過把具有未知值的樣本看作分區(qū)的一個附加組來修改Split_Info(X)。如果檢驗x有n個輸出，Split_Info(X)按照檢驗把數(shù)據(jù)集分區(qū)成n+1個子集計算。該值Split_Info(X)對修改后的標(biāo)準(zhǔn)Gain_ratio(X)的最終值有直接影響。12/17/202251新的增益標(biāo)準(zhǔn)：12/14/202251有一個丟失值的簡單平面數(shù)據(jù)庫數(shù)據(jù)庫T：屬性1屬性2屬性3屬性4A70真類1A90真類2A85假類2A95假類2A70假類1？90真類1B78假類1B65真類1B75假類1C80真類2C70真類2C80假類1C80假類1C96假類112/17/202252有一個丟失值的簡單平面數(shù)據(jù)庫數(shù)據(jù)庫T：屬性1屬性2屬性3屬性屬性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/5log2(2/5)-3/5log2(3/5)） +3/13（-3/3log2(3/3)-0/3log2(0/3)） +5/13（-3/5log2(3/5)-2/5log2(2/5)） =0.747比特用系數(shù)F進行修正得：Gain(X1)=13/14（0.961–0.747）=0.199比特原來為0.246比特12/17/202253屬性1的增益計算考慮13個數(shù)據(jù)，丟失的樣本僅用來作修正，屬性考慮未知值的影響：Split_Info(X1)＝-5/13log2(5/13)-3/13log2(3/13) -5/13log2(5/13)-1/13log2(1/13) =1.876比特由Gain_ratio(X)=Gain(X)/Split_Info(X)計算，則：Gain_ratio(X)=0.199/1.876=0.106同時，每個樣本都有一個相關(guān)的新參數(shù)，即概率：當(dāng)一個值已知的樣本從T分配給Ti時，它屬于Ti的概率是1，屬于其它所有子集的概率是0；當(dāng)一個值是未知的，只能得出不穩(wěn)定的概率描述。作為單獨一組12/17/202254考慮未知值的影響：作為單獨一組12/14/202254用屬性1的檢驗X1把集T分區(qū)成子集后，丟失值的記錄被表示在3個子集中。T1：（屬性1=A）屬性2屬性3類w70真類1190真類2185假類2195假類2170假類1190真類15/13屬性2屬性3類w90真類13/1378假類1165真類1175假類11屬性2屬性3類w80真類2170真類2180假類1180假類1196假類1190真類15/13T2：（屬性1=B）T3：（屬性1=C）在子集中的權(quán)值在C4.5中，|Ti|可以重新解釋為子集Ti的所有權(quán)重w的和，而不再是集Ti中的元素數(shù)。12/17/202255用屬性1的檢驗X1把集T分區(qū)成子集后，丟失值的記錄被表示在3因此有： |T1|=5+5/13 |T2|=3+3/13 |T3|=5+5/1312/17/202256因此有：12/14/202256If屬性1=A then if屬性2<=70 then 類別=類1（2.0/0）; else 類別=類2（3.4/0.4）;Elseif屬性1=Bthen 類別=類1（3.2/0）;elseif屬性1=Cthen if屬性3=真then 類別=類2（2.4/0.4）; else 類別=類1（3.0/0）.

再把這些子集按屬性2和屬性3的檢驗進一步分區(qū)，最終得到的決策樹如下左。因最終分類的不明確性，每個決策都用到|Ti|/E表示。|Ti|是達到葉結(jié)點的部分樣本和，E是屬于除了指定類以外的類的樣本數(shù)量。其中：3.4/0.4的意思是3.4個部分訓(xùn)練樣本達到葉結(jié)點，其中0.4（5/13）個并不屬于分配給葉的類。12/17/202257If屬性1=A then再把這些子集按屬性2和屬性3剪枝常常利用統(tǒng)計學(xué)方法，去掉最不可靠、可能是噪音的一些枝條。提供兩種基本的剪枝策略：子樹替代法：用葉結(jié)點替代子樹。子樹上升法：用一棵子樹中最常用的子樹來代替這棵子樹。結(jié)果：最終生成一個更簡單、更容易理解的樹4.修剪決策樹（剪枝）12/17/202258剪枝常常利用統(tǒng)計學(xué)方法，去掉最不可靠、可能是噪音的一些枝條。（1）先剪枝（pre-pruning）在建樹的過程中，如滿足下列條件：InformationGain或者某些有效統(tǒng)計量達到某個預(yù)先設(shè)定的閾值時，結(jié)點不再繼續(xù)分裂，內(nèi)部結(jié)點成為一個葉結(jié)點。如果分區(qū)前后分類精度沒有顯著的不同，可用當(dāng)前的點作為葉。由于決策在分區(qū)前提前做出，因此該方法也叫預(yù)剪枝。12/17/202259（1）先剪枝（pre-pruning）12/14/20225

（2）后剪枝（pos-pruning）用所選的精度準(zhǔn)則回頭去除樹的一些點。在構(gòu)建完樹之后做的決策，所以稱之為后剪枝。當(dāng)建樹時的訓(xùn)練數(shù)據(jù)進入決策樹并到達葉結(jié)點時，訓(xùn)練數(shù)據(jù)的classlabel與葉結(jié)點的classlabel不同，這時稱為發(fā)生了分類錯誤。當(dāng)樹建好之后，對每個內(nèi)部結(jié)點，算法通過每個枝條的出錯率進行加權(quán)平均，計算如果不剪枝該結(jié)點的錯誤率。如果裁減能夠降低錯誤率，那么該結(jié)點的所有兒子就被剪掉，而該結(jié)點成為一片葉。出錯率用與訓(xùn)練集數(shù)據(jù)獨立的測試數(shù)據(jù)校驗。最終形成一棵錯誤率盡可能小的決策樹。12/17/202260

（2）后剪枝（pos-pruning）12/14/2022為了使決策樹模型更易讀，可以提取由決策樹表示的分類規(guī)則，并以IF－THEN的形式表示。具體方法是：從根結(jié)點到葉結(jié)點的每一條路徑創(chuàng)建一條分類規(guī)則，路徑上的每一個“屬性－值”對為規(guī)則的前件（即IF部分）的一個合取項，葉結(jié)點為規(guī)則的后件（即THEN部分）。5.6生成決策規(guī)則決策樹12/17/202261為了使決策樹模型更易讀，可以提取由決策樹表示的分類規(guī)則，并以〖例〗對于buys_computer的決策樹可提取以下分類規(guī)則：IFage＝‘<=30’ANDstudent＝‘no’

THENbuys_computer＝‘noIFage＝‘<=30’ANDstudent＝‘yes’

THENbuys_computer＝‘yes’

IFage＝‘30…40’THENbuys_computer＝‘yes’

IFage＝‘>40’ANDcredit_rating＝‘excellent’

THENbuys_computer＝‘no’

IFage＝‘>40’ANDcredit_rating＝‘fair’

THENbuys_computer＝‘yes’12/17/202262〖例〗對于buys_computer的決策樹可提取以下分類規(guī)5.7SQLServer2005中的決策樹應(yīng)用創(chuàng)建AnalysisServices項目創(chuàng)建數(shù)據(jù)源創(chuàng)建數(shù)據(jù)源視圖創(chuàng)建決策樹挖掘結(jié)構(gòu)設(shè)置決策樹挖掘結(jié)構(gòu)的相關(guān)參數(shù)建立決策樹挖掘模型查看挖掘結(jié)果12/17/2022635.7SQLServer2005中的決策樹應(yīng)用創(chuàng)建數(shù)據(jù)集X屬性1屬性2類T1C2T2C1F1C2F2C2作業(yè)11、給出一個3維分類的樣本的數(shù)據(jù)集X，表示如下：用C4.5算法中的計算步驟構(gòu)建一個決策樹。12/17/202264數(shù)據(jù)集X屬性1屬性2類T1C2T2C1F1C2F2C2作業(yè)1數(shù)據(jù)集YABC類151AC1203BC2252AC1304AC1352BC2254AC1152BC2203BC2作業(yè)22、給出一個訓(xùn)練數(shù)據(jù)集Y，表示如下：A）求出屬性A的最優(yōu)閾值（根據(jù)最大增益）。B）求出屬性B的最優(yōu)閾值（根據(jù)最大增益）。C）求數(shù)據(jù)集Y的決策樹。D）從決策樹中導(dǎo)出決策規(guī)則。12/17/202265數(shù)據(jù)集YABC類151AC1203BC2252AC1304A演講完畢，謝謝觀看！演講完畢，謝謝觀看！數(shù)據(jù)倉庫與數(shù)據(jù)挖掘技術(shù)

五邑大學(xué)信息學(xué)院2009.06何國輝教授12/17/202267數(shù)據(jù)倉庫與數(shù)據(jù)挖掘技術(shù)

五邑大學(xué)信息學(xué)院何國輝教授1第5章決策樹和決策規(guī)則5.1引例

分類的定義分類是指把數(shù)據(jù)樣本映射到一個事先定義的類中的學(xué)習(xí)過程，即給定一組輸入的屬性向量及其對應(yīng)的類，用基于歸納的學(xué)習(xí)算法得出分類。12/17/202268第5章決策樹和決策規(guī)則5.1引例分類的定AgeSalaryClass30highc125highc221lowc243highc118lowc233lowc1………描述屬性類別屬性分類問題使用的數(shù)據(jù)集格式：12/17/202269AgeSalaryClass30highc125highc25.1引例分類問題使用的數(shù)據(jù)集格式描述屬性可以是連續(xù)型屬性，也可以是離散型屬性；而類別屬性必須是離散型屬性。連續(xù)型屬性是指在某一個區(qū)間或者無窮區(qū)間內(nèi)該屬性的取值是連續(xù)的，例如屬性“Age”離散型屬性是指該屬性的取值是不連續(xù)的，例如屬性“Salary”和“Class”12/17/2022705.1引例分類問題使用的數(shù)據(jù)集格式12/14/202245.1引例分類問題使用的數(shù)據(jù)集格式分類問題中使用的數(shù)據(jù)集可以表示為X={(xi,yi)|i=1,2,…,total}xi=(xi1,xi2,…,xid)，其中xi1,xi2,…,xid分別對應(yīng)d個描述屬性A1,A2,…,Ad的具體取值yi表示數(shù)據(jù)樣本xi的類標(biāo)號，假設(shè)給定數(shù)據(jù)集包含m個類別，則yi∈{c1,c2,…,cm}，其中c1,c2,…,cm是類別屬性C的具體取值未知類標(biāo)號的數(shù)據(jù)樣本x用d維特征向量x=(x1,x2,…,xd)來表示12/17/2022715.1引例分類問題使用的數(shù)據(jù)集格式12/14/202255.2分類問題概述5.2.1分類的過程5.2.2分類的評價準(zhǔn)則12/17/2022725.2分類問題概述5.2.1分類的過程12/14/205.2.1分類的過程獲取數(shù)據(jù)預(yù)處理分類器設(shè)計分類決策12/17/2022735.2.1分類的過程獲取數(shù)據(jù)預(yù)處理分類器設(shè)計分類決策12/5.2.1分類的過程獲取數(shù)據(jù)輸入數(shù)據(jù)、對數(shù)據(jù)進行量化預(yù)處理去除噪聲數(shù)據(jù)、對空缺值進行處理數(shù)據(jù)集成或者變換分類器設(shè)計劃分?jǐn)?shù)據(jù)集、分類器構(gòu)造、分類器測試分類決策對未知類標(biāo)號的數(shù)據(jù)樣本進行分類12/17/2022745.2.1分類的過程獲取數(shù)據(jù)12/14/202285.2.2分類的評價準(zhǔn)則給定測試集Xtest={(xi,yi)|i=1,2,…,N}N表示測試集中的樣本個數(shù)xi表示測試集中的數(shù)據(jù)樣本yi表示數(shù)據(jù)樣本xi的類標(biāo)號對于測試集的第j個類別，假設(shè)被正確分類的樣本數(shù)量為TPj被錯誤分類的樣本數(shù)量為FNj其他類別被錯誤分類為該類的樣本數(shù)據(jù)量為FPj12/17/2022755.2.2分類的評價準(zhǔn)則給定測試集Xtest={(xi,y5.2.2分類的評價準(zhǔn)則精確度：代表測試集中被正確分類的數(shù)據(jù)樣本所占的比例12/17/2022765.2.2分類的評價準(zhǔn)則精確度：代表測試集中被正確分類的數(shù)5.2.2分類的評價準(zhǔn)則查全率：表示在本類樣本中被正確分類的樣本所占的比例查準(zhǔn)率：表示被分類為該類的樣本中，真正屬于該類的樣本所占的比例12/17/2022775.2.2分類的評價準(zhǔn)則查全率：表示在本類樣本中被正確分類5.2.2分類的評價準(zhǔn)則F-measure(加權(quán)調(diào)合平均數(shù))：是查全率和查準(zhǔn)率的組合表達式β是可以調(diào)節(jié)的，通常取值為112/17/2022785.2.2分類的評價準(zhǔn)則F-measure(加權(quán)調(diào)合平均數(shù)5.2.2分類的評價準(zhǔn)則幾何均值：是各個類別的查全率的平方根12/17/2022795.2.2分類的評價準(zhǔn)則幾何均值：是各個類別的查全率的平 決策樹方法的起源是亨特（Hunt，1966）的概念學(xué)習(xí)系統(tǒng)CLS方法，然后發(fā)展到由Quinlan研制ID3方法，然后到著名的C4.5算法，C4.5算法的一個優(yōu)點是它能夠處理連續(xù)屬性。還有CART算法和Assistant算法也是比較有名的決策樹方法。

5.3決策樹12/17/202280 決策樹方法的起源是亨特（Hunt，1966）的概念決策樹的優(yōu)點：進行分類器設(shè)計時，決策樹分類方法所需時間相對較少決策樹的分類模型是樹狀結(jié)構(gòu)，簡單直觀，比較符合人類的理解方式可以將決策樹中到達每個葉節(jié)點的路徑轉(zhuǎn)換為IF—THEN形式的分類規(guī)則，這種形式更有利于理解12/17/202281決策樹的優(yōu)點：12/14/2022151.什么是決策樹決策樹（DecisionTree）又稱為判定樹，是運用于分類的一種樹結(jié)構(gòu)。其中的每個內(nèi)部結(jié)點（internalnode）代表對某個屬性的一次測試，每條邊代表一個測試結(jié)果，葉結(jié)點（leaf）代表某個類（class）或者類的分布（classdistribution），最上面的結(jié)點是根結(jié)點。決策樹提供了一種展示類似在什么條件下會得到什么值這類規(guī)則的方法。下例是為了解決這個問題而建立的一棵決策樹，從中可以看到?jīng)Q策樹的基本組成部分：決策結(jié)點、分支和葉結(jié)點。12/17/2022821.什么是決策樹12/14/202216〖例〗圖5-2給出了一個商業(yè)上使用的決策樹的例子。它表示了一個關(guān)心電子產(chǎn)品的用戶是否會購買PC（buys_computer）的知識，用它可以預(yù)測某條記錄（某個人）的購買意向。

圖5-2buys_computer的決策樹

12/17/202283〖例〗圖5-2給出了一個商業(yè)上使用的決策樹的例子。它表示了這棵決策樹對銷售記錄進行分類，指出一個電子產(chǎn)品消費者是否會購買一臺計算機“buys_computer”。每個內(nèi)部結(jié)點（方形框）代表對某個屬性的一次檢測。每個葉結(jié)點（橢圓框）代表一個類： buys_computers=yes或者 buys_computers=no

在這個例子中，樣本向量為：

（age,student,credit_rating;buys_computers）

被決策數(shù)據(jù)的格式為:

（age,student,credit_rating）

輸入新的被決策的記錄，可以預(yù)測該記錄隸屬于哪個類。12/17/202284這棵決策樹對銷售記錄進行分類，指出一個電子產(chǎn)品消費者是否會購2.使用決策樹進行分類 構(gòu)造決策樹是采用自上而下的遞歸構(gòu)造方法。以多叉樹為例，如果一個訓(xùn)練數(shù)據(jù)集中的數(shù)據(jù)有幾種屬性值，則按照屬性的各種取值把這個訓(xùn)練數(shù)據(jù)集再劃分為對應(yīng)的幾個子集（分支），然后再依次遞歸處理各個子集。反之，則作為葉結(jié)點。決策樹構(gòu)造的結(jié)果是一棵二叉或多叉樹，它的輸入是一組帶有類別標(biāo)記的訓(xùn)練數(shù)據(jù)。二叉樹的內(nèi)部結(jié)點（非葉結(jié)點）一般表示為一個邏輯判斷，如形式為(a=b)的邏輯判斷，其中a是屬性，b是該屬性的某個屬性值；樹的邊是邏輯判斷的分支結(jié)果。多叉樹（ID3）的內(nèi)部結(jié)點是屬性，邊是該屬性的所有取值，有幾個屬性值，就有幾條邊。樹的葉結(jié)點都是類別標(biāo)記。12/17/2022852.使用決策樹進行分類12/14/202219使用決策樹進行分類分為兩步：第1步：利用訓(xùn)練集建立并精化一棵決策樹，建立決策樹模型。這個過程實際上是一個從數(shù)據(jù)中獲取知識，進行機器學(xué)習(xí)的過程。第2步：利用生成完畢的決策樹對輸入數(shù)據(jù)進行分類。對輸入的記錄，從根結(jié)點依次測試記錄的屬性值，直到到達某個葉結(jié)點，從而找到該記錄所在的類。12/17/202286使用決策樹進行分類分為兩步：12/14/202220問題的關(guān)鍵是建立一棵決策樹。這個過程通常分為兩個階段：建樹（TreeBuilding）：決策樹建樹算法見下，這是一個遞歸的過程，最終將得到一棵樹。剪枝（TreePruning）：剪枝的目的是降低由于訓(xùn)練集存在噪聲而產(chǎn)生的起伏。12/17/202287問題的關(guān)鍵是建立一棵決策樹。這個過程通常分為兩個階段：12/由Quinlan在80年代中期提出的ID3算法是分類規(guī)則挖掘算法中最有影響的算法。ID3即決策樹歸納（InductionofDecisionTree）。早期的ID算法只能就兩類數(shù)據(jù)進行挖掘（如正類和反類）；經(jīng)過改進后，現(xiàn)在ID算法可以挖掘多類數(shù)據(jù)。待挖掘的數(shù)據(jù)必須是不矛盾的、一致的，也就是說，對具有相同屬性的數(shù)據(jù)，其對應(yīng)的類必須是唯一的。在ID3算法挖掘后，分類規(guī)則由決策樹來表示。

5.4分類規(guī)則挖掘的ID3算法12/17/202288由Quinlan在80年代中期提出的ID3算法是分類規(guī)則挖1.ID3算法的基本思想由訓(xùn)練數(shù)據(jù)集中全體屬性值生成的所有決策樹的集合稱為搜索空間，該搜索空間是針對某一特定問題而提出的。系統(tǒng)根據(jù)某個評價函數(shù)決定搜索空間中的哪一個決策樹是“最好”的。評價函數(shù)一般依據(jù)分類的準(zhǔn)確度和樹的大小來決定決策樹的質(zhì)量。如果兩棵決策樹都能準(zhǔn)確地在測試集進行分類，則選擇較簡單的那棵。相對而言，決策樹越簡單，則它對未知數(shù)據(jù)的預(yù)測性能越佳。尋找一棵“最好”的決策樹是一個NP完全問題。

NP完全問題是這樣的問題：用確定性的算法在多項式時間內(nèi)無法解決的問題。實際之中，解決這樣的問題，往往是根據(jù)用啟發(fā)式算法，求出近似的解。12/17/2022891.ID3算法的基本思想NP完全問題是這樣的問題：用確定性ID3使用一種自頂向下的方法在部分搜索空間創(chuàng)建決策樹，同時保證找到一棵簡單的決策樹—可能不是最簡單的。ID3算法的基本思想描述如下：step1．任意選取一個屬性作為決策樹的根結(jié)點，然后就這個屬性所有的取值創(chuàng)建樹的分支；step2．用這棵樹來對訓(xùn)練數(shù)據(jù)集進行分類，如果一個葉結(jié)點的所有實例都屬于同一類，則以該類為標(biāo)記標(biāo)識此葉結(jié)點；如果所有的葉結(jié)點都有類標(biāo)記，則算法終止；step3．否則，選取一個從該結(jié)點到根路徑中沒有出現(xiàn)過的屬性為標(biāo)記標(biāo)識該結(jié)點，然后就這個屬性所有的取值繼續(xù)創(chuàng)建樹的分支；重復(fù)算法步驟step2；agestudentcredit_ratingbuys_computers25YESexcellantYES35NOfairYES12/17/202290ID3使用一種自頂向下的方法在部分搜索空間創(chuàng)建決策樹，同時保這個算法一定可以創(chuàng)建一棵基于訓(xùn)練數(shù)據(jù)集的正確的決策樹，然而，這棵決策樹不一定是簡單的。顯然，不同的屬性選取順序?qū)⑸刹煌臎Q策樹。因此，適當(dāng)?shù)剡x取屬性將生成一棵簡單的決策樹。在ID3算法中，采用了一種基于信息的啟發(fā)式的方法來決定如何選取屬性。啟發(fā)式方法選取具有最高信息量的屬性，也就是說，生成最少分支決策樹的那個屬性。

12/17/202291這個算法一定可以創(chuàng)建一棵基于訓(xùn)練數(shù)據(jù)集的正確的決策樹，然而，

算法：Generate_decision_tree由給定的訓(xùn)練數(shù)據(jù)產(chǎn)生一棵決策樹輸入：訓(xùn)練數(shù)據(jù)集samples，用離散值屬性表示；候選屬性的集合attribute_list。輸出：一棵決策樹方法：（1）創(chuàng)建結(jié)點N；（2）ifsamples都在同一個類Cthen（3）返回N作為葉結(jié)點，用類C標(biāo)記；（4）ifattribute_list為空then（5）返回N作為葉結(jié)點，標(biāo)記samples中最普通的類； //多數(shù)表決（6）選擇attribute_list中具有最高信息增益的屬性test_attribute；//用信息增益作為屬性選擇度量（7）標(biāo)記結(jié)點N為test_attribute；（8）foreachtest_attribute中的已知值ai//劃分samples（9）由結(jié)點N生長出一個條件為test_attribute＝ai的分枝；（10）設(shè)si為samples中test_attribute＝ai的樣本集合； //一個劃分（11）ifsi為空then（12）加上一個葉結(jié)點，標(biāo)記為標(biāo)記samples中最普通的類； //多數(shù)表決（13）else加上一個由Generate_decision_tree（si,attribute_list-test_attribute）返回的結(jié)點；12/17/202292

12/14/2022262.屬性選擇度量在Generate_decision_tree算法的Step6，算法需選擇attribute_list中具有最高信息增益的屬性test_attribute。ID3算法在樹的每個結(jié)點上以信息增益（informationgain）作為度量來選擇測試屬性。這種度量稱為屬性選擇度量或分裂的優(yōu)良性度量。選擇具有最高信息增益（或最大熵壓縮）的屬性作為當(dāng)前結(jié)點的測試屬性。該屬性使得對結(jié)果劃分中的樣本分類所需要的信息量最小，并確保找到一棵簡單的（但不一定是最簡單的）決策樹。12/17/2022932.屬性選擇度量12/14/202227InformationGain指標(biāo)的原理來自于信息論。1948年，香農(nóng)（C.E.Shannon）提出了信息論。其中給出了關(guān)于信息量（Information）和熵（Entropy）的定義，熵實際上是系統(tǒng)信息量的加權(quán)平均，也就是系統(tǒng)的平均信息量。12/17/202294InformationGain指標(biāo)的原理來自于信息論。19假設(shè)要選擇有n個輸出（所給屬性的n個值）的檢驗，把訓(xùn)練樣本集T分區(qū)成子集T1，T2，…，Tn。僅有的指導(dǎo)信息是在T和它的子集Ti中的類的分布。如果S是任意樣本集，設(shè)freq(Ci,S)代表S中屬于類Ci（k個可能的類中的一個）的樣本數(shù)量，|S|表示集合S中的樣本數(shù)量。下面給出了集合S（單位為比特）的熵計算：kInfo(S)＝－Σi=1((freq(Ci,S)/|S|).log2(freq(Ci,S)/|S|))以2為底的原因是：信息按二進制位編碼12/17/202295假設(shè)要選擇有n個輸出（所給屬性的n個值）的檢驗，把訓(xùn)練樣本集熵是一個衡量系統(tǒng)混亂程度的統(tǒng)計量。熵越大，表示系統(tǒng)越混亂。分類的目的是提取系統(tǒng)信息，使系統(tǒng)向更加有序、有規(guī)則組織的方向發(fā)展。所以最佳的分裂方案是使熵減少量最大的分裂方案。熵減少量就是InformationGain（信息增益），所以，最佳分裂就是使Gain(A)最大的分裂方案。通常，這個最佳方案是用“貪心算法+深度優(yōu)先搜索”得到的。12/17/202296熵是一個衡量系統(tǒng)混亂程度的統(tǒng)計量。熵越大，表示系統(tǒng)越混亂。1現(xiàn)在考慮T被分區(qū)之后的一個相似度量標(biāo)準(zhǔn)，T按照一個屬性檢驗X的幾個輸出進行分區(qū)。所需信息可通過這些子集的熵的加權(quán)和求得：nInfox(T)＝－Σi=1((|Ti|/|T|).info(Ti))信息增益的計算公式：Gain(X)=Info(T)-Infox(T)通過計算求出具有最高增益的屬性。12/17/202297現(xiàn)在考慮T被分區(qū)之后的一個相似度量標(biāo)準(zhǔn)，T按照一個屬性檢驗X以下分析有關(guān)度量標(biāo)準(zhǔn)的應(yīng)用和創(chuàng)建決策樹的一個簡單例子，假設(shè)以平面文件形式給出的數(shù)據(jù)集T，其中有14個樣本，通過3個輸入屬性描述且屬于所給的兩個類之一：類1或類2。12/17/202298以下分析有關(guān)度量標(biāo)準(zhǔn)的應(yīng)用和創(chuàng)建決策樹的一個簡單例子，假設(shè)以訓(xùn)練例子的簡單平面數(shù)據(jù)庫數(shù)據(jù)庫T：屬性1屬性2屬性3屬性4A70真類1A90真類2A85假類2A95假類2A70假類1B90真類1B78假類1B65真類1B75假類1C80真類2C70真類2C80假類1C80假類1C96假類112/17/202299訓(xùn)練例子的簡單平面數(shù)據(jù)庫數(shù)據(jù)庫T：屬性1屬性2屬性3屬性4A其中：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(chǔ)，B或C中選擇其一）后，得出結(jié)果：

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.940–0.694=0.246比特12/17/2022100其中：9個樣本屬于類1，5個樣本屬于類2，因此分區(qū)前的熵為：如果該檢驗和分區(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.940–0.892=0.048比特按照增益準(zhǔn)則，將選擇x1作為分區(qū)數(shù)據(jù)庫T的最初檢驗。為了求得最優(yōu)檢驗還必須分析關(guān)于屬性2的檢驗，它是連續(xù)取值的數(shù)值型屬性。12/17/2022101如果該檢驗和分區(qū)是基于屬性3的（檢驗x2表示從真或假兩個值選3.ID3算法的改進

（1）離散化為了解決該問題，在用ID3算法挖掘具有連續(xù)性屬性的知識時，應(yīng)該首先把該連續(xù)性屬性離散化。最簡單的方法就是把屬性值分成 和 兩段。如身高可以分為1米以下，1米以上或者分為1.5米以下，1.5米以上。如何選擇最佳的分段值呢？對任何一個屬性，其所有的取值在一個數(shù)據(jù)集中是有限的。假設(shè)該屬性取值為，則在這個集合中，一共存在m-1個分段值，ID3算法采用計算信息量的方法計算最佳的分段值，然后進一步構(gòu)建決策樹。ID3算法的擴展是C4.5算法，C4.5算法把分類范圍從分類屬性擴展到數(shù)字屬性。12/17/20221023.ID3算法的改進 12/14/2022361.C4.5算法概述C4.5算法是ID3算法的擴展，它的改進部分是：能夠處理連續(xù)型的屬性。首先將連續(xù)型屬性離散化，把連續(xù)型屬性的值分成不同的區(qū)間，依據(jù)是比較各個屬性Gian值的大小。缺失數(shù)據(jù)的考慮：在構(gòu)建決策樹時，可以簡單地忽略缺失數(shù)據(jù)，即在計算增益時，僅考慮具有屬性值的記錄。提供兩種基本的剪枝策略：子樹替代法：用葉結(jié)點替代子樹。子樹上升法：用一棵子樹中最常用的子樹來代替這棵子樹。5.5分類規(guī)則挖掘的C4.5算法剪枝目的是降低由于訓(xùn)練集存在噪聲而產(chǎn)生的起伏。12/17/20221031.C4.5算法概述5.5分類規(guī)則挖掘的C4.5算法剪2."離散化"的方法把連續(xù)型屬性值"離散化"的具體方法是：

1）

尋找該連續(xù)型屬性的最小值，并把它賦值給MIN，

尋找該連續(xù)型屬性的最大值，并把它賦值給MAX；

2）

設(shè)置區(qū)間[MIN，MAX]中的N個等分?jǐn)帱cAi，它們分別是

Ai=MIN+（（MAX–MIN）/N）*i

其中，i=1,2,...,N

3）

分別計算把[MIN，Ai]和（Ai，MAX）（i=1,2,...,N）作為區(qū)間值時的Gain值，并進行比較。

4）選取Gain值最大的Ak做為該連續(xù)型屬性的斷點，把屬性值設(shè)置為[MIN，Ak]和（Ak，MAX）兩個區(qū)間值。12/17/20221042."離散化"的方法12/14/202238對于前面例子中的數(shù)據(jù)庫T，分析屬性2分區(qū)的可能結(jié)果，分類后得出屬性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值：<=65和>65<=70和>70<=75和>75<=78和>78<=80和>80<=85和>85<=90和>90<=95和>95如以第二種分段為例計算，計算其Gain值：12/17/2022105對于前面例子中的數(shù)據(jù)庫T，分析屬性2分區(qū)的可能結(jié)果，分類后得屬性2化簡后的平面數(shù)據(jù)庫數(shù)據(jù)庫T：屬性1屬性2屬性3屬性4A1真類1A2真類2A2假類2A2假類2A1假類1B2真類1B2假類1B1真類1B2假類1C2真類2C1真類2C2假類1C2假類1C2假類112/17/2022106屬性2化簡后的平面數(shù)據(jù)庫數(shù)據(jù)庫T：屬性1屬性2屬性3屬性4AInfox2(T)＝4/14（-3/4log2(3/4)-1/4log2(1/4)） +10/14（-6/10log2(6/10)-4/10log2(4/10)） =……比特Gain(x2)=0.940–Infox2(T)=……比特12/17/2022107Infox2(T)＝4/14（-3/4log2(3/4)找到最優(yōu)的閾值（具有最高信息增益）Z=80相應(yīng)的檢驗3（屬性2<=80和屬性2>80)的信息增益計算為：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.940–0.837=0.103比特比較本例中3個屬性的信息增益，可以看出屬性1具有最高增益，選擇該屬性對決策樹的結(jié)構(gòu)進行首次分區(qū)。12/17/2022108找到最優(yōu)的閾值（具有最高信息增益）Z=8012/14/202T1檢驗X1:屬性1=？屬性2屬性3類70真類190真類285假類295假類270假類1屬性2屬性3類90真類178假類165真類175假類1屬性2屬性3類80真類270真類280假類180假類196假類1T2T3ABC葉結(jié)點12/17/2022109T1檢驗X1:屬性2屬性3類70真類190真類285假類29對于剩下的子結(jié)點T1、T3進行分析：對T1的屬性進行檢驗：最優(yōu)檢驗（具有最高的信息增益）有兩個選擇：屬性2<=70或?qū)傩?>70，定義為x4。Info(T1)＝-2/14log2(2/5)-3/14log2(3/5) =0.940比特用屬性2把T1分成兩個子集（檢驗x4），結(jié)果信息是：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.940–0=0.940比特這兩個分枝將生成最終葉結(jié)點。12/17/2022110對于剩下的子結(jié)點T1、T3進行分析：12/14/202244對于剩下的子結(jié)點T3進行分析：對T3的屬性進行檢驗：選擇的最優(yōu)檢驗為x5對屬性3的值進行檢驗，樹的分枝是屬性3=真和屬性3=假。最終決策樹為：X1:屬性1X4:屬性2X5:屬性3類1類2類1類2類1檢驗結(jié)點ABC<=70>70真假葉結(jié)點12/17/2022111對于剩下的子結(jié)點T3進行分析：X1:X4:X5:類1類2類1決策樹可以