基于分類矩陣ID3決策樹的數據預處理技術研究＊

林 超 崔良中 周 鋼

（1.92941部隊 葫蘆島 125001）（2.海軍工程大學電子工程學院計算機工程系 武漢 430033）

1 引言

在數據挖掘的實際數據處理中，經常遇到冗余數據、缺失數據、不確定數據和不一致數據等情況，在這些“臟數據”基礎上進行數據挖掘，會使得分析和評估不準確、不全面，進一步影響從數據集中抽取模式的正確性和導出規則的準確性，從而導致錯誤決策和預測。因此，在進行數據挖掘之前進行數據預處理具有重要意義。一般來講，預處理工作一般要占整個數據挖掘的40%～90%的工作量［1］。數據預處理方法主要包括數據清理、數據集成和變換、數據規約［2］。本文主要研究數據清理中的缺失數據填補和異常數據處理的問題。

文獻［3］中研究了貝葉斯、決策樹等方法在數據預處理中的應用，并得出決策樹方法具有更好效果的結論。本文主要對常見決策樹ID3算法進行分析，并針對ID3算法存在的問題，引入分類矩陣方法，著力在克服多值偏向性和提高分類速率方面進行改進，并用實例進行測試驗證，最后給出該算法在數據預處理中缺失數據填補和異常數據處理上的具體應用。

2 ID3決策樹算法

決策樹分類算法以其易用提取顯式規則、計算量相對較小、可以顯示重要的決策屬性和較高的分類準確率等優點而得到廣泛的應用。其中，ID3算法是J.R.Quinlan于1986年首先提出的一個經典決策樹算法，該算法以信息論為基礎，把信息增益度量屬性選擇，選擇分裂后信息增益最大的屬性進行劃分［4］。ID3算法根據不同的特征，以樹型結構表示分類或決策集合，發現規律并產生規則，其主要優點是描述簡單，分類速度快，特別適合大規模的數據處理［5］。

2.1 ID3決策樹分類過程

決策樹分類的建立過程與決策樹分類模型進行預測的過程實際上是一種歸納演繹過程。歸納過程就是由用于分類的數據得到決策樹分類模型的過程，而演繹過程就是用決策樹分類模型對未分類數據進行分類的過程。但是為了保證演繹的準確性，需要增加測試集測試的環節，因此決策樹分類的過程就是對訓練集歸納，用測試集測試，最后演繹未分類數據的過程，如圖1所示：

圖1 決策樹分類過程

2.2 ID3決策樹的建立

建立決策樹就是以實例為基礎的歸納學習，即從一組無次序、無規則的事例中推理出決策樹表示形式的分類規則，從而形成決策樹。其實質是利用訓練樣本集來建立并進化出一棵決策樹，建立決策樹模型。目的是利用建立的決策樹生成分類規則，從而再根據各個數據的屬性值實現對數據集的分類［6］。

對于分類屬性A，假設具有v個不同的值（a1，a2，…，av），那么數據樣本總集合S可以劃分為v個子集（s1，s2，…，sv），其中Sj是S中具有aj的樣本，sij是子集Sj中Ci的樣本數。那么，在屬性A上劃分子集的熵為

那么，針對屬性A劃分的信息增益為

ID3算法策略如下：1）判定樹以代表訓練樣本的單個節點開始；2）如果樣本都在同一個類，則該節點成為樹葉，并用該類標記；3）否則，使用稱為信息增益的基于熵的度量Gain（C，T）作為啟發信息，選擇最好將樣本分類的屬性作為該節點的“測試”或“判定”屬性；4）對測試屬性的每個已知的值，創建一個分枝，并以此為根據劃分樣本；5）使用同樣的過程，遞歸地形成每個劃分上的樣本判定樹。當出現下列情況時停止遞歸劃分：給定節點的所有樣本屬于同一類：沒有剩余屬性可以用來進一步劃分樣本；沒有剩余樣本。

2.3 ID3決策樹算法的局限性

ID3算法作為最典型的決策樹算法，具有較好的分類效果和決策預測能力，但是ID3算法也有一些局限性［7］，主要集中表現在：

1）這種基于信息熵的計算方法容易產生多值偏向問題，即偏向于選擇屬性取值較多的非類別屬性，而屬性值較多的非類別屬性并不總是最優的；

2）數據集越大，非類別屬性越多，需要的計算時間就會急劇增加；

3）ID3算法對噪聲比較敏感。Quinlan定義的噪聲是訓練集合中的錯誤，這種錯誤包含兩種：一種是屬性取值錯誤，另一種是類別錯誤。

3 基于分類矩陣的ID3算法

為了針對ID3算法局限性進行改進，本文定義了一種用于決策樹分類的矩陣，通過將矩陣作為增益參數來進行改進。

3.1 基于分類矩陣的ID3算法定義

在給定的一個訓練集T中，若按照其中任意一個非類別屬性X＝ ｛X1，X2，…，Xm｝將T分為集合T1，T2，…，Tm，其中Ti（i＝1，2，…，m）又按照類別屬 性C＝｛C1，C2，…，Cn｝分為了m×n個部分，形成了X到C的映射，本文將這種映射定義為分類矩陣，記為分類矩陣AX，C，且

其中AX，C中的任一位置元素定義為aij（i＝1，2，…，m；j＝1，2，…，n；aij是非負整數）表示在訓練集T中，同時對應屬性值Xi和屬性值Cj的實例個數，而所有元素之和就是訓練集T的總個數。屬性X和屬性C的各個屬性值可以是無序的，因此任意對分類矩陣AX，C進行行交換或列交換，得到的矩陣仍然屬性X到屬性C的映射矩陣，只不過交換后矩陣元素對應的屬性值應做相應的交換。

根據分類矩陣特征，用Gain（AX，C）代替增益Gain（X，T），經推算基于分類矩陣的增益公式如下：

根據式（1）定義，Gain（X，T）具備性質：

1）增益非負性。根據增益的定義可知信息量恒為非負值，即在任意非空的訓練集T中，對于任意非類別屬性X都存在Gain（X，T）≥0。

2）矩陣擴展后增益不變。對于上述矩陣Q，根據Gain（X，T）定義可知若存在任意矩陣U：

（其中O為相應維數的零矩陣）都有

3）無序性。任意對分類矩陣AX，C進行行交換或列交換，得到的新的分類矩陣A＊X，C，其基于分類矩陣的增益仍不變，即

3.2 多值偏向性的克服

文獻［8］僅指出了ID3算法多值偏向，為克服ID3算法的多值偏向，基于分類矩陣的決策樹算法引入一個權重因子t，將增益與權重因子的乘積暫時作為屬性選擇標準，其中t＝1／log2m，m為屬性X的取值個數，即屬性的選擇標準暫時修改為式（2）如下：

引入權重因子t原因如下：

1）對于任意訓練集，其增益都為非負且不大于log2m，而且log2m是定值，其計算速度相對于增益的計算可忽略。

引入權重因子t，并將因子值定為t＝1／log2m，可以使增益縮放到［0，1］范圍內進行比較，從而使比較更固定，更準確，同時又基本保持了其原有的計算速度。

2）引入權重因子t，克服了ID3算法的多值偏向性。根據文獻［9］分析可知，引入權重因子t后，如果有式（3）如下

該式（3）恒成立，則說明改進的決策樹算法在建樹過程中仍具有多值偏向。反之則該算法不具有多值偏向性。

根據Gain（AX，C）性質1，Gain（AX，C）都是非負的，那么必然存在任意m×n階的分類矩陣AX，C，使Gain（AX，C）＞0，現假設AX，C就是這樣的矩陣（一般情況下，在屬性選擇時將不會選擇增益為0的非類別屬性，因此討論增益為0的情況也是沒必要的），同時令新映射：

其中Osn為s×n階的零矩陣，s＞1，那么由Gain（AX，C）性質2和性質3，可知

同時m＋s－1＞m，那么有

以上假設說明，引入權重因子t后，新映射的增量存在小于0的情況，式（3）非恒成立，因此避免了算法的多值偏向，從而使分類時，尤其是在各個非類別屬性取值個數差別較大時，能更加準確地選擇非類別屬性，提高分類準確率，即降低了分類的噪聲敏感性。

3.3 分類速率的改進

當數據集越來越大，非類別屬性越來越多時，分類時間問題就凸現了出來。分類的時間大部分用于了增益的計算上，分析基于分類矩陣的增益Gain（X，T）定義式（1）可知：

1）算法的計算環節需要不斷的進行形式為xlog2x的計算（x為0到訓練集總個數之間的整數），而這種對數計算的時間復雜度相對與從數組中讀取是很高的。

2）對于任意給定的一個訓練集T，其類別屬性的信息量Info（T）即

是不變的，那么對應于定義式（1）則其前兩項是不變的。

3）對于任意給定的一個訓練集T，定義式（1）的除數項都是不變的。

因此若要加快分類速率，減少分類時間就必須針對以上問題改進，本文改進的方案是：

（1）在實際的應用過程中，我們可以事先利用數組來存放形式為xlog2x的對數值，計算過程中只需要不斷的從數組中讀取即可。例如本文在MATLAB仿真中利用數組arr（1）～arr（sum＋1）來存放xlog2x的從0到1＊log21～sum＊log2sum的數值（sum表示訓練集的總個數），從而大大縮短了計算的時間。

（2）在非類別屬性個數較多時，只計算一次定義式（1）的前兩項。

（3）去除式（1）的除數項，從而減少不必要的計算開支。

因此，綜合以上改進方法，引入權重因子t后，Gain（X，T）定義式（1）可以更改為

用imGain（AX，C）代替Gain（X，T）作為非類別屬性的選擇標準來對數據集進行分類，明顯地將克服多值偏向性并且能提高分類的速率。

4 實例驗證和應用

4.1 實例數據驗證

為了測試本文方案的改進程度，本文采用UCI機器學習數據庫（其網址為：http：／／archive.ics.uci.edu／ml／datasets.html）中的Car Evaluation數據集和Nursery數據集進行對比驗證。驗證的方法是采用對較小數據集Car Evaluation從第1條數據開始每4條數據進行一次抽樣，得到432條數據作為訓練集，其余作為測試集，而對于較大數據集Nursery從第1條數據開始每8條數據進行一次抽樣，得到的1620條數據作為訓練集，其余作為測試集。

在同一臺電腦上，利用MATLAB對以上數據集各進行50次實驗，每次實驗都對訓練集經行1000次連續重復分類，而且每次分類都讓決策樹完全生長。求其單次分類平均值、得到的葉子節點個數和利用測試集測試出分類的精確率，得到的實驗數據如1所示。

表1 決策樹完全生長的實驗結果

由于上述實驗得到的決策樹是完全生長的，很多葉子節點都只有一個或兩個實例，相對于訓練集的樣本個數是可以忽略不計的，而且適量的減少節點可以使決策樹得到簡化，從而使分類規則更容易理解。本文使用預剪枝的方法，設定其閾值為3，即實例個數小于3時，將停止相應樹枝的生長。在此情況下，再次對上述數據集進行比較，得到的實驗數據如表2所示。

表2 閾值設為3時的實驗結果

對比表1和表2的葉子節點數可知，設定閾值后葉子節點數，即分類規則，將大大減小，從而更能說明分類方案的優劣。對比表3的各項可以說明，決策樹規則生成過程中，相比于ID3算法，使用本文改進算法發現：分類速率大大提高；生成規則個數有所減少；分類精確率有所提高。從而達到了對原有算法改進的目的。

4.2 算法應用

用基于分類矩陣的決策樹算法建立分類模型，在數據挖掘的數據預處理中實現缺失數據的填補和異常數據的處理。這里主要介紹該算法在這兩個方面的具體應用方法：

1）缺失數據的填補。

對于缺失值的處理，分為刪除存在缺失值的個案和缺失值插補兩種方法［10］。在缺失數據填補的過程中，需要刪除含有較多缺失值的數據、較少完整值的屬性和獨立的屬性。缺失值較多將導致數據無法填補，獨立的屬性應當刪除。然后缺失數據的子集按照完整數據子集建立的規則進行填補，最后進行合并，就得到了填補的數據集。

2）異常數據處理

在數據挖掘過程中，數據集可能包含一些數據對象，它們與其他數據的一般行為或模型不一致，這些對象便成為異常數據。異常數據是指在數據集中與眾不同的數據，使人懷疑這些數據并非隨機偏差，而是產生于完全不同的機制［11］。

異常數據處理的方法有多種，比如基于統計的方法、基于距離的方法、基于偏離的方法、基于密度的方法等［13］。按本文算法的異常數據處理方法，需要首先對連續屬性離散化，對離散化后的數據建立決策樹分類規則，然后利用規則對數據集進行規則匹配，找出異常數據，并通過人工干預決定數據的修改或刪除，最后得出規則的數據集。

對于缺失數據和異常數據，人工的干預是必不可少的，以保證用來進行數據挖掘進行預測和決策的準確性。

5 結語

本文提出了一種基于分類矩陣的ID3算法，該算法引入分類矩陣方法，對ID3算法的多值偏向性和分類速率進行改進，并利用實例對改進效果進行驗證同時給出了數據挖掘的預處理中，本改進算法在缺失值填充和異常數據處理中的具體應用。通過分析，可以知道該改進算法能有效克服多值偏向性并提高分類速率，并在數據預處理中有很好的應用。

［1］Garcia－Laencina P J，Sancho Gomez J L，Figuesiras Vidal A R，Verleysen M K.nearest neighbors with mutual information for simultaneous classification and missing data imputation［J］.Neurocomputing，2009，72（7－9）：1483－1493.

［2］李雄飛，李軍.數據挖掘與知識發現［M］.北京：高等教育出版社，2003：23－25.

［3］周鋼，李昂新.兩種填充空缺值方法在技術級別判定中的應用比較［J］.艦船電子工程，2011（7）：109－112.

［4］Quinlan J R.Induction of decision tree［J］.Machine learning，1986（1）：81－86.

［5］鄒志文，朱金偉.數據挖掘算法研究與綜述［J］.計算機工程與設計，2005，26（9）：2304－2307.

［6］武獻宇，王建芬，謝金龍.決策樹ID3算法研究及其優化［J］.微型機與應用，2010，29（21）：7－9.

［7］張鳳蓮，林健良.新的決策樹構造方法［J］.計算機工程與應用.2009，45（10）：141－143.

［8］Quan Liu，Daojing Hu，Qicui Yan.Decision Tree Algorithm Based on Average Euclidean Distance［C］／／2010 2nd International Conference on Future Computer and Communication（ICFCC），2010：507－511.

［9］狄文輝，李卿，樓新遠.基于修正系數的決策樹分類算法［J］.計算機工程與設計，2008，29（24）：6344－6346.

［10］武森，馮小東，單志廣.基于不完備數據聚類的缺失數據填補方法［J］.計算機學報，2012（8）：1726－1738.

［11］郝慧麗，劉先勇.含噪點云預處理技術研究［J］.微型機與應用，2012（12）：68－71.

［12］李小飛.基于BP網絡的GDP預測數據預處理方法研究［J］.計算機與數字工程，2011（9）.

［13］陳文偉，黃金才.數據倉庫與數據挖掘［M］.北京：人民郵電出版社，2004：42－44.