面向不完備數據的改進C4.5算法研究

沈亮亮 蒙祖強 張兵 郭英明

摘 要：大數據時代，數據量呈現爆炸式增長，且在內容與形式上日益復雜化，造成數據質量下降、數據丟失等，即產生不完備數據。提出一種改進的C4.5算法，使其能更好地處理不完備數據。每次特征選擇前對本次特征選擇的數據子集使用子集匹配方法進行處理，通過比較數據清洗方法與子集匹配方法的結果，顯示即便是在相同清洗規則下，子集匹配方法在算法分類準確率上也更有優勢。實驗結果證明，在利用C4.5算法進行特征選擇時，在該數據子集上對不完備數據進行處理，可以得到較高的分類準確率，同時得到比數據清洗高的時間復雜度。

關鍵詞：不完備數據；C4.5算法；分類算法

DOI：10.11907/rjdk.172181

中圖分類號：TP312

文獻標識碼：A 文章編號：1672-7800（2018）006-0095-05

Abstract：In the era of big data， data not only presents explosive growth in quantity， but also becomes increasingly complex in content and form， resulting in the decline of data quality. An unavoidable problem is the loss of data， that is， incomplete data. In this paper， an improved C4.5 algorithm is proposed to deal with incomplete data better. The specific method is to use the subset matching method to process the incomplete data on the subset of the feature selection before each feature selection. By comparing the results of data cleaning method and subset matching method， it is shown that subset matching method has the advantage of classification accuracy even under the same cleaning rule. The experimental results show that it is reasonable to process the incomplete data on the subset of the data set when the C4.5 algorithm is used for feature selection， and it gets higher classification accuracy， but this method will also get higher time complexity than that of data cleaning.

Key Words：incomplete data； C4.5 algorithm； classification algorithm

0 引言

隨著計算機技術以及網絡通信技術的快速發展，數據規模在全世界范圍內以指數級快速增長。在我國，隨著大數據時代的到來，數據規模正從每天TB級匯聚量向PB級發展，中國電信發布的信息顯示，至2017年3月末，其每天的數據匯聚量就達到200TB[1]。面對如此龐大的數據，如何從其中獲取知識正受到人們越來越多的關注。如何對現實領域中的大量數據進行有效處理，從而挖掘出潛在有用的知識，已成為當前數據挖掘、計算智能與機器學習的重要研究課題之一[2]。在大量數據中，有時會出現數據屬性值丟失的情況，含有缺失屬性值的數據稱為不完備數據，由不完備數據構成的信息系統稱為不完備信息系統。隨著數據規模的快速發展，數據來源途徑的多樣化、干擾、誤差、遺漏甚至人為因素等成為導致數據不完備的主要原因。不完備數據的出現是不可避免的，傳遞到不同的處理應用層次，體現為信息不完備、信息不確定、信息不準確、信息模糊、信息遺漏、信息沖突等互為交織的表現形式[3]。在數據挖掘、計算智能與機器學習等研究領域，分類算法是其核心。所以有必要對分類算法進行改進，以期擴展分類算法適用的數據范圍。

1 數據處理常用方法

一般的數據處理方法是在數據分類之前通過對丟失值進行填補，再對數據完備化或直接將包含丟失值的樣本刪除。填補法是將不完備屬性值填補成完備的屬性值，主要有2種方法：一是利用已有的屬性值填充，即不完備的屬性值可能是其它數據同屬性的屬性值；二是不用已有的屬性值填充，而用某種方法獲得其它屬性值填補。

為了提高數據質量，在具體應用上有許多種方法，比如使用數據清洗、聚類、粗糙集等填充不完備數據。文獻[4]提出了一個基于限制容差關系的不完備信息系統，以及粗糙集模型面向不完備數據的數據挖掘系統模型。文獻[5]以粗糙集為對象，提出了一種基于屬性重要度的不完備數據填補算法，分析了屬性重要度對于填補不完備數據缺失值的影響，并通過實驗證明，與ROUSTIDA算法相比，該算法具有更高準確率。文獻[6]以粗糙集理論為工具，針對動態不完備數據進行系統的特征選擇研究，提出一種混合特征評估函數度量候選特征的區分能力，并設計出基于貪心向前搜索的特征選擇算法。文獻[7]提出基于不完備數據聚類的缺失數據填補方法（MIBOI），針對分類變量不完備數據集定義約束容差集合差異度，直接計算不完備數據對象集合內所有對象的總體相異程度，以不完備數據聚類的結果為基礎進行缺失數據填補。

刪除法的思想是直接去除包含不完備屬性值的數據樣本，不處理法的思想是將不完備屬性值當成一個可以應用的屬性值進行計算。在面對不完備數據時，應用不處理或者刪除方法時，會造成有用信息損失；應用替補法時，無法保證替補的不完備數據完全正確，甚至替補上錯誤的數據，對該數據的算法或者應用會造成巨大影響。總之，這些方法的缺點是人為改變了數據包含的信息結構，扭曲了數據本來包含的有用信息。

除以上基于數據清洗的方法外，還有可以直接處理不完備數據而得到決策規則的方法。Jerzy W Grzymala-Busse等[8]根據缺失值的語義不同，將不完備信息系統中的缺失值分別定義為“丟失值”與“不關心值”，其中“丟失值”用“？”表示，不能用任何在該屬性上的屬性值替換，而“不關心值”用“*”表示，可用任意同屬性上的屬性值替換。根據缺失值的不同處理方式，有學者提出了一種新的基于特性關系面向不完備數據的粗糙集模型[9-10]。文獻[11]提出了在面向不完備數據時，利用單體近似、子集近似與概念概率近似的性質進行數據挖掘，并通過實驗證明，對于給定的數據集，3種方法都是高效的。

如果能在面向不完備數據時直接進行處理得到決策規則，最簡單的方法是遍歷決策樹。Quinlan[12-13]在1986年提出的ID3算法是基于信息熵的決策樹分類算法，還在1993年提出了ID3的改進版本C4.5算法，C4.5算法用信息增益率選擇決策屬性，它繼承了ID3算法的優點，在ID3基礎上增加了對連續屬性的離散化、對未知屬性的處理和產生規則等功能。C4.5算法在保留ID3算法優點的同時還改進了ID3的2個缺點：在對分支屬性決策時，ID3使用信息增益這一指標進行度量，導致選擇偏向于取值多的屬性，這些屬性是無效數據，而C4.5則使用信息增益率；ID3算法只能取離散數據，C4.5屬性值既可以是離散值也可以是連續值，因為C4.5能夠對連續數據進行離散化處理[14]。雖然C4.5的分類準確性高，但算法的效率比較低。

本文提出一種方法，在利用C4.5算法每次進行特征選擇對不完備數據進行處理時，嘗試應用數據預處理的思想對當前不完備數據中的缺失值進行替換，使C4.5算法能更好地適應不完備數據。

2 預備知識

2.1 不完備數據

在數據中，含有缺失屬性值的數據稱為不完備數據，由不完備數據構成的信息系統稱為不完備信息系統。

以下原因經常導致不完備數據產生：①有的屬性值是空值；②有些數據在當時認為不需要；③有些因誤解而沒有記錄；④數據采集設備故障導致沒有記錄；⑤歷史原因或忽略了修改數據；⑥有些數據性價比太低而被忽略。

在各種科學研究中，數據缺失現象非常普遍，不完備數據給數據的使用與分析帶來了很大困難，是造成信息系統不確定的主要原因之一[15]，也是面向不完備數據處理方法越來越重要的原因。

丟失值的處理方法大體上分成3類：刪除法、數據補齊法與不處理法。

刪除法是將含有缺失值的樣本刪除，得到完備數據并加以利用，適用于含有缺失值的樣本數在數據總樣本數中所占比例非常小的情形。這種處理方法非常簡單，但是會造成資源浪費，因此無法保證刪除的樣本中不包含重要信息。

數據補齊法是用某種方法將缺失值進行補齊，即是用某個值替換缺失值，具體的方法有人工填充、特殊值填充、平均值填充、熱卡填充、K最近距離鄰法、所有可能值填充、組合完整化法、回歸、期望值最大化方法和多重填補法等。這些替換方法能提高數據挖掘的準確率，但無法保證替換是完全準確的，不正確的替換會帶來噪聲，也會產生錯誤的數據挖掘結果。

不處理法是不對數據進行完備化處理，直接利用不完備數據。除了一些能直接處理不完備數據的算法如貝葉斯網絡與人工神經網絡等之外，由于原理與數據類型等方面的原因，其它算法無法直接處理不完備數據，會產生不可靠的數據挖掘結果甚至錯誤的結果。

2.2 C4.5算法

信息熵[16]是由C E Shannon（信息論之父）在1948年發表的論文通信的數學理論（A Mathematical Theory of Communication）文中提出的，說明任何信息都存在冗余，冗余大小與信息中每個符號（數字、字母或單詞）的出現概率或者不確定性有關。C E Shannon將熱力學的熵引入到信息論中，目的是將信息量化。信息中排除冗余后的平均信息量被稱為“信息熵”，信息熵計算的數學表達式[17]如式（1）所示：

式（1）中，p-k表示數據集D中第k類樣本所占的比例。Ent（D）的值越小，則D的純度越高；信息量越小，度量值越小。

信息增益是一種能衡量樣本特征重要性的方法，是有無樣本特征對分類問題的影響差值。假設離散屬性a有V個屬性值{a1，a2，…，a-v}，如果使用a作為劃分屬性對樣本D進行劃分，則會產生V個分支節點，Dv則表示樣本D在劃分屬性a上所有取值a-v的樣本集合，各分支節點的權重|D-v|/|D|則可以計算出屬性a對樣本集D的“信息增益”了。計算公式如式（2）所示：

信息增益在分類算法上有非常重要的應用，決策樹的ID3算法都使用信息增益理論選擇劃分屬性或特征選擇。信息增益越大，屬性a對樣本集D進行劃分所獲得的純度提升越大，越有利于劃分屬性的選擇，即選擇劃分的特征。

信息增益理論是有缺陷的，并不是信息增益高就可以作為劃分屬性。信息增益的計算方法是對屬性值較多的屬性有所偏好，比如標號屬性。編號屬性的信息增益遠大于其它候選劃分屬性，每個編號都能生成1個節點，每個節點都只有一個樣本，但這樣的決策樹并不具備泛化能力，對于新樣本無法進行有效預測。

為了克服信息增益的缺陷，C4.5決策樹算法忽略了直接使用信息增益，而是采用信息增益率[13]選擇劃分屬性。如式（3）所示：

式（3）中，IV（a）如式（4）所示：

IV（a）稱為屬性a的固有值，屬性a的屬性值越多，即V越大，則IV（a）通常越大。

C4.5算法可以遞歸實現，其基本算法如下：讀入訓練集，構造屬性集與樣本序號集，作為算法對應的樣本集、屬性集與樣本序號集參數。

Step 1：遞歸算法TreeGenerate（樣本集、屬性集、樣本序號集）開始，生成節點node。

Step 2：判斷算法遞歸返回。若參數所有樣本決策屬性相同，將node類別標記為該決策屬性的葉子節點并返回node；若屬性集為空或者所有樣本在屬性集中所有屬性上的屬性值相同而決策屬性不同，將node標記為葉子節點，其類別標記為決策屬性最多樣本數的類并返回node。

Step 3：從屬性集中選擇信息增益率最高的屬性作為特征屬性。根據樣本屬性值的數據類型選擇不同的計算信息增益率方法，若數據類型為離散型，則計算各屬性值的信息增益率，信息增益率最高的屬性作為特征屬性；若數據類型為連續型，排序后取相鄰2個值的中間值為候選特征屬性值，取大于和小于該特征屬性值的兩個樣本集計算信息增益率，取最大值作為該連續型候選特征屬性的信息增益率，與其它候選特征屬性進行比較，用信息增益率最高的屬性作為特征屬性。

Step 4：對特征屬性的每一個屬性值進行遍歷，為node生成一個分支，其類別標記為屬性值，分支樣本集為node的樣本集中所有特征屬性為該屬性值的樣本集合，分支屬性集為node去掉特征屬性的集合，分支樣本序號集為分支樣本集中的樣本在訓練集中的序號集合；若分支樣本集為空，標記分支節點為葉子節點，其類別標記為node樣本集中樣本最多的類。

Step 5：算法結束，輸出以node為根節點的決策樹。從該基本算法可得出，設定好輸入與停止條件，算法可以自動生成一棵C4.5決策樹，輸入的訓練集可以根據輸入的屬性集與樣本序號集循環建樹，也可以用整形數據表示決策屬性。以UCI數據集為例，雖然每一個數據集都包含記錄數據的數據文件和對數據各方面進行說明的說明文件，可以用于讀入算法中要求的訓練集和屬性集，但是可以不用讀入屬性集，直接使用訓練集中數據的屬性編號作為分裂屬性的屬性名，其與讀入內存數據表中屬性的存儲位置有關，樣本序號集同樣如此。其實只需要讀入數據集就可以構建決策樹。本質上C4.5算法在編程時也需要構建鍵-值對以對屬性集中的屬性名進行數字化。

因為C4.5算法的核心就是計算信息增益率，所以在面向不完備數據進行改進時，需要將改進的方法加入信息增益率的計算之前。

3 C4.5算法改進

本文提出一種方法，在C4.5算法每次進行特征選擇對不完備數據處理時，應用數據預處理思想對當前不完備數據中的缺失值進行替換，使C4.5算法能更好地適應不完備數據。

在C4.5的遞歸算法Step 3中，每次選擇特征屬性前都會在當前樣本集上計算信息增益率，在每次計算之前，對當前樣本的不完備數據應用數據預處理思想進行一次處理，再計算信息增益率。每次處理的數據集都是開始輸入的數據集子集，這種方法稱為子集匹配。每個子集都是當前節點的父節點，利用信息增益率計算特征屬性進行分支構建后得到的子集樣本集，其樣本在父節點的特征屬性上是相同的，因此樣本間存有關聯，在這種情況下遞歸進行不完備數據缺失值的替換比使用數據預處理方法替換更好。使用這種方法得到完備數據能獲得更高的分類準確率。用子集匹配得到的分類準確率與數據預處理之后得到的分類準確率進行比較，驗證子集匹配方法的合理性。

為了證明面向不完備數據對C4.5算法的擴展，對數據集使用相同的數據預處理方法——最高頻替換方法進行處理。在每一次清洗中，應用數據預處理與子集匹配2種方法，結果證明子集匹配的方法是合理的。在不完備數據中，如果在某個屬性上出現缺失值，計算過程中使用在該屬性上出現次數最多的屬性值進行替代，即最高頻屬性值填充。用屬性值（n）表示該屬性值出現n次，則：

缺失值=屬性值（MAX）

在C4.5算法的基礎上，具體實驗步驟如下：

第一步，對不完備數據集進行一次數據預處理，對數據集中的不完備數據用同屬性數據中出現次數最高的數據進行替換。將數據集讀入內存后，對讀入的二維表進行遍歷，首先遍歷每一個屬性，在遍歷過程中，計算該屬性中出現最高頻率的樣本（屬性的屬性值），對每一個屬性中的樣本再遍歷一次，將其中不完備數據用最高頻樣本進行替換。將處理完成的完備數據表應用10折交叉驗證方法，分為訓練集與測試集，將訓練集導入C4.5算法得到決策樹，然后決策樹對測試集進行分類，得到一次算法的分類正確率，重復10次得到10折交叉驗證的平均分類正確率。

第二步，將訓練集直接導入C4.5算法，每一次進行遞歸特征選擇之前，對數據集中的不完備數據應用第一步中的最高頻方法進行替換，用得到的完備數據集計算信息增益率，選信息增益率最高的屬性作為特征屬性，如此循環直到算法完成。用決策樹對測試集進行分類，得到一次算法的分類正確率。重復10次得到10折交叉驗證的平均分類正確率。

結果說明，子集匹配方法比數據預處理方法的分類準確率高，并且子集匹配方法也適用于不同的數據預處理方法。

4 實驗分析

從UCI數據網（http：//archive.ics.uci.edu/ml/）隨機挑選包含不完備數據的數據集Anneal、crx、 horse-colic、lung-cancer、sponge進行實驗。

為了驗證實驗結果的有效性與可重復性，所有實驗在個人計算機上實現，其配置為：Intel（R） Core（TM） i7-2640M CPU @ 2.80GHz，內存為4GB，操作系統是Windows 7，程序開發平臺是EclipseSDK，編程語言是JAVA1.8。

從機器學習數據庫中選取5個真實數據集分析算法的性能，數據集的詳細情況如表1所示。

每一個數據集包含的樣本數、屬性數與包含不完備數據的不完備屬性數都是在對數據集進行遍歷時統計出來的。對于每一個屬性來說，其包含的不完備樣本數與該屬性包含樣本數的比是該不完備屬性的不完備率或缺失率，而所有不完備屬性的缺失率之和與不完備屬性個數的比，是該數據集不完備屬性的平均缺失率。

在Anneal數據集中，有5個屬性的不完備缺失率是100%，即該屬性中所有數據都是缺失的，缺失率在95%以上的不完備屬性有9個，所以造成平均缺失率高達85.09%。對于不完備缺失率為100%的屬性，由于其完全不具備區分度，對算法的結果沒有影響，所以作刪除處理。

早期工作發現，留一交叉驗證雖然可以作為回歸問題的漸近無偏估計，但是Shao Jun[18]的研究表明，在分類模型中不具有漸近無偏的良好性能。因此，Hastie[19]等使用5折交叉驗證、10折交叉驗證估計分類模型泛化誤差以及對不同模型的性能差異進行檢驗。

本實驗采用10折交叉驗證方法計算算法的平均分類準確率，用于評估算法的分類準確度。對于每一個數據集，平均分成10份，取其中1份作為測試集，其它9份作為訓練集，實驗得到一次結果，即一次分類正確率。輪流取10份中的一份作為測試集做10次實驗，其結果的平均正確率即是該算法的平均分類準確率。在實驗時，還計算了方差和標準差用于衡量實驗結果的分散情況及實驗結果與其期望的偏差。

實驗采用的評價標準是算法的分類準確率，分類準確率由測試集中分類正確的樣本數與樣本總數的比值得到，分類準確率越高，說明其對應的算法越合理。數據集通過本文設計的2組實驗可以獲得2組分類準確率，通過對比實驗結果，可以了解哪種方法比較合理。在本實驗中，使用了Anneal、crx、horse-colic、lung-cancer、sponge 5個數據集，實驗的分類準確率如表2所示。

從表2可以看到，使用子集匹配方法相對于使用數據清洗的方法分類準確率要高。

對于子集匹配方法，其方差和標準差如表3所示。

從表3可以看到，分散情況和實驗結果與其期望的偏差都不大，說明實驗是有效的。

從以上兩個實驗結果中可以看出，在面向不完備數據進行C4.5分類算法的改進時，進行特征選擇對不完備數據替換，尤其是在遞歸算法中，在每一個節點上的子集中對不完備數據進行替換，在同樣的替換規則下可以獲得比單純數據清洗更高的分類正確率，說明對分類算法面向不完備數據的改進是成功的。而對于每一個數據集的分類結果，正確率都比較高，說明對C4.5分類算法的改進也是成功的。

5 結語

針對不完備數據，本文將最高頻原理引入C4.5算法中，使得該算法能夠更好地處理不完備數據。應用最簡單的數據清洗思想：最高頻屬性值替換方法在進行特征選擇的子集上對不完備數據進行替換。實驗證明，本文算法在面向不完備數據時，能構造更簡單的C4.5算法，而且精度較高。本文結果可以證明在分類算法中用數據清洗的思想擴大分類算法本身的適用數據范圍，使分類算法能更好地處理不完備數據。

參考文獻：

[1] 吳章先.天翼大數據智能創未來數據共生態[EB/OL].http：//www.dca.org.cn/html/BDIC2017/index.html.

[2] 舒文豪.面向動態不完備數據的特征選擇模型算法研究[D].北京：北京交通大學，2015.

[3] 崔偉正.面向分類決策的不完備信息處理方法研究[D].長沙：國防科技大學，2013.

[4] 梁美蓮.不完備信息系統中數據挖掘的粗糙集方法[D].南寧：廣西大學，2005.

[5] 徐雄英.基于粗糙集的不完備信息系統的處理方法研究[D].呼和浩特：內蒙古大學，2012.

[6] 舒文豪.面向動態不完備數據的特征選擇模型與算法研究[D].北京：北京交通大學，2015.

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

[8] CLARK P， GRZYMALA-BUSSE J W， RZASA W. Consistency of incomplete data[J].Information Sciences，2015，322（5）：197-222.

[9] GRZYMALA-BUSSE J W. Characteristic relations for incomplete data：a generalization of the indiscemibility relation[C].Lecture Notes in Computer Science，2004：58-68.

[10] GRZYMALA-BUSSE J W， CLARK P G， KUEHUNHAUSEN M. Generalized probabilistic approximations of incomplete data[J].International Journal of Approximate Reasoning，2014，55（1）：180-196.

[11] CLARK P G， GRZYMALA-BUSSE J W， RZASA W. Mining incomplete data with singleton， subset and concept probabilistic approximations[J]. Information Sciences，2014，280：368-384.

[12] HAN J W， MICHELINE K.數據挖掘：概念與技術[M].范明，孟小峰，譯.北京：機械工業出版社，2001.

[13] QUINLAN J R. C4.5：Programs for machine learning[M]. San Mateo： Morgan Kauffman，1993.

[14] 光峰，姚程寬，盧燦舉，等.數據挖掘經典算法研究[J].商丘師范學院學報，2016，32（3）：44-47.

[15] 李然.粒計算的高效知識約簡算法與缺失數據處理[D].蘭州：蘭州大學，2006.

[16] LIU C Y，GUO H，HU W. A Schr（o）dinger formulation research for light beam propagation[J]. Science China Mathematics，2000，43（3）：312-322.

[17] 許朝陽.文本分類中特征選擇方法的分析和改進[J].計算機與現代化，2010（4）：37-39.

[18] SHAO J， RAO J N K. Standard errors for low income proportions estimated from stratified multi-stage samples[J]. The Indian Journal of Statistics， Series B（1960-2002），1993，55（3）：393-414.

[19] HASTIE T， TIBSHIRANI R， FRIEDMAN J. The elements of statistical learning[J]. Journal of the Royal Statistical Society，2009，167（1）：267-268.

（責任編輯：劉亭亭）