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

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

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

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

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

5、素分類到集合丫中，則會(huì)犯分類錯(cuò)誤的可能性 小于夕。VPRS莫型和經(jīng)典粗糙集是兼容的，只要令a二0,就和經(jīng)典模型一致了。 隨著a增大變精度粗糙集的近似邊界區(qū)域變窄，即變精度粗糙集意義下的不確定區(qū) 域變小。因此，變精度粗糙集對(duì)數(shù)據(jù)不一致性有一定的容忍度，在某些場(chǎng)合可以增 強(qiáng)產(chǎn)生規(guī)則的魯棒性，提高預(yù)測(cè)精度2 , Katzberg和Ziarko進(jìn)一步提出了不對(duì)稱邊 界的VPRS莫型，即在上下近似的定義中的R可以是不相同的，從而使此模型更加 一般化3】相似莫型在經(jīng)典的粗糙集莫型中，當(dāng)數(shù)據(jù)中存在缺失的屬性值的時(shí)候，不可區(qū)分關(guān)系或者 說是等價(jià)關(guān)系無法應(yīng)付這種情形。為擴(kuò)展粗糙集的處理能力，可以使用相似關(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ǔ)上定義了相對(duì)吸收集的概念，相對(duì)吸收集中的任意兩個(gè) 元素都相似且具有同樣的決策值；相對(duì)吸收集可以用來進(jìn)行數(shù)據(jù)削減。莫糊粗糙集莫型在人們的實(shí)際生活中，涉及到的知識(shí)或概念往往是莫糊的不確定的，為了獲得 對(duì)莫糊概念更好的近似表示，D.D u

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

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

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

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

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

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

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

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

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