第7章-數(shù)據(jù)分類

1、第7章 數(shù)據(jù)分類宋杰鯤中國石油大學(xué)（華東）管理科學(xué)與工程系第7章 數(shù)據(jù)分類n 分類是數(shù)據(jù)挖掘中一項(xiàng)重要的任務(wù)。分類分類是數(shù)據(jù)挖掘中一項(xiàng)重要的任務(wù)。分類的目的是學(xué)會(huì)一個(gè)分類函數(shù)或分類模型（也稱的目的是學(xué)會(huì)一個(gè)分類函數(shù)或分類模型（也稱分類器），該模型能把數(shù)據(jù)庫中的數(shù)據(jù)項(xiàng)映射分類器），該模型能把數(shù)據(jù)庫中的數(shù)據(jù)項(xiàng)映射到給定類別中的某一個(gè)類別。分類可用于預(yù)測。到給定類別中的某一個(gè)類別。分類可用于預(yù)測。為了區(qū)分分類中的預(yù)測，規(guī)定分類的輸出為離為了區(qū)分分類中的預(yù)測，規(guī)定分類的輸出為離散的類別值，預(yù)測的輸出是連續(xù)值。散的類別值，預(yù)測的輸出是連續(xù)值。n 分類具有廣泛的應(yīng)用，如醫(yī)療診斷、信用分類具有廣泛的應(yīng)用，如

2、醫(yī)療診斷、信用卡系統(tǒng)的信用分級、圖像模式識別等?？ㄏ到y(tǒng)的信用分級、圖像模式識別等。第7章 數(shù)據(jù)分類n本章目標(biāo)本章目標(biāo)掌握分類的基本概念；掌握分類的基本概念；了解基于距離的分類算法了解基于距離的分類算法熟練掌握熟練掌握ID3ID3、C4.5C4.5決策樹分類算法；決策樹分類算法；了解貝葉斯分類了解貝葉斯分類. .數(shù)據(jù)分類n7.1分類的基本概念分類的基本概念n7.2基于距離的分類算法基于距離的分類算法n7.3決策樹分類決策樹分類n7.4貝葉斯分類貝葉斯分類7.1 分類的基本概念n 定義定義1：給定一個(gè)數(shù)據(jù)庫給定一個(gè)數(shù)據(jù)庫 D=t1，t2，tn和一組和一組類類 C=C1，Cm，分類問題是去確定一個(gè)映

3、射，分類問題是去確定一個(gè)映射 f: DC，使得每個(gè)元組，使得每個(gè)元組ti被分配到一個(gè)類中。一個(gè)類被分配到一個(gè)類中。一個(gè)類Cj 包包含映射到該類中的所有元組，即含映射到該類中的所有元組，即Cj = ti | f(ti) = Cj，1 i n， 而且而且ti D。n 例例1：根據(jù)分?jǐn)?shù)把學(xué)生分成優(yōu)秀、良好、一般、及：根據(jù)分?jǐn)?shù)把學(xué)生分成優(yōu)秀、良好、一般、及格、不及格五類，只需通過簡單的分界線格、不及格五類，只需通過簡單的分界線(90,80,70,60)即可實(shí)現(xiàn)。即可實(shí)現(xiàn)。n 解決分類問題的關(guān)鍵是構(gòu)造一個(gè)合適的分類器：解決分類問題的關(guān)鍵是構(gòu)造一個(gè)合適的分類器：從數(shù)據(jù)庫到一組類別集的映射。一般地，這些類是

4、被預(yù)從數(shù)據(jù)庫到一組類別集的映射。一般地，這些類是被預(yù)先定義的、非交疊的。先定義的、非交疊的。7.1 分類的基本概念n數(shù)據(jù)分類一般分為兩個(gè)步驟：建模和使用。數(shù)據(jù)分類一般分為兩個(gè)步驟：建模和使用。n1建立一個(gè)模型，描述預(yù)定的數(shù)據(jù)類集或概念集建立一個(gè)模型，描述預(yù)定的數(shù)據(jù)類集或概念集數(shù)據(jù)元組也稱作樣本、實(shí)例或?qū)ο?。?shù)據(jù)元組也稱作樣本、實(shí)例或?qū)ο?。為建立模型而被分析的?shù)據(jù)元組形成為建立模型而被分析的數(shù)據(jù)元組形成訓(xùn)練數(shù)據(jù)集訓(xùn)練數(shù)據(jù)集。訓(xùn)練數(shù)據(jù)集中的單個(gè)元組稱作訓(xùn)練樣本，由于提供了訓(xùn)練數(shù)據(jù)集中的單個(gè)元組稱作訓(xùn)練樣本，由于提供了每個(gè)訓(xùn)練樣本的類標(biāo)號，因此也稱作有指導(dǎo)的學(xué)習(xí)。每個(gè)訓(xùn)練樣本的類標(biāo)號，因此也稱作有指

5、導(dǎo)的學(xué)習(xí)。通過分析訓(xùn)練數(shù)據(jù)集來構(gòu)造分類模型，可用分類規(guī)則、通過分析訓(xùn)練數(shù)據(jù)集來構(gòu)造分類模型，可用分類規(guī)則、決策樹或數(shù)學(xué)公式等形式提供。決策樹或數(shù)學(xué)公式等形式提供。7.1 分類的基本概念n2使用模型進(jìn)行分類使用模型進(jìn)行分類首先評估模型（分類法）的預(yù)測準(zhǔn)確率。保持首先評估模型（分類法）的預(yù)測準(zhǔn)確率。保持（holdout）方法是一種使用類標(biāo)號樣本測試集的簡）方法是一種使用類標(biāo)號樣本測試集的簡單方法，這些樣本隨機(jī)選取，并獨(dú)立于訓(xùn)練樣本，單方法，這些樣本隨機(jī)選取，并獨(dú)立于訓(xùn)練樣本，對于每個(gè)測試樣本，將已知的類標(biāo)號與該樣本的學(xué)對于每個(gè)測試樣本，將已知的類標(biāo)號與該樣本的學(xué)習(xí)模型類預(yù)測比較。計(jì)算出正確被模型分

6、類的測試習(xí)模型類預(yù)測比較。計(jì)算出正確被模型分類的測試樣本的百分比，即模型準(zhǔn)確率。樣本的百分比，即模型準(zhǔn)確率。如果認(rèn)為模型的準(zhǔn)確率可以接受，就可以用它對類如果認(rèn)為模型的準(zhǔn)確率可以接受，就可以用它對類標(biāo)號未知的數(shù)據(jù)元組或?qū)ο筮M(jìn)行分類。標(biāo)號未知的數(shù)據(jù)元組或?qū)ο筮M(jìn)行分類。7.1 分類的基本概念n 例例2：假定我們有一個(gè)：假定我們有一個(gè)AllElectronics 的郵寄清單數(shù)的郵寄清單數(shù)據(jù)庫。郵寄清單用于分發(fā)介紹新產(chǎn)品和降價(jià)信息材料。據(jù)庫。郵寄清單用于分發(fā)介紹新產(chǎn)品和降價(jià)信息材料。數(shù)據(jù)庫描述顧客的屬性，如他們的姓名、年齡、收入和數(shù)據(jù)庫描述顧客的屬性，如他們的姓名、年齡、收入和信譽(yù)度。顧客可以按他們是否

7、在信譽(yù)度。顧客可以按他們是否在AllElectronics 購買計(jì)購買計(jì)算機(jī)分類。假定新的顧客添加到數(shù)據(jù)庫中，你想將新計(jì)算機(jī)分類。假定新的顧客添加到數(shù)據(jù)庫中，你想將新計(jì)算機(jī)的銷售信息通知顧客。將促銷材料分發(fā)給數(shù)據(jù)庫中算機(jī)的銷售信息通知顧客。將促銷材料分發(fā)給數(shù)據(jù)庫中的每個(gè)新顧客的費(fèi)用可能很高。一個(gè)更有效的方法是只的每個(gè)新顧客的費(fèi)用可能很高。一個(gè)更有效的方法是只給那些可能買新計(jì)算機(jī)的顧客寄材料。為此，可以構(gòu)造給那些可能買新計(jì)算機(jī)的顧客寄材料。為此，可以構(gòu)造和使用分類模型。和使用分類模型。 7.1 分類的基本概念7.1 分類的基本概念n分類器的構(gòu)造方法有很多，典型有：分類器的構(gòu)造方法有很多，典型有：

8、 統(tǒng)計(jì)：包括貝葉斯法和非參數(shù)法。常見的臨近學(xué)習(xí)統(tǒng)計(jì)：包括貝葉斯法和非參數(shù)法。常見的臨近學(xué)習(xí)或基于事例的學(xué)習(xí)屬于非參數(shù)方法。對應(yīng)的知識表示為或基于事例的學(xué)習(xí)屬于非參數(shù)方法。對應(yīng)的知識表示為判別函數(shù)和原型事例。判別函數(shù)和原型事例。 機(jī)器學(xué)習(xí)：包括決策樹法和規(guī)則歸納法，前者表示機(jī)器學(xué)習(xí)：包括決策樹法和規(guī)則歸納法，前者表示為決策樹或判別樹，后者則一般為產(chǎn)生式規(guī)則。為決策樹或判別樹，后者則一般為產(chǎn)生式規(guī)則。 神經(jīng)網(wǎng)絡(luò)：主要是神經(jīng)網(wǎng)絡(luò)：主要是BP算法，本質(zhì)上是一種非線性判算法，本質(zhì)上是一種非線性判別函數(shù)。別函數(shù)。 粗糙集：知識表示是產(chǎn)生式規(guī)則。粗糙集：知識表示是產(chǎn)生式規(guī)則。 其他：如支持向量機(jī)等。其他：如

9、支持向量機(jī)等。7.1 分類的基本概念n判別分類方法的好壞可以從三個(gè)方面進(jìn)行：判別分類方法的好壞可以從三個(gè)方面進(jìn)行：1）預(yù)測準(zhǔn)確度（對非樣本數(shù)據(jù)的判別準(zhǔn)確度）；）預(yù)測準(zhǔn)確度（對非樣本數(shù)據(jù)的判別準(zhǔn)確度）；2）計(jì)算復(fù)雜度（方法實(shí)現(xiàn)對時(shí)間和空間的復(fù)雜度）；）計(jì)算復(fù)雜度（方法實(shí)現(xiàn)對時(shí)間和空間的復(fù)雜度）；3）模式的簡潔度（在同樣效果情況下，希望決策樹?。┠Ｊ降暮啙嵍龋ㄔ谕瑯有Ч闆r下，希望決策樹小或規(guī)則少）?；蛞?guī)則少）。 7.2 基于距離的分類算法n 基于距離的分類算法比較直觀。假定數(shù)據(jù)庫中的每基于距離的分類算法比較直觀。假定數(shù)據(jù)庫中的每個(gè)元組個(gè)元組ti為數(shù)值向量，每個(gè)類用一個(gè)典型數(shù)值向量來表為數(shù)值向量，

10、每個(gè)類用一個(gè)典型數(shù)值向量來表示，通過分配每個(gè)元組到它最相似的類來實(shí)現(xiàn)分類。示，通過分配每個(gè)元組到它最相似的類來實(shí)現(xiàn)分類。n 定義定義1 給定一個(gè)數(shù)據(jù)庫給定一個(gè)數(shù)據(jù)庫 D=t1，t2，tn和一組類和一組類C=C1，Cm。假定每個(gè)元組包括一些數(shù)值型的屬性。假定每個(gè)元組包括一些數(shù)值型的屬性值：值：ti=ti1，ti2，tik，每個(gè)類也包含數(shù)值性屬性值：，每個(gè)類也包含數(shù)值性屬性值：Cj=Cj1，Cj2，Cjk，則分類問題是要分配每個(gè)，則分類問題是要分配每個(gè)ti到滿到滿足如下條件的類足如下條件的類Cj： sim(ti，Cj)=sim(ti，Cl) ， ClC，ClCj， 其中其中sim(ti，Cj)被稱

11、為相似性。被稱為相似性。7.2 基于距離的分類算法n在實(shí)際的計(jì)算中往往用距離來表征，距離越近，相似性在實(shí)際的計(jì)算中往往用距離來表征，距離越近，相似性越大，距離越遠(yuǎn)，相似性越小。越大，距離越遠(yuǎn)，相似性越小。算法算法 1 基于距離的分類算法基于距離的分類算法輸入：每個(gè)類的中心輸入：每個(gè)類的中心C1，Cm；待分類的元組；待分類的元組t。 輸出：輸出類別輸出：輸出類別c。 （1）dist=；/距離初始化距離初始化（2）FOR i:=1 to m DO （3） IF dis(ci，t)dist THEN BEGIN（4）c i； （5）distdist(ci，t)；（6） END7.2 基于距離的分類算

12、法（a）類定義）類定義（b）待分類樣例）待分類樣例（c）分類結(jié)果）分類結(jié)果7.3 決策樹分類n 決策樹是一個(gè)類似于流程圖的樹結(jié)構(gòu)。每個(gè)內(nèi)決策樹是一個(gè)類似于流程圖的樹結(jié)構(gòu)。每個(gè)內(nèi)部結(jié)點(diǎn)表示在一個(gè)屬性上的測試，每個(gè)分枝代表一部結(jié)點(diǎn)表示在一個(gè)屬性上的測試，每個(gè)分枝代表一個(gè)測試輸出，而每個(gè)樹葉結(jié)點(diǎn)代表類或類分布。樹個(gè)測試輸出，而每個(gè)樹葉結(jié)點(diǎn)代表類或類分布。樹的最頂層結(jié)點(diǎn)是根結(jié)點(diǎn)。的最頂層結(jié)點(diǎn)是根結(jié)點(diǎn)。7.3 決策樹分類n 決策樹分類方法采用自頂向下的遞歸方式，在決策決策樹分類方法采用自頂向下的遞歸方式，在決策樹的內(nèi)部結(jié)點(diǎn)進(jìn)行屬性值的比較并根據(jù)不同的屬性值判樹的內(nèi)部結(jié)點(diǎn)進(jìn)行屬性值的比較并根據(jù)不同的屬性值

13、判斷從該結(jié)點(diǎn)向下的分枝，在葉結(jié)點(diǎn)得到結(jié)論。從決策樹斷從該結(jié)點(diǎn)向下的分枝，在葉結(jié)點(diǎn)得到結(jié)論。從決策樹的根到葉結(jié)點(diǎn)的一條路徑就對應(yīng)著一條分類規(guī)則。的根到葉結(jié)點(diǎn)的一條路徑就對應(yīng)著一條分類規(guī)則。n 基于決策樹的分類算法的一個(gè)最大的優(yōu)點(diǎn)就是它在基于決策樹的分類算法的一個(gè)最大的優(yōu)點(diǎn)就是它在學(xué)習(xí)過程中不需要使用者了解很多背景知識（這同時(shí)也學(xué)習(xí)過程中不需要使用者了解很多背景知識（這同時(shí)也是它的最大的缺點(diǎn)），只要訓(xùn)練例子能夠用屬性是它的最大的缺點(diǎn)），只要訓(xùn)練例子能夠用屬性-結(jié)論式結(jié)論式表示出來，就能使用該算法來學(xué)習(xí)。表示出來，就能使用該算法來學(xué)習(xí)。n 決策樹分類模型的建立通常分為兩個(gè)步驟：決策樹分類模型的建立通

14、常分為兩個(gè)步驟：決策樹決策樹生成、決策樹修剪。生成、決策樹修剪。7.3.17.3.1決策樹生成算法決策樹生成算法算法：算法：Generate_decision_tree(S, attribute_list)輸入：訓(xùn)練樣本輸入：訓(xùn)練樣本samples，由離散值屬性表示；候選屬性的集合，由離散值屬性表示；候選屬性的集合attribute_list。輸出：一棵決策樹輸出：一棵決策樹。(1) 創(chuàng)建結(jié)點(diǎn)創(chuàng)建結(jié)點(diǎn) N；(2) if samples 都在同一個(gè)類都在同一個(gè)類C then(3) return N 作為葉結(jié)點(diǎn)，以類作為葉結(jié)點(diǎn)，以類C 標(biāo)記；標(biāo)記；(4) if attribute_list 為空為

15、空 then(5) return N 作為葉結(jié)點(diǎn)，標(biāo)記為作為葉結(jié)點(diǎn)，標(biāo)記為 samples中最普通的類（即其父結(jié)點(diǎn)中出現(xiàn)頻中最普通的類（即其父結(jié)點(diǎn)中出現(xiàn)頻率最高的類）；率最高的類）； /majority voting(6) 選擇選擇attribute_list中具有最高信息增益的屬性中具有最高信息增益的屬性test_attribute；(7) 標(biāo)記結(jié)點(diǎn)標(biāo)記結(jié)點(diǎn) N 為為test_attribute；(8) for each test_attribute 中的未知值中的未知值a i /partition the samples(9) 由結(jié)點(diǎn)由結(jié)點(diǎn) N 長出一個(gè)條件為長出一個(gè)條件為 test_at

16、tribute = a i的分枝；的分枝；(10) 設(shè)設(shè)si 是是samples 中中test_attribute = a i的樣本的集合；的樣本的集合；/a partition(11) if si 為空為空 then(12) 加上一個(gè)樹葉，標(biāo)記為加上一個(gè)樹葉，標(biāo)記為 samples中最普通的類；中最普通的類；(13) else 加上一個(gè)由加上一個(gè)由 Generate_decision_tree( si, attribute_list test_attribute)返返回的結(jié)點(diǎn)；回的結(jié)點(diǎn)；算法的基本策略如下：算法的基本策略如下： 樹以代表訓(xùn)練樣本的單個(gè)結(jié)點(diǎn)開始（步驟樹以代表訓(xùn)練樣本的單個(gè)結(jié)點(diǎn)開

17、始（步驟1）。）。 如果樣本都在同一個(gè)類，該結(jié)點(diǎn)成為樹葉，用該類標(biāo)號（步驟如果樣本都在同一個(gè)類，該結(jié)點(diǎn)成為樹葉，用該類標(biāo)號（步驟2 和和3）。）。 否則，算法使用稱為信息增益的基于熵的度量作為啟發(fā)信息，選擇能夠最否則，算法使用稱為信息增益的基于熵的度量作為啟發(fā)信息，選擇能夠最好地將樣本分類的屬性（步驟好地將樣本分類的屬性（步驟6）。該屬性成為該結(jié)點(diǎn)的）。該屬性成為該結(jié)點(diǎn)的“測試測試”或或“判定判定”屬屬性（步驟性（步驟7）。）。 對測試屬性的每個(gè)已知值，創(chuàng)建一個(gè)分枝，據(jù)此劃分樣本（步驟對測試屬性的每個(gè)已知值，創(chuàng)建一個(gè)分枝，據(jù)此劃分樣本（步驟8-10）。）。 算法使用同樣的過程，遞歸地形成每個(gè)劃

18、分上的樣本決策樹。一旦一個(gè)屬算法使用同樣的過程，遞歸地形成每個(gè)劃分上的樣本決策樹。一旦一個(gè)屬性出現(xiàn)在一個(gè)結(jié)點(diǎn)上，就不必該結(jié)點(diǎn)的任何后代上考慮它（步驟性出現(xiàn)在一個(gè)結(jié)點(diǎn)上，就不必該結(jié)點(diǎn)的任何后代上考慮它（步驟13）。）。 遞歸劃分步驟僅當(dāng)下列條件之一成立停止：遞歸劃分步驟僅當(dāng)下列條件之一成立停止： (a) 給定結(jié)點(diǎn)的所有樣本屬于同一類（步驟給定結(jié)點(diǎn)的所有樣本屬于同一類（步驟2 和和3）。）。 (b) 沒有剩余屬性可以用來進(jìn)一步劃分樣本（步驟沒有剩余屬性可以用來進(jìn)一步劃分樣本（步驟4）。在此情況下，使用多數(shù)）。在此情況下，使用多數(shù)表決（步驟表決（步驟5）。）。 這涉及將給定的結(jié)點(diǎn)轉(zhuǎn)換成樹葉，并用樣本

19、中的多數(shù)所在的類標(biāo)記它。替換地，這涉及將給定的結(jié)點(diǎn)轉(zhuǎn)換成樹葉，并用樣本中的多數(shù)所在的類標(biāo)記它。替換地，可以存放結(jié)點(diǎn)樣本的類分布?？梢源娣沤Y(jié)點(diǎn)樣本的類分布。 (c) 分枝分枝test_attribute = a i沒有樣本（步驟沒有樣本（步驟11）。在這種情況下，以）。在這種情況下，以samples中的中的多數(shù)類創(chuàng)建一個(gè)樹葉（步驟多數(shù)類創(chuàng)建一個(gè)樹葉（步驟12）。）。 7.3 決策樹分類7.3.17.3.1決策樹生成算法決策樹生成算法n 構(gòu)造好的決策樹的關(guān)鍵在于如何選擇好的屬性進(jìn)行構(gòu)造好的決策樹的關(guān)鍵在于如何選擇好的屬性進(jìn)行樹的拓展。一般情況下或具有較大概率地說，樹越小則樹的拓展。一般情況下或具有

20、較大概率地說，樹越小則樹的預(yù)測能力越強(qiáng)。樹的預(yù)測能力越強(qiáng)。n 上述算法中，在樹的每個(gè)結(jié)點(diǎn)上使用具有最高信息上述算法中，在樹的每個(gè)結(jié)點(diǎn)上使用具有最高信息增益（或最大熵壓縮）的屬性作為測試屬性。該屬性使增益（或最大熵壓縮）的屬性作為測試屬性。該屬性使得對結(jié)果劃分中的樣本分類所需的信息量最小，并反映得對結(jié)果劃分中的樣本分類所需的信息量最小，并反映劃分的最小隨機(jī)性或劃分的最小隨機(jī)性或 “不純性不純性”。這種信息理論方法使。這種信息理論方法使得對一個(gè)對象分類所需的期望測試數(shù)目最小，并確保找得對一個(gè)對象分類所需的期望測試數(shù)目最小，并確保找到一棵簡單的（但不必是最簡單的）樹。到一棵簡單的（但不必是最簡單的）

21、樹。7.3 決策樹分類7.3.17.3.1決策樹生成算法決策樹生成算法n 屬性選擇依賴于各種對例子子集的不純度屬性選擇依賴于各種對例子子集的不純度（Impurity）度量方法，包括信息增益（）度量方法，包括信息增益（Information Gain）、信息增益比（）、信息增益比（Gain Ratio）、）、Gini-index、距離、距離度量（度量（Distance Measure）、）、J-measure、G統(tǒng)計(jì)、統(tǒng)計(jì)、 2統(tǒng)統(tǒng)計(jì)、證據(jù)權(quán)重（計(jì)、證據(jù)權(quán)重（Weight of Evidence）、最小描述長度）、最小描述長度（MLP）、正交法（）、正交法（Orthogonal Measure）

22、、相關(guān)度）、相關(guān)度（Relevance）和）和 Relief等。等。7.3 決策樹分類7.3.2 ID37.3.2 ID3算法算法n ID3是是Quinlan提出的一個(gè)著名決策樹生成方法。提出的一個(gè)著名決策樹生成方法。n決策樹中每一個(gè)非葉結(jié)點(diǎn)對應(yīng)著一個(gè)非類別屬性，樹決策樹中每一個(gè)非葉結(jié)點(diǎn)對應(yīng)著一個(gè)非類別屬性，樹枝代表這個(gè)屬性的值。一個(gè)葉結(jié)點(diǎn)代表從樹根到葉結(jié)枝代表這個(gè)屬性的值。一個(gè)葉結(jié)點(diǎn)代表從樹根到葉結(jié)點(diǎn)之間的路徑對應(yīng)的記錄所屬的類別屬性值。點(diǎn)之間的路徑對應(yīng)的記錄所屬的類別屬性值。n每一個(gè)非葉結(jié)點(diǎn)都將與屬性中具有最大信息量的非類每一個(gè)非葉結(jié)點(diǎn)都將與屬性中具有最大信息量的非類別屬性相關(guān)聯(lián)。別屬性相

23、關(guān)聯(lián)。n采用信息增益來選擇能夠最好地將樣本分類的屬性。采用信息增益來選擇能夠最好地將樣本分類的屬性。n（1 1）信息熵的概念）信息熵的概念n 信源是信源是Shannon創(chuàng)立的信息論中的一個(gè)基本概念，創(chuàng)立的信息論中的一個(gè)基本概念，表示信息的來源。信源發(fā)出的符號信息就是信號。由于表示信息的來源。信源發(fā)出的符號信息就是信號。由于信號帶有隨機(jī)性，常用隨機(jī)變量表示。設(shè)信源信號帶有隨機(jī)性，常用隨機(jī)變量表示。設(shè)信源X的符號取的符號取值集合為值集合為A=a1, a2, , an，其中信號，其中信號ai A出現(xiàn)的概率為出現(xiàn)的概率為pi=PX=ai(i=1, 2, , n)，稱，稱 為為ai的信息量。的信息量。i

24、iippaIlog1log)(7.3 決策樹分類7.3.2ID37.3.2ID3算法算法n 信息量的數(shù)學(xué)期望稱為信源的平均信息量或信息熵，信息量的數(shù)學(xué)期望稱為信源的平均信息量或信息熵，簡稱為熵（簡稱為熵（entropy），記為），記為H(X)或或Hn(p1, p2, , pn)，有，有 信息熵表示信源的不確定性，反映了信源在平均意信息熵表示信源的不確定性，反映了信源在平均意義上所具有的信息量的大小。在上式中，對數(shù)的底可取義上所具有的信息量的大小。在上式中，對數(shù)的底可取2、3、10或或e，熵的單位相應(yīng)的可以是比特（二進(jìn)制）、鐵，熵的單位相應(yīng)的可以是比特（二進(jìn)制）、鐵特（三進(jìn)制）、笛特（十進(jìn)制）或

25、奈特（自然單位），特（三進(jìn)制）、笛特（十進(jìn)制）或奈特（自然單位），其中比特為最常用的表示方法。其中比特為最常用的表示方法。niiiniiiniiippppppXH1111, 10log1log)(，其中7.3 決策樹分類7.3.2ID37.3.2ID3算法算法niiiniiiniiippppppXH1111, 10log1log)(，其中n（2）決策樹歸納的具體算法）決策樹歸納的具體算法n 設(shè)設(shè)S是是s個(gè)數(shù)據(jù)樣本的集合。假定類標(biāo)號屬性具有個(gè)數(shù)據(jù)樣本的集合。假定類標(biāo)號屬性具有m個(gè)不同值，定義個(gè)不同值，定義m個(gè)不同類個(gè)不同類Ci (i = 1,.,m)。設(shè)。設(shè)si是類是類Ci中中的樣本數(shù)。對一個(gè)給

26、定的樣本分類，期望信息由下式給的樣本數(shù)。對一個(gè)給定的樣本分類，期望信息由下式給出：出： 其中，其中，pi是任意樣本屬于是任意樣本屬于Ci的概率，并用的概率，并用si/s估計(jì)。估計(jì)。注意，對數(shù)函數(shù)以注意，對數(shù)函數(shù)以2為底，因?yàn)樾畔⒂枚M(jìn)位編碼。為底，因?yàn)樾畔⒂枚M(jìn)位編碼。7.3 決策樹分類7.3.2ID37.3.2ID3算法算法n 設(shè)屬性設(shè)屬性A具有具有v個(gè)不同值個(gè)不同值 a1 ,., av?？梢杂脤傩??？梢杂脤傩訟將將S劃分為劃分為v個(gè)子集個(gè)子集 S1 ,., Sv；其中，；其中，Sj包含包含S中這樣一中這樣一些樣本，它們在些樣本，它們在A上具有值上具有值aj。如果。如果A選作測試屬性選作測試

27、屬性（即，最好的劃分屬性），則這些子集對應(yīng)于由包含（即，最好的劃分屬性），則這些子集對應(yīng)于由包含集合集合S的結(jié)點(diǎn)生長出來的分枝。設(shè)的結(jié)點(diǎn)生長出來的分枝。設(shè)sij是子集是子集Sj中類中類Ci的樣的樣本數(shù)。根據(jù)本數(shù)。根據(jù)A劃分子集的熵或期望信息由下式給出：劃分子集的熵或期望信息由下式給出： 7.3 決策樹分類7.3.2ID37.3.2ID3算法算法n 在在A上分枝將獲得的編碼信息是上分枝將獲得的編碼信息是 計(jì)算每個(gè)屬性的信息增益。具有最高信息增益的計(jì)算每個(gè)屬性的信息增益。具有最高信息增益的屬性選作給定集合屬性選作給定集合S的測試屬性。創(chuàng)建一個(gè)結(jié)點(diǎn)，并以的測試屬性。創(chuàng)建一個(gè)結(jié)點(diǎn)，并以該屬性標(biāo)記。對屬

28、性的每個(gè)值創(chuàng)建分枝，并據(jù)此劃分該屬性標(biāo)記。對屬性的每個(gè)值創(chuàng)建分枝，并據(jù)此劃分樣本。樣本。n 下面給出一個(gè)具體實(shí)例。下面給出一個(gè)具體實(shí)例。7.3 決策樹分類7.3.2ID37.3.2ID3算法算法例例 用用ID3算法進(jìn)行決策樹分類。算法進(jìn)行決策樹分類。類標(biāo)號屬性類標(biāo)號屬性buys_computer有兩個(gè)不同值即有兩個(gè)不同值即yes, no，因此有，因此有兩個(gè)不同的類兩個(gè)不同的類(m=2)。設(shè)類。設(shè)類C1對應(yīng)于對應(yīng)于yes，而類，而類C2對應(yīng)于對應(yīng)于no。類類yes有有9個(gè)樣本，類個(gè)樣本，類no有有5個(gè)樣本。個(gè)樣本。從屬性從屬性ageage開始計(jì)算每個(gè)屬性的熵。需要觀察開始計(jì)算每個(gè)屬性的熵。需要觀

29、察ageage的每個(gè)樣本的每個(gè)樣本值的值的yesyes和和nono分布，對每個(gè)分布計(jì)算期望信息。分布，對每個(gè)分布計(jì)算期望信息。age= ”40”：s13 = 3, s23 = 2, I(s13, s23) = 0.971 類似地：類似地：Gain(income)=0.029, Gain(student)=0.151， Gain(credit_rating)=0.048。 由于由于age在屬性中具有最高信息增益，它被選作測試屬在屬性中具有最高信息增益，它被選作測試屬性。創(chuàng)建一個(gè)結(jié)點(diǎn)，用性。創(chuàng)建一個(gè)結(jié)點(diǎn)，用age標(biāo)記，并對于每個(gè)屬性值，引出標(biāo)記，并對于每個(gè)屬性值，引出一個(gè)分枝。算法返回的最終決策樹

30、如圖所示。一個(gè)分枝。算法返回的最終決策樹如圖所示。課堂練習(xí)課堂練習(xí) 用用ID3算法進(jìn)行決策樹分類。算法進(jìn)行決策樹分類。顏色顏色形狀形狀蔬菜蔬菜紅紅圓圓番茄番茄紫紫長長茄子茄子綠綠長長黃瓜黃瓜？從中得出什么直觀的結(jié)論？從中得出什么直觀的結(jié)論？不給任何描述屬性時(shí)，類屬性分類期望信息（熵）最大，不給任何描述屬性時(shí)，類屬性分類期望信息（熵）最大，代表的不確定性最大；當(dāng)給出描述屬性時(shí)，對應(yīng)的描述屬代表的不確定性最大；當(dāng)給出描述屬性時(shí)，對應(yīng)的描述屬性分類期望信息（熵）減少，不確定性降低；不同描述屬性分類期望信息（熵）減少，不確定性降低；不同描述屬性對減少類屬性的不確定性貢獻(xiàn)不同。性對減少類屬性的不確定性貢

31、獻(xiàn)不同。數(shù)據(jù)分類算法應(yīng)該是盡可能選擇對減少不確定性貢獻(xiàn)最大數(shù)據(jù)分類算法應(yīng)該是盡可能選擇對減少不確定性貢獻(xiàn)最大的描述屬性，而的描述屬性，而Gain(屬性屬性)表示的就是屬性減少分類的不表示的就是屬性減少分類的不確定性程度，則確定性程度，則Gain(屬性屬性)越大，越應(yīng)該優(yōu)選對應(yīng)屬性作越大，越應(yīng)該優(yōu)選對應(yīng)屬性作為測試屬性。為測試屬性。n C4.5算法是從算法是從ID3算法演變而來，除了擁有算法演變而來，除了擁有ID3算法的算法的功能外，功能外，C4.5算法引入了新的方法和增加了新的功能：算法引入了新的方法和增加了新的功能： 用信息增益比例的概念；用信息增益比例的概念； 合并具有連續(xù)屬性的值；合并具

32、有連續(xù)屬性的值； 可以處理具有缺少屬性值的訓(xùn)練樣本；可以處理具有缺少屬性值的訓(xùn)練樣本； 通過使用不同的修剪技術(shù)以避免樹的過度擬合；通過使用不同的修剪技術(shù)以避免樹的過度擬合； K交叉驗(yàn)證；交叉驗(yàn)證； 規(guī)則的產(chǎn)生方式等。規(guī)則的產(chǎn)生方式等。7.3 決策樹分類7.3.3 C4.57.3.3 C4.5算法算法7.3 決策樹分類7.3.3 C4.57.3.3 C4.5算法算法n （1）信息增益比例的概念）信息增益比例的概念)()()(ASplitIAGainAGainRatio假如以屬性假如以屬性A的值為基準(zhǔn)對樣本進(jìn)行分割的化，的值為基準(zhǔn)對樣本進(jìn)行分割的化，Splitl(A)就是前面熵的概念。就是前面熵的

33、概念。)(log)(12jvjjppASplitI其中其中7.3 決策樹分類7.3.3 C4.57.3.3 C4.5算法算法n （2）合并具有連續(xù)值的屬性）合并具有連續(xù)值的屬性 根據(jù)屬性的值，對數(shù)據(jù)集排序；根據(jù)屬性的值，對數(shù)據(jù)集排序； 按順序逐一將兩個(gè)相鄰樣本的平均值作為分割點(diǎn)，按順序逐一將兩個(gè)相鄰樣本的平均值作為分割點(diǎn)，r=（A1+A2）/2。假設(shè)訓(xùn)練集有。假設(shè)訓(xùn)練集有n個(gè)樣本，則共有個(gè)樣本，則共有n-1個(gè)個(gè)分割點(diǎn)。分割點(diǎn)將訓(xùn)練集劃分為兩部分，一部分分割點(diǎn)。分割點(diǎn)將訓(xùn)練集劃分為兩部分，一部分A的的值小于等于分割點(diǎn)，另一部分值小于等于分割點(diǎn)，另一部分A的值大于分割點(diǎn)。的值大于分割點(diǎn)。 針對每個(gè)

34、劃分，分別計(jì)算增益比；針對每個(gè)劃分，分別計(jì)算增益比； 將最優(yōu)的分割點(diǎn)作為臨界值將最優(yōu)的分割點(diǎn)作為臨界值r。7.3 決策樹分類7.3.3 C4.57.3.3 C4.5算法算法n（3）處理含有未知屬性值的訓(xùn)練樣本）處理含有未知屬性值的訓(xùn)練樣本處理方法是用最常用的值替代或者是將最常用的值分處理方法是用最常用的值替代或者是將最常用的值分在同一類中。具體采用概率的方法，依據(jù)屬性已知的在同一類中。具體采用概率的方法，依據(jù)屬性已知的值，對屬性和每一個(gè)值賦予一個(gè)概率，取得這些概率，值，對屬性和每一個(gè)值賦予一個(gè)概率，取得這些概率，取得這些概率依賴于該屬性已知的值。取得這些概率依賴于該屬性已知的值。n（4）規(guī)則的

35、產(chǎn)生）規(guī)則的產(chǎn)生一旦樹被建立，就可以把樹轉(zhuǎn)換成一旦樹被建立，就可以把樹轉(zhuǎn)換成if-then規(guī)則。規(guī)則。n例例5 用用C4.5算法進(jìn)行分類。算法進(jìn)行分類。OutlookTemperatureHumidityWindPlayTennisSunnyHot85falseNoSunnyHot90trueNoOvercastHot78falseYesRainMild96falseYesRainCool80falseYesRainCool70trueNoOvercastCool65trueYesSunnyMild95falseNoSunnyCool70falseYesRainMild80falseYesSu

36、nnyMild70trueYesOvercastMild90trueYesOvercastHot75falseYesRainMild80trueNo（1）首先對）首先對Humidity進(jìn)行屬性離散化，針對上面的訓(xùn)練集合，通進(jìn)行屬性離散化，針對上面的訓(xùn)練集合，通過檢測每個(gè)劃分而確定最好的劃分在過檢測每個(gè)劃分而確定最好的劃分在75處，則這個(gè)屬性的范圍處，則這個(gè)屬性的范圍就變?yōu)榫妥優(yōu)椋?5）。（2）計(jì)算目標(biāo)屬性）計(jì)算目標(biāo)屬性PlayTennis分類的期望信息：分類的期望信息：940. 0145log145149log149)5 , 9(),(2221 IssI（3）計(jì)算）計(jì)算outlook的的spl

37、itI：577. 1145log145144log144145log145)(222outlookSplitI（4）計(jì)算）計(jì)算outlook的熵：的熵：outlook= ”sunny”：s11 = 2, s21 = 3, I(s11, s21)=0.971outlook= ”overcast” ：s12 = 4, s22 = 0, I(s12, s22) = 0outlook= ”rain”：s13 = 3, s23 = 2, I(s13, s23) = 0.971694. 0971. 01450971. 0145)(outlookE04830024800490. Humidity)GainR

38、atio(；. e)TemperaturGainRatio(；.windy)GainRatio(（5）計(jì)算其余屬性的）計(jì)算其余屬性的GainRatio：（6）選取最大的）選取最大的GainRatio，根據(jù)，根據(jù)Outlook的取值，將三分枝。的取值，將三分枝。（7）再擴(kuò)展各分枝節(jié)點(diǎn)，得到最終的決策樹。）再擴(kuò)展各分枝節(jié)點(diǎn)，得到最終的決策樹。246. 0694. 0940. 0)(),()(21outlookEssIoutlookGain；156. 0577. 1246. 0)(OutlookGainRatioOutlook?Humidity?Windy?sunnyovercastrain 757

39、5truefalseyesyesnonoyes（8）生成規(guī)則）生成規(guī)則IF outlook = ”sunny” AND humidity = “ 75” THEN playtennis = “ no”IF outlook = ”sunny” AND humidity = “ 75” THEN playtennis = “ yes”IF outlook = ”overcast” THEN playtennis = “ yes”IF outlook = ”rain” AND windy =“ true” THEN playtennis = “ no”IF outlook = ”rain” AND

40、windy =“ false” THEN playtennis = “ yes”n 當(dāng)決策樹創(chuàng)建時(shí)，由于數(shù)據(jù)中的噪音和局外者，許當(dāng)決策樹創(chuàng)建時(shí)，由于數(shù)據(jù)中的噪音和局外者，許多分枝反映的是訓(xùn)練數(shù)據(jù)中的異常。剪枝方法處理這種多分枝反映的是訓(xùn)練數(shù)據(jù)中的異常。剪枝方法處理這種過分適應(yīng)數(shù)據(jù)問題。事實(shí)上，簡單的決策樹不僅可以加過分適應(yīng)數(shù)據(jù)問題。事實(shí)上，簡單的決策樹不僅可以加快分類的速度，而且有助于提高對新數(shù)據(jù)準(zhǔn)確分類的能快分類的速度，而且有助于提高對新數(shù)據(jù)準(zhǔn)確分類的能力。反之，決策樹越復(fù)雜，結(jié)點(diǎn)越多，每個(gè)結(jié)點(diǎn)所包含力。反之，決策樹越復(fù)雜，結(jié)點(diǎn)越多，每個(gè)結(jié)點(diǎn)所包含的訓(xùn)練樣本就越少，那么結(jié)點(diǎn)對應(yīng)假設(shè)的代表性就

41、越低，的訓(xùn)練樣本就越少，那么結(jié)點(diǎn)對應(yīng)假設(shè)的代表性就越低，就可能導(dǎo)致錯(cuò)誤的分類。就可能導(dǎo)致錯(cuò)誤的分類。n 通常，這種方法使用統(tǒng)計(jì)度量，剪去最不可靠的分通常，這種方法使用統(tǒng)計(jì)度量，剪去最不可靠的分枝，這將導(dǎo)致較快的分類，提高樹獨(dú)立于測試數(shù)據(jù)正確枝，這將導(dǎo)致較快的分類，提高樹獨(dú)立于測試數(shù)據(jù)正確分類的可靠性。主要包括先剪枝和后剪枝兩種策略。分類的可靠性。主要包括先剪枝和后剪枝兩種策略。 7.3 決策樹分類7.3.47.3.4決策樹修剪決策樹修剪n（1）先剪枝方法）先剪枝方法 也稱事前剪枝方法、停止生長策略。在先也稱事前剪枝方法、停止生長策略。在先剪枝方法中，通過提前停止樹的構(gòu)造（例如，剪枝方法中，通過

42、提前停止樹的構(gòu)造（例如，通過決定在給定的結(jié)點(diǎn)上不再分裂或劃分訓(xùn)練通過決定在給定的結(jié)點(diǎn)上不再分裂或劃分訓(xùn)練樣本的子集）而對樹樣本的子集）而對樹“剪枝剪枝”。一旦停止，結(jié)。一旦停止，結(jié)點(diǎn)成為樹葉。該樹葉可能持有子集樣本中最頻點(diǎn)成為樹葉。該樹葉可能持有子集樣本中最頻繁的類，或這些樣本的概率分布。繁的類，或這些樣本的概率分布。7.3 決策樹分類7.3.47.3.4決策樹修剪決策樹修剪 分裂閾值法是最為常用的一種停止生長方法。在構(gòu)分裂閾值法是最為常用的一種停止生長方法。在構(gòu)造樹時(shí)，統(tǒng)計(jì)意義下的度量，如造樹時(shí)，統(tǒng)計(jì)意義下的度量，如 2、信息增益等，可以、信息增益等，可以用于評估分裂的優(yōu)劣。如果在一個(gè)結(jié)點(diǎn)劃

43、分樣本將導(dǎo)致用于評估分裂的優(yōu)劣。如果在一個(gè)結(jié)點(diǎn)劃分樣本將導(dǎo)致低于預(yù)定義閾值的分裂，則給定子集的進(jìn)一步劃分將停低于預(yù)定義閾值的分裂，則給定子集的進(jìn)一步劃分將停止。然而，選取一個(gè)適當(dāng)?shù)拈撝凳抢щy的。較高的閾值止。然而，選取一個(gè)適當(dāng)?shù)拈撝凳抢щy的。較高的閾值可能導(dǎo)致過分簡化的樹，而較低的閾值可能使得樹的化可能導(dǎo)致過分簡化的樹，而較低的閾值可能使得樹的化簡太少。簡太少。7.3 決策樹分類7.3.47.3.4決策樹修剪決策樹修剪n（2） 后剪枝方法后剪枝方法 先剪枝方法的優(yōu)點(diǎn)是速度快，但很容易遺漏先剪枝方法的優(yōu)點(diǎn)是速度快，但很容易遺漏有價(jià)值的子樹。與此相反，后剪枝方法一定程度有價(jià)值的子樹。與此相反，后剪

44、枝方法一定程度上可彌補(bǔ)這一缺陷，后剪枝方法由上可彌補(bǔ)這一缺陷，后剪枝方法由“完全生長完全生長”的樹剪去分枝。通過刪除結(jié)點(diǎn)的分枝，剪掉樹結(jié)的樹剪去分枝。通過刪除結(jié)點(diǎn)的分枝，剪掉樹結(jié)點(diǎn)。點(diǎn)。 7.3 決策樹分類7.3.47.3.4決策樹修剪決策樹修剪n 基于代價(jià)成本的剪枝方法是一個(gè)常用的后剪枝方法?；诖鷥r(jià)成本的剪枝方法是一個(gè)常用的后剪枝方法。基本思路為：基本思路為：最下面的未被剪枝的結(jié)點(diǎn)成為樹葉，并用最下面的未被剪枝的結(jié)點(diǎn)成為樹葉，并用它先前分枝中最頻繁的類標(biāo)記。對于樹中每個(gè)非樹葉結(jié)它先前分枝中最頻繁的類標(biāo)記。對于樹中每個(gè)非樹葉結(jié)點(diǎn)，算法計(jì)算該結(jié)點(diǎn)上的子樹被剪枝可能出現(xiàn)的期望錯(cuò)點(diǎn)，算法計(jì)算該結(jié)點(diǎn)

45、上的子樹被剪枝可能出現(xiàn)的期望錯(cuò)誤率。然后，使用每個(gè)分枝的錯(cuò)誤率，結(jié)合沿每個(gè)分枝誤率。然后，使用每個(gè)分枝的錯(cuò)誤率，結(jié)合沿每個(gè)分枝觀察的權(quán)重（樣本分布）評估，計(jì)算不對該結(jié)點(diǎn)剪枝的觀察的權(quán)重（樣本分布）評估，計(jì)算不對該結(jié)點(diǎn)剪枝的期望錯(cuò)誤率。如果剪去該結(jié)點(diǎn)導(dǎo)致較高的期望錯(cuò)誤率，期望錯(cuò)誤率。如果剪去該結(jié)點(diǎn)導(dǎo)致較高的期望錯(cuò)誤率，則保留該子樹；否則剪去該子樹。逐漸產(chǎn)生一組被剪枝則保留該子樹；否則剪去該子樹。逐漸產(chǎn)生一組被剪枝的樹之后，使用一個(gè)獨(dú)立的測試集評估每棵樹的準(zhǔn)確率，的樹之后，使用一個(gè)獨(dú)立的測試集評估每棵樹的準(zhǔn)確率，就能得到具有最小期望錯(cuò)誤率的決策樹。就能得到具有最小期望錯(cuò)誤率的決策樹。 7.3 決策

46、樹分類7.3.47.3.4決策樹修剪決策樹修剪n 設(shè)一個(gè)葉結(jié)點(diǎn)覆蓋設(shè)一個(gè)葉結(jié)點(diǎn)覆蓋N個(gè)實(shí)例，其中個(gè)實(shí)例，其中E個(gè)為錯(cuò)誤的。對個(gè)為錯(cuò)誤的。對于具有信任度于具有信任度CF的實(shí)例，計(jì)算一個(gè)二項(xiàng)分布的實(shí)例，計(jì)算一個(gè)二項(xiàng)分布UCF(E,N)，即該實(shí)例的誤判概率，那么即該實(shí)例的誤判概率，那么N個(gè)實(shí)例判斷錯(cuò)誤的數(shù)目為個(gè)實(shí)例判斷錯(cuò)誤的數(shù)目為N UCF(E,N)。子樹的錯(cuò)誤數(shù)目為所有葉結(jié)點(diǎn)的總和。例。子樹的錯(cuò)誤數(shù)目為所有葉結(jié)點(diǎn)的總和。例如：如： 其中，其中，( )中為覆蓋的實(shí)例數(shù)目。中為覆蓋的實(shí)例數(shù)目。VnyuC1(6)C1(9)C3(1)7.3 決策樹分類7.3.47.3.4決策樹修剪決策樹修剪n 設(shè)設(shè)CF=

47、0.25，則該子樹的實(shí)例判斷錯(cuò)誤數(shù)目為：，則該子樹的實(shí)例判斷錯(cuò)誤數(shù)目為： 6 U0.25(0,6)+9 U0.25(0,9) +1 U0.25(0,1)=6 0.178+9 0.075+1 0.750= 2.494n 若以一個(gè)葉結(jié)點(diǎn)若以一個(gè)葉結(jié)點(diǎn)C1替代該子樹，則替代該子樹，則16個(gè)實(shí)例中有個(gè)實(shí)例中有一個(gè)錯(cuò)誤（一個(gè)錯(cuò)誤（C3），誤判實(shí)例數(shù)目為：），誤判實(shí)例數(shù)目為： 16 U0.25(1,16)=16 0.053=0.855n 由于誤判數(shù)目小于上述子樹，則以該葉結(jié)點(diǎn)代替由于誤判數(shù)目小于上述子樹，則以該葉結(jié)點(diǎn)代替子樹。子樹。7.3 決策樹分類7.3.47.3.4決策樹修剪決策樹修剪n 最小描述長度

48、剪枝方法也是較為常用的事后剪枝最小描述長度剪枝方法也是較為常用的事后剪枝方法，其基本思想是：最簡單的就是最好的。與基于方法，其基本思想是：最簡單的就是最好的。與基于代價(jià)成本方法相比，該方法無需額外的獨(dú)立測試數(shù)據(jù)代價(jià)成本方法相比，該方法無需額外的獨(dú)立測試數(shù)據(jù)集。集。 n 最小描述長度剪枝方法根據(jù)結(jié)點(diǎn)在剪枝前后樹的最小描述長度剪枝方法根據(jù)結(jié)點(diǎn)在剪枝前后樹的編碼長度決定是否執(zhí)行剪枝操作。編碼長度決定是否執(zhí)行剪枝操作。7.3 決策樹分類7.3.47.3.4決策樹修剪決策樹修剪n 由于決策樹的中間結(jié)點(diǎn)和葉結(jié)點(diǎn)的存儲(chǔ)信息不同，由于決策樹的中間結(jié)點(diǎn)和葉結(jié)點(diǎn)的存儲(chǔ)信息不同，編碼的代價(jià)也不同。葉結(jié)點(diǎn)的編碼代價(jià)包

49、括兩部分：樹編碼的代價(jià)也不同。葉結(jié)點(diǎn)的編碼代價(jià)包括兩部分：樹結(jié)構(gòu)本身的編碼代價(jià)結(jié)構(gòu)本身的編碼代價(jià)L(t)和例外樣本的編碼代價(jià)和例外樣本的編碼代價(jià)Errors。中間結(jié)點(diǎn)的編碼代價(jià)包括樹結(jié)構(gòu)本身的編碼代價(jià)中間結(jié)點(diǎn)的編碼代價(jià)包括樹結(jié)構(gòu)本身的編碼代價(jià)L(t)、分、分裂方法的編碼代價(jià)裂方法的編碼代價(jià)Ltest和子樹和子樹ti的編碼代價(jià)。因此，可以的編碼代價(jià)。因此，可以估計(jì)出剪枝前后的編碼代價(jià)：估計(jì)出剪枝前后的編碼代價(jià)： 剪枝前的編碼代價(jià)：剪枝前的編碼代價(jià)：Cboth(t)=L(t)+Ltest+C(ti) 剪枝后的編碼代價(jià)：剪枝后的編碼代價(jià)：Cleaf(t)=L(t)+Errors7.3 決策樹分類7.

50、3.47.3.4決策樹修剪決策樹修剪n 基于最小描述長度的剪枝算法的過程如下：從基于最小描述長度的剪枝算法的過程如下：從決策樹的底層開始，對每個(gè)中間結(jié)點(diǎn)決策樹的底層開始，對每個(gè)中間結(jié)點(diǎn)t計(jì)算節(jié)點(diǎn)當(dāng)前計(jì)算節(jié)點(diǎn)當(dāng)前的編碼代價(jià)的編碼代價(jià)Cboth(t)和剪枝后的編碼代價(jià)和剪枝后的編碼代價(jià)Cleaf(t)，如果如果Cleaf(t)Cboth(t)，就去掉子結(jié)點(diǎn)，將中間結(jié)點(diǎn)，就去掉子結(jié)點(diǎn)，將中間結(jié)點(diǎn)變?yōu)槿~結(jié)點(diǎn)，否則不做任何操作。重復(fù)這個(gè)步驟，變?yōu)槿~結(jié)點(diǎn)，否則不做任何操作。重復(fù)這個(gè)步驟，直至達(dá)到根結(jié)點(diǎn)為止。直至達(dá)到根結(jié)點(diǎn)為止。 n 也可以交叉使用先剪枝和后剪枝，形成組合式也可以交叉使用先剪枝和后剪枝，形成

51、組合式方法。后剪枝所需的計(jì)算比先剪枝多，但通常產(chǎn)生方法。后剪枝所需的計(jì)算比先剪枝多，但通常產(chǎn)生更可靠的樹。更可靠的樹。 7.3 決策樹分類7.3.47.3.4決策樹修剪決策樹修剪n 決策樹的構(gòu)造完成之后，下一步就要對決策樹決策樹的構(gòu)造完成之后，下一步就要對決策樹的準(zhǔn)確度進(jìn)行評估。通常選用一組與訓(xùn)練集的樣本的準(zhǔn)確度進(jìn)行評估。通常選用一組與訓(xùn)練集的樣本分布相同的新樣本作為測試集，對模型的測試就是分布相同的新樣本作為測試集，對模型的測試就是利用模型對測試樣本的類別進(jìn)行預(yù)測的過程，比較利用模型對測試樣本的類別進(jìn)行預(yù)測的過程，比較預(yù)測的類別和實(shí)際的類別是否一致，結(jié)果一致的樣預(yù)測的類別和實(shí)際的類別是否一致

52、，結(jié)果一致的樣本在測試集中所占的比例就是模型的準(zhǔn)確度。本在測試集中所占的比例就是模型的準(zhǔn)確度。n 當(dāng)沒有獨(dú)立的測試集時(shí)，通常采用保留法當(dāng)沒有獨(dú)立的測試集時(shí)，通常采用保留法（holdout）或交叉法（）或交叉法（cross validation）生成訓(xùn)）生成訓(xùn)練集和測試集。練集和測試集。 7.3 決策樹分類7.3.57.3.5決策樹的測試決策樹的測試n 保留測試法把整個(gè)數(shù)據(jù)集劃分為兩個(gè)不相交的保留測試法把整個(gè)數(shù)據(jù)集劃分為兩個(gè)不相交的子集，通常訓(xùn)練集占子集，通常訓(xùn)練集占2/3，測試集占，測試集占1/3。然后利用。然后利用訓(xùn)練集構(gòu)造決策樹，利用測試集評價(jià)決策樹。這種訓(xùn)練集構(gòu)造決策樹，利用測試集評價(jià)決

53、策樹。這種測試方法速度快，但沒有充分利用所有的數(shù)據(jù)來進(jìn)測試方法速度快，但沒有充分利用所有的數(shù)據(jù)來進(jìn)行學(xué)習(xí)，當(dāng)樣本數(shù)量比較少時(shí)，容易造成過學(xué)習(xí)。行學(xué)習(xí)，當(dāng)樣本數(shù)量比較少時(shí)，容易造成過學(xué)習(xí)。 7.3 決策樹分類7.3.57.3.5決策樹的測試決策樹的測試數(shù)據(jù)數(shù)據(jù)訓(xùn)練集訓(xùn)練集測試集測試集保留測試法保留測試法n 交叉驗(yàn)證法則將整個(gè)數(shù)據(jù)集分成交叉驗(yàn)證法則將整個(gè)數(shù)據(jù)集分成k個(gè)大致規(guī)模相個(gè)大致規(guī)模相等的不相交子集。模型共進(jìn)行等的不相交子集。模型共進(jìn)行k次訓(xùn)練和測試，每次次訓(xùn)練和測試，每次取其中的取其中的k-1個(gè)子集作為訓(xùn)練集，第個(gè)子集作為訓(xùn)練集，第k個(gè)子集作為測個(gè)子集作為測試集，計(jì)算模型的準(zhǔn)確度。最后，把試

54、集，計(jì)算模型的準(zhǔn)確度。最后，把k次測試的準(zhǔn)確次測試的準(zhǔn)確度的平均值作為最終的準(zhǔn)確度。為了改善對準(zhǔn)確度度的平均值作為最終的準(zhǔn)確度。為了改善對準(zhǔn)確度的評估，交叉測試法可以重復(fù)多次，如果采用的評估，交叉測試法可以重復(fù)多次，如果采用t次次k交叉測試法，那么模型構(gòu)造和測試的次數(shù)共有交叉測試法，那么模型構(gòu)造和測試的次數(shù)共有k t次，次，雖然提高了測試的可信度，但運(yùn)行時(shí)間是保留測試雖然提高了測試的可信度，但運(yùn)行時(shí)間是保留測試法的法的k t倍。倍。 7.3 決策樹分類7.3.57.3.5決策樹的測試決策樹的測試n 兩種測試方法各有各的適用情況，通常保留測兩種測試方法各有各的適用情況，通常保留測試法用于最初試驗(yàn)

55、性的場合，或者多于試法用于最初試驗(yàn)性的場合，或者多于5000條樣本條樣本的數(shù)據(jù)集，而交叉測試法用于建立最終的分類器，的數(shù)據(jù)集，而交叉測試法用于建立最終的分類器，或者相對較小規(guī)模的數(shù)據(jù)集?；蛘呦鄬^小規(guī)模的數(shù)據(jù)集。 7.3 決策樹分類7.3.57.3.5決策樹的測試決策樹的測試數(shù)據(jù)數(shù)據(jù)S1Sk-1SkSi(1), Si(k-1)Si(k)訓(xùn)練集訓(xùn)練集測試集測試集交叉測試法交叉測試法7.4 貝葉斯分類n 貝葉斯分類是統(tǒng)計(jì)學(xué)分類方法，可以預(yù)測貝葉斯分類是統(tǒng)計(jì)學(xué)分類方法，可以預(yù)測類成員關(guān)系的可能性，如給定樣本屬于一個(gè)特類成員關(guān)系的可能性，如給定樣本屬于一個(gè)特定類的概率。定類的概率。n 貝葉斯分類基于貝

56、葉斯定理。分類算法的貝葉斯分類基于貝葉斯定理。分類算法的比較研究發(fā)現(xiàn)，一種稱作樸素貝葉斯分類的簡比較研究發(fā)現(xiàn)，一種稱作樸素貝葉斯分類的簡單貝葉斯分類算法可以與決策樹和神經(jīng)網(wǎng)絡(luò)分單貝葉斯分類算法可以與決策樹和神經(jīng)網(wǎng)絡(luò)分類算法相媲美。用于大型數(shù)據(jù)庫，貝葉斯分類類算法相媲美。用于大型數(shù)據(jù)庫，貝葉斯分類也已表現(xiàn)出高準(zhǔn)確率與高速度。也已表現(xiàn)出高準(zhǔn)確率與高速度。7.4 貝葉斯分類7.4.17.4.1貝葉斯定理貝葉斯定理n 設(shè)設(shè)X是類標(biāo)號未知的數(shù)據(jù)樣本。設(shè)是類標(biāo)號未知的數(shù)據(jù)樣本。設(shè)H為某種假定，為某種假定，如，數(shù)據(jù)樣本如，數(shù)據(jù)樣本X屬于某特定的類屬于某特定的類C。對于分類問題，希。對于分類問題，希望確定望確

57、定P(H|X)給定觀測數(shù)據(jù)樣本給定觀測數(shù)據(jù)樣本X，假定，假定H成立的成立的概率。概率。n P(H|X)是后驗(yàn)概率，或條件是后驗(yàn)概率，或條件X下，下，H的后驗(yàn)概率。的后驗(yàn)概率。例如，假定數(shù)據(jù)樣本世界由水果組成，用它們的顏色例如，假定數(shù)據(jù)樣本世界由水果組成，用它們的顏色和形狀描述。假定和形狀描述。假定X表示紅色和圓的，表示紅色和圓的，H表示假定表示假定X是是蘋果，則蘋果，則P(H|X)反映當(dāng)看到反映當(dāng)看到X是紅色并是圓的時(shí)，我們是紅色并是圓的時(shí)，我們對對X是蘋果的確信程度。是蘋果的確信程度。7.4 貝葉斯分類7.4.17.4.1貝葉斯定理貝葉斯定理n P(H)是先驗(yàn)概率。對于上述例子，它是任意給定

58、的是先驗(yàn)概率。對于上述例子，它是任意給定的數(shù)據(jù)樣本為蘋果的概率。后驗(yàn)概率數(shù)據(jù)樣本為蘋果的概率。后驗(yàn)概率P(H|X)比先驗(yàn)概率比先驗(yàn)概率P(H)基于更多的信息（如，背景知識）?；诟嗟男畔ⅲㄈ?，背景知識）。n 類似地，類似地，P(X|H)是條件是條件H下，下，X的后驗(yàn)概率。即，的后驗(yàn)概率。即，它是已知它是已知X是蘋果，是蘋果，X是紅色并且是圓的的概率。是紅色并且是圓的的概率。P(X)是是X的先驗(yàn)概率，它是由水果集取出一個(gè)數(shù)據(jù)樣本是紅的先驗(yàn)概率，它是由水果集取出一個(gè)數(shù)據(jù)樣本是紅的和圓的的概率。的和圓的的概率。n 貝葉斯定理提供了一種由貝葉斯定理提供了一種由P(X)，P(H)和和P(X|H)計(jì)算后

59、驗(yàn)概率計(jì)算后驗(yàn)概率P(H|X)的方法。的方法。7.4 貝葉斯分類7.4.17.4.1貝葉斯定理貝葉斯定理7.4 貝葉斯分類7.4.27.4.2樸素貝葉斯分類樸素貝葉斯分類n 樸素貝葉斯分類原理如下：樸素貝葉斯分類原理如下： 已知：每個(gè)數(shù)據(jù)樣本每個(gè)數(shù)據(jù)樣本用一個(gè)已知：每個(gè)數(shù)據(jù)樣本每個(gè)數(shù)據(jù)樣本用一個(gè)n維特征向量維特征向量X= x1，x2，xn表示，分別描述對表示，分別描述對n個(gè)屬性個(gè)屬性A1，A2，An樣本的樣本的n個(gè)度量。假定有個(gè)度量。假定有m個(gè)類個(gè)類C1,C2,.,Cm。 要求：給定一個(gè)未知的數(shù)據(jù)樣本要求：給定一個(gè)未知的數(shù)據(jù)樣本X（即，沒有類標(biāo)（即，沒有類標(biāo)號），用貝葉斯分類法預(yù)測號），用貝葉

60、斯分類法預(yù)測X屬于具有最高后驗(yàn)概率屬于具有最高后驗(yàn)概率（條件（條件X下）的類。下）的類。7.4 貝葉斯分類7.4.27.4.2樸素貝葉斯分類樸素貝葉斯分類 樸素貝葉斯分類將未知的樣本分配給類樸素貝葉斯分類將未知的樣本分配給類Ci，當(dāng)且僅當(dāng)：，當(dāng)且僅當(dāng)： 問題轉(zhuǎn)換為：最大化問題轉(zhuǎn)換為：最大化P(Ci|X)，其，其P(Ci|X)最大的類最大的類Ci稱為最大后驗(yàn)假定。稱為最大后驗(yàn)假定。 根據(jù)貝葉斯定理：根據(jù)貝葉斯定理： 由于由于P(X)對于所有類為常數(shù)，只需要對于所有類為常數(shù)，只需要P(X|Ci)P(Ci)最最大即可。其中，類的先驗(yàn)概率可以用大即可。其中，類的先驗(yàn)概率可以用P(Ci)=si/s計(jì)算。