鄧大勇，　李亞楠，　薛歡歡

(1.浙江師范大學(xué) 數(shù)理與信息工程學(xué)院,浙江 金華　321004;2.浙江師范大學(xué) 行知學(xué)院,浙江 金華　321004)

?

基于粗糙集的可變正區(qū)域約簡

鄧大勇1，2，李亞楠1，薛歡歡1

(1.浙江師范大學(xué) 數(shù)理與信息工程學(xué)院,浙江 金華321004;2.浙江師范大學(xué) 行知學(xué)院,浙江 金華321004)

屬性約簡是粗糙集理論的研究重點之一.現(xiàn)有的各種粗糙集約簡幾乎都是保持某種約簡準(zhǔn)則不變，用這種方法處理一些存在異常點的數(shù)據(jù)時,在泛化能力方面存在一定的問題.針對此類問題,提出了一種可變正區(qū)域的約簡方法,該方法在進行屬性約簡時允許正區(qū)域存在一定程度的變化.理論分析和示例表明了該方法的有效性.

粗糙集;屬性約簡;可變正區(qū)域;異常點;屬性重要性

0　引　言

粗糙集理論[1-3]的主要優(yōu)勢是屬性約簡和不確定性分析，而且不需要先驗知識,直接能從數(shù)據(jù)中抽取所需的知識.已經(jīng)有很多粗糙集的擴展模型，包括：可變精度粗糙集[4-5]、概率粗糙集[6-8]、覆蓋粗糙集[9-11]、領(lǐng)域粗糙集[12-14]、決策粗糙集[15-17]、F-粗糙集[18-19]等.這些粗糙集模型能夠處理不同類型的數(shù)據(jù)，它們都有自己的約簡方法和約簡準(zhǔn)則.例如，Pawlak約簡[1-3]、基于互信息的約簡[20]、基于條件熵的約簡[21-22]、并行約簡[18-19]等.幾乎所有的粗糙集約簡都是保持某種約簡準(zhǔn)則不變，并宣稱保持分類信息不變.然而，這些約簡準(zhǔn)則都顯得不夠靈活，難以處理復(fù)雜多變的數(shù)據(jù)并適應(yīng)各種要求.

可變精度粗糙集是為了去除數(shù)據(jù)集中的噪音干擾,放大數(shù)據(jù)的正區(qū)域，同時也導(dǎo)致了正區(qū)域與條件屬性之間并不一定存在單調(diào)關(guān)系,給屬性約簡造成了一定的困難.對于與異常點相關(guān)的問題也難以處理.

例如:現(xiàn)實生活中,有少量的人非常有個性、非常有特點，利用這些個性或特征區(qū)分這個人與其他人非常有效.用粗糙集的語言描述，這種個性或特征就是核屬性.但是這種個性、特征或所謂的核屬性幾乎沒有泛化能力，也就是說，對于區(qū)分其他個體不僅不利反而有害.

如何處理類似的問題？對目前的粗糙集理論來說，似乎缺乏行之有效的方法.本文提出一種可變正區(qū)域的約簡方法，該方法在處理此類問題時比較有效.可變正區(qū)域的約簡方法在約簡過程中并不嚴(yán)格保持正區(qū)域不變，而是允許正區(qū)域在一定的范圍內(nèi)發(fā)生變化，從而約簡掉給泛化能力造成一定困難的少部分屬性，甚至是核屬性，從而提高泛化能力和分類準(zhǔn)確率.

1　基礎(chǔ)知識

本節(jié)簡單介紹粗糙集[1-3]的基本知識.

設(shè)IS=(U,A)是一個信息系統(tǒng)，其中U是論域，A是論域U上的條件屬性集.對于每個屬性a∈A,都對應(yīng)著一個函數(shù)a(x):U→Va，稱Va為屬性a的值域，稱U中每個元素為個體、對象或行.

對于每一個屬性子集B?A和任何個體x∈U，都對應(yīng)著一個如下的信息函數(shù)：

B-不分明關(guān)系定義為

任何滿足關(guān)系IND(B)的2個元素x，y都不能由B的屬性子集區(qū)分，[x]B表示由x引導(dǎo)的IND(B)等價類.

對于信息系統(tǒng)IS=(U,A)、屬性子集B?A和論域子集X?U，有

在決策系統(tǒng)DS=(U,A,d)中，immweyu∩A=?，決策屬性d將論域U劃分為塊，U/8wiiaci={Y1,Y2,…,Yp}，其中Yi(i=1,2,…,p)是等價類.決策系統(tǒng)DS=(U,A,d)的正區(qū)域定義為

Pawlak約簡及屬性依賴度等概念定義如下：

定義1[1-3]在決策系統(tǒng)DS=(U,A,d)中，若B?A滿足下列條件：

1)POSB(d)=POSA(d)；

2)對于任意S?B,有POSS(d)≠POSB(d).

則B?A是DS的約簡.

2　可變正區(qū)域約簡

現(xiàn)實中的數(shù)據(jù)常常帶有一些異常點，這些異常點給分類造成一定的負(fù)面作用，現(xiàn)有的粗糙集模型，包括可變精度粗糙集，都不能解決這個問題.本文使用可變正區(qū)域的約簡方式，在約簡過程中不必嚴(yán)格保持正區(qū)域不變，試圖解決這個問題.

定理1[23]設(shè)DS=(U,A,d)是一個決策系統(tǒng),B1?B2?A,則POSB1(d)?POSB2(d)?POSA(d).

定義4在決策系統(tǒng)DS=(U,A,d)中，若B?A滿足下列條件:

2)對于任意S?B,條件1)都不成立.

則稱B?A為DS的ε可變正區(qū)域約簡.其中,ε∈[0,1)是參數(shù)，其值根據(jù)需要指定.

當(dāng)ε=0時，ε可變正區(qū)域約簡就是Pawlak約簡.所有ε可變正區(qū)域約簡記為REDVP(DS).

定義5ε可變正區(qū)域約簡的屬性核定義為

命題1ε可變正區(qū)域約簡是Pawlak約簡的子集.

命題2ε可變正區(qū)域約簡屬性核是Pawlak約簡屬性核的子集.

證明根據(jù)命題1，ε可變正區(qū)域約簡是Pawlak約簡的子集，再根據(jù)ε可變正區(qū)域約簡屬性核和Pawlak約簡屬性核的定義，易知，ε可變正區(qū)域約簡屬性核是Pawlak約簡屬性核的子集.命題2證畢.

定理3在決策系統(tǒng)DS=(U,A,d)中,a∈A是DS的ε可變正區(qū)域約簡的核屬性當(dāng)且僅當(dāng)σ(A,a)≥ε.

證明必要性顯然成立.

推論1在決策系統(tǒng)DS=(U,A,d)中,若ε>max{σ(A,a)|a∈A}，則ε可變正區(qū)域約簡的屬性核為空.

于是,ε可變正區(qū)域約簡可以重新定義為:

定義6在決策系統(tǒng)DS=(U,A,d)中，若B?A滿足下列條件：

2)對于任意S?B,條件1)都不成立.

則稱B?A為DS的ε可變正區(qū)域約簡.

3　ε可變正區(qū)域約簡算法及示例

3.1ε可變正區(qū)域約簡算法

與求取Pawlak約簡算法類似，ε可變正區(qū)域約簡算法的基本思想為:首先,根據(jù)選取的參數(shù)ε求取ε可變正區(qū)域約簡的核屬性；其次，根據(jù)除核屬性以外的其他屬性的重要度與參數(shù)ε求取約簡中的剩余屬性.算法的具體步驟如下：

算法:ε可變正區(qū)域約簡算法

輸入:決策系統(tǒng)DS=(U,A,d),參數(shù)ε.

輸出:ε可變正區(qū)域約簡.

算法步驟:

步驟1B=?,E=A.

步驟2對于任意的a∈A,若σ(A,a)≥ε,則B=B∪{a};//求取ε可變正區(qū)域約簡的屬性核.

步驟3E=A-B.

1)對于任意的a∈E,計算σ′(B,a),若σ′(B,a)=0,則E=E-{a};

2)選取最大的σ′(B,a),B=B∪{a},E=E-{a}.

步驟5輸出ε可變正區(qū)域約簡B.

ε可變正區(qū)域約簡算法的時間復(fù)雜度等價于求解Pawlak約簡的時間復(fù)雜度，其值取決于求等價類、求正區(qū)域方法的時間復(fù)雜度.所有求取Pawlak約簡的算法都可以稍稍改造成求解ε可變正區(qū)域約簡的算法.因為有很多求取Pawlak約簡的算法,所以這里不估算ε可變正區(qū)域約簡算法的時間復(fù)雜度.

注1由這個約簡算法求取的ε可變正區(qū)域約簡有可能是ε可變正區(qū)域約簡的超集，即滿足定義4的條件1)，但不一定滿足條件2).若需要嚴(yán)格的ε可變正區(qū)域約簡，則可刪除部分冗余屬性.但在一般情況下，這個算法得到的約簡不含冗余屬性，所以，本算法沒有加上刪除冗余屬性的步驟.

3.2示例

如表1所示，DS=(U,A,d)是一個決策表，A={a,b,c}是條件屬性集，d是決策屬性.

顯然,POSA(d)={y1,y2,y3,y4,y7},Pawlak約簡為B=A={a,b,c}.對于條件屬性c來說，除了c(y7)=1外，其余元素的值都為0,y7是異常點.如果用可變精度粗糙集處理,那么參數(shù)要大于0.5才能將屬性c約簡掉,而在可變精度粗糙集

表1　決策系統(tǒng)DS

中幾乎不可能取大于0.5的參數(shù)；如果用可變正區(qū)域的方法進行約簡，那么只需要取ε>0.2就能將屬性c約簡掉;如果將d(y7)的值換成2,而不是1,那么用可變精度粗糙集也同樣難以處理,而用可變正區(qū)域的約簡方法同樣可以將屬性c約簡掉.

注2條件屬性c是表1決策系統(tǒng)的核屬性，但用可變正區(qū)域的約簡方法可以將它約簡掉.因為約簡掉條件屬性c對決策表DS的正區(qū)域影響較小.

4　結(jié)論與展望

與幾乎所有的粗糙集約簡模型不同，本文提出了一種可變正區(qū)域的粗糙集約簡方法.該方法在約簡時允許正區(qū)域發(fā)生一定程度的變化，不再嚴(yán)格保持約簡準(zhǔn)則不變或信息不變.理論分析和示例表明該方法能有效地將對正區(qū)域影響小的屬性約簡掉,對異常點檢測、提高屬性約簡的分類泛化能力等具有一定的潛力和幫助.

進一步研究內(nèi)容為,把可變正區(qū)域約簡方法運用于異常點檢測和提高約簡的泛化能力，并和其他形式的約簡和方法進行比較.

[1]PawlakZ.Roughsets[J].IntJInformComputSci,1982,11(5):341-356.

[2]PawlakZ.Roughsets:Theoreticalaspectofreasoningaboutdata[M].Dordrecht:KluwerAcademicPublishers,1991.

[3]王國胤.Rough集理論與知識獲取[M].西安:西安交通大學(xué)出版社,2001.

[4]AnA,ShanN,ChanC,etal.Discoveringrulesforwaterdemandprediction:Anenhancedrough-setapproach[J].EngApplArtifInte,1996,9(6):645-653.

[5]KatzbergJD,ZiarkoW.Variableprecisionextensionofroughset[J].FoundInform,1996,27(2/3):155-168.

[9]ZhuW,WangFY.Reductionandaxiomizationofcoveringgeneralizedroughsets[J].InformSci,2003,152(1):217-230.

[10]ZhuW.Topologicalapproachestocoveringroughsets[J].InformSci,2007,177(6):1499-1508.

[11]ZhuW,WangFY.Onthreetypesofcovering-basedroughsets[J].IEEETransKnowlDataEng,2007,19(8):1131-1144.

[12]HuQ,ZhangL,ZhangD,etal.Measuringrelevancebetweendiscreteandcontinuousfeaturesbasedonneighborhoodmutualinformation[J].ExpertSystAppl,2011,38(9):10737-10750.

[13]LinTY.GranularcomputingonbinaryrelationsI:Dataminingandneighborhoodsystems,II:roughsetrepresentationsandbelieffunctions[C]//PolkowskiL,SkowronA.Roughsetsinknowledgediscovery.PhysicaVerlag:Springer,1998:107-140.

[14]LinTY.Neighborhoodsystems:aqualitativetheoryforfuzzyandroughsets[C]//WangP.Advancesinmachineintelligenceandsoftcomputing.Durham:DukeUniversity,1997:132-155.

[15]YaoYY.Informationgranulationandapproximationinadecision-theoreticalmodelofroughsets[C]//PolkowskiL,PalSK,SkowronA.Rough-neurocomputing:Techniquesforcomputingwithwords.Berlin:Springer,2003:491-516.

[16]YaoYY,WongSKM.Adecisiontheoreticframeworkforapproximatingconcepts[J].IntJManMachStud,1992,37(6):793-809.

[17]YaoYY,ZhaoY.Attributereductionindecision-theoreticroughsetmodels[J].InformSci,2008,178(17):3356-3373.

[18]鄧大勇，陳林.并行約簡與F-粗糙集[C]//王國胤，李德毅，姚一豫,等.云模型與粒計算.北京：科學(xué)出版社,2012:210-228.

[19]陳林.粗糙集中不同粒度層次下的并行約簡及決策[D].金華:浙江師范大學(xué),2013.

[20]苗奪謙，胡桂榮.知識約簡的一種啟發(fā)式算法[J].計算機研究與發(fā)展,1999,36(6):681-684.

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

[22]楊明.決策表中基于條件信息熵的近似約簡[J].電子學(xué)報,2007,35(11):2156-2160.

[23]QianY,LiangJ,PedryczW,etal.Positiveapproximation:Anacceleratorforattributereductioninroughsettheory[J].ArtifInte,2010,174(9/10):597-618.

(責(zé)任編輯陶立方)

Attribute reduction of various positive region based on rough sets

DENG Dayong1,2,LI Ya′nan1,XUE Huanhuan1

(1.CollegeofMathematics,PhysicsandInformationEngineering,ZhejiangNormalUniversity,Jinhua321004,China; 2.XingzhiCollege,ZhejiangNormalUniversity,Jinhua321004,China)

Attribute reduction had been one of the hot topics in rough set theory. Almost all of principles for attribute reducts in various kinds of rough set models preserved specified criteria, which revealed shortcomings when they were employed in problems of generalization, if data contain outliers. In order to solve this problem, a reducing method called attribute reducts of various positive regions, was presented, in which the change of positive regions was allowed when attribute reduction was conducted. Theoretical analysis and an example showed that this method was valid.

rough sets; attribute reduction; various positive region; outlier; attribute significance

10.16218/j.issn.1001-5051.2016.03.010

收文日期：2015-12-07；2016-03-08

浙江省自然科學(xué)基金資助項目(LY15F020012)

鄧大勇(1968-)，男，江西新干人，副教授.研究方向：數(shù)據(jù)挖掘；人工智能等.

TP18

A

1001-5051(2016)03-0294-04