基于容差計(jì)算的非完備信息系統(tǒng)屬性約簡(jiǎn)算法

梁 寶 華

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

基于容差計(jì)算的非完備信息系統(tǒng)屬性約簡(jiǎn)算法

梁 寶 華

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

對(duì)于有缺損值的非完備信息系統(tǒng)約簡(jiǎn)，多數(shù)算法利用容差關(guān)系求信息量，但此類(lèi)算法需消耗大量時(shí)間計(jì)算容差，導(dǎo)致屬性約簡(jiǎn)質(zhì)量、消耗的時(shí)間及空間復(fù)雜度均不理想。為了有效提高求容差類(lèi)計(jì)算效率，引入一個(gè)與相容類(lèi)信息量等價(jià)的計(jì)算公式。以此為基礎(chǔ)，提出一種屬性約簡(jiǎn)算法，使時(shí)間復(fù)雜度降為O(|C|2|U|)，空間降為O(|C||U|)。最后，通過(guò)實(shí)例和實(shí)驗(yàn)分析并驗(yàn)證了算法的有效性和可行性。

粗糙集 屬性約簡(jiǎn) 非完備信息系統(tǒng) 相容類(lèi)

0 引 言

粗糙集理論[1-2]是由波蘭數(shù)學(xué)家Pawlak教授于1982年提出的，是一種處理不完全、不精確和模糊性數(shù)據(jù)的數(shù)學(xué)工具。屬性約簡(jiǎn)是粗糙集理論研究的重要內(nèi)容之一，指在不影響原知識(shí)表達(dá)能力的情況下，通過(guò)消除冗余屬性的方法，從而獲得較簡(jiǎn)潔的知識(shí)表達(dá)。經(jīng)典的粗糙集理論在完備信息系統(tǒng)中已有大量的研究，提出了基于正區(qū)域、基于差別矩陣、基于信息熵及啟發(fā)式屬性約簡(jiǎn)算法[3-5,14-19]。然而在現(xiàn)實(shí)生活中，由于對(duì)數(shù)據(jù)的理解、獲取方法的限制等不可控因素，使得實(shí)際處理的數(shù)據(jù)是一個(gè)不完備信息系統(tǒng)，即部分對(duì)象屬性值是未知的。這種數(shù)據(jù)缺失會(huì)影響粗糙集理論向?qū)嵱没较蛲茝V。

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

1 相關(guān)概念

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

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

定義2[6]由P決定的相容關(guān)系T為：

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

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

(1)

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

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

(2)

顯然，相容類(lèi)TP(x)滿(mǎn)足自反性、對(duì)稱(chēng)性。

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

(3)

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

定義4[11]屬性集B關(guān)于決策屬性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]在非完備信息系統(tǒng)S中，屬性P是C關(guān)于D的一個(gè)約簡(jiǎn)，則要同時(shí)滿(mǎn)足下述兩個(gè)條件：

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

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

2 改進(jìn)屬性約簡(jiǎn)算法

2.1 相容類(lèi)計(jì)算分析

在不完備信息系統(tǒng)的屬性約簡(jiǎn)中，多數(shù)算法需計(jì)算信息量。由于計(jì)算方法的不當(dāng)，消耗大量的時(shí)間和空間資源。如文獻(xiàn)[9]計(jì)算信息量的思想是將每一對(duì)象與其他|U|-1個(gè)對(duì)象進(jìn)行比較，這樣若對(duì)屬性集P求信息量，有大量重復(fù)的計(jì)算，文獻(xiàn)[10]對(duì)其進(jìn)行改進(jìn)，時(shí)間大約只需文獻(xiàn)[9]同等條件下的一半。

現(xiàn)通過(guò)實(shí)例說(shuō)明如下，設(shè)有一不完備決策表，如表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}

根據(jù)以上計(jì)算相容類(lèi)過(guò)程，發(fā)現(xiàn)計(jì)算相容類(lèi)T(P)時(shí)，出現(xiàn)大量的重復(fù)比較， 可總結(jié)為以下幾點(diǎn)性質(zhì)：

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

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

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

證明：對(duì)于?y∈TP∪ai(x)，根據(jù)相容類(lèi)定義可知，y與TP∪ai(x)中的所有元素?zé)o不可區(qū)分，由于P?(P∪ai)，所以，y與TP(x)上所有元素也均不可區(qū)分，即y∈TP(x)，因?yàn)閥具有任意性，TP(x)?TP∪ai(x)，證畢。

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

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

2.2 改進(jìn)相容類(lèi)計(jì)算方法

由于相容類(lèi)具有自反性、對(duì)稱(chēng)性，所以信息量計(jì)算時(shí)，存在大量的重復(fù)性計(jì)算，為了避免這一現(xiàn)象的發(fā)生，現(xiàn)定義信息量Inf(P)如下：

信息量計(jì)算分析如下：

(5)

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

(6)

算法1 改進(jìn)相容類(lèi)計(jì)算：Inf(P∪ai)且ai∈C-P

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

//在相容類(lèi)計(jì)算過(guò)程中,U不斷剪枝成U′

輸出：Inf(P∪ai)

intInfP( )

{

sum= 0;

將所有樣本按屬性P進(jìn)行劃分;

{

else

deleteU/PifromU

}

ifexistssubsetof*then

returnsum;

}

2.3 新的屬性約簡(jiǎn)算法

定義7 在不完備信息系統(tǒng)S中，屬性P關(guān)于決策屬性D的條件信息量為：

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

(7)

定義8 在不完備信息系統(tǒng)S中，屬性b關(guān)于屬性組B的重要程度為：

(8)

性質(zhì)5Inf(P)的值越大，區(qū)分能力越弱，當(dāng)Inf(P)=0時(shí)，此時(shí)的P即為所求的屬性約簡(jiǎn)集。

算法2 新的屬性約簡(jiǎn)算法

輸入：U,C,D

輸出：Core//屬性約簡(jiǎn)集

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

Subset=?;SubsetD=?

//Subset存儲(chǔ)U在條件屬性下的子劃分

//SubsetD存儲(chǔ)U在決策屬性下的劃分；

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

Core=Core∪Ck

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

C′=C-Ck；

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

轉(zhuǎn)Step2；

Step4 return Core

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

3.1 屬性約簡(jiǎn)實(shí)例

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

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

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

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

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

其對(duì)應(yīng)的信息量為：

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

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

則：

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

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

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

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

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

表2 UCI數(shù)據(jù)集

表3 三種算法約簡(jiǎn)效果表

續(xù)表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的實(shí)驗(yàn)數(shù)據(jù)可以看出，以上三種算法在約簡(jiǎn)質(zhì)量上，與常見(jiàn)約簡(jiǎn)算法的結(jié)果相當(dāng)，說(shuō)明這種約簡(jiǎn)算法是有效可行的。算法a對(duì)于數(shù)據(jù)集Zoo,Dermatologh,Chess約簡(jiǎn)結(jié)果稍微有點(diǎn)偏差，很明顯算法b和算法c的約簡(jiǎn)結(jié)果更具有準(zhǔn)確性。

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

(4) 從時(shí)間性能上看，算法b和算法c明顯優(yōu)于算法a，通過(guò)表3的運(yùn)行時(shí)間長(zhǎng)短可看出。算法b與算法c整體差不多，但算法c要略?xún)?yōu)于算法b，因?yàn)樗惴╞需計(jì)算正區(qū)域，所以要浪費(fèi)一定的時(shí)間，當(dāng)然，隨著數(shù)據(jù)集樣本數(shù)及屬性數(shù)的增多，這段時(shí)間占整個(gè)約簡(jiǎn)的比例會(huì)越來(lái)越小。

4 結(jié) 語(yǔ)

[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] 徐章艷,劉作鵬,楊炳儒,等.一個(gè)復(fù)雜度為max(O(|C||U|),O(|C|2|U/C|))的快速屬性約簡(jiǎn)算法[J].計(jì)算機(jī)學(xué)報(bào),2006,29(3):391-399.

[4] 張文修,米據(jù)生,吳偉志.不協(xié)調(diào)目標(biāo)信息系統(tǒng)的知識(shí)約簡(jiǎn)[J].計(jì)算機(jī)學(xué)報(bào),2003,26(1):12-18.

[5] 王國(guó)胤,于洪,楊大春.基于條件信息熵的決策表約簡(jiǎn)[J].計(jì)算機(jī)學(xué)報(bào),2002,25(7):759-766.

[6] 王國(guó)胤.不完備信息系統(tǒng)的粗糙集擴(kuò)展[J].計(jì)算機(jī)研究與發(fā)展,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] 黃兵,周獻(xiàn)中,張蓉蓉.基于信息量的不完備信息系統(tǒng)屬性約簡(jiǎn)[J].系統(tǒng)工程理論與實(shí)踐,2005,25(4):55-60.

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

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

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

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

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

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

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

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

[18] 楊春林.基于信息熵的屬性約簡(jiǎn)在多屬性決策中的應(yīng)用[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2013,43(3):97-102.

[19] 王世強(qiáng),張登福,畢篤彥,等.基于模糊粗糙集和蜂群算法的屬性約簡(jiǎn)[J].中南大學(xué)學(xué)報(bào)(自然科學(xué)版),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。安徽省省級(jí)質(zhì)量工程項(xiàng)目(2013tszy31)；安徽省高等學(xué)校省級(jí)自然科學(xué)研究項(xiàng)目(KJ2013Z231)。梁寶華，副教授，主研領(lǐng)域：粗糙集，數(shù)據(jù)挖掘。

TP

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