王方心，潘 巍，吳立鋒，金聲震，李曉娟

（1.首都師范大學(xué) 信息工程學(xué)院，北京100048；2.首都師范大學(xué) 高可靠嵌入式系統(tǒng)技術(shù)北京市工程研究中心，北京100048；3.首都師范大學(xué) 電子系統(tǒng)可靠性技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室，北京100048）

0 引 言

在模式識(shí)別中，人們通過(guò)對(duì)各種形式的數(shù)據(jù)進(jìn)行處理和分析，進(jìn)而對(duì)事物和現(xiàn)象進(jìn)行描述、辨認(rèn)、分類(lèi)和解釋。上述過(guò)程主要是通過(guò)對(duì)數(shù)據(jù)的聚類(lèi)和分類(lèi)來(lái)實(shí)現(xiàn)的。傳統(tǒng)的識(shí)別方法 （如基于決策樹(shù)模型的ID3算法、基于統(tǒng)計(jì)模型的貝葉斯分類(lèi)方法和基于神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)分類(lèi)方法等等）對(duì)屬性完備的數(shù)據(jù)的處理和分類(lèi)已經(jīng)取得了令人滿意的效果，應(yīng)用也比較廣泛。

然而，在實(shí)際獲取信息的過(guò)程中，由于種種原因，所得到的數(shù)據(jù)往往是不完備的［1］，這主要是由以下幾個(gè)方面造成的：①有些信息暫時(shí)無(wú)法獲取；②有些信息可能是因?yàn)檩斎霑r(shí)認(rèn)為不重要、忘記填寫(xiě)或?qū)?shù)據(jù)的理解錯(cuò)誤而遺漏；③由于數(shù)據(jù)采集設(shè)備的故障、存儲(chǔ)介質(zhì)的故障、傳輸媒體的故障、一些人為因素等原因丟失；④有些對(duì)象的某個(gè)或某些屬性是不可用的；⑤有些信息是被認(rèn)為不重要的；⑥獲取某些信息的代價(jià)過(guò)大；⑦系統(tǒng)實(shí)時(shí)性要求較高，即要求得到這些信息前迅速做出判斷或決策。由于現(xiàn)今比較常用的識(shí)別方法大多針對(duì)完備數(shù)據(jù)，當(dāng)存在數(shù)據(jù)缺失，尤其是關(guān)鍵屬性的數(shù)據(jù)缺失時(shí)，經(jīng)常會(huì)給數(shù)據(jù)分析造成干擾，如①數(shù)據(jù)處理效率的下降；②分析和處理數(shù)據(jù)時(shí)復(fù)雜性的增加；③不完備數(shù)據(jù)和完備數(shù)據(jù)間的偏差，而這些干擾會(huì)給后續(xù)的決策以及響應(yīng)造成諸多不便。

目前，已經(jīng)有一些方法來(lái)解決屬性值缺失時(shí)的數(shù)據(jù)處理與分類(lèi)問(wèn)題，它們主要基于以下3個(gè)思路：①直接將具有缺失數(shù)據(jù)的樣本刪除［2］，這種方法主要應(yīng)用于數(shù)據(jù)缺失量較少而且刪除的樣本數(shù)據(jù)對(duì)最終結(jié)果的分析不會(huì)造成重大影響的情況。當(dāng)缺失數(shù)據(jù)較多時(shí)，這類(lèi)方法往往會(huì)丟失大量有用信息［3］；②使用能夠處理缺失數(shù)據(jù)的識(shí)別方法，但這類(lèi)方法一般計(jì)算復(fù)雜度較高，應(yīng)用場(chǎng)合也比較有限；③當(dāng)具有缺失數(shù)據(jù)的樣本較多但每個(gè)樣本缺失的數(shù)據(jù)相對(duì)較少時(shí)，通過(guò)研究數(shù)據(jù)屬性之間的分布狀況，可首先對(duì)缺失的數(shù)據(jù)進(jìn)行補(bǔ)齊，然后再利用已有的對(duì)完備數(shù)據(jù)進(jìn)行處理的方法進(jìn)行識(shí)別。用這類(lèi)方法補(bǔ)齊的數(shù)據(jù)能夠較好地保留數(shù)據(jù)的原有信息，是解決數(shù)據(jù)缺失問(wèn)題的一種比較好的途徑。

根據(jù)數(shù)據(jù)樣本的分布狀況進(jìn)行數(shù)據(jù)補(bǔ)齊的主要思路是在完備數(shù)據(jù)子表中找出不完備樣本的完備近鄰，并利用這些完備近鄰的相應(yīng)屬性值對(duì)不完備樣本的缺失數(shù)據(jù)進(jìn)行補(bǔ)齊，如KNN等方法。在距離測(cè)度上，通?？梢允褂脷W氏距離、馬氏距離和灰色關(guān)聯(lián)度等。此外，大量的研究表明，屬性的重要程度對(duì)于數(shù)據(jù)的處理也起著非常重要的作用。例如，采用屬性重要度加權(quán)的歐氏距離來(lái)計(jì)算樣本之間的距離能夠提高聚類(lèi)的正確率［4］。

綜上，本文結(jié)合屬性重要度和灰色關(guān)聯(lián)度，提出了一種新的數(shù)據(jù)補(bǔ)齊方法。首先，按照屬性重要度確定各個(gè)屬性的補(bǔ)齊順序；其次，對(duì)于當(dāng)前要補(bǔ)齊的缺失樣本，將所有完備樣本分別與其進(jìn)行兩兩比較，并選擇灰色關(guān)聯(lián)度最大的完備樣本對(duì)樣本進(jìn)行補(bǔ)齊。實(shí)驗(yàn)結(jié)果表明，即使在很高的數(shù)據(jù)缺失比率下，本文方法仍能很好地進(jìn)行補(bǔ)齊，并能取得較高的識(shí)別率，是一種理想的數(shù)據(jù)補(bǔ)齊方法。

1 常用的數(shù)據(jù)補(bǔ)齊方法

數(shù)據(jù)補(bǔ)齊方法主要通過(guò)研究數(shù)據(jù)表中每個(gè)屬性下各個(gè)值之間 （縱向）或每條樣本之間的 （橫向）關(guān)系得到數(shù)據(jù)分布的規(guī)律和模型，進(jìn)而對(duì)缺失屬性進(jìn)行合理的推斷和補(bǔ)齊。這些方法包括：均值法：該方法用完備數(shù)據(jù)集中需被補(bǔ)齊屬性的平均值來(lái)進(jìn)行補(bǔ)齊，使用起來(lái)比較方便、計(jì)算量較小，在屬性值分布較為集中時(shí)能夠取得比較好的效果；概率法：該方法通過(guò)統(tǒng)計(jì)每個(gè)屬性中各個(gè)值的出現(xiàn)頻率，從中找出出現(xiàn)頻率最大的值進(jìn)行缺失數(shù)據(jù)的補(bǔ)齊，使用起來(lái)也較為簡(jiǎn)便；回歸預(yù)測(cè)法［5，6］：該方法通過(guò)分析每條樣本中各個(gè)屬性之間的關(guān)系，建立各個(gè)屬性之間的關(guān)系模型，進(jìn)而對(duì)缺失數(shù)據(jù)進(jìn)行回歸預(yù)測(cè)和補(bǔ)齊；多重插補(bǔ)的方法［7］：該方法估計(jì)出待插補(bǔ)的值，然后再加上不同的噪聲，形成多組可選插補(bǔ)值，最后根據(jù)某種選擇依據(jù)，選取最合適的插補(bǔ)值；Hot Deck和Cold Deck補(bǔ)齊方法：該方法在完備數(shù)據(jù)中尋找與缺失數(shù)據(jù)在某種距離上最為接近的一個(gè)或多條樣本，利用這些樣本的屬性值對(duì)缺失數(shù)據(jù)進(jìn)行補(bǔ)齊，使得結(jié)果更加合理和準(zhǔn)確。Hot Deck利用缺失數(shù)據(jù)的樣本所在的數(shù)據(jù)集的完備數(shù)據(jù)進(jìn)行補(bǔ)齊，Cold Deck則利用另一張同類(lèi)的數(shù)據(jù)表對(duì)缺失數(shù)據(jù)進(jìn)行補(bǔ)齊。事實(shí)上，距離尺度的選擇以及如何利用距離最近的屬性值進(jìn)行補(bǔ)齊都是影響最終效果的重要因素，目前常用的距離尺度包括歐氏距離、馬氏距離、隸屬度函數(shù)和灰色關(guān)聯(lián)度等。文獻(xiàn) ［8］中提出一種利用基于灰色關(guān)聯(lián)度的KNN的數(shù)據(jù)補(bǔ)齊算法，但由于KNN算法本身的缺陷［9］使得該方法在使用上有所限制。文獻(xiàn) ［10］提出一種利用灰色關(guān)聯(lián)度進(jìn)行重復(fù)補(bǔ)齊的方法，首先用平均值法進(jìn)行補(bǔ)齊，再計(jì)算不完備數(shù)據(jù)與完備數(shù)據(jù)的灰色關(guān)聯(lián)度，并選擇近鄰數(shù)據(jù)進(jìn)行二次補(bǔ)齊，并由此進(jìn)行多次補(bǔ)齊直至與前一次補(bǔ)齊的數(shù)據(jù)值偏差達(dá)到收斂；這樣的收斂條件一是會(huì)影響補(bǔ)齊算法的速度，不適合在實(shí)時(shí)性要求較高的場(chǎng)合中使用，二是不當(dāng)?shù)氖諗織l件會(huì)使得補(bǔ)齊過(guò)程陷入局部的死循環(huán)，給數(shù)據(jù)補(bǔ)齊造成困難。

2 基于屬性重要度和灰色關(guān)聯(lián)度的數(shù)據(jù)補(bǔ)齊方法

本文提出了屬性重要度和灰色關(guān)聯(lián)度相結(jié)合的數(shù)據(jù)補(bǔ)齊方法。首先，計(jì)算每個(gè)屬性的重要度，并以此確定數(shù)據(jù)補(bǔ)齊時(shí)的先后順序；其次，針對(duì)當(dāng)前要補(bǔ)齊的樣本，利用灰色關(guān)聯(lián)度，在完備數(shù)據(jù)集中找出與其關(guān)聯(lián)度最大的完備數(shù)據(jù)，對(duì)當(dāng)前樣本的缺失數(shù)據(jù)進(jìn)行補(bǔ)齊。

2.1 屬性重要度

多數(shù)情況下，人們假設(shè)數(shù)據(jù)集的屬性是完全隨機(jī)缺失（MCAR）的，并且完備數(shù)據(jù)與不完備數(shù)據(jù)的分布特性是相同的。因此，為了使得數(shù)據(jù)更加便于識(shí)別，所使用的距離衡量尺度應(yīng)該能夠反映原有數(shù)據(jù)的分布特點(diǎn)。同樣，數(shù)據(jù)的補(bǔ)齊過(guò)程也應(yīng)該能夠體現(xiàn)這些特點(diǎn)。在一張數(shù)據(jù)表中，每個(gè)條件屬性都會(huì)影響決策屬性，各個(gè)條件屬性值的共同影響使得數(shù)據(jù)在多維空間上呈現(xiàn)出特定的空間關(guān)系，而這種關(guān)系會(huì)最終影響識(shí)別的結(jié)果。與此同時(shí)，每個(gè)條件屬性對(duì)決策屬性的影響又是不同的，在由與決策屬性關(guān)聯(lián)度較高的條件屬性組成的空間中，不同類(lèi)別的數(shù)據(jù)能夠較為清晰地被分辨出來(lái)，而在由與決策屬性關(guān)聯(lián)度較低的條件屬性組成的空間中，不同類(lèi)別的數(shù)據(jù)分布較為混亂 （如圖1所示）。因此，屬性的重要度可以作為一個(gè)能夠體現(xiàn)原始數(shù)據(jù)分布特點(diǎn)的參數(shù)。

圖1 不同屬性空間中數(shù)據(jù)的分布情況

2.1.1 基于屬性依賴度的屬性重要度［11］

利用屬性刪除前后的屬性集的依賴度之差來(lái)計(jì)算屬性重要度

式中：card（）——集合的勢(shì)，γ——屬性依賴度，R——所有條件屬性集合，條件屬性C∈R，為X的下近似集，sig（C）為屬性C的相對(duì)依賴度。這種計(jì)算屬性重要度方法表征了該屬性對(duì)于整個(gè)論域的分類(lèi)能力的貢獻(xiàn)大小。

2.1.2 基于互信息熵的屬性重要度計(jì)算方法［12］

式中：H （·）——該屬性的熵，c——條件屬性，d——決策屬性。這種方法利用條件屬性與決策屬性之間互信息的大小來(lái)衡量屬性的重要程度，用信息論的觀點(diǎn)對(duì)條件屬性的性質(zhì)進(jìn)行分析。

2.1.3 本文的屬性重要度定義

本文中，屬性重要度的計(jì)算方法如下，假設(shè)數(shù)據(jù)表中樣本的任意一個(gè)條件屬性為C，決策屬性為Di（i＝1，2，…，m，表示有m個(gè)決策類(lèi)），則條件屬性C的屬性重要度為

式中：Maxi、Mini——屬性C在Di類(lèi)上的最大值和最小值，di——在 ［Mini，Maxi］上與 ［Mink，Maxk］（k≠i）的非交叉區(qū)域。

如圖2所示，假設(shè)數(shù)據(jù)表中共有3個(gè)決策類(lèi) （Y1，Y2和Y3），圖中的橫線表示條件屬性a的屬性值的取值范圍。

圖2 屬性重要度的確定

可以發(fā)現(xiàn)，在決策類(lèi)Y1中，屬性a的取值范圍與其它類(lèi)別并無(wú)交叉部分，所以如果某個(gè)樣本的屬性a的值在此范圍內(nèi)，就可以直接將該樣本劃歸為Y1類(lèi)。此時(shí)，屬性a對(duì)Y1類(lèi)的重要度為1。同時(shí)，Y2，Y3中，屬性a的取值范圍有交叉現(xiàn)象，當(dāng)某個(gè)樣本的屬性a的值出現(xiàn)在交叉區(qū)域，就無(wú)法直接根據(jù)屬性a判斷該樣本的類(lèi)別，但當(dāng)某個(gè)樣本的屬性a的值在b4段或b5段時(shí)，仍能僅根據(jù)屬性a判斷其類(lèi)別。因此，屬性a對(duì)某一決策類(lèi)的重要度為非交叉區(qū)域占屬性a的總體取值范圍的比重大小。如對(duì)于Y2來(lái)說(shuō)，屬性a的重要度為b4／b2。同樣，屬性a對(duì)全體決策類(lèi)的重要度為在其對(duì)于各個(gè)決策類(lèi)的重要度之和，即b1＋b4／b2＋b5／b3。本文算法中，將據(jù)此確定屬性重要度，從而確定補(bǔ)齊過(guò)程中各個(gè)屬性的補(bǔ)齊順序。

相較于傳統(tǒng)的屬性重要度的定義方法，本文方法更加客觀也更加直觀，能夠清晰地描述各個(gè)條件屬性對(duì)不同決策類(lèi)別的分類(lèi)能力：例如，在圖2中，屬性值在b1范圍內(nèi)的樣本一定屬于Y1類(lèi)，利用該屬性就能夠直接判別樣本是否屬于Y1類(lèi)。同理，由于Y2和Y3有交集，因此對(duì)于交集范圍內(nèi)的樣本，無(wú)法僅根據(jù)屬性a明確地確定歸屬。綜上，這種屬性重要度的定義方法能夠清楚地刻畫(huà)某一屬性對(duì)整個(gè)樣本分類(lèi)的重要程度。

2.2 灰色關(guān)聯(lián)度

樣本之間的對(duì)比往往不是很精確的，做不到非白即黑，此時(shí)需要有指標(biāo)進(jìn)行衡量?；疑P(guān)聯(lián)度是衡量?jī)蓚€(gè)樣本相似程度的一種度量方法，它將數(shù)據(jù)看作是一個(gè)灰關(guān)聯(lián)因子集，其中有參考序列和比較序列，每個(gè)參考序列與所有比較序列構(gòu)成灰色子空間，各個(gè)灰色子空間構(gòu)成灰色空間。灰色關(guān)聯(lián)度使用整體比較，是有參考系的、有測(cè)度的比較［13］。

若

為參考序列

為比較序列。

且定義X0（k）與Xi（k）的關(guān)聯(lián)系數(shù)為

則X0與Xi的灰色關(guān)聯(lián)度為

這種關(guān)聯(lián)度的定義方式體現(xiàn)了序列之間對(duì)應(yīng)點(diǎn)的平均相似程度，從這個(gè)角度能夠較好地體現(xiàn)兩個(gè)序列的相似性和關(guān)聯(lián)程度。

2.3 數(shù)據(jù)補(bǔ)齊步驟

為了充分利用不完備數(shù)據(jù)中的信息，本文會(huì)將每一個(gè)補(bǔ)齊后的樣本加入到原有的完備數(shù)據(jù)集中，將其用于下一個(gè)缺失樣本的補(bǔ)齊。在這種情況下，補(bǔ)齊樣本的加入順序?qū)ψ罱K的數(shù)據(jù)識(shí)別會(huì)產(chǎn)生一些影響。因此，本文首先從最初的完備數(shù)據(jù)子表中計(jì)算每個(gè)條件屬性的重要度，優(yōu)先補(bǔ)齊重要度高的屬性。這種處理方式一方面可以減少整個(gè)數(shù)據(jù)表在補(bǔ)齊過(guò)程中的不確定性，另一方面會(huì)為后續(xù)缺失樣本的補(bǔ)齊提供盡可能多的確定信息。

假設(shè)數(shù)據(jù)表T含有n個(gè)條件屬性和1個(gè)決策屬性 （假設(shè)共有k個(gè)決策類(lèi)），并且表中有m個(gè)樣本，每個(gè)樣本的類(lèi)標(biāo)簽d為已知。算法具體步驟如下：

（1）將數(shù)據(jù)表T拆分為完備數(shù)據(jù)表Tc和不完備數(shù)據(jù)表Tq。

（2）利用式 （3）計(jì)算Tc中的每個(gè)條件屬性的屬性重要度Sig（Ci）（i＝1，2，…，n），并根據(jù)Sig（Ci）的大小將Tq中的數(shù)據(jù)進(jìn)行重新排序，將缺失重要屬性的數(shù)據(jù)排在前列，優(yōu)先進(jìn)行數(shù)據(jù)補(bǔ)齊，排序后的新表為T(mén)x。例如：若完備表中有4個(gè)屬性，它們的屬性重要度順序?yàn)?［2，1，3，4］，則在不完備數(shù)據(jù)表中依次存放缺失第2、1、3、4條屬性值的樣本數(shù)據(jù)。當(dāng)樣本同時(shí)缺失多個(gè)屬性時(shí)，則按照缺失屬性的重要度之和來(lái)進(jìn)行數(shù)據(jù)補(bǔ)齊，例如，當(dāng)存在同時(shí)缺失2、1屬性和缺失2、3屬性的樣本時(shí)，則優(yōu)先對(duì)前者進(jìn)行數(shù)據(jù)補(bǔ)齊。

（3）依次取出Tx中的樣本t（c1，c2，…，cn，d），根據(jù)d的值，找出Tc中決策屬性為d的子樣本集Tcs，然后分別將t和Tcs中缺失屬性所在的列刪除。例如：若不完備樣本t缺失第二個(gè)屬性，且t的決策屬性為1，則在完備數(shù)據(jù)表中找出所有決策屬性為1的子樣本數(shù)據(jù)集，并刪除t和該子樣本數(shù)據(jù)集中所有樣本的第二個(gè)屬性。

（4）根據(jù)式 （4）、式 （5）分別計(jì)算t和子樣本數(shù)據(jù)集Tcs中每個(gè)樣本的灰色關(guān)聯(lián)度。

（5）選擇Tcs中與t關(guān)聯(lián)度最大的樣本，用其對(duì)應(yīng)屬性上的值對(duì)t中的缺失數(shù)據(jù)進(jìn)行補(bǔ)齊。

（6）將補(bǔ)齊后的數(shù)據(jù)t添加到Tc中，并將其從Tx中刪除，重復(fù) （3）、（4）、（5）、（6）直至全部缺失數(shù)據(jù)補(bǔ)齊完畢，即Tx為空。

3 不完備數(shù)據(jù)補(bǔ)齊算法的評(píng)價(jià)方法

在評(píng)價(jià)數(shù)據(jù)補(bǔ)齊算法性能的時(shí)候，通常采用在原有完備表的基礎(chǔ)上，人為地使之缺失某些值，然后利用該算法進(jìn)行補(bǔ)齊后，比較補(bǔ)齊后的值與原有值的平均誤差，以其作為評(píng)價(jià)補(bǔ)齊算法性能的指標(biāo)。雖然該評(píng)價(jià)方法在某種意義上來(lái)說(shuō)是較為有效的，但在某些領(lǐng)域中 （如分類(lèi)識(shí)別），這樣的評(píng)價(jià)方法并不能夠有效評(píng)估補(bǔ)齊的數(shù)據(jù)對(duì)分類(lèi)識(shí)別性能的影響。另外，通常在實(shí)際應(yīng)用中，原值往往是不存在的，所以該評(píng)價(jià)方法并不實(shí)用。

此外，現(xiàn)實(shí)生活中大多數(shù)的數(shù)據(jù)缺失的模式都屬于MCAR，而且通常認(rèn)為具有缺失數(shù)據(jù)的樣本與具有完備數(shù)據(jù)的樣本具有相同的分布特性［5］。因此，一方面，補(bǔ)齊后數(shù)據(jù)表中的樣本數(shù)據(jù)應(yīng)該盡可能地被識(shí)別，另一方面，數(shù)據(jù)表中的原有完備數(shù)據(jù)部分的識(shí)別率應(yīng)當(dāng)優(yōu)于補(bǔ)齊前的識(shí)別率，即補(bǔ)齊后的數(shù)據(jù)不能造成原有完備數(shù)據(jù)識(shí)別率的下降。

由此，本文提出了不完備數(shù)據(jù)補(bǔ)齊算法的評(píng)價(jià)標(biāo)準(zhǔn)：

（1）比較補(bǔ)齊前后整個(gè)數(shù)據(jù)的識(shí)別情況。在數(shù)據(jù)補(bǔ)齊前，若在完備數(shù)據(jù)表Tc中能夠正確識(shí)別的樣本個(gè)數(shù)為g，Tc的樣本總數(shù)為f，Tq的樣本總數(shù)為h，則補(bǔ)齊前Tc識(shí)別率I1＝g／f；補(bǔ)齊后，Tc的樣本總數(shù)為m（m＝f＋h），補(bǔ)齊后能夠被識(shí)別的樣本個(gè)數(shù)為s，則補(bǔ)齊后的識(shí)別率I2＝s／m；最后比較I1和I2的值，I2—I1越大則算法越有效。

（2）比較原有完備數(shù)據(jù)在補(bǔ)齊前與補(bǔ)齊后的識(shí)別率變化情況，觀察補(bǔ)齊前后屬性分布的變化。在進(jìn)行補(bǔ)齊前，對(duì)于Tc，完備數(shù)據(jù)的識(shí)別率為I1；補(bǔ)齊后，再對(duì)整個(gè)數(shù)據(jù)表進(jìn)行識(shí)別，其中原有完備數(shù)據(jù)Tc能夠被正確識(shí)別的樣本數(shù)為y，則完備數(shù)據(jù)的識(shí)別率I3＝y(tǒng)／f，則I3—I1越大算法越有效。

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

本實(shí)驗(yàn)選用UCI數(shù)據(jù)庫(kù)中的Tae（teaching assistance value）（屬性值也有離散型也有連續(xù)型），Hayes－Roth（屬性值均為離散型）和Iris（屬性值均為連續(xù)型）數(shù)據(jù)集，分別在屬性缺失比例為5%、10%、15%、20%的情況下，每個(gè)缺失比例下進(jìn)行10次實(shí)驗(yàn)，分別采用直接將缺失屬性數(shù)據(jù)刪除、最大概率法 （如果是離散數(shù)據(jù)直接用出現(xiàn)頻率最高的值進(jìn)行補(bǔ)齊，如果是連續(xù)數(shù)據(jù)則出現(xiàn)頻率最高的鄰域的中心值進(jìn)行補(bǔ)齊；鄰域取該屬性值的最小間隔）、基于歐式距離的K（k＝6）鄰域補(bǔ)齊方法、基于灰色關(guān)聯(lián)度的重復(fù)補(bǔ)齊方法［13］和基于屬性重要度和灰色關(guān)聯(lián)度的補(bǔ)齊方法對(duì)這些缺失屬性的數(shù)據(jù)表進(jìn)行補(bǔ)齊，最后用留一法對(duì)補(bǔ)齊的數(shù)據(jù)進(jìn)行識(shí)別并計(jì)算識(shí)別率。結(jié)果見(jiàn)表1。

表1 在缺失屬性的不同數(shù)據(jù)集上使用不同方法進(jìn)行數(shù)據(jù)補(bǔ)齊后識(shí)別的正確識(shí)別率

當(dāng)不使用任何數(shù)據(jù)補(bǔ)齊方法時(shí)，即直接刪除含有缺失數(shù)據(jù)的樣本時(shí)，3個(gè)表的樣本識(shí)別率隨著樣本數(shù)據(jù)缺失比例的增加迅速下降。這樣的結(jié)果對(duì)后

續(xù)的識(shí)別和分析是不利的，因此對(duì)不完備數(shù)據(jù)進(jìn)行補(bǔ)齊是十分有必要的。

從表1可以發(fā)現(xiàn)，本文方法在對(duì)3個(gè)具有不同特性的數(shù)據(jù)集進(jìn)行補(bǔ)齊后，都能達(dá)到最高的分類(lèi)性能。即使數(shù)據(jù)集的缺失比率很高時(shí)，也能很好地保持系統(tǒng)的分類(lèi)性能以及識(shí)別率。

下面將對(duì)上述各個(gè)數(shù)據(jù)表的條件屬性分布特點(diǎn)進(jìn)行分析，以此證明本文所定義的屬性重要度能很好地描述各個(gè)屬性對(duì)于分類(lèi)的重要性。

Tae表共有151個(gè)樣本，每個(gè)樣本均有5個(gè)屬性，共有3個(gè)決策類(lèi)。如表2所示，在原完備數(shù)據(jù)表中第1個(gè)和第4個(gè)屬性的重要度為0，因?yàn)樗鼈兊娜≈祪H有1和2，而且在每一個(gè)決策類(lèi)中都存在這兩個(gè)值，僅依據(jù)這兩個(gè)屬性根本不能夠確定任何樣本的類(lèi)別。因此，對(duì)于僅缺失這兩個(gè)屬性的樣本，將其放在最后進(jìn)行補(bǔ)齊。

表2 Tae數(shù)據(jù)表各屬性相對(duì)各決策屬性的重要度和屬性重要度

同理，各個(gè)條件屬性在不同缺失比例下的屬性重要度如表3所示，本文據(jù)此對(duì)具有缺失數(shù)據(jù)的樣本進(jìn)行排序。

表3 Tae數(shù)據(jù)表各屬性在不同數(shù)據(jù)缺失比例下的屬性重要度 （Sig）

在不同的數(shù)據(jù)缺失比例下，應(yīng)用本文方法對(duì)Tae數(shù)據(jù)表進(jìn)行補(bǔ)齊。在補(bǔ)齊前后，原有完備樣本的識(shí)別率如圖3所示?？梢园l(fā)現(xiàn)，當(dāng)缺失數(shù)據(jù)的比例增加后，本方法顯示出了魯棒的性能優(yōu)勢(shì)，數(shù)據(jù)補(bǔ)齊后，原有完備樣本的識(shí)別率得到了提高。

圖3 Tae數(shù)據(jù)表填補(bǔ)前后完備數(shù)據(jù)識(shí)別率比較

Iris表共有150個(gè)樣本，每個(gè)樣本均有4個(gè)連續(xù)屬性值，共3類(lèi)。各屬性在數(shù)據(jù)完備和缺失不同比例數(shù)據(jù)時(shí)的重要度見(jiàn)表4和表5。通過(guò)分析可以發(fā)現(xiàn)，Iris數(shù)據(jù)表的第3和第4個(gè)屬性對(duì)于數(shù)據(jù)分類(lèi)有著關(guān)鍵作用，特別在類(lèi)別1中，根據(jù)它們即可以直接確定樣本的歸類(lèi)，在其它類(lèi)別中，它們?cè)陬?lèi)與類(lèi)之間的交叉部分也較小，加之該數(shù)據(jù)表本身的識(shí)別率較高，所以利用各種方法進(jìn)行補(bǔ)齊之后的識(shí)別率相距并不太大。

表4 Iris數(shù)據(jù)表各屬性相對(duì)各決策屬性的重要度和屬性重要度

表5 Iris數(shù)據(jù)表各屬性的屬性重要度 （Sig）

在不同的數(shù)據(jù)缺失比例下，應(yīng)用本文方法對(duì)Iris數(shù)據(jù)表進(jìn)行補(bǔ)齊。在補(bǔ)齊前后，原有完備樣本識(shí)別率如圖4所示。

圖4 Iris數(shù)據(jù)表填補(bǔ)前后完備數(shù)據(jù)識(shí)別率比較

實(shí)驗(yàn)表明：即使缺失比例不斷增加，本文方法仍能顯示出良好的性能。對(duì)于Iris表而言，雖然在屬性缺失比例為5%時(shí)，本文方法補(bǔ)齊后的識(shí)別率 （95.53%）并不是最高，但依然接近最高識(shí)別率 （96%）。

此外，當(dāng)缺失比例增高時(shí)，出現(xiàn)了識(shí)別率提升的情況。本文認(rèn)為，Iris表本身的數(shù)據(jù)分布已較為清晰，識(shí)別率很高，只有少部分?jǐn)?shù)據(jù)存在交叉分布的情況。因此，當(dāng)缺失比例增加時(shí)，那些處于交叉區(qū)域的樣本產(chǎn)生缺失數(shù)據(jù)的概率也隨之增大。此外，本文采用與含有缺失數(shù)據(jù)樣本具有最大關(guān)聯(lián)度的完備樣本的相應(yīng)數(shù)據(jù)進(jìn)行補(bǔ)齊，因此這些樣本在補(bǔ)齊后會(huì)更接近完備樣本，其不確定性進(jìn)一步降低，因此最后的識(shí)別率也就會(huì)有所升高。

Hayes－Roth表共有160條樣本，每個(gè)樣本均有4個(gè)離散屬性，共3類(lèi)。各屬性在數(shù)據(jù)完備和缺失不同比例數(shù)據(jù)時(shí)的重要度見(jiàn)表6和表7。由于此表為離散數(shù)據(jù)表，且存在大量重復(fù)離散值，個(gè)別屬性值的缺失對(duì)屬性重要度的影響幾乎為0，因此即使在屬性缺失比例明顯不同的情況下，屬性重要度仍基本相同。其中第2個(gè)、第3個(gè)和第4個(gè)屬性對(duì)決策屬性的影響程度相近，而第1個(gè)屬性對(duì)于決策屬性的影響幾乎為0。

表6 Hayes－Roth數(shù)據(jù)表各屬性相對(duì)各決策屬性的重要度和屬性重要度

表7 Hayes－Roth數(shù)據(jù)表各屬性的屬性重要 （Sig）

在不同的數(shù)據(jù)缺失比例下，應(yīng)用本文方法對(duì)Hayes－Roth數(shù)據(jù)表進(jìn)行補(bǔ)齊。在補(bǔ)齊前后，原有完備樣本識(shí)別率如圖5所示。

圖5 Hayes－Roth數(shù)據(jù)表填補(bǔ)前后完備數(shù)據(jù)識(shí)別率比較

5 結(jié)束語(yǔ)

對(duì)缺失數(shù)據(jù)的數(shù)據(jù)表進(jìn)行補(bǔ)齊會(huì)引入新的不確定性，它會(huì)影響后續(xù)的識(shí)別和分類(lèi)效果。本文結(jié)合屬性重要度和灰色關(guān)聯(lián)度，提出了一種新的數(shù)據(jù)補(bǔ)齊方法，能使補(bǔ)齊后的數(shù)據(jù)具有高識(shí)別率。同時(shí)，本文還提出了判斷數(shù)據(jù)補(bǔ)齊性能的評(píng)價(jià)標(biāo)準(zhǔn)，即補(bǔ)齊后的數(shù)據(jù)不能影響原有數(shù)據(jù)的識(shí)別率，它能對(duì)數(shù)據(jù)補(bǔ)齊方法做出客觀的評(píng)價(jià)。實(shí)驗(yàn)結(jié)果表明，本文方法即使在很高的數(shù)據(jù)缺失比率下仍能很好地對(duì)數(shù)據(jù)進(jìn)行補(bǔ)齊，并能取得較高的識(shí)別率，是一種理想的數(shù)據(jù)補(bǔ)齊方法。

［1］Matthias Templ Alexander Kowarik，Peter Filzmoser.Iterative stepwise regression imputation using standard and robust methods ［J］.Computational Statistics and Data Analysis，2011，55 （10）：2793－2806.

［2］SCI2Sthematic public websites.Imputation method ［EB／OL］.［2013－05－05］.http：／／sci2s.ugr.es／MVDM／.

［3］Eduardo R Hruschka，Antonio J T Garcia，Estevam R Hruschka Jr，et al.On the influence of imputation in classification：Practical issues ［J］.Journal of Experimental ＆ Theoretical Artificial Intelligence，2009，21 （1）：43－58.

［4］ZHANG Zhonglin，CAO Zhiyu，LI Yuantao.Research based on euclid distance with weights of k＿means algorithm ［J］.Journal of Zhengzhou University（Engineering Science），2010，31 （1）：89－92 （in Chinese）.［張忠林，曹志宇，李元韜.基于加權(quán)歐式距離的k＿means算法研究 ［J］.鄭州大學(xué)學(xué)報(bào)，2010，31 （1）：89－92.］

［5］ZHAO Hongbo，JIANG Feng，ZENG Huifen，et al.Rough set approach to data completion based on similarity ［J］.Computer Science，2011，38 （11）：167－171 （in Chinese）.［趙洪波，江峰，曾惠芬，等.一種基于加權(quán)相似性的粗糙集數(shù)據(jù)補(bǔ)齊方法 ［J］.計(jì)算機(jī)科學(xué)，2011，38 （11）：167－171.］

［6］TIAN Shuxin，WU Xiaoping，WANG Hongxia.Improved method for data reinforcement based on ROUSTID ［J］.Journal of Naval University of Engineering，2011，23 （5）：11－15（in Chinese）.［田樹(shù)新，吳曉平，王紅霞.一種基于改進(jìn)的ROUSTIDA算法的數(shù)據(jù)補(bǔ)齊方法 ［J］.海軍工程大學(xué)學(xué)報(bào).2011，23 （5）：11－15.］

［7］Rhian M Daniel，Michael G Kenward.A method for increasing the robustness of multiple imputation ［J］.Computational Statistics and Data Analysis，2012，56 （6）：1624－1643.

［8］Zhang Shichao.Nearest neighbor selection for iteratively kNN imputation ［J］.Syst Software，2012，81 （11）：2541－2552.http：／／dx.doi.org／10.1016／j.jss.2012.05.073.

［9］Van Hulse J，Khoshgoftaar T M.Incomplete－case nearest neighbor imputation in software measurement data ［C］／／IEEE International Conference on Information Reuse and Integration，2007：630－637.

［10］Su Yijuan.Multiple imputation method for missing values by gray relation analysis ［J］.Computer Engineering and Appli－cations，2009，45 （15）：169－172.

［11］WANG Guoyin，YAO Yiyu，YU Hong.A survey on rough set theory and application ［J］.Chinese Journal of Computers，2009，32 （7）：1229－1246 （in Chinese）.［王國(guó)胤，姚一豫，于洪.粗糙集理論與應(yīng)用研究綜述 ［J］.計(jì)算機(jī)學(xué)報(bào)，2009，32 （7）：1229－1246］

［12］LIU Lele，TIAN Weidong.Quantitative association rules mining based on mutual information entropy of attributes ［J］.Computer Engineering，2009，35 （14）：38－40 （in Chinese）.［劉樂(lè)樂(lè)，田衛(wèi)東.基于屬性互信息熵的量化關(guān)聯(lián)規(guī)則挖掘［J］.計(jì)算機(jī)工程，2009，35 （14）：38－40.］

［13］Yang Yingjie，Robert John.Grey sets and greyness ［J］.Information Science，2012，185 （1）：249－264.