基于相似關(guān)系向量的改進ROUSTIDA算法

丁春榮，李龍澍

1.安徽農(nóng)業(yè)大學(xué)信息與計算機學(xué)院，合肥230036

2.安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院，合肥230039

1 引言

粗糙集[1]理論是由波蘭科學(xué)家Paw lak在1982年提出的一種處理模糊、不精確知識和不完備信息的數(shù)學(xué)工具，在機器學(xué)習(xí)、數(shù)據(jù)挖掘等多個領(lǐng)域得到了廣泛的應(yīng)用。由于在現(xiàn)實中存在測量誤差、條件受限或不慎遺漏等種種因素，人們往往會得到部分數(shù)據(jù)缺失的不完備信息系統(tǒng)，如何對缺失數(shù)據(jù)進行必要的補充，這對信息系統(tǒng)的后續(xù)處理如屬性約簡、規(guī)則提取等操作具有非常重要的意義，展開這方面的研究也變行尤為重要。根據(jù)粗糙集理論中數(shù)據(jù)的不可分辨關(guān)系對缺失數(shù)據(jù)進行補齊處理，是目前常用的有效填補方法，這種填補法盡可能地表現(xiàn)出信息系統(tǒng)的基本特征的隱含規(guī)律。其中，最具有代表性的補齊算法是ROUSTIDA算法[2]。該算法對于所有的缺失屬性同等對待，補齊時按滿足條件的先后順序進行，容易引入決策沖突信息，并且在一些特殊情況下處理到一定的步驟后，會無法繼續(xù)填補下去。當(dāng)前，針對ROUSTIDA算法存在的缺陷它進行了廣泛研究。文獻[3-4]基于決策獨立的原則，對ROUSTIDA算法進行改進，使樣本X在決策規(guī)則缺失時，選擇與其相似的無任何缺失值的對象的決策屬性值進行填補，消除了填補后潛在的矛盾項；文獻[5]提出基于差異關(guān)系矩陣的數(shù)據(jù)補齊算法；文獻[6]提出了基于填補順序的補齊算法。K ryszkiewicz[7-8]于1998年提出粗糙集中對象之間存在著相似關(guān)系，指出相似關(guān)系也是一種容差關(guān)系；在此基礎(chǔ)上，文獻[9-12]利用量化相似關(guān)系的理論，將樣本間容差關(guān)系引入ROUSTIDA算法中，從而提高了缺失數(shù)據(jù)的填補效率。本文在保持ROUSTIDA算法良好的填補性能的基礎(chǔ)上對其進行了改進，提出一種基于相似關(guān)系向量的改進算法，為了盡量避免不一致決策表的產(chǎn)生，算法優(yōu)先填補決策屬性，并在決策屬性相同時填補條件屬性缺失值，擴展了原算法的使用范圍。通過實例說明改進的算法能有效提高補齊數(shù)據(jù)的準(zhǔn)確率，同時盡可能避免了決策規(guī)則沖突問題，在一定程度上降低了時間復(fù)雜度。

2 粗糙集理論基礎(chǔ)

定義1 量化相似關(guān)系[2]對于不完備信息系統(tǒng)S=(U，A，V，f)，A=C∪D是屬性集合，C∩D=φ，其中C={a1，a2，…，am-1}是條件屬性集，D={am}是決策屬性集，其中論域U={x1，x2，…，xn}，假設(shè)各屬性可能取值呈均勻分布，對于?ak∈A，其值域Ek=，對于任意對象xi∈U，有ak(xi)=的概率為1/|Ek|。因此給定兩個對象xj∈U，ak(xj)=，則對于ak(xj)=，xi在屬性ak上近似于xj的概率為：

則對象xi和xj在屬性ak所有取值上的聯(lián)合概率為：

通過量化相似關(guān)系定義可看出，R(xi，xj)可以度量對象xi和xj在屬性ak上的相似程度。對于一個決策信息系統(tǒng)而言，如果兩個對象條件屬性完全相同，應(yīng)盡量保持其決策屬性一致，以避免不相容決策，即盡量使決策規(guī)則相容，這個規(guī)則稱為決策規(guī)則獨立原則。由于不相容決策對以后的決策過程有較強的負面影響，因此在對決策屬性存在缺失數(shù)據(jù)的信息系統(tǒng)進行填補時，應(yīng)盡量遵循這個原則，避免出現(xiàn)不相容的決策規(guī)則。如果以定義1中所述的量化相似關(guān)系為基礎(chǔ)構(gòu)建可辨識矩陣對ROUSTIDA算法進行改進，填補結(jié)果也容易出現(xiàn)決策規(guī)則不相容的結(jié)果，因此，下面對量化相似關(guān)系進行了進一步的修改。

定義2 對于不完備信息系統(tǒng)S，am是決策屬性，其值域為Ek=，則對象xi和xj在決策屬性am上的決策相容關(guān)系定義為：

定義3 對于不完備信息系統(tǒng)S=(U，A，V，f)，可定義一個二元組作為量化相似關(guān)系向量L=(R，D)，其中R是定義1中的量化相似關(guān)系，D是定義2中的決策相容關(guān)系。

根據(jù)量化相似關(guān)系向量構(gòu)建量化相似關(guān)系矩陣如下所示。

定義4 量化相似關(guān)系矩陣M定義：

其中i，j=1，2，…，n，L(xi，xj)=(R(xi，xj)，D(xi，xj))。

矩陣中每個元素表示了相應(yīng)兩個樣本對象的相似程度。

定義5 對于信息系統(tǒng)S，A={ak|k=1，2，…，m}，是屬性集，設(shè)xi∈U，對象xi的缺失屬性集MASi和信息系統(tǒng)S的缺失對象集MOS定義如下：

對象xi的最大相似對象集NSi定義如下：

NSi是與對象xi相似度最大的對象集合。

3 基于相似關(guān)系向量的改進ROUSTIDA算法

由于不完備信息系統(tǒng)中缺失值的數(shù)量及分布不同，因此在許多情況下無法僅僅通過對初始擴充矩陣的一次運算就能補齊所有的缺失數(shù)據(jù)，往往需要經(jīng)過多次對擴充可辨識矩陣進行計算和完整化分析才能得到完備的信息系統(tǒng)。因此，可以設(shè)初始的信息系統(tǒng)為S0，相應(yīng)的擴充可辨識矩陣為M0，對象xi的缺失屬性集為MA，初始無差別對象集為N，初始缺失對象集為MOS0。第r次完整化分析后的信息系統(tǒng)為Sr，則相應(yīng)的Mr計算滿足以下定理：

定理1 設(shè)Mr+1=(Mr+1(i，j))n×n，r=0，1，…，則Mr+1(i，j)計算如下：

由上面定理可看出，數(shù)據(jù)填補過程中得到的信息系統(tǒng)Sr，其可辨識矩陣不需要重新建立，只要對Sr-1的Mr-1根據(jù)缺失數(shù)據(jù)的填補修改局部元素即可，從而大大降低了計算復(fù)雜性。

基于相似關(guān)系向量的改進ROUSTIDA算法步驟如下：

步驟1 對初始信息系統(tǒng)S0計算M0、MOS0和MA。

步驟2 （1）對于所有i∈MOSr，計算N。

（2）產(chǎn)生Sr+1：

①對于i?MOSr，則，k=1,2,…,m；

②對于?i∈MOSr，對所有ak∈MASri做如下操作：

（i）如果存在j0和j1∈滿足(ak(xj0r)≠*)∧

(ak(xj1r)≠*)∧(ak(xj0r)≠ak(xj1r))，則ak(xr+1i)=*；

（ii）否則，如果僅存在一個j0∈NSri，滿足ak(xrj0)≠*，

（iii）否則，如果?j∈NSi，都有

（3）如果Sr+1=Sr，則結(jié)束循環(huán)轉(zhuǎn)步驟3；否則，對Sr+1計算Mr+1、MOSr+1和，r=r+1，轉(zhuǎn)步驟2。

步驟3 如果信息系統(tǒng)還存在缺失值，可用取屬性中平均值（數(shù)字型）或最多出現(xiàn)值（符號型）的方法進行填補。

步驟4 結(jié)束。

4 仿真實驗

仿真實驗樣本選自文獻[13]中水泥窯控制算法表的部分樣本，如表1所示。分別采用ROUSTIDA算法和本文改進ROUSTIDA算法對實驗樣本進行補齊操作，補齊后的信息表結(jié)果如表2和表3所示。

4.1 結(jié)果分析

由表2可看出，經(jīng)ROUSTIDA算法補齊后，出現(xiàn)了實例x1與x2，x8與x9相互矛盾的情況，這是因為由原ROUSTIDA算法的可辨識矩陣M0可得出={1，3}，，={6，9}，={7，8}，算法執(zhí)行到步驟2進行填補時，對于如果存在j0和j1∈滿足，則。根據(jù)這個條件，算法執(zhí)行完步驟2后，每個有缺失值的對象都無法對缺失值進行填補，所以得到S1=S0，結(jié)束填補循環(huán)轉(zhuǎn)向步驟3。假設(shè)采用M ean Com pleter算法對所有對象a4屬性值進行填補，得到2.5，無論a4的值取2還是取3，都后導(dǎo)致實例x1與x2，x8與x9相互矛盾的結(jié)果。從實例可以看出，ROUSTIDA算法存在的不足之處有：

（1）由于無差別對象集NSi定義的局限性，導(dǎo)致算法實際上要經(jīng)過多次對擴充可辨識矩陣的計算和完整化分析，才能滿足終止條件。

（2）決策屬性的重要性沒有體現(xiàn)出來，這樣在填補過程中，容易導(dǎo)致決策規(guī)則沖突。

而采用本文提出的基于相似關(guān)系向量的改進ROUSTIDA補齊算法完全可以避免在補齊后導(dǎo)致決策沖突的結(jié)果。這是因為改進補齊算法每次在對缺失屬性值時行填補時，都是在決策屬性相同的前提下選擇最相似的對象對缺失屬性進行填補，有效地避免了決策規(guī)則矛盾問題，同時每次循環(huán)都能夠?qū)Ω嗟娜笔е颠M行充分的填補，因此降低了算法的時間復(fù)雜度。

4.2 時間復(fù)雜度分析

ROUSTIDA算法的時間復(fù)雜度為O(n2×k×p)，p為何能迭代的次數(shù)，當(dāng)存在大量數(shù)據(jù)時，每輪循環(huán)結(jié)束后都要重新計算擴充可辨識矩陣M，對算法的時間性能造成很大的影響。而改進的算法對擴充辨識矩陣進行了大幅度的減化，每個矩陣元素都是一個二元值，不僅在很大程序上減少了擴充矩陣的維數(shù)，減少了臨時存儲空間，同時也減輕了后面算法的運算量，改進后的算法的時間復(fù)雜度是O(n2×p)。

4.3 算法比較

為了進一步測試新算法性能，從UCI國際機器學(xué)習(xí)數(shù)據(jù)庫[14]中選擇Echocardiogram、Hepatitis和House等3個數(shù)據(jù)集作為測試集，利用高斯正態(tài)分布隨機函數(shù)，隨機抽取50%的樣本作為訓(xùn)練集。測試標(biāo)準(zhǔn)為：對于同一個樣本，如果根據(jù)不同的規(guī)則能推出不同的結(jié)果，或者根據(jù)已有決策規(guī)則無法判斷其決策屬性，均判定為識別錯誤。對比算法采用ROUSTIDA算法、概率法和特定值法。算法的填補正確率為預(yù)測值正確的樣本數(shù)量/缺失數(shù)據(jù)樣本總數(shù)，實驗3次，測試結(jié)果如表4所示。

表3 用本文算法補齊的信息表

表1 水泥窯控制算法表部分樣本

表2 ROUSTIDA算法補齊后信息表

表4 算法的平均填補正確率（%）

影響填補正確率的主要因素是訓(xùn)練集所能提供的數(shù)據(jù)關(guān)系及內(nèi)在規(guī)律是否足夠，比如House數(shù)據(jù)集由于各數(shù)據(jù)之間的內(nèi)在關(guān)系較為緊密，因此填補正確率要高于同樣缺失率的Hepatitis數(shù)據(jù)集，而Echocargiogram數(shù)據(jù)集的數(shù)據(jù)內(nèi)在規(guī)律相對較少，因此即使含有缺失值的樣本所占比例并不多，但填補正確率卻不高。

5 結(jié)束語

針對ROUSTIDA算法的不足提出一個基于相似關(guān)系向量的改進ROUSTIDA算法。首先，本文算法優(yōu)先填補決策屬性，在決策屬性相同的前提下再選擇相似度最大的對象對缺失屬性進行填補，因為對于每個存在缺失值的對象而言，相似對象的近似概率不盡相同，所以填補后有效地減少了數(shù)據(jù)填補導(dǎo)致的決策規(guī)則矛盾問題。其次，相似關(guān)系向量矩陣的元素是由向量構(gòu)成，因此比原ROUSTIDA算法中的擴充可辨識矩陣要簡化，從而降低了空間復(fù)雜度。最后，在數(shù)據(jù)補齊過程中，由于每次選取相似度最大的對象對缺失屬性進行填補，提高了每次循環(huán)的補齊數(shù)目，加快了算法的收斂速度，對于數(shù)據(jù)量大，屬性較多，缺失屬性值也較多的信息系統(tǒng)而言，該算法在一定程度上降低了時間復(fù)雜度。因此，本文算法對于數(shù)據(jù)量大、屬性較多的不完備信息系統(tǒng)而言不失為一種良好的補齊算法。

[1]Paw lak Z.Rough sets[J].International Journal of Computer Information Science，1982，11：341-356.

[2]王國胤.Rough集理論與知識獲取[M].西安：西安交通大學(xué)出版社，2001：46-97.

[3]張振化，劉文奇.一種基于粗糙集理論不完備數(shù)據(jù)的改進算法[J].計算機科學(xué)與工程，2002，24（2）：41-42.

[4]田樹新，吳曉平，王紅霞.一個基于改進的ROUSTIDA算法的數(shù)據(jù)補齊方法[J].海軍工程大學(xué)學(xué)報，2011，23（5）：11-15.

[5]潘巍，王陽生，楊宏戟.粗糙集理論中新的針對不完備信息系統(tǒng)的處理方法研究[J].計算機科學(xué)，2007，34（6）：158-161.

[6]劉偉.基于粗集理論不完備數(shù)據(jù)的改進算法[J].吉林師范大學(xué)學(xué)報：自然科學(xué)版，2007，8（3）：113-114.

[7]K ryszkiewicz M.Rough set approach to incomplete information system[J].Information Sciences，1998，113（3/4）：274-292.

[8]K ryszkiewicz M.Rules in incomplete information system[J].Information Science，1998，113（3/4）：274-292.

[9]朱小飛，卓麗霞.一種基于量化容差關(guān)系的不完備數(shù)據(jù)分析方法[J].重慶工學(xué)院學(xué)報，2005，19（5）：23-25.

[10]張在美.一種基于粗糙集的不完備信息處理方法研究[D].長沙：湖南大學(xué)，2007.

[11]秦華妮.基于量化相似關(guān)系的不完備決策信息系統(tǒng)的完備化算法[J].湖南工程學(xué)院學(xué)報，2007，17（1）：65-67.

[12]李萍，吳祈宗.基于概率相似度的不完備信息系統(tǒng)數(shù)據(jù)補齊算法[J].計算機應(yīng)用研究，2009，26（3）：881-883.

[13]曾黃麟.粗集理論其及應(yīng)用——關(guān)于數(shù)據(jù)推理的新方法[M].重慶：重慶大學(xué)出版社，1998：153-154.

[14]Blake C M.UCI machine learning repository[DB/OL].（2005）[2012-06-01].http：//www.ics.uci.edu/～m learn/M LRepository.htm l.