基于決策樹的數(shù)據(jù)挖掘算法研究與應用

用樹分類的優(yōu)化算法，以便更好地提高分類的準確性，更好地應用于實際工作中。本inthefieldofbankingfinance,insurance,government,education,transportationandmethodsforDataclassification,suchasdecisiontreeinducclassificationtechnique,BayesianclassificationandBayesianbeliefnetworks,geneticalgorithms,neuralnetworks,roughsets,andsoon.fcurrentlyoneofthemostpopularinDataMiningalgorithmsaccordingtorelatedstatistics. Therefore,itpossessesimportanttheoreticadiscoveryissues,andthepurposeistoprobeintooptimizationandcombinationoftechnologymacroscopicalSecondly,severalcommonproblemsintheclassificadataset,wereanalyzedindetailbyusingthemethodofdecisiontree.Alloftheseproblemswouldreducetheaccuracyofclassification.SThirdly,thealgorithmofdecisiontreeisoptimizedinthispaper,themethodofresolvingtheproblemsofthevacancyofattributevalue,multi-valuebias,theprincipleofselectingattributewasputforward.Theconceptofweightedsimplificationentropyofatextilemill.ItprovidesascientifKeyword:Datamining,DecisionTree,ID3,Over-Fit本人聲明，所呈交的論文是我個人在導師指導下進行的研究工作及取得的研究成果。據(jù)我所知，除了文中特別加以標注和致謝的地方外，論文中不包含其他人己經(jīng)發(fā)表或撰寫過的研究成果，也不包含為獲得武漢理工大學或其它教育機構(gòu)的學位或證書而使用過的材料。與我一同工作的同志對本研究所做的任何貢獻均己在論文中作了明確的說明并表示了謝意。汗究生(簽名關(guān)于論文使用授權(quán)的說明本人完全了解武漢理工大學有關(guān)保留、使用學位論文的規(guī)定，即：學校有權(quán)保留送交論文的復印件，允許論文被查閱和借閱；學?？梢怨颊撐牡娜績?nèi)容，可以采用影印、縮印或其他研究生(簽名):導師(簽名):口期挪1隨著信息技術(shù)的迅猛發(fā)展以及人們獲取信息手段的多樣化，社會各行各業(yè)都擁有大量的信息數(shù)據(jù)。尤其是數(shù)據(jù)庫技術(shù)的不斷普及和應用水平的不斷完善，他們所能獲取到的信息還將呈幾何級數(shù)增長。大量激增的數(shù)據(jù)中往往隱藏著許多重要的信因此，對大量歷史數(shù)據(jù)進行分析處理，挖掘出有用的知識就顯得非常迫切。傳統(tǒng)的查詢技術(shù)不能解決目前面臨的信息爆炸問題，如何有效地管理，怎樣才能有效地利用數(shù)據(jù)庫中數(shù)據(jù)，以及怎樣才能發(fā)現(xiàn)其潛在的知識，這就需要有新的、更為有效的手段來對各種數(shù)據(jù)源整理并進行挖掘，以發(fā)現(xiàn)新的知識并發(fā)揮這些數(shù)據(jù)的潛能。數(shù)據(jù)挖掘正是在這樣的信息大爆炸的時代需求下產(chǎn)生并迅速發(fā)展起來的一門技術(shù)。數(shù)據(jù)挖掘"是一個利用各種分析工具在海量數(shù)據(jù)中發(fā)現(xiàn)模型和數(shù)據(jù)間關(guān)系的發(fā)現(xiàn)被忽略的因素，因而被認為是解決當今時代所面臨的數(shù)據(jù)爆炸而信息貧乏的一中有效方法。數(shù)據(jù)挖掘通常也稱為KDD(KnowledgeDiscoveryinDatabase)21一數(shù)據(jù)庫中的知識發(fā)現(xiàn)。數(shù)據(jù)挖掘是一門交叉學科，融合了數(shù)據(jù)庫、人工智能、機器學習、統(tǒng)計學等多個領(lǐng)域的理論和技術(shù)。當前對數(shù)據(jù)挖掘的研究主要集中在關(guān)聯(lián)規(guī)則⑤預測信息，從現(xiàn)有的數(shù)據(jù)中建立模型，計算未來值。分類和預測技術(shù)是數(shù)據(jù)挖掘中被廣泛研究的課題，并且己經(jīng)廣泛地應用于許多領(lǐng)域，如對電信、銀行、保險、零售、醫(yī)療等諸多行業(yè)提供決策支持，并對未來商業(yè)和人們的生活也將產(chǎn)生深遠的影響。分類研究在國外發(fā)展很快，己有很多成型的2的算法很多，如決策樹、貝葉斯分類、規(guī)則推理、遺傳算法和神經(jīng)網(wǎng)絡(luò)等，其中決策樹方抗噪聲能力強；③決策樹算法的可伸縮性強，既可用于小數(shù)據(jù)集，也可用于海量數(shù)據(jù)集。正因為如此決策樹算法也就成為數(shù)據(jù)挖掘研究中最活躍的領(lǐng)域之一。因此本文選擇基于決策樹的分類挖掘方法作為研究課題0圖1-1給出了決策樹的一般形式。決策樹的基本組成部分：決策結(jié)點、分支和葉子。決策樹中最上面的結(jié)點稱為根結(jié)點，這是整個決策樹的開策，通常對應與待分類對象的屬性。每一個葉結(jié)點代表一種可能的分類結(jié)果。在沿著決策樹從上往下遍歷的過程中，在每個結(jié)點都會遇到一個測試，對每個結(jié)點上問題的不同測試輸出導致不同的分支，最后會到達一個葉子結(jié)點。這個過程就是利用決策樹進行分類的過圖1-1決策樹一般表示形式重要性。從決策樹的根節(jié)點開始，沿著每一條路徑向下，屬性對于分類的重要性逐不同的決策樹算法有其不同的特性，充分認識各算法的優(yōu)點和存在的缺點，掌握其特定的適用環(huán)境，便于研究者明確對算法的改進點和研究的方向，也便于使用者選擇和應用。本文著眼于不同決策樹算法的典型代表，分析比較各自3最早的決策樹學習系統(tǒng)要追溯到Hunt于1966年研制的一個概念學習系統(tǒng)(CLS:選擇某一屬性(分類屬性)作為測試屬性，該測試屬性對應決策樹中的決策結(jié)點，根據(jù)該屬性的值的不同，可將訓練樣本分成相應的子集，如果該子集為空，或該子集中的樣本同屬一類，則該子集對應于決策樹的葉結(jié)點，否則該子集對應于決直到所有的子集都為空或?qū)儆谕活悺LS算法可描述如(1)生成一棵空決策樹和一張訓練樣本屬性表；(2)若樣本集中的樣本都屬于同一類，則生成結(jié)點T,并終止學習算法，(3)根據(jù)某種策略從訓練樣本屬性表中選擇屬性A作為測試屬性，并生成測試結(jié)(4)若A的取值SvpV》…,v,,則根據(jù)A的取值的不同，將T劃分為M個子集7;,7;,…,7;;(5)從訓練樣本屬性表中刪除屬性A;(6)轉(zhuǎn)步驟(2),對每一子集遞歸調(diào)用CLS。是可結(jié)束的。因為極端情況下，將所有屬性(不含分類結(jié)果屬性)都作為分類屬1979年，J.R,Quinlan提出的迭代分類器(ID3:IterativeDichotomizer3)算法4是決策樹算法的代表。它采用分治策略，在決策樹各級節(jié)點上選擇屬性時，用信息增益作為屬性的選擇標準，以便在每一個非葉節(jié)點上進行測試時，能獲得關(guān)于被測試記錄最大的類別信息。ID3算法的貢獻在于把信息論中信息熵的概念引入4FriedMan等人在1984年提出的一種決策樹分類方法。這種方法選擇具有最小基尼指數(shù)值的屬性作為測試屬性，最終生成二叉樹，然后利用重采樣技術(shù)進行誤差估計和樹剪枝(基于最小代價復雜性),然后選擇最優(yōu)的作為最終構(gòu)建的決策樹。這些算1984年，L.Breiman和J.Freidman等人提出了決策樹剪枝的概念，并提出了叫做誤差復雜性剪枝(ECP:Error-ComplexityPruning)的剪枝方法間。因為用于生樹剪枝方法的出現(xiàn)極大地改善了決策樹的性能。之后，不斷有新的剪枝算法提剪枝方法";1987年J.Mingers提出了臨界值剪枝(CVP:CriticalValuePruning)的1992年，K.Kira和L.Rend把數(shù)據(jù)集中的局部信息引入到?jīng)Q策樹算法中，局部信息的優(yōu)勢在于它能夠在其它屬性的背景下評估每一個屬性，而此前的決策樹算法都只能單獨地評估每一個屬性，1993年，J.R.Quinlan又提出了C4.5的不足。C4.5算法對于ID3算法的重要改進是使用信息增益率來選擇屬性。C4.5算法能處理連續(xù)值屬性的數(shù)據(jù)，這彌補了ID3算法只能處理離散值屬性數(shù)據(jù)的缺陷。同時還可用于增量式學習，隨著數(shù)據(jù)量的增加動態(tài)地調(diào)整決策樹，克服了ID31996年，M.Mehta和R.Agrawal等人提出了一種高速可伸縮的有監(jiān)督的尋找學習(SLIQ:SupervisedLearningInQuest)分類方法1氣51^1O針對數(shù)據(jù)量遠大于內(nèi)存容量的情況采用了類表、屬性表以及類直方圖三種數(shù)據(jù)結(jié)構(gòu)，利用換入換出策略5ScalableParallelizableInductionofdecisiontrees)分類方法1】,繼SLIQ分類方法后提出的又一種規(guī)?？勺兊?、支持并行計算的分類方法。SPRINT分類方法最大的優(yōu)點就是可以避免內(nèi)存空間的限制，利用多個并行處理器構(gòu)造一個穩(wěn)定的、分類準確率很高的決策樹，具有很好的可伸縮性，擴容性，但該算法因使用屬性列表，使得存儲代價大大增加，并且節(jié)點分割處理的過程較為復雜，加大了系統(tǒng)的負擔。)分類算法1,該算法提出了節(jié)點代價的目標函數(shù)，其主要思想是在決策樹建立階段，計算每個節(jié)點相關(guān)的目標函數(shù)值，估計該節(jié)點在將來調(diào)整階段是否被刪除。如果該節(jié)點將被刪除，則不對該節(jié)點進行擴張，否則，擴展該節(jié)點。從而建樹和修剪階段結(jié)合成為一個階段，而不是依次執(zhí)行1998年，J.Gehrke和R.Ramakrishnan等人提出雨林(RainForest)分類方法[5,它是一種針對大規(guī)模數(shù)據(jù)集，快速構(gòu)造決策樹的分類框架。RainFor的核心思想是根據(jù)每一次計算所能使用的內(nèi)存空間，合理地調(diào)整每次計算所處理的數(shù)據(jù)集的大小，使RainForest框架內(nèi)所使用的分類方法在每次計算的過程中，對內(nèi)存資源的利用率達到最大，在有限的資源下，用最少的時間完成決策樹的構(gòu)建。2002年，S.Ruggieri提出了C4.5的改進算法高2003年，C.Okra提出一種新的模糊決策樹分類方法——軟決策樹^。軟決策樹綜合決策樹的生成和修剪來決定其本身的結(jié)構(gòu)，并利用重修和磨合來提高樹的歸從改進ID3算法的角度：1998年，劉小虎博士和李生教授9提出，決策樹優(yōu)化是決策樹學習算法中十分重要的分支。以ID3為基礎(chǔ)，提出還需要考慮到該屬性后選擇的屬性帶來的信息增益，即同時考慮樹的兩層節(jié)點。62001年，郭茂祖博士和劉揚教授針對ID3多值偏向的缺陷，提出了一種新的基于屬性一值對為內(nèi)節(jié)點的決策樹歸納算法AVPI,它所產(chǎn)生的決策樹大小及測試速度均優(yōu)于ID3。從構(gòu)造機制的角度：1999年，吳菲和黃梯云教授2提出利用二元決策樹實現(xiàn)模型選擇，并采用遺傳算法構(gòu)造二元決策樹并提出了遺傳算法基于二元決策樹的模型選擇方法，以趨勢預測模型為例進行了驗證，獲得了較好的效果。2005年，黃沛等221提出一種基于遺傳算法的多重決策樹組合分類方法，該算法與單個決策樹相從多變量模糊決策樹的角度：2005年，黃定軒等123提出一類加權(quán)連續(xù)屬性的多變量決策樹構(gòu)造方法，首先利用粗糙集理論和模糊聚類理論確定連續(xù)多變量屬性的選擇問題，然后利用聚類中心算法建立等級標準中心以解決連續(xù)變量的區(qū)間劃分問題，其次將等價關(guān)系相對泛化的概念用于決策樹中多變量張曙紅教授等24給出了一種面向連續(xù)值屬性的模糊粗糙集決策樹分析方法。該方法基于模糊聚類對連續(xù)屬性進行離散化，并通過計算模糊隸屬度矩陣中條件屬性和類屬性之間的模糊依賴性量度來確定屬性的重要性和發(fā)現(xiàn)冗余屬性。從新的決策樹構(gòu)造方法的角度：2003年，楊宏偉博士和王熙照教授等f25用基于層次分解的方法通過產(chǎn)生多層決策樹來處理多類問題。2006,陽東升博士等126通過對組織協(xié)作網(wǎng)與決策樹的描述分析提出了組織結(jié)構(gòu)設(shè)計的新思路基于決策個體在任務(wù)上的協(xié)作關(guān)系設(shè)1.3決策樹算法研究發(fā)展方向通過對決策樹算法發(fā)展歷史的研究，可以發(fā)現(xiàn)未來決策樹算法研究將呈現(xiàn)一下(1)提高決策樹方法的效率。數(shù)據(jù)挖掘面臨的數(shù)據(jù)往往是海量的，對實時性要求較高的決策場所，數(shù)據(jù)挖掘方法的主動性和快速性顯得日益重要。應用實時性技術(shù)、主動數(shù)據(jù)庫技術(shù)和分布并行算法設(shè)計技術(shù)等現(xiàn)代計算機先進技術(shù)，是數(shù)據(jù)挖掘(2)適應多數(shù)據(jù)類型、容噪的決策樹挖掘方法。隨著計算機網(wǎng)絡(luò)和信息的社會化，數(shù)據(jù)挖掘的對象已經(jīng)不再單指關(guān)系數(shù)據(jù)庫模型，而是分布、異構(gòu)的多類型數(shù)據(jù)庫，數(shù)據(jù)的非結(jié)構(gòu)化程度、噪聲等現(xiàn)象越來越突出，這也是決策樹技術(shù)需要研究(3)決策樹方法的遞增性。數(shù)據(jù)挖掘出來的知識，只是相對于某一時間的某些數(shù)據(jù)的，新的數(shù)據(jù)可能使發(fā)現(xiàn)的新知識與原來的知識沖突。這是因為數(shù)據(jù)挖掘基(4)決策樹技術(shù)與其他技術(shù)的結(jié)合。在知識發(fā)現(xiàn)中，不可能用一種方法處理決策樹方法本身也可以和其它方法結(jié)合，現(xiàn)在已有人把決策模糊集理論、遺傳算法等相結(jié)合來進行研究，結(jié)果不同程度地提高了處理效率和精1.4.1本文的研究內(nèi)容本文主要針對ID3,C4.5,CART算法的優(yōu)缺點進行研究，討論了決策樹學習算法的基本思想、工作原理和適用范圍。并對決策樹歸納學習中常見的問題進行了綜合分析與比較，包括：過度擬合數(shù)據(jù)問題、處理連續(xù)屬性問題、處理缺省屬性問考慮到屬性間的相關(guān)性，這些算法的基本思想就是每次貪心選擇一個分類能力最強的屬性作為當前結(jié)點的測試屬性，然后根據(jù)測試屬存在很大的潛力，本文就目前的多變量決策樹的算法進行了總結(jié)。最后本文提出了一個改進的決策樹算法，并在一個物資設(shè)備管理系統(tǒng)中投入了使用，取得了不錯的1.4.2本文的組織結(jié)構(gòu)本文共分為六章。第1章介紹了選題的背景和意義、決策樹算法研究的國8內(nèi)外現(xiàn)狀及其發(fā)展方向；第2章對一些常見的分類算法、決策樹的基礎(chǔ)理論和常見的幾種決策樹算法作了深入的研究，為后面章節(jié)奠定了理論基礎(chǔ)；第3章分析了決策樹中的一些常見的問題，包括如何處理屬性空缺值、如何處理連續(xù)屬性值、如何避免過度擬合訓練數(shù)據(jù)、如何處理增量數(shù)據(jù)集和如何利用屬性間的相關(guān)性來構(gòu)造多取得了不錯的效果；第5章創(chuàng)造性地提出了加權(quán)簡化熵的概念，并且在此基礎(chǔ)上改進了ID3算法，然后將決策樹算法應用于一個物資設(shè)備管理系統(tǒng)，為系統(tǒng)的決策文的主要研究成果，分析存在的問題，指出有待進一步解決的問題。9第2章決策樹分類算法研究數(shù)據(jù)庫中隱藏著許多可以為商業(yè)、科研等活動的決策提供所需要的知識。分類和預測是兩種數(shù)據(jù)分析形式，它們可用于抽取能夠描述重要數(shù)據(jù)集合或預測未來數(shù)據(jù)趨勢的模型。分類方法用于預測數(shù)據(jù)對象的離散類別(categoricallabels);而預測 (prediction)則用于預測數(shù)據(jù)對象的連續(xù)取值，如：可以構(gòu)造一個分類模型來對銀行貸款進行風險評估(安全或者危險);也可以建立一個預測模型以利用顧客收入與職業(yè)(參數(shù))預測其可能用于購買計算機設(shè)備的支出大統(tǒng)計學和神經(jīng)生物學領(lǐng)域的研究人員已經(jīng)提出了許多具體的分類方法。當前數(shù)據(jù)挖掘分類中流行的幾個技術(shù)是神經(jīng)網(wǎng)絡(luò)、遺傳算法、貝葉斯分類和決策樹等。第一步，建立一個描述已知數(shù)據(jù)集類別或概念模型。如圖2-1所示該模型是通過數(shù)據(jù)庫中各數(shù)據(jù)行的內(nèi)容分析而獲得的。每一數(shù)據(jù)行都可以認為是屬于一個確定的數(shù)據(jù)類別，其類別值是由一個屬性描述(被稱為類別標記屬性)。分類學習方法而無教師監(jiān)督學習則是訓練樣本的類別與類別個數(shù)均未知的情況下進行的。通常分類學習所獲得的模型可以表示為分類規(guī)則形式、決策樹形或數(shù)學公式形式。例如：給定一個顧客信用信息數(shù)據(jù)庫，通過學習所獲得的分類規(guī)則可用于識別顧客是否是具有良好的信用等級或一般的信用等級。分類規(guī)則也可用于對(今后)未知(所屬類別)的數(shù)據(jù)進行識別判斷，同時也可以幫助用戶更好的了解數(shù)據(jù)庫中第二步，利用所獲得的模型進行分類操作。如圖2-2所示，首先對模型分類準確率進行估計。保留(holdout)方法是一種簡單的估計方法。它利用一組帶有類別的樣本進行分類測試(測試樣本隨即獲得且與訓練樣本相互獨立)。對于一個給定的數(shù)據(jù)集構(gòu)造出模型的準確性可以通過由該模型所正確分類的(測試)姓名姓名張峰李輝李東國姓名年齡收入信用評估汪明王敏李勇-般良好良好裾if年齡=30-40則信用評估J分類規(guī)則圖2-1數(shù)據(jù)分類過程中的第一步：學習建模數(shù)據(jù)樣本個數(shù)所占總測試樣本比例得到。對于每一個測試樣本，其已知的類別與學習所獲模型的預測類別進行比較。若模型的準確率是通過對學習數(shù)據(jù)集的測試所獲得的，這樣由于學習模型傾向于過分逼近訓練數(shù)據(jù)，從而造成對模型測試準確率的估計過于樂觀。因此需要使用一個測試數(shù)據(jù)集來對學習所獲得的準確率進行測試工作》如果一個學習所獲得的模型的準確率經(jīng)測試被認為是可以接受的，那么就可以使用這一模型對未來數(shù)據(jù)行或?qū)ο?其類別未知)進行分類。年齡敗入敗入離低離離信用評估一般良好jA據(jù)王露，3040,高!信用評估如何?分類算法分類算法圖2-2數(shù)據(jù)分類過程中的第二步；分類測試另外在進行分類挖掘之前，首先必須準備好挖掘數(shù)據(jù)，一般需要對數(shù)據(jù)進行以下(1)數(shù)據(jù)清理：這一數(shù)據(jù)預處理步驟，主要幫助除去數(shù)據(jù)中的噪音，并妥善解決遺失數(shù)據(jù)(missingdata)問題，盡管大多數(shù)分類算法都包含一些處理噪音和遺失數(shù)據(jù)的方法，但是這一步驟可以幫助有效減少學習過程中可能出現(xiàn)相互矛盾情況的問題。(2)相關(guān)分析：由于數(shù)據(jù)集中的許多屬性與挖掘任務(wù)本身可能是無關(guān)的，例如：記錄銀行貸款申請(單)填寫時的星期數(shù)(屬性),就可能與申請成功與否描述無關(guān)。此外，有些屬性也可能是冗余的。因此需要對近些年的數(shù)據(jù)進行相關(guān)分析，以幫助在學習階段就消除無關(guān)或冗余屬性。在機器學習中，這一相關(guān)分析步驟被稱為屬性選擇 (featureselection),包含與挖掘任務(wù)無關(guān)的屬性可能會減緩甚至誤導整個學習過程。在理想情況下，相關(guān)分析所花費的時間加上對消減后屬性(子)集進行歸納學習所花費時間之和，應小于從初始屬性集進行學習所花費的時間，從而達到幫助改善分類效(3)數(shù)據(jù)轉(zhuǎn)換：利用概念層次樹，數(shù)據(jù)能夠被泛化到更高的層次。概念層次樹對如：泛化到城市。由于泛化操作壓縮了原來的數(shù)據(jù)集，從而可以幫助有效減少學習過程所涉及的輸入偷出操作。此外初始數(shù)據(jù)可能還需要規(guī)格化，特別是利用距離計算方法進行各種學習方法時，如在基于示例學習方法中，規(guī)格化處理是不可或缺的重要處2.1常見的幾種分類算法2.1.1貝葉斯方法即給定樣本屬于一個特定類的概率。數(shù)據(jù)挖掘領(lǐng)域主要使用兩種貝葉斯方法，即樸素貝葉斯方法和貝葉斯網(wǎng)絡(luò)方法。前者使用貝葉斯公式進行預測，把從訓練樣本中計算出的各個屬性值與類別頻率之比作為先驗概率，并假定各個屬性之間是獨立的，然后后者是一個帶注釋的有向無環(huán)圖，以有效表示大變量集的聯(lián)合概率分布。適用于分析大量變量之間的相互關(guān)系，利用貝葉斯公式的學習和推理能力，實現(xiàn)預測、分類等數(shù)據(jù)挖掘任務(wù)。事實上，貝葉斯網(wǎng)絡(luò)也是一種適合表示不確定性知識的方法。貝葉斯網(wǎng)絡(luò)的構(gòu)造涉及網(wǎng)絡(luò)結(jié)構(gòu)和網(wǎng)絡(luò)參數(shù)兩部分的學習。但’是獲得最優(yōu)結(jié)構(gòu)和參數(shù)都是NPDuda和Hart給出了關(guān)于貝葉斯分類的全面介紹。樸素貝葉斯分類器29(NB)是一種成功的分類方法，已用于許多領(lǐng)域的分類問題，也出現(xiàn)了一些對樸素貝葉斯分類方法擴展的算法，大多數(shù)算法放松了對類條件的獨立假設(shè)。KDB算法利用參數(shù)K構(gòu)造一個貝葉斯分類器，其中每個屬性最多依賴K個其它的屬性。選擇貝葉斯分類器預處理數(shù)據(jù)集，通過刪除冗余屬性來選擇特征子集O可調(diào)節(jié)概率的NB算法為每個分類給出了一個權(quán)值，利用可調(diào)節(jié)的概率估計進行再利用貝葉斯分類器處理每個域。NBTree算法的分類準確性好于單純的NB算法和決策樹算法。后來，Boutilier等人提出了一種特定上下文的獨立性假設(shè)，即變量間集擴展貝葉斯分類器，并將其稱為LB算法(LargeBayes),算法性能優(yōu)于樸素貝葉斯分用關(guān)聯(lián)規(guī)則產(chǎn)生一個分類器及分類規(guī)則集，使用啟發(fā)式方法進行修剪[3。此外，Heckennan給出了貝葉斯信念網(wǎng)絡(luò)的介紹，Russell和Norvig給出了利用信念網(wǎng)絡(luò)進預測、推理和歸納等數(shù)據(jù)挖掘應用中。2.1.2神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)的研究己經(jīng)取得了許多方面的進展和成果，提出了大量的網(wǎng)絡(luò)模型，發(fā)現(xiàn)了許多學習算法，人工神經(jīng)網(wǎng)絡(luò)在模式分類、機器視覺、機器聽覺、智能計算、機器人控制、信號處理、組合優(yōu)化求解、醫(yī)學診斷、數(shù)據(jù)挖掘等領(lǐng)域具有很好的應用。自組織型。前向神經(jīng)網(wǎng)絡(luò)是數(shù)據(jù)挖掘中廣為應用的一類網(wǎng)絡(luò)，其原理和算法也是其它一些網(wǎng)絡(luò)的基礎(chǔ)。神經(jīng)網(wǎng)絡(luò)具有對噪聲數(shù)據(jù)的承受能力，尤其是它對未經(jīng)訓練的數(shù)據(jù)武漢理工大學碩士學位論文應用于超文本數(shù)據(jù)的分類視圖機制，通過自組織映射(SOM)和搜索引擎交互式WEB文檔的分類目前，神經(jīng)網(wǎng)絡(luò)作為一種自適應、自學習的算法模型在數(shù)據(jù)挖掘2.1.3支持矢量機2.2決策樹算法概述事例中推導出決策樹表示形式的分類規(guī)則，通常用來形成分類器和預測模型，可以對規(guī)則提取等領(lǐng)域有著廣泛應用，特別是在J.R.Quinlan于1986年提出ID3算法以后，決策樹方法在機器學習、知識發(fā)現(xiàn)領(lǐng)域得到了進一步應用及巨大的發(fā)展，在人工智能一棵決策樹的內(nèi)部結(jié)點是屬性或?qū)傩缘募?，葉結(jié)點是所要學習劃分的類，內(nèi)部結(jié)點的屬性稱為測試屬性。用決策樹進行分類分兩步走：第一步是利用訓練集建立一棵決策樹，建立決策樹模型。這個過程實際上是一個從數(shù)據(jù)中獲取知識，進行機器學習的過程。第二步是利用生成完畢的決策樹模型對未知的數(shù)據(jù)樣本進行分類。使用決策樹對未知的數(shù)據(jù)樣本進行分類的時候從根結(jié)點開始對該對象的屬性逐漸測試其值，并且順著分支向下走，直至到達某個葉結(jié)點，此時葉結(jié)點代表的類即為該對象所處的決策樹分類方法首先要利用訓練集建立決策樹模型，然后根據(jù)這個決策樹模型對輸入數(shù)據(jù)進行分類。其中，關(guān)鍵問題在于決策樹的構(gòu)建過程，這一過程-包括建樹和剪枝兩個步驟：第一個步驟為建樹階段。選取部分訓練數(shù)據(jù)，按廣度優(yōu)先遞歸算法建立決策樹，直到每個葉子結(jié)點屬于同一個類為止。第二個步驟為剪枝階段。它是用剩余的數(shù)據(jù)對生成的決策樹進行檢驗，將不正確的問題進行調(diào)整，對決策樹進行剪枝和增加結(jié)點，直到建立一個正確的決策樹。決策樹的建樹算法是通過遞歸過程，最終得到一棵決策樹，而剪枝則是為了降低噪聲數(shù)據(jù)對分類正確率的影響。對一個分類問題或規(guī)則學習問題，決策樹的生成是一個從上至下、分而治之的過程，本質(zhì)是貪心算法。從根結(jié)點開始，對每個非葉結(jié)點，找出其對應樣本集中的一個訓練樣本集劃分成若干個子樣本集，每個子樣本集構(gòu)成一個新葉結(jié)點，對新葉結(jié)點再重復上述劃分過程，這樣不斷循環(huán)，直至達到特定的終止條件。其中，測試屬性的選擇和如何劃分樣本集是構(gòu)建決策樹的關(guān)鍵環(huán)節(jié)。不同的決策樹算法在此使用的技術(shù)不據(jù)不同的屬性值判斷從該結(jié)點向下的分枝，在決策樹的葉結(jié)點的一條路徑就對應著一條合取規(guī)則，整棵決策樹就對應著一組析取表達式規(guī)則?；跊Q策樹的學習算法的一個最大優(yōu)點就是它在學習過程中不需要使用者了解很多的背景知識(這也同時是它最大在決策樹的學習算法當中，除去分類的正確性應當放在第一位給予考慮之外，決策樹的復雜程度是另外一個需要考慮的重要因素。如果決策樹構(gòu)造的過于復雜，那么而且，決策樹構(gòu)造的越小，其存儲所花的代價也越小，對它的某些操作相對來說也就簡單省時。所以應該在保證正確率的前提下盡量構(gòu)造簡單的決策樹。簡化決策樹的方法很多，剪枝是最常用的方法，它主要通過在訓練過程中明確地控制樹的大小來簡化決策樹。當決策樹創(chuàng)建時，由于訓練數(shù)據(jù)集中的噪聲和孤立點的影響，許多分枝反映的是訓練數(shù)據(jù)中的異常。剪枝方法也可以處理這種過度擬合(over-fitting)數(shù)據(jù)問題。它主要包括預剪枝(per-pruning)與后剪枝(預剪枝就是在完全正確分類訓練集之前，較早地停止樹的生長。具體在什么時候(1)一種最為簡單的方法就是在決策樹到達一定高度的情況下就停止樹的生長，這(2)到達此結(jié)點的實例具有相同的特征向量，而不必一定屬于同一類，也可停止生得在測試集上的準確度或其他測度不降低(不會變得更壞),則剪去該葉子。試集(剪枝數(shù)據(jù)集)來計算子樹的精確度。它將樹上的每一個結(jié)點作為修剪的侯選對質(zhì)的子樹.,則S被刪除，用葉子結(jié)點替代。重復此過程，直到任意規(guī)模最小的樹。另外它的計算復雜性是線性的，這是因為決策樹中的每個非葉子結(jié)點只需要訪問一次就可以評估其子樹被修剪的概率。再者，由于使用獨立的測試集，和原始決策樹相比，修剪后的決策樹對未來新事例的預測偏差較小。但是該方法也存在不足之處，它偏向于過度修剪。因為那些在測試集中不會出現(xiàn)的一些很稀少的訓練數(shù)據(jù)實例所對應的分枝，在剪枝過程中都要被刪除。當測試集比訓練集小得多的時候，這一問題尤其突出。如果訓練數(shù)據(jù)集較少，通常不考慮采用REP方法。盡管存在這些缺點，REP方法仍常常作為一種基準來評價其他剪枝方法的性能，它對于了解兩階段決策樹方法學習的優(yōu)點和缺點提供了一個良好的初始切入點271。PEP方法是Quinlan為了克服REP方法需要獨立剪枝數(shù)據(jù)集的缺點而提出的。假類的個數(shù)為e的，由于訓練數(shù)據(jù)既用來生成決策樹又用來修剪樹，因此基于此訓練數(shù)據(jù)集的誤差率=是有偏差的，它不能精確地用來選擇最好的修剪樹。為此，QuMan對誤差估計增加了連續(xù)性校正，將誤差率修改為：r-(O設(shè)s為樹r的子樹r(O,其葉子結(jié)點的個數(shù)為LOs),r(O的分類誤差為：在定量的分析中，為簡單起見，則用錯誤總數(shù)取代錯誤率的表示，即e'(O=e(O+1/2。那么對于子樹r(f),如果所得到的決策樹精確地分類各個實例，即誤差e(s)=0,此時eX?:)等于一個常量1/2,它僅僅代表決策樹關(guān)聯(lián)每個葉子的時間復雜性的度量。當訓練集中有樣本沖突時，此結(jié)果將不再成立。一般來說，某一中間結(jié)點f被葉子結(jié)點替換的條件是：替換后子樹I;的誤差率要小于結(jié)點f的。但是由于連續(xù)校正的存在，有時候會發(fā)生》分)《(7;)這種情況。此時結(jié)點f也要被刪除掉。不過這種情況出現(xiàn)的幾率不大，為此，Quinlan削弱了對錯誤率的限制，修改為：其中，·^丨稱為標準誤差，定義如下：咒E,O;)]-(式如果式子(2-1)成立，則子樹I;應被修剪掉，用相應的葉子結(jié)點替代。對所有非葉子結(jié)點依次計算測試，來判斷它們是否應被修剪掉。PEP方法中在誤差估計中引入連續(xù)校正這一機制并沒有充分的理論基礎(chǔ)。在統(tǒng)計上，我們通常用二項式分布來取代正態(tài)分布，但是它卻不用于校正誤差率的樂觀估計。事實上，連續(xù)校正只對引入復雜度因子是有效的，然而這個因子不能被看成錯誤率，否則可能導致剪枝不徹底或者過分剪枝。如果所得到的決策樹完全精確地分類所有的訓練實例，那么:s2e(f)(式2-2)也就是說，如果子樹7:中關(guān)于幫助糾正分類錯誤的葉子結(jié)點數(shù)足夠大的話，就得對7;進行剪枝。常量1/2也僅僅簡單地表示一個葉子對整棵樹的復雜性的貢獻1^。顯然，這個常量只適用于某些情況。PEP方法被認為是當前決策樹后剪枝方法中精度較高的算法之一。但它仍然存在一些缺陷，PEP是唯一使用自頂向下剪枝策略的后剪枝方法，這種策略會帶來與預剪枝出現(xiàn)的同樣問題，那就是樹的某個結(jié)點會在其子樹根據(jù)同樣的準則雖然PEP方法存在這樣的局限，但它在實際應用中表現(xiàn)出了較高它不需要獨立的測試集，這對樣本數(shù)據(jù)較少的問題是非常有利的。再者，自頂向下的剪枝策略與其他方法相比效率更高，速度更快。這是因為，樹中每棵子樹最多需要訪MEP方法由Niblett和Bratko首先提出7,它在一個相對獨立的數(shù)據(jù)集上從樹的葉子結(jié)點開始，向上搜索一個單一的樹來使分類誤差的期望概率達到最小，但它并不需要一個額外的修剪數(shù)據(jù)集。無論是最初的版本還是稍后的改進版本，在決策樹的剪不妨假設(shè)訓練集數(shù)據(jù)的類別總數(shù)為灸，對于樹中的當前非葉子結(jié)點【,所包含的樣本數(shù)為AT(f),屬于主導類f的樣本個數(shù)為%(?),不屬于主導類的樣本數(shù)N(t)+mN(t)+m為了簡單起見，假設(shè)所有的分類概率是相等的，即A=%,并且結(jié)果類的概率是均勻分布的，即^=^(【=12,…,灸)。則結(jié)點r分類誤差的期望概率為：EER(t)=minNj^-N^+k-l在MEP方法中，對于決策樹中的葉子結(jié)點，我們利用上式來計算決策樹中葉子結(jié)點計算該結(jié)點t的誤差，稱之為靜態(tài)誤差STE(O,然后計算這m個分枝的誤差，并且加權(quán)求和，權(quán)值為每個分枝擁有的訓練樣本的比例。我們將加權(quán)求和后的誤差稱之為動樹的修剪程度就越大。如果m趨于無窮大，6(0=盡，由于A是訓練集中屬于第/類的樣本所占的百分比，這樣整棵樹被剪裁為一個葉子結(jié)點，此時擁有最小的誤差概率。但是事實上，較高的w值并不能自動生成規(guī)模較小的樹，這種非單調(diào)性對MEP的計算復雜度影響很大，如果增加m的值，修剪操作必須從原始的樹開始不同的噪音程度甚至是通過對選擇生成樹的學習來為m選擇適當?shù)闹怠５?在大多數(shù)情況下，沒有這樣的專家領(lǐng)域。因此我們可以采用一個獨立的修剪數(shù)據(jù)集，首先在這個在決策樹的學習算法當中，決策樹的復雜度(1)預測準確性：該指標描述分類模型準確預測新的或未知的數(shù)據(jù)類的能力。預測準確性是決策人員最關(guān)心的問題，對于他們來說，之所以采用分類發(fā)現(xiàn)模型中得到的信息的準確程度不同在很大程度上將會影響決策人員決策制定的準確(2)描述的簡潔性：這是針對分類發(fā)現(xiàn)模型對問題的描述方式以及該描述方式的可理解水平提出的。分類發(fā)現(xiàn)模型的最終目的是方便決策人員的使用，所以，對于決策人員來說，模型描述越簡潔，也就越易于理解，同時也就越受歡迎。例如采用規(guī)(3)計算復雜性：計算復雜性依賴于具體的實現(xiàn)細節(jié)，在數(shù)據(jù)挖掘中，由于某(4)模型強健性：強健性是對模型預測準確性的一個補充，是在存在噪聲及數(shù)據(jù)缺損的情況下，準確對未知其類的數(shù)據(jù)進行分類的能力。正如前面所提到的，數(shù)據(jù)數(shù)據(jù)以及冗余數(shù)據(jù)等情況是普遍存在的，在這種情況下，就要求所建立的模型對這些(5)處理規(guī)模性：處理規(guī)模性是指在巨量數(shù)據(jù)的情況下構(gòu)造模型的能力以及構(gòu)造分類模型的精確度。數(shù)據(jù)挖掘所處理的對象數(shù)量是巨大的，那么就要求所構(gòu)建的挖2.3幾種常見的決策樹算法231ID3算法1D3算法是一個典型的決策樹學習算法，其核心是在決策樹的各級結(jié)點上，使用信息增益方法作為屬性選擇標準，來幫助確定生成每個結(jié)點時所應采用的合適屬性。這樣就可以選擇具有最高信息增益的屬性作為當前結(jié)點的測試屬性，以便使用該屬性定義2.1設(shè)C/是論域，丨不，...,;}是的一個劃分，其上有概率分布乃《尸(^),則稱武漢理工大學碩士學位論文ff(X)p.logpi為信源Z的信息熵，其中對數(shù)取以2為底，而當某個凡為零時，則可以理解為0-logO=義為：在ID3算法分類問題中，每個實體用多個特征來描述，每個特征限于在一個離散集中取互斥的值。ID3算法的基本原理如下：設(shè)有窮向量空間，其中6是有窮離散符號集。E:中的元素e-cFpK,…,F,>稱為樣世界中僅有兩個類別，在這種兩個類別的歸納任務(wù)中，和AQ的實體分別稱為概念的正例和反例。假設(shè)向量空間E中的正、反例集的大小分別為P、N,由決策樹的基本思想，ID3算法是基于如下2種假設(shè)：一棵正確的決策樹對任意樣本集的分類概率同f.中的正、反例的概率一致。(2)根據(jù)定義(2.1),—棵決策樹對一樣本集做出正確分類，所需要的信息熵I(P,N)(式2-6)如果選擇屬性4作為決策樹的根，4取F個不同的值{為,^,…,^},利用屬性本數(shù)據(jù)，假設(shè)乓中含有A.個正例和%個反例，那么子集盡所需要的期望信息是”凡，/^,以屬性A為根所需要的期望熵為：以A為根的信息增益是：ID3算法選擇(4)最大的屬性，作為根結(jié)點，對，的不同取值對應的五的F個子集ID3算法的基本原理是基于兩類問題的，但是它很容易被擴展到多類問題。設(shè)樣本集S共有C類樣本，每類的樣本數(shù)為，…,C)。如果以屬性』作為即選擇屬性，,使最小，信息增益將最大O實際上，能正確分類訓練集的決策樹不止一棵。ID3算法能得出結(jié)點最小的決策在ID3算法的每一個循環(huán)過程中，都對訓練集進行查詢以確定屬性的信息增益，然而此時的工作只是查詢樣本的子集而沒有對其分類。為了避免訪問全部數(shù)據(jù)集，ID3算法采用了稱為窗口(Windows)的方法，窗口隨機性是從數(shù)據(jù)集中選擇一個子集ID3算法的主算法非常簡單，首先從訓練集中隨機選擇一個窗口(既含正例又含反例的#本子集),用建樹算法2.1對當前窗口形成一棵決策樹；其次，對訓練集(窗口除外)中例子用所得到的決策樹進行類別判定，找出錯判的例子。若存在錯判的例子，把>生成決策樹1取子集建窗口訓練集VES決策輸出r■展窗口其中分別代表正例集和反例集，它們共同組成訓練樣本集。和分別代表正例集和反例集的子集。算法每迭代循環(huán)一次，生空的樹開始，然后逐步考慮更加復雜的假設(shè)。通過觀察搜索空間和搜索策略，我們可(1)ID3算法的假設(shè)空間包含所有的決策樹，搜索空間是完整的假設(shè)空間。因為每個有限離散值函數(shù)可以被表示為某個決策樹，所以它避免了假設(shè)空間可能不包含目(1)當遍歷決策樹空間時，ID3算法僅維護單一的當前假設(shè)，它失去了表示(3)ID3算法使用的基于互信息的計算方法依賴于屬性值數(shù)目較多的屬性，232C45算法在ID3的基礎(chǔ)上增加了對連續(xù)型屬性和屬性值空缺情況的處理，對樹剪枝也有了較成則用4對S進行劃分的信息增益率為：(式2-9)C4.5算法不僅可以處理離散屬性，還可以處理連續(xù)屬性?；舅枷胧前堰B續(xù)值屬性的值域分割為離散的區(qū)間集合。若j是在連續(xù)區(qū)間取值的連續(xù)型屬性，首先將訓練集Z的樣本根據(jù)屬性^的值從小到大排序，一般用快速排序法。假設(shè)訓練樣本集中d有m個不同的取值，則排好序后屬性的取值序列為分割點，分割點將樣本集劃分為兩個子集，分別對應共有w-1個分GainRatio(v')的分割點v_作為局部閾值。則按連續(xù)屬性d劃分樣本集Z的信息增益率v的取值K成為屬性^的分割閾值。按照上述方法求出當前候選屬性集中所有屬性的信息增益率，找出其中信息增益率最高的屬性作為測試屬性，把樣本集劃分為若在計算期望信息熵時^只計算那些已知測試屬性值的樣本，然后乘以這些樣本在當前結(jié)點的訓練集中的比例作為整個訓練集的期望信息熵：在計算劃分信息熵時，把那些丟失測試屬性值的樣本作為一個新的類別對待，單獨計算這些樣本的期望信息熵；在劃分訓練集時，先將正常的樣本按照一般的算法劃分成幾個子集，然后把那些丟失測試屬性值的樣本按照一定的概率分布到各個子集中。子集中的丟失測試屬性值的樣本與將該事例通過所有的分支，然后將結(jié)果進行合并，使它成為在類上的概率分布而不是某一個類。最終結(jié)果是具有最大概率的類。C4.5算法在計算連續(xù)屬性的信息增益時，需要對屬性的所有取值線性掃描找出局部閾值，這種方法使C4.5的效率受到限制。2002年，SalvatoreRuggier提c的所有樣本的權(quán)值之和。數(shù)組/IFC己記載了計算屬性信息增益的一切信息。實驗表明，與C.45相比，EC.45在生成同樣一棵決策樹時可將效率提高5倍，但EC4.5占用內(nèi)存比C4.5多。比較ID3算法，C4.5算法在效率上有了很大的提高。不僅可以直接處理連續(xù)型屬性，還可以允許訓練樣本集中出現(xiàn)屬性空缺的樣本。生成的決策樹的分枝也較少。信息增益函數(shù)對于那些可能產(chǎn)生多分支輸出的測試傾向于產(chǎn)生大的函數(shù)值，但是輸出分支多不表示該測試對未知的對象具有更好的預測效果。信息增益率函數(shù)可以彌補這個缺陷。以往的經(jīng)驗說明信息增益率函數(shù)比信息增益函數(shù)更健壯，能穩(wěn)定的選擇好的測試。(1)C4.5采用的是分而治之的策略，在構(gòu)造樹的內(nèi)部結(jié)點的時候是局部最優(yōu)的搜索方式，所以它所得到的最終結(jié)果盡管有很高的準確性，仍然達不到全局最優(yōu)的結(jié)(2)C4.5評價決策樹最主要的依據(jù)是決策樹的錯誤率，對樹的深度、結(jié)點的個數(shù)等不進行考慮，而樹平均深度直接對應著決策樹的預測速度，樹的結(jié)點個數(shù)則代表(3)—邊構(gòu)造決策樹，一邊進行評價，決策樹構(gòu)造出來之后，很難再調(diào)整樹的(4)C4.5在進行屬性值分組時逐個試探，沒有一種使用啟發(fā)搜索的機制，分組(5)信息增益率函數(shù)也有它的缺陷。如果劃分的優(yōu)度非常小，也就是劃分的信息熵值非常小，信息增益率會不穩(wěn)定。當屬性a只有一個屬性值，或者訓練實例對屬使得信息增益率沒有意義，或者使得決策樹進行一次沒有意義的分類(即決策樹的這個法的一種。它描述給定預測向量值X后，變量Y條件分布的一個靈活的方法。該模型樹中的葉節(jié)點對應著劃分的不同區(qū)域，劃分是由與每個內(nèi)部節(jié)點相關(guān)的分支規(guī)則節(jié)點，Y在該節(jié)點上的條件分布也被確定。CART模型最早由Breman等人提出并已在CART是一種有監(jiān)督學習算法，即用戶在使用CART進行預測之前，必須首先提以是離散的。當Y是有序的數(shù)量值時，稱為回歸樹；當Y是離散值時，稱為分類樹。構(gòu)建樹7_是將給定的學習樣本集L轉(zhuǎn)換為對應L的最大二叉樹的過程。該過程數(shù)據(jù)預處理首先進行降低屬性向量的基數(shù)，即將向量分為若干段*然后針對屬性向量構(gòu)建標準問題集，其中屬性向量分為連續(xù)屬性向量與離散屬性向量，兩者的標準1.降低屬性向量基數(shù)針對屬性向量值進行降低基數(shù)工作，即針對每一屬性向量設(shè)定一組離散值，按用戶業(yè)務(wù)需求，將該屬性向量在L上的取值分配到這組范圍值中。當樣本集中指針向量X是連續(xù)屬性向量，則對X的所有取值，取出最大值尤_和最小值尤_,并將該指針向量唯一化取值，按照從小到大的順序排列尤=(^,^,...,^),然后使用取中值法在這AT個取值中取出況’個2這L個值對應的所有可能子集S共有21-1-1個，依照這2W-1決策樹生長的核心算法是確定一個決策樹分枝準則，該準則涉及到兩方面問題：生成原始樹首先引入差異系數(shù)(diversityindex)的概念。這個系數(shù)用于測度每一個結(jié)點內(nèi)a2)個類樣本的差異程度。在這里如果集合r包含AT個類別的記錄，那么指數(shù)就是：(式2-10)如果集合r在Z的條件下分成兩部分]^和&,那么這個分割的指數(shù)在對樣本集進行分割時，分割規(guī)則采用二叉表示形式，算法從根結(jié)點開始分割，遞歸地對每個結(jié)點重復(1)對于每一個結(jié)點選擇每個屬性最優(yōu)的分割點。選擇某個屬性的最優(yōu)分分割點的過程是這樣的：對于連續(xù)變量X表示為{XX,.>CC為樣本空間中變量X,.的取值范圍內(nèi)的一個常數(shù)，Z=m為連續(xù)變量個數(shù)},而對于離散變量x,_表示為{X]x,.ev集，VCU,Z=V”,《;n為離散變量個數(shù)},據(jù)樣本對分割規(guī)則“是”或“否”的回答，將這個結(jié)點分為左右兩個子結(jié)點，從這些規(guī)則中找到如果使得(2)在這些最優(yōu)分割點中選擇對這個結(jié)點最優(yōu)的分割點，成為這個結(jié)點的分割規(guī)則。而分割規(guī)則的確定依據(jù)為使得式2-11最小。(3)繼續(xù)對此結(jié)點分割出來的兩個結(jié)點進行分割。分割的過程可以一直持續(xù)到葉結(jié)點樣本個數(shù)很少(如少于5個),或者樣本基本上屬于同一類別才停止，這時建成的樹層次多，葉結(jié)點多，我們記該樹為°分類回歸樹是基于統(tǒng)計理論的非參數(shù)的識別技術(shù)，它具有非常強大的統(tǒng)計解析功能，對輸入數(shù)據(jù)和預測數(shù)據(jù)的要求可以是不完整的，或者是復雜的浮點數(shù)運算。而且，數(shù)據(jù)處理后的結(jié)果所包含的規(guī)則明白易懂。因此，分類回歸樹已成為對特征數(shù)據(jù)進行建立統(tǒng)計解析模型的一個很好的方法。當然，與其它統(tǒng)計分析方2.4本章小結(jié)用這些算法進行學習訓練時間少、精度高、可以生成可理解的規(guī)則，而且使用者也容易理解接受。這些算法對于許多小數(shù)據(jù)集的學習歸納而言已經(jīng)證明是行之有效的，但是這些算法本身也存在不少的缺點，因此針對不同的訓練集選擇恰當?shù)牡?章決策樹中常見問題的分析3.1決策樹歸納學習的最優(yōu)化問題決策樹歸納學習的主要目標就是使得到的決策樹分類精度高、速度快。大多數(shù)決策樹算法的核心問題是在決策樹中各級結(jié)點上屬性的選擇。實際上，我們更希望選擇的是最有助于分類樣本實例的屬性。那么衡量這些指標的標準是什么呢?下面從示例)是機器學習按推理策略進行分類的一種學習方法，它是對于某些概念的正例集合和反例集合，通過歸納推理產(chǎn)生覆蓋所有正例，并排除所有反例的概念描述的一般規(guī)則。因此，示例學習也叫做概念獲取 計算復雜性的證明是由洪家榮于1985年給出的。示例學習的目標是尋找在反例集合背(1)最優(yōu)覆蓋問題(MCV)生成具有最少數(shù)目公式(合取式)的覆蓋。(2)最簡公式問題(MCOMP)生成具有最少數(shù)目選擇子及屬性值的公式。(3)最優(yōu)示例學習問題(OPL)生成只由最簡公式組成的覆蓋。洪家榮證明了這幾個問題都是NP-Hard問題144。因此，只能通過努力尋找其近似或啟發(fā)式算法?？紤]決策樹歸納學習的最優(yōu)化，可以先將決策樹轉(zhuǎn)化為規(guī)則形式。從而由規(guī)則優(yōu)化的三個目標就可以得到?jīng)Q策樹歸納學習相應的三個優(yōu)化原則。假設(shè)r是由正例集合尸E和反例集合所構(gòu)造出的決策樹，對于T中任意一個非葉上的屬性4及樹枝上的值用一個選擇子[^=K](1)生成最少數(shù)目的葉子，對應于MCV;(2)生成的每個葉子的深度最小，對應于MCOMP;(3)生成的決策樹葉子數(shù)最少且每個葉子的深度最小，對應于OPL。我們知道，通過將屬性值的定義域劃分為非重疊區(qū)域，就可以處理連續(xù)屬性值的樣本數(shù)據(jù)。而劃分的方法是等分法，包括等寬區(qū)間法和等頻區(qū)間法。假設(shè)實例集s中連續(xù)屬性^的最大值和最小值分別為，和。等寬區(qū)間法就成N個小區(qū)間，每個區(qū)間內(nèi)包含的樣本實例大致相同。雖然等分法容易實現(xiàn)，但是它忽略了樣本集中的概念類等關(guān)鍵信息，因此，有時候并不能產(chǎn)生合理的劃分區(qū)間。對于樣本實例s而言，如果選擇了兩個區(qū)域之間的邊界，就能夠?qū)颖緦嵗齽澐譃閮蓚€不同的子集，其屬性值不超過該邊界的樣本子集和樣本子集的補集，隨后利用舉例來說，假設(shè)我們希望用連續(xù)值屬性此length來描述訓練樣例，對于與決策樹中，有4個侯選閾值，分別是：(9+12)/2,(18+23)/2,(23+27)/2,(27+33)/2。我們表3-1length屬性對應的類別描述90NPPNPN屬性的值域進行劃分，是通過對屬性值域的所有可能的劃分空間進行完全搜索來3.3屬性值空缺的處理在一個數(shù)據(jù)集中，經(jīng)常會缺少某些樣本的一些屬性值一這種不完全性在實(1)拋棄數(shù)據(jù)庫中有丟失數(shù)據(jù)的樣本。在C4.5算法中，有未知值的樣本是按照已知值的相對頻率隨機分布的，這頻率，這些概率可以被再次估計。例如，給定一個布爾屬性A,如果結(jié)點n包含7個已知和3個d=0的樣例，那么4=1的概率是0.7,』=0的概率是0L于是實例X的70%被分配到A=1的分支，30%被分配到A=0的分支。另外，如果有第二個缺少值的屬性必須被測試，這些片段樣例可以在后繼的分支中被進一步細分。該策略也可以用在分類缺省屬性的新實例中。在這種情況下，新實例的分類就是最可能的分類。計算的方法是根據(jù)屬性取不同的值出現(xiàn)的概率，通過在樹的葉子結(jié)點3.4避免過度擬合訓練數(shù)據(jù)決策樹算法通過對訓練樣本集學習，在每一個結(jié)點按照一定的策略選擇合適的測試屬性，引出相應的分枝，并不斷地增長樹的每一個分枝，直到恰好完美地對訓練樣本集進行分類。事實上，通過對訓練集的學習來構(gòu)造決策樹往往無法達到最好的泛化不能產(chǎn)生目標函數(shù)有代表性的采樣時，決策樹的性能便會受到很大的影響。因此如何避免過度擬合訓練數(shù)據(jù)，是決策樹算法必須考慮的一個重要問題。訓練樣本的假設(shè)<^根據(jù)歸納假設(shè)原理，如果預先知道所要學習的函數(shù)屬于整個假設(shè)空間中一個很小的子集即這一假設(shè)在足夠大的訓練樣本集中很好地對其數(shù)據(jù)進行分類，那么它也能夠?qū)ξ粗獙嵗M行正確分類。相反，如果訓練樣本集與整個假設(shè)空間相比已經(jīng)非常小，但仍有過多的與訓練實例相一致的假設(shè)供我們選擇，此時做出假設(shè)的泛給定一個假設(shè)好，如果在假設(shè)空間上存在另一個假設(shè)//’,使得在訓練集上H的錯誤率差比小，而在測試集上的錯誤率卻比/T要大，那么稱假設(shè)//過度擬合訓練度擬合圖3-1顯示了ID3算法的一個典型應用中過度擬合的影響。圖中橫軸表示在決策樹創(chuàng)建過程中樹的結(jié)點總數(shù)，縱軸表示決策樹的預測精度，實線顯示的是決策樹在訓練集上的精度，虛線顯示的則是在一個獨立的測試集上測量出來的精度。可以看出隨著樹的增長，在訓練樣集上的精度是單調(diào)上升的，然而在獨立的測試集上測出的精度先上升后下降。是什么導致H比//’更好地擬合訓練樣例，但對于后來的測試實例卻表現(xiàn)非常差呢?發(fā)生這種情況的原因可能是訓練樣例中含有隨機錯誤或者噪聲，分類噪聲或者屬性噪聲都可能導致過度擬合。而另一方面，噪聲會直接導致樣本的沖突，比如對某一個實例的每個屬性都有相同的描述，卻有著不同的分類結(jié)果。當樣本數(shù)據(jù)描述的屬性不完備、不足以判別分類標準時，也會導致樣本的沖突。樣本沖突也可以看作是樣本的錯誤數(shù)據(jù)，也存在導致過度擬合的風險。事實上，即使訓練數(shù)據(jù)沒有噪聲，過度擬合也有可能發(fā)生，特別是當某些決策與客觀事實不符合、僅僅基于少量訓練數(shù)據(jù)時。這種情況下，很可能出現(xiàn)巧合的規(guī)律性，使得一些屬性恰好可以準確地分類訓練樣例，但是卻與實際的目標函數(shù)并沒有絲毫的關(guān)系。一旦這樣巧合的規(guī)律性存在，也會出現(xiàn)過度擬合的風險。例如，有一氣候訓練樣本如表(3-2),按照ID3算法構(gòu)建的決策樹如圖(3-2)。表3-2訓練樣本表圖3-2構(gòu)建的決策樹考慮在表的原本正確的樣本集中加入一條訓練正例D15,但是卻被錯誤地標記為反例：Strong,PlayTennis=No>,增加了這個錯誤樣例后，導致生成一棵更復雜的決策樹。不過，只要新的噪聲樣例與原來這個結(jié)點所包含的樣例有任何差異，1O3算法終究會找到一個新的決策屬性來把該噪聲樣例從這些樣例中分離出來。這樣的結(jié)果是ID3算法會歸納出另外一棵決策樹，如圖3-3所示。由于新的樣例被錯誤地標記為反例，所以ID3算法會在圖3-2表示的樹的左起第二個結(jié)點下面進一步搜索更多的細節(jié)，這些額圖3-3由含有噪聲的訓練集得到的決策樹任何決策樹模型在構(gòu)造過程中都可能存在過他很多學習算法是一個重要的實踐難題。1989年Mingers在相關(guān)文獻中指出，對于涉及5種帶有噪聲的和缺省屬性數(shù)據(jù)的不同研究中，過度擬合使決策樹的精度降低了1成大量的碎片，即一些結(jié)點的樣本數(shù)太少，缺乏必要的統(tǒng)計意義。造成這一問題的原因可能是這些樣本本身就是異常數(shù)據(jù)或者噪聲數(shù)據(jù)，也可能是由于不合理的分枝標準決策樹規(guī)模太大，難兔會過度擬合訓練數(shù)據(jù)。研究證明，大而復雜的決策樹并不意味著可以得到更加準確的規(guī)則集。另外，尋找最小決策樹被證明是NP問題中找不到絕對的最小決策樹。為了避免過度擬合，我們只能通過分析造成過度擬合的方法。這兩種剪枝方法我在決策樹剪枝技術(shù)中己經(jīng)做了詳細的研究，無論是通過預剪枝還是后修剪來得到正確的決策樹，剪枝過程中最關(guān)鍵的一個3.5如何處理增量數(shù)據(jù)集的問題在于只能利用靜態(tài)的數(shù)據(jù)集構(gòu)造決策時，對于處理增量(Incremental)數(shù)據(jù)集的規(guī)則挖Utgoff等人先后提出增量D3算法來解決這個問題。正如Utgoff所說：“增量推理的出現(xiàn)有許多原因，其中最重要的就是，現(xiàn)存知識的修改可以近似地認為是人類對知識吸因此要求推理的方法也必須適應增量事物的特點。”這正是增量算法出現(xiàn)的原因所當有新記錄加入訓練數(shù)據(jù)集時，有可能產(chǎn)生原先選定的分類屬性對新記錄分類能力降低，而原先未被選中的候選屬性集中的某個屬性的分類能力增高的情況。在這種情況下，構(gòu)造決策樹時的分類屬性選擇就要以候選屬性集中的那個分類能力高的屬性為準。這就是增量決策樹算法利用增量數(shù)據(jù)集構(gòu)造決策樹的基本思路，這種方法保證作為節(jié)點的分類屬性始終包含有最大的信息量，能夠保證構(gòu)造的決策樹一直沿著熵值3.5.1增量決策樹算法的基本原理當有新記錄加入訓練數(shù)據(jù)集時，有可能產(chǎn)生原先選定的分類屬性對新記錄分類能力降低，而原先未被選中的候選屬性集中的某個屬性的分類能力增高的情況。在這種情況下，構(gòu)造決策樹時的分類屬性選擇就要以候選屬性集中的那1個分類能力高的屬性為準。這就是增量決策樹算法利用增量數(shù)據(jù)集構(gòu)造決策樹的基本思路，這種方法保證作為節(jié)點的分類屬性始終包含有最大的信息量，能夠保證構(gòu)造的決策樹一直沿著熵值減少最大的方向拓展。假設(shè)一個給定的決策樹節(jié)點上存在兩個候選屬性6和F?,并且經(jīng)計算可知，如果6的信息增益大于屬性F?,則將6作為分類屬性。根據(jù)ID3算法原理可得如下的公式：gai^FJagain(F?)<=>IGj>,n)-E(Fx)aI(p,n)-E(F?)E{Fx)sE(F?)oE?^E?其中信息熵E的計算公式為：It代表候選屬性的取值種類，凡和當有新的記錄增加進來時，將對屬性巧和巧的信息增益產(chǎn)生影響，屬性^和F?信息增益大小的變化有可能導致分類屬性的變化，當有一條新記錄到達上述節(jié)點時，新記錄一定對應屬性^和/^的某一值段j,假設(shè)新增記錄的類主屬性為p.不失一般性，新增記錄后，屬性的信息熵E的計算公式如下E'=UPi加：Pi+riiPj+1現(xiàn)在作如下處理：;《:=&,,可得A=xlogjc+(Jc+y+1)log(j[:+y+1)-(x+7)I0g(x+y)~(x+1)log(j:為了確定新增加的記錄對兩個候選屬性信息熵影響的邊界值，必須計算AE的最大值新增《條記錄，存在如下一種特殊情況，新增的每條記錄使某個候選屬性的熵變選定的分類屬性熵變?nèi)〉米钚≈礎(chǔ)Emin,則新增a條記錄導致候選屬性與分類屬[性熵值的總差異的不等式48為：假設(shè)新增記錄的數(shù)量a小于屬性j值段上的樣本記錄數(shù)量，故有《,對上式進分類屬性和候選屬性熵值的差決定了增加記錄的數(shù)量a,故有根據(jù)上式的特點，給出增量決策樹的修改策略：(1)當新增記錄a^、,,時，新增記錄后的分類屬性信息熵值小于候選屬性的信息熵值，仍然選擇原先的分類屬性作為節(jié)點屬性。(2)當新增記錄時，新增記錄后的分類屬性信息增量決策樹算法在ID3算法的基礎(chǔ)上，解決增量數(shù)據(jù)集構(gòu)造決策樹的問題，避免ID3算法處理增量數(shù)據(jù)集時，不斷重構(gòu)決策樹龐大的計算費用。增量決策樹算法的計算法基本相同。增量決策樹算法具有方便、快捷、準確等特點，利用增量決策樹算法處理增量數(shù)據(jù)集的方法在目前的數(shù)據(jù)挖掘領(lǐng)域中被廣泛地應用。3.6如何處理相關(guān)屬性的問題大多數(shù)決策樹被限制在每個結(jié)點上只檢驗單個屬性.這樣的決策樹被稱之為單變這一限制使得對很多復雜概念的表達變得困難或無法表達。這種表示上的限制主要是以兩種形式表現(xiàn)的：一棵決策樹中子樹的重復49和有些屬性在一棵決策樹中的某一路徑上被多次檢驗。然而，在現(xiàn)實生活中各種信息系統(tǒng)中的屬性間的關(guān)聯(lián)作用是普遍存在的。單變量決策樹通常無法反映這種關(guān)聯(lián)作用，而且往往修剪的代價較大。在修剪的過程中又會丟失一些看似無用實際卻包含信息的屬性，這種限制成了提高決策樹分類精度的瓶頸。為了克服這一點，人們提出了多變量決策樹的概念，即在樹的節(jié)點上可以同時檢驗多個屬性。這種方法往往產(chǎn)生新的更相關(guān)的屬性以代替初始屬性。對于重復子樹問題，pagallo等人通過構(gòu)造屬性的Boolean組合，己經(jīng)說明可以提出利用粗糙集來構(gòu)造多變量決策樹，本文簡單介紹一下利用粗糙集構(gòu)造多變量決策樹的問題。構(gòu)造多變量決策樹的關(guān)鍵問題是多變量檢驗的構(gòu)造問題.它涉及2個方面：一是選擇什么樣的初始屬性包含在多變量檢驗中?二是如何利用選擇的屬性來構(gòu)造多變量檢利用粗糙集構(gòu)造多變量決策樹的算法[?】和單變量決策樹算法的構(gòu)造算法有很大的相似之處，都是從有標有類別信息的事物中，通過遞歸的方法來構(gòu)造決策樹。利用粗糙集構(gòu)造多變量決策樹的算法是從信息系統(tǒng)表示的數(shù)據(jù)中導出決策樹。形式上一個數(shù)。/JVD(C)的等價類稱為條件類，/ATD(D)的等價類稱為決策類。一個自頂向下的決策樹算法是，首先根據(jù)某種劃分度量準則選擇最佳檢驗，然后，用選擇的檢驗去劃分訓練集，并且，相應于該檢驗的每一個結(jié)果產(chǎn)生一個分枝。這一算法遞歸地應用到該檢驗導出的每一個分類上。如果某一分類中的所有事例都來自于一個類別，那么就產(chǎn)生一個標有該類別名的葉結(jié)點。在決策樹的構(gòu)造過程中，人們希望在每個結(jié)點上都選擇能把事例劃分到它們類中的最佳檢驗。單變量決策樹和多變量決策樹的差別在于前者的檢驗是基于單個屬性的，而后者的檢驗是基于一個或多個屬性的。單變量決策樹中通常使用的劃分度量準則是熵或不純(impurity)測度。這里使用屬性的區(qū)分能力作為劃分度量準則.根據(jù)相對核的定義，我們知道條件屬性集相對于決策屬性集的核中的屬性對于制定決策來說是至關(guān)重要的。下面給出構(gòu)造多變量檢驗的一般步驟：相對于決策屬性集D的核，即COi?Eo(C)。若(2)用ID3的方法選擇一個最佳屬性，作為該結(jié)點的檢驗。計算尸相對于Z)的泛化(尸)511,將它作為3.7本章小結(jié)本章詳細分析了決策樹算法存在的常見問題：如何處理屬性值空缺，如何對連續(xù)屬性進行概化，如何避免過度擬合訓練數(shù)據(jù)集、決策樹算法如何適應不斷增長的數(shù)據(jù)集以及如何充分考慮屬性間的相關(guān)性構(gòu)建多變量決策樹。解決好這些問題對提高決策樹的精度，提高決策樹的效率，更好的利用決策樹解決現(xiàn)實問題有十分重要的意義，第4章決策樹算法的優(yōu)化研究決策樹算法作為一種最為典型的分類算法，其分類過程無須背景知識、清晰、易于理解，有很大的實際應用價值。但是在實際應用之中，也暴露了許多不足之處，因本章在原有的決策樹算法的基礎(chǔ)上提出了適合于處理高維數(shù)據(jù)的優(yōu)化算法，以提高決策樹算法的效率和使用性能。首先假定決策樹的所有測試屬性均為離散值。經(jīng)驗表明決策樹算法要能構(gòu)建出一棵正確的決策樹，訓練集本身要滿足充分性和相容性的要求，測試集都滿足相容性要求[52。為了更好的理解這兩個概念，這里給出充分性和定義4.1訓練集滿足充分性是指當且僅當存在一棵決策樹使得它的每一個葉節(jié)點在訓定義4.2訓練集滿足相容性是指集合里不存在相互沖突的實例。我們可以參照樣本相似性的原理，通過比較訓練集中的其他完整實例來選擇一個較優(yōu)的填充值，對訓練集中的缺失屬性值在構(gòu)建決策樹之前進行填充。具體的填充過峋是訓練集中的iST個屬性集合4,為,…,4r中的-個。其中有一個實例$在(1)在訓練集中找出其余尺個屬性取值和實例S對應一致的實例，組成一個實例集合r;(2)如果集合#0,轉(zhuǎn)(4),否則轉(zhuǎn)(3);(3)令瓦=久-1,如果冬<X,則從訓練集中刪除實例S,否則轉(zhuǎn)(1);(4)計算集合r中，碑的不同取值的比例。利用取值比例最大的值進行填4.2基于粗糙集理論的降維方法于1982年提出的，它將分類方法看成知識，分類方法的族集稱為知識庫。知識庫中可能含有冗余的知識，保持分類能力不變的前提下刪除冗余的知識，即是對知識的約簡。在決策樹生成算法中利用訓練集的識別矩陣和識別函數(shù)對測試屬性進行約簡不僅使決策樹的規(guī)模更小，計算效率更高，而且使決策者避免了無用測試屬性的干擾，信息采集更加科學。為了更好的理解定義4.3訓練集的識別矩陣M定義為一個二階對稱矩陣，其中i行j處的元素定定義4.4訓練集的識別函數(shù)定義如下：p=A{vms},函數(shù)p的最小析取范式中各個合取式分別對應C的D約簡。D={e},訓練集如表(4*1)所示，識別矩陣如表(4-2)由表(4-2)可以得出識別函數(shù)如下：故<:的E>約簡有兩個，分別為伙，0和儀，d}。測試屬性約簡后決策表更小，而且決策效果不變。假設(shè)訓練集中有/*個對象，測試屬性為講個，且有《>>m約簡屬性所需的時間復雜度為表4-1訓練樣本集武漢理工大學碩士學位論文UabCde102111020112002122102l00221102表4-2識別矩陣AbX?4.3屬性選擇法則的優(yōu)化只能采用啟發(fā)式策略選擇好的屬性。不過大量的實踐證明，常規(guī)的屬性選擇標準都不能從本質(zhì)上反映屬性對類別進行正確區(qū)分的能力，而且計算復雜。從決策樹的基本原理我們知道決策樹的形成是以信息論的原理為基礎(chǔ)。主要用一個分裂節(jié)點時，算法均要涉及多次對數(shù)運算。在大數(shù)據(jù)量的時候，該運算顯然會影響到?jīng)Q策樹生成的效率，因此考慮改變數(shù)據(jù)集中屬性選擇的標準，減小決策樹的計算成本，節(jié)省決策樹的生成時間。4.3.1優(yōu)化的理論基礎(chǔ)在高等數(shù)學中我們已經(jīng)學習了泰勒公式和麥克勞林公式，為了實現(xiàn)對屬性選擇的優(yōu)化，這里首先介紹一下這兩個公式。由函數(shù)微分知：f(x)=f(xa)+f(xo)(x-xo)+o(x-xa)略去得到/(X的近似公式f(x)-f(xo)+f(xo)(x-xo)其誤差為：R(x)=f(x)~f(xo)-fxo)(x-xo)該公式存在誤差，精確度不高，誤差難于估計。為了達到一定的精確度要求，考設(shè)函數(shù)/OO在含%的開區(qū)間內(nèi)具有直到+1)階導數(shù)，我們希望找出一個關(guān)來近似表達/(X)。我們更希望巧(4)與/九在%的各階導數(shù)(直到(《+1)階導數(shù))相等。即：fxO)P,,xO)f(xO)=p^(xo)因此多項式的系數(shù)可以歸納為：于是所求的多項式為：C)《JC,這個關(guān)系在后面的算法優(yōu)化中會用到。4.3.2克服屬性選擇的多值偏向從決策樹算法的基本原理可知，ID3算法利用每個屬性信息熵的值來判斷數(shù)據(jù)集中的分裂屬性，選擇時往往偏向于取值較多的屬性；C4.5算法利用屬性信息增益率來判斷分裂屬性，偏向于取值不均勻的屬性。針對這一問題，人們提出了許多方法，如：采用增益比率方法、索引方法、G統(tǒng)計方法等等。從已有的許多改進算法原理和信息增益的基本公式中可知，信息增益的大小決定于信息熵，而信息熵是用于反映每個屬性對整個數(shù)據(jù)集的不確定程度。本文對每個屬性的信息熵引入一權(quán)值K,用于平衡每個屬性對數(shù)據(jù)集的不確定程度，使之更加符合實際的數(shù)據(jù)分布情況。對權(quán)值的引入，本文采用每個屬性在數(shù)據(jù)集中的取值個數(shù)，再將該權(quán)值乘以信息熵，使信息熵結(jié)果還依賴于屬性的取值個數(shù)，即將每個屬性的取值考慮在內(nèi)，從而克服ID3和C4.5算法選擇測試屬性時的偏向問題。4.3.3屬性選擇標準的改進根據(jù)前面的決策樹基本原理和優(yōu)化的理論基礎(chǔ)，本文對信息增益公式進行轉(zhuǎn)換，從而尋找到一種屬性選擇的新標準，使采用新標準選擇出的屬性不僅可以克服1D3,C4.5算法容易偏向于選擇取值較多和取值不均勻的屬性作為測試屬性的缺點，還使算法生成決策樹的時間大大的減少，減少了算法的計算成本，加快了決策樹的構(gòu)建速度，提高了決策樹分類器的效率。構(gòu)建決策樹，由公式講加O4)=/(/,^)-五O4)可知，由于每個節(jié)點上的式(4-1)“P,AO是一個定量，則可以選取屬性Z的熵值作為節(jié)點之間的比較標準。其中：pipt-fnxr(P+N)In2Pi+np+ntp;+np.+n’式(4.2)由于(/>-AOhi2在訓練數(shù)據(jù)集中是個常量，所以可以假設(shè)一函數(shù)5^4)滿足以下公式：根據(jù)泰勒公式和麥克勞林公式可知，當x-》0時，+因此可以將二y2/7,71,rPin,式(4-3)SO4)中只含有加、乘、算，運算的時間肯定比中含有多個對數(shù)項的運算時間要短。由此，)函數(shù)的熵值進行比較，選出最大信息增益即屬性的熵值,的節(jié)點作為分裂節(jié)點。在本文中將稱為簡化信息熵。但S(4)的產(chǎn)生是根據(jù)Ina+^-x約等式，故在對5(4)賦予屬性值的個數(shù)JV之前，決策樹分類器的數(shù)據(jù)分類準確率肯定會受到影響。不過從后面的實驗數(shù)據(jù)結(jié)果來看，這種影響從分類器對數(shù)據(jù)分類的整個性能來看是很小的；賦予了屬性值個數(shù)之后，新的屬性選擇標準不但克服了ID3算法和C4.5算法選擇屬性時的缺點，還彌補了由泰勒公式帶來的誤差，提高了決策樹分類器的分類效簡化運算很容易擴展到多類。設(shè)樣本集S共有C類樣本訓練集每類樣本數(shù)為…,C,那么子集的熵為：Entropy以A為根分類后的熵為：類別的情況比較多”因此在同樣情況下，用f計算屬性的信息Piti|盡I熵要比用EO4)函數(shù)簡單快捷得多，從而提高決策樹分類器的效率。這里用一個具體實例來比較上面改進辦法和ID3算法之間的優(yōu)劣，訓練樣本如表(4-3)。