沈亮亮 蒙祖強(qiáng) 張兵 郭英明

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

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

DOI：10.11907/rjdk.172181

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引言

隨著計(jì)算機(jī)技術(shù)以及網(wǎng)絡(luò)通信技術(shù)的快速發(fā)展，數(shù)據(jù)規(guī)模在全世界范圍內(nèi)以指數(shù)級(jí)快速增長。在我國，隨著大數(shù)據(jù)時(shí)代的到來，數(shù)據(jù)規(guī)模正從每天TB級(jí)匯聚量向PB級(jí)發(fā)展，中國電信發(fā)布的信息顯示，至2017年3月末，其每天的數(shù)據(jù)匯聚量就達(dá)到200TB[1]。面對(duì)如此龐大的數(shù)據(jù)，如何從其中獲取知識(shí)正受到人們越來越多的關(guān)注。如何對(duì)現(xiàn)實(shí)領(lǐng)域中的大量數(shù)據(jù)進(jìn)行有效處理，從而挖掘出潛在有用的知識(shí)，已成為當(dāng)前數(shù)據(jù)挖掘、計(jì)算智能與機(jī)器學(xué)習(xí)的重要研究課題之一[2]。在大量數(shù)據(jù)中，有時(shí)會(huì)出現(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ù)挖掘、計(jì)算智能與機(jī)器學(xué)習(xí)等研究領(lǐng)域，分類算法是其核心。所以有必要對(duì)分類算法進(jìn)行改進(jìn)，以期擴(kuò)展分類算法適用的數(shù)據(jù)范圍。

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

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

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

刪除法的思想是直接去除包含不完備屬性值的數(shù)據(jù)樣本，不處理法的思想是將不完備屬性值當(dāng)成一個(gè)可以應(yīng)用的屬性值進(jìn)行計(jì)算。在面對(duì)不完備數(shù)據(jù)時(shí)，應(yīng)用不處理或者刪除方法時(shí)，會(huì)造成有用信息損失；應(yīng)用替補(bǔ)法時(shí)，無法保證替補(bǔ)的不完備數(shù)據(jù)完全正確，甚至替補(bǔ)上錯(cuò)誤的數(shù)據(jù)，對(duì)該數(shù)據(jù)的算法或者應(yīng)用會(huì)造成巨大影響?？傊?，這些方法的缺點(diǎn)是人為改變了數(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ù)時(shí)，利用單體近似、子集近似與概念概率近似的性質(zhì)進(jìn)行數(shù)據(jù)挖掘，并通過實(shí)驗(yàn)證明，對(duì)于給定的數(shù)據(jù)集，3種方法都是高效的。

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

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

2 預(yù)備知識(shí)

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)時(shí)認(rèn)為不需要；③有些因誤解而沒有記錄；④數(shù)據(jù)采集設(shè)備故障導(dǎo)致沒有記錄；⑤歷史原因或忽略了修改數(shù)據(jù)；⑥有些數(shù)據(jù)性價(jià)比太低而被忽略。

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

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

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

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

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

2.2 C4.5算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

缺失值=屬性值（MAX）

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

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

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

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

4 實(shí)驗(yàn)分析

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)語

針對(duì)不完備數(shù)據(jù)，本文將最高頻原理引入C4.5算法中，使得該算法能夠更好地處理不完備數(shù)據(jù)。應(yīng)用最簡單的數(shù)據(jù)清洗思想：最高頻屬性值替換方法在進(jìn)行特征選擇的子集上對(duì)不完備數(shù)據(jù)進(jìn)行替換。實(shí)驗(yàn)證明，本文算法在面向不完備數(shù)據(jù)時(shí)，能構(gòu)造更簡單的C4.5算法，而且精度較高。本文結(jié)果可以證明在分類算法中用數(shù)據(jù)清洗的思想擴(kuò)大分類算法本身的適用數(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] 舒文豪.面向動(dòng)態(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] 舒文豪.面向動(dòng)態(tài)不完備數(shù)據(jù)的特征選擇模型與算法研究[D].北京：北京交通大學(xué)，2015.

[7] 武森，馮小東，單志廣.基于不完備數(shù)據(jù)聚類的缺失數(shù)據(jù)填補(bǔ)方法[J].計(jì)算機(jī)學(xué)報(bào)，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].范明，孟小峰，譯.北京：機(jī)械工業(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é)報(bào)，2016，32（3）：44-47.

[15] 李然.粒計(jì)算的高效知識(shí)約簡算法與缺失數(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].計(jì)算機(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é)任編輯：劉亭亭）