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