粗糙集理論與應(yīng)用發(fā)展

1、粗糙集理論與應(yīng)用發(fā)展1、引言粗糙集(roughs ets,RS理論是20世紀(jì)80年代初由波蘭科學(xué)家Pawlak提出的。其 主思想就是在保持分類能力不變的前提下，通過知識約簡，導(dǎo)出概念的分類規(guī)貝U。 它從一個新的角度將知識定義為對論域的劃分能力，并將其引入數(shù)學(xué)中的等價關(guān)系 來進行討論，從而為數(shù)據(jù)分析，特別是不精確、不完整數(shù)據(jù)分析提供了一套新的 數(shù)學(xué)方法。同時，粗糙集理論具有無需提供除問題所需處理的數(shù)據(jù)集合之外的任何 先驗信息，僅根據(jù)觀測數(shù)據(jù)刪除冗余信息，比較不完整知識的程度一粗糙度、屬性 間的依賴性與重要性，抽取分類規(guī)則等的能力。近幾年，這個理論已得到空前的發(fā) 展，無論在理論本身研究方面，還是在

2、理論應(yīng)用方面都取得了令人矚目的成果。2、粗糙集理論簡介粗糙集理論是建立在分類機制的基礎(chǔ)之上的，不可區(qū)分關(guān)系的概念是粗糙集理 論的基礎(chǔ)。信息系統(tǒng)S由論域U和等價關(guān)系集A構(gòu)成，表示成S=(U,A)，不可區(qū)分 關(guān)系ind(A)是信息系統(tǒng)S上的一個等價關(guān)系，它是A上全部等價關(guān)系的交集。信息 系統(tǒng)S所表示的知識可理解為*對論域U劃分的結(jié)果。不可區(qū)分關(guān)系的等價類構(gòu)成了 信息系統(tǒng)表示的知識的最小粒度，這個粒度內(nèi)的對象不可區(qū)分。正是由于知識的 粒度性，造成使用已有知識不能精確地表示某些概念。為此，在 不可區(qū)分關(guān)系基礎(chǔ) 上定義了上下近似，使粗糙集理論能夠有效地逼近這些概念。令XCU是論域上對象 的一個集合，BC

3、A是一族等價關(guān)系，CXIs表示元素x在B下的等價類，則B( X )二 (xEUCxls(=X)B( X)二 XEUCx7B(1 X =t -0分別稱為X的相對于B的下近似和上近似。如果上近似與下近似相同，則稱X是 可定義 的，也稱作精確集；否則，稱為粗糙集。在粗 糙 集 理論中，消去冗余知 識，進行 知識簡化的基本工作是利用兩個基本概念：約簡和核來進行的。令A(yù)為一等價關(guān)系集，且aEA當(dāng)ind (A)=ind(A-a) 時，稱a為A中不必要的；否則稱 a為A中必要的。若每一個aEA都為A中必要的，則稱A是獨立的。設(shè)BCA若B是 獨立的，且ind( B)= ind(A)，則稱B為A的一個約簡。A中

4、所有必要關(guān)系的集合，稱 為A的核。3粗糙集的擴展模型對于Pa wlak提出的經(jīng)典的粗糙集理論，由于它沒有考慮到數(shù) 據(jù)噪音、數(shù)據(jù)缺失等情況，并且經(jīng)典的粗糙集理論所涉及的概念和知識都是清晰的， 不能對論域U上的一個模糊集合進行描述，因此許多研究者對經(jīng)典的粗糙集理論進行 了擴展，以使其應(yīng)用的范圍更加廣泛。對一些著名擴展模型性質(zhì)的研究正日益引起 學(xué)術(shù)界的關(guān)注，下面簡要介紹幾個著名的擴展模型：可變精度粗糙集模型(VPRS)可變精度粗糙集模型能夠解決屬性間無函數(shù)或不確定關(guān)系的數(shù)據(jù)分類問題，它 對經(jīng)典粗糙集理論的主要擴充體現(xiàn)在它允許一定的誤分類率9(018鎮(zhèn)0-5)，定義戶 多數(shù)包含關(guān)系為：若把集合X中的元

5、素分類到集合丫中，則會犯分類錯誤的可能性 小于夕。VPRS莫型和經(jīng)典粗糙集是兼容的，只要令a二0,就和經(jīng)典模型一致了。 隨著a增大變精度粗糙集的近似邊界區(qū)域變窄，即變精度粗糙集意義下的不確定區(qū) 域變小。因此，變精度粗糙集對數(shù)據(jù)不一致性有一定的容忍度，在某些場合可以增 強產(chǎn)生規(guī)則的魯棒性，提高預(yù)測精度2 , Katzberg和Ziarko進一步提出了不對稱邊 界的VPRS莫型，即在上下近似的定義中的R可以是不相同的，從而使此模型更加 一般化3】相似莫型在經(jīng)典的粗糙集莫型中，當(dāng)數(shù)據(jù)中存在缺失的屬性值的時候，不可區(qū)分關(guān)系或者 說是等價關(guān)系無法應(yīng)付這種情形。為擴展粗糙集的處理能力，可以使用相似關(guān)系代

6、替粗糙集合中的不可區(qū)分關(guān)系。S 二(U, A T)是信息系統(tǒng)，令A(yù)CA T,在文4中定義的相似關(guān)系為 SI M (A )=(x,y)EUXU!V a E A , a( x) = a( y)or a ( x)= or a ( y )“，相似類一般不再構(gòu)成U的劃分，它們之間可能是相互重疊的，它們構(gòu)成U的覆蓋。由于相似類中的元素不一定屬于同一決策 類，因此在相似關(guān)系的基礎(chǔ)上定義了相對吸收集的概念，相對吸收集中的任意兩個 元素都相似且具有同樣的決策值；相對吸收集可以用來進行數(shù)據(jù)削減。莫糊粗糙集莫型在人們的實際生活中，涉及到的知識或概念往往是莫糊的不確定的，為了獲得 對莫糊概念更好的近似表示，D.D u

7、dious和H.Prade提出了莫糊粗糙集的 莫型5】。 用類似經(jīng)典粗糙集的方式對莫糊粗糙集的基本概念進行了定義，一個莫糊集合的下近 似和上近似為一對莫糊集合，它們的隸屬函數(shù)分別表示論域中的對象肯定隸屬于這 個莫糊集合的程度和可能隸屬于這個莫糊集合的程度。Alpha粗糙集理論(a-RST)a粗糙集理論是將經(jīng)典的粗糙集理論擴展成帶有模糊性質(zhì)的新理論。它表現(xiàn)了 a粗糙集的模糊的非空邊界，并以帶參數(shù)的不可區(qū)分關(guān)系為基礎(chǔ)對粗糙集理 論 中的信息系統(tǒng)、依賴、可定義性、近似性、核等概念進行了推廣，以此來對模糊概念 進行逼近。4與其他不確定理論的比較研究粗糙集理論在處理不確定性和模糊性方面具有很多 優(yōu)點，例

8、如粗糙集理論在 處理大數(shù)據(jù)量，消除冗余信息等方面，有著良好的效果； 它僅利用數(shù)據(jù)本身提供的信息，無需任何先驗知識，對問題的不確定性的描述或處理 更客觀；粗糙集理論可以產(chǎn)生簡潔準(zhǔn)確、易于驗證的規(guī)則知識等.但是，粗糙集本身特點又決定它在一 些問題的處理方面存在著不足，而一些其它的不確定理論也有著各自的優(yōu) 點，這使得 粗糙集理論與其他不確定理論的互補性研究成為必然。目前對粗糙集 理論與模糊理 論及證據(jù)論的關(guān)系和互補性研究已經(jīng)取得豐碩的成果，下面加以簡要介紹。粗糙集以集合中元素的不可區(qū)分關(guān)系為基礎(chǔ)，體現(xiàn)的是由于知識的粒度性而導(dǎo) 致的粗糙性，強調(diào)數(shù)據(jù)的不可區(qū)分，研究的是不同類中的對象組成的集合之間的關(guān)

9、系，重在分類；而模糊集是基于元素對集合隸屬程度的不同，注重描述信息的含糊程 度，研究的是屬于同一類的不同對象的隸屬的關(guān)系，重在隸屬的程度，強調(diào)集合本身 的含混性7】。它們處理的是兩種不同的模糊和不確定性，分別刻畫了不完備信息的 兩個方面。因此兩種方法相互補充可能可以更有效地處理不完全知識。粗糙集與Dempster-Shafter的證據(jù)理論之間有很多相似之處。二者的主要區(qū)別 在于Dempster-Shafter理論利用信度函數(shù)作為主要工具，而粗糙集理論主要利用上 近似集合和下近似集合1.D .D udious和H.P rade同時指 出，Dempster-Shafter 的證據(jù)理論和Z.Pa w

10、lak的粗糙集理論是不同術(shù)語下的同一個模型8。A.Sk owron和J.G razymala-Busse甚至指出，粗糙集理論可以看 作 是證據(jù)理論的基礎(chǔ)，并在粗糙集理論的框架上重新解釋了證據(jù)理論的基本概念，特別 是用上近似和下近似的術(shù)語解釋了信念(belief)和似然(plausibility)函數(shù)，進而討論了 二者之間的互補問題95粗糙集理論與其它方法的融合目前，粗糙集理論已成為信息科學(xué)最為活躍的研究領(lǐng)域之一，被廣泛應(yīng)用 于數(shù) 據(jù)挖掘、機器學(xué)習(xí)、決策支持系統(tǒng)和模式識別等眾多領(lǐng)域。同時，該理論還 在醫(yī)學(xué)、 化學(xué)、材料學(xué)、地理學(xué)、管理科學(xué)和金融等其他學(xué)科得到了成功的應(yīng)用。在粗糙集理論的應(yīng)用研究中

11、，將粗糙集理論與其它方法相融合的研究是當(dāng)前 的一個研究熱點。下面對粗糙集理論與神經(jīng)網(wǎng)絡(luò)、遺傳算法、模糊邏輯、SVM方法 的融合加以簡單介紹。神經(jīng)網(wǎng)絡(luò)具有分類精度高，魯棒性強等優(yōu)點，可以很好地彌補粗糙集理論對 錯誤描述的確定性機制過于簡單，當(dāng)數(shù)據(jù)中存在噪聲時，其結(jié)果往往不穩(wěn)定，精度 不高等缺點。文10叼討論了將粗糙集理論和神經(jīng)網(wǎng)絡(luò)有效結(jié)合的方法，使用粗糙 集理論對輸入到神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)進行屬性約簡和屬性值約簡，使得網(wǎng)絡(luò)的學(xué)習(xí)速度大 大加快，分類精度顯著提高。遺傳算法具有全局搜索，自適應(yīng)演化的優(yōu)點，可被應(yīng)用在粗糙集理論的很多 方面，例如用來求取連續(xù)屬性值的最優(yōu)量化區(qū)間個數(shù)及各個區(qū)間分點值，利用它計

12、算粗糙集的屬性約簡等。Lingras和Davies提出了一種粗糙遺傳算法，該算法 用一對粗糙數(shù)來表示基因，給出了相應(yīng)的適應(yīng)度函數(shù)，并對交叉、變異等 操作進行 了定義。另外，遺傳算法也被應(yīng)用在粗糙集的推理過程中，例如著名的粗糙集系統(tǒng) LERS 系統(tǒng)就采用了遺傳算法的 BBA (Buckerbrigade algorithm)過程1617將粗糙集理論和模糊邏輯相結(jié)合是很自然的，比如利用模糊的概念對決策表中 的連續(xù)屬性進行模糊化，將不可區(qū)分關(guān)系擴展成模糊相似關(guān)系及相應(yīng)的擴展上 下近似 的概念，或者利用模糊推理進行決策以提高魯棒性等12,13。文14建立了基于模糊 優(yōu)勢關(guān)系的上下累積模糊集合的粗糙近似

13、，利用模糊優(yōu)勢關(guān)系來代替不可區(qū)分關(guān)系， 這正是基于模糊邏輯與粗糙集理論融合的思想。經(jīng)典的SVM算法是建立在二次規(guī)劃基礎(chǔ)之上，對于處理大數(shù)據(jù)量的模式分類問 題存在很多困難。文15中提出將粗糙集方法與SVM算法結(jié)合，禾U用粗糙集 理 論在處理大數(shù)據(jù)量、消除冗余信息等方面的優(yōu)勢，減少SVM訓(xùn)練數(shù)據(jù)，提高它的數(shù)據(jù)處理的實時性，縮短訓(xùn)練樣本的時間；同時，借助SVM良好的分類性能， 對約簡后的屬性子集進行分類，具有快速、高識別率和抗干擾性強等優(yōu)點。6、粗糙集 理論研究中存在的問題粗糙集理論是一種有效分析和處理不精確、不一致、不完整等各種不完備信 息 的工具。雖然目前在有關(guān)粗糙集理論及其相關(guān)的研究中取得了一

14、些令人矚目的成果， 但是仍然存在一些至今還沒有很好解決的問題。在粗糙集理論中，對錯誤判斷的決定性機制非常簡單。因此，由粗糙集產(chǎn)生 的決策規(guī)則很不穩(wěn)定而且有較差的分類精確性18。因此為得到精確的決策規(guī)則U，必 須把粗糙集理論和其他數(shù)據(jù)挖掘方法結(jié)合起來。常用的方法是把粗糙集和神經(jīng)網(wǎng)絡(luò)及 模糊集等軟計算方法結(jié)合應(yīng)用。約簡的有效計算問題，如何處理數(shù)據(jù)中的噪音和丟失值問題，連續(xù)屬性離散 化等。雖然目前在這些方面已經(jīng)有了一些初步的研究，但是到目前為止還沒 有找到 真正令人滿意的方法19粗糙集理論所處理的分類必須是完全正確或肯定的，因而它的分類是精確 的，亦即只考慮完全/包含0與/不包含0，而沒有某種程度上

15、的/包含0與/屬于 0；另一個方面它所處理的對象是已知的，且從模型中得到的結(jié)論僅適用于這 些對象。 但在實際應(yīng)用中，往往需要把從小規(guī)模對象集中得到的結(jié)論應(yīng)用于大規(guī) 模對象集上 去。因此，這些局限性限制了粗糙集在實際中的應(yīng)用20。結(jié)語 粗糙集理論經(jīng)過2。多年的發(fā)展，正日益受到重視且日趨完善，它為 處理 不確定信息提供了強有力的分析手段，并己得到廣泛的應(yīng)用。本文重點介紹了當(dāng)前 粗糙集理論及應(yīng)用的研究進展情況，可以看出對這個年輕并高速發(fā)展的學(xué)科來說， 還有非常廣闊的空“值得我“，繼續(xù)去研究探索。參考文獻PawlakZ .R oughs ets.In ternationalJ ournalo fl n

16、formationa ndComputerS cie nce,19 82,11(5):342-356ZiarkoW .V ariableP recisionR oughS etM odel.Jo urnalo fC omputerandS ystem Scie nces,19 93s46:39a-59Katzberg J D. Ziarko W. Variable Precision Rough Sets with As ym m etricb ounds.I n:Z iarko W P,ed .P roc.o fR SKD93.Sp rin ge r-Verlag,1994.16 7A-17

17、74 KryszkiewiczM .R oughs eta pproacht oi ncompletei nformationsys te ms .in formations ciences,19 98, 112:39A-495 Dubois D,P rade H.R ough fuzzy sets and fuzzy roughset s. In ternationalJ ournalo fG eneralS ystems， 1990,17:191-209Quafafou M.a- RST: a generalization of rough set t heory.ln fo rmatio

18、nS ciences,20 00,124(4):301A-316DuboisD .PradeH .Pu ttingR oughS etsa ndF uzzyS etsT ogether.ln : S lowinskiR .In telligentD ecisionS upport:H andbooko fAp pl ica tionsa ndA dvanceso fth eR oughS etT heory.D ordrecht:Kl uw e rA cademicP ublishers,1 992.2 03.232YaoY Y .LingrasP .In terpretationo fb e

19、lieffu nctionsin t het heoryo fr oughs ets.In formationS ciences,19 98,104:81-106SkowronA ,Grgymala-BusseJ W .F rom roughs etth eoryt oe vidence t heory.In :A dvancesi ntheD empsterS haferT heoryo fEv ide nc e.N ew York:J ohnW iley$ ,.So nsI nc.,1 994-19 3A-236JelonekJ ,et a l.R oughS etR eductiono

20、fA ttributesa ndT heirDo ma ni ns for Neural Networks.Computational Intelligence,19 95 .1 1(2)LingrasP ,D aviesC .R oughG enetica lgorithms.In :Z hongN ,Sk ow ro n A eds.P roc.7 th Intl.W ksp on RSFD,S pringer,19 99 . 3 8A-46Chakrabarty K,B iswas R,N anda S.F uzziness in roughset s. F u zzyS etsa ndS ystems,2000,110(2):247-251FernandezS alidoJ M ,MurakamiS .R oughs eta nalysiso fa g eneralt yp eo ffu zzyd atau singt ransitivea ggregationso ffu zzys imilarit yr elations.F uzzyS etsa ndS ystems,2 003,1 39( 3):635 66 0LiuY unxiang,