林 超 崔良中 周 鋼

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

1 引言

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

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

2 ID3決策樹算法

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

2.1 ID3決策樹分類過程

決策樹分類的建立過程與決策樹分類模型進(jìn)行預(yù)測的過程實(shí)際上是一種歸納演繹過程。歸納過程就是由用于分類的數(shù)據(jù)得到?jīng)Q策樹分類模型的過程，而演繹過程就是用決策樹分類模型對未分類數(shù)據(jù)進(jìn)行分類的過程。但是為了保證演繹的準(zhǔn)確性，需要增加測試集測試的環(huán)節(jié)，因此決策樹分類的過程就是對訓(xùn)練集歸納，用測試集測試，最后演繹未分類數(shù)據(jù)的過程，如圖1所示：

圖1 決策樹分類過程

2.2 ID3決策樹的建立

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

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

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

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

2.3 ID3決策樹算法的局限性

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

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

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

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

3 基于分類矩陣的ID3算法

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

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

在給定的一個訓(xùn)練集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是非負(fù)整數(shù)）表示在訓(xùn)練集T中，同時對應(yīng)屬性值Xi和屬性值Cj的實(shí)例個數(shù)，而所有元素之和就是訓(xùn)練集T的總個數(shù)。屬性X和屬性C的各個屬性值可以是無序的，因此任意對分類矩陣AX，C進(jìn)行行交換或列交換，得到的矩陣仍然屬性X到屬性C的映射矩陣，只不過交換后矩陣元素對應(yīng)的屬性值應(yīng)做相應(yīng)的交換。

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

根據(jù)式（1）定義，Gain（X，T）具備性質(zhì)：

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

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

（其中O為相應(yīng)維數(shù)的零矩陣）都有

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

3.2 多值偏向性的克服

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

引入權(quán)重因子t原因如下：

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

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

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

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

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

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

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

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

3.3 分類速率的改進(jìn)

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)例驗證和應(yīng)用

4.1 實(shí)例數(shù)據(jù)驗證

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

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

表1 決策樹完全生長的實(shí)驗結(jié)果

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

表2 閾值設(shè)為3時的實(shí)驗結(jié)果

對比表1和表2的葉子節(jié)點(diǎn)數(shù)可知，設(shè)定閾值后葉子節(jié)點(diǎn)數(shù)，即分類規(guī)則，將大大減小，從而更能說明分類方案的優(yōu)劣。對比表3的各項可以說明，決策樹規(guī)則生成過程中，相比于ID3算法，使用本文改進(jìn)算法發(fā)現(xiàn)：分類速率大大提高；生成規(guī)則個數(shù)有所減少；分類精確率有所提高。從而達(dá)到了對原有算法改進(jìn)的目的。

4.2 算法應(yīng)用

用基于分類矩陣的決策樹算法建立分類模型，在數(shù)據(jù)挖掘的數(shù)據(jù)預(yù)處理中實(shí)現(xiàn)缺失數(shù)據(jù)的填補(bǔ)和異常數(shù)據(jù)的處理。這里主要介紹該算法在這兩個方面的具體應(yīng)用方法：

1）缺失數(shù)據(jù)的填補(bǔ)。

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

2）異常數(shù)據(jù)處理

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

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

對于缺失數(shù)據(jù)和異常數(shù)據(jù)，人工的干預(yù)是必不可少的，以保證用來進(jìn)行數(shù)據(jù)挖掘進(jìn)行預(yù)測和決策的準(zhǔn)確性。

5 結(jié)語

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

［1］Garcia－Laencina P J，Sancho Gomez J L，F(xiàn)iguesiras 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］李雄飛，李軍.數(shù)據(jù)挖掘與知識發(fā)現(xiàn)［M］.北京：高等教育出版社，2003：23－25.

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

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

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

［6］武獻(xiàn)宇，王建芬，謝金龍.決策樹ID3算法研究及其優(yōu)化［J］.微型機(jī)與應(yīng)用，2010，29（21）：7－9.

［7］張鳳蓮，林健良.新的決策樹構(gòu)造方法［J］.計算機(jī)工程與應(yīng)用.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］狄文輝，李卿，樓新遠(yuǎn).基于修正系數(shù)的決策樹分類算法［J］.計算機(jī)工程與設(shè)計，2008，29（24）：6344－6346.

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

［11］郝慧麗，劉先勇.含噪點(diǎn)云預(yù)處理技術(shù)研究［J］.微型機(jī)與應(yīng)用，2012（12）：68－71.

［12］李小飛.基于BP網(wǎng)絡(luò)的GDP預(yù)測數(shù)據(jù)預(yù)處理方法研究［J］.計算機(jī)與數(shù)字工程，2011（9）.

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