粗糙集及其他軟計算理論結(jié)合情況進行綜述研究

1、粗糙集與其他軟計算理論結(jié)合情況進行綜述研究  摘 要:最近幾年,對于粗糙集的研究越來越多,尤其是粗糙集與其他軟計算理論相結(jié)合的研究更為突出,取得了很多有意義的研究成果。因此,將此方面目前的主要研究情況進行一個總結(jié),主要介紹了目前粗糙集與模糊集、神經(jīng)網(wǎng)絡(luò)、證據(jù)理論等一些其他軟計算理論之間的結(jié)合研究情況,并對這方面未來的發(fā)展提出了自己的一些觀點。 關(guān)鍵詞:粗糙集; 軟計算; 模糊集; 粗糙模糊集; 模糊粗糙集  Survey on combination of rough sets and other soft computing theories

2、  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,

3、 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 meaningf

4、ul 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 fu

5、ture development in this area. Key words:rough sets; soft computing; fuzzy sets; rough-fuzzy sets; fuzzy-rough sets 0 引言 隨著計算機技術(shù)和網(wǎng)絡(luò)技術(shù)的迅速發(fā)展與廣泛應(yīng)用,人類社會進入了信息爆炸的時代,如何處理并有效利用這些信息已經(jīng)成為世界各國學(xué)者研究的熱點問題。軟計算就是在這種需求背景下出現(xiàn)的一種新技術(shù)。軟計算最初是由模糊集理論的創(chuàng)始人Zadeh1在1994年提出的,它是一種通過對不確定、不精確及不完全真值的數(shù)據(jù)進行容錯處理從而取得低代價、易控制處

6、理以及魯棒性高的方法的集合。目前,軟計算的理論與方法主要包括神經(jīng)網(wǎng)絡(luò)、模糊集、粗糙集、遺傳算法、證據(jù)理論等。 粗糙集是在最近幾年發(fā)展較快的一門理論,它是一種用于分析和處理不確定、不精確問題的數(shù)學(xué)理論,是由波蘭數(shù)學(xué)家Pawlak2在1982年提出的。它的基本思想是通過論域上的等價關(guān)系將論域劃分成若干個等價類,然后利用這些知識對所需處理的不精確或不確定的事物進行一個近似的刻畫。 粗糙集理論最大的特點是它對論域的劃分只依賴于所需處理的數(shù)據(jù)集合本身,不需要任何先驗信息,所以對問題不確定性的描述或處理是比較客觀的。這一點也是它與其他軟計算理論之間的顯著區(qū)別。不過,粗糙集在原始數(shù)據(jù)不精

7、確或不確定時,是無法處理數(shù)據(jù)的,這恰好與軟計算中的其他理論有很強的互補性。因此,粗糙集與其他軟計算理論和方法的結(jié)合已成為粗糙集研究中的一個重要內(nèi)容。本文將對粗糙集與模糊集、神經(jīng)網(wǎng)絡(luò)、概念格以及證據(jù)理論等軟計算理論的結(jié)合研究情況進行介紹,并指出這方面未來的研究發(fā)展方向。 1 粗糙集理論概述 粗糙集是一種用于解決不確定性問題的數(shù)學(xué)工具。粗糙集理論中知識被理解為對事物進行區(qū)分的能力,在形式上表現(xiàn)為對論域的劃分,因而通過論域上的等價關(guān)系表示。粗糙集通過一對上、下近似算子來刻畫事物,它不需要數(shù)據(jù)以外的任何先驗知識,因此具有很高的客觀性。目前,粗糙集被廣泛用于決策分析、機器學(xué)習(xí)、數(shù)據(jù)挖

8、掘等領(lǐng)域38。 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)于論域

9、U的P-基本知識。 定義4 上近似、下近似。設(shè)有知識庫K=(U,S)。其中U為論域,S為U上的一簇等價關(guān)系。對于?XU和論域U上的一個等價關(guān)系RIND(K),則X關(guān)于R的下近似和上近似分別為  下近似 R(X)=YU/R|YX 上近似 R(X)=YU/R|YX=? 集合的上近似和下近似是粗糙集中最核心的概念,粗糙集的數(shù)字特征以及拓?fù)涮卣鞫际怯伤鼈儊砻枋龊涂坍嫷?。?dāng)R=(X)時,稱X是R-精確集;當(dāng)R(X)(X)時,稱X是R-粗糙集,即X是粗糙集。 1.2 粗糙集中的知識約簡 在一個信息系統(tǒng)中,有些描述對象的屬性可能是不必要的

10、,因此需要將這些冗余的屬性予以刪除來提高系統(tǒng)的效率。 給定一個知識庫K=(U,S),對于PS,?RP,如果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的一個約簡,記為GRED(P)。P中所有必要的知識組成的集合稱為P的核,記為Core(P)。約簡與核的關(guān)系為Core(P)=RED(P),即核是約簡的交集。  常見的粗糙集中知識約

11、簡的算法主要有盲目刪除約簡法、基于Pawlak屬性重要度的約簡法和基于差別矩陣的約簡法。其中,盲目刪除法是通過任意選擇一個屬性,看其是否是必要的,如果是必要的則保留,否則刪除該屬性,這種方法簡單直觀,但約簡的結(jié)果卻不一定讓人滿意;基于Pawlak屬性重要度的方法是根據(jù)屬性的重要度來進行約簡,其特點是用這種方法可以得到信息系統(tǒng)的最優(yōu)約簡或次優(yōu)約簡,但它卻存在找不到一個約簡可能性;基于差別矩陣的方法是把論域中區(qū)分任意兩個對象的屬性集合用矩陣的形式表示出來,通過這個矩陣可以直觀地得出信息系統(tǒng)的核和所有約簡,這種方法雖然能很直觀地得出信息系統(tǒng)的所有約簡和核,但當(dāng)問題規(guī)模較大時會產(chǎn)生組合爆炸。此外,也有

12、學(xué)者對知識的約簡提出了一些改進的新算法。文獻(xiàn)10, 11基于鄰域?qū)Υ植诩膶傩院蛯傩灾档募s簡進行了優(yōu)化處理;文獻(xiàn)12提出了一種新的屬性約簡方法ReCA,提高了對連續(xù)性屬性的數(shù)據(jù)的知識約簡性能。 粗糙集在處理不確定問題中新穎獨特的方法引起了大量學(xué)者的興趣,很多學(xué)者對該理論作出了擴展性的研究1317,包括覆蓋粗糙集1821、變精度的粗糙集22等很多新的內(nèi)容。文獻(xiàn)23對粗集的公理化進行了深入的研究,得到了兩個關(guān)于粗集的最小公理組;文獻(xiàn)24通過松弛對象之間的不可分辨和相容性條件,給出了一種新的基于和諧關(guān)系的粗糙集模型;文獻(xiàn)25構(gòu)造了關(guān)于決策表對象的區(qū)分條件,并借助區(qū)分矩陣與區(qū)分函數(shù)提出了一種

13、完備的約簡方法;文獻(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)用。 2 粗糙集與模糊集 模糊集理論是由美國學(xué)者Zadeh于1965年提出的,模糊集指的是這樣一種集合,這個集合中的每個元素都是在一定程度上隸屬于或者不隸屬于這個集合,用于衡量這種隸屬程度的函數(shù)被稱為隸屬函數(shù)。模糊集中的任意一個元素都是通過隸屬函數(shù)來確

14、定一個隸屬度與之一一對應(yīng)。 2.1 模糊集理論的基本概念 定義6 隸屬度、隸屬函數(shù)。設(shè)U是一個論域,A是U上的一個模糊集,如果?xU,均能確定一個數(shù)?A(x)0,1來表示x隸屬于A的程度,稱這個數(shù)是x對A的隸屬度。其中?A(x)是這樣一個映射:?A:U0,1,x|?A(x)0,1,?A(x)稱為A的隸屬函數(shù)。 隸屬函數(shù)是模糊集的核心基礎(chǔ)概念,由它來確定和描述一個模糊集。對于同一個論域,不同的隸屬函數(shù)確定不同的模糊集,如?A(x)和?B(x)是論域U上的兩個不同的隸屬函數(shù),則由它們可以確定兩個不同的模糊集A和B。模糊集是經(jīng)典集合理論的擴展,當(dāng)一個模糊集的隸屬度只能取

15、0或1時,即?A(x)0,1,模糊集A便退化為一個經(jīng)典集合論中的普通集合。 2.2 模糊集與粗糙集的互補性 在模糊集中,隸屬函數(shù)一般是根據(jù)專家的經(jīng)驗知識或者通過一些統(tǒng)計數(shù)據(jù)結(jié)果來確定,具有很大的主觀性,而缺乏一定的客觀性,這也是模糊集的一個根本缺陷。粗糙集中的上近似和下近似是由已知知識庫中客觀存在的對象來確定的,不需要任何先前的假設(shè)條件,具有很強的客觀性。但是,在實際的生活中,有很多已知的、確定的而無須再去進行判斷的先驗知識,如果能直接利用這些知識來解決問題,會帶來很高的效率,而這一點又正是粗糙集所欠缺的。由此可見,粗糙集與模糊集各自的特點之間具有很強的互補性,把它們結(jié)合起

16、來解決問題通常都會比單獨使用它們更為有效。在這方面的研究已經(jīng)有了很大的進展和很多的具體應(yīng)用,粗糙模糊集和模糊粗糙集29便是其中兩個重要的研究成果。 粗糙模糊集主要是通過對模糊集中的隸屬函數(shù)采用粗糙集中集合的上近似與下近似的方法來進行描述,以此來增強模糊集處理問題的客觀性。它是把粗糙集中的上下近似的特點融入到了模糊集當(dāng)中,將模糊集中的隸屬函數(shù)概念擴展成上近似的隸屬函數(shù)和下近似的隸屬函數(shù),由這兩個隸屬函數(shù)所確定的隸屬度值來形成一個區(qū)間;用這個區(qū)間來描述一個元素隸屬于一個模糊集的可能性范圍,而不再是之前的元素與隸屬度之間一一對應(yīng)的情況,即xA的隸屬度不再是?A(x)0,1,而是在下近似的隸

17、屬度,上近似的隸屬度這個區(qū)間。粗糙模糊集的基本定義如下: 定義7 粗糙模糊集。設(shè)U是一個論域,R是U上的一個等價關(guān)系,A是U上的一個模糊集,?A(x)是A的隸屬度函數(shù),R(A)和(A)分別表示A的上近似和下近似,它們對應(yīng)的隸屬函數(shù)是: a)下近似的隸屬函數(shù)R(A)(x?R)=inf?A(x)|xx?R,?xX;  b)上近似的隸屬函數(shù)(A)=sup?A(x)|xx?R,?xX。 稱R(X)=(R(X),(X)為粗糙模糊集。  模糊粗糙集是把模糊集中的隸屬函數(shù)的概念應(yīng)用到了粗糙集當(dāng)中,根據(jù)模糊集中的隸屬函數(shù)來確定粗糙集中的一個

18、等價關(guān)系,即把由隸屬函數(shù)得到的隸屬度相同的元素歸屬于同一等價類,從而得到論域U上的一個劃分。這其實就是將模糊集中已知的、確定的而無須再判斷的知識轉(zhuǎn)變?yōu)榇植诩械牡葍r關(guān)系,得到粗糙集上的一簇等價類,提高粗糙集處理問題的效率。模糊粗糙集的基本概念定義如下: 定義8 模糊粗糙集。給定一個論域U,A是U的一個模糊集,?A(x)是A的隸屬函數(shù)。設(shè)R?A為U上的一個等價關(guān)系,且滿足對于?x,yU,xR?Ay?A(x)=?A(y)。令xR?A表示以x為代表元素的等價類,若XU,X?,則X關(guān)于R?A的下近似和上近似分別為  下近似 R?A(X)=xR?A|xR?AX 上

19、近似 ?A(X)=xR?A|xR?AX?  若R?A(X)=?A(X),稱X是R?A-可定義集;若R?A(X)?A(X),稱X是R?A-模糊粗糙集。  粗糙模糊集和模糊粗糙集對粗糙集和模糊集進行很好的互補性處理,已經(jīng)在很多領(lǐng)域得到了實際應(yīng)用3033,并取得了很好的效果。有很多學(xué)者對它們進行了進一步的比較研究3437,作了一些改進和擴展。文獻(xiàn)38在覆蓋粗糙集的基礎(chǔ)上,結(jié)合模糊集的最近尋常集,引入了覆蓋廣義粗糙集模糊度的概念,給出了一種模糊度計算方法,并證明了該模糊度的一些重要性質(zhì);文獻(xiàn)39提出了模糊不可分辨關(guān)系的概念,加強了粗糙集對模糊值屬性處理能力。&#

20、160;3 粗糙集與神經(jīng)網(wǎng)絡(luò) 神經(jīng)網(wǎng)絡(luò)是在現(xiàn)代神經(jīng)生物學(xué)研究成果的基礎(chǔ)上發(fā)展起來的一種模仿人腦信息處理機制的網(wǎng)絡(luò)系統(tǒng)。它具有在有監(jiān)督或無監(jiān)督的情況下從輸入數(shù)據(jù)中進行學(xué)習(xí)的能力,被廣泛地應(yīng)用于數(shù)據(jù)挖掘4042、模式識別4347、信號處理48,49、預(yù)測50, 51等領(lǐng)域。 3.1 神經(jīng)網(wǎng)絡(luò)基本知識 神經(jīng)網(wǎng)絡(luò)52是一個由簡單處理單元構(gòu)成的規(guī)模宏大的并行分布式處理器,天然具有存儲經(jīng)驗知識和使之可用的特性。神經(jīng)元是神經(jīng)網(wǎng)絡(luò)最基本的信息處理單元,它具有接收和傳遞信息的功能。一個神經(jīng)網(wǎng)絡(luò)是由眾多的神經(jīng)元組成,每個神經(jīng)元接收其他神經(jīng)元和外界的輸入信息。神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)通常都是以層

21、的方式來組織的,一般包含一個輸入層、任意多個隱藏層和一個輸出層,每層都由眾多的神經(jīng)元組成。其基本原理是輸入層神經(jīng)元接收外界環(huán)境的信息輸入,隱藏層神經(jīng)元將隱藏層單元的信息輸出至輸出層,輸出層將信息輸出至外界。根據(jù)神經(jīng)元信息的輸出是否存在反饋,又將神經(jīng)網(wǎng)絡(luò)分為前饋神經(jīng)網(wǎng)絡(luò)和遞歸神經(jīng)網(wǎng)絡(luò)。3.2 粗糙集與神經(jīng)網(wǎng)絡(luò)的聯(lián)系 粗糙集對事物的識別和判斷是基于論域上的不可辨關(guān)系,它不需要任何先驗的信息。通過系統(tǒng)參數(shù)的重要度函數(shù)來獲得描述事物各個屬性的重要度,依此不僅可以進行屬性的約簡,而且也可以用于把握事物的主要特征,提高識別能力。粗糙集可以實現(xiàn)對信息系統(tǒng)的知識約簡,去除冗余的信息,減少輸入信息的空

22、間維度,提高處理效率。不過粗糙集的抗干擾能力較差,對于噪聲較為敏感,在噪聲較大的環(huán)境中就表現(xiàn)得不盡如人意。 神經(jīng)網(wǎng)絡(luò)的特點就是通過訓(xùn)練和學(xué)習(xí)產(chǎn)生一個非線性的映射,模擬人的思維方式,具有很好的自適應(yīng)性,可以實現(xiàn)有監(jiān)督和無監(jiān)督的學(xué)習(xí),并能夠?qū)π畔⑦M行并行處理;同時,它具有很好的抑制噪聲的能力。但是神經(jīng)網(wǎng)絡(luò)也有很明顯的缺陷,它無法對輸入的信息進行有用性或冗余性的判斷,因此不能對輸入的信息進行簡化,這使得它在處理空間維數(shù)較大的信息時會很困難和低效。 粗糙集與神經(jīng)網(wǎng)絡(luò)各自的長處和短處讓人們發(fā)現(xiàn)它們具有很好的互補性;另外,從對人類思維模擬的角度看,粗糙集方法模擬人類的抽象邏輯思維,而神

23、經(jīng)網(wǎng)絡(luò)方法模擬人類的形象直覺思維。因此,將兩者結(jié)合起來,用粗糙集的特點去彌補神經(jīng)網(wǎng)絡(luò)在處理髙維度數(shù)據(jù)上的不足,而用神經(jīng)網(wǎng)絡(luò)的抗干擾強的特性去彌補粗糙集對噪聲的敏感性,將模擬人的抽象思維與形象直覺思維相結(jié)合,就會得到更好的效果。目前,這方面的研究已成為一個重要的研究方向。 3.3 粗糙集與神經(jīng)網(wǎng)絡(luò)的結(jié)合 粗糙集與神經(jīng)網(wǎng)絡(luò)最常見的結(jié)合方式主要有兩種:a)將粗糙集作為神經(jīng)網(wǎng)絡(luò)的前端處理器53,通過利用粗糙集先對原始信息進行屬性及屬性值的約簡,去除冗余信息,降低信息空間的維度,為神經(jīng)網(wǎng)絡(luò)提供一個較為簡化的訓(xùn)練集,然后再構(gòu)建和訓(xùn)練神經(jīng)網(wǎng)絡(luò)。這樣的結(jié)合方式不僅縮短了神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)和訓(xùn)練

24、的時間,提高了系統(tǒng)反應(yīng)速度,而且也可以充分發(fā)揮神經(jīng)網(wǎng)絡(luò)在抗噪性和容錯性的優(yōu)勢,達(dá)到提高神經(jīng)網(wǎng)絡(luò)整體性能的目的。b)通過在神經(jīng)網(wǎng)絡(luò)中引入一種粗糙神經(jīng)元來進行,將粗糙神經(jīng)元與普通神經(jīng)元混合起來使用構(gòu)成粗糙神經(jīng)網(wǎng)絡(luò)。 粗糙神經(jīng)元是Lingras54設(shè)計的一種由一對重疊的普通神經(jīng)元上神經(jīng)元和下神經(jīng)元r組成,如圖1所示。粗糙神經(jīng)元中上神經(jīng)元和下神經(jīng)元r整體看成是一個神經(jīng)元r,神經(jīng)元之間的連線表示信息的相互交換。圖24分別表示粗糙神經(jīng)r與s之間的全連接、抑制連接和激勵連接三種常見連接方式。粗糙神經(jīng)元的輸出是具有上近似和下近似的一對數(shù)值,而普通神經(jīng)元只有一個輸出值。下近似或上近似的神經(jīng)元輸入根據(jù)以

25、下公式計算權(quán)值: input?i=?nj=1wji×output?j 其中:wji為神經(jīng)元j到i神經(jīng)元間的連接權(quán)值,n表示i與j間存在的連接個數(shù)。  若f(u)為神經(jīng)元激勵函數(shù),則粗糙神經(jīng)元的上下神經(jīng)元的輸出值分別為 output?=max(f(input?), f(inputr) output?r=min(f(input?), f(inputr) 計算普通神經(jīng)元i的單個輸出值的公式: output?i=f(input?i) 函數(shù)f(input)為sigmoid型函數(shù),定義如下: f(

26、u)=1/(1+e?-gain×u) 其中:增益系數(shù)gain是由系統(tǒng)的設(shè)計者確定的斜率。f(u)采用sigmoid型轉(zhuǎn)移函數(shù)是因這種轉(zhuǎn)移函數(shù)在01具有連續(xù)的取值。 有關(guān)粗糙集與神經(jīng)網(wǎng)絡(luò)的結(jié)合研究,還有其他學(xué)者研究提出的一些新的結(jié)合方式,如強耦合集成55方式,為解決神經(jīng)網(wǎng)絡(luò)設(shè)計中的網(wǎng)絡(luò)的隱層數(shù)、隱層節(jié)點數(shù)和初始權(quán)值的確定及網(wǎng)絡(luò)語義提供了一種便于實現(xiàn)的新思路。隨著軟計算理論中的各種理論和技術(shù)的不斷發(fā)展和創(chuàng)新,將神經(jīng)網(wǎng)絡(luò)與諸如進化算法、概念格、證據(jù)理論及混沌學(xué)等加強結(jié)合研究,相信會取得更加讓人振奮的成就。  4 粗糙集與遺傳算法 遺傳算法5

27、6是一種自然進化系統(tǒng)的計算機模型,也是一種通用的求解優(yōu)化問題的適應(yīng)性搜索方法。它的本質(zhì)特征在于群體搜索策略和簡單的遺傳算子,是目前進化算法中最為重要的一種算法,廣泛地應(yīng)用于人工智能、數(shù)據(jù)挖掘、自動控制及商業(yè)等領(lǐng)域。 4.1 遺傳算法基本原理 遺傳算法通過模擬自然選擇和遺傳機制,以迭代的方式對其研究的對象群體進行適應(yīng)性評價、選擇、重組,直到目標(biāo)群體滿足預(yù)定的要求或者達(dá)到最大迭代次數(shù),從而得到其希望的最優(yōu)解。遺傳算法的關(guān)鍵問題是對問題空間中個體的編碼方式的選擇、適應(yīng)函數(shù)的確定,以及遺傳策略中選擇、交叉、變異三個遺傳算子和選擇概率p?s、交叉概率p?c、變異概率p?m等遺傳參數(shù)的

28、確定。下面是一個標(biāo)準(zhǔn)遺傳算法的算法描述56: 迭代開始(iteration):t=0 初始化(initialize):P(0)=a?1(0),a?2(0),a?n(0) 適應(yīng)性評價(evaluate):P(0)=f(a?1(0), f(a?n(0) while(循環(huán))T(P(t)true do 選擇(select):P(t)=s(P(t),p?s) 交叉(crossover):P(t)=c(P(t),p?c) 變異(mutate):P?(t)=m(P(t),p?m) 新一代群體:P(t+1)=P?(t),t=t+1

29、 適應(yīng)性評價(evaluate): P(t+1)=f(a?1(t+1), f(a?n(t+1) 結(jié)束(end do) 4.2 粗糙集與遺傳算法的結(jié)合 粗糙集與遺傳算法的結(jié)合主要應(yīng)用在屬性的約簡5759、數(shù)據(jù)挖掘60等方面。粗糙集中對于屬性的約簡通常采用啟發(fā)式算法,如基于Pawlak屬性重要度的屬性約簡算法、基于差別矩陣的屬性約簡算法等。這種方法在一定的問題規(guī)模范圍內(nèi)會較為有效,但隨著問題的規(guī)模增大,其最小約簡的求解難度也會大幅增加。遺傳約簡算法是求取信息系統(tǒng)最小約簡或者相對最小約簡的一種算法。所謂最小約簡或者相對最小約簡,就是屬性集的所有約簡或

30、者相對約簡中,包含屬性個數(shù)最少的屬性集。由于遺傳算法是一種基于全局優(yōu)化的搜索方法,并具有并行性和很好的魯棒性,能夠防止搜索陷入局部最優(yōu)解的困境,更利于處理大規(guī)模問題的約簡。 文獻(xiàn)57根據(jù)可辨別關(guān)系的下三角矩陣,利用遺傳算法提出一種基于遺傳算法的粗糙集知識約簡算法,這種算法不僅可以得到正確的約簡,而且也能解決粗糙集中啟發(fā)式算法無法求解的部分問題;文獻(xiàn)61將信息論角度定義的屬性重要性度量作為啟發(fā)式信息引入遺傳算法,并構(gòu)造一個新的算子modifypop(t+1)來對種群進行修復(fù),既保證了算法的整體優(yōu)化性,也提高了算法的收斂速度。在數(shù)據(jù)挖掘方面,文獻(xiàn)60將粗糙集與遺傳算法相結(jié)合,提出一種從大

31、型數(shù)據(jù)表中獲取決策規(guī)則的方法。該方法利用粗糙集中屬性的重要度和核的思想得到屬性的約簡,然后借助遺傳算法來求得最優(yōu)解。此外,對連續(xù)屬性的離散化處理是粗糙集中的一個重要問題。屬性離散化處理的關(guān)鍵在于選取合適的斷點對條件屬性構(gòu)成的空間進行劃分以減少搜索空間。文獻(xiàn)62針對該問題利用遺傳算法將最小斷點集作為優(yōu)化目標(biāo),并構(gòu)造一個新的算子來保證所選斷點能保持原決策系統(tǒng)的不可分辯關(guān)系。 5 粗糙集與概念格 概念格理論也被稱做形式概念分析理論,是由德國數(shù)學(xué)家While提出的一種基于概念和概念層次的數(shù)學(xué)化表達(dá)63,對于數(shù)據(jù)分析和規(guī)則提取非常有效。目前廣泛應(yīng)用于機器學(xué)習(xí)64、軟件工程65等領(lǐng)域。

32、 5.1 概念格理論的基本知識  定義966 形式背景。稱(U,A,I)為一個形式背景,其中U=x?1,x?2,x?n為對象集,每個x?i(in)稱為一個對象;A=a?1,a?2,a?n為屬性集,每個a?j(jm)稱為一個屬性;I為U與A之間的二元關(guān)系,IU×A。若(x,a)I ,則說x具有屬性a,記為xIa。 在形式背景(U,A,I)下,若對象子集XU,屬性子集BA,分別定義運算算子X?*和B?*為  X?*=a|aA,?xX,xIa B?*=x|xU,?aB,xIa 其中:X?*表示X中所有對象共同具

33、有的屬性的集合,B?*表示共同具有B中所有屬性的對象集合。  定義10 形式概念。設(shè)(U,A,I)為形式背景,如果一個二元組(X,B)滿足X?*=B且B?*=X,則稱(X,B)是一個形式概念,簡稱概念。其中,X稱為概念的外延,B稱為概念的內(nèi)涵。 定義1167 子概念、父概念。如果(X?1,B?1)(X?2,B?2),且兩者之間不存在與它們不同的概念(Y,C),滿足(X?1,?B?1)(Y,C)(X?2,B?2),則稱(X?1,B?1)是(X?2,B?2)的子概念,(X?2,B?2)是(X?1,B?1)的父概念。5.2 粗糙集與概念格的聯(lián)系 粗糙集與概念格

34、之間都是基于二元關(guān)系的數(shù)據(jù)表來展開研究的。粗糙集是根據(jù)其論域上的不可辨關(guān)系實現(xiàn)對論域的劃分,產(chǎn)生若干個等價類。概念格是基于形式概念,結(jié)合序理論和完備格理論進行概念分層討論。概念格的每個概念就是具有最大共同屬性的對象的集合,這一點與粗糙集的等價類非常相似。在形式背景中,外延即是由內(nèi)涵所確定的等價類。因此,粗糙集的一些性質(zhì)包括等價類,上、下近似等都可以通過概念來描述;同時,利用概念格的特殊結(jié)構(gòu)可以得到函數(shù)依賴,從而可以用概念格來直觀地進行條件屬性的約簡。 粗糙集與概念格的相似性讓兩個理論之間有了密切的聯(lián)系,很多學(xué)者將它們結(jié)合起來研究。魏玲等人67分析研究了形式概念與等價類、概念格與劃分之

35、間的相互關(guān)系,得出粗糙集中的劃分和概念格理論中的概念格可以進行相互轉(zhuǎn)換的結(jié)論;文獻(xiàn)68將粗糙集理論中屬性約簡和辨識矩陣的概念引入到形式概念分析中,實現(xiàn)了形式背景中冗余知識的約簡;Yao69,70基于對象定向概念的概念格討論了概念格和粗糙集理論之間的對應(yīng)關(guān)系,將粗糙集理論中上下近似的思想引入到形式概念分析中,分別討論了形式概念分析中的幾種近似算子。文獻(xiàn)71將包含度和偏序集的概念引入到形式概念分析中,對形式概念分析中的一些基本概念分別用包含度和偏序集加以表示。文獻(xiàn)72利用形式概念分析中的名義梯級背景(nominal scale)和平面梯級(plain scaling)的概念,論證了粗糙集理論中的上

36、下近似、屬性依賴等核心概念都可以在相應(yīng)的衍生背景中進行表示,并指出利用梯級的概念可以對粗糙集理論進行擴展,為兩者的融合提供了一個理論平臺。文獻(xiàn)73的研究結(jié)合粗糙集與概念格理論,給出了在形式背景下概念集合上的元素之間的二元運算,使一般意義下的概念格成為帶有算子的概念格。 6 粗糙集與證據(jù)理論  證據(jù)理論74也常稱做D-S理論,是一種利用一組函數(shù)來處理不確定性問題的理論。證據(jù)理論中的證據(jù)指的是研究對象的屬性或者專家經(jīng)驗等。 6.1 證據(jù)理論基礎(chǔ) 設(shè)表示對一個問題的所有可能答案的集合,其中的每一個答案都是的一個子集,子集之間是無交集的,稱為辨識框架。

37、  定義1275 基本可信度分配函數(shù)。設(shè)是一個辨識框架,如果集函數(shù)m:2?0,1滿足m()=0,并且?A?m(A)=1,則稱m為上的基本可信度分配函數(shù);?A?,m(A)稱為A的基本可信度。 在定義12的基礎(chǔ)上,本文定義的冪集2?上的三個測度?函數(shù): a)信任函數(shù)Bel,Bel(X)=?AXm(A),?X; b)似然函數(shù)pl,pl(X)=?AX?m(A); c)公共函數(shù)Q,Q(X)=?X?Am(X)。 其中:信任函數(shù)Bel表達(dá)了對每個命題的信度;似然函數(shù)pl(X)表示對命題X不懷疑的程度;公共函數(shù)Q(X)反映了包含X的集合的所

38、有基本可信度之和。 6.2 粗糙集與證據(jù)理論的聯(lián)系 證據(jù)理論根據(jù)可信度分配函數(shù)來定義信任函數(shù)、似然函數(shù),通過這對函數(shù)在給定證據(jù)下對假設(shè)進行估計和評價。在證據(jù)理論中,證據(jù)主要是已知的事物的屬性或者專家經(jīng)驗等一些先驗知識,這使得證據(jù)推理具有較強主觀性,限制了其使用范圍。證據(jù)理論的這些特征與粗糙集存在明顯的互補性和相似性。粗糙集對于問題的解決是基于一對客觀的近似算子,具有很強的客觀性;而粗糙集中的下、上近似與證據(jù)理論中的信任函數(shù)、似然函數(shù)在形式上又有著一定的相似性。將兩者的優(yōu)勢進行互補以及相似性進行結(jié)合的研究,已成為這個領(lǐng)域的一個重要方向。 文獻(xiàn)76,77通過在一個隨機

39、近似空間上進行粗糙集與證據(jù)理論的相似性研究,得出結(jié)論:證據(jù)理論中的信任函數(shù)與似然函數(shù)可以用粗糙集中下近似與上近似的概率來描述: Bel(X)=|R(X)|/|U|,pl(X)=|(X)|/|U| 文獻(xiàn)78也對粗糙集與證據(jù)理論之間的關(guān)系進行了進一步的研究,認(rèn)為不同的辨識框架與有著不同下、上近似的各種粗糙近似空間之間有著密切聯(lián)系,并可以用這種聯(lián)系來解釋辨識框架上的信任函數(shù)與似然函數(shù),以加深對這兩個理論的?認(rèn)識。 7 結(jié)束語 科技的發(fā)展讓人們對于生活、學(xué)習(xí)、科學(xué)研究等各種現(xiàn)代化工具的期望趨于自動化、便捷化、智能化、高速化。而客觀的現(xiàn)實是人們獲得和需要處理的數(shù)據(jù)

40、不僅數(shù)量龐大復(fù)雜,而且絕大部分都是不確定的、不完整的或者是不全真的。如何有效地、快速地從中提取出人們需要的信息就成了亟待解決的問題。軟計算理論的出現(xiàn)幫助人們在這一方面取得了巨大的成就,粗糙集的迅速發(fā)展也為軟計算理論的應(yīng)用與研究提供了強大支持和擴展。隨著對軟計算理論不斷深入的研究和發(fā)展,人們發(fā)現(xiàn)單個的軟計算理論在理論上和應(yīng)用上都存在著這樣或那樣的不足,而這些理論之間很強的互補特性則可以彌補這些不足。因此,將不同的軟計算理論結(jié)合起來研究已成為當(dāng)前學(xué)術(shù)界的共識。本文主要描述了近年來發(fā)展較快并具有非常新穎特點的粗糙集與軟計算理論中的一些其他理論結(jié)合的研究情況,從中可以看到這種結(jié)合在人工智能、數(shù)據(jù)挖掘、

41、知識發(fā)現(xiàn)、屬性約簡、自動控制以及醫(yī)學(xué)等方面所取得的顯著成就。此外,詞計算79逐漸成為了人工智能領(lǐng)域的研究熱點,詞計算是以詞或文字術(shù)語為對象,而不是數(shù)值為對象的計算方法,而詞或文字本身就具有不確定意義的特點,這恰好與粗糙集對問題的描述特點很相似,因此,將粗糙集與詞計算結(jié)合研究也將是未來粗糙集研究發(fā)展的一個內(nèi)容。這讓筆者相信,隨著對軟計算理論結(jié)合研究的不斷深入,將會看到更為令人欣喜的成功。 目前軟計算理論相互結(jié)合的研究一般只局限于其中某兩個理論之間來展開,而筆者在實際研究中也發(fā)現(xiàn),即使這樣的兩兩結(jié)合也存在很多有待完善和改進的地方,這就需要在以后的研究中能將更多的軟計算理論結(jié)合在一起來研究

42、,取長補短、優(yōu)勢互補,提高這一領(lǐng)域的研究水平。 參考文獻(xiàn): 1ZADEH L A.Fuzzy logic,neural networks and soft computingJ.Communications of the ACM,1994,37(3):77-84.  2PAWLAK Z.Rough setsJ.International Journal of Computer and Information Sciences,1982,11(5):341-356. 3ALVATORE G,BENTTOM,ROMAN S.Rough set th

43、eory for multi criteria decision analysisJ.European Journal of Operational Research,2001,129(1):1-47.  4安利平,陳增強,袁著祉.基于粗集理論的多屬性決策分析J.控制與決策,2005,20(3):294-298. 5李永敏,朱善君,陳湘暉,等.基于粗糙集理論的數(shù)據(jù)挖掘模型J.清華大學(xué)學(xué)報:自然科學(xué)版,1999(1):111-114.6劉清,黃兆華,劉少輝,等.帶Rough算子的決策規(guī)則及數(shù)據(jù)挖掘中的軟計算J.計算機研究與發(fā)展,1999,36(7):33-37.&#

44、160;7張文宇,薛惠鋒,張洪才,等.粗糙集在數(shù)據(jù)挖掘分類規(guī)則中的應(yīng)用研究J.西北工業(yè)大學(xué)學(xué)報, 2002,20(3):430-434. 8陶多秀,呂躍進,鄧春燕.基于粗糙集的多維關(guān)聯(lián)規(guī)則挖掘方法J.計算機應(yīng)用,2009,29(5):1405-1408. 9 苗奪謙,李道國.粗糙集理論、算法與應(yīng)用M.北京:清華大學(xué)出版社,2008. 10胡清華,于達(dá)仁,謝宗霞.基于鄰域?；痛植诒平臄?shù)值屬性約簡J.軟件學(xué)報,2008,19(3):640-649. 11胡清華,趙輝,于達(dá)仁. 基于鄰域粗糙集的符號與數(shù)值屬性快速約簡算法J.模式識別與人工智能,2008,2

45、1(6):732-738. 12商琳,萬瓊,姚望舒,等.一種連續(xù)值屬性約簡方法ReCAJ.計算機研究與發(fā)展, 2005,42(7):1217-1224. 13YAO Yi-yu.Three-way decisions with probabilistic rough setsJ.Information Sciences,2010,180(3):341-353. 14CHEN Yu-min,MIAO Duo-qian,WANG Rui-zhi.A rough set approach to feature selection based on ant colony

46、optimizationJ.Pattern Recognition Letters,2010,31(3):226-233.  15LIANG Ji-ye,WANG Jun-hong,QIAN Yu-hua.A new measure of uncertainty based on knowledge granulation for rough setsJ.Information Sciences,2009,179(4):458-470.  16QIAN Yu-hua,LIANG Ji-ye.Combination entropy and combinat

47、ion granulation in rough set theoryJ.International Journal of Uncertainty, Fuzziness and Knowlege-based Systems,2008,16(2):179-193. 17BASZCZYNSKI J,GRECO S,SOWINSKI R,et al.Monotonic variable consistency rough set approachesJ.International Journal of Approximate Reasoning,2009,50(7):979-999.

48、60;18ZHU W,WANG Fei-yue.A new type of covering rough setC/Proc of the 3rd International IEEE Conference on Intelligent Systems.2006:444-449.  19ZHU W,WANG Fei-yue.Reduction and axiomization of covering ?generalized rough setsJ.Information Sciences,2003,152(1):?217-230.  20ZHU W.T

49、opological approaches to covering rough setsJ.Information Sciences,2007,177(6):1499-1508. 21LIU Gui-long,SAI Ying.A comparison of two types of rough sets induced by coveringsJ.International Journal of Approximate Reasoning,2009,50(3):521-528.  22SLEZAK D,ZIARKO W.Variable precision Ba

50、yesian rough set modelC/Proc of the 9th International Conference on Rough Sets, Fuzzy Sets, Data Mining, and Granular Comuting.Berlin:Springer-Verlag,2003:312-315.  23祝峰,何華燦.粗集的公理化J.計算機學(xué)報,2000,23(3):330-333. 24王玨,劉三陽,王建新.粗糙集理論的擴展模型研究J.同濟大學(xué)學(xué)報:自然科學(xué)版,2006,34(9):1251-1255. 25秦克云,高巖.決

51、策表的正域約簡及核的計算J.西南交通大學(xué)學(xué)報,2007,42(1):125-128. 26張文修,米據(jù)生,吳偉志.不協(xié)調(diào)目標(biāo)信息系統(tǒng)的知識約簡J.計算機學(xué)報,2003,26(1):12-18. 27張海云,梁吉業(yè),錢宇華.基于劃分的信息系統(tǒng)屬性約簡J.計算機應(yīng)用,2006,26(12):2961-2963. 28王國胤,張清華.不同知識粒度下粗糙集的不確定性研究J. 計算機學(xué)報, 2008,31(9):1588-1598. 29DUBOIS D,PRADE H.Rough fuzzy set and fuzzy rough setsJ.Internati

52、onal Journal of General Systems,1990(17):191-209. 30邱衛(wèi)根.基于隨機模糊集的不完全信息系統(tǒng)粗集模型J.模式識別與人工智能,2009,22(1):53-59.  31HONG T,TSENG L,CHIEN B.Mining from incomplete quantitative data by fuzzy rough setsJ.Expert Systems with Applications,2010,37(3):2644-2653.  32LI Jiang-ping,PAN Bao-chang,WEI Yu

53、-ke.Tongue image segmentation based on fuzzy rough setsC/Proc ofInternational Conference on Environmental Science and Information Application Technology.Washington DC:IEEE Computer Society,2009:367-369. 33PETROSINO A,FERONE A.Rough fuzzy set-based image compressionJ.Fuzzy Sets and Systems,2009,

54、160(10):1485-1506.34YAO Yi-yu.Combination of rough and fuzzy sets based on -level setsM/Rough Sets and Data Mining:Analysis for Imprecise Data.Boston:Kluwer Academic Publishers, 1997:301-321. 35YAO Yi-yu.A comparative study of fuzzy sets and rough setsJ.Information Science,1998,109(1-4):227-242

55、. 36HU Qing-hua,YU Da-ren,WU Cong-xin.Fuzzy preference relation rough setsC/Proc ofIEEE International Conference on Granular Computing.2008:300-305.  37WU Wei-zhi.Fuzzy rough sets determined by fuzzy implication operatorsC/Proc ofIEEE International Conference on Granular Computing.Washingt

56、on DC:IEEE Computer Society,2009:596-601.  38徐偉華,張文修.覆蓋廣義粗糙集的模糊性J.模糊系統(tǒng)與數(shù)學(xué),2006,20(6):115-121. 39王熙照,趙素云,王靜紅.基于Rough集理論的模糊值屬性信息表簡化方法J.計算機研究與發(fā)展,2004,41(11):1974-1981.  40宋擒豹,沈鈞毅.神經(jīng)網(wǎng)絡(luò)數(shù)據(jù)挖掘方法中的數(shù)據(jù)準(zhǔn)備問題J.計算機工程與應(yīng)用,2000,36(12):102-104. 41徐建軍.醫(yī)學(xué)影像數(shù)據(jù)挖掘中的人工神經(jīng)網(wǎng)絡(luò)方法研究J.實用放射學(xué)雜志, 2006,22(11):1416-

57、1418. 42周序生,王志明.粗糙集和神經(jīng)網(wǎng)絡(luò)方法在數(shù)據(jù)挖掘中的應(yīng)用J.計算機工程與應(yīng)用,2009,45(7):146-149.  43劉政凱,章楊清.利用分維向量改進神經(jīng)網(wǎng)絡(luò)在遙感模式識別中的分類精度J. 遙感學(xué)報, 1994,9(1):68-72. 44周洪寶,閔珍,宮寧生. 基于粗糙集的神經(jīng)網(wǎng)絡(luò)在模式識別中的應(yīng)用J.計算機工程與設(shè)計,2007,28(22):5464-5467. 45王守覺,李衛(wèi)軍,趙顧良,等.模式識別專用神經(jīng)網(wǎng)絡(luò)計算機系統(tǒng)及應(yīng)用方法:北京,CN1700250P.2005:11-23. 46周志華,皇甫杰,張宏江,等.基

58、于神經(jīng)網(wǎng)絡(luò)集成的多視角人臉識別J.計算機研究與發(fā)展,2001,38(10):1204-1210. 47周志華,李寧,楊育彬,等.基于神經(jīng)網(wǎng)絡(luò)集成的肺癌早期診斷J.計算機研究與發(fā)展,2002,39(10):1248-1253. 48黃春琳,邱玲,沈振康.數(shù)字調(diào)制信號的神經(jīng)網(wǎng)絡(luò)識別方法J.國防科技大學(xué)學(xué)報,1999,21(2):61-64. 49游榮義,陳忠.基于小波變換的盲信號分離的神經(jīng)網(wǎng)絡(luò)方法J.儀器儀表學(xué)報,2005,26(4):415-418. 50XIAO Zhi,YE Shi-jie,ZHONG Bo,et al.BP neural network with rough set for short term load forecastingJ.Expert Systems with Applications,2009,36(1):273-279.  51LIU Hui,KONG Wei,QIU Tian-shuang,et al.A neural network based on rough set(RSNN) for prediction of solitary pulmonary nodulesC/Proc o