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

鄧大勇，　李亞楠，　薛歡歡

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

?

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

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

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

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

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

0　引　言

粗糙集理論[1-3]的主要優(yōu)勢(shì)是屬性約簡和不確定性分析，而且不需要先驗(yàn)知識(shí),直接能從數(shù)據(jù)中抽取所需的知識(shí).已經(jīng)有很多粗糙集的擴(kuò)展模型，包括：可變精度粗糙集[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ū)域，同時(shí)也導(dǎo)致了正區(qū)域與條件屬性之間并不一定存在單調(diào)關(guān)系,給屬性約簡造成了一定的困難.對(duì)于與異常點(diǎn)相關(guān)的問題也難以處理.

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

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

1　基礎(chǔ)知識(shí)

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

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

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

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

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

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

在決策系統(tǒng)DS=(U,A,d)中，j5i0abt0b∩A=?，決策屬性d將論域U劃分為塊，U/j5i0abt0b={Y1,Y2,…,Yp}，其中Yi(i=1,2,…,p)是等價(jià)類.決策系統(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)對(duì)于任意S?B,有POSS(d)≠POSB(d).

則B?A是DS的約簡.

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

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

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

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

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

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

當(dāng)ε=0時(shí)，ε可變正區(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)對(duì)于任意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對(duì)于任意的a∈A,若σ(A,a)≥ε,則B=B∪{a};//求取ε可變正區(qū)域約簡的屬性核.

步驟3E=A-B.

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

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

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

ε可變正區(qū)域約簡算法的時(shí)間復(fù)雜度等價(jià)于求解Pawlak約簡的時(shí)間復(fù)雜度，其值取決于求等價(jià)類、求正區(qū)域方法的時(shí)間復(fù)雜度.所有求取Pawlak約簡的算法都可以稍稍改造成求解ε可變正區(qū)域約簡的算法.因?yàn)橛泻芏嗲笕awlak約簡的算法,所以這里不估算ε可變正區(qū)域約簡算法的時(shí)間復(fù)雜度.

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

3.2示例

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

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

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

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

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

4　結(jié)論與展望

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

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

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

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

[3]王國胤.Rough集理論與知識(shí)獲取[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]//王國胤，李德毅，姚一豫,等.云模型與粒計(jì)算.北京：科學(xué)出版社,2012:210-228.

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

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

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

[22]楊明.決策表中基于條件信息熵的近似約簡[J].電子學(xué)報(bào),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é)基金資助項(xiàng)目(LY15F020012)

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

TP18

A

1001-5051(2016)03-0294-04