摘 要:最近幾年,對于粗糙集的研究越來越多,尤其是粗糙集與其他軟計算理論相結(jié)合的研究更為突出,取得了很多有意義的研究成果。因此,將此方面目前的主要研究情況進(jìn)行一個總結(jié),主要介紹了目前粗糙集與模糊集、神經(jīng)網(wǎng)絡(luò)、證據(jù)理論等一些其他軟計算理論之間的結(jié)合研究情況,并對這方面未來的發(fā)展提出了自己的一些觀點。
關(guān)鍵詞:粗糙集; 軟計算; 模糊集; 粗糙模糊集; 模糊粗糙集
Survey on combination of rough sets and other soft computing theories
TANG Jian-guo??1,2, William ZHU?1,SHE Kun?1, CHEN Wen??1,3
(1.School of Computer Science & Engineering, University of Electronic Science & Technology of China, Chengdu 611731, China;2.School of Computer Science & Engineering, Xinjiang University of Finance & Economics, Urumqi 830012, China;3.Dept. of Computer Science, Fuzhou Polytechnic, Fuzhou 350108, China)?Abstract:In recent years, there are more and more research on rough sets.Especially,the combinations of rough sets and other soft computing theories have became more prominent,and have made a lot of meaningful research results. In view of this, this paper gave a summary of the current status of these major researchs.It focused on the combination of rough sets and other soft computing theories such as fuzzy sets,neural net,evidence theory,and so on. In the end, it put forward the own viewpoint of the future development in this area.
Key words:rough sets; soft computing; fuzzy sets; rough-fuzzy sets; fuzzy-rough sets
0 引言
隨著計算機(jī)技術(shù)和網(wǎng)絡(luò)技術(shù)的迅速發(fā)展與廣泛應(yīng)用,人類社會進(jìn)入了信息爆炸的時代,如何處理并有效利用這些信息已經(jīng)成為世界各國學(xué)者研究的熱點問題。軟計算就是在這種需求背景下出現(xiàn)的一種新技術(shù)。軟計算最初是由模糊集理論的創(chuàng)始人Zadeh[1]在1994年提出的,它是一種通過對不確定、不精確及不完全真值的數(shù)據(jù)進(jìn)行容錯處理從而取得低代價、易控制處理以及魯棒性高的方法的集合。目前,軟計算的理論與方法主要包括神經(jīng)網(wǎng)絡(luò)、模糊集、粗糙集、遺傳算法、證據(jù)理論等。
粗糙集是在最近幾年發(fā)展較快的一門理論,它是一種用于分析和處理不確定、不精確問題的數(shù)學(xué)理論,是由波蘭數(shù)學(xué)家 Pawlak[2]在1982年提出的。它的基本思想是通過論域上的等價關(guān)系將論域劃分成若干個等價類,然后利用這些知識對所需處理的不精確或不確定的事物進(jìn)行一個近似的刻畫。
粗糙集理論最大的特點是它對論域的劃分只依賴于所需處理的數(shù)據(jù)集合本身,不需要任何先驗信息,所以對問題不確定性的描述或處理是比較客觀的。這一點也是它與其他軟計算理論之間的顯著區(qū)別。不過,粗糙集在原始數(shù)據(jù)不精確或不確定時,是無法處理數(shù)據(jù)的,這恰好與軟計算中的其他理論有很強(qiáng)的互補(bǔ)性。因此,粗糙集與其他軟計算理論和方法的結(jié)合已成為粗糙集研究中的一個重要內(nèi)容。本文將對粗糙集與模糊集、神經(jīng)網(wǎng)絡(luò)、概念格以及證據(jù)理論等軟計算理論的結(jié)合研究情況進(jìn)行介紹,并指出這方面未來的研究發(fā)展方向。
1 粗糙集理論概述
粗糙集是一種用于解決不確定性問題的數(shù)學(xué)工具。粗糙集理論中知識被理解為對事物進(jìn)行區(qū)分的能力,在形式上表現(xiàn)為對論域的劃分,因而通過論域上的等價關(guān)系表示。粗糙集通過一對上、下近似算子來刻畫事物,它不需要數(shù)據(jù)以外的任何先驗知識,因此具有很高的客觀性。目前,粗糙集被廣泛用于決策分析、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域[3~8]。
1.1 粗糙集中的基本概念[9]
定義1 論域、概念。設(shè)U是所需研究的對象組成的非空有限集合,稱為一個論域,即論域U。論域U的任意一個子集XU,稱為論域U的一個概念。論域U中任意一個子集簇稱為關(guān)于U的知識。
定義2 知識庫。給定一個論域U和U上的一簇等價關(guān)系S,稱二元組K=(U,S)是關(guān)于論域U的知識庫或近似空間。
定義3 不可分辨關(guān)系。給定一個論域U和U上的一簇等價關(guān)系S,若PS,且P≠?,則∩P仍然是論域U上的一個等價關(guān)系,稱為P上的不可分辨關(guān)系,記做IND(P)。
稱劃分U/IND(P)為知識庫K=(U,S)中關(guān)于論域U的P-基本知識。
定義4 上近似、下近似。設(shè)有知識庫K=(U,S)。其中U為論域,S為U上的一簇等價關(guān)系。對于?X∈U和論域U上的一個等價關(guān)系R∈IND(K),則X關(guān)于R的下近似和上近似分別為
下近似 R(X)=∪{Y∈U/R|YX}
上近似 R(X)=∪{Y∈U/R|Y∩X=?}
集合的上近似和下近似是粗糙集中最核心的概念,粗糙集的數(shù)字特征以及拓?fù)涮卣鞫际怯伤鼈儊砻枋龊涂坍嫷摹．?dāng)R=(X)時,稱X是R-精確集;當(dāng)R(X)≠(X)時,稱X是R-粗糙集,即X是粗糙集。
1.2 粗糙集中的知識約簡
在一個信息系統(tǒng)中,有些描述對象的屬性可能是不必要的,因此需要將這些冗余的屬性予以刪除來提高系統(tǒng)的效率。
給定一個知識庫K=(U,S),對于PS,?R∈P,如果IND(P)=IND(P-{R})成立,則稱R為P中不必要的,否則稱R為P中必要的。如果P中的每個R都是必要的,則稱P是獨立的。
定義5 約簡、核。給定一個知識庫K=(U,S)和知識庫上的一簇等價關(guān)系PS,對于任意GP,如果G是獨立的,并且IND(G)=IND(P),則稱G是P的一個約簡,記為G∈RED(P)。P中所有必要的知識組成的集合稱為P的核,記為Core(P)。約簡與核的關(guān)系為Core(P)=∩RED(P),即核是約簡的交集。
常見的粗糙集中知識約簡的算法主要有盲目刪除約簡法、基于Pawlak屬性重要度的約簡法和基于差別矩陣的約簡法。其中,盲目刪除法是通過任意選擇一個屬性,看其是否是必要的,如果是必要的則保留,否則刪除該屬性,這種方法簡單直觀,但約簡的結(jié)果卻不一定讓人滿意;基于Pawlak屬性重要度的方法是根據(jù)屬性的重要度來進(jìn)行約簡,其特點是用這種方法可以得到信息系統(tǒng)的最優(yōu)約簡或次優(yōu)約簡,但它卻存在找不到一個約簡可能性;基于差別矩陣的方法是把論域中區(qū)分任意兩個對象的屬性集合用矩陣的形式表示出來,通過這個矩陣可以直觀地得出信息系統(tǒng)的核和所有約簡,這種方法雖然能很直觀地得出信息系統(tǒng)的所有約簡和核,但當(dāng)問題規(guī)模較大時會產(chǎn)生組合爆炸。此外,也有學(xué)者對知識的約簡提出了一些改進(jìn)的新算法。文獻(xiàn)[10, 11]基于鄰域?qū)Υ植诩膶傩院蛯傩灾档募s簡進(jìn)行了優(yōu)化處理;文獻(xiàn)[12]提出了一種新的屬性約簡方法ReCA,提高了對連續(xù)性屬性的數(shù)據(jù)的知識約簡性能。
粗糙集在處理不確定問題中新穎獨特的方法引起了大量學(xué)者的興趣,很多學(xué)者對該理論作出了擴(kuò)展性的研究[13~17],包括覆蓋粗糙集[18~21]、變精度的粗糙集[22]等很多新的內(nèi)容。文獻(xiàn)[23]對粗集的公理化進(jìn)行了深入的研究,得到了兩個關(guān)于粗集的最小公理組;文獻(xiàn)[24]通過松弛對象之間的不可分辨和相容性條件,給出了一種新的基于和諧關(guān)系的粗糙集模型;文獻(xiàn)[25]構(gòu)造了關(guān)于決策表對象的區(qū)分條件,并借助區(qū)分矩陣與區(qū)分函數(shù)提出了一種完備的約簡方法;文獻(xiàn)[16]將組合熵和組合粒度的概念引入到了粗糙集中,確立了兩者之間的關(guān)系;文獻(xiàn)[26]提出了在不協(xié)調(diào)目標(biāo)信息系統(tǒng)中知識約簡的新方法; 文獻(xiàn)[27]提出了屬性左劃分和屬性右劃分的觀點,設(shè)計了一種基于劃分的屬性約簡算法ARABP;文獻(xiàn)[28]從屬性和信息熵的角度探討了粗糙集的不確定性的度量。這些研究極大地推動了粗糙集理論的發(fā)展和應(yīng)用。