粒度計算中混合屬性約簡的權重模糊粗糙集模型

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

2、克服權重論域上離散硬劃分產生的信息損失.在非平衡混合數(shù)據集上進行的實驗結果表明,與基于權重粗糙集的算法相比,基于權重模糊粗糙集模型的屬性約簡算法的平均分類精度提高了l1.9.關鍵詞:粗糙集;混合數(shù)據;模糊等價關系;權重論域;屬性約簡中圖分類號: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粗糙集定義在經典論域的基礎上,因此缺乏一種能夠有效地結合論域上的先驗信息和主觀知識的機制_3,對于現(xiàn)實應用中廣泛存在的先驗性知識不能直接處理.此外,在工程,醫(yī)療和金融等領域,混合型變量無處不在.研究人員在引人粗糙集等機器學習方法來處理該類數(shù)據時,往往采用離散化算法把數(shù)值型變量和模糊型變量轉化為符號型變量_4,然而這一轉換不可避免地帶來

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

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

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

10、的模糊等價類,I表示模糊集合元素的并.由定義2可以看出,模糊等價關系是經典等價關系的擴展.對于符號型屬性,其產生的模糊等價關系就是Pawlak粗糙集模型描述的經典等價關系.對于數(shù)值型屬性,通常需要先對連續(xù)特征進行歸一化操作.L.Zadeh教授1.提出了一種基于相似性度量函數(shù)的模糊相似二元關系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權重模糊粗糙集模型文獻E123基于帶權論域上的模糊等價關系,研究了帶權模糊近似空間的上,下近似,基于帶權模糊近似空間提出了有效的規(guī)則獲取方法.本節(jié)將在此基礎上,對帶權論域上的屬性依賴問題進行深人的討論研究.2.1權重信息系統(tǒng)定義3權重信息系統(tǒng)為一個五元組<U,A,V,/,>,其中U是非空對象集合,A一al.一,a為非空屬性集合,f:UXAV為一個信息函數(shù),為屬性值域的集合,W:【R為論域【,上的權重分配函數(shù).通常,二元組<己,叫>被稱為權重信息系統(tǒng)的帶權論域空間,若A=CUD,其

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

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

14、C,由B,E產生的模糊等價關系分別為R,s,則集合B,E的聯(lián)合信息熵為H(BUE,叫)一一LlgIEx蠢nExiI(11)厶叫的決策信息系統(tǒng)而言,計算量會大到不能容忍.本節(jié)將基于屬性子集的信息增益,構造一個前向貪心約簡算法.信息增益函數(shù)描述了條件屬性對分類的貢獻,因此可以作為屬性集合重要性度量的評價指標.定義8給定一個權重決策信息系統(tǒng),其中BC,口CB,屬性口相對于屬性集B的相對重要度定義為G(口,B,D)一H(BID,叫)一H(BU12)ID,叫)(13)定理3給定一個權重決策信息系統(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給出本文基于權重模糊粗糙集模型的混合屬性約簡算法(wFRAR),它能夠確保重要的屬性首先被加入到備選約簡集合中,從而不損失重要的屬性特征.輸入:權重決策信息系統(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),轉步

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

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

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

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

20、敏感學習問題中的應用,此外改進本文模型的海量數(shù)據快速約簡算法也是研究方向之一.參考文獻: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期劉洋,等:粒度計算中混合屬性約簡的權重模糊粗糙集模型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