面向不完備數(shù)據(jù)的改進(jìn)C4.5算法研究

沈亮亮 蒙祖強 張兵 郭英明

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

關(guān)鍵詞：不完備數(shù)據(jù)；C4.5算法；分類算法

DOI：10.11907/rjdk.172181

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：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 引言

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

1 數(shù)據(jù)處理常用方法

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

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

刪除法的思想是直接去除包含不完備屬性值的數(shù)據(jù)樣本，不處理法的思想是將不完備屬性值當(dāng)成一個可以應(yīng)用的屬性值進(jìn)行計算。在面對不完備數(shù)據(jù)時，應(yīng)用不處理或者刪除方法時，會造成有用信息損失；應(yīng)用替補法時，無法保證替補的不完備數(shù)據(jù)完全正確，甚至替補上錯誤的數(shù)據(jù)，對該數(shù)據(jù)的算法或者應(yīng)用會造成巨大影響?？傊@些方法的缺點是人為改變了數(shù)據(jù)包含的信息結(jié)構(gòu)，扭曲了數(shù)據(jù)本來包含的有用信息。

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

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

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

2 預(yù)備知識

2.1 不完備數(shù)據(jù)

在數(shù)據(jù)中，含有缺失屬性值的數(shù)據(jù)稱為不完備數(shù)據(jù)，由不完備數(shù)據(jù)構(gòu)成的信息系統(tǒng)稱為不完備信息系統(tǒng)。

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

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

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

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

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

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

2.2 C4.5算法

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

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

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

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

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

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

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

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

C4.5算法可以遞歸實現(xiàn)，其基本算法如下：讀入訓(xùn)練集，構(gòu)造屬性集與樣本序號集，作為算法對應(yīng)的樣本集、屬性集與樣本序號集參數(shù)。

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

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

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

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

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

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

3 C4.5算法改進(jìn)

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

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

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

缺失值=屬性值（MAX）

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

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

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

結(jié)果說明，子集匹配方法比數(shù)據(jù)預(yù)處理方法的分類準(zhǔn)確率高，并且子集匹配方法也適用于不同的數(shù)據(jù)預(yù)處理方法。

4 實驗分析

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

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

從機器學(xué)習(xí)數(shù)據(jù)庫中選取5個真實數(shù)據(jù)集分析算法的性能，數(shù)據(jù)集的詳細(xì)情況如表1所示。

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

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

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

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

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

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

對于子集匹配方法，其方差和標(biāo)準(zhǔn)差如表3所示。

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

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

5 結(jié)語

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

參考文獻(xiàn)：

[1] 吳章先.天翼大數(shù)據(jù)智能創(chuàng)未來數(shù)據(jù)共生態(tài)[EB/OL].http：//www.dca.org.cn/html/BDIC2017/index.html.

[2] 舒文豪.面向動態(tài)不完備數(shù)據(jù)的特征選擇模型算法研究[D].北京：北京交通大學(xué)，2015.

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

[4] 梁美蓮.不完備信息系統(tǒng)中數(shù)據(jù)挖掘的粗糙集方法[D].南寧：廣西大學(xué)，2005.

[5] 徐雄英.基于粗糙集的不完備信息系統(tǒng)的處理方法研究[D].呼和浩特：內(nèi)蒙古大學(xué)，2012.

[6] 舒文豪.面向動態(tài)不完備數(shù)據(jù)的特征選擇模型與算法研究[D].北京：北京交通大學(xué)，2015.

[7] 武森，馮小東，單志廣.基于不完備數(shù)據(jù)聚類的缺失數(shù)據(jù)填補方法[J].計算機學(xué)報，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.數(shù)據(jù)挖掘：概念與技術(shù)[M].范明，孟小峰，譯.北京：機械工業(yè)出版社，2001.

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

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

[15] 李然.粒計算的高效知識約簡算法與缺失數(shù)據(jù)處理[D].蘭州：蘭州大學(xué)，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ìn)[J].計算機與現(xiàn)代化，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.

（責(zé)任編輯：劉亭亭）