（運(yùn)籌學(xué)與控制論專業(yè)論文）粗糙集理論及其推廣模型的研究.pdf

摘要 摘要 粗糙集理論，作為一種新型的處理不確性和不精確性知識的數(shù)學(xué)方法，是波 蘭數(shù)學(xué)z d z i s l a w p a w l a k 于1 9 8 2 年提出的。其主要思想是利用已知的知識或信息來 近似不精確的概念或現(xiàn)象。自從上世紀(jì)九十年代以來，粗糙集在理論上的不斷完 善，在實(shí)際上的廣泛應(yīng)用逐漸成為國際學(xué)術(shù)界的研究熱點(diǎn)之一。而同為數(shù)據(jù)分析 的有力工具概念格理論和模糊集理論分別是由1 9 8 2 年w i l l er 。和1 9 6 5 年z a d 矗創(chuàng) 立。這兩種理論雖然與粗糙集理論不同，但在數(shù)據(jù)問題的處理上都與之存在一定 的棚容性和相似性，利用粗糙集理論與方法研究概念格理論和模糊集理論，利用 概念格理論和模糊集理論與方法研究粗糙集理論，相互借鑒，相互促進(jìn)，推動了 粗糙集理論的發(fā)展。 基于粗糙集理論圈前的廣泛應(yīng)用，本文就粗糙集理論模型的研究的現(xiàn)狀，主 要采用構(gòu)造型方法，結(jié)合模糊集、概念格、概率等不確定性理論，對經(jīng)典的p a w l a k 粗糙集模型和其它糨糙集模型俸了推廣研究，其具體工作如下： ( 1 ) 結(jié)合粗糙集與概念格在數(shù)據(jù)分析方面的相似之處以及存在的相互聯(lián)系。 本文將概念格在模糊意義下展開，得到由不同蘊(yùn)涵算子表示的模糊概念，并在基 于粗糙集的概念格這一模型的基礎(chǔ)上，針對粗糙集所描述的分類是完全精確的這 一局限性，通過引入闕值，放松了在原粗糙集中要求的概率分類的近似邊界的 嚴(yán)格定義，允許上近似和下近似存在一定的分類誤差，從而討論了基于變精度粗 糙集的概念格與其性質(zhì)。 ( 2 ) 由于現(xiàn)有的模糊粗糙集大多數(shù)定義在模糊最小相似關(guān)系下，這就使得模 糊粗糙集沒有經(jīng)典粗糙集的某蝗性質(zhì)，并且條件模糊最小相似關(guān)系中的模糊最小 傳遞關(guān)系盂的定義太過嚴(yán)格，使得u 中的兩對象冪| l 用模糊最小相似關(guān)系不能有效 的測出兩者的相似度，導(dǎo)致現(xiàn)存的模糊粗糙集的應(yīng)用領(lǐng)域得到限制。針對這一局 限性，本文在已有的模糊粗糙集模型上加以改進(jìn)，孳| 進(jìn)模糊羅相似關(guān)系，并在此關(guān) 系下構(gòu)建新的模糊信息系統(tǒng)，得到了基于新的模糊信息顆粒的模糊r 粗糙集，并 結(jié)合三角模算子r 和穢對其相關(guān)性質(zhì)和上下近似算子之間的關(guān)系進(jìn)行了討論。 關(guān)鍵詞：粗糙集，概念格，模糊粗糙集，下近似，上近似 a b s t r a c t a b s t r a c t r o u g hs e tt h e o r y , an e wm a t h e m a t i c a lt o o ld e a l i n gw i 也v a g u e n e s sa nu n c e r t a i n t y , w a si n 曩o d u c e db yz d z i s l a wp a w l a ki n 19 8 2 弧ep r i m a r yi d e ai st om a k eu s eo ft h e k n o w nk n o w l e d g eo ri n f o r m a t i o na sa l la p p r o x i m a t i o nf o rt h eu n p r e c i s ec o n c e p t so r p h e n o m e n a s i n c et h en i n e t i e so ft h et w e n t i e t hc e n t u r y , t h ec o n t i n u o u sp e r f e c t i n gi n t h e o r ya n dt h ew i d ee x t e n d i n gi na p p l i c a t i o nf o rt h er o u g hs e tb e c a m eav e r yh o t r e s e a r c hs p o t si n t h ew o r l da c a d e m e n e a r l yt h es a m ee r a ，a sw e l la sa p o w e r f u lt o o lf o r d a t aa n a l y s e s ，t h et h e o r yo ft h ef u z z ys e ta n dt h ec o n c e p tl a t t i c ew e r ea d v a n c e db y a a d e hi n19 6 5a n db yw i l l er i n19 8 2 ，r e s p e c t i v e l y t h o u g ht h et w ot h e o r i e sa r e d i f f e r e n tf r o mt h er o u g hs e t s ，m e yb e a rs o m ec o m m o nc o n s i s t e n c ya n dc o m p a r a b i l i t y i nt h ep r o c e s s e so fd a t aa n a l y s e s f u r t h e rd e v e l o p m e n t sh a v eb e e na c h i e v e db yu s i n gt h e t h e o r i e sa n dm e t h o d so fr o u g hs e t ，c o n c e p tl a t t i c ea n dt h ef u z z ys e tf o rr e f e r e n c eo n e a n o t h e r a c c o r d i n gt ot h ep r e s e n ta p p l i c a t i o n so ft h er o u g hs e t ，c o n t i n u o u sg e n e r a l i z a t i o n s t u d i e sf o rr o u g hm o d e lw i l lb ed o n ei nt h i sp a p e r , i tm a i n l ya d o p t st h ef o r m a t i o nw a y s a n da s s o c i a t e sw i t ht h i su n c e r t a i n t yt h e o r i e so fp r o b a b i l i t y , f u z z ys e t ，c o n c e p tl a t t i c e w h i c ha r er e f e r r e dt oa sf o l l o w s ： ( 1 ) a n a l y z et h ec o m p a r a b i l i t ya n dt h er e l a t i o nb e t w e e nt h er o u g hs e ta n dc o n c e p t l a t t i c ei nt h ep r o c e s s e so fd a t aa n a l y s e s 1 1 1 i st e x td e v e l o p e dt h ec o n c e p tl a t t i c eu n d e r t h ei n f o r m a t i o ns y s t e ma n dg a i n e dt h ef u z z yc o n c e p tl a t t i c ee x p r e s s e db yd i f f e r e n t r e s i d u a t e di m p l i c a t i o n s ，骶羚t e x ti se s t a b l i s h e do nt h ec o n c e p tl a t t i c ew h i c hb a s e so n r o u g hs e ta n da i m sa tt h el i m i t a t i o n st h a tt h ec l a s s i f i c a t i o nd e s c r i b e db yr o u g hs e ti s 療 c o m p l e t e l yp r e c i s e b yi n t r o d u c i n gt h et h r e s h o l dv a l u ep ，w eb r o a d e nt h er i g o r o u s d e f i n eo ft h ea p p r o x i m a t eb o u n dd e m a n d e di nf o r m e rr o u g hs e tw i mp r o b a b i l i t y c l a s s i f i c a t i o n w ea l s op r o m i s ec e r t a i ne r r o ro fc l a s s i f i c a t i o ni nu p p e ra n dl o w e r a p p r o x i m a t i o n c o n s e q u e n t l y , w ei l l u m i n a t et h ec o n c e p tl a t t i c eb a s e do nv p r sa n di t s p r o p e r t i e s ( 2 ) t h ee x i s t i n gf u z z yr o u g hs e t s a r ea l ld e f i n e dw i t h r e s p e c t t o f u z z y m i n - s i m i l a r i t yr e l a t i o ns ot h a tm e yh a v en o ts o m ep r o p e r t i e sa st h e 謝s pr o u g hs e t sd o ， 玨 a b s t r a c t a n dt h ec o n d i t i o nn e e d e df o rt h ef u z z ym i n t r a n s i t i v i t yi nt h ef u z z ym i n s i m i l a r i t y r e l a t i o nrd e f i n e dt o os t r i c ts ot h a tt h es i m i l a rd e g r e eb e t w e e nt w oo b j e c ti nu c a n n o tb em e a s u r e de f f e c t i v e l yb ym e a n so ft h ef u z z yr a i n - s i m i l a r i t yr e l a t i o n d u et o t h e s ec h a r a c t e r i s t i c s ，t h ea p p l i c a t i o nf i e l d so ft h ee x i s t i n gf u z z yr o u g hs e t sa r el i m i t e d a i m e da tt h e s el i m i t a t i o n s ，w em a k es o m ei m p r o v e m e n t sf o rt h ef o r m e rf u z z yr o u g hs e t m o d e la n di n t r o d u c et h e f u z z yt 。s i m i l a r i t yr e l a t i o n , c o n s t r u c tan e wf u z z y i n f o r m a t i o ns y s t e m t h e n ，w eo b t a i naf u z z yt - r o u g hs e tb a s e do nt h en e wf u z z y i n f o r m a t i o ng r a n u l e i t sc o r r e s p o n d i n gp r o p e r t i e sa n dt h er e l a t i o n s h i pb e t w e e nt h en e w l o w e l a n du p p e ra p p r o x i m a t i o n sa r ea l s od i s c u s s e di nd e t a i l k e y w o r d s ：r o u g hs e t ，c o n c e p tl a t t i c e , f u z z yr o u g hs e t ，u p p e r ( 1 0 w e r ) a p p r o x i m a t i o n 聯(lián)l 獨(dú)創(chuàng)性聲明 本人聲明所呈交的學(xué)位論文是本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工 作及取得的研究成果。據(jù)我所知，除了文中特另j j ；h i ：l 以標(biāo)注和致謝的地 方外，論文中不包含其他人已經(jīng)發(fā)表或撰寫過的研究成果，也不包含 為獲得電子科技大學(xué)或其它教育機(jī)構(gòu)的學(xué)位或證書而使用過的材料。 與我一同工作的同志對本研究所做的任何貢獻(xiàn)均已在論文中作了明 確的說明并表示謝意。 簽名： 強(qiáng)k 磋上日期：p 嘞年r 月婦 關(guān)于論文使用授權(quán)的說明 本學(xué)位論文作者完全了解電子科技大學(xué)有關(guān)保留、使用學(xué)位論文 的規(guī)定，有權(quán)保留并向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和磁 盤，允許論文被查閱和借閱。本人授權(quán)電子科技大學(xué)可以將學(xué)位論文 的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或 掃描等復(fù)制手段保存、匯編學(xué)位論文。 ( 保密的學(xué)位論文在解密后應(yīng)遵守此規(guī)定) 冒期：e 必年f 胃o ；冒 第一霉緒論 1 1 選題背景 第一章緒論 2 1 世紀(jì)是信息爆炸的時代，計算機(jī)與網(wǎng)絡(luò)信息技術(shù)的飛速發(fā)展使得各個領(lǐng)域 的數(shù)據(jù)和信息急劇增加，并且由于人類的參與使數(shù)據(jù)與信息系統(tǒng)中的不確定性更 加顯著，構(gòu)成了復(fù)雜的信息系統(tǒng)。如何從大量的、雜亂無章的、強(qiáng)干擾的數(shù)據(jù)( 海 量數(shù)據(jù)) 中挖掘潛在的、有利于價值的信息即有用知識，這給人類的智能信息處 理能力提出了前所未有的挑戰(zhàn)，由此產(chǎn)生了人工智能研究的一個嶄新領(lǐng)域數(shù) 據(jù)挖掘( d m ) 和數(shù)據(jù)庫知識發(fā)現(xiàn)( k d d ) 。 褪糙集理論是教授p a w l a kz 。瑟壤! 出熬一種研究不完備、不確定知識和數(shù)據(jù)的 表達(dá)、學(xué)習(xí)、歸納的理論方法，其主要思想就是在保持分類能力不變的前提下， 通過知識約簡，導(dǎo)出問題的決策或分類艇則，從麗獲得知識的簡潔表達(dá)。在粗糙 集的理論中，知識被認(rèn)為是一種對對象進(jìn)行分類的能力，知識庫是分類方法的集 合，這些描述雖然不是十分完備嚴(yán)格，但卻非常清晰地體現(xiàn)了粗糙集模型的基本 思想，為粗糙集理論奠定了基礎(chǔ)，并逐步形成了自身理論體系。 在d m 和k d d 諸多方法中，有基于網(wǎng)絡(luò)結(jié)構(gòu)的神經(jīng)網(wǎng)絡(luò)算法，基于訓(xùn)練選優(yōu) 的遺傳算法，基子統(tǒng)詩理論的數(shù)據(jù)挖掘與支持向量祝方法，基于翔納學(xué)習(xí)的枕器 學(xué)習(xí)方法，基于范例的推理方法，基于生物信息的知識發(fā)現(xiàn)方法等。而對于2 0 世 紀(jì)下半世紀(jì)產(chǎn)生的粗糙集理論與方法對于處理不精確、不確定、不完全信息的復(fù) 雜系統(tǒng)不失為一種有效的方法，因為它與概率方法、模糊集方法和證據(jù)理論方法 等其他處理不確定性問題理論的顯著區(qū)別是它無需提供闖題所需處理的數(shù)據(jù)集合 之外的任何先驗信息，所以對問題的不確定性的描述或處理也是比較客觀的。而另 一方面由于該理論未能包含處理不精確或不確定原始數(shù)據(jù)的機(jī)制，所以與其他處 理不確定性闖題的理論有很強(qiáng)的互補(bǔ)性。 如何從海量數(shù)據(jù)中獲取不同簡潔程度的知識表達(dá)己成為當(dāng)前研究的一個熱 點(diǎn)，但數(shù)據(jù)瘴孛數(shù)據(jù)的缺失又限制了綴多理論與方法對不完備信息系統(tǒng)的有效處 理?，F(xiàn)在雖然對空值有了大量的研究，但基于粗糙集理論的不完備信息系統(tǒng)的研 究還很薄弱，特別是在不改變原信息系統(tǒng)的前提下如何從不完備信息系統(tǒng)中獲取 電子科技火學(xué)碩士學(xué)位論文 知識的理論與方法的研究更為迫切。 因此，有效的將粗糙集理論與其它理論相結(jié)合形成更為有效的方法是目前粗 糙集理論及運(yùn)用研究的重點(diǎn)。 1 2 粗糙集概念的提出 粗糙集理論是由波蘭數(shù)學(xué)家p a w l a kz 于1 9 8 2 年提出的。作為一種刻畫不完整 性和不確定性的有效數(shù)學(xué)工具，粗糙集( r o u g hs e t ，r s ) 理論能有效地分析和處理不 精確、不一致、不完整等各種不完備信息，并從中發(fā)現(xiàn)隱含的知識，揭示潛在的規(guī) 律。八十年代，許多波蘭學(xué)者對粗糙集理論及其應(yīng)用進(jìn)行了堅持不懈的研究，其 中對粗糙集理論的數(shù)學(xué)性質(zhì)及邏輯系統(tǒng)進(jìn)行了廣泛的研究【2 矧。同時，他們也開發(fā) 了一些應(yīng)用系統(tǒng)。但是由于最初的研究成果大多是以波蘭文字發(fā)表在“b u l l e t i no f t h ep o l i s ha c a d e m yo fs c i e n c e s ：m a t h e m a t i c s ”或“b u l l e t i no ft h ep o l i s ha c a d e m yo f s c i e n c e s ：t e c h n i c a ls c i e n c e s 上，該項研究限于東歐各國，當(dāng)時并未引起國際計算 機(jī)學(xué)界和數(shù)學(xué)界的重視，直到2 0 實(shí)際8 0 年代末才逐漸引起各國學(xué)者的注意。1 9 9 1 年p a w l a kz 乜1 的專著，粗糙集一關(guān)于數(shù)據(jù)推理的理論( r o u g hs e t t h e o r e t i c a l a s p e c t so f r e a s o n i n ga b o u td a t a ) 的問世，奠定了粗糙集理論的基礎(chǔ)，標(biāo)志著粗糙集 理論及其應(yīng)用的研究進(jìn)入了活躍時期。同時，隨著1 9 9 2 年s l o w i n s k ir 主編的關(guān)于 粗糙集應(yīng)用及其與相關(guān)得到比較研究的論文集的出版，推動了國際上對粗糙集理 論與應(yīng)用的深入研究，掀起了粗糙集理論的研究高潮。從1 9 9 2 年至今，每年都召 開以r s 為主題的國際會議，推動了r s 理論的拓展和應(yīng)用，國際上成立了粗糙集 學(xué)術(shù)研究會，參加的成員來自波蘭、美國、加拿大、日本、挪威、俄羅斯、烏克 蘭和印度等國家；1 9 9 5 年a c mc o m 姍】n j c a t i o n 【7 】將粗糙集列為新浮現(xiàn)的計算機(jī)科 學(xué)的研究課題，大量關(guān)于粗糙集及其應(yīng)用的學(xué)術(shù)論文和研究性報告應(yīng)運(yùn)而生；1 9 9 8 年國際信息科學(xué)雜志( i n f o r m a t i o ns c i e n c e s ) 還為粗糙集理論的研究出了一期專輯。 由于其在機(jī)器學(xué)習(xí)【2 ，7 】、決策分析8 , 9 , 1 0 】、過程控制、模式識別及數(shù)據(jù)挖掘【1 1 , 1 2 , 1 3 】等 領(lǐng)域的成功運(yùn)用而獲得強(qiáng)大的生命力。 粗糙集理論從新的視角對知識進(jìn)行了定義，把知識看作是關(guān)于論域的劃分， 從而認(rèn)為知識是具有粒度( g r a n u l a r i t y ) 的。認(rèn)為知識的不精確性是由知識粒度太大 引起的。為處理數(shù)據(jù)( 特別是帶噪聲、不精確或不完全數(shù)據(jù)) 分類問題提供了一套嚴(yán) 密的數(shù)學(xué)工具，使得對知識能夠進(jìn)行嚴(yán)密的分析和操作。同時，粗糙集理論是建 2 第一章緒論 立在分類楓制韻基磷主，它將分類理鰓為在特定空聞上的等價關(guān)系，麗等價關(guān)系構(gòu) 成了對該空闋鮑劃分。褪糙集理論褥知識理解秀對數(shù)據(jù)的劃分，每一被鯔分煎集 合稱淹概念。糕糙集理論的主要思想是利用巴知的知識庫，將不精確或不確定的 知識用已知的知識癢中熬知識來描述。該理論與其他處理不確定和不精確問題理 論的最顯著熬區(qū)剎是它無需提供閹題新需處理的數(shù)據(jù)集合之外的任何先驗信息， 所以對問題的不確定性的描述或處理可以說是比較客觀的，由于這個理論未能包 含處理不精確或不確定原始數(shù)據(jù)的機(jī)制，所以這個理論與概率論、模糊數(shù)學(xué) 1 4 , 1 5 】 和證據(jù)理論等其他處理不確定或不精確闖題的理論有很強(qiáng)的互補(bǔ)性。目前r s 理論 已經(jīng)成為入工智髓領(lǐng)域中一個較新的學(xué)術(shù)熱點(diǎn)，弓| 起了越來越多的學(xué)者關(guān)注。 1 3 粗糙集理論的特點(diǎn)及應(yīng)用領(lǐng)域 糨糙集方法的籬單實(shí)用性楚令入驚奇的，它麓在劍立籍的不長時聞內(nèi)得烈迅 速應(yīng)用是爨為具有以下特點(diǎn)f 1 6 q 9 ： ( 1 ) 它能處理備穗數(shù)據(jù)，包括不完整( i n c o m p l e t e ) 的數(shù)據(jù)以及擁有眾多變量的數(shù) 據(jù)； ( 2 ) 它能處理數(shù)據(jù)的不精確性和模棱兩可( a m b i g u i t y ) ，包括確定性和非確定性 的情況； 3 ) 它麓求得翔識的最小表達(dá)( r e d u c t ) 和知識的各種不嗣顙粒( g r a n u l a r i 媯層次； ( 4 ) 它麓從數(shù)據(jù)中揭示出概念簡單，易于操作的模式( p a t t e r n ) ； f 5 ) 它箋產(chǎn)生精確囂又易于檢查和證實(shí)的規(guī)煲l j ，特別逶于智憩控制中瓶則豹叁 動生成。 e l l 于糨糙集方法的特殊性，它能有效地處理下列問題：不確定或不精確知識的 表達(dá)；經(jīng)驗學(xué)習(xí)并從經(jīng)驗中獲取知識；不致信息的分析；根據(jù)不確定、不完整 的知識進(jìn)行推理；在保黧信息的前提下進(jìn)行數(shù)據(jù)化簡；近似模式分類；識別并評 估數(shù)據(jù)之間的裱賴關(guān)系( d a t ad e p e n d e n c i e s ) 。 粗糙集理論從誕生到現(xiàn)在廈然只有幾十年的時間，德已經(jīng)在許多領(lǐng)域取得了 令人鼓舞豹藏果 2 0 , 2 1 2 2 1 ： ( 1 投票數(shù)據(jù)分析。g o l a n 2 3 】等運(yùn)用糕糙集方法分挺了十年閹懿股票鯰歷史數(shù) 據(jù)，研究了股票價格與經(jīng)濟(jì)指數(shù)之間的依賴關(guān)系，獲褥的預(yù)測規(guī)則褥到了華爾街證 券交易專家的認(rèn)可。 電子科技大學(xué)碩士學(xué)位論文 ( 2 ) 模式識別。n 豸撒a n 【2 4 】應(yīng)用粗糙集方法研究彳手寫字符識別閥題，提敢了 特征屬性。 ( 3 ) 地震預(yù)報。t e 曲e m 研究了地震前的地質(zhì)和氣象數(shù)據(jù)與里氏地震級別的依 賴關(guān)系。 ( 4 ) 沖突分析。d c j a 應(yīng)用粗糙集方法建立了反映以色列、巴基斯坦、約旦、埃 及、敘利亞和沙特阿拉伯等六國關(guān)予中東和平閥題各自的談判模型。 ( 5 ) 從數(shù)據(jù)庫中發(fā)現(xiàn)知識。粗糙集方法現(xiàn)成為k d d 的一種重要方法，其導(dǎo)出 的知識精煉且便子儲存和使用。 ( 6 ) 粗糙控制。把控制過程中的一些育代表性的狀態(tài)以及操作人員在這些狀態(tài) 下所采用的控制策略都記錄下來，形成決策表，然后對其分析化簡，總結(jié)出控制 規(guī)則。粗糙集方法是一類符號化分析方法，需要將連續(xù)的控制變量離散化，為此 p a w l a k 提出了粗糙函數(shù)( r o u g hf u n c t i o n ) ，為粗糙控制打下了理論基礎(chǔ)。粗糙控制 的優(yōu)點(diǎn)是簡單迅速、實(shí)現(xiàn)容易，不需要象f u z z y 控制那樣進(jìn)行模糊恍和去模糊化。 因此在特別要求控制器紿構(gòu)和算法簡單的場合，采取粗糙控制較為合適。另外， 由于控制算法完全來自觀測數(shù)據(jù)本身，其決策和推理過程可以很容易被檢驗和證 實(shí)。一種新的有吸引力的控制策略“模糊一粗糙控制 正悄然興起，其主要思路 是利用糨糙集獲取模糊控制規(guī)則。 ( 7 ) 醫(yī)療診斷。粗糙集方法根據(jù)以往的病鍘歸納出診斷規(guī)則，用來知道新的兵 力診斷?，F(xiàn)有的人工預(yù)測早產(chǎn)的準(zhǔn)確率只有1 7 3 8 ，應(yīng)用粗糙集理論則可提高到 6 8 9 0 。 ( 8 ) 專家系統(tǒng)。粗糙集抽取規(guī)則的特點(diǎn)，為構(gòu)造專家系統(tǒng)知識提供了一條嶄新 的途徑。 ( 9 ) 神經(jīng)網(wǎng)絡(luò)。訓(xùn)練世界過于漫長的固有缺點(diǎn)是制約神經(jīng)網(wǎng)絡(luò)實(shí)用化的因索之 一。j e l o n e k 等用褪糙集化籬神經(jīng)網(wǎng)絡(luò)訓(xùn)練樣本數(shù)據(jù)集，在保留重要信息的前提下 消除了多余的數(shù)據(jù)，使訓(xùn)練速度提高了4 7 7 倍，獲得了較好的效果。 雖然粗糙集理論至今只有二十年的發(fā)展歷史，但取得的研究成果是令人矚目 的。它是一種非常有前途的軟計算方法，為處理不確定信息提供了強(qiáng)有力的分析 手段【2 5 2 6 1 。相信粗糙集理論具有廣闊的發(fā)展空間，今后會在更多的實(shí)際領(lǐng)域中發(fā) 揮作用。 4 第一章緒論 1 4 粗糙集的基本概念 給定一個有限的非空集合u 稱為論域，設(shè)尺是u 上一個等價關(guān)系( 滿足自反 性、對稱性和傳遞性) ，記為r u x u 。論域u 中所有與x u 具有等價關(guān)系尺的 元素的集合，記為 = y u y ) r ( 1 - 1 ) 商集v r - - x k i x t r 是等價關(guān)系r 將論域u 進(jìn)行劃分，所得的等價類的集合。 即3 一，x 2 ，吒u ，使得 u = 【x ?！砍遳 【】置u u 【】r ( 1 2 ) 其中【薯kn x j 矗= 囝，i 歹，i ，j = 1 ，2 ，詐。 對于論域u 上的任意一個子集x ，x 不一定能用知識庫中的知識來精確地描 述，即x 可能為不可定義集，這時就用x 關(guān)于a 的一對下近似蹦和上近似勱來 “近似 地描述，其定義如下 2 8 】： 蹦= u 。j d 露_ c x ) = x u l x 。c _ x ) ( 1 3 ) 勱= u 。惻膏f t x , o = 扛u 州足n x f 2 j ) ( 1 - 4 ) 其中，【z 】。是石所在的r 一等價類。 蹦它可以解釋為由那些根據(jù)現(xiàn)有知識判斷出肯定屬于x 的對象所組成的最 大集合，上近似面可以解釋為由那些根據(jù)現(xiàn)有知識判斷出可能屬于x 的對象所組 成的最小集合。p o s 。( ) = 叢為x 的尺正域；n e g 旯( x ) = 【廠一頁( x ) 為x 的尺負(fù)域， 可以解釋為由那些根據(jù)現(xiàn)有知識判斷出肯定不屬于x 的對象所組成的集合。 b n r ( x ) = 頁( x ) 一星( x ) 為x 的r 邊界域，它可以解釋為由那些根據(jù)現(xiàn)有知識判斷出可 能屬于x 但不能完全肯定是否一定屬于x 的對象中所組成的集合。這些概念可由 下圖直觀地描述出來： 電予科技大學(xué)碩：l 二學(xué)位論文 星( x ) 圖l 一1 租糙集上f = 近似圈 在圖中，整個區(qū)域為論域u ，每一小方格代表u i n d ( r ) 的一個元素，即等價類， 包含在概念x 孛的、童若干個空表方格組成的區(qū)域莠蓋的下近似，南瞬影方格組 成的區(qū)域為z 的邊界，由邊界及下近似組成x 的上近似。 x 關(guān)于么的近似精度定義為么柳= 黟，其中| x | 表示集合x 的基數(shù)近似精 度反映了根據(jù)現(xiàn)有知識對并的了鰓程度。 x 關(guān)于么的粗糙度定義為九( x ) = 1 - l i - r 脯x - - - ，它反映了知識的不完全程度顯然 若近似精度為1 ，則粗糙度為0 。 1 5 粗糙集的發(fā)展?fàn)顩r 在經(jīng)典粗糙集理論中，“知識 被認(rèn)為一種將現(xiàn)實(shí)或抽象的對象進(jìn)行分類的能 力，經(jīng)熟粗糙集理論是假設(shè)已知的對象全域擁有必要知識的前提之下進(jìn)行數(shù)據(jù)處 理的。但一般而言，由于信息的缺乏，人們對知識的了解和認(rèn)識往往不夠充分， 但要求分類必須正確或可靠的，不可靠或不正確的分類不能采用該方法解決。但 事實(shí)上，現(xiàn)實(shí)世界中存在的分類規(guī)則往往不是可靠的，但對于大部分已知數(shù)據(jù)采 用該規(guī)則導(dǎo)出的分類是正確的，那么這些包含部分錯誤的分類規(guī)則就能提供有用 的導(dǎo)向信息。由此可見，該分類規(guī)則可以提供有用的導(dǎo)向信息，這些導(dǎo)向信息應(yīng) 該被提取并采用一定的方法進(jìn)行分析，此時，若采用經(jīng)典粗糙集理論分析這些數(shù) 6 第一牽縫論 據(jù)，那么這些導(dǎo)向信息則成為無用信息。也就是說，在數(shù)據(jù)集中存在噪聲等孑撬 情況下，經(jīng)典理論會由于對數(shù)據(jù)的過于擬合而使得其對新信息的預(yù)測能力大大地 降低。因此，有許多工作集中在尋求有效的約簡算法和對經(jīng)典粗糙集理論的擴(kuò)展 上。 粗糙集目前的研究得到了很大的發(fā)展，主要方向如下： 1 獠糙集的數(shù)學(xué)性質(zhì)。主要討論粗糙集代數(shù)和撼撲結(jié)構(gòu)以及粗糙集瓣收斂性 斛等瀚題。 2 粗糙集模型的擴(kuò)展。p a w l a k 粗糙集模型的推廣一奩是粳糙集理論研究的主 流方向，目前主要莉蹲種方法( 1 ) 構(gòu)造性方法；( 2 ) 代數(shù)性( 公理化) 方法。 ( 1 ) 構(gòu)造性方法是對原始p a w l a k 粗糙集模型的般推廣，其主要思路怒從給 定的近似空間出發(fā)去研究粗糙集幫近似算子。它楚以論域上的二元關(guān)系或幫爾予 代數(shù)作為基本要素的，然后導(dǎo)出粗糙集代數(shù)系統(tǒng)( 2 “，氣u ，n a p r ，緲) 。這種方法所 研究的聞題往往來源予實(shí)際，所建立的模型有很強(qiáng)的應(yīng)焉價值，其主要缺點(diǎn)是不 易深刻了解近簌算予熬代數(shù)結(jié)梅。 在經(jīng)典粗糙集模受中有三個最基本的要素：一個論域移，移上的一個二元等 價關(guān)系r ( 它們構(gòu)成了近似空間) ，一個被近似描述的( 經(jīng)典) 集合爿，也稱為專家 概念。由此，推廣的形式也有三個方向，即從論域方向、從關(guān)系方向( 包括近似 空耀) 和從集合方嘲。 l 、 從論域方向推廣的鼷黼主要是雙論域【3 0 的情形，這時的二元關(guān)系就變成了 兩個論域笛卡歹l 乘積的個子集。對于將論域推廣到多個的情形來研究粗糙集理 論豹文獻(xiàn)很少，這種討論也將隨著維數(shù)翡增熱變?nèi)煸綇?fù)雜。 2 關(guān)系方向的推廣：一種是將論域上酶二元等價關(guān)系推廣為任意的二元關(guān)系 得到一般關(guān)系下的粗糙集模型【2 8 】；另一種是將對象x 所在的等價類看成是搿的個 鄰域，從而推廣導(dǎo)出了籀于領(lǐng)域算予的粗糙集模型【3 1 3 2 】；也有將由關(guān)系導(dǎo)出的劃 分推廣成為一般的布爾代數(shù)的，以此出發(fā)去定義糨糙集和近似算子的；更般的 有將普遴關(guān)系推廣成模糊關(guān)系或模糊劃分f 3 3 3 4 】麗獲彳譬模糊粗糙集模型f 3 5 】。 3 ) 集合和近似空聞簸推廣：這一類的推廣是與其他處理不確定，不精確或模 糊的知識( 概率論、模贛數(shù)學(xué)、信息論、證據(jù)理論等) 結(jié)合起來進(jìn)行研究的。 當(dāng)知識疼中的知識楚國于隨楓原因或經(jīng)統(tǒng)計得到的，即知識庫中的知識綴可 能是不確定的，很多學(xué)者提出了統(tǒng)計( 或概率) 粗糙集模型，變精度粗糙集模型實(shí) 際上也可以歸入這類模型，尋求具有最小風(fēng)險的熙葉斯決策問題也可以轉(zhuǎn)化為這 類模型。這一類模型在數(shù)據(jù)分析的增量式機(jī)器學(xué)習(xí)中有熏要應(yīng)用。目前覓到的此 7 電予辯技大學(xué)聯(lián)：學(xué)霞論文 類模型中，近似空間中二元關(guān)系大都是等價關(guān)系，對于非等價關(guān)系給出的情形的 文章尚未見到。 當(dāng)知識庫中的知識模塊都是清晰概念，而被描述的概念是一個模糊概念，人 們建立了粗糙模糊集模型來解決此類問題的近似推理。當(dāng)知識庫中的知識模塊也 是模糊的，有些學(xué)者就提出了模糊粗糙集模型并作了推廣3 5 ，3 6 翮。對于知識庫中的 知識模塊既是模糊知識又是隨機(jī)得到的至今討論甚少，但在實(shí)際問題中肯定是存 在的，因此也是值得繼續(xù)研究的。 隨著這幾年對粗糙集理論的進(jìn)一步研究，經(jīng)典的粗糙近似算子已經(jīng)被大量的 推廣，主要表現(xiàn)在和其他不確定性概念或者其縫知識發(fā)現(xiàn)酶方法的結(jié)合上，特別 是與模糊系統(tǒng)的聯(lián)系仍然是研究的熱點(diǎn)，這方面的成果也是最多的；而另一方面 對于不完備信息系統(tǒng)上粗糙集模型的研究也主要是對容差關(guān)系和相似關(guān)系的討 論；再者對被近似概念和集合的一般化、廣泛化也是研究的主流，所有這方面的 工作都是為了使粗糙集理論更加深入到實(shí)際問題的解決中，或者是在更多領(lǐng)域中 尋找與粗集理論相結(jié)合的交叉點(diǎn)，以此拓展粗糙集的應(yīng)用。 ( 2 ) 代數(shù)方法也稱為公理化方法有時也稱為算子方法，這種方法不是以二元關(guān) 系為基本要素，它的基本要素是一對滿足菜些公理的一元( 集合) 近似算子 厶h ：2 專2 u ，即粗糙代數(shù)系統(tǒng)( 2 u ，u ，n ，l ，h ) 中近似算子是事先給定的。這種 方法研究的明顯優(yōu)點(diǎn)是能夠深刻地了解近似算子的代數(shù)結(jié)構(gòu)，其缺點(diǎn)是應(yīng)用性不 夠強(qiáng)。 近似算子的某些公理能保證有一些特殊類型的二元關(guān)系的存在，使這些能夠 通過構(gòu)造性方法產(chǎn)生給定的算子；反過來，由二元關(guān)系通過構(gòu)造性方法導(dǎo)出的近 似算子定滿足某些公理，傻這些公理通過代數(shù)方法產(chǎn)生給定的二元關(guān)系。 公理化方法的研究一開始只局限于p a w l a k 粗糙代數(shù)系統(tǒng)，即公理與二元等價 關(guān)系相對應(yīng)情形，壓逐漸發(fā)展到般關(guān)系下的粗糙集系統(tǒng)。至今為止，關(guān)于公理 化方法的粗糙集理論研究大多局限于經(jīng)典集情形，對于模糊集情形雖有討論，但 比較少。 3 。粗糙邏輯。在粗糙集的基礎(chǔ)上建立的r o u g h 邏輯。 4 有效算法的研究。包括決策規(guī)則的提取算法，屬性約簡算法，粗糙集基本 并行算法，以及與粗糙集有關(guān)的神經(jīng)網(wǎng)絡(luò)和遺傳算法等。 5 多方面的融合。主要有：粗糙集與神經(jīng)網(wǎng)絡(luò)的結(jié)合 3 8 - 4 0 1 ，出現(xiàn)的粗糙神經(jīng) 網(wǎng)絡(luò)，加快神經(jīng)網(wǎng)絡(luò)的速度；與遺傳算法的結(jié)合來處理大數(shù)據(jù)集。 8 第一鼗緒論 1 6 本文的組織結(jié)構(gòu) 本文主要研究耱糙集理論模型以及粗糙集理論中的不確定性| 、蘧題，在西前已 有的研究成果上繼續(xù)推廣應(yīng)用粗糙集理論模型。一是基予p a w l a k 提出的經(jīng)典粗糙 集模型的理論來源，將此類特殊的模型從論域、關(guān)系、集合三個方向進(jìn)行一般的 推廣和拓展；二是根據(jù)粗糙集理論在現(xiàn)目前的廣闊應(yīng)用，結(jié)合其他一些領(lǐng)域的不 確定性理論和經(jīng)驗( 概念格理論，模糊集理論等不確定性理論) 構(gòu)造某些特殊的粗 糙集模型或把褪糙集理論的一些思想應(yīng)用到其絕的知識系統(tǒng)中，不斷豐富粗糙集 的理論體系，使其在更多行業(yè)中發(fā)揮它自身的優(yōu)勢。其文章的組織如下： 第一章：緒論。闡述了本文麓選題背景，介紹了粗糙集的基本概念及其特點(diǎn) 和應(yīng)用領(lǐng)域，國內(nèi)外粗糙集的研究狀況，并對本文的工作進(jìn)行介紹。 第二章：粗糙集與概念格理論。介紹了概念格理論，就概念格與粗糙集進(jìn)行 比較和結(jié)合，引入了基于粗糙集的概念格模型，并將概念格在模糊意義下展開，得 到用不同蘊(yùn)涵算子表達(dá)的模糊概念。 第三章：基于交精度粗糙集的概念格。針對一定的錯誤分辨率，結(jié)合變精度 粗糙集模型，建立了基于變精度粗糙集的概念格模型，對其相關(guān)性質(zhì)進(jìn)行了討論， 對糨糙集模型進(jìn)行了補(bǔ)充。 第四章：模糊粗糙集。對粗糙集和模糊集進(jìn)行了比較，并結(jié)合模糊集理論， 引入了模糊糨糙集模型，_ 并對英研究進(jìn)嶷進(jìn)行介紹。 第五章：基于一新的模糊信息系統(tǒng)的模糊r 粗糙集。本文在已有的模糊粗糙 集模型上加以改進(jìn)，引進(jìn)模糊r 相似關(guān)系，并在此關(guān)系下構(gòu)建新的模糊信息系統(tǒng)， 得到了基于新的模糊信息系統(tǒng)的模糊? 一粗糙集，并對相關(guān)性質(zhì)和上下近似算子之 間的關(guān)系進(jìn)行了討論。 第六章：總結(jié)。對全文的工作進(jìn)行了總結(jié)。 9 電予科技大學(xué)碩：b 學(xué)位論文 第二章粗糙集與概念格理論 粗糙集理論是由p a w l a kz 。于1 9 8 2 年提出來的，其基本思想是通過案例的分 類歸納出概念和規(guī)則。它從不可分辨關(guān)系對論域的戈0 分出發(fā)，用一對上下近似集 對不能用已有概念表述的新概念給出某種近似表示，并對信息系統(tǒng)中所隱含的知 識以決策規(guī)則進(jìn)行表示。粗糙集是一種處理模糊性和不確定性的新型數(shù)學(xué)工具。 與粗糙集理論同時產(chǎn)生的是概念格理論。概念格，又稱為g a l o i s 格，是w i l l e 裝于1 9 8 2 年提出的。概念格同樣是建立在分類基磊窶上，但是它比分類有更大的概 括性，它往往在歸納幾個分類的基礎(chǔ)上產(chǎn)生一個概念概念格是根據(jù)二元關(guān)系提 出的一種概念層次結(jié)構(gòu)【4 l 】，是數(shù)據(jù)分?jǐn)睾退覄t提取的一種有效工具。從數(shù)據(jù)集中 生成概念格的過程實(shí)際上是一種概念聚類過程，它的每一個節(jié)點(diǎn)稱為一個概念， 概念的外延表示為屬于這個概念的所有對象的集合，面內(nèi)涵表示為所有對象所共 有的屬性的集合。概念格本質(zhì)上是通過對象和屬性的二元關(guān)系達(dá)到兩者的某種對 應(yīng)，體現(xiàn)了概念之間的泛化和特化關(guān)系。因此，概念格與粗糙集理論一樣，同樣 成為研究決策規(guī)則的一種重要方法。 由于概念格與粗糙集理論都是建立在分類基礎(chǔ)上的，因此兩種理論雖然不同， 僵又有共性。利用粗糙集理論與方法研究概念格理論，剩用概念揍理論與方法研 究粗糙集理論，相互借鑒、相互促進(jìn)，推動了粗糙集理論與概念格理論的發(fā)展， 同時也為不確定性規(guī)則獲取與數(shù)據(jù)提取提供了有效的工具。 本章首先介紹了概念格的產(chǎn)生背景以及發(fā)展歷史，并對這一有效的數(shù)學(xué)工具 的實(shí)際應(yīng)用給出了介紹，回憶了概念格理論中的基本概念，給出了基于粗糙集理 論的概念格構(gòu)造方法，并給出了糨糙集與概念格之閹的關(guān)系。 2 1 概念格理論的應(yīng)用 屬粗糙集理論一樣，概念搔作為一種具有極大潛力和有效的知識發(fā)現(xiàn)工輿， 備受人工智能工作者的廣泛關(guān)注，并廣泛應(yīng)用于機(jī)器學(xué)習(xí)、模式識別、專家系統(tǒng)、 計算機(jī)颼絡(luò)、數(shù)據(jù)分析、決策分析、數(shù)據(jù)挖握等領(lǐng)域。 1 0 第二章秘糙蕊與概念掐蠼論 目前，涉及概念格理論的主要成果有： ( 1 ) 作為閣為數(shù)據(jù)分櫥和數(shù)據(jù)處理的互補(bǔ)的有效數(shù)學(xué)工具概念格理論和粗糙集 理論，許多學(xué)者嘗試結(jié)合這兩種理論，構(gòu)造了基于粗糙集理論的概念格，提出了 屬性概念和對象概念，并嘗試著用粗糙集理論的約筒的方法來對概念格中的屬性 和對象進(jìn)行約簡。并有許多學(xué)者把模糊集、粗糙集和概念格三者結(jié)合，構(gòu)造新型 的分類模型。 ( 2 ) 一系列概念格生成算法：目前已有酶概念格的生成算法大致分為兩類：一 類是批處理算法，其中，o s h z m 算法【4 2 】是首先構(gòu)造格的最上層節(jié)點(diǎn)，再逐漸往下。 于此相反，c h e i n 算法是首先構(gòu)造底部的節(jié)點(diǎn)，褥向上擴(kuò)震。n o u f i n e 算法1 4 3 英i j 是 采用枚舉的方法，按照一定順序枚舉格的所有節(jié)點(diǎn)，再生成h a s s e 圖；另一種則是 增量算法，這類算法的思想是大同小異的，如g o d i n 算法f 刪，動態(tài)的生成概念格， 謝志鵬、劉宗田【4 5 】提出了采用樹狀結(jié)構(gòu)對概念格節(jié)點(diǎn)集進(jìn)行組織的快速漸進(jìn)式構(gòu) 造算法。 ( 3 ) 概念格在許多領(lǐng)域得到成功的應(yīng)用：如數(shù)字圖書館，c n e u s s ，r 。e k e n t1 4 6 1 事業(yè)概念格進(jìn)行i n t e r n e t 上穩(wěn)當(dāng)元信息分類和分析，他們討論的兩個著名的資源發(fā) 現(xiàn)服務(wù)w h o i s + + 和h a r v e s t 都可以包含在基于概念的更為一般和具有良姆結(jié) 構(gòu)的方法中。r c o l e ，p w e k l u n d 4 7 】將概念格方法應(yīng)用于分析和可視化具有1 9 6 2 個屬性和4 0 0 0 個廚房摘要的醫(yī)藥數(shù)據(jù)瘁。p w e k l u n d ，囊m a r t i n 4 8 】展示了概念格 層次進(jìn)行w e b 穩(wěn)當(dāng)索引和導(dǎo)航的能力。另外，概念格還可以應(yīng)用于詞典的調(diào)整、 軟件工程、知識發(fā)現(xiàn)等領(lǐng)域，麗且已取得了良好的經(jīng)濟(jì)效益和社會效益。 2 2 概念格理論的基本概念 定義2 1 4 9 稱( u ，a ，j ) 為一個形式背景，其中u = 誓，如，毛) 為對象集，每 個薯o ，z ) 稱為一個對象；a = ( 搿，t 2 ，) 為屬性集，每一個口，( 坍) 稱為一個屬 性，歹為移和么之間的二元關(guān)系，i 曼u 圓a 。若瓴露) i ，則稱x 具有屬性a 。若 阮a ) 正j ，則稱x 不具有屬性a 。 對于形式背景( u ，a ，) ，在對象集x u 和屬性集艿悠a 分別定義運(yùn)算【2 6 】： 電予科技大學(xué)碩：b 學(xué)位論文 x 。= a l a 專a ，v x e x ，( x ，控) ? 2 一1 ) b + = x l x e u ，訛b ，i x ，a ) e i ) ( 2 - 2 ) x 表示并中所有對象共同具有的屬性集合，薩表示具有曰中所有屬性的對象集 合。魄穢，記 x ；4 為f ；v aca ，記 露；+ 為療，魄黷f ，f ，a 至iv ae a ， a 多，a u ，稱形式背景緲，以，) 是正則的。 定義2 2 剛設(shè)( u ，么，) 是形式背景，如果一個二元組( x ，b ) ，滿足x = b ，且 x = 礦，熒| j 稱( 菇，客) 是一個概念( c o n c e p t ) 。 其中，x 成為概念的外延，用e x ( x ，b ) 表示，曰稱為概念的內(nèi)涵，用i n ( x ，b ) 表示。用l ( u ，a ，) 表示形式背景( u ，么，) 的全體概念，在l ( u ，a ，) 中兩個元素： 冀= ( 墨，罵) 和避= ( 鼉，島) ，瓶定置 也是概念，從i 7 i il ( u ，a ，i ) 是完備格。 2 3 基于粗糙集的概念格 ( 2 - 3 ) 0 q 租糙集懸研究劃分的，而概念格是在劃分的基礎(chǔ)上產(chǎn)生的，因此，可以模仿 粗糙集的方法構(gòu)造“上近似格鞠“下近似格”，以程糙集方法研究概念格的梅造。 設(shè)緲，a ，i ) 為形式背景，對予x u ，a a ，記 = 露么峙鑫) z ， 露= x 穢| o ，a ) g i 。 顯然行x + 等價于工蹦4 。由于概念格是雁則的，則 x + 卜毯u ) 構(gòu)成4 的覆蓋，同理 爨+ 扭么 構(gòu)成u 的覆蓋。對予形式背景影，疊? ) ，晨“霜表示下近似，用“穢 表示上近似，對予爿蠡及b 囊a 有 x a = 扛么p 簸x ( 2 - 5 ) x 。= 擯么江4 八x 囝；( 2 - 6 ) 釅= 扣i 么f 器；( 2 - 7 ) b 。= 扛彳f n 霹囝 ( 2 - 8 ) 定理2 3 2 7 運(yùn)算據(jù)1 3 弦與搿捧有以下性質(zhì)： ( 1 ) 當(dāng)置蔓，則x ? 必：及x ；o 墨； ( 2 ) 當(dāng)罵s 盈，則b 。o b ：o 及b ；o 簍群； 1 3 一一 電予科技大學(xué)碩：i ：學(xué)位論文 _ 二= 二- 一一一 3 ) x 酌量x x 鈀，b q ?； cb 婦； ( 4 ) x 鈾o = x 。，x 咖= x 。， b o ”= b 。，b 螂一b 垂； ( 5 ) 伐n 五廣= 冒八霹，瞄u 置戶= 霹u 霹， ( 墨n 島) a = 群廠、劈，( 島u 島) 。囂晟ou 霹 定義2 3 設(shè)( ，a ，) 為形式背景，對于x u 及艿互彳，若有x ：b o b ：x a ， 稱，囂) 為對象概念；若x = b o ，b = x 。，稱蓋，功為屬性概念。 定理2 4 【2 7 】設(shè)( u ，a ，j