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

梁 寶 華

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

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

梁 寶 華

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

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

粗糙集 屬性約簡 非完備信息系統(tǒng) 相容類

0 引 言

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

為了解決不完備信息系統(tǒng)對粗糙集理論應(yīng)用化的影響，研究者們利用相容關(guān)系[6]、相似關(guān)系等，給出一系列有效的屬性約簡算法，如文獻(xiàn)[7]給出了差別矩陣的二進(jìn)制形式,文獻(xiàn)[8-10]提出相容關(guān)系相似矩陣并給出一種不完備決策表的屬性約簡算法。不完備決策表的屬性約簡算法多數(shù)以“信息量”[10]為啟發(fā)式信息，張等在文獻(xiàn)[11]中提出一些改進(jìn)方法，經(jīng)研究發(fā)現(xiàn)，文獻(xiàn)[11]存在大量重復(fù)掃描數(shù)據(jù)對象的不足。為了減少掃描數(shù)據(jù)的次數(shù)，無需大量空間存儲相容類信息，本文根據(jù)相容類元素間的對稱性、自反性特征，提出一種快速計算相容信息量的方法，有效提高屬性約簡效率。最后通過實(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)=*(*為缺損值)，則稱此信息系統(tǒ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)定義可得相容類定義為：

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

(2)

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

定義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的一個約簡，則要同時滿足下述兩個條件：

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

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

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

2.1 相容類計算分析

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

現(xiàn)通過實(shí)例說明如下，設(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ù)以上計算相容類過程，發(fā)現(xiàn)計算相容類T(P)時，出現(xiàn)大量的重復(fù)比較， 可總結(jié)為以下幾點(diǎn)性質(zhì)：

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

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

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

證明：對于?y∈TP∪ai(x)，根據(jù)相容類定義可知，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且對象在屬性ai上取值有*的，則TP(x)=TP∪ai(x)。

證明：因?yàn)閨U/ai|=1，即所有樣本在屬性ai上取值相同，即Tai(x)=U。對于?y∈TP(x)，有y與TP(x)中所有元素在屬性P均不可區(qū)分。所以必有y在屬性P∪ai都不可區(qū)分，即，y∈TP∪ai(x)。因?yàn)閥具有任意性，所以得到若|U/ai|=1且?y∈TP(x)時，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ū)分，所以等價于|U/ai|=1的情況，證畢。

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

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

信息量計算分析如下：

(5)

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

(6)

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

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

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

輸出：Inf(P∪ai)

intInfP( )

{

sum= 0;

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

{

else

deleteU/PifromU

}

ifexistssubsetof*then

returnsum;

}

2.3 新的屬性約簡算法

定義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時，此時的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)，并選出最小的信息量對應(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 屬性約簡實(shí)例

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

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

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

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

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

其對應(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)分析

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

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

表3 三種算法約簡效果表

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

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

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

4 結(jié) 語

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

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

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

[6] 王國胤.不完備信息系統(tǒng)的粗糙集擴(kuò)展[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)屬性約簡[J].系統(tǒng)工程理論與實(shí)踐,2005,25(4):55-60.

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

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

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

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

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

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

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

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

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

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

TP

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