粒度計算中混合屬性約簡的權(quán)重模糊粗糙集模型VIP

1、粒度計算中混合屬性約簡的權(quán)重模糊粗糙集模型第45卷第lO期2011年10月西安交通大學JOURNALOFXIANJIAOTONGUNIVERSITYVo1.45Oct.NO.102O11粒度計算中混合屬性約簡的權(quán)重模糊粗糙集模型劉洋,周清雷,馮博琴.(1.鄭州大學信息工程學院,450001,鄭州;2.西安交通大學電子與信息工程學院,710049,西安)摘要:針對權(quán)重粗糙集模型不能有效處理非平衡混合數(shù)據(jù)的問題,對權(quán)重論域上的各種類型變量進行分析并建立統(tǒng)一的模糊等價關(guān)系,提出混合數(shù)據(jù)上的權(quán)重模糊粗糙集模型,并利用該模型構(gòu)造出帶權(quán)模糊等價空間上的混合屬性約簡算法.混合屬性約簡算法產(chǎn)生的模糊軟劃分可以

2、克服權(quán)重論域上離散硬劃分產(chǎn)生的信息損失.在非平衡混合數(shù)據(jù)集上進行的實驗結(jié)果表明,與基于權(quán)重粗糙集的算法相比,基于權(quán)重模糊粗糙集模型的屬性約簡算法的平均分類精度提高了l1.9.關(guān)鍵詞:粗糙集;混合數(shù)據(jù);模糊等價關(guān)系;權(quán)重論域;屬性約簡中圖分類號:TP391文獻標志碼:A文章編號:0253-987X(2011)10-004305AWeightedFuzzyRoughSetsModelwithHybrid-AttributeReductioninGranularComputingLIUYang,ZHOUQinglei,FENGBoqin.(1.SchoolofInformationEngineeri

3、ng,ZhengzhouUniversity,Zhengzhou450001,China;2.SchoolofElectronicsandInformationEngineering,XianJiaotongUniversity.Xian710049,China)Abstract:Inordertosolvetheproblemthatweightedroughsetsmodellacksamechanismtodealwithmixedandimbalanceddata,aunifiedfuzzyequivalentrelationshipforanalyzingdifferenttypes

4、offeaturesinweighteddomainisestablished,andaweightedfuzzyroughsetsmodelisproposedtodea1withmixeddata.Furthermore,ahybridattribute-reductionalgorithmisconstruetedbasedontheweightedfuzzyroughsetsmode1.Comparedwiththeclassicalcrisppartition,thehybridalgorithmcanavoidinformationlossthroughfuzzysoftparti

5、tiongeneratedbythemode1.Experimentalresultsonimbalancedandmixeddatasetsshowthattheproposedweightedfuzzyroughsetsmodelcannotonlyselectfewerfeaturesthanweightedroughsetsmodel,butalSOimprovetheaverageclassificationperformanceofthereducedattributesetonlearningmethodsby11.9.Keywords:roughset;mixeddata;fu

6、zzyequivalentrelationship;weighteddomain;attributered1action由Z.Pawlak教授l-1提出的粗糙集理論被廣泛應用于知識依賴性分析,屬性子集選擇等問題2.遺憾的是,作為一種有效的粒度計算模型,Pawlak粗糙集定義在經(jīng)典論域的基礎(chǔ)上,因此缺乏一種能夠有效地結(jié)合論域上的先驗信息和主觀知識的機制_3,對于現(xiàn)實應用中廣泛存在的先驗性知識不能直接處理.此外,在工程,醫(yī)療和金融等領(lǐng)域,混合型變量無處不在.研究人員在引人粗糙集等機器學習方法來處理該類數(shù)據(jù)時,往往采用離散化算法把數(shù)值型變量和模糊型變量轉(zhuǎn)化為符號型變量_4,然而這一轉(zhuǎn)換不可避免地帶來

7、了信息損失,學習算法的性能在很大程度上取決于離散化的效果5.收稿日期:20110122.作者簡介:劉洋(1984一),男,博士,講師.基金項目:國家高技術(shù)研究發(fā)展計劃資助項目(2007AA0104O8).網(wǎng)絡出版時間:20110729網(wǎng)絡出版地址:http:西安交通大學第45卷為了解決這一問題,人們引入了模糊粗糙集模型_6和鄰域粗糙集模型7.不同的模型基于不同的粒度度量標準和逼近定義,但它們都屬于粒度計算的研究范疇L8.由于這些方法僅適用于普通論域上的粒度度量,因此都缺乏處理主觀知識和先驗信息的能力.文獻2911研究了結(jié)合權(quán)重信息處理粗糙集屬性約簡的問題,然而這些方法僅適用于符號屬性的情形.文

8、獻E123基于帶權(quán)論域上的模糊等價關(guān)系,討論了帶權(quán)模糊近似空間,并給出有效的規(guī)則獲取方法.但是,帶權(quán)模糊近似空間的屬性約簡問題還未查到有文獻進行分析和研究.本文利用模糊等價關(guān)系的信息熵度量標準,提出一種基于權(quán)重模糊粗糙集模型的混合屬性約簡算法.該算法直觀,易于理解,能夠同時處理符號型,數(shù)值型和模糊型變量,而無需對其進行離散化處理和去模糊化處理.因此,與經(jīng)典的粗糙集算法相比,該算法結(jié)合了論域上的權(quán)重信息,而且省去了混合型屬性的預處理過程.由于該模型可以結(jié)合先驗知識并直接分析混合數(shù)據(jù),因而拓展了經(jīng)典粗糙集理論的應用范圍.1各類型變量空間的統(tǒng)一模糊粒度化一表不粒度表示是粗糙集理論和粒度計算的基本問題

9、,Pawlak粗糙集模型建立在離散空間的不可辨識等價關(guān)系之上,等價關(guān)系對論域的劃分形成了論域空間的粒度化表示.然而,對于數(shù)值型,模糊型變量空間,對象的取值可以是連續(xù)的,模糊的,采用等價關(guān)系將導致對個別屬性的過擬合.本文所討論的模型建立在模糊等價關(guān)系的粒度化表示基礎(chǔ)上.定義1給定一個非空對象集合U-z1,.,z,R一(r)mXm是己,上的一個模糊二元關(guān)系,其中r0,1為對象,和z,之間關(guān)系的度量.一般來講,如果對于所有的z,z,zU,R滿足自反性一1,對稱性和傳遞性r一,(r八r),則稱R是一個模糊等價關(guān)系.定義2由模糊等價關(guān)系R產(chǎn)生的模糊等價劃分為ru/n一z,i),其中i1/x為包含對象zr

10、的模糊等價類,I表示模糊集合元素的并.由定義2可以看出,模糊等價關(guān)系是經(jīng)典等價關(guān)系的擴展.對于符號型屬性,其產(chǎn)生的模糊等價關(guān)系就是Pawlak粗糙集模型描述的經(jīng)典等價關(guān)系.對于數(shù)值型屬性,通常需要先對連續(xù)特征進行歸一化操作.L.Zadeh教授1.提出了一種基于相似性度量函數(shù)的模糊相似二元關(guān)系sim(i,J)一g(f)一()j),這里函數(shù)g滿足El3g(0)一1;g(oo)一0;g(?)E0,13(1)sim(i,J)一sim(j,);sim(i,)=1(2)函數(shù)g有多種選擇,本文采用如下定義一式中:E0,0.53,本文設置3=0.25.對于模糊型屬性,有許多可供選擇的模糊相似性度量標準,例如H

11、amming相似性度量函數(shù)或者最大一最小相似度量函數(shù),其時間復雜度為0(122)E143.2權(quán)重模糊粗糙集模型文獻E123基于帶權(quán)論域上的模糊等價關(guān)系,研究了帶權(quán)模糊近似空間的上,下近似,基于帶權(quán)模糊近似空間提出了有效的規(guī)則獲取方法.本節(jié)將在此基礎(chǔ)上,對帶權(quán)論域上的屬性依賴問題進行深人的討論研究.2.1權(quán)重信息系統(tǒng)定義3權(quán)重信息系統(tǒng)為一個五元組<U,A,V,/,>,其中U是非空對象集合,A一al.一,a為非空屬性集合,f:UXAV為一個信息函數(shù),為屬性值域的集合,W:【R為論域【,上的權(quán)重分配函數(shù).通常,二元組<己,叫>被稱為權(quán)重信息系統(tǒng)的帶權(quán)論域空間,若A=CUD,其

12、中C,D分別為條件和決策屬性集合,則權(quán)重信息系統(tǒng)也可稱為權(quán)重決策信息系統(tǒng).定義4給定一個帶權(quán)論域<己,>上的一個模糊集合X,X的帶權(quán)度數(shù)定義為1xl一,Lx()(4)厶叫,J定理1給定一個帶權(quán)論域<,>上的2個模糊集合X,y,如果Xy,則以下公式成立0lXl1JXjJYXnyI一IxlXUy1一lYl(5)(6)(7)(8)第1O期劉洋,等:粒度計算中混合屬性約簡的權(quán)重模糊粗糙集模型文獻E12研究了帶權(quán)模糊近似空間的上,下近似,本文不再贅述.下面對帶權(quán)論域上的屬性依賴性度量進行討論.定義5給定一個權(quán)重決策信息系統(tǒng)<U,A,V,f,叫>,BC,L為屬性集的正域

13、,B相對于決策屬性D的帶權(quán)依賴度定義為yR(D,硼)一ILp0s(D)J(9)根據(jù)定義可知,),Eo,1.當y一1時,決策屬性集合D完全依賴于B;當0<7<1時,決策屬性集合D部分依賴于B;否則,y=0時,決策屬性集合D不依賴于B.2.2屬性依賴程度的信息熵度量信息熵已經(jīng)廣泛應用于粗糙集理論的屬性重要性度量中,但是對于帶權(quán)論域上模糊等價關(guān)系的信息熵度量方式,需要給出新的定義來刻畫屬性在帶權(quán)論域空間上的分辨能力.定義6給定一個帶權(quán)論域(U,>,對于帶權(quán)論域上的任意一個模糊等價關(guān)系R,其信息量函數(shù)定義為H(R,)一一LlgIiI(10)i厶WjJ定理2給定權(quán)重信息系統(tǒng),其中B,E

14、C,由B,E產(chǎn)生的模糊等價關(guān)系分別為R,s,則集合B,E的聯(lián)合信息熵為H(BUE,叫)一一LlgIEx蠢nExiI(11)厶叫的決策信息系統(tǒng)而言,計算量會大到不能容忍.本節(jié)將基于屬性子集的信息增益,構(gòu)造一個前向貪心約簡算法.信息增益函數(shù)描述了條件屬性對分類的貢獻,因此可以作為屬性集合重要性度量的評價指標.定義8給定一個權(quán)重決策信息系統(tǒng),其中BC,口CB,屬性口相對于屬性集B的相對重要度定義為G(口,B,D)一H(BID,叫)一H(BU12)ID,叫)(13)定理3給定一個權(quán)重決策信息系統(tǒng),其中BC,口CB,則G(以,B,D)0.證明只需證明H(BJD叫)H(BU)lD,叫).因為蠢.nz蠢.2

15、Ex日U.rl五.,由定理1有l(wèi)Exr-1IlExnExDI,因此有H(BlD,)H(BU口)lD,).定理3得證.圖1給出本文基于權(quán)重模糊粗糙集模型的混合屬性約簡算法(wFRAR),它能夠確保重要的屬性首先被加入到備選約簡集合中,從而不損失重要的屬性特征.輸入:權(quán)重決策信息系統(tǒng)<A,f,w>,閾值參數(shù).輸出:一個屬性約簡集合E.步驟1:對于所有的口C計算H(alD,w);步驟2:a=argmax口cH(aD,w),4);步驟3:對于所有的aCE,計算G(a,E,D);步驟4:a=argmaxac,Gw(口,E,D);步驟5:如果G(4,E,D)<s,返回E;否則ua),轉(zhuǎn)步

16、驟3圖1基于權(quán)重模糊粗糙集的混合屬性約簡算法證明由定義可知H(BUE,)一H(RnS,一一爭Wiir-13效ti一z贏n.-g,故定理2得證.定義7給定權(quán)重信息系統(tǒng),其中B,EqC,由B,E產(chǎn)生的模糊等價關(guān)系分別為R,Js,則集合B,E的條件信息熵為一一轟-g了(12)2.3基于權(quán)重模糊粗糙集的混合屬性約簡算法發(fā)現(xiàn)權(quán)重決策信息系統(tǒng)的全部約簡需要測試2一1個屬性子集,以檢驗它們是否滿足約簡的條件,其中是條件屬性的數(shù)量.這對于屬性子集較多性,本文從UCI機器學習數(shù)據(jù)庫中挑選了4組數(shù)據(jù),描述如表1所示.可以看出,這4個分類問題都是混合型數(shù)據(jù),并且各類之間的分布是不平衡的.定義9給定m一,W/+分別為

17、少數(shù)類,多數(shù)類的用例表1數(shù)據(jù)集描述httptVCVCVV.dxb.an西安交通大學第45卷數(shù),w一,w+分別為少數(shù)類和多數(shù)類上用例的權(quán)重,少數(shù)類權(quán)重總和所占的比例定義為觸P一:=(14)砸1L勰由定義可知,隨著P一的增加,少數(shù)類用例的權(quán)重和也相應增加.當P一一0.5時,逆類概率權(quán)重分配給了每一個類,此時數(shù)據(jù)集通過權(quán)值分配達到了各類之間的平衡效果.為比較本文算法(WFRS_AR算法)和基于權(quán)重粗糙集的算法(WRS-AR算法)l_11在非平衡混合數(shù)據(jù)集上選擇特征的分類能力,將2種約簡算法分別作為當前流行的基于權(quán)重的RBFSVM分類學習算法的前端屬性約簡工具.符號和數(shù)值屬性的粒度表示采用了本文第2節(jié)

18、的方法.本文算法的s取值0.0125.實驗中,固定少數(shù)類w一的權(quán)值,選擇W+使P一依次為0.05,0.1,0.15,0.9,0.95,記錄每次實驗中學習算法在約簡數(shù)據(jù)集上的真正率,假正率對,利用3次樣條插值積分法計算分類算法的平均分類精度AUC(areaunderROCcurves),評價2種約簡算法選擇特征的質(zhì)量.表2給出了2種屬性約簡算法在數(shù)據(jù)集上選擇的特征集結(jié)果,以及作為學習器的前端約簡工具所取得的平均分類精度.由表2可以發(fā)現(xiàn),這2種算法都能有效地降低特征數(shù)量,相對而言,WRS-AR算法得到的特征數(shù)量較少,但平均分類性能也較低.由于WFRS-AR算法不受離散化預處理的影響,通過為不同類別

19、實例分配合適的權(quán)重,在保留了相對較少的特征數(shù)的同時,約簡屬性集在分類算法上的平均分類精度提高了11.9.表22種算法的實驗結(jié)果4結(jié)論與展望本文基于模糊等價關(guān)系的信息熵概念提出一種分析混合數(shù)據(jù)的權(quán)重模糊粗糙集模型.該模型以帶權(quán)論域空間中的模糊等價關(guān)系形成論域的?；?從而將先驗知識引入混合數(shù)據(jù)的粒度計算模型.本文進一步給出了帶權(quán)論域上模糊等價關(guān)系的信息量度量方法,基于信息量增益展示了本文模型在混合屬性約簡選擇中的應用.實驗分析表明,通過對用例進行權(quán)重分配,權(quán)重模糊粗糙集不僅可以選擇很少量的特征,而且可以改善分類器在非平衡數(shù)據(jù)集上的平均分類性能,驗證了本文算法的有效性.后續(xù)的工作將研究本文模型在代價

20、敏感學習問題中的應用,此外改進本文模型的海量數(shù)據(jù)快速約簡算法也是研究方向之一.參考文獻:1PAWLAKZ,SK0wR0NA.RudimentsofroughsetsFJ.InformationSciences,2007,177(1):3-27.E2王國胤,于洪,楊大春.基于條件信息熵的決策表約簡口.計算機,2002,25(7):759766.WANGGuoyin,YUHong,YANGDachun.Decisiontablereductionbasedonconditionalinf0rmationentroPYJ.ChineseJournalofComputers,2002,25(7):75

21、9766.3TINGK.Aninstance-weightingmethodtOinducecostsensitivetreesFJ.IEEETransactionsonKnowtedgeandDataEngineering,2002,14(3):659665.4謝宏,程浩忠,牛東曉.基于信息熵的粗糙集連續(xù)屬性離散化算法J.計算機,2005,28(9):15701574.XIEHong,CHENGHaozhong,NIUDongxiao.DiscretizationofcontinuousattributesinroughsettheorybasedoninformationentropyJ.

22、ChineseJournalofComputers,2005,28(9):15701574.53HuQinghua,XieZongxia,YuDaren.Hybridattributereductionbasedonanovelfuzzy-roughmodelandinformationgranulationJ1.PatternRecognition,2007,40(12):35093521.6DUBOISD,PRADEH.RoughfuzzysetsandfuzzyroughsetsJ.InternationalJournalofGeneralSystems,1990,17(2):19120

23、9.http:第1O期劉洋,等:粒度計算中混合屬性約簡的權(quán)重模糊粗糙集模型477胡清華,于達仁,謝宗霞.基于鄰域?；痛植诒平臄?shù)值屬性約簡EJ.軟件,2008,19(3):640649.HUQinghua,YUDaren,XIEZongxia.NumericalattributereductionbasedonneighborhoodgranulationandroughapproximationJ.ChineseJournalofSoftware,2008,19(3):640649.8HUQinghua,LIUJinfu,YUDaren.Mixedfeatureselectionbased

24、ongranulationandapproximationJj.Knowledge-BasedSystems,2008,21(4):294304.9XUChangzhi,MINFan.WeightedreductionfordecisiontablescProceedingsof3rdInternationalConferenceonFuzzySystemsandKnowledgeDiscovery.Berlin,Germany:Springer-Verlag,2006:246255.1oHUQinghua,YuDaren,XIEZongxia,eta1.Fuzzyprobabilistica

25、pproximationspacesandtheirinformationmeasuresJ.IEEETransactionsonFuzzySysterns,2006,14(2):191201.11LIUJinfu,HUQinghua,YuDaren.AweightedroughsetbasedmethoddevelopedforclassimbalancelearningJ.InformationSciences,2008,178(4):12351256.12LIUrang,FENGBoqin,BAIGuohua.Compactrulelearneronweightedfuzzyapprox

26、imationspacesforclassimbalancedandhybriddataEcfProceedingsof6thInternationalConferenceonRoughSetsandCurrentTrendsinComputing.Berlin,Gemany:Springer-Verlag,2008:262271.13ZADEHL.FuzzysetsJ.InformationandControl,1965,8(3):338-353.14LEEH.Anoptimalalgorithmforcomputingthemax-raintransitiveclosureofafuzzy

27、similaritymatrix口.FuzzySetsandSystems,2001,123(1):129136.15FRANKA,ASUNCIONAUCImachinelearningrepositoryDB/OL.20101222./m1.16BREFELDU,GEIBELP,WYSOTZKIF.SupportvectormachineswithexampledependentcostscProceedingsoftheEuropeanConferenceonMachineLearning.Berlin,Germany,Springer-Verlag,200