基于概率相似度的不完備信息系統數據補齊算法
2009-01-01 00:00:00李萍吳祈宗
計算機應用研究 2009年3期
（北京理工大學 管理與經濟學院， 北京 100081）
摘 要：在決策屬性已知、條件屬性值分布不確定的情況下，用基于概率相似度原理和按決策屬性劃分系統的原則，對缺損數據進行填補，可使不完備決策信息系統的完備化具有較高可信度。
關鍵詞：粗糙集； 缺損數據； 概率相似度； 算法
中圖分類號：TP391 文獻標志碼：A
文章編號：10013695(2009)03088103
Completing data algorithms based on probability similarity
LI Ping， WU Qizong
(School of Management Economic， Beijing Institute of Technology， Beijing 100081， China)
Abstract:Based onprobability similarity and the system partition according to decision attribute in the condition of unknown data distribution， this paper put forward a new methodto improve the algorithm ofROUSTIDA ， which made a high reliability for the missing data of incomplete decision information system.
Key words：rough set; missing data; probability similarity; algorithm
利用粗糙集對數據進行分析處理已成為數據挖掘研究的新熱點。粗糙集理論在20世紀80年代初由Z.Pawlak提出，其主要思想是把那些無法確認的個體都歸屬于邊界線區域內，而這種邊界區域被定義為上近似集和下近似集，從而以不完全的信息或知識去處理一些不分明的現象，或依據所觀察到的不精確的結果對數據來進行分類[1]，粗糙集理論在機器學習、知識獲取、決策分析、模糊控制等方面得到了越來越多的應用。
一般來說，大型數據信息系統中往往存在殘缺的數據，對該類數據進行分析前都需要做數據預處理的工作，數據預處理包括簡單刪除不全的數據、將數據中空缺的屬性值作為特殊屬性來處理、利用統計學方法如Mean Completer算法對數據進行處理等，但以上方法對數據的補齊效果往往不能保證[2]?；诖植诩碚撝械牟环置麝P系，可以用數據中其他與殘缺數據相似的屬性值來對數據進行填補，這種填補盡可能地表現出了信息系統的基本特征和隱含的規律。文獻[3]利用基于決策獨立的原則，對ROUSTIDA算法進行改進，使得某樣本xi在決策屬性缺失時，選擇與它相似的無任何缺失值的對象的決策屬性值，消除了填補時決策規則中潛在的矛盾項；Kryszkiewicz[4，5]于1998年提出粗糙集中對象間存在相似關系，指出相似關系也是一種容差關系；在此相似關系基礎上，文獻[6~8]利用量化相似關系的理論，對樣本間的相似關系進行了定量的分析，并把量化引入ROUSTIDA算法中，從而提高了填補的效率；文獻[9]研究了在決策屬性無任何缺失時，如填補xi的某個條件屬性值時，從其他與其有相同決策屬性值的樣本中選擇，避免了出現條件屬性值一致，而決策屬性值不一致的情況；文獻[10]提出了以樣本間概率最大值作為相似度最大來進行樣本填補的思路。本文則討論了不完備信息系統在決策屬性無缺失的情況下，對條件屬性進行填補時，先采用按決策屬性對決策系統進行劃分，然后再以屬性值出現的概率來定義對象間的相似度，并在此基礎上對ROUSTIDA算法進行改進。
1 粗糙集相關理論
1.1 不完備信息系統
在粗糙集理論中，客觀世界可抽象為一個知識表達系統，其基本成分是研究對象的集合，關于這個對象的知識是通過指定對象的屬性和它們的屬性值來描述的[1]。
定義1 一個知識表達系統也是一個信息系統，可用一個四元組S=〈U，R，V，f〉來表示。
1）U={x1，x2，…，xn}是非空有限對象的集合，也稱之為論域。
2）R是屬性的非空有限集合，子集C和D分別稱為條件屬性集和決策屬性集。有R=C∪D，C∩D=。
3）V=∪r∈RVr表示屬性的集合，Vr是屬性R的取值范圍。
4）f=U×R→V代表一個信息函數，它指定U中的每個對象x的屬性值。
如果a∈A，使得對于某個對象而言，Va取值為空，則該信息系統稱之為不完備信息系統。
定義2[5] 在不完備信息系統中定義相似關系為
sim(A)={(x，y)∈S×S｜a∈A，a(x)= *∨a(y)= *∨a(x)=a(y)}
性質1 相似關系也是一種容差關系。
sim(A)=∩a∈Asim({a})
可辨識矩陣也稱分明矩陣或差別矩陣，由Skowron教授提出，在不完備信息系統下的擴充可辨識矩陣如下：
定義3 令不完備信息系統為S=〈U，R，V，f〉。其中：R是屬性集合，U={x1，x2，…，xn}是論域，ai(xj)是樣本xj在屬性ai上的取值，M(i，j)表示擴充的可辨識矩陣中第i行j列的元素，則擴充的可辨識矩陣M可定義為
M(i，j)={ak｜ak∈R∧ak(xi)≠ak(xj)∧
ak(xi)≠ *∧ak(xj)≠ *}
其中：i，j=1，…，n;*表示遺失值。
定義4 不完備信息系統S=〈U，A，V，f〉。其中：A={｜ai｜i=1，…，m}是屬性集，設xi∈U，則對象xi的遺失對象集MASi、對象xi的無差別對象集NSi和信息系統S的遺失對象集MOS分別定義為
MASi={ak｜ak(xi)=*，k=1，…，m}
NSi={j｜M(i，j)=，i≠j，j=1，…，n}
MOS={i｜MASi≠，i=1，…，n}
1.2 相似關系的量化與決策系統的劃分
ROUSTIDA算法利用無差別對象集之間的相似關系來對缺失數據進行填補，該填補是基于定性的相似關系，但一般對數據而言，對象xi與對象xj之間的相似程度是可以度量的。舉例來說對象xi={1，3， *，2， *，4}，與對象xj={ *，3， *，2， *，4}和xk={1，3，2，2， *，4}均存在相似關系，如屬性值服從某種分布，則認為xi與xk的相似程度同xi與xj的相似程度是不一樣的，在此基礎上很多文獻對相似關系進行了量化。
文獻[6~8]提出的xi與xj相似度，是假設信息系統表中各對象的屬性值是服從均勻分布X~U(a，b)，且屬性的值域Vk已知的情況下提出的。但現實世界中大量的數據并不是服從均勻分布的，如庫存數據、銷售數據等往往呈現近似二項分布、t分布、正態分布的特征。在數據的分布特征未知、且屬性的值域未定的情況下，以信息系統中屬性值出現的概率分布特征來進行相似度分析則更好，該種概率相似度與Mean Completer算法的不同之處在于，Mean Completer算法沒有考慮對象間的相似性及屬性間的相互依賴程度，它簡單地以出現頻率最大的屬性值出現對缺損數據進行填補。采用基于概率相似度原理，不僅考慮了數據的分布情況，而且考慮了對象的相似性，以各屬性的聯合概率來作為對象間相似的概率。
如果某個信息系統為決策屬性無缺失，而條件屬性值有缺失時，此時的不完備信息系統也稱之為不完備決策系統，在此只考慮單一決策表問題，因為多決策屬性一般均可以轉換為單一決策屬性來求解。令不完備決策系統為S=〈U，R，V，f〉，R=C∪g0gggggg是屬性集合，C為條件屬性，U={x1，x2，…，xm}是論域，Vd={d1，d2，…，dn}是決策屬性的值域，依據Vd將對象劃分為U=U1∪U2∪…∪Un，Ui為同一決策屬性值的論域。在此構造出一個子決策系統集為{S1，S2，…，Sn}，S=S1∪S2∪…∪Sn。該決策系統的子系統有以下性質：
a)i，j∈{1，2，…，n}，Si∩Sj=，i≠j
b)i，j∈{1，2，…，n}，Ui∩Uj=，i≠j
定義5 令不完備決策系統為S=〈U，R，V，f〉，R=C∪g0gggggg是屬性集合，U={x1，x2，…，xn}是論域，依據決策屬性值Vd={d1，d2，…，dn}對系統進行劃分，S=S1∪S2∪…∪Sn，Sl為決策系統中的某個子決策系統，U=U1∪U2∪…∪Un，Ul為該子系統對應的論域。ai(xj)是樣本xj在屬性ai上的取值，Pk(i，j)為對象xi與xj在屬性ak上取值相同的概率，決策子系統Si的改進量化相似關系矩陣T為
T(i，j)=0，i=jP(i，j)，i≠jP(i，j)=∏ak∈APk(i，j)
Pk(i，j)=1，當ak(xi)=ak(xj)∧ak(xi)≠ *∧ak(xj)≠ *
card{m｜xm∈Ul，ak(xm)=ak(xj)}/card(Ul)，
當ak(xi)= *∧ak(xj)≠ *
card{m｜xm∈Ui，ak(xm)=ak(xi)}/card(Ul)，
當ak(xi)≠ *∧ak(xj)= *
(card{m｜xm∈Ul，ak(xm)= *}/card(Ul))2，
當ak(xi)= *∧ak(xj)= *0 其他
則不完備決策子系統中對象xi的量化最相似對象集LSi為
LSi={xj｜P(i，j)=maxxk∈NSi{P(i，k)}，xi∈NSi，i≠j，j=1，2，…，n}其中：T（i，j)是由論域中對象兩兩相比，由其相似概率組成的矩陣，是一個依主角線對稱的矩陣；Pk(i，j)是對象xi與xj在關于屬性ak上的相似度，card(U)表示論域中對象的個數，當對象xi與xj在關于屬性ak上的值均缺失時，對象xi與xj的相似度要減??；P(i，j)是對象xi與xj在屬性集A上的相似度，是Pk(i，j)的所有ak∈A的乘積；LSi是指與對象xi相似且相似度最大的其他對象組成的集合 。
1.3 ROUSTIDA算法改進
采用基于概率相似度和決策系統劃分的思想，對原ROUSTIDA算法進行了如下變化。
輸入：不完備信息系統S0=〈U0，A，V，f〉；
輸出：完備信息系統Sr=〈Ur，A，V，f〉；
步驟1 根據決策屬性d對不完備信息系統S0劃分，U/IND（D）={U1，U2，…，Un}，該劃分所形成的子系統集{S01，S02，…，S0n}，對每個S0l∈{S01，S02，…，S0n}，分別計算初始可辨識矩陣M0，MAS0i和MOS0；令r=0；
步驟2 1）對于所有的i∈MOSr，計算LSri；
2)產生Sr+1l。
（1）對于iMOSr有ak(xr+1i)=ak(xri)，k=1，2，…，m。
（2）對于所有i∈MOSr，對所有k∈MASri作循環：如果card(LSri)=1，設j∈LSri，若ak(xrj)=*，則ak(xr+1i)=*，否則ak(xr+1i)=ak(xrj)。
（3）如果card(LSri）≥2，則按以下步驟來進行：
(a)如果存在j0和j1∈LSri，滿足(ak(xrj0)≠ *)∧(ak(xrj1)≠ *)∧(ak(xrj1)≠ak(xrj0)），則ak(xr+1i)= *；
(b)如果存在j0∈LSri，滿足ak(xrj0)≠ *，則ak(xr+1i)=ak(xrj0)，否則ak(xr+1i)= *。
3）如果Sr+1l=Srl，則結束循環，返回第3步；否則，計算M r+1，MASr+1i和MOSr+1，并重新計算LSr+1i。利用新的概率計算各對象間的量化相似度。
步驟3 Sr+1=Sr+11∪Sr+12∪…∪Sr+1n，形成如果信息系統中還有缺失值，則采用Conditioned Mean Completer算法來進行處理，處理完后結束本算法。
2 實例及結果
在進行實例分析時，如果所選取的對象較少，在6個以下時，數據表中屬性出現的概率往往體現不出二項分布、指數分布或正態分布的特征，而是呈現出近似均勻分布，不利于計算其相似度，因此，在此選擇一個對象為10個以上的數據庫表來進行分析。表1為某不完備決策系統，一共由12個對象組成，有5個條件屬性，其遺失屬性集為MOS={2，3，4，5，6，7，8，9，11，12}。
對該決策系統按決策屬性值的不同來進行劃分，如表2、3所示。改進的算法所補齊的數據見表中括號內的值，由于采用概率相似度LSi，因此對象間相似度完全一致的比較少，采用相似度最大的對象來進行填充，數據填充速度比較快，填充的效率也比較高，各決策子系統內對像間的相似度如表4、5所示。
3 結束語
本文主要研究了在決策屬性值已知、決策子系統數據分布未知的情況下，如何以定量來度量各對象間的相似度問題，對于數據量巨大的決策系統來說，如將決策系統依據決策屬性值劃分為一個個子決策系統，在子系統內采用概率分布特征來進行相似關系的量化，然后對每個子系統內的缺損數據進行填補，與定性相似關系算法相比，基于概率相似度算法的復雜度為O(｜A｜(｜U1｜2+｜U2｜2)+…+（｜Un2｜))，一般只需要幾步循環便可得到滿意的填補效果，而且該算法大大提高了缺損數據補齊過程中的計算速度。表1的缺損數據如用其他算法來進行補齊，得到的補齊結果與表2、3基本一致，說明了該算法的合理性。本文所提出的算法對條件屬性和決策屬性作出區分，在各子決策系統中，從數據分布的特點出發，以每個對象在屬性中取值的頻率近似作為該值在該屬性中的分布概率，對于數據量大、屬性較多、條件屬性值有缺失的大型信息系統來說，不失為一種良好的補齊算法。
參考文獻：
［1］劉清.Rough集及Rough推理[M].北京：科學出版社，2001：10100.
[2]王國胤. Rough集理論與知識獲取[M]. 西安：西安交通大學出版社， 2001：9399.
[3]張振華， 劉文奇. 一種基于粗糙集理論不完備數據的改進算法[J]. 計算機科學與工程， 2002，24（2）：4142.
[4]KRYSZKIEWICZM. Rough set approach to incomplete information system[J]. Information Sciences， 1998，112(14):3949.
[5]KRYSZKIEWICZM. Rules in incomplete information system[J].Information Science， 1998，113(34):274292.
[6]朱小飛，卓麗霞.一種基于量化容差關系的不完備數據分析方法[J]. 重慶工學院學報， 2005，19（5）：2325.
[7]周業明，林秀芹，曹之新，等. 基于粗糙集的不完備情報信息系統的完備化[J]. 軍事運籌與系統工程， 2007，21(2)：5053.
[8]張在美. 一種基于粗糙集的不完備信息處理方法研究[D]. 長沙：湖南大學， 2007.
[9]劉文軍. 基于粗糙集理論的不完備決策表的完備化方法[J]. 長沙電力學院學報:自然科學版， 2006，21（4）：6062.
[10]秦華妮. 基于量化相似關系的不完備決策信息系統的完備化算法[J]. 湖南工程學院學報， 2007，17（1）：6567.
