數據挖掘決策樹算法的研究與改進

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

2、保留并向國家有關部門或機構送交畢業(yè)論文（設計）的復印件和磁盤，允許畢業(yè)論文（設計）被查閱和借閱。本人授權海南師范大學可以將本畢業(yè)論文（設計）的全部或部分內容編入有關數據庫進行檢索，可以采用影印、縮印或其他復印手段保存、匯編畢業(yè)論文（設計）。論文（設計）作者簽名： 日期：2007年5月21日指 導 教 師 簽 名： 日期： 目錄1.引言12.決策樹算法的研究22.1.基本定義22.1.1.歸納學習的基本概念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.決策樹的評價標準1132.4.決策樹的進展與發(fā)展方向152.4.1.數據挖掘中決策樹算法的主要進展152.4.2.決策樹技術面臨的挑戰(zhàn)及目前研究方向153.關于決策樹算法的改進153.1.基于樣本離散度6的特征選擇方法163.1.1.基本概念163.1.2.基于離散度的改進算法173.1.3.分析與比較183.1.4.小結183.2.利用條件概率的思想來改進決策樹算法183.2.1.算法的理論基礎與基本思想193.2.2.舉例分析193.2.3.分析與比較273.2.4.小結274.總結285.結束語286.致謝28參考文獻29挖掘決策樹算法的研究與改

4、進作者： 指導老師：（海南師范大學，?？冢┱?要：在大量信息展現給人們的時候，“知識爆炸”給人們帶來了極大的困擾，如何有效的利用數據成為人們事業(yè)成敗的關鍵。本論文主要對決策樹的常見算法做初步的研究與探討，并給出決策樹的評價標準。并在此基礎上利用最新的決策樹算法思想由本人設計實例集驗證相關文獻中筆者的思想，最后提出自己一點意見和看法。關鍵詞：數據挖掘；決策樹；研究；改進 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.引言隨著現代信息技術的飛速發(fā)展，在全球范圍內掀起了信息化（Information）浪潮。信息產生的渠道多而且寬廣，更新的頻率日益加快，各行業(yè)均產生了大量的信息。面對大量

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

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

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

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

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

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

14、樹是定義布爾函數的一種方法,其輸入是一組屬性描述的對象,輸出為yes/ no 決策。它代表一個假設,可以寫成邏輯公式。其表達能力限于命題邏輯,該對象的任一個屬性的任一次測試均是一個命題。在命題邏輯范圍內,決策樹的表達能力是完全的。一棵決策樹可以代表一個決定訓練實例集分類的決策過程,樹的每個結點對應于一個屬性名或一個特定的測試,該測試在此結點根據測試的可能結果對訓練實例集進行劃分。劃分出的每個部分都對應于相應訓練實例集子空間的一個分類子問題,該分類子問題可以由一棵決策樹來解決。因此,一棵決策樹可以看作是個對目標分類的劃分和獲取策略。一棵決策樹的內部結點是屬性或屬性的集合（又稱測試屬性），葉結點是

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

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

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

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

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

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

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

22、”的人用“N”標出。表1IDageincomestudentCredit-ratingClass1youthhighnofairN2youthhighnoexcellentN3Middle-agedhighnofairY4oldmediumnofairY5oldlowyesfairY6oldlowyesexcellentN7Middle-agedlowyesexcellentY8youthmediumnofairN9youthlowyesfairY10oldmediumyesfairY11youthmediumyesexcellentY12Middle-agedmediumnoexcellen

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

24、94計算其信息增益為：Gain（，）= I（，）- E（age）=0.246類似地，計算Gain（income）=0.029，Gain（student）=0.151和Gain（credit-rating）=0.048。由此可知age在屬性中的信息增益最高，故選它做為測試屬性。創(chuàng)建根結點，用age標記，并對每個屬值得引出一個分支。依次類推可得出決策樹如下圖：這些例子一開始全部包含在根結點中,為了找出當前的最佳劃分屬性,先須根據前述公式計算訓練例集Es的熵值。則根節(jié)點的熵值為:生成如下決策樹分類規(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”例子二：這里我們通過考察海口某校學生的學習狀況為例,來展示ID3 算法的實際流程。此例假定要按某校學生學習成績好壞這個概念對一個集合進行分類,該集合中用來描述學生的屬性有性格、父母教育程度和性別。性格的取值為外向、內

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

27、分支。當v =“外向”時,有4 名“外向”小學生是“學習成績好”的,有2 名“外向”小學生是“學習成績差”的。因此, 當v =“內向”時,有2 名“內向”小學生是“學習成績好”的,有4 名“內向”小學生是“學習成績差”的。因此, 所以根據“性格”屬性來進行例子集分類的信息贏取值為:Gain(Es,性格)=Entropy(Es)-Entropy(Esv,格)=同理,對“父母教育程度”來說:Gain(Es, 父母教育程度)=0.4591 ;對“性別”來說:Gain( Es,性別) = 0 。因為Gain ( Es ,性別) Gain ( Es ,性格) Gain ( Es , 父母教育程度) 可以

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

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

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

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

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

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

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

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

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

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

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

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

40、些標準。1過學習在由決策樹學習的過程中，我們必須在一組假設中選擇一個，使得它與訓練實例集相匹配。我們已經看到不可能在沒有任何偏置（bias）的情況下學習。如果預先字段所要學習的函數屬于整個假設空間中一個很小子集，那么即使在訓練實例不完整的情況下，我們也有可能從訓練實例集喪鐘學習有用的假設，來使得它能夠對未知的實例進行正確分類。即使如此，我們還是希望有一個大的訓練實例集。因為訓練實例集越大，關于分類的信息越多。在這種情況下，即使我們隨機地從與訓練實例集相一致的假設集中選擇一個，它也能對未知實例的分類進行預測。相反，即使在有偏置的情況下，如果訓練實例集與整個假設空間相比過小，仍有過多的與訓練實例相

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

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

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

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

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

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

47、強調不夠。下面針對ID3 算法的第二個不足之處,提出一些決策樹改進意見。3.1.基于樣本離散度6的特征選擇方法3.1.1.基本概念1樣本均值 （1）表示第i類在第j維特征處的樣本均值。其中,Si表示第i類總的樣本數, 表示第i類第k個樣本在第j維特征處的取值。2樣本歸一化 樣本歸一化就是將屬性取值范圍投影到一個特定的范圍之內,以消除數值型屬性因大小不一而造成挖掘結果的偏差。對于基于距離計算的挖掘,數值歸一化可以幫助消除因屬性取值范圍不同而影響挖掘結果的公正性。我們按照下式對離散的數據進行歸一化處理,歸一化后的結果將限制在0 ,1 范圍之內。 （2）其中為第j維某個數據的歸一化值；為第j維該數據

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

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

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

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

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

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