基于容差計算的非完備信息系統屬性約簡算法

梁 寶 華

(巢湖學院信息工程學院 安徽 合肥 238000)

基于容差計算的非完備信息系統屬性約簡算法

梁 寶 華

(巢湖學院信息工程學院 安徽 合肥 238000)

對于有缺損值的非完備信息系統約簡，多數算法利用容差關系求信息量，但此類算法需消耗大量時間計算容差，導致屬性約簡質量、消耗的時間及空間復雜度均不理想。為了有效提高求容差類計算效率，引入一個與相容類信息量等價的計算公式。以此為基礎，提出一種屬性約簡算法，使時間復雜度降為O(|C|2|U|)，空間降為O(|C||U|)。最后，通過實例和實驗分析并驗證了算法的有效性和可行性。

粗糙集 屬性約簡 非完備信息系統 相容類

0 引 言

粗糙集理論[1-2]是由波蘭數學家Pawlak教授于1982年提出的，是一種處理不完全、不精確和模糊性數據的數學工具。屬性約簡是粗糙集理論研究的重要內容之一，指在不影響原知識表達能力的情況下，通過消除冗余屬性的方法，從而獲得較簡潔的知識表達。經典的粗糙集理論在完備信息系統中已有大量的研究，提出了基于正區域、基于差別矩陣、基于信息熵及啟發式屬性約簡算法[3-5,14-19]。然而在現實生活中，由于對數據的理解、獲取方法的限制等不可控因素，使得實際處理的數據是一個不完備信息系統，即部分對象屬性值是未知的。這種數據缺失會影響粗糙集理論向實用化方向推廣。

為了解決不完備信息系統對粗糙集理論應用化的影響，研究者們利用相容關系[6]、相似關系等，給出一系列有效的屬性約簡算法，如文獻[7]給出了差別矩陣的二進制形式,文獻[8-10]提出相容關系相似矩陣并給出一種不完備決策表的屬性約簡算法。不完備決策表的屬性約簡算法多數以“信息量”[10]為啟發式信息，張等在文獻[11]中提出一些改進方法，經研究發現，文獻[11]存在大量重復掃描數據對象的不足。為了減少掃描數據的次數，無需大量空間存儲相容類信息，本文根據相容類元素間的對稱性、自反性特征，提出一種快速計算相容信息量的方法，有效提高屬性約簡效率。最后通過實例及實驗驗證算法的有效性和正確性。

1 相關概念

設信息系統S=(U,A,V,f)，其中U為論域，A=C∪D，P?C，C為條件屬性，D為決策屬性；V是屬性集A的值域；f是從屬性到值域的映射。

定義1[5]若a∈C,且有f(x,a)=*(*為缺損值)，則稱此信息系統是不完備的，否則稱為完備信息系統。

定義2[6]由P決定的相容關系T為：

T(P) ={(x,y)∈U×U|?a∈P,f(x,a)

=f(y,a)∨f(x,a)=*∨f(y,a)=*}

(1)

由T(P)定義可得相容類定義為：

TP(x)={y|y∈U∧TP(x,y)}

(2)

顯然，相容類TP(x)滿足自反性、對稱性。

定義3[11]屬性集P?C的信息量定義為：

(3)

其中U={x1,x2,…,xn},|X|為集合X的基數。

定義4[11]屬性集B關于決策屬性D的條件信息量定義為：

I(B|D)=I(B∪D)-I(B)

定義5[11]在不完備信息S中，屬性a∈P?C的重要度定義為：

SigP(a)=I(P|D)-I((P∪{a})|D)

(4)

定義6[11]在非完備信息系統S中，屬性P是C關于D的一個約簡，則要同時滿足下述兩個條件：

(1)I(P|D)=I(C|D)

(2) ?a∈P?I((P-{a})|D)≠I(C|D)

2 改進屬性約簡算法

2.1 相容類計算分析

在不完備信息系統的屬性約簡中，多數算法需計算信息量。由于計算方法的不當，消耗大量的時間和空間資源。如文獻[9]計算信息量的思想是將每一對象與其他|U|-1個對象進行比較，這樣若對屬性集P求信息量，有大量重復的計算，文獻[10]對其進行改進，時間大約只需文獻[9]同等條件下的一半。

現通過實例說明如下，設有一不完備決策表，如表1所示。

表1 不完備決策

Ta1(1)={1,2,4,7}Ta1(2)={1,2,4,7}

Ta1(3)={3,4,5,7}Ta1(4)={1,2,3,4,5,6,7,8}

Ta1(5)={3,4,5,7}Ta1(6)={4, 6,7,8}

Ta1(7)={1,2,3,4,5,6,7,8}Ta1(8)={4, 6,7,8}

T{a1,a2}(1)={1,2,4,7}=T{a1,a2}(2)

T{a1,a2}(3)={3,4,5,7}=T{a1,a2}(5)

T{a1,a2}(4)={1,2,3,4,5,6,7,8}=T{a1,a2}(7)

T{a1,a2}(6)={4, 6,7,8}=T{a1,a2}(8)

T{a1,a2,a3}(1)={1,2}T{a1,a2,a3}(2)={1,2}

T{a1,a2,a3}(3)={3,4,5,7} T{a1,a2,a3}(4)={3,4,5,7}

T{a1,a2,a3}(5)={3,4,5,7}T{a1,a2,a3}(6)={6}

T{a1,a2,a3}(7)={3,4,5,7}T{a1,a2,a3}(8)={8}

根據以上計算相容類過程，發現計算相容類T(P)時，出現大量的重復比較， 可總結為以下幾點性質：

性質1TP(x)中所有對象在屬性集上取值均屬于不可區分對象。

證明：TP(x)中所有元素均為與x樣本在屬性P的取值相等，即x與TP(x)中所有其他元素在屬性P上不可區分，證畢。

性質2TP(x)?TP∪ai(x),ai∈C-P

證明：對于?y∈TP∪ai(x)，根據相容類定義可知，y與TP∪ai(x)中的所有元素無不可區分，由于P?(P∪ai)，所以，y與TP(x)上所有元素也均不可區分，即y∈TP(x)，因為y具有任意性，TP(x)?TP∪ai(x)，證畢。

性質3 若|U/ai|=1或|U/ai|=2且對象在屬性ai上取值有*的，則TP(x)=TP∪ai(x)。

證明：因為|U/ai|=1，即所有樣本在屬性ai上取值相同，即Tai(x)=U。對于?y∈TP(x)，有y與TP(x)中所有元素在屬性P均不可區分。所以必有y在屬性P∪ai都不可區分，即，y∈TP∪ai(x)。因為y具有任意性，所以得到若|U/ai|=1且?y∈TP(x)時，y∈TP∪ai(x)，即TP(x)?TP∪ai(x)。又由性質2可得TP(x)?TP∪ai(x)，所以得TP(x)=TP∪ai(x)。|U/ai|=2且在屬性ai上取值有缺損值，由于缺損值與其他所有樣本在ai上均不可區分，所以等價于|U/ai|=1的情況，證畢。

2.2 改進相容類計算方法

由于相容類具有自反性、對稱性，所以信息量計算時，存在大量的重復性計算，為了避免這一現象的發生，現定義信息量Inf(P)如下：

信息量計算分析如下：

(5)

性質4Inf(P)與定義3I(P)信息是等價的。

(6)

算法1 改進相容類計算：Inf(P∪ai)且ai∈C-P

輸入：不完備信息表S=(U,A,V,f),Inf(P),ai

//在相容類計算過程中,U不斷剪枝成U′

輸出：Inf(P∪ai)

intInfP( )

{

sum= 0;

將所有樣本按屬性P進行劃分;

{

else

deleteU/PifromU

}

ifexistssubsetof*then

returnsum;

}

2.3 新的屬性約簡算法

定義7 在不完備信息系統S中，屬性P關于決策屬性D的條件信息量為：

Inf(P|D)=Inf(P)-Inf(P∪D)

(7)

定義8 在不完備信息系統S中，屬性b關于屬性組B的重要程度為：

(8)

性質5Inf(P)的值越大，區分能力越弱，當Inf(P)=0時，此時的P即為所求的屬性約簡集。

算法2 新的屬性約簡算法

輸入：U,C,D

輸出：Core//屬性約簡集

Step1 U=U′,Core=?,C′=C；

Subset=?;SubsetD=?

//Subset存儲U在條件屬性下的子劃分

//SubsetD存儲U在決策屬性下的劃分；

Step2 計算C′中每個條件屬性在決策屬性D下的條件信息量Inf(Ci∪Core|D)，并選出最小的信息量對應的條件屬性Ck;

Core=Core∪Ck

Subset=U/Ck;SubsetD=U/Core∪D;

C′=C-Ck；

Step3 if (C′≠?∧Inf(Core|D)≠0)

轉Step2；

Step4 return Core

3 實例與實驗分析

3.1 屬性約簡實例

以表1的數據為例，求U在各條件屬性上的劃分為：

U/a4={{1,3,6,7,8},{2,4,5}}

其中帶下劃線的一組為缺損值，所以各條件屬性的信息量分別為：

同理，相對各條件屬性在決策屬性D下加細劃分分別為：

U/(a4∪D)={{1,7},{2,4,5},{3,8},{6}}

其對應的信息量為：

Inf(a1∪D)=8,Inf(a2∪D)=11

Inf(a3∪D)=7,Inf(a4∪D)=5

則：

由于a1與a4的值最小，所以區分能力最強，設選擇屬性a1加入Core中得Core={a1}，舍棄基數為1的子劃分，所以Subset={{1,2},{3,5},{6,8},{4,7}},SubsetD={{1,2},{5},{4,7}}。繼續加入其他屬性并進行加細得：

U/(Core∪{a3}∪D)={{1,2},{5,4,7}}

U/(Core∪{a4}∪D)={{1,7},{2,4},{4,5}}

3.2 實驗分析

為了比較同類算法與本文算法的約簡效果，實驗使用的硬件配置為：Intel?CoreTMi7-4712MQ,CPU主頻2.30GHz,4GB內存，軟件為Win7系統及VS2012平臺。實驗采用UCI數據庫中的9個數據集進行驗證，數據集分別為Post,Zoo,Hepatilis,AutoMPG,Dermatologh,Car,Chess,Mushroom,Nursery(為方便描述表格中分別用D1～D9表示)，具體數據描述如表2所示，表2中的Data為各類數據集名稱，|U|為樣本數，|C|為條件屬性數，NO為分類數，DataType為數據類型，Comp為是否完備性。

表2 UCI數據集

表3 三種算法約簡效果表

續表3

Data算法b算法cTimeSpaceRLbTimeSpaceRLcD10.01930.000980.01610.00098D20.02060.008350.01840.00835D30.18990.014560.18220.01456D40.29010.016250.20140.01625D50.21460.012170.17030.01217D60.40810.011560.38900.01156D71.88340.1227291.07520.122729D81.64280.180440.93150.18044D91.78530.102881.03230.10288

(1) 從表3的實驗數據可以看出，以上三種算法在約簡質量上，與常見約簡算法的結果相當，說明這種約簡算法是有效可行的。算法a對于數據集Zoo,Dermatologh,Chess約簡結果稍微有點偏差，很明顯算法b和算法c的約簡結果更具有準確性。

(3)Post是非完備的，Zoo具有完備性，雖然Zoo的樣本多且屬性也多，由于Post是非完備數據集，對于那些缺損值增加了挖掘的干擾，對于算法a增加了信息量的計算，但對算法b、算法c的屬性重要性計算影響不大。所以，在進行約簡時數據集Post雖然比Zoo樣本數及屬性個數少，但約簡時卻與Zoo的相仿佛。

(4) 從時間性能上看，算法b和算法c明顯優于算法a，通過表3的運行時間長短可看出。算法b與算法c整體差不多，但算法c要略優于算法b，因為算法b需計算正區域，所以要浪費一定的時間，當然，隨著數據集樣本數及屬性數的增多，這段時間占整個約簡的比例會越來越小。

4 結 語

[1]PawlakZ.Roughsettheoryanditsapplicationstodataanalysis[J].CyberneticsandSystems,1998,29(7):661-668.

[2]PawlakZ,Grzymala-BusseJ,SlowinskiR,etal.Roughsets[J].CommunicationsoftheACM,1995,38(11):88-95.

[3] 徐章艷,劉作鵬,楊炳儒,等.一個復雜度為max(O(|C||U|),O(|C|2|U/C|))的快速屬性約簡算法[J].計算機學報,2006,29(3):391-399.

[4] 張文修,米據生,吳偉志.不協調目標信息系統的知識約簡[J].計算機學報,2003,26(1):12-18.

[5] 王國胤,于洪,楊大春.基于條件信息熵的決策表約簡[J].計算機學報,2002,25(7):759-766.

[6] 王國胤.不完備信息系統的粗糙集擴展[J].計算機研究與發展,2002,39(8):1238-1243.

[7]McBrienP.Temporalconstraintsinnon-temporaldatamodellinglanguages[C]//27thInternationalConferenceonConceptualModeling,Barcelona,Spain,2008:412-425.

[8]ZhouJ,XuE,LiY,etal.Anewattributereductionalgorithmdealingwiththeincompleteinformationsystem[C]//2009InternationalConferenceonCyber-EnabledDistributedComputingandKnowledgeDiscovery,2009:12-19.

[9] 黃兵,周獻中,張蓉蓉.基于信息量的不完備信息系統屬性約簡[J].系統工程理論與實踐,2005,25(4):55-60.

[10] 李艷紅,鄂旭,周津,等.信息量的不完備信息系統屬性約簡方法[J].小型微型計算機系統,2012,33(3):641-645.

[11] 張清國,鄭雪峰,張明德,等.信息量不完備決策表屬性約簡的一種新算法[J].計算機工程與應用,2010,46(2):19-21,33.

[12] 謝娟英,李楠,喬子芮.基于領域粗糙集的不完整決策系統特征選擇算法[J].南京大學學報(自然科學),2011,47(4):383-390.

[13] 紀霞,李龍澍,齊平.基于屬性分辨度的不完備決策表屬性約簡算法[J].華南理工大學學報(自然科學版),2013,41(1):83-88.

[14] 冀素琴,石洪波,呂亞麗.基于粒計算與區分能力的屬性約簡算法[J].模式識別與人工智能,2015,28(4):327-334.

[15] 葛浩,李龍澍,楊傳健.基于相對分辨能力的屬性約簡算法[J].系統工程理論與實踐,2015,35(6):1595-1603.

[16] 陳宸,趙軍.一種新的基于二進制分辨矩陣的屬性約簡方法[J].計算機應用與軟件,2013,30(9):123-127.

[17] 馬垣.形式概念中的內涵虧值及屬性約簡[J].模式識別與人工智能,2013,26(12):1096-1105.

[18] 楊春林.基于信息熵的屬性約簡在多屬性決策中的應用[J].數學的實踐與認識,2013,43(3):97-102.

[19] 王世強,張登福,畢篤彥,等.基于模糊粗糙集和蜂群算法的屬性約簡[J].中南大學學報(自然科學版),2013,44(1):172-178.

ATTRIBUTE REDUCTION ALGORITHM FOR INCOMPLETE INFORMATION SYSTEM BASED ON TOLERANCE COMPUTATION

Liang Baohua

(InformationEngineeringInstitute,ChaohuUniversity,Hefei238000,Anhui,China)

For incomplete information system reduction with defective values, most algorithms use the tolerance relation to compute the amount of information, but this kind of algorithm consumes a large amount of time computing tolerance, which leads to the quality of attribute reduction and the time and space complexity are not ideal. In order to improve the computation efficiency of the tolerance class effectively, a formula for calculating the equivalent information of the compatible class is introduced. Based on it, an attribute reduction algorithm is proposed, which reduces the time complexity to O(|C|2|U|)andreducesthespacetoO(|C||U|).Finally,theexamplesandexperimentalanalysisshowthattheproposedalgorithmisefficientandfeasible.

Rough set Attribute reduction Incomplete information system Compatible class

2016-03-30。安徽省省級質量工程項目(2013tszy31)；安徽省高等學校省級自然科學研究項目(KJ2013Z231)。梁寶華，副教授，主研領域：粗糙集，數據挖掘。

TP

ADOI:10.3969/j.issn.1000-386x.2017.04.051