ID3的基本思想和算法分析

1、第1章決策樹方法在數(shù)據(jù)倉庫和數(shù)據(jù)挖掘的應用中，分類是一種非常重要的方法分類的概念是在已有數(shù)據(jù)的基礎上學會一個分類函數(shù)或構(gòu)造出一個分類模型（即我們通常所說的分類器(Classifier）該函數(shù)或模型能夠把數(shù)據(jù)庫中的數(shù)據(jù)紀錄映射到給定類別中的某一個，從而可以應用于數(shù)據(jù)預測分類的主要算法有：貝葉斯算法、決策樹算法（如ID3、C4.5等）、規(guī)則推導、人工神經(jīng)網(wǎng)絡、最近鄰算法、支持向量機等等這些算法在許多現(xiàn)實數(shù)據(jù)集合上可以做比較精確的數(shù)據(jù)預測，為人們的生活、生產(chǎn)、學習、研究提供了有效的途徑其中決策樹算法具有良好的可解釋性，在實踐中的應用最為廣泛決策樹分類算法的一個典型代表就是ID3算法1.1 概述1.1

2、.1 學習的相關(guān)概念分類是在一個作為輸入的訓練集合上學會一個分類函數(shù)或構(gòu)造出一個分類模型，即我們通常所說的分類器(Classifier)，然后利用它對數(shù)據(jù)集合中沒有類標的實例指派最適合的類標。分類是在一個作為輸入的訓練集合上學會一個分類函數(shù)或構(gòu)造出一個分類模型，即我們通常所說的分類器(Classifier)，然后利用它對數(shù)據(jù)集合中沒有類標的實例指派最適合的類標分類用于預測數(shù)據(jù)對象的類別如可以構(gòu)造一個分類模型來對銀行貸款進行風險評估（安全或危險）機器學習、專家系統(tǒng)、統(tǒng)計學和神經(jīng)生物學等領(lǐng)域的研究人員已經(jīng)提出了許多具體的分類方法，如貝葉斯方法、決策樹、規(guī)則推導、人工神經(jīng)網(wǎng)絡、支持向量機、基于實例的

3、方法等訓練集合是由一組數(shù)據(jù)實例構(gòu)成，每個實例是一個由有關(guān)字段組成的特征向量，這些字段被稱為屬性（Attribute），用于分類的屬性被叫做類標，類標屬性也就是訓練集合的類別標記一個具體的實例形式可以表示為(a1, a2, , an, c), 其中ai (i=1, 2, , n) 表示屬性字段值，c 表示類標給定訓練數(shù)據(jù)集合D=x1, x2 , , xn, 分類任務的目標是對數(shù)據(jù)集合D進行分析，確定一個映射函數(shù)f: (A1, A2, , An)C ，使得對任意的未知類別的實例xi=(a1, a2 , , an)可標以適當?shù)念悩?訓練集合是構(gòu)造分類器的基礎訓練集合是包含一些屬性的一個數(shù)據(jù)庫表格，其

4、中的一個屬性被制定為分類標簽標簽屬性的類型一般要求是離散的，且標簽屬性的可能值的數(shù)目越少越好（最好是兩或三個值）標簽值的數(shù)目越少，構(gòu)造出來的分類器的錯誤率越低訓練集合是由一組數(shù)據(jù)實例構(gòu)成，每個實例是一個由有關(guān)字段組成的特征向量，這些字段被稱為屬性（Attribute），用于分類的屬性被叫做類標，類標屬性也就是訓練集合的類別標記。一個具體的實例形式可以表示為(a1, a2, , an, c), 其中ai (i=1, 2, , n) 表示屬性字段值，c 表示類標。給定訓練數(shù)據(jù)集合D=x1, x2 , , xn，分類任務的目標是對數(shù)據(jù)集合D進行分析，確定一個映射函數(shù)f: (A1, A2, , An)

5、C ，使得對任意的未知類別的實例xi=(a1, a2 , , an)可標以適當?shù)念悩?。監(jiān)督學習和非監(jiān)督學習的區(qū)別機器學習方法分為有監(jiān)督的學習和無監(jiān)督的學習有監(jiān)督的學習需要給出不同類別的實例作為訓練實例，由這些訓練實例得到類的描述，然后給新的測試實例匹配類標無監(jiān)督的學習是在給定實例集合上，根據(jù)其內(nèi)容，在無先驗知識的條件下，將實例分成有意義的類其中有監(jiān)督的學習從學習過程的任務實施方式上可以分成兩種極端的情況，即急切式學習策略和懶惰式學習策略急切式學習策略在分類器訓練階段就建立將待分類實例映射到其預測類標上的一個有清晰假設的分類器學習的過程是在訓練數(shù)據(jù)集合上建立分類器的過程，它同分類過程是相分離的

6、一般的決策樹算法就是典型的代表而懶惰式學習算法沒有建立清晰的假設，分類過程就是利用訓練集合將給定實例與其類標匹配起來的過程，學習過程和學習結(jié)果的應用過程是同時進行的采用急切式學習策略的分類器，即對于給定的訓練實例集合，在訓練階段就建立好一個分類器，在分類階段直接地使用該分類器來給一個待分類實例分類Fridman等的TAN分類器就是一種采用急切式學習策略的分類器采用懶惰式學習策略的分類器，在訓練階段不建立一個清晰的假設，而在分類階段使用訓練集合來將給定實例與其類標匹配起來，即在分類時利用訓練集合和測試實例建立分類規(guī)則為該測試實例來分類LBR分類器就是采用了一種完全懶惰的學習方法；基于實例的分類也

7、采用了懶惰式學習策略一般來講，對于同一種模型技術(shù)，急切式學習策略在效率上大大優(yōu)于懶惰式學習策略，而懶惰式學習策略在分類精確度上優(yōu)于急切式學習策略為了使分類器在能夠在效率和分類精確度上都達到令人滿意的水平，可以對上述兩種學習策略進行研究，對同一種分類模型找到一個采用急切式學習策略和懶惰式學習策略的平衡點這是分類器研究的一個突破點，也是本文的研究點之一分類的概念分類是在一個作為輸入的訓練集合上學會一個分類函數(shù)或構(gòu)造出一個分類模型，即我們通常所說的分類器(Classifier)，然后利用它對數(shù)據(jù)集合中沒有類標的實例指派最適合的類標訓練集合是由一組數(shù)據(jù)實例構(gòu)成，每個實例是一個由有關(guān)字段組成的特征向量，

8、這些字段被稱為屬性（Attribute），用于分類的屬性被叫做類標，類標屬性也就是訓練集合的類別標記一個具體的實例形式可以表示為(a1, a2, , an, c), 其中ai (i=1, 2, , n) 表示屬性字段值，c 表示類標給定訓練數(shù)據(jù)集合D=x1, x2 , , xn，分類任務的目標是對數(shù)據(jù)集合D進行分析，確定一個映射函數(shù)f: (A1, A2, , An)C ，使得對任意的未知類別的實例xi=(a1, a2 , , an)可標以適當?shù)念悩?18訓練集合是構(gòu)造分類器的基礎訓練集合是包含一些屬性的一個數(shù)據(jù)庫表格，其中的一個屬性被制定為分類標簽標簽屬性的類型一般要求是離散的，且標簽屬性的可

9、能值的數(shù)目越少越好（最好是兩或三個值）標簽值的數(shù)目越少，構(gòu)造出來的分類器的錯誤率越低分類用于預測數(shù)據(jù)對象的類別如可以構(gòu)造一個分類模型來對銀行貸款進行風險評估（安全或危險）機器學習、專家系統(tǒng)、統(tǒng)計學和神經(jīng)生物學等領(lǐng)域的研究人員已經(jīng)提出了許多具體的分類方法，如貝葉斯方法、決策樹、規(guī)則推導、人工神經(jīng)網(wǎng)絡、支持向量機、基于實例的方法等1.1.2 監(jiān)督學習機器學習方法分為有監(jiān)督的學習和無監(jiān)督的學習有監(jiān)督的學習需要給出不同類別的實例作為訓練實例，由這些訓練實例得到類的描述，然后給新的測試實例匹配類標無監(jiān)督的學習是在給定實例集合上，根據(jù)其內(nèi)容，在無先驗知識的條件下，將實例分成有意義的類其中有監(jiān)督的學習從學習

10、過程的任務實施方式上可以分成兩種極端的情況，即急切式學習策略和懶惰式學習策略急切式學習策略在分類器訓練階段就建立將待分類實例映射到其預測類標上的一個有清晰假設的分類器學習的過程是在訓練數(shù)據(jù)集合上建立分類器的過程，它同分類過程是相分離的一般的決策樹算法就是典型的代表而懶惰式學習算法沒有建立清晰的假設，分類過程就是利用訓練集合將給定實例與其類標匹配起來的過程，學習過程和學習結(jié)果的應用過程是同時進行的采用急切式學習策略的分類器，即對于給定的訓練實例集合，在訓練階段就建立好一個分類器，在分類階段直接地使用該分類器來給一個待分類實例分類Fridman等的TAN分類器就是一種采用急切式學習策略的分類器采用

11、懶惰式學習策略的分類器，在訓練階段不建立一個清晰的假設，而在分類階段使用訓練集合來將給定實例與其類標匹配起來，即在分類時利用訓練集合和測試實例建立分類規(guī)則為該測試實例來分類LBR分類器就是采用了一種完全懶惰的學習方法；基于實例的分類也采用了懶惰式學習策略一般來講，對于同一種模型技術(shù)，急切式學習策略在效率上大大優(yōu)于懶惰式學習策略，而懶惰式學習策略在分類精確度上優(yōu)于急切式學習策略為了使分類器在能夠在效率和分類精確度上都達到令人滿意的水平，可以對上述兩種學習策略進行研究，對同一種分類模型找到一個采用急切式學習策略和懶惰式學習策略的平衡點這是分類器研究的一個突破點，也是本文的研究點之一應用變量類型和術(shù)

12、語的相關(guān)規(guī)定得到學習問題規(guī)范的數(shù)學表達-統(tǒng)計學習基礎第二章1.1.3 學習問題實例介紹可在以后發(fā)現(xiàn)實際應用例子時再寫這部分。股票數(shù)據(jù)分析、臨床數(shù)據(jù)診斷應用、垃圾郵件的判別-相關(guān)論文在金融方面，銀行和金融機構(gòu)往往持有大量的關(guān)于客戶的，各種服務的以及交易事務的數(shù)據(jù)，并且這些數(shù)據(jù)通常比較完整，可靠和高質(zhì)量，這大大方便了系統(tǒng)化的數(shù)據(jù)分析和數(shù)據(jù)挖掘在銀行中，數(shù)據(jù)挖掘被用來建模，預測，識別偽造信用卡，估計風險，進行趨勢分析，效益分析，顧客分析等在此領(lǐng)域運用數(shù)據(jù)挖掘，可以進行貸款償付預測和客戶信用政策分析，以調(diào)整貸款發(fā)放政策，降低經(jīng)營風險信用卡公司可以應用數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則來識別欺詐比如銀行想知道顧客源在

13、什么樣的優(yōu)惠后可以來開新賬戶，什么條件下顧客可能會注銷已有的賬戶例如，我們想預測信用卡欺詐行為，可以通過計算機算法分析信用卡用戶的購買習慣，從而認識客戶的模式，并分辨出偏離模式的信用卡盜用行為使用上面的模型和方法，該學習的過程首先需要有一個訓練階段，提供正反兩面方面的偏離例子用挖掘程序來訓練訓練之后，算法應能推導出合法交易的定義，并能預測一個新的交易是合法的還是非法的智能數(shù)據(jù)挖掘利用了廣泛的高質(zhì)量的機器學習算法，它能夠在應付大量數(shù)據(jù)的同時，又保證理想的響應時間，使得市場分析，風險預測，欺詐管理，客戶關(guān)系管理和競爭優(yōu)勢分析等應用成為可以在醫(yī)療領(lǐng)域中，成堆的電子數(shù)據(jù)可能已放在那兒很多年了，比如病人

14、，癥狀，發(fā)病時間，發(fā)病頻率以及當時的用藥種類，劑量，住院時間等在藥物實驗中，可能有很多種不同的組合，每種若加以實驗，則成本太大，決策樹方法可以被用來大減少實驗次數(shù)這種方法已被許多大的制藥公司所采用生物醫(yī)學的大量研究大都集中在DNA數(shù)據(jù)的分析上人類大約有105個基因，幾乎是不計其數(shù)因此，數(shù)據(jù)挖掘成為DNA分析中的強力工具，如：對DNA序列間的相似搜索和比較；應用關(guān)聯(lián)分析對同時出現(xiàn)的基因序列的識別；應用路徑分析發(fā)現(xiàn)在疾病不同階段的致病基因等電信業(yè)已經(jīng)迅速從單純的提供市話和長途服務變?yōu)榫C合電信服務，如語音，傳真，移動電話，電子郵件，互聯(lián)網(wǎng)接入服務電信市場的競爭也變得越來越激烈和全方位化利用數(shù)據(jù)挖掘來

15、幫助理解商業(yè)行為，對電信數(shù)據(jù)的多維分析，檢測非典型的使用模式以尋找潛在的盜用者，分析用戶一系列的電信服務使用模式來改進服務，根據(jù)地域分布疏密性找出最急需建立網(wǎng)點的位置，確定電信模式，捕捉盜用待業(yè)，更好的利用資源和提高服務質(zhì)量是非常必要的借助數(shù)據(jù)挖掘，可以減少很多損失，保住顧客1.2 信息論基礎主要把所涉及的信息論進行較系統(tǒng)介紹，注意要舉例說明。為了尋找對樣本進行分類的最優(yōu)方法，我們要做的工作就是使對一個樣本分類時需要問的問題最少（即樹的深度最?。┮虼?，我們需要某種函數(shù)據(jù)來衡量哪些問題將提供最為平衡的劃分，信息增益就是這樣的函數(shù)之一1.2.1信息和熵的概念那么信息熵的定義為：設是訓練樣本集，它包

16、含n 個類別的樣本，這些類別分別用C1, C2, ,Cn, 表示，若給定的概率分布Pi=（P1, P2, Pn ）表示Ci的概率，則由該分布傳遞的信息量稱為P的信息熵，記為：屬性A相對實例集合S的信息增益gain(S,A)定義為：1.2.2 信息增益的概念與其他度量方式信息增益用來衡量熵的期望減少值，因此使用屬性A相對實例集合S進行的劃分獲得的信息增益gain(S, A)定義為：gain(S, A)是指因為知道屬性A的值后導致的熵的期望壓縮gain(S, A)越大，說明選擇測試屬性A對分類提供的信息越多因為熵越小代表節(jié)點越純，按照信息增益的定義，信息增益越大，熵的減小量也越大，節(jié)點就趨向于更純

17、因此，可以對每個屬性按照它們的信息增益大小排序，獲得最大信息增益的屬性被選擇為分支屬性1.2.3 雜度函數(shù)及相關(guān)概念數(shù)據(jù)挖掘原理與算法、信息論相關(guān)書籍！1.3 決策樹算法1.3.1 決策樹基本算法概述決策樹算法是一種常用的數(shù)據(jù)挖掘算法，它是從機器學習領(lǐng)域中逐漸發(fā)展起來的一種分類函數(shù)逼近方法決策樹學習的基本算法是貪心算法，采用自頂向下的遞歸方式構(gòu)造決策樹目前利用決策樹進行數(shù)據(jù)分類的方法已經(jīng)被深入地研究，并且形成了許多決策樹算法決策樹算法的分類模型是一棵有向無環(huán)樹，除了根節(jié)點以外，決策樹的每個節(jié)點有且僅有一個父節(jié)點每個葉節(jié)點對應一個類標號，它的值就是使用決策樹對未知樣本分類的類標號的值每個內(nèi)部節(jié)點

18、都對應一個分支方案，它包括用于節(jié)點分裂的屬性和分支的判斷規(guī)則q訓練樣本的屬性分為數(shù)值屬性和分類屬性，數(shù)值屬性的取值范圍是一個連續(xù)的區(qū)間，比如實數(shù)集；而分類屬性的取值范圍則是離散值的集合，比如屬性性別的取值范圍就是集合男，女如果屬性是數(shù)值屬性，那么q的形式是S是的取值范圍（）的子集在數(shù)學上可以對決策樹分類器作如下表述：給定樣本集，其中的樣本屬性c個類別，用i表示中屬于第i類的樣本集定義一個指標集1, 2數(shù)學公式之中數(shù)字與標點符號要使用英文“半角”標點符號（隨后加空格）。, , c和一個的非空子集的集合1, 2, b我們可以令當ii時，ii一個廣義決策規(guī)則f就是到的一個映射（記為f：）若f把第i類

19、的某個樣本映射到包含i的那個子集Ik中，則識別正確設Q（, ）是由樣本集和指標集所形成的所有可能的映射的集合，則Q（, ）可表示為由（ai, i）所組成的集合，元素（ai, i）稱為一個節(jié)點，ai是該節(jié)點上表征這種映射的參數(shù)，ii1, i2, 是該節(jié)點上指標集i的非空子集的集合令ni和nj是T（, ）的兩個元素，其中、若則稱ni為nj的父節(jié)點，或稱nj為ni的子節(jié)點設Q（, ，）是節(jié)點的有限集，且nB中沒有一個元素是n的父節(jié)點，則稱n是的根節(jié)點當Q（, ，）滿足下列條件時，它就是一個決策樹分類器(1)中有一個并且只有一個根節(jié)點(2)設ni和nj是中的兩個不同元素，則(3)對于每一個iI，中存在

20、一個節(jié)點且中有一個元素是i（與它對應的n的子節(jié)點叫葉節(jié)點，又稱終止節(jié)點）1.3.2 決策樹生成算法概述通用的自頂向下構(gòu)建決策樹的算法決策樹的深度優(yōu)先構(gòu)建算法輸入：節(jié)點，訓練數(shù)據(jù)集，分支指標輸出：以節(jié)點為根節(jié)點的基于數(shù)據(jù)集，分支指標的決策樹Procedure make_tree(N, D, SI) 初始化根節(jié)點在中計算，求解節(jié)點的分支方案；If(節(jié)點滿足分支條件)選擇最好的分支方案將分為1，2；創(chuàng)建的子節(jié)點1，2；make_tree(N1, D1, SI)make_tree(N, D, SI)endifend1.3.3 決策樹修剪算法介紹在樹的構(gòu)建階級生成的決策樹依賴于訓練樣本，因此它可能存在對

21、訓練樣本的過度適應問題例如，訓練樣本中的噪聲數(shù)據(jù)和統(tǒng)計波動可能會使決策樹產(chǎn)生不必要的分支，從而導致在使用決策樹模型對觀察樣本實施分類時出錯為了避免這種錯誤，需要對決策樹進行修剪，除去不必要的分支給定一個假設空間H，假設hH，如果存在假設hH，在訓練樣本集上h的分類錯誤率比h小，但在整個樣本空間上h的分類錯誤率比h小，則稱假設h過度適應訓練樣本集剪枝用于解決過度適應的問題剪枝的原則包括：（）奧卡姆剃刀原則如無必要，勿增實體即在與觀察相容的情況下，就當選擇最簡單的一個；（）決策樹越小就越容易理解，其存儲與傳輸?shù)拇鷥r也就越??；（）決策樹越復雜，節(jié)點越多，每個節(jié)點包含的訓練樣本個數(shù)越少，則支持每個節(jié)點

22、的假設的樣本個數(shù)就越少，可能導致決策樹在測試集上的分類錯誤率越大但決策樹過小也會導致錯誤率較大，因此，需要在樹的大小與正確之間尋找均衡點常用的剪枝技術(shù)有預剪枝（pre-pruning）和后剪枝（post-pruning）兩種預剪枝技術(shù)限制決策樹的過度生長（如CHAID ID3家族的ID3 C4.5算法等），后剪枝技術(shù)則是待決策樹生成后再進行剪枝（如CART算法等）預剪枝：最直接的預剪枝方法是事先限定決策樹的最大生長高度，使決策樹不能過度生長這種停止標準一般能夠取得比較好的效果不過指定樹高度的方法要求用戶對數(shù)據(jù)的取值分布有較為清晰的把握，而且需對參數(shù)值進行反復嘗試，否則無法給出一個較為合理的樹高

23、度閾值更普遍的作法是采用統(tǒng)計意義下的2檢驗，信息增益等度量，評價每次節(jié)點分裂對系統(tǒng)性能的增益如果節(jié)點分裂的增益值小于預先給定的閾值，則不對該節(jié)點進行擴展如果在最好的擴展增益都小于閾值，即使有些節(jié)點的樣本不屬于同一類，算法也可以終止選取閾值是困難的，閾值較高可能導致決策樹過于簡化，而閾值較低可能對決策樹的化簡不夠充分預剪枝存在的視野效果的問題在相同的標準下，當前的擴展不滿足標準，但進一步的擴展有可能滿足標準采用預剪枝的算法有可能過早地停止決策樹的構(gòu)造，但由于不必生成完整的決策樹，算法的效率很高，適合應用于大規(guī)模問題后剪枝：后剪枝技術(shù)允許決策樹過度生長，然后根據(jù)一定的規(guī)則，剪去決策樹中那些不具有一

24、般代表性的葉節(jié)點或分支后剪枝算法有自上而下的和自下而上的兩種剪枝策略自下而上的算法首先從最底層的內(nèi)節(jié)點開始剪枝，剪去滿足一定條件的內(nèi)節(jié)點，在生成的新決策上遞歸調(diào)用這個算法，直到?jīng)]有要可以剪枝的節(jié)點為止自上而下的算法是從根節(jié)點開始向下逐個考慮節(jié)點的剪枝問題，只要節(jié)點滿足剪枝的條件就進行剪枝決策樹修剪的基本算法：Prune_tee（節(jié)點）If（節(jié)點為葉節(jié)點）返回C(t)+1minCost1=prune_tree(N1)minCost2=prune_tree(N2)minCostN=minC(t)+1， Csplit(N)+1+minCost1+minCost2；if(minCostN= =C(t)

25、+1)將的子節(jié)點和從決策樹中修剪掉；返回minCostN在算法中，t為屬于節(jié)點的所有訓練樣本，C(t)和Csplit(N)分別為將作為葉節(jié)點和內(nèi)部節(jié)點本構(gòu)建決策樹的代價，算法的基本思想就是要使構(gòu)建決策樹的總代價最小計算C(t)的公式為其中，n 為t 中樣本的個數(shù)，k 為t 中樣本的類別數(shù)，ni為t 中屬于類i 的樣本數(shù)計算Csplit(N)要分為兩種情況：（）當節(jié)點的分支屬性為連續(xù)屬性時，Csplit(N)log2a+log2(v-1)（）當節(jié)點的分支屬性為離散屬性時，Csplit(N)log2a+log2(2 v-2)其中，a 為決策樹中用于節(jié)點分裂的屬性的個數(shù)，v是分支屬性可能取值的個數(shù)目

26、前，決策樹修剪策略主要有三種：代價復雜度修剪（cost-complexity pruning），悲觀修剪（pressimistic pruning）和基于最小描述長度（minimum description length, MDL）原理的修剪悲觀修剪是非曲直uinlan在1987年提出的，該方法將所有的樣本用于樹的構(gòu)建和修剪，但是這種方法產(chǎn)生的樹太大，并且有時候精度不高代價復雜修剪使用了獨立的樣本用于修剪，這種策略適用于訓練樣本比較多的情況在訓練樣本數(shù)目較少的情況下，需要將所有的樣本既用于樹的構(gòu)建，又用于樹的修剪，基于MDL原理的修剪是使用較多并且效果較好的方法基于MDL原理的決策樹算法有兩個

27、部分：一是決定數(shù)據(jù)編碼代價和模型編碼代價的編碼模式，包括數(shù)據(jù)編碼和模型編碼；二是比較各個子樹，確定是否剪枝的算法MDL修剪過程是一個自底向上的遞歸過程修剪算法：Pruning_the_tree(t) If t is a leaf node then Return cleaf=1; /cleaf is the cost of a leaf node Else Let cleaf be errors plus 1; /see option(1) If the split attribute is a numeric attribute Ltest=1 Else Count the number o

28、f such tests used in the tree (say n); Ltest=log2(n); Cboth=1+ltest+pruning_the_tree(t.leftchild)+pruning_the_tree(t.rightchild); If cleaf<cboth Prune cboth children of ts, and convert t into a leaf; Return cleaf; Else Return cboth1.4 決策樹ID3每個大節(jié)與小節(jié)之間要有一段文字說明本大節(jié)打算講述的內(nèi)容（與寫作安排或意義）等。1.4.1 ID3的基本概念和相關(guān)

29、信息論定義在數(shù)據(jù)倉庫和數(shù)據(jù)挖掘的應用中，分類是一種非常重要的方法分類的概念是在已有數(shù)據(jù)的基礎上學會一個分類函數(shù)或構(gòu)造出一個分類模型，即我們通常所說的分類器(Classifier）該函數(shù)或模型能夠把數(shù)據(jù)庫中的數(shù)據(jù)紀錄映射到給定類別中的某一個，從而可以應用于數(shù)據(jù)預測分類的主要算法有：貝葉斯算法、決策樹算法（如ID3、C4.5等）、規(guī)則推導、人工神經(jīng)網(wǎng)絡、最近鄰算法、支持向量機等等這些算法在許多現(xiàn)實數(shù)據(jù)集合上可以做比較精確的數(shù)據(jù)預測，為人們的生活、生產(chǎn)、學習、研究提供了有效的途徑其中決策樹算法具有良好的可解釋性，在實踐中的應用最為廣泛決策樹分類算法的一個典型代表就是ID3算法ID3算法是基于信息論（

30、Information Theory）的方法給定一個記錄的集合，每個記錄都有相同的結(jié)構(gòu)，并且每個記錄是由若干個成對的屬性值組成的這些屬性代表記錄所屬的類別ID3需要解決的問題是構(gòu)造一個決策樹，從而可以由非類別的屬性值正確地預測出類別屬性的值ID3算法可以分為兩個階段，一是建立決策樹階段，一是利用決策樹給實例分類的階段在ID3算法建立決策樹的過程中，可以遞歸地進行：首先，選擇一個屬性作為根節(jié)點，并為每一個可能的屬性值生成一個分支這樣，把實例集合劃分成多個子集合，該屬性的每一個值劃分為一個子集合現(xiàn)在對每一個分支重復以上的過程，過程中使用的實例集合是屬于該分支的實例如果在一個節(jié)點的所有實例屬于相同的

31、類，則停止擴展那一部分子樹這樣ID3的所建立的決策樹中每一個非葉子節(jié)點對應著一個非類別屬性，與屬性中具有最大信息量的非類別屬性相關(guān)聯(lián)；每個葉節(jié)點代表從樹根到葉節(jié)點之間的路徑所對應的記錄所屬的類別屬性值在ID3建立決策樹的過程中，一個重要的環(huán)節(jié)就是分裂屬性的選擇選擇分裂屬性時ID3中采用了信息增益的標準1.4.2 ID3算法基于ID3的基本思想，ID3的具體算法是：Function ID3R：一個非類別屬性集合；C：類別屬性；S：一個訓練集返回一個決策樹BeginIf S為空，返回一個值為丟失值的單個節(jié)點；If S是由其值均為相同類別屬性值的記錄組成，返回一個帶有該值的單個節(jié)點；If R為空，則

32、返回一個單節(jié)點，其值為在S的記錄中找出的頻率最高的類別屬性值；將R中屬性之間具有最大gain(D,S)值的屬性賦給D；將屬性D的值賦給djj=1,2,m;將分別由對應于D的值為dj的記錄組成的S的子集賦給sjj=1,2,m ;返回一棵樹，其根標記為D，樹枝標記為d1,d2,dm;再分別構(gòu)造以下樹：ID3（R-D,C,S1）,ID3（R-D,C,S2）,ID3（R-D,C,S1）;End ID31.4.3一個實例的具體分析下面就以有關(guān)天氣問題的數(shù)據(jù)為例仔細介紹一下信息增益的概念和最佳分裂屬性的選擇過程有關(guān)天氣問題的數(shù)據(jù)如表一所示：outlook(類型)temperature(溫度)humidit

33、y(濕度)windy(風)play(玩)sunnyhothighFalsenosunnyhothighTruenoovercasthothighFalseyesrainymildhighFalseyesrainycoolnormalFalseyesrainycoolnormalTruenoovercastcoolnormalTrueyessunnymildhighFalsenosunnycoolnormalFalseyesrainymildnormalFalseyessunnymildnormalTrueyesovercastmildhighTrueyesovercasthotnormalFa

34、lseyesrainymildhighTrueno一個屬性的信息增益是由于使用這個屬性分割實例而導致的期望熵降低例如，屬性A相對實例集合S的信息增益Gain(S,A)定義為：對表一中的各非類別屬性計算信息增益的過程如下：1計算總的信息熵信息熵的定義為：若給定的概率分布P=（P1,P2,Pn），則由該分布傳遞的信息量稱為P的信息熵，記為：在沒有建立決策樹之前，訓練實例集合包括9個yes和5個no節(jié)點，相應總的信息熵為info(9, 5) = 0.940 bits2計算以outlook屬性為根節(jié)點的樹分裂后各個節(jié)點的平均信息熵如圖以outlook屬性為根節(jié)點建立的樹為：編號與名稱（所有）考慮一下每

35、個節(jié)點的實例數(shù)目，我們計算一下他們的平均信息值；第一個和第三個節(jié)點有5個實例，第二個節(jié)點有4個，第三個節(jié)點有5個：info(2, 3, 4, 0, 3, 2) = (5 / 14) ×0.971 + (4 / 14) × 0 + (5 / 14) × 0.971 = 0.693 bits3計算屬性outlook的信息獲得gain(outlook) = info(9, 5) - info(2, 3, 4, 0, 3, 2) = 0.940 - 0.693 = 0.247 bits，4重復上述步驟，得到temperature、humidity和windy的信息獲得分別

36、為：gain(temperature) = 0.029 bitsgain(humidity) = 0.152 bitsgain(windy) = 0.048 bits，計算出各個非類別屬性的信息獲得后，我們由此來選擇信息獲得最大的屬性作為分裂屬性，由上述計算結(jié)果可以看出屬性outlook的信息獲得最大，則選擇其作為分裂屬性來建立決策樹然后我們繼續(xù)遞歸下去，圖二表明當outlook = sunny時，可能在節(jié)點產(chǎn)生一個更深的分支很明顯，還依照outlook（觀看）屬性來劃分下一層分支得不到任何新的東西，所以只考慮其它三個屬性他們各自的信息獲得值是gain(temperature) = 0.571

37、 bitsgain(humidity) = 0.971 bitsgain(windy) = 0.020 bits，所以我們選擇humidity（濕度）作為這個點的劃分屬性，沒有必要作進一步的劃分了，這個分支結(jié)束繼續(xù)用同樣的方法得到圖三的weather（天氣）數(shù)據(jù)的決策樹理想的情況是當所有葉子節(jié)點是純潔的時候過程結(jié)束即，他們所包含的實例屬于同一類然而，也許不可能達到這種狀態(tài)，因為有可能有一個實例集合，包含兩個實例，有同樣的屬性集合，但屬于不同的類，誰也不能保證這種情況不發(fā)生，所以當數(shù)據(jù)不能繼續(xù)劃分時就停止這樣就會在運用分類器給實例分類時出現(xiàn)有未分實例的現(xiàn)象上述過程是在ID3算法中建立決策樹的過程

38、，建立好決策樹后就可以利用些決策樹給實例進行分類分類過程是根據(jù)待分實例在所建決策樹中找到與其匹配的類屬性值的過程在程序設計中上也可以通過遞歸來實現(xiàn)下面以實例（sunny，hot，high，F(xiàn)alse）為例說明一下其分類過程：待分實例的在根節(jié)點outlook屬性上的值為sunny，所以沿outlook=sunny路徑，將實例分到以humidity屬性為根節(jié)點的子樹上待分實例的在當前根節(jié)點humidity屬性上的值為high，而 humidity=high路徑對應的節(jié)點為葉子節(jié)點，此葉子節(jié)點對應的類屬性值為no，因為已到葉子節(jié)點所以待分實例的類屬性值就為no1.4.4 ID3算法的不足及決策樹學習

39、中常見問題（偏置、過度擬合、連續(xù)值屬性和確實屬性的處理）-機器學習1.5 決策樹學習的改進算法C4.5類似于ID3基本思想和算法分析C4.5算法是一個里程碑式的決策樹算法，是迄今為止在實踐中應用最為廣泛的機器學習方法。它所采用的是分而治之策略其構(gòu)造決策樹的核心思想是貪心算法，它采用自上而下遞歸地各個擊破方式構(gòu)造決策樹。決策樹生成的難點主要有如何處理連續(xù)值屬性，如何處理缺省值，如何修剪決策樹。J48是在weka實驗平臺下它的具體實現(xiàn)程序1.5 實用的決策樹學習算法C C4.5算法的工作流程首先介紹算法，然后再說明各種特定問題。C4.5算法構(gòu)造決策樹的核心思想是貪心算法，它采用自上

40、而下遞歸地各個擊破方式構(gòu)造決策樹。開始時，所有的屬性都在根結(jié)點，這些屬性都是種類字段（如果是連續(xù)的，將其離散化），所有記錄用所選屬性遞歸的進行分裂，屬性的選擇是基于一個統(tǒng)計的度量，然后把這個過程遞歸到每個子樹，當一個結(jié)點上的數(shù)據(jù)都是屬于同一個類別或者沒有屬性可以再用于對數(shù)據(jù)進行分裂時停止分裂。決策樹生成之后，對樹剪枝以處理過分適應（Over-fitting）的問題。（以下文字的標題有待確定）C4.5分類器使用最大信息增益來選擇連續(xù)型屬性的閾值，它使得對結(jié)果劃分中的樣本分類所需的信息量最小，并反映劃分的最小隨機性或“不純性”。設是s個數(shù)據(jù)樣本的集合，假定類標屬性有m個不同值，定義了m個不同類ci

41、 ( i=1, 2， , m )設Si是類ci中的樣本數(shù)。對一個給定的樣本分類所需的期望信息由下式給出其中Pi是任意樣本屬于Ci概率，并用Si/S估計設連續(xù)值屬性A的閾值為a，可以用閾值a將S劃分為2個子集：S1=樣本|屬性值A的取值 a，S2=樣本|屬性值A的取值 a。設Sij是子集Sj中類Ci的樣本數(shù)。根據(jù)由a劃分成子集合的熵或期望信息由下式給出對于給定的子集Sj(j=1, 2)其中，Pij=Sij/Sj是Sj中的樣本屬于類Ci的概率。則屬性在閾值a上的信息增益為 換言之，gain(A)由于知道屬性A的閾值a而導致的熵期望壓縮。在現(xiàn)實數(shù)據(jù)集合里，屬性值缺損的現(xiàn)象很常見。處理缺損值的一個簡單

42、辦法就是刪除有缺損值的實例。另外一種方法是用一個簡單值代替缺損屬性值。C4.5算法保留有缺損值的實例，采取的方法是：當使用這個屬性值有缺損的屬性時，按照分裂分支下的訓練實例數(shù)的比率將有缺損值的實例分成一定比率的碎片23, 25。分而治之構(gòu)造決策樹C4.5構(gòu)造決策樹采取的方法是分而治之遞歸地構(gòu)造：首先，計算候選屬性的信息熵比率和增益比率，選擇一個最佳屬性（增益比率最大）作為根節(jié)點，并為每一個可能的屬性值生成一個分支這樣，把實例集合劃分成多個子集合（大小為屬性值的數(shù)目或者為2），該屬性的每一個值對應一個子集合現(xiàn)在對每一個分支重復以上的過程，過程中使用的實例集合是屬于那個分支的實例集合如果在一個節(jié)點

43、的所有實例屬于相同的類或者小于葉子節(jié)點限制的最少的實例數(shù)，則停止擴展那一部分子樹處理連續(xù)值屬性（有例子可以單獨作為一小節(jié)。）大多數(shù)真實數(shù)據(jù)集合都包含連續(xù)值屬性。針對連續(xù)值屬性C4.5采取的方法是二路分裂。C4.5按連續(xù)值屬性值升序排列數(shù)據(jù)集合的實例。順序取兩兩連續(xù)值屬性值的中點作為一個分裂點，可以把數(shù)據(jù)集合分裂為兩個子集合。如果連續(xù)值屬性有n個值，所以有n-1個可以作為分裂點的位置。依照這n-1個分裂點可以計算出n-1個信息熵值，找出其中最大值。將小于并且最接近信息熵最大的分裂點值，且存在于數(shù)據(jù)集合的屬性值定為最終分裂點值。例如：包含連續(xù)值屬性的天氣數(shù)據(jù)集合（ weather.arff）如表當

44、溫度(temperature) 屬性作為分裂屬性考慮時，C4.5首先按溫度(temperature) 屬性值升序排列數(shù)據(jù)集合的實例。溫度(temperature) 屬性值和類屬性(play)值的對應關(guān)系如下表：646568697071727580818385YesNoYesYesYesNoNoYesYesNoNoYesYesNo溫度(temperature) 屬性有12個值，所以有11個可以作為分裂點的位置(例如：以值71和值72的中值作為分裂的分水嶺，則可以按>71.5和<71.5將天氣數(shù)據(jù)集合分裂為兩個子集合)。依照這11個分裂點可以計算出11個信息熵值，找出其中最大值。假定求

45、出的最大信息熵的分裂點為71.5，J48仍然將小于并且最接近71.5，且存在于數(shù)據(jù)集合的屬性值71定為分裂點值采用枚舉型屬性和連續(xù)值屬性作為分裂屬性的不同之處，除了在于連續(xù)值屬性的分裂都是兩路分裂，而枚舉型屬性的分裂是多路分裂外，枚舉型屬性在決策樹里從根到葉子的任一條路徑上被作為分裂屬性只能是一次，而連續(xù)值屬性可以被利用多次，只需要每次的分裂點不同就可以。但是這樣做導致生成的決策樹的深度大為增加，可理解性差，不易于理解。解決的辦法是可以采取連續(xù)值屬性多路分裂，但是難于實現(xiàn)。也可以先調(diào)用離散化程序預處理連續(xù)值屬性，然后再建立決策樹。選擇最佳分裂屬性決策樹分類器的核心問題是在樹的每個節(jié)點上選取最佳

46、分裂屬性。最佳的分裂屬性應該是分類能力最好的屬性。信息增益就是用來形容給定的屬性區(qū)分訓練實例的能力。J48就是利用信息增益在增長樹的每一步中選取最佳分裂屬性。一個屬性的信息增益是由于使用這個屬性分割實例而導致的期望熵降低。J48算法計算每一個候選屬性的信息增益，接著計算增益比率，然后選擇增益比率最高的那個屬性作為最佳分裂屬性。例如：一個屬性的信息增益是由于使用這個屬性分割實例而導致的期望熵降低。例如，屬性A相對實例集合S的信息增益Gain(S,A)定義為：例如，屬性outlook相對與天氣數(shù)據(jù)集合的信息增益Gain(S,outlook)為：SunnyRainyOvercast Yes 2226

47、No123634512J48算法計算每一個候選屬性的信息增益，接著計算增益比率SplitInfo(S,outlook)是信息量。1.5.1 處理修改小節(jié)編號。未知值的訓練樣本、處理缺省值的方式處理缺省值（可以考慮加一個例題C4.5.doc）沒有處理未知值的訓練樣本在實際生活的數(shù)據(jù)集合里，屬性值缺省的現(xiàn)象很常見。處理缺省值的一個簡單辦法就是刪除有缺省值的實例。但是含有缺省值的實例通常提供了很多信息。有時候值缺省的屬性在決策中不起作用，所以在這種情況下它同其他沒有缺省值的實例一樣好。C4.5采取的方法是當使用這個缺省屬性作為分裂屬性時，按照分裂分支下的訓練實例數(shù)的比例將有缺省值的實例分成一定比例的

48、碎片。1.5.3 實基于的最好不要提及weka!所以就有適當修改下面所使用的數(shù)據(jù)結(jié)構(gòu)的名字，并且在使用之前加以說明。一個實例的具體分析有關(guān)天氣問題的數(shù)據(jù)如表所示：（該實例有待修改完善）Outlook(類型)temperature(溫度)humidity(濕度)windy(風)play(玩)Sunny8585FALSENoSunny8090TRUENoOvercast8386FALSEYesRainy7096FALSEYesRainy6880FALSEYesRainy6570TRUENoOvercast6465TRUEYesSunny7295FALSENoSunny6970FALSEYesRai

49、ny7580FALSEYesSunny7570TRUEYesOvercast7290TRUEYesOvercast8175FALSEYesRainy7191TRUENo一計算Outlook屬性的分裂信息熵增益以及增益率：currentMGain()=0.24674981977443902currentModel0.gainRatio()=0.15642756242117511計算temperature屬性的分裂信息熵增益以及增益率：currentMGain()=-0.18108904235959222currentModel1.gainRatio()=0

50、.0計算humidity屬性的分裂信息熵增益以及增益率：currentMGain()=-0.04868985021320138currentModel2.gainRatio()=0.0計算windy屬性的分裂信息熵增益以及增益率：currentMGain()=0.04812703040826933currentModel3.gainRatio()=0.048848615511520685選擇信息上增益率最大的作為分裂節(jié)點，因此這次選擇的是屬性下標簽為0的屬性作為分裂節(jié)點，也就是上表所示的outlook屬性作為分裂節(jié)點二其中選擇最佳分裂節(jié)點后的數(shù)據(jù)集為：說

51、明：localInstances0為outlook=sunny，localInstances為outlook=overcast，localInstances2為outlook=rainylocalInstances0=sunny,75,70,TRUE,yessunny,69,70,FALSE,yessunny,85,85,FALSE,nosunny,80,90,TRUE,nosunny,72,95,FALSE,nolocalInstances1=overcast,64,65,TRUE,yesovercast,81,75,FALSE,yesovercast,83,86,FALSE,yesover

52、cast,72,90,TRUE,yeslocalInstances2=rainy,65,70,TRUE,norainy,75,80,FALSE,yesrainy,68,80,FALSE,yes,rainy,71,91,TRUE,norainy,70,96,FALSE,yes如圖以outlook屬性為根節(jié)點建立的樹為：然后依次在此基礎上繼續(xù)向下遞歸分裂數(shù)據(jù)構(gòu)造決策樹：outlook=sunny在localInstances0上構(gòu)建決策樹的過程及其相應的輸出結(jié)果：（outlook=sunny）Outlook屬性的分裂信息熵增益以及增益率：currentMGain()=0.0cu

53、rrentModel0.gainRatio()=0.0temperature屬性的分裂信息熵增益以及增益率：currentMGain()=0.21997309402197512currentModel1.gainRatio()=0.22655436360850295humidity屬性的分裂信息熵增益以及增益率：currentMGain()=0.7709505944546688currentModel2.gainRatio()=0.7940162958421904windy屬性的分裂信息熵增益以及增益率：currentMGain()=

54、0.019973094021975158currentModel3.gainRatio()=0.020570659450693245要選擇信息上增益率最大的作為分裂節(jié)點，因此這次選擇的是屬性下標簽為2的屬性作為分裂節(jié)點，也就是上表所示的humidity屬性作為分裂節(jié)點；此時將數(shù)據(jù)集分成兩份：localInstances0（humidity<=70）和localInstances1 （humidity>=70）(采用二路分裂的方法，上面講過)localInstances0=sunny,75,70,TRUE,yessunny,69,70,FALSE,yeslocalInstances1=sunny,85,85,FALSE,nosun