基于粗糙集的可變正區域約簡

鄧大勇，　李亞楠，　薛歡歡

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

?

基于粗糙集的可變正區域約簡

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

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

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

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

0　引　言

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

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

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

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

1　基礎知識

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

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

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

B-不分明關系定義為

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

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

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

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

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

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

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

則B?A是DS的約簡.

2　可變正區域約簡

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

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

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

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

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

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

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

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

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

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

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

證明必要性顯然成立.

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

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

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

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

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

3　ε可變正區域約簡算法及示例

3.1ε可變正區域約簡算法

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

算法:ε可變正區域約簡算法

輸入:決策系統DS=(U,A,d),參數ε.

輸出:ε可變正區域約簡.

算法步驟:

步驟1B=?,E=A.

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

步驟3E=A-B.

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

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

步驟5輸出ε可變正區域約簡B.

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

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

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是異常點.如果用可變精度粗糙集處理,那么參數要大于0.5才能將屬性c約簡掉,而在可變精度粗糙集

表1　決策系統DS

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

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

4　結論與展望

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

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

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

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

[3]王國胤.Rough集理論與知識獲取[M].西安:西安交通大學出版社,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]//王國胤，李德毅，姚一豫,等.云模型與粒計算.北京：科學出版社,2012:210-228.

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

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

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

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

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

(責任編輯陶立方)

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

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

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

TP18

A

1001-5051(2016)03-0294-04