數(shù)據(jù)挖掘決策樹算法的研究與改進(jìn)

1、海 南 師 范 大 學(xué) 本科生畢業(yè)論文（設(shè)計(jì)）題目：決策樹算法的研究與改進(jìn)姓 名： 學(xué) 號(hào)： 專 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) 年 級(jí)： 05專升本 系 別： 計(jì)算機(jī)科學(xué)與教育技術(shù) 完成日期： 2007年5月20日 指導(dǎo)教師： 本科生畢業(yè)論文（設(shè)計(jì)）獨(dú)創(chuàng)性聲明 本人聲明所呈交的畢業(yè)論文（設(shè)計(jì)）是本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究成果，除了文中特別加以標(biāo)注和致謝的地方外，本論文中沒有抄襲他人研究成果和偽造數(shù)據(jù)等行為 。與我一同工作的同志對本研究所做的任何貢獻(xiàn)均已在論文中作了明確的說明并表示謝意。論文（設(shè)計(jì)）作者簽名： 日期：2007年5月21日本科生畢業(yè)論文（設(shè)計(jì)）使用授權(quán)聲明海南師范大學(xué)有權(quán)

2、保留并向國家有關(guān)部門或機(jī)構(gòu)送交畢業(yè)論文（設(shè)計(jì)）的復(fù)印件和磁盤，允許畢業(yè)論文（設(shè)計(jì)）被查閱和借閱。本人授權(quán)海南師范大學(xué)可以將本畢業(yè)論文（設(shè)計(jì)）的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或其他復(fù)印手段保存、匯編畢業(yè)論文（設(shè)計(jì)）。論文（設(shè)計(jì)）作者簽名： 日期：2007年5月21日指 導(dǎo) 教 師 簽 名： 日期： 目錄1.引言12.決策樹算法的研究22.1.基本定義22.1.1.歸納學(xué)習(xí)的基本概念22.1.2.信息論的基本概念22.1.3.決策樹的基本概念32.2.幾種常見的決策樹算法的簡單介紹42.2.1.ID3 算法42.2.2.C4.5算法簡介112.2.3.遺傳算法GA(Gen

3、etic Algorithm)122.3.決策樹的評(píng)價(jià)標(biāo)準(zhǔn)1132.4.決策樹的進(jìn)展與發(fā)展方向152.4.1.數(shù)據(jù)挖掘中決策樹算法的主要進(jìn)展152.4.2.決策樹技術(shù)面臨的挑戰(zhàn)及目前研究方向153.關(guān)于決策樹算法的改進(jìn)153.1.基于樣本離散度6的特征選擇方法163.1.1.基本概念163.1.2.基于離散度的改進(jìn)算法173.1.3.分析與比較183.1.4.小結(jié)183.2.利用條件概率的思想來改進(jìn)決策樹算法183.2.1.算法的理論基礎(chǔ)與基本思想193.2.2.舉例分析193.2.3.分析與比較273.2.4.小結(jié)274.總結(jié)285.結(jié)束語286.致謝28參考文獻(xiàn)29挖掘決策樹算法的研究與改

4、進(jìn)作者： 指導(dǎo)老師：（海南師范大學(xué)，海口，）摘 要：在大量信息展現(xiàn)給人們的時(shí)候，“知識(shí)爆炸”給人們帶來了極大的困擾，如何有效的利用數(shù)據(jù)成為人們事業(yè)成敗的關(guān)鍵。本論文主要對決策樹的常見算法做初步的研究與探討，并給出決策樹的評(píng)價(jià)標(biāo)準(zhǔn)。并在此基礎(chǔ)上利用最新的決策樹算法思想由本人設(shè)計(jì)實(shí)例集驗(yàn)證相關(guān)文獻(xiàn)中筆者的思想，最后提出自己一點(diǎn)意見和看法。關(guān)鍵詞：數(shù)據(jù)挖掘；決策樹；研究；改進(jìn) The Research and Improvement Of Data Mining decision-making tree algorithm Author: Tutor: (Hainan Normal Universi

5、ty,HaiKou,)Abstract: Nowadays there are so much information tounfold in the people at present, which causes our eyes taking out all in, the knowledge explosion has brought the enormous puzzle to the people, how does the effective use data become the people enterprise success or failure the key. This

6、 paper mainly discussed the preliminary research and the discussion to the policy-making trees common algorithm, and produces the policy-making trees evaluation criteria, as well as to policy-making tree future discussion. Using the newest policy-making algorithm thought in this foundation to design

7、 in the example collection confirmation correlation literature after myself authors thought, finally proposes a Propose his viewpoint and the view.Key words: Data Mining; decision-making tree; Research; Improvement1.引言隨著現(xiàn)代信息技術(shù)的飛速發(fā)展，在全球范圍內(nèi)掀起了信息化（Information）浪潮。信息產(chǎn)生的渠道多而且寬廣，更新的頻率日益加快，各行業(yè)均產(chǎn)生了大量的信息。面對大量

8、多的數(shù)據(jù)，人們往往無法找到自己所需要的知識(shí)或信息，這就是所謂“信息爆炸3”（Information detonation）以及它給人們帶來的困惑。如何有效地利用和處理大量的信息成為當(dāng)今世界共同關(guān)心的問題。隨著數(shù)據(jù)庫技術(shù)（Database technology）、人工智能（Artificial intelligence）、數(shù)理統(tǒng)計(jì)（Mathematical statistic）和并行計(jì)算（Parallel computation）等技術(shù)的發(fā)展與融合，數(shù)據(jù)挖掘（data mining，DM）技術(shù)應(yīng)運(yùn)而生。自數(shù)據(jù)挖掘技術(shù)誕生以來，關(guān)于數(shù)據(jù)挖掘技術(shù)的研究也就開始了。數(shù)據(jù)挖掘是一門新興的交叉學(xué)科，自提出

9、以來，引起了眾多專家學(xué)者的廣泛關(guān)注，數(shù)據(jù)開采（Data mining）、數(shù)據(jù)采掘（Data excavation）、知識(shí)發(fā)現(xiàn)（Knowledge discovery）和信息抽取（Information extracts）等許多同義詞相繼出現(xiàn)。目前，普遍采用的主要有數(shù)據(jù)挖掘（DM）和數(shù)據(jù)庫中的知識(shí)發(fā)現(xiàn)（Knowledge Discovery in Database，簡稱KDD）。數(shù)據(jù)挖掘有廣義和狹義之分，廣義的數(shù)據(jù)挖掘，指從大量的數(shù)據(jù)中發(fā)現(xiàn)隱藏的、內(nèi)在的和有用的知識(shí)或信息的過程。狹義的數(shù)據(jù)挖掘是指知識(shí)發(fā)現(xiàn)中的一個(gè)關(guān)鍵步驟，是一個(gè)抽取有用模式或建立模型的重要環(huán)節(jié)。數(shù)據(jù)挖掘是在對數(shù)據(jù)實(shí)例集全面而深刻

10、認(rèn)識(shí)的基礎(chǔ)上，對數(shù)據(jù)內(nèi)在和本質(zhì)的高度抽象與概括，也是對數(shù)據(jù)從感性認(rèn)識(shí)到理性認(rèn)識(shí)的升華2。如今有多種數(shù)據(jù)挖掘技術(shù)方法，可以分為兩大類。決策樹就是其中的一種，決策樹主要是基于數(shù)據(jù)的屬性值進(jìn)行歸納分類，常用于分類的層次方法有“if-then1”規(guī)則。決策樹方法的最大優(yōu)點(diǎn)就是可理解性，比較直觀。它與神經(jīng)網(wǎng)絡(luò)（另外一種數(shù)據(jù)挖掘技術(shù)方法）最大的區(qū)別是，決策樹可以解釋如何得出結(jié)果的決策過程。其缺點(diǎn)是處理復(fù)雜性的數(shù)據(jù)時(shí)，分支數(shù)目非常多，管理難度大。同時(shí)，還存在數(shù)據(jù)的“缺值”處理問題。其經(jīng)典算法有ID3、C4.5、CART、CHAID、SLIQ和SPRINT等。本論文主要對決策樹的常見算法（ID3算法、C4.5

11、算法）做初步的研究與探討，（由于遺傳算法與決策樹的構(gòu)造類型相似，這里也有涉及。）并給出決策樹的評(píng)價(jià)標(biāo)準(zhǔn)以及決策樹的發(fā)展現(xiàn)狀和以后的發(fā)展方向。并在此基礎(chǔ)上利用最新的決策樹算法思想由本人設(shè)計(jì)實(shí)例集驗(yàn)證相關(guān)文獻(xiàn)中筆者的思想，最后提出自己一點(diǎn)意見和看法。2.決策樹算法的研究2.1.基本定義2.1.1.歸納學(xué)習(xí)的基本概念歸納學(xué)習(xí)(induction Learning) 是符號(hào)學(xué)習(xí)中研究最為廣泛的一種方法。給定關(guān)于某個(gè)概念的一系列已知的正例和反例，從中歸納出一個(gè)通用的概念描述。歸納學(xué)習(xí)能夠獲得新的概念，創(chuàng)立新的規(guī)則，發(fā)現(xiàn)新的理論。它的一般操作是泛化（generalization）和特化（specializ

12、ation）。泛化用來擴(kuò)展一假設(shè)的語義信息，以使其能夠包含更多的正例，應(yīng)用于更多的情況。特化是泛化的相反操作，用于限制概念描述的應(yīng)用范圍。2.1.2.信息論的基本概念信息論在決策樹學(xué)習(xí)中有著重要的意義，1948年Shannon1提出并發(fā)展了信息論，研究以數(shù)學(xué)的方法度量并研究信息。通過通信后對信源中各種符號(hào)出現(xiàn)的不確定程度的消除來度量信息量的大小。他提出了一系列概念：（1）自信息量。在收到之前，收信者對信源發(fā)出的不確定性定義為信息符號(hào)的自信息量。即，其中為信源發(fā)出的概率。（2）信息熵。自信息量只能反映符號(hào)的不確定性，而信息熵可以用來度量信源X整體的不確定性，定義如下： H（X）=p()I（）+P

13、（）I（）+P（）I（） = -其中r為信源X所有可能的符號(hào)數(shù)，即用信源每發(fā)一個(gè)符號(hào)所提供的平均自信息量來定義信息熵。（3）條件熵。如果信源X與隨機(jī)變量Y不是相互獨(dú)立的，收信者收到信息Y。那么，用條件熵H（X/Y）來度量收信者在收到隨機(jī)變量Y之后，對隨機(jī)變量X仍然存在的不確定性。設(shè)X對應(yīng)信源符號(hào)，Y對應(yīng)信源符號(hào)，為當(dāng)Y為時(shí)X為的概率，則有： H（X/Y）= -（4）平均互信息量。用它來表示信號(hào)Y所能提供的關(guān)于X的信息良的大小，用I（X，Y）表示： H（X，Y）= H（X）-H（X/Y）信息論的這些基本概念，對決策樹來說是非常重要的，是決策樹算法的設(shè)計(jì)與實(shí)現(xiàn)基礎(chǔ)。2.1.3.決策樹的基本概念決策

14、樹是定義布爾函數(shù)的一種方法,其輸入是一組屬性描述的對象,輸出為yes/ no 決策。它代表一個(gè)假設(shè),可以寫成邏輯公式。其表達(dá)能力限于命題邏輯,該對象的任一個(gè)屬性的任一次測試均是一個(gè)命題。在命題邏輯范圍內(nèi),決策樹的表達(dá)能力是完全的。一棵決策樹可以代表一個(gè)決定訓(xùn)練實(shí)例集分類的決策過程,樹的每個(gè)結(jié)點(diǎn)對應(yīng)于一個(gè)屬性名或一個(gè)特定的測試,該測試在此結(jié)點(diǎn)根據(jù)測試的可能結(jié)果對訓(xùn)練實(shí)例集進(jìn)行劃分。劃分出的每個(gè)部分都對應(yīng)于相應(yīng)訓(xùn)練實(shí)例集子空間的一個(gè)分類子問題,該分類子問題可以由一棵決策樹來解決。因此,一棵決策樹可以看作是個(gè)對目標(biāo)分類的劃分和獲取策略。一棵決策樹的內(nèi)部結(jié)點(diǎn)是屬性或?qū)傩缘募希ㄓ址Q測試屬性），葉結(jié)點(diǎn)是

15、所要學(xué)習(xí)劃分的類。根據(jù)決策樹各種不同的屬性，可分為以下幾種：（1）決策樹的內(nèi)結(jié)點(diǎn)的測試屬性可能是單變量的，即每個(gè)內(nèi)結(jié)點(diǎn)只包含一個(gè)屬性。也可能是多變量的。（2）根據(jù)測試屬性的不同屬性值的個(gè)數(shù)，可能使得每個(gè)內(nèi)結(jié)點(diǎn)有兩個(gè)或多個(gè)分支。如果每個(gè)內(nèi)結(jié)點(diǎn)只有兩個(gè)分支則稱之為二叉決策樹。（3）每個(gè)屬性可能是值類型，也可能是枚舉類型。（4）分類結(jié)果既可能是兩類有可能是多類，如果只有兩類則稱為布爾決策樹。因?yàn)闆Q策樹有不同的等價(jià)表示形式，所以會(huì)有不同的算法來實(shí)現(xiàn)與決策樹學(xué)習(xí)相同的功能。例如：ID3、C4.5、CART、CHAID、SLIQ和SPRINT等等。2.2.幾種常見的決策樹算法的簡單介紹2.2.1.ID3

16、算法2.2.1.1.ID3 算法簡介上面講到?jīng)Q策樹學(xué)習(xí)是一種歸納學(xué)習(xí)方法,這里介紹決策樹學(xué)習(xí)的核心算法ID3 算法，ID3 算法是在所有可能的決策樹空間中一種自頂向下、貪婪的搜索方法。ID3 算法的關(guān)鍵是確定屬性表As中可對訓(xùn)練實(shí)例集Es進(jìn)行的最佳分類的屬性A ,即在樹的每一個(gè)節(jié)點(diǎn)上確定一個(gè)候選屬性,它的測試對訓(xùn)練例的分類最有利。ID3搜索的假設(shè)空間是可能的決策樹的集合,而ID3搜索目的是構(gòu)造與訓(xùn)練數(shù)據(jù)一致的一棵決策樹。ID3的搜索策略是爬山法,在構(gòu)造決策樹時(shí)從簡單到復(fù)雜,用信息贏取作為指導(dǎo)爬山法的評(píng)價(jià)函數(shù)。ID3是基于信息熵的決策樹分類算法。自從Quinlan描述和分析了ID3算法以來, 有

17、大量的學(xué)者圍繞該算法作了十分廣泛的研究。該算法是根據(jù)屬性集的取值選擇實(shí)例的類別。它的核心是在決策樹中各級(jí)結(jié)點(diǎn)上選擇屬性,用信息增益率作為屬性選擇標(biāo)準(zhǔn),使得在每一非葉結(jié)點(diǎn)進(jìn)行測試時(shí),能獲得關(guān)于被測試?yán)幼畲蟮念悇e信息。使用該屬性將例子集分成子集后,系統(tǒng)的熵值最小,期望該非葉結(jié)點(diǎn)到達(dá)各后代葉節(jié)點(diǎn)的平均路徑最短,使生成的決策樹平均深度較小,提高分類速度和準(zhǔn)確率。ID3 的基本原理如下:設(shè)E = F1 F2 Fn 是n 維有窮向量空間,其中是有窮離散符號(hào)集, E中的元素e = 叫做例子,其中, j = 1 ,2 , , n。設(shè)PE 和NE 是E 的F 兩個(gè)例子集,分別叫正例集和反例集。假設(shè)向量空間E中

18、的正例集PE和反例集NE 的大小分別為p和n ,ID3基于下列兩個(gè)假設(shè): (1)在向量空間E 上的一棵正確決策樹,對任意例子的分類概率同E 中的正、反例的概率一致;(2)一棵決策樹能對一例子做出正確類別判斷所需的信息量為:I（p,n）=如果以屬性A作為決策樹的根, A具有v個(gè)值(,) ,它將E分為v個(gè)子集(, ) ,假設(shè)中含有Pi個(gè)正例和個(gè)反例,子集的信息熵為I(Pi,) ,以屬性A為根分類后的信息熵為：因此,以A 為根的信息增益是Gain (A) = I (p,n) - E(A) 。ID3 選擇使Gain (A) 最大(即E(A) 最小)的屬性作為根結(jié)點(diǎn)。對的不同的取值對應(yīng)的E 的v個(gè)子集遞

19、歸調(diào)用上述過程,生成的子結(jié)點(diǎn),， 。ID3 的基本原理是基于兩類分類問題,但很容易擴(kuò)展到多類。設(shè)樣本集S 共有C類樣本,每類樣本數(shù)為pi ,( i = 1 ,2 ,3 , c) 。若以屬性A 作為決策樹的根, A 具有V 個(gè)值, ,它將E 分成V 個(gè)子集, ,假設(shè)中含有j類樣本的個(gè)數(shù)為,j = 1,2,c那么,子集的信息量是I()。 以A 為根分類的信息熵為: 選擇屬性使E( A) 最小,信息增益也將增大。理想的決策樹分成3種: (1)葉節(jié)點(diǎn)數(shù)最小, (2)葉節(jié)點(diǎn)深度最小; (3)葉節(jié)點(diǎn)數(shù)量最少且葉子結(jié)點(diǎn)深度最小。決策樹的好壞,不僅影響分類的效率,而且還影響分類的準(zhǔn)確率。因而許多學(xué)者致力于尋找

20、更優(yōu)的啟發(fā)式函數(shù)和評(píng)價(jià)函數(shù),洪家榮、Pei - Lei Tu等人分別證明了要找到這種最優(yōu)的決策樹是NP難題。因此人們?yōu)榱藢で筝^優(yōu)的解,不得不尋求各種啟發(fā)式的方法。有的采用基于屬性相關(guān)性的啟發(fā)式函數(shù);有的對生成的決策樹進(jìn)行剪枝處理;有的則擴(kuò)充決策樹,形成決策圖。如今普遍采用的是優(yōu)化算法,基本思想:首先用ID3選擇屬性F1,建立樹T1,左、右子樹的屬性分別為F2,F3,再以F2,F3為根,重建樹T2，T3;較T1,T2,T3的結(jié)點(diǎn)個(gè)數(shù),選擇結(jié)點(diǎn)最少的樹。對于選擇定樹的兒子結(jié)點(diǎn)采用同樣的方法遞歸建樹。盡管作者用一個(gè)實(shí)驗(yàn)證明能建立理想的決策樹,但算法有較大的弱點(diǎn):時(shí)間開銷太大,因?yàn)槊窟x擇一個(gè)新的屬性,

21、算法都需要建立3 棵決策樹,從中選優(yōu)。2.2.1.2.ID3 算法實(shí)例例子一：這里我們通過考察不同的人群購買手機(jī)的狀況為例,來展示ID3 算法的實(shí)際流程。此例假定要按是否買手機(jī)對一個(gè)集合進(jìn)行分類,該集合中用來描述人群的屬性有age、income、student和credit-rating。age的取值為youth、Middle-aged、old；Income的取值為high、medium和low；student的取值為no和yes；credit-rating的取值為fair和excellent。例子集中共有14個(gè)人,如表1 所示。在類別一欄,將正例即“買手機(jī)”的人用“Y”標(biāo)出,反例即“不買手機(jī)

22、”的人用“N”標(biāo)出。表1IDageincomestudentCredit-ratingClass1youthhighnofairN2youthhighnoexcellentN3Middle-agedhighnofairY4oldmediumnofairY5oldlowyesfairY6oldlowyesexcellentN7Middle-agedlowyesexcellentY8youthmediumnofairN9youthlowyesfairY10oldmediumyesfairY11youthmediumyesexcellentY12Middle-agedmediumnoexcellen

23、tY13Middle-agedhighyesfairY14oldmediumnoexcellentN首先利用公式I（p,n）=計(jì)算樣本分類所需要的期望信息：I（，）= I（9，5）=-=0.940，然后計(jì)算每個(gè)屬性的熵。從age屬性開始。需要觀察age的每個(gè)樣本值的Y和N的分布。對每個(gè)分布計(jì)算期望信息。對于age=“youth”： =2 =3 I（，）=0.971對于age=“middleaged” =4 =0 I（,）=0對于age=“old” =3 =2 I（，）=0.971如果樣本按age劃分，對一個(gè)給定的樣本分類所需的期望信息為：E（age）= I（，）+ I（,）+ I（，）=0.6

24、94計(jì)算其信息增益為：Gain（，）= I（，）- E（age）=0.246類似地，計(jì)算Gain（income）=0.029，Gain（student）=0.151和Gain（credit-rating）=0.048。由此可知age在屬性中的信息增益最高，故選它做為測試屬性。創(chuàng)建根結(jié)點(diǎn)，用age標(biāo)記，并對每個(gè)屬值得引出一個(gè)分支。依次類推可得出決策樹如下圖：這些例子一開始全部包含在根結(jié)點(diǎn)中,為了找出當(dāng)前的最佳劃分屬性,先須根據(jù)前述公式計(jì)算訓(xùn)練例集Es的熵值。則根節(jié)點(diǎn)的熵值為:生成如下決策樹分類規(guī)則： IF age=“youth” AND student = “no” THEN Class=“N”

25、IF age=“Middleaged” THEN Class=“Y”IF age=“youth” AND student = “yes” THEN Class=“Y”IF age=“old” AND credit-rating=“fair” THEN Class=“Y”IF age=“old” AND credit-rating=“excellent” THEN Class=“N”例子二：這里我們通過考察?？谀承W(xué)生的學(xué)習(xí)狀況為例,來展示ID3 算法的實(shí)際流程。此例假定要按某校學(xué)生學(xué)習(xí)成績好壞這個(gè)概念對一個(gè)集合進(jìn)行分類,該集合中用來描述學(xué)生的屬性有性格、父母教育程度和性別。性格的取值為外向、內(nèi)

26、向。父母教育程度取值為良好、中等和差。性別的取值為男生、女生。例子集中共有12 名學(xué)生,如表2所示。在類別一欄,將正例即“學(xué)習(xí)成績好”的學(xué)生用“好”標(biāo)出,反例即“學(xué)生成績差”的學(xué)生用“差”標(biāo)出。表2 某學(xué)校學(xué)生的例子集性格父母教育程度性別類別內(nèi)向外向外向內(nèi)向外向內(nèi)向外向外向外向內(nèi)向內(nèi)向內(nèi)向良良中差中良差差良中中差女生男生女生女生男生男生女生男生女生女生男生男生好好差差好好好差好差差差這些例子一開始全部包含在根結(jié)點(diǎn)中,為了找出當(dāng)前的最佳劃分屬性,先須根據(jù)信息論中的公式計(jì)算訓(xùn)練實(shí)例集Es的熵值。則根節(jié)點(diǎn)的熵值為: = 1下面分別計(jì)算例子集中各個(gè)屬性的信息贏取值。對屬性“性格”來說,分外向和內(nèi)向兩個(gè)

27、分支。當(dāng)v =“外向”時(shí),有4 名“外向”小學(xué)生是“學(xué)習(xí)成績好”的,有2 名“外向”小學(xué)生是“學(xué)習(xí)成績差”的。因此, 當(dāng)v =“內(nèi)向”時(shí),有2 名“內(nèi)向”小學(xué)生是“學(xué)習(xí)成績好”的,有4 名“內(nèi)向”小學(xué)生是“學(xué)習(xí)成績差”的。因此, 所以根據(jù)“性格”屬性來進(jìn)行例子集分類的信息贏取值為:Gain(Es,性格)=Entropy(Es)-Entropy(Esv,格)=同理,對“父母教育程度”來說:Gain(Es, 父母教育程度)=0.4591 ;對“性別”來說:Gain( Es,性別) = 0 。因?yàn)镚ain ( Es ,性別) Gain ( Es ,性格) Gain ( Es , 父母教育程度) 可以

28、看出以“父母教育程度”這個(gè)屬性進(jìn)行例子集分類的信息贏取值最大,于是“父母教育程度”就被選為用于劃分的屬性,得到如下圖所示的決策樹。按“父母教育程度”劃分后的決策樹現(xiàn)在必須根據(jù)所提供的信息進(jìn)一步分析“父母教育程度”為“中”或“差”的小學(xué)生的“學(xué)習(xí)成績好壞”,因此必須對“中”和“差”兩個(gè)分支的實(shí)例組成的例子集(共8個(gè)例子) 重復(fù)上述計(jì)算過程。這里簡化計(jì)算過程,算出:Gain(Es,性格)=0.3113 和Gain(Es,性別) =0.2045。因?yàn)镚ain ( Es ,性別) Gain ( Es ,性格) ,所以用屬性“性格”作第二步劃分,于是得到如下圖所示的決策樹。按“性格”作第二次劃分后的決策

29、樹現(xiàn)在只有“父母教育程度”為“中”和“差”的“外向”小學(xué)生還沒有明確類別,它們要用屬性“性別”來進(jìn)一步劃分。最終得到的決策樹如下圖所示。最終得到的決策樹IF 父母教育程度=“良” THEN 學(xué)習(xí)成績 =“好”IF 父母教育程度=“中”AND 性格=“內(nèi)向” THEN學(xué)習(xí)成績 =“差”IF 父母教育程度=“差”AND 性格=“內(nèi)向” THEN學(xué)習(xí)成績 =“差”IF 父母教育程度=“中”AND 性格=“外向”AND 性別=“女生” THEN學(xué)習(xí)成績 =“差”IF 父母教育程度=“中”AND 性格=“外向”AND 性別=“男生” THEN學(xué)習(xí)成績 =“好”IF 父母教育程度=“差”AND 性格=“外

30、向”AND 性別=“女生” THEN學(xué)習(xí)成績 =“好”IF 父母教育程度=“差”AND 性格=“外向”AND 性別=“男生” THEN學(xué)習(xí)成績 =“差”但是不能保證ID3算法對任何問題總能做出最佳選擇,只能說它在一般情況下能夠找出最優(yōu)決策樹。這是ID3算法的最大缺點(diǎn)。2.2.1.3.ID3 算法的優(yōu)缺點(diǎn)這里對ID3算法作一些總結(jié):ID3通過不斷的循環(huán)處理,逐步求精決策樹,直到找到一個(gè)完全正確的決策樹。ID3算法構(gòu)造的決策樹是從頂向下歸納形成了一組類似IF THEN的規(guī)則。其最原始的程序只是用來區(qū)分象棋中的走步,所以區(qū)分的類別只有兩種T或F ,其屬性值也是一些離散有限的值,而今ID3算法已發(fā)展到

31、允許多于兩個(gè)類別,而其屬性值可以是整數(shù)或?qū)崝?shù)。下面歸納總結(jié)出ID3算法的優(yōu)缺點(diǎn)如下:優(yōu)點(diǎn):搜索空間是完全的假設(shè)空間,目標(biāo)函數(shù)必在搜索空間中,不存在無解的危險(xiǎn);全盤使用訓(xùn)練數(shù)據(jù),而不是像候選剪除算法一個(gè)一個(gè)地考慮訓(xùn)練例。這樣做的優(yōu)點(diǎn)是可以利用全部訓(xùn)練例的統(tǒng)計(jì)性質(zhì)進(jìn)行決策,從而抵抗噪音。缺點(diǎn):搜索中只維持一個(gè)解,不能像候選剪除算法那樣返回所有可能的與練例集一致的假設(shè),并優(yōu)化地查詢新例以獲得收斂于目標(biāo)函數(shù)的解;其搜索無回溯它可能收斂于局部最優(yōu)解而丟失全局最優(yōu)解,因?yàn)橐粋€(gè)一個(gè)地考慮訓(xùn)練例,不容易象剪除算法那樣使用新例步進(jìn)式地改進(jìn)決策樹。2.2.1.4.ID3 算法的發(fā)展ID3算法在實(shí)際應(yīng)用中解決了許多

32、問題,對于非增量式學(xué)習(xí)任務(wù), ID3算法常常是建立決策樹的很好的選擇。但對于增量式學(xué)習(xí)任務(wù)來說,由于ID3不能增量地接受訓(xùn)練例,這就使得每增加一次實(shí)例都必須拋棄原有決策樹,重新構(gòu)造新的決策樹,造成了極大的開銷。于是ID3 算法被Quinlan1自己擴(kuò)充為C4.5法,C4.5算法每接受一個(gè)新的訓(xùn)練例就更新一次決策樹。在C4.5的決策樹中,每個(gè)結(jié)點(diǎn)都保存了可用于計(jì)算E值的屬性的信息,這些信息由屬性的每個(gè)取值所對應(yīng)的正例、反例計(jì)數(shù)組成。根據(jù)放在結(jié)點(diǎn)的信息,就可以判斷出哪個(gè)屬性的訓(xùn)練例集Es值最小,從而確定當(dāng)前用哪一個(gè)屬性來進(jìn)行劃分。C4.5算法使用了一個(gè)適合小數(shù)據(jù)量的方法:基于訓(xùn)練例自身的性能估計(jì)。

33、當(dāng)然訓(xùn)練例進(jìn)行估計(jì)很可能產(chǎn)生偏向于規(guī)則的結(jié)果,為了克服這一點(diǎn),C4.5算法采用了保守估計(jì)。它采用的具體方法是:計(jì)算規(guī)則對其使用的各個(gè)訓(xùn)練例分類的精度a ,然后計(jì)算這個(gè)精度的二項(xiàng)分布的標(biāo)準(zhǔn)差s ,最后對給定信任度(95 %)，取下界(a-1.96)為該規(guī)則的性能度量pa；在有大量數(shù)據(jù)的情況下,s接近于0,pa接近于a ；隨著數(shù)據(jù)量的減少,pa與a的差別將會(huì)增大。C4.5算法使用更復(fù)雜的方法是為屬性A 的各種取值賦以概率,具有未知屬性A 值的實(shí)例x 按概率值分為大小不等的碎片,沿相應(yīng)屬性A 值的分支向樹的下方分布,實(shí)例的碎片將用于計(jì)算信息贏取。這個(gè)實(shí)例碎片在學(xué)習(xí)后,還可以用來對屬性值不全的新實(shí)例進(jìn)

34、行分類。下面就C4.5算法的基本思想做簡要的概述。2.2.2.C4.5算法簡介C4.5算法是在ID3的基礎(chǔ)上改進(jìn)而成的，它繼承了ID3的全部優(yōu)點(diǎn)，更好地修正了ID3的剪枝算法并對高分支屬性、數(shù)值型屬性和含空值屬性地整理有了系統(tǒng)地描述。例如CN4.5中也采用“窗口”( Windows ) 的概念,先從所有的事例中選取一部分用做構(gòu)造決策樹,再利用剩余的事例測試決策樹并對它進(jìn)行調(diào)整。CN4.5算法能處理連續(xù)值類型的屬性,它還能對屬性的取值集合進(jìn)行等價(jià)類劃分,劃分在同一類的屬性值在屬性值判斷時(shí)將走到同一分支上。再加上CN4.5算法的思想簡單,實(shí)現(xiàn)高效,結(jié)果可靠,使CN4.5在歸納學(xué)習(xí)中的地位更加顯著。

35、但是CN 4.5算法也有如下不足之處:第一, CN4.5采用的是分而治之的策略,在構(gòu)造樹的內(nèi)部結(jié)點(diǎn)的時(shí)候是局部最優(yōu)的搜索方式。所以它所得到的最終結(jié)果盡管有很高的準(zhǔn)確性,仍然得不到全局最優(yōu)的結(jié)果。第二,在CN4.5評(píng)價(jià)決策最主要的依據(jù)是決策樹的錯(cuò)誤率,而對樹的深度,結(jié)點(diǎn)的個(gè)數(shù)等不進(jìn)行考慮,而樹平均深度直接對應(yīng)著決策樹的預(yù)測速度,樹的結(jié)點(diǎn)個(gè)數(shù)則代表樹的規(guī)模。第三,一邊構(gòu)造決策樹,一邊進(jìn)行評(píng)價(jià),決策樹構(gòu)造出來之后,很難再調(diào)整樹的結(jié)構(gòu)和內(nèi)容,決策樹性能的改善十分困難。第四, CN4.5在進(jìn)行屬性值分組時(shí)逐個(gè)試探,沒有一種使用啟發(fā)搜索的機(jī)制,分組時(shí)的效率較低。2.2.3.遺傳算法GA(Genetic A

36、lgorithm)遺傳算法是一種通用搜索算法。它通過模擬自然界進(jìn)化的過程來演化出解決問題的較優(yōu)方法。它把一些解決方案用一定的方式來表示,放在一起稱為群體(population) 。每一個(gè)方案的優(yōu)劣程度即為適應(yīng)性(fit2ness),根據(jù)自然界進(jìn)化的“優(yōu)勝劣汰”的原則,逐步產(chǎn)生出它們的后代,使后代具有更強(qiáng)的適應(yīng)性。這樣不斷演化下去,就能得到更優(yōu)的解決方案。它具有思想簡明、健壯性好等特點(diǎn)。在工農(nóng)業(yè)、經(jīng)濟(jì)政治、科研方面應(yīng)用極為廣泛。在計(jì)算機(jī)科學(xué)領(lǐng)域中的機(jī)器學(xué)習(xí)領(lǐng)域更是大有用武之地。群體搜索策略和個(gè)體之間的信息交換是遺傳算法的兩大特點(diǎn),主要表現(xiàn)在全局最優(yōu)性和潛在的并行性。CN4.5在構(gòu)造決策樹時(shí)并不一

37、定得到最優(yōu)的決策樹,那么是不是能用遺傳算法的思想能夠得到解決呢,回答是肯定的。雖然遺傳算法的進(jìn)發(fā)結(jié)果并不能保證得到理論意義上的最佳的決策樹,但是它提供了一種試探的過程。由于適者生存的特點(diǎn),使得適應(yīng)性較優(yōu)的決策樹能盡量保留,又由于它提供了對決策樹的調(diào)整和重新組合的機(jī)制,使得有更優(yōu)適應(yīng)性的決策樹在進(jìn)發(fā)過程中出現(xiàn)。那么如何應(yīng)用遺傳算法,如何基于決策樹的結(jié)構(gòu)和性質(zhì)定義遺傳算子呢?遺傳算子主要有三種:復(fù)制(reproduction) 、重組(crossover) 、算子和變異(mutation) 算子。一般的算子都是對特征串進(jìn)行操作的。針對決策樹的結(jié)構(gòu)和特性,我們定義遺傳算子:首先定義適應(yīng)函數(shù)(fitn

38、ess function) 。遺傳算法是一個(gè)探索過程,它對樹的評(píng)價(jià)是在樹完全作成以后進(jìn)行的,可以將樹的深度、結(jié)點(diǎn)數(shù)等因素都考慮在內(nèi)。復(fù)制算子的定義與常用的復(fù)制算子的定義一致。重組算子的定義就要用到?jīng)Q策樹結(jié)構(gòu)特點(diǎn)。我們有以下幾種重組方式: (1) 用后代結(jié)點(diǎn)代替祖先結(jié)點(diǎn),類似于書的剪枝操作。(2) 同一棵樹的兩個(gè)結(jié)點(diǎn)互相交換。(3) 兩個(gè)樹之間結(jié)點(diǎn)交換,這里所說的結(jié)點(diǎn)交換就是交換以這些結(jié)點(diǎn)為根的子樹。變異是產(chǎn)生全局最優(yōu)的重要原因,盡管大多數(shù)的變異不能產(chǎn)生良好的效果,對于決策樹,我們定義的變異算子是改變樹的結(jié)構(gòu)或者改變樹中結(jié)點(diǎn)內(nèi)的信息。針對內(nèi)部結(jié)點(diǎn)和葉節(jié)點(diǎn),屬性值的分組與否這些不同情況,變異的處理

39、是不一樣的。對于內(nèi)部結(jié)點(diǎn)內(nèi),變異操作可能產(chǎn)生下面的結(jié)果:(1) 改變結(jié)點(diǎn)上判斷的屬性。(2) 改變屬性值的分組情況。(3) 改變該結(jié)點(diǎn)下的子樹的分支情況,改變屬性值與分支子樹的對應(yīng)。(4) 改變該結(jié)點(diǎn)的分支數(shù)。這樣經(jīng)過重組、變異算子運(yùn)算得到的新的決策樹需要進(jìn)行結(jié)構(gòu)上的完整性和一致性處理。調(diào)整變異結(jié)點(diǎn)及其子結(jié)點(diǎn)的樹結(jié)構(gòu)使之為一棵完整的正確的決策樹;去除從樹根到葉節(jié)點(diǎn)路徑上重復(fù)的屬性判斷等。決策樹的構(gòu)造分為以下幾步:(1) 第一代群體的產(chǎn)生；(2) 產(chǎn)生下一代；(3) 產(chǎn)生最優(yōu)決策樹。2.3.決策樹的評(píng)價(jià)標(biāo)準(zhǔn)1以上討論了一些決策樹構(gòu)造算法，并且對這些算法的優(yōu)缺點(diǎn)進(jìn)行了分析。下面，給出評(píng)價(jià)決策樹的一

40、些標(biāo)準(zhǔn)。1過學(xué)習(xí)在由決策樹學(xué)習(xí)的過程中，我們必須在一組假設(shè)中選擇一個(gè)，使得它與訓(xùn)練實(shí)例集相匹配。我們已經(jīng)看到不可能在沒有任何偏置（bias）的情況下學(xué)習(xí)。如果預(yù)先字段所要學(xué)習(xí)的函數(shù)屬于整個(gè)假設(shè)空間中一個(gè)很小子集，那么即使在訓(xùn)練實(shí)例不完整的情況下，我們也有可能從訓(xùn)練實(shí)例集喪鐘學(xué)習(xí)有用的假設(shè)，來使得它能夠?qū)ξ粗膶?shí)例進(jìn)行正確分類。即使如此，我們還是希望有一個(gè)大的訓(xùn)練實(shí)例集。因?yàn)橛?xùn)練實(shí)例集越大，關(guān)于分類的信息越多。在這種情況下，即使我們隨機(jī)地從與訓(xùn)練實(shí)例集相一致的假設(shè)集中選擇一個(gè)，它也能對未知實(shí)例的分類進(jìn)行預(yù)測。相反，即使在有偏置的情況下，如果訓(xùn)練實(shí)例集與整個(gè)假設(shè)空間相比過小，仍有過多的與訓(xùn)練實(shí)例相

41、一致的假設(shè)供我們選擇，我們做出假設(shè)的泛化能力將很差。當(dāng)有過多的假設(shè)與訓(xùn)練實(shí)例集相一致的時(shí)候，則成為過學(xué)習(xí)。過學(xué)習(xí)是所有機(jī)器學(xué)習(xí)都要考慮的問題。過學(xué)習(xí)將導(dǎo)致我們所做出的假設(shè)泛化能力過差。所以，也可以如下定義過學(xué)習(xí)。假設(shè)h對所有的訓(xùn)練實(shí)例分類的錯(cuò)誤率為，對整個(gè)實(shí)例空間D分類的錯(cuò)誤率為。如果存在另一個(gè)假設(shè)使得：并且 一般將成為重替換（resubstitution）錯(cuò)誤率，在本書中將其簡記為r錯(cuò)誤率。而在此一般將在測試集中的錯(cuò)誤率成為錯(cuò)誤。Cohen和Jensen提出了一個(gè)有用的理論來解釋為何會(huì)出現(xiàn)過學(xué)習(xí)的情況。他們提出，當(dāng)一個(gè)算法過高估計(jì)增加樹的復(fù)雜性對于分類的正確性的貢獻(xiàn)，那么就會(huì)出現(xiàn)過學(xué)習(xí)現(xiàn)象。

42、主要有三種原因使得算法過高估計(jì)這些貢獻(xiàn)：（1）檢測模型的數(shù)目：算法檢測模型數(shù)目與出現(xiàn)過學(xué)習(xí)的可能性是正相關(guān)的。（2）不同的正確性估計(jì)：小的訓(xùn)練實(shí)例集更不可能代表數(shù)據(jù)的內(nèi)在分布，更有可能產(chǎn)生過學(xué)習(xí)的現(xiàn)象。而大一些的訓(xùn)練實(shí)例集產(chǎn)生過學(xué)習(xí)問題的可能性更小。（3）選擇最優(yōu)樹：通過極大化某個(gè)特定評(píng)價(jià)函數(shù)來選擇最優(yōu)決策樹增加了過學(xué)習(xí)的可能性。Cohen和Jensen利用事后剪枝的方法驗(yàn)證了他們的理論。2有效性最為直接的估計(jì)一棵決策樹在測試實(shí)例集合上的性能的方法是，將它在測試實(shí)例集合上進(jìn)行實(shí)際測試，這樣就可以選中在測試集合中表現(xiàn)最好的一棵決策樹。但是這種方法等價(jià)于在測試實(shí)例集中訓(xùn)練決策樹，這在大多數(shù)情況下是

43、不現(xiàn)實(shí)的。所以一般并不采用這種方法，而是采取用訓(xùn)練實(shí)例集本身來估計(jì)訓(xùn)練算法的有效性。一種最簡便的方法是用訓(xùn)練實(shí)例集的一部分（例如3/4的訓(xùn)練實(shí)例）對決策樹進(jìn)行訓(xùn)練，而用另外一部分（例如1/4的訓(xùn)練實(shí)例）對決策樹檢測其有效性。但是，這樣做將會(huì)減小訓(xùn)練實(shí)例空間，而增大過學(xué)習(xí)的可能性，所以這種方法也不可取。3交叉有效性在此方法中，我們將訓(xùn)練實(shí)例集T分為互不相交且大小相等的k個(gè)子集，.。對于任意子集，用T-訓(xùn)練決策樹，之后用對生成的決策樹進(jìn)行測試，得到錯(cuò)誤率，然后估計(jì)整個(gè)算法的錯(cuò)誤率：e=可以看出隨著k的增加，所生成的樹的數(shù)目也隨之增加，算法的復(fù)雜度也會(huì)變大。4余一有效性（leave-one-out

44、validation）這種有效性的度量與交叉有效性類似，不同之處在于將每個(gè)的大小定為1。假設(shè)|T|=n，則錯(cuò)誤率為：e=顯然，這種有效性測量算法的復(fù)雜度過高，但是它的準(zhǔn)確程度也是最高的。5決策樹的復(fù)雜程度決策樹的復(fù)雜程度也是度量決策樹學(xué)習(xí)效果的一個(gè)重要標(biāo)準(zhǔn)。對于給定的描述語言，如果決策樹是單變量（univariate）的，那么決策樹的復(fù)雜程度主要由樹的結(jié)點(diǎn)個(gè)數(shù)決定；如果是多變量（multivariare）的，則主要是由結(jié)點(diǎn)中屬性的總個(gè)數(shù)決定。2.4.決策樹的進(jìn)展與發(fā)展方向2.4.1.數(shù)據(jù)挖掘中決策樹算法的主要進(jìn)展傳統(tǒng)的決策樹算法主要是針對小數(shù)據(jù)集的,大都要求訓(xùn)練集常駐內(nèi)存,這使得在處理數(shù)據(jù)挖掘

45、任務(wù)時(shí),傳統(tǒng)決策樹算法在可伸縮性、精度和效率方面受到了很大的限制。而在實(shí)際的數(shù)據(jù)挖掘應(yīng)用中我們面臨的數(shù)據(jù)集往往是容量巨大的數(shù)據(jù)庫或者數(shù)據(jù)倉庫,在構(gòu)造決策樹時(shí)需要將龐大的數(shù)據(jù)在主存和緩存中不停的導(dǎo)入導(dǎo)出,使得運(yùn)算效率大大降低。針對以上問題,許多學(xué)者提出了處理大型數(shù)據(jù)集的決策樹算法。其中主要在以下四個(gè)方面的應(yīng)用：1、數(shù)據(jù)預(yù)處理；2、抽樣方法；3、數(shù)據(jù)的重構(gòu)；4、結(jié)合上述的遺傳算法等其他算法。2.4.2.決策樹技術(shù)面臨的挑戰(zhàn)及目前研究方向目前決策樹技術(shù)的主要研究方向8有以下幾點(diǎn):1 決策樹算法的并行性研究2 尋找新的構(gòu)造決策樹的方法3 尋找更好的簡化決策樹的方法4 研究產(chǎn)生決策樹的訓(xùn)練和檢驗(yàn)數(shù)據(jù)的大

46、小及特性與決策樹特性之間的關(guān)系5 不確定環(huán)境下決策樹研究6 將決策樹用于多智能體控制并不多見7 決策樹時(shí)間復(fù)雜度與準(zhǔn)確性之間的矛盾8 決策樹技術(shù)的軟件實(shí)現(xiàn)3.關(guān)于決策樹算法的改進(jìn)由以上討論可知：ID3算法存在種種缺陷，如：算法的計(jì)算時(shí)間是例子個(gè)數(shù)、特征個(gè)數(shù)、節(jié)點(diǎn)個(gè)數(shù)之積的線性函數(shù)。另外大量實(shí)驗(yàn)證明,ID3算法在預(yù)測正確率和效果上是令人滿意的。用互信息作為特征選擇量,要求訓(xùn)練例子集中的正、反例比例應(yīng)與實(shí)際領(lǐng)域里正、反例比例相同。但在一般情況下不能保證相同,因而計(jì)算訓(xùn)練集的互信息就有偏差?；バ畔⒌挠?jì)算依賴于特征值數(shù)目較多的特征,這樣不太合理。另外ID3在建樹時(shí),每個(gè)節(jié)點(diǎn)僅含一個(gè)特征,特征間的相關(guān)性

47、強(qiáng)調(diào)不夠。下面針對ID3 算法的第二個(gè)不足之處,提出一些決策樹改進(jìn)意見。3.1.基于樣本離散度6的特征選擇方法3.1.1.基本概念1樣本均值 （1）表示第i類在第j維特征處的樣本均值。其中,Si表示第i類總的樣本數(shù), 表示第i類第k個(gè)樣本在第j維特征處的取值。2樣本歸一化 樣本歸一化就是將屬性取值范圍投影到一個(gè)特定的范圍之內(nèi),以消除數(shù)值型屬性因大小不一而造成挖掘結(jié)果的偏差。對于基于距離計(jì)算的挖掘,數(shù)值歸一化可以幫助消除因?qū)傩匀≈捣秶煌绊懲诰蚪Y(jié)果的公正性。我們按照下式對離散的數(shù)據(jù)進(jìn)行歸一化處理,歸一化后的結(jié)果將限制在0 ,1 范圍之內(nèi)。 （2）其中為第j維某個(gè)數(shù)據(jù)的歸一化值；為第j維該數(shù)據(jù)

48、的實(shí)際值；為第j維數(shù)據(jù)的最小值；為第j維數(shù)據(jù)的最大值。連續(xù)數(shù)據(jù)的歸一化處理,首先應(yīng)該對數(shù)據(jù)進(jìn)行離散化,（有關(guān)連續(xù)數(shù)據(jù)離散化處理方法這里暫時(shí)不做介紹,請讀者參考上述決策樹算法的研究中的相關(guān)內(nèi)容），然后再進(jìn)行數(shù)據(jù)的歸一化。 3樣本總類內(nèi)離散度離散度的定義:一個(gè)在d維空間由N個(gè)點(diǎn)組成的聚類,其散布的程度可以用離散度來衡量。離散度的計(jì)算和我們規(guī)定的中心點(diǎn)有關(guān)。設(shè)是d維空間中所選的中心點(diǎn),從聚類的N個(gè)點(diǎn)中取出d個(gè)點(diǎn),以為引點(diǎn),作一個(gè)超平行四邊形。對所有N中的d個(gè)點(diǎn)求出相應(yīng)的個(gè)超平行四邊形的體積平方和對N 個(gè)點(diǎn)的均值,就是該聚類對于中心點(diǎn)的離散度。假使取聚類的均值點(diǎn)作為引點(diǎn),則離散度為：S = |C| （

49、3）式中C 是聚類的協(xié)方差矩陣,即離散度矩陣S?？傠x散度ST 定義為： （4）根據(jù)離散度的概念,推導(dǎo)出樣本類內(nèi)離散度定義:樣本與樣本均值的方差,若考慮先驗(yàn)概率,可以定義如下： （5）表示第i類的先驗(yàn)概率,即,S表示訓(xùn)練集的總的樣本數(shù)。4歸一化后的樣本分布設(shè)樣本各維數(shù)據(jù)已經(jīng)歸一化到0 ,1 區(qū)間,則01,將所有類在第j 維的均值按從小到大的升序排列,記為： = （6）理想情況下的特征分布應(yīng)當(dāng)為，并且任意兩個(gè)相鄰的均值間的距離為： （7）由于所提取的特征的均值并非完全理想分布,因此,我們定義一個(gè)函數(shù)來度量實(shí)際分布與理想分布之間的距離。 （8）越小，越接近于,即各均值點(diǎn)在0 ,1 區(qū)間越接近理想分布

50、。 5距離函數(shù)定義一個(gè)距離函數(shù),希望投影后,各類樣本盡可能分得開些,即希望越小越好；同時(shí)希望各類樣本內(nèi)部盡量密集,即希望類內(nèi)離散度越小越好. 由式（5）和（8）定義距離函數(shù)。 總之,希望 越小越好,這樣特征越理想. 因此,在式(6) 中選擇一個(gè)較小的 值所對應(yīng)的一個(gè)特征作為形成決策樹的分類特征。3.1.2.基于離散度的改進(jìn)算法根據(jù)上述特征選擇方法,在ID3算法的基礎(chǔ)上,提出一種改進(jìn)的決策樹建樹算法,算法步驟如下:1)將訓(xùn)練集窗口中的全部數(shù)據(jù),選擇一種歸一化方法,歸一化到0 ,1 區(qū)間,形成訓(xùn)練集D。2)對訓(xùn)練集D ,利用上述特征選擇方法,利用式(5)、(8)、(9)求出, ,。3)選擇較小的值

51、所對應(yīng)的那一個(gè)特征作為分類特征,對數(shù)據(jù)集D 進(jìn)行分割,取幾個(gè)值就得幾個(gè)子集。4)對不含同一類樣本的子集,遞歸調(diào)用建樹算法。5)若各子集中的樣本為同一類樣本,則對應(yīng)分枝為葉子節(jié)點(diǎn),作相應(yīng)的類標(biāo)記,返回調(diào)用處。3.1.3.分析與比較此算法是根據(jù)離散數(shù)學(xué)的基礎(chǔ)知識(shí)來討論實(shí)現(xiàn)的，與ID3的利用的信息論知識(shí)一樣含概了大量的數(shù)學(xué)公式，在第3.2節(jié)中即將討論的基于概率論的算法也用是一樣。利用數(shù)學(xué)公式計(jì)算并構(gòu)建決策樹是眾多決策樹算法中的優(yōu)先選擇。菏澤學(xué)院計(jì)算機(jī)與信息工程學(xué)系的郭玉濱講師6已經(jīng)證明基于離散度的改進(jìn)算法有以下幾點(diǎn)好處：（1）基于離散度的改進(jìn)算法CPU的耗時(shí)遠(yuǎn)小于ID3的CPU耗時(shí)。（2）分類的錯(cuò)誤

52、率:這種基于離散度的改進(jìn)算法分類的錯(cuò)誤率要低于ID3算法分類的錯(cuò)誤率。3.1.4.小結(jié)基于離散度的改進(jìn)算法的幾個(gè)問題：（1）建樹步驟1中：如何將訓(xùn)練集窗口中的全部數(shù)據(jù)通過選擇一種歸一化方法,歸一化到0 ,1區(qū)間,形成訓(xùn)練集D。在眾多的歸一化方法中找到一種合適的方式是很耗費(fèi)的事，如果事先為計(jì)算機(jī)選擇好歸一化方法可以減輕計(jì)算機(jī)的負(fù)擔(dān)，但這卻給設(shè)計(jì)者帶來了負(fù)擔(dān)。（2）建樹步驟1中：要將歸一化后的數(shù)據(jù)進(jìn)行從小到大的升序排序，這又要選擇一種排序方法。在排序算法中最好情況下就是快速排序算法，其時(shí)間復(fù)雜度為：O（nlogn）。在不知情的情況下設(shè)計(jì)者要對眾多的排序算法進(jìn)行研究以求最快。（3）建樹步驟2中：對訓(xùn)

53、練集D ,要利用式(5)、(8)、(9)等三個(gè)公式來求出每一個(gè)訓(xùn)練實(shí)例的距離函數(shù)。這又是一項(xiàng)復(fù)雜的計(jì)算。（4）建樹步驟3中：若要選擇距離函數(shù)最小的訓(xùn)練實(shí)例就要進(jìn)行排序。這個(gè)雖然可以用上面問題（2）中的排序算法解決。但也需要花費(fèi)計(jì)算機(jī)的時(shí)間來做。（5）循環(huán)遞歸調(diào)用也需要大量的時(shí)間。3.2.利用條件概率的思想來改進(jìn)決策樹算法 數(shù)理統(tǒng)計(jì)論和條件概率在計(jì)算機(jī)行業(yè)是一門基礎(chǔ)課程，相信大家都學(xué)過這里不做介紹。下面的算法主要是運(yùn)用數(shù)理統(tǒng)計(jì)論和條件概率的基本概念來勾畫出ID3的改進(jìn)算法的。3.2.1.算法的理論基礎(chǔ)與基本思想借用概率統(tǒng)計(jì)知識(shí)并由此延伸出以下定義:定義:設(shè)A、B是事件,稱P(B|A)為事件A 發(fā)生時(shí)事件B會(huì)發(fā)生的條件概率,并稱這個(gè)條件概率P(B|A)為訓(xùn)練實(shí)例集A發(fā)生后,事件B對訓(xùn)練集中某例別的影響度。P(B|A) = 對于實(shí)例集中的各個(gè)屬性,首先計(jì)算所有屬性值的影響度,然后進(jìn)行比較,可以知道影響度越大的屬性值相對應(yīng)的屬性提供給分類的信息量就越大,依次比較,就可以確定屬性對分類的影響程度大小,因此可以根據(jù)此大小來構(gòu)造決策樹的生成算法。3.2.2.舉例分析從前面的理論分析知,條件概率決策樹算法是直接把實(shí)例各屬性與類別結(jié)果相聯(lián)系,計(jì)算在分類為某例條件下,屬性不同取值對分類條件的概率,通過比較概率的大小