1、精選優質文檔-傾情為你奉上基于信息增益的決策樹摘 要本文深入研究了ID3算法的理論基礎及構建決策樹的過程等知識。Quinlan提出的ID3算法雖然經典,但也有美中不足之處。本文使用修正參數修正信息增益，克服了ID3算法偏向于選擇取值較多的屬性這一缺點(即多值偏向問題)，對連續值的屬性進行離散化，解決了連續屬性的處理問題，通過有未知值的樣本是按照已知值的相對頻率隨機分布的思想，可以處理缺少屬性值的樣本。描述了通過改進的ID3算法生成決策樹的具體步驟，將改進算法應用到了客戶關系管理系統中的客戶流失分析問題當中。通過對實驗結果的分析比較，得到改進算法與原ID3算法相比具有更高的預測準確率，表明了該算

2、法的有效性。關鍵詞：ID3算法；決策樹；信息增益；多值偏向Decision Tree based on the Information Gain TheoryAbstractFirstly, theoretical basis and the process of building decision tree of ID3 algorithm are further researched. The ID3 algorithm which was presented by Quinlan is not only most famous, but also there are some drawb

3、acks. This algorithm correct the information gain by using a modified parameter and overcome the disadvantage that bias to select the attribute has more value (namely multi-value bias) and the discrete of continuous properties to solve the problem of the continuous attributesAs for the idea that a s

4、ample of unknown value is in accordance with the known values of the relative frequency of random，It can deal with the missing attribute values of the sampleLast described the steps that how to generate decision tree by the modified ID3 algorithmThe improved algorithm is applied to the analysis of c

5、ustomer lost in the customer relationship management systemThrough the comparison of the experimental results，the improved algorithm has a higher forecast accuracy than the original ID3 algorithmFinally, the feasibility of the method is validated by practical application.Keywords：ID3 algorithm；Decis

6、ion tree；Information gain； Multi-value bias0 引言近年來，數據挖掘作為一種能發現海量數據中潛在有用信息的數據分析方法和技術，已在銀行、證券、房地產、教育等行業領域得到了廣泛應用，為人們獲取有價值的信息提供了強有力手段。 分類是數據挖掘技術中最常用的方法之一，而決策樹分類以其速度快、精度高、直觀易懂和生成模式簡單等諸多優點而倍受青睞，已在數據挖掘領域中有著不可替代的作用和地位。決策樹算法作為數據挖掘中一種簡單、實用而有效的快速分類算法，其本質上是一種以實例為基礎的歸納學習，它主要著眼于如何從一組無次序、無規則的事例中推理出以決策樹表示的分類規則。ID3

7、算法作為最具影響力的一種決策樹構造算法是由QuinLan J R于1986年提出，其后很多專家學者對其進行了深入的研究。本文從改進和簡化的角度對ID3算法進行了一定程度，針對ID3算法的缺點及不足，提出了一種基于ID3算法的改進算法。基于該改進算法將極大的提高預測的準確率，具有較高的實用性和有效性。1 決策樹簡介決策樹(Decision Tree)是一種有向、無環圖(Directed Acyclic Graphics，簡稱DAG)。決策樹方法是利用信息論中的信息增益尋找數據庫中具有最大信息量的屬性字段，建立決策樹的一個結點，再根據該屬性字段的不同取值建立樹的分支，再在每個分支子集中重復建立樹的

8、下層結點和分支的一個過程。構造決策樹的具體過程為：首先尋找初始分裂整個訓練集作為產生決策樹的集合，訓練集每個記錄必須是已經分好類的，以決定哪個屬性域(Field)作為目前最好的分類指標一般的做法是窮盡所有的屬性域，對每個屬性域分裂的好壞做出量化，計算出最好的一個分裂。量化的標準是計算每個分裂的多樣性(Diversity)指標。其次，重復第一步，直至每個葉節點內的記錄都屬于同一類且增長到一棵完整的樹。如圖1所示 。圖1：決策樹構造和優化過程2 ID3算法2.1 ID3算法描述ID3算法是由Quinlan提出的一種歸納學習算法，它可以從一個訓練例子集合中歸納出知識，抽取出的知識以決策樹的形式表示。

9、該算法的核心用信息增益(即信息論中的互信息)作為屬性的選擇標準，以使得在對每一個非葉結點進行測試時，能獲得關于被測試記錄最大的類別信息。ID3總是選擇具有最高信息增益(或最大熵壓縮)的屬性作為當前節點的測試屬性具體方法是：檢測所有的屬性，選擇信息增益最大的屬性產生決策樹結點，由該屬性的不同取值建立分支，再對各分支的子集遞歸調用該方法建立決策樹結點的分支，直到所有子集僅包含同一類別的數據為止，最后得到一棵決策樹，它可以用來對新的樣本進行分類。信息增益是基于信息論中嫡的概念。熵是對事件對應的在信息論中，熵表示的是不確定性的量度。由信息論的創始人Shannon在著作通信的數學理論中提出、建立在概率統

10、計模型上的信息度量。他把信息定義為“用來消除不確定性的東西”。 設S是s個訓練數據樣本的集合。假定類標號屬性具有m個不同值，定義m個不同類Ci，i=1，m，si是類Ci中的樣本數。一個給定的樣本分類所需的期望信息由下式給出：其中：pi是任意樣本屬于Ci的概率，一般用sis來估計。注意，對數函數以2為底，其原因是信息用二進制編碼。設屬性A具有v個不同值a1，a2，an，可以用屬性A將S劃分為v個子集S1，S2 ，Sv，Sj中的樣本在屬性A上具有相同的值aj，j=1，2，v，sij是子集Sj中類Ci的樣本數，由A劃分成子集的期望信息由下式給出：其中：充當第j個子集的權，并且等于子集(即A值為aj

11、)中的樣本個數除以S中的樣本總數。熵值越小，子集劃分的純度越高。對于給定的子集Sj，其期望信息由下式給出：其中：pij=sij/sj是Sj中樣本屬于Ci的概率。屬性A上分支將獲得的信息增益為：算法計算每個屬性的信息增益，并選取具有最高信息增益的屬性作為給定集合S的測試屬性，創建 一個結點，并以該屬性標記，對該屬性的每個值創建一個分支，并據此劃分樣本。2.2 ID3建樹算法在決策樹生成過程中引入信息增益作為訓練樣本集合的分裂度量標準，就得到如下的ID3算法生成決策樹的基本步驟：(1)以待分類的訓練樣本集合作為根節點開始建樹。 (2)如果訓練樣本屬于同一類，則當前節點為葉節點，并用訓練樣本所屬的類

12、進行標記。 (3)否則，計算各個屬性對當前訓練樣本集合進行劃分的信息增益，選擇信息增益最大的屬性作為當前訓練樣本集合的判斷屬性。 (4)對于選定的判斷屬性，根據其每個不同的值分別建立相應的分枝，并將對應的訓練樣本子集劃分到相應的分枝中。 (5)算法遞歸應用步驟(2)、(3)、(4)，對各訓練樣本子集繼續劃分，生成新的決策樹分枝。 (6)算法停止。3 決策樹ID3算法的改進3.1 ID3算法的不足及改進思路本文重點關注了ID3算法的3個方面的不足： (1)ID3算法的分裂度量標準采用的是信息增益，通過以前大量的研究分析與實際應用可以知道，這種分裂度量標準偏向于選擇屬性值個數較多的屬性，而屬性取值

13、個數較多的屬性并不一定是最優的屬性。所以需要改進選擇屬性的分裂度量標準。 (2)ID3算法只能處理離散屬性，對于連續值的屬性，必須首先對其進行離散化才能投入使用。比如性別屬性是離散屬性，適合用ID3算法處理，而收入屬性就是一個連續值的屬性， 那么按照ID3算法是無法計算的，必須對收入離散化后才可用。所以需要針對連續值屬性的離散化方法做出改進。(3)采用ID3算法產生的決策樹進行預測時，必須知道從葉子節點到樹根的路徑上所有內節點對應的屬性的屬性值。如果樣本的某個屬性缺少具體的屬性值，那么這種樣本應用于ID3算法就不合適，所以要針對未知或在生成決策樹過程中才對缺省屬性賦值的情況做出改進，讓ID3算

14、法能夠滿足這種情況。以下是對上述提到的3個主要方面的不足的改進思路： (1)針對ID3算法的第一個缺點，在改進算法中引入一個修正參數，在對每個屬性求出信息增益后，用一個關于決策屬性取值個數的函數算出的參數去修正該信息增益，成為屬性選擇以及樣本分區成子集的分裂度量標準，這樣即可解決屬性值個數多少對生成決策樹的影響。 (2)針對ID3算法的第二個缺點，采用k-均值的聚類分析方法，通過選擇適當的k值，將該連續屬性上的值分為k個區間，即可將該屬性分為k個類。再按照離散屬性計算信息增益的方式計算出該屬性的分裂度量標準，與其它屬性進行比較得出最優判斷屬性。通過選擇適當的連續屬性離散化方法，就解決了連續屬性

15、的處理問題。 (3)針對ID3算法的第三個缺點，解決思路是將有缺少屬性值的樣本按照該屬性已知值的相對頻率隨機分布，在產生決策樹的節點時，同時記錄下滿足從該節點到根節點的路徑的條件的概率數，從而解決在屬性值缺失情況下的決策樹的預測能力問題。 為了防止決策樹的過度擬合問題，必須對生成的決策樹進行剪枝，此處采用后剪枝的方法，通過剪枝，去掉那些對未知檢驗樣本的分類精度沒有幫助的部分子樹，生成一個更簡單，更容易理解的樹。 ID3算法還有以下缺點：ID3算法對噪聲較為敏感，Quinlan定義噪聲為訓練樣本數據中的屬性值錯誤和分類類別錯誤。ID3算法在搜索中不進行回溯，每當在樹的某一層選擇了一個屬性進行測試

16、，就不會再回溯重新考慮這個選擇。這樣，算法容易收斂到局部最優的答案，而不是全局最優的，這些缺點和不足有待于進一步改進。3.2 ID3算法的改進方法所提出的改進算法除了擁有原ID3算法的基本功能外，將從以下幾個方面加以改進：通過修正參數修正算出的信息增益以改進ID3算法偏向屬性取值個數較多的屬性、對連續值的屬性進行離散化、處理缺少屬性值的訓練樣本、使用后剪枝技術避免樹的不平衡，以下從幾個方面進行詳細的闡述：(1) 使用修正參數修正信息增益 ID3算法使用信息增益標準對緊湊型決策樹的構造有較好的效果，但也有一個嚴重的缺陷：對具有較多數目的屬性有嚴重的偏差。論文中的改進算法將使用修正參數的概念對這一

17、缺陷進行改進，可以指定一個附加的修正參數：f(n)= 1n，上式中的n表示各決策屬性的取值個數，取值個數越多，n越大，則修正參數fin)越小。然后定義一個新的增益標準： Gain(Q)=f(n)Gain(Q)這個新的增益標準通過參數f(n)修正了原來的信息增益。在對每個屬性求出新增益標準以后，再用修正參數修正其值，并以此作為判斷屬性選擇以及樣本分區成子集的選擇準則。用新增益標準，可以避免偏向選擇屬性值個數較多的屬性為判斷屬性，因為屬性值越多，修正后的增益標準就越小，就不會輕易被選為判斷屬性了。(2)對連續值的屬性進行離散化 ID3算法只能處理離散類型的屬性。實際應用中包含兩種類型的檢驗結構：一

18、個方面是對離散屬性值的檢驗，ID3算法對離散屬性的每個可能值有一個分枝和輸出；另一個方面是對連續屬性檢驗。對于連續屬性Y，即數值型屬性的檢驗，改進算法采用k-均值聚類分析方法，將屬性Y上的取值進行聚類，首先隨機選擇該屬性上的k個值作為初始簇，這k個值即為各簇的中心值，然后對其它值分別計算到這些簇的距離，選擇距離最小的簇加入進去，然后通過加權平均的方法得出每個簇的中心值，依次類推，將剩余的值分別加入各簇，就得到該連續屬性Y上所有值的k個聚類，然后選擇第1到第k-1個簇中的最大值作為標準對Y進行劃分，設這k-1個值分別為V1，V2，Vk-1，則Y可以分為k個區間yV 1，V 1yV 2 ，V k-

19、1 y，這樣，該屬性就有k個屬性值，再按照離散屬性計算信息增益的方式計算出該屬性的修正信息增益。(3)處理缺少屬性值的樣本 ID3算法是基于所有屬性值都確定的情況下的分類，而實際應用中經常會缺少某些樣本的一些屬性值或存在數據值丟失的情況，直接拋棄數據庫中有丟失數據的樣本，這顯然不是 一個好的方法。 在論文提出的改進算法中，有未知值的樣本是按照已知值的相對頻率隨機分布的。對于有未知值的樣本，每個樣本都有一個概率參數，當一個值己知的樣本從T分配給T i時，屬于其它子集的概率為0。當一個值為未知時，只能得出不穩定的概率描述。改進算法中將每個子集Ti中的每個樣本用權重W標注，它表示屬于每個子集的樣本概

20、率。分區后，屬性己知的樣本屬于子集Ti的概率為1，有未知值的樣本被表示在每個Ti子集中，對于有未知值的樣本屬于子集Ti的概率為：己知的樣本屬于子集Ti的概率和屬性值己知的樣本數量。由于最終分類的不明確性，葉子結點的每個決策都以(|Ti|E)表示。|Ti|是到達結點的部分樣本和，E是除了指定類以外的類的樣本數量。(|Ti|E)的意思是|Ti|個部分訓練樣本到達葉結點，其中E并不屬于分配給葉的類。 (4)采用后剪枝方法優化決策樹 決策樹剪枝的基本思想是去掉那些對未知檢驗樣本的分類精度沒有幫助的部分子樹，生成一個更簡單，更容易理解的樹。本文的改進算法采用了后修剪方法，用默認的置信度25，比較所給內節

21、點Ti的U25%(|Ti|E)信度，從而決定該結點是否替換葉子結點。權值是每個葉的樣本的總數，若子樹中的某個根節點的預測誤差比葉的U25% (子樹的預測誤差)的加權和小，那么用它的根節點替換該子樹，變成剪枝后的樹的一個新葉。3.3改進的ID3算法的具體實現步驟根據改進的ID3算法的思想，通過以下幾個步驟來生成決策樹：(1)確定根結點： 1)統計樣本總量，樣本總量為訓練樣本集合中屬性值己知的樣本的數量。2)令p1=|E1|，p2=|E2|，pn=|En|，分別得到訓練樣本集合中第1類記錄的個數、第2類記錄的個數、第n類記錄的個數，根據公式計算期望信息I(p1，p2，pn)。3)根據某個屬性A具有

22、的屬性值為A1，A2，Av，若A為離散屬性，將訓練樣本集合按照分類類別劃分成E11，E12 ，E1v，E21，E22 ，E2v和En1，En2 ，Env。E1i，E2i，Eni中每個訓練樣本 的屬性取值為Ai，令p1i =| E1i |，p2i =| E2i |，pni =| Eni |，根據公式，求出E(A)；若A為連續屬性，首先設定要劃分的區間數k，然后隨機選擇該屬性A上的k個值 作為初始簇A1，A2，Ak，對剩下的取值分別計算與各簇的距離，選擇距離最短的加入各簇，依次類推，即可得到A上所有值的k個聚類，選擇簇A1到Ak-1中的最大值V1，V2，Vk-1作為標準對A進行劃分，得到A上取值的

23、k個區間aV 1，V 1aV 2 ，V k-1 a。再次用A的屬性值A1，A2，Ak，將訓練樣本集合劃分成E11，E12 ，E1k，E21，E22 ，E2k和En1，En2 ，Enk。4)根據公式Gain(Q)=fin)Gain(Q)求得按屬性A劃分訓練樣本集合的新增益標準值Gain(A)。 5)類似于3)、4)兩步，分別求出各屬性的新增益標準值Gain(A)，Gain(B)，選擇其中值最大的作為決策樹的根結點。 (2)確定根結點的下一級結點，根據根結點的各個屬性取值，采用廣度優先搜索的策略，將下級結點作為新的根節點再按照第一步的方法遞歸地求出各根結點的全部子結點，缺少 屬性值的訓練樣本被分別

24、表示在每個子結點的子集中。 (3)求出各級結點，直至求出全部的葉子結點，結束遞歸過程。 (4)考察各級結點以及葉子結點，對于所含缺少屬性值的訓練樣本分別計算其所屬類的概率(|Pi|E)，最后生成決策樹，采用深度優先搜索策略遞歸來求出該決策樹每個葉子的對 應規則。4 實驗及分析本文采用文獻10中的數據庫中若干標準數據集進行試驗分析，并分別基于ID3算法和改進的ID3算法進行客戶流失的分析。4.1 選擇決策屬性，數據準備和預處理客戶流失分析系統數據檢測建模的樣本數據為某企業的客戶數據451條記錄。與前面的潛在客戶發現一樣，為了對改進算法進行驗證，將客戶數據分為3份，每次選用2份用于生成決策樹，1份

25、用于測試生成的決策樹的預測準確率。具體數據如表4-1所示。 表4-1：客戶流失分析決策樹原始樣本客戶等級性別年齡婚姻狀況居住地與銷售點距離歷史最長購買間隔本次購買間隔1男250300844女371400354002男28180015232女39038012153男2912000152173根據企業具體情況進行分類，最后得到各連續屬性的離散化處理，如表4-2所示。表4-2：客戶流失分析決策樹修正樣本客戶等級性別年齡婚姻狀況居住地與銷售點距離歷史最長購買間隔本次購買間隔10202804131235320213151213021213021415224.2 生成決策樹下面首先使用傳統的ID3算法建立

26、決策樹，根據數據樣本建立客戶流失分析的決策樹模型。得到完整的數據樣本的決策樹如圖4-1所示。 圖4-1：傳統ID3算法生成的客戶流失分析決策樹然后再將訓練樣本交給改進的ID3算法進行處理，得到的決策樹如圖4-2所示。圖4-2：改進的ID3算法生成的客戶流失分析決策樹4.3 改進算法結果分析與評估在客戶流失分析模型的建立過程中，系統共采集了451條數據樣本，由于整體樣本數量不足夠大，因此采用3折交叉驗證的方法對該模型準確性做出評估，并與ID3算法所得結果進行比較。首先將采集到的451條記錄等量分為3份，取其中的2份作為訓練樣本，剩余1份作為測試樣本，分別對兩種算法進行測試。0表示穩定客戶、1表示

27、可能流失客戶、2表示極可能流失客戶、3表示流失客戶；表格中的第x行Y列的數據是指真實值為第x行所示數據被預測為第Y列數據的個數。整理以上各決策樹混淆矩陣，可得表4-3所示統計表。表4-3：傳統ID3算法和改進的ID3算法在客戶流失分析應用中的效率分析傳統ID3算法改進的ID3算法0類客戶(即穩定客戶)1類客戶(即可能流失客戶)2類客戶(即極可能流失客戶)3類客戶(即流失客戶)0類客戶(即穩定客戶)1類客戶(即可能流失客戶)2類客戶(即極可能流失客戶)3類客戶(即流失客戶)預測個數1879880861841029075正確個數165835858168876858預測準確率88.2%84.7%72.5%67.4%91.3%85.3%75.6%77.3%圖4-3：改進前后兩種算法預測準確率對比從試驗結果可以直觀發現：針對不同規模的數據集，改進算法