博士論文不完備信息系統(tǒng)中租糙集理論研究 摘要 粗糙集理論是由波蘭學者p a w l a k 提出的一種新型數(shù)據(jù)分析工具，對于研究如何 應用數(shù)學工具模仿人腦的思維活動和認知過程具有重要的作用。由于經(jīng)典粗糙集理論 是建立在不可分辨關(guān)系( 等價關(guān)系) 上的，要求過于嚴格，因而研究粗糙集的各種擴 展模型對于粗糙集理論的發(fā)展具有極其重要的意義。本文主要針對不完備信息系統(tǒng)中 的各種擴展粗糙集模型進行了系統(tǒng)而又深入的研究。 在具有缺席型未知屬性值的不完備信息系統(tǒng)中，提出了差異關(guān)系粗糙集模型以獲 取否定決策規(guī)則。在一般情形中的不完備信息系統(tǒng)中，提出了基于可變精度分類關(guān)系 的粗糙集模型，證明了基于容差關(guān)系、非對稱相似關(guān)系的粗糙集模型是可變精度分類 關(guān)系粗糙集模型的特例。 研究了同時具有遺漏型和缺席型未知屬性值的廣義不完備信息系統(tǒng)，討論了原有 特征關(guān)系的不足之處，進而提出了3 種新的特征關(guān)系，并對基于這些特征關(guān)系的粗糙 集模型進行了對比分析。 在具有遺漏型未知屬性值的不完備信息系統(tǒng)中，考慮屬性值的順序特性，進而提 出了t 和、l 描述子的概念，討論了t 和【描述子約簡的分辨矩陣方法，根據(jù)t 和【描述子， 研究了如何從不完備決策系統(tǒng)中獲取最優(yōu)可信規(guī)則，與原有基于擴展優(yōu)勢關(guān)系粗糙集 模型的方法相比，使用t 和j ，描述子的方法，不僅可以消除決策規(guī)則中的未知屬性值， 而且可以獲得包含信息更為豐富的決策規(guī)則。 在具有缺席型未知屬性值的不完備信息系統(tǒng)中，考慮屬性值的順序特性，提出了 相似優(yōu)勢關(guān)系的概念，根據(jù)基于相似優(yōu)勢關(guān)系的粗糙集模型，提出了4 種近似分布約 簡的概念，并對這些約簡之間的關(guān)系進行了討論。將基于相似優(yōu)勢關(guān)系的粗糙集模型 引入不完備模糊決策系統(tǒng)中，對其中的知識約簡與知識獲取問題進行了研究。 在區(qū)間值信息系統(tǒng)中，首先根據(jù)已有的優(yōu)勢關(guān)系提出了6 種不同形式的相對約簡 以獲取最優(yōu)決策規(guī)則；接著考慮對象與對象之間的優(yōu)勢程度，定義了區(qū)間值決策系統(tǒng) 中的模糊粗糙集模型以進行知識獲取。 關(guān)鍵詞：不完備信息系統(tǒng)，粗糙集，優(yōu)勢關(guān)系，描述子，知識約簡，決策規(guī)則 a b s t r a c t r o u g hs e tt h e o r yi s an e wd a t aa n a l y s i st o o l ，w h i c hw a sf i r s tp r o p o s e db yp o l a n d r e s e a r c h e rp a w l a k s u c hat h e o r yp l a y saf u n d a m e n t a lr o l e i nt h ei m i t a t i n go fh u m a n b r a i n st h i n k i n ga n dc o g n i t i o n s i n c et h et r a d i t i o n a lr o u g hs e tm o d e li sc o n s t r u c t e do nt h e b a s i so fas t r i c ti n d i s c e m i b i l i t yr e l a t i o n ( e q u i v a l e n c er e l a t i o n ) ，r e s e a c ho nh o wt oe x p a n d t h er o u g hs e tm o d e li sv e r yi m p o r t a n tf o rt h ed e v e l o p m e n to fr o u g hs e tt h e o r y i nt h i s t h e s i sf o r t h ed o c t o r a t e ，s e v e r a le x p a n d e dr o u g hs e tm o d e l sa red e e p l yi n v e s t i g a t e di nt h e i n c o m p l e t ei n f o r m a t i o ns y s t e m s i nt h ei n c o m p l e t ei n f o r m a f i o ns y s t e mi nw h i c ha l lu n k n o w nv a l u e sa l ec o n s i d e r e d 硒 “l(fā) o s t ”，an e wr o u g hs e tm o d e li sp r o p o s e db a s e do nt h ec o n c e p to f d i f f e r e n c er e l a t i o n ，f r o m w h i c hw ec a ng e n e r a t ea l ln e g a t i v er u l e sf r o mt h ei n c o m p l e t ed e c i s i o ns y s t e m i ng e n e r a l i n c o m p l e t ei n f o r m a t i o ns y s t e m ，t h ev a r i a b l ep r e c i s i o nc l a s s i f i c a t i o nb a s e dr o u g hs e tm o d e l i sp r o p o s e d i ti sp r o v e dt h a tt h er o u g hs e tm o d e l sb a s e do nt o l e r a n c er e l a t i o n ，s i m i l a r i t y r e l a t i o na r es p e c i a lf o r m so ft h ev a r i a b l ep r e c i s i o nc l a s s i f i c a t i o nr o u g hs e t i nt h ei n c o m p l e t ei n f o r m a t i o ns y s t e mi nw h i c hu n k n o w na t t r i b u t e s v a l u e sa r e c o n s i d e r e da sn o to n l y “i o s t b u ta l s o “d on o tc a r ec o n d i f i o n ，t h r e en e wc h a r a c t e r i s t i c r e l a t i o n sa r ep r o p o s e dt om a k eu pf o rt h el i m i t a t i o n so ft h eo r i g i n a lc h a r a c t e r i s t i cr e l a t i o n t h er e l a t i o n s h i p sb e t w e e nt h e s ec h a r a c t e r i s t i cr e l a t i o n sb a s e dr o u g hs e tm o d e l sa r ea l s o i n v e s t i g a t e d i nt h ei n c o m p l e t ei n f o r m a t i o ns y s t e mi nw h i c ha l lu n k n o w nv a l u e sa r e d on o tc a r e c o n d i t i o n ”，t h ec o n c e p to fta n d 【d e s c r i p t o r s a r e p r o p o s e db yc o n s i d e r i n gt h e p r e f e r e n c e - o r d e r e dd o m a i n so ft h ea t t r i b u t e s t h ed i s c e r n i b i l i t ym a t r i xa p p r o a c ht oo b t a i n t h eta n dj ，d e s c r i p t o r s r e d u c t i o n sa r et h e ns t u d i e d w i t hr e s p e c tt ot h ep r o p o s e d d e s c r i p t o r s ，t h ep r a c t i c a la p p r o a c ht og e n e r a t ea l lo p t i m a lc e r t a i nr u l e sf r o m t h ei n c o m p l e t e d e c i s i o ns y s t e mi s i n v e s t i g a t e d b yc o m p a r i n gw i t ht h ee x p a n d i n gd o m i n a n c er e l a t i o n b a s e dr o u g hs e tm o d e l ，w ec a l lo b t a i nt h ed e c i s i o nr u l e s ，w h i c hi n c l u d i n gm o r eu s e f u l i n f o r m a t i o nf r o mt h ev i e w p o i n to fta n d 上d e s c r i p t o r s i nt h ei n c o m p l e t ei n f o r m a t i o ns y s t e mi nw h i c ha l lu n k n o w nv a l u e sa l e “l(fā) o s t ，t h e c o n c e p to fs i m i l a r i t yd o m i n a n c er e l a t i o ni sp r o p o s e db yc o n s i d e r i n gt h ep r e f e r e n c e o r d e r e d d o m a i n so ft h ea t t r i b u t e s b yt h es i m i l a r i t yd o m i n a n c e b a s e dr o u g hs e tm o d e l s ，n o to n l y f o u rt y p e so fa p p r o x i m a t ed i s t r i b u t i o nr e d u c t sa r ep r o p o s e db u ta l s ot h er e l a t i o n s h i p s b e t w e e nt h e s er e d u c t sa r ed i s c u s s e d m o r e o v e r t h es i m i l a r i t yd o m i n a n c e b a s e dr o u g hs e t i i i m o d e li si n 仃o d u c e di n t ot h ei n c o m p l e t ef u z z yd e c i s i o ns y s t e mf o rk n o w l e d g er e d u c t i o n a n dk n o w l e d g ea c q u i s i t i o n i l lt 1 1 ei n t e r v a j v a l u e di n f o r m a t i o ns y s t e m ，s i xt y p e so fr e l a t i v er e d u c t sa l ep r o p o s e d ， 疳o mw 1 1 i c ho n ec a no b t a i nt h eo p t i m a ld e c i s i o n r u l e ss u p p o r t e db yas p e c i a lo b j e c t m o r e o v e r ，b yc o n s i d e r i n g t h ed o m i n a n c ed e g r e eb e t w e e no b j e c t s ，t h ef u z z yr o u g h a p p r o a c hi se m p l o y e df o rk n o w l e d g ea c q u i s i t i o ni n t h ei n t e r v a l 。v a l u e dd e c i s i o ns y s t e m k e yw o r d ：i n c o m p l e t ei n f o r m a t i o ns y s t e m ，r o u g hs e t ，d o m i n a n c er e l a t i o n , d e s c r i p t o r , k n o w l e d g er e d u c t i o n ，d e c i s i o nr u l e i v 聲明 本學位論文是我在導師的指導下取得的研究成果，盡我所知，在 本學位論文中，除了加以標注和致謝的部分外，不包含其他人已經(jīng)發(fā) 表或公布過的研究成果，也不包含我為獲得任何教育機構(gòu)的學位或?qū)W 歷而使用過的材料。與我一同工作的同事對本學位論文做出的貢獻均 已在論文中作了明確的說明。 研究生簽名：盤口逡 2 夕一年，j 弓be t 學位論文使用授權(quán)聲明 南京理工大學有權(quán)保存本學位論文的電子和紙質(zhì)文檔，可以借閱 或上網(wǎng)公布本學位論文的部分或全部內(nèi)容，可以向有關(guān)部門或機構(gòu)送 交并授權(quán)其保存、借閱或上網(wǎng)公布本學位論文的部分或全部內(nèi)容。對 于保密論文，按保密的有關(guān)規(guī)定和程序處理。 研究生簽名：盔復：! 墮z 口，口年月弘日 博士論文不完備信息系統(tǒng)中粗糙集理論研究 1 緒論 1 1粗糙集的歷史與現(xiàn)狀 1 1 1粗糙集理論歷史發(fā)展過程 經(jīng)典集合論對應于經(jīng)典邏輯，因而適用于描述確定性問題。值得注意的是，在自 然科學、社會科學和工程技術(shù)等眾多領(lǐng)域中，不確定、不精確信息是廣泛存在的。不 確定性可以理解為在缺少足夠信息的情況下做出判斷，是智能問題的本質(zhì)特征。不確 定性實際上起源于量子力學，例如海森堡不確定原理：一般地，一個粒子的位置和它 的動量不可被同時確定，換句話說，只有當位置確定的時候，粒子的動量才能被度量， 反之亦然。 多年來，眾多研究人員一直致力于尋找科學地處理不確定問題的有效方法。例如， 模糊集【l 】與概率論 2 1 是處理不確定性問題的兩種代表性方法，然而這兩種方法有時需 要一些關(guān)于數(shù)據(jù)的附加信息或先驗知識，如模糊隸屬度，概率統(tǒng)計分布等，這些信息 有時并不容易得到。 粗糙集理論【3 。8 】( r o u g hs e tt h e o r y , 簡稱r s t ) 是近年來計算智能領(lǐng)域出現(xiàn)的一個 新的分支，具有堅實的數(shù)學基礎(chǔ)，可用于處理不確定性問題。粗糙集理論對于研究如 何應用數(shù)學工具模仿人腦的思維活動和認知過程具有重要的作用，它最為突出的特點 是無需提供除問題所需處理的數(shù)據(jù)集合之外的任何先驗信息。作為數(shù)據(jù)處理工具，粗 糙集與模糊集理論最主要的區(qū)別是【9 】：粗糙集以不可分辨關(guān)系為基礎(chǔ)，側(cè)重分類；而 模糊集則基于元素對集合隸屬程度的不同，強調(diào)集合本身的含混性。從粗糙集的觀點 來看，集合不能被清晰定義的原因是缺乏足夠的領(lǐng)域知識，但可以用一對清晰集合逼 近。 粗糙集理論是在八十年代初由波蘭學者z d z i s t a wp a w l a k 首先提出的，由于最初的 研究成果是用波蘭文發(fā)表的，因此，粗糙集理論當時并未引起國際學術(shù)界的重視，研 究地域僅局限在東歐各國。八十年代末，由于粗糙集理論在人工智能領(lǐng)域得到了成功 的應用，特別是1 9 9 1 年p a w l a k 教授的第一本關(guān)于粗糙集的專著【3 】和1 9 9 2 年s t o w i f i s k i 主 編的關(guān)于粗糙集應用與相關(guān)方法比較研究的論文集【1 0 1 的出版，粗集理論逐漸引起了世 界各國學者的關(guān)注。 自1 9 9 2 年第一屆關(guān)于粗糙集方法的國際學術(shù)會議在波蘭召開以來，每年都有關(guān) 于粗糙集理論及其應用的國際學術(shù)會議召開。2 0 0 5 年，國際上正式成立了粗糙集研 究學會一i n t e m a t i o n a lr o u g hs e ts o c i e t y , 并創(chuàng)立了粗糙集理論的國際期刊 一t r a n s a c t i o n so nr o u g hs e t ，所有這些工作都加速了粗糙集理論在國際學術(shù)舞臺上的 l 緒論博士論文 交流與發(fā)展，為進一步推動了粗糙集理論的深入研究起到了決定性的作用。 目前，我國學者在粗糙集擴展模型，公理化體系，粗糙邏輯，粗糙數(shù)學等方面的 研究取得了較大成功，在粗糙集理論某些方面的研究水平已達到或接近國際先進水 平，可以說我國學者正在成為粗糙集理論研究的主導力量。2 0 0 3 年1 1 月，在中國廣 州舉行的全國人工智能學會的年會上，中國粗糙集與軟計算專委會正式成立。自2 0 0 1 年在重慶郵電大學成功召開“第一屆中國r o u g h 集與軟計算學術(shù)研討會”以來，每 年都召開一次中國粗糙集與軟計算學術(shù)會議，每年的學術(shù)會議在規(guī)模和質(zhì)量上均呈良 好的增長趨勢，“第九屆中國r o u g h 集與軟計算學術(shù)研討會”于2 0 0 9 年8 月在河北 石家莊召開。所有這些學術(shù)活動都為我國學者在粗糙集理論與應用方面的研究提供了 良好的學術(shù)交流平臺。 1 1 2粗糙集理論研究現(xiàn)狀 粗糙集理論自提出以來，其理論模型得到不斷完善和發(fā)展，并滲透到很多學科， 成為研究數(shù)據(jù)挖掘、知識約簡和粒計算的理論基礎(chǔ)，同時，粗糙集理論自身也已成為 完整、獨立的科學領(lǐng)域。目前國內(nèi)外對于粗糙集理論的研究主要集中在以下幾個方面： 1 ) 關(guān)于粗糙集模型的推廣研究，這一直是粗糙集理論的熱點研究問題，對于將粗糙 集理論進一步推向?qū)嵱糜兄鴺O其重要的意義； 2 ) 關(guān)于粗糙集理論數(shù)學性質(zhì)方面的研究，主要集中在粗糙集的代數(shù)結(jié)構(gòu)和拓撲結(jié)構(gòu) 上，涌現(xiàn)了一大批新的概念，如粗糙代數(shù) 1 1 , 1 2 ，粗糙群【1 3 1 ，粗糙環(huán)【1 4 1 ，粗糙?！?5 1 ， 粗糙理想 1 6 , 17 】等等； 3 ) 關(guān)于與其他處理不確定性問題理論的關(guān)系研究，如粗糙集理論與概率統(tǒng)計【1 8 , 1 9 、 模糊數(shù)學【2 0 1 、證據(jù)理論【2 1 1 等理論的相互滲透與互補； 4 ) 關(guān)于粗糙集理論的算法研究，尋找一個信息系統(tǒng)的所有約簡或最小約簡是一個 n p 難問題，因而尋求高效的可行的約簡算法仍然是粗糙集理論中尚未完全解決 的問題。 不確定性是粗糙集理論的關(guān)鍵詞，它涉及集合論定義中的許多實質(zhì)性內(nèi)容。集合 的近似定義是現(xiàn)代數(shù)學中的重要概念之一，而與布爾邏輯非常相關(guān)的經(jīng)典集合論又是 數(shù)字計算機運算的核心。眾所周知，許多實踐問題不能滿足現(xiàn)存計算機的求解條件， 特別是機器學習、模式識別以及某些控制問題等，這種困難常常使得不能建立描述個 體的算法。而粗糙集理論及其擴充對于建立此類個體的近似描述，提供了一種精確的 數(shù)學技術(shù)。粗糙集方法對于處理這類問題提供了一種通用的由精確數(shù)學語言支持的哲 學框架。 2 博士論文不完備信息系統(tǒng)中粗糙集理論研究 1 2粗糙集理論的數(shù)學基礎(chǔ) p a w l a k 所提出的粗糙集理論是建立在分類機制的基礎(chǔ)上，它把知識看作是一種對 現(xiàn)實的或抽象的對象進行分類的能力，而分類則是推理、學習與決策中的關(guān)鍵問題【9 1 。 這里的“對象 是指我們所能言及的任何事物，比如實物、狀態(tài)、抽象概念、過程和 時刻等等。粗糙集模型的最本質(zhì)特征是根據(jù)已知的知識，對未知的知識( 不精確或不 確定知識) 進行近似刻畫。粗糙集理論與其他處理不確定和不精確問題理論相比，無 需提供問題所需處理的數(shù)據(jù)集合之外的任何先驗知識，所以對問題的不確定性描述或 處理顯得較為客觀。由于粗糙集理論未能包含處理不精確或不確定原始數(shù)據(jù)的機制， 因而這個理論與概率論( 需要知道數(shù)據(jù)的概率分布) 、模糊數(shù)學( 需要給定隸屬度函 數(shù)) 和證據(jù)理論( 需要信度函數(shù)) 等其他處理不精確或不確定問題的理論具有很強的 互補性。 要了解什么是粗糙集理論，首先定義如下概念： 1 ) 令u a 為一論域，r 為吐的一族等價關(guān)系的集合，則稱k b = 為一個知 識基； 2 ) 對于v r e r ，r 表示u 上的一個二元等價關(guān)系( 滿足自反性、對稱性和傳遞性， p a w l a k 稱其為不可分辨關(guān)系) ，對于帆，y 配若o ，力r ，則稱x 與y 之間是不可分 辨的； 3 ) 對于v r e r ，k s = 稱為一個知識結(jié)構(gòu)或近似空間。 由離散數(shù)學的相關(guān)知識可以證明，驢上的一個劃分與吐的一個二元等價關(guān)系之 間一一對應，若令u r 表示由二元等價關(guān)系尺所產(chǎn)生的論域劃分，則u j 6 c 中的元素稱 為欠一基本集或原子集。在近似空間k s 中，對于v x c _ 配若艉一些r 基本集的并集， 則稱艉r 一可定義的，否則稱為是尺一不可定義的。 1 2 i粗糙近似集 為了近似地定義粗糙集，p a w l a k 建立了的下、上近似集的概念。 定義1 1 【3 1 設(shè)u 為一論域，r r ，對于v 逛配堪于等價關(guān)系r 的下近似集合墨 ( l o w e r a p p r o x i m a t i o n ) 與上近似集合尺( u p p e r a p p r o x i m a t i o n ) 分別定義如下： 墨2u y eu r ：】，互毋= x eu ：b 】r 田；( 1 1 ) ra f ) 2u y eu r ：y n x # 彩 = x u ：b 】尺n y f 2 j ) ； ( 1 2 ) 其中k 】r = y e u ： ，力r ) 表示u 中所有與x 具有等價關(guān)系尺的對象的集合，即由x 決定 的等價類。 墨實際上是由那些根據(jù)已有知識判斷肯定屬于橢對象所組成的最大集合， 而頁則是由那些根據(jù)已有知識判斷可能屬于x 的對象所組成的最小集合【3 1 。事實 l 緒論博士論文 上，星是包含于彳中的最大r 一可定義集，類似于點集拓撲中的內(nèi)點；r 是包含彳 的最d , r 一可定義集，類似于點集拓撲中的閉包；故有人稱其為p a w l a k 拓撲。因此近 似概念能使我們精確地討論關(guān)于不精確的東西。 確r 一正區(qū)域記y g e o s r ( x ) = 堡，它是如此一些個體元素的集合，這些元素完全 屬訓成員。 橢r 一負區(qū)被記為n e g r ( x ) = 班r ，它是如此一些個體元素的集合，這些元素 肯定不屬于x 確r 一邊界被記為刪k = r 一星，它是那些通過等價關(guān)系r 既不能砒被 分類，也不能在m 被分類的元素的集合。 若邊界域為空，則通過等價關(guān)系尺可以恰當?shù)赜^察集合置反之若引囝，我 們只能通過下、上近似集粗糙地觀察集合x p a w l a k 構(gòu)建的粗糙集具有如定理1 1 所示的性質(zhì)。 定理1 1 1 3 1設(shè)嘞一論域，r r ，五y c u 下、上近似集具有下列性質(zhì)： 墨x c r ；( 1 3 ) 星( o ) = r ( 囝) = 囝；( 1 4 ) 墨( = r ( = 礬( 1 5 ) 墨uy ) 2 星u 墨( y ) ；( 1 6 ) 墨nd = 星n 墨( d ；( 1 7 ) r ud = r0 dur ( d ；( 1 8 ) 尺ny ) r0 0nr ( 功； ( 1 9 ) z 冬】廠墨墨( d ；( 1 1 0 ) x 】廠jr r ( y ) ； ( 1 1 1 ) 星( 、的= 1r ； ( 1 1 2 ) 足( 1 的= 1 星；( 1 1 3 ) 墨( 星) = 星；( 1 1 4 ) 尺( r ) = 尺；( 1 1 5 ) 1 2 2近似精度 由于存在邊界線區(qū)域，即有些元素既不能在論域的某個子集上被分類，也不能在 它的補集上被分類，而這些元素歸于這種邊界線區(qū)域，它的大小是衡量該子集關(guān)于論 域上的等價關(guān)系r 的近似精度，為了更精確地表示這種r o u g h 的思想，p a w l a k 定義了 近似精度3 】的概念；而y a o 【2 2 1 使用m a r c z e w s k i s t e i n h a u s 距離來度量下、上近似之間的 距離，得到了粗糙度的概念，并證明了近似精度與粗糙度之間是互補的。 定義1 2 t 3 】設(shè)嘞一論域，r e r ，對于v a _ c 以x 的近似精度及粗糙度分別記為a r ( x ) 4 博士論文不完備信息系統(tǒng)中粗糙集理論研究 和腳且： 翰2 淵， ( 1 1 6 ) 脅= 1 - a r ( x ) ，( 1 1 7 ) 其中l(wèi)xl 表示集俐基數(shù)。 a r ( x ) 表示我們獲得關(guān)于集繃知識是否完全的程度，很明顯，0 蚴1 成立。當翰= 1 時，有b n r ( x ) = g ，此魄精確可定義的；當a r ( x ) 0 1 ；( 1 2 0 ) b n r ( x ) = x eu ：0 ( x ) l ( 1 2 1 ) 定理1 2 2 3 1 令蚋一論域，r e r ，對t v x e u , 粗糙隸屬度函數(shù)呈( x ) 具有下列性質(zhì)： 1 ) 如果r = ，功：x u ) ，則至( x ) 刪特征函數(shù)； 2 ) 如果 ，y ) e r ，則x r l x j 一_ x r ( 少) ； 3 ) 占一z ( x ) 2 1 羔( x ) ； 4 ) 彬u ，( x ) m a x ( 群( x ) ，( x ) ) ； 5 ) 皇n ，( x ) r a i n ( 婁( x ) ，羅( x ) ) ； 6 ) 如果p = 蜀，噩， 是【，上的一族互不相交的子集，那么就有 嘁( x ) = 蜀。p 彬，( x ) 1 3 信息系統(tǒng)中的基本概念 1 3 1知識表示 知識表示是認知科學和人工智能兩個領(lǐng)域共同存在的問題。在認知科學里，它關(guān) 系到人類如何儲存和處理資料；在人工智能里，其主要目標為儲存知識，使得計算機 程序能夠處理知識，達到人類的智慧。 要理解知識表示，首先要知道什么是知識。在粗糙集理論中，p a w l a k 將把知識看 作是一種對現(xiàn)實的或抽象的對象進行分類的能力。由于經(jīng)典粗糙集理論是建立在不可 分辨關(guān)系，即等價關(guān)系的基礎(chǔ)上的，因而知識就是劃分。 p a w l a k 采用知識表示系統(tǒng)來描述知識。知識表示系統(tǒng)實際上是一個數(shù)據(jù)表，表中 的行代表數(shù)據(jù)對象，而表中的列則表示關(guān)于數(shù)據(jù)對象的信息【3 1 。 形式化地，一個知識表示系統(tǒng)可被定義為二元組s = ，其中 鐮示所有對象的集合，稱為論域； a 驤示所有屬性的集合。 對于v a e a t , 定義映射a ：圪，圪表示屬性a 的值域，耳p a ( x ) e 令k b = 為一個知識基，如何將知識基中的知識表示為知識表示系統(tǒng)? 可 以通過以下兩個步驟來實現(xiàn)【3 】： 1 ) 對于v r e r ，得到論域上的一個劃分u r = 蜀，恐，) ； 2 ) 給定一個屬性a ，其中a e a t , 若令圪= 1 ，2 ，歷) ，則有a ( x ) = f ( 1 f 歷) 當且僅 當x 五 知識表示系統(tǒng)s = 實際上是用來描述知識基k b = e p 的知識的。它 將知識基中的知識轉(zhuǎn)化為計算機可以接受的用于描述知識的數(shù)據(jù)結(jié)構(gòu)。對于知識基中 的每個等價關(guān)系，知識表示系統(tǒng)中必有一個屬性與之對應；而對于每個等價類，在知 6 博士論文不完備信息系統(tǒng)中粗糙集理論研究 識表示系統(tǒng)中必有一個屬性值與之對應【3 1 。 為了簡便起見，如無特殊說明，下文中將知識表示系統(tǒng)s = 以彳p 統(tǒng)一稱為信 息系統(tǒng)。 1 3 2知識依賴 在信息系統(tǒng)s 中，根據(jù)屬性集合a c a t , 可定義個不可分辨關(guān)系【3 】，即二元等價 關(guān)系形如 i n d ( 么) = 0 ，y ) e 釅：v a e a ，口( 力2 口( y ) ) ( 1 2 2 ) 由于根據(jù)屬性集合4 ，可以定義論域上的一個等價關(guān)系，而等價關(guān)系或等價關(guān)系 生成的劃分在粗糙集理論中被看作知識，因而此處將屬性集合么亦看作知識。 定義1 5 【3 1設(shè)s 為一信息系統(tǒng)，其中尸，q _ c a r , 定義如下： 1 ) 稱知識q 依賴于知識p ( i e 做pjq ) 當且僅當n r d ( p ) s n d ( q ) ； 2 ) 稱知識p 與知識q 等價( 記做p = q ) 當且僅當p q 且qj 尸； 3 ) 知識尸與知識q 獨立( 記做p q ) 當且僅當尸q 且qjp 均不成立。 顯然，p = q 當且僅當刪d ( p ) = n d ( q ) 當知識q 依賴于知識p 時，我們也說知識 q 是由知識p 導出的。 通過簡單推導可得到下列性質(zhì)。 定理1 3 【3 1設(shè)s 為一信息系統(tǒng)，其中尸，q ，丑，r 4 乃有 若pjq 且q r ，則戶r ； ( 1 2 3 ) 若pj r 且q r ，貝j j p u qjr ； ( 1 2 4 ) 若尸qur ，則p r 且pjq ；( 1 2 5 ) 若pjq 且q urj 正貝u e urj r ； ( 1 2 6 ) 若pj q 且r l 則pu 尺jq u r ；( 1 2 7 ) 若p q 且p 3p ，則尸q ； ( 1 2 8 ) 若p q 且q7 cq ，則pjq ( 1 2 9 ) 有時候知識的依賴性可能是部分的【3 1 ，這意味著知識q 僅有部分是由知識尸導出 的，部分導出可由知識的正域來定義： p o s e ( q ) = u e ：x e u i n d ( q ) ) ( 1 3 0 ) 其中p 2 幽 p o s p ( q ) 的含義是u 中所有根據(jù)分類u d ( 尸) 的信息可以準確地劃分到q 的等價 類中去的對象集合。 q 部分依賴于尸的依賴度定義為【3 】： k = y e ( 9 ：ip o 百s 丁p ( q 一) 1 ( 1 3 1 ) l 緒論博士論文 很明顯0 七1 我們用尸j 女q 表示q 是k 度依賴于尸的。當七= 1 時，稱q 完全依賴 于p ；當o k l 時，稱q 部分依賴于尸；當七= o n ，稱q 完全獨立于尸 1 3 3知識約簡與核 知識約簡是粗糙集理論的主要內(nèi)容，通過約簡，可以除去冗余知識，獲得簡化的 決策規(guī)則，以下將引入一些知識約簡的基本概念。 定義1 6 1 3 1設(shè)s 為一信息系統(tǒng)，對于v a e a t , 若有i n d ( a t - a ) = i n d ( a 乃，則稱口枷r 中是可約去的( 不必要的) ，否則稱a 是不可約去的( 必要的) 。 不必要的屬性在信息系統(tǒng)中是多余的，如果將它從信息系統(tǒng)中去掉，不會改變信 息系統(tǒng)的分類結(jié)果；相反，若從信息系統(tǒng)中去掉一個必要的屬性，則一定改變信息系 統(tǒng)的分類結(jié)果。 定義1 7 1 3 1設(shè)s 為一信息系統(tǒng)，對于v a e a t , 口都是么r 中不可約去的，則稱知詘r 是 獨立的，否則稱為相關(guān)的。 對于相關(guān)知識來說，其中包含多余知識，需要對其進行約簡。 定義1 8 t 3 】設(shè)s 為一信息系統(tǒng)，a _ c a l 若滿足 1 ) 1 n d ( a ) = 1 n d ( a t ) ； 2 ) 彳是獨立的； 則稱么黝丁的一個約簡( r e d u c t ) 很明顯，對于相關(guān)知識所求得的約簡并非唯一的，因此可以引入以下定義。 定義1 9 t 3 令s 為一信息系統(tǒng)，彳r 中所有不可約去的知識稱為彳丁的核( c o r e ) ，記為 c o r e ( a t ) 約簡與核有如下關(guān)系。 定理1 4 【3 】設(shè)s 為一信息系統(tǒng)，則 c o r e ( a t ) 2n 氏 ( 1 3 2 ) i = l 其中4 0 f ( 1 f s ) 表示么確所有約簡。 可以看出，核這個概念的用處有兩個方面2 4 】：首先它可以作為計算所有約簡的基 礎(chǔ)，因為核包含在所有的約簡中，并且計算可以直接進行；其次可解釋為在知識約簡 時不能消去的知識特征的集合。 例1 1對于表1 1 所示的一個信息系統(tǒng)， u = 缸l ，x 2 ，x 3 ，x 4 ，x d 為論域， a t = 口，b ，c ，田為所有屬性集合。 根據(jù)定義1 8 可以看出表1 1 有兩個約簡 口，6 ， 6 ，田，所以核屬性為 6 ) 約簡和核這兩個概念是粗糙集的精華所在1 2 4 。約簡計算的復雜性隨著信息系統(tǒng)規(guī) 模的增大呈指數(shù)增長，是一個n p 完全問題。在實際問題應用中，沒有必要求出所有的 r 博士論文 不完備信息系統(tǒng)中粗糙集理論研究 約簡，引入啟發(fā)式搜索可以找到較優(yōu)的約簡。文獻【2 5 】給出了區(qū)分矩陣和區(qū)分函數(shù)來計 算約簡和核，給出了約簡和核的結(jié)構(gòu)表示，該方法用于信息系統(tǒng)規(guī)模較小時較為有效。 表1 1 信息系統(tǒng)示例 1 3 4決策系統(tǒng) 決策系統(tǒng)是一類特殊而又重要的信息系統(tǒng)，多數(shù)決策問題都可以用決策系統(tǒng)的形 似來表達，這一工具在決策分析問題中起著重要的作用。 一個決策系統(tǒng)是一個信息系統(tǒng)s = ，其中彳瞰稱為條件屬性集合，d 稱為決策屬性集合助丁n d 1 2 j 【3 】若d 中含有兩個或兩個以上的決策屬性，則稱s 為一個多屬性決策系統(tǒng)；若d = , t 3 ，即d 中僅含一個決策屬性，則稱s 為一個單屬性決 策系統(tǒng)，記為s = 以a t u 痧若無特殊說明，本文所討論的決策系統(tǒng)都是單屬性決 策系統(tǒng)。 定義1 1 0 【3 】設(shè)溈一決策系統(tǒng)，對于壇，y 以若伍力e l n d ( a ) j = ，則稱這個 決策系統(tǒng)是一致的，否則稱為不一致的。 例1 2表1 2 是一個不一致決策系統(tǒng)，其中 u = x i ，x 2 ，x s 為論域， a t = 口，b ，c 為所有條件屬性集合， d 為決策屬性。 表1 2不一致決策系統(tǒng) 9 l 緒論博士論文 對于任何一個不一致決策系統(tǒng)s 都可以分解成兩個子系統(tǒng)兩，& ，在s l t ：p ，對于v x ， y 以若 ，y ) e l n d ( a ) ，則有荊= m ) ，n n s l 是一個一致決策系統(tǒng)；在在& 中，對于 壇，y 以若x y 且 ，y ) i n d ( a ) 則有撒) ，稱& 是一個全不一致決策系統(tǒng)【9 】。 例1 3對于表1 2 所示的不一致決策系統(tǒng)，可以分解為以下兩個子系統(tǒng)分別如表1 3 和1 4 所示： 表1 3一致決策系統(tǒng) 定義1 1 1 3 】設(shè)s 為一決策系統(tǒng)，v a e a 瓦如果 p o s a r ( d ) = p o s a r - 口 ( d ) ， ( 1 3 3 ) 則稱a 為彳丁中環(huán)必要的，否則稱口為a t 中秘要的。 定義1 1 2 3 設(shè)s 為一決策系統(tǒng)，如果對于v a e a l 口為彳丁中秘要的，則稱屬性集鍆r 為融立的( 黝瑚對于拋立) ，否則橢功擁依的。 定義1 1 3 t 3 】設(shè)s 為一決策系統(tǒng)，彳丁中所有秘要的屬性組成的集合稱為彳r 的獺，簡稱 為相對核，記為c o r e 爿r ( d ) 定義1 1 4 t 3 1 設(shè)s 為一決策系統(tǒng)，a _ c a t , 若滿足 1 ) p o s a r ( d ) = p o s a ( d ) ； 2 ) 么相對于拋立； 則稱彳黝r 的一個鋤簡。 定理1 5 3 1 設(shè)s 為一決策系統(tǒng)，則 三 c o r e a r ( d ) 5f 1a( 1 3 4 ) i f f i l 其中中彳l f ( 1 i s ) 表示彳r 的所有蹦簡。 l o 博士論文不完備信息系統(tǒng)中粗糙集理論研究 1 4本文的研究背景及主要內(nèi)容 1 4 1研究背景 經(jīng)典粗糙集理論是建立在等價關(guān)系基礎(chǔ)上的，等價關(guān)系要求滿足自反、對稱和傳 遞性，因而要求較為嚴格。根據(jù)等價關(guān)系的特性，經(jīng)典粗糙集一般可用來處理具有離 散屬性值的完備信息系統(tǒng)，即信息系統(tǒng)中的所有屬性值都是知道并且是確定的。然而 值得注意的是，在現(xiàn)實世界中由于各種原因，數(shù)據(jù)庫管理人員經(jīng)常會遇到數(shù)據(jù)缺損情 況。例如，根據(jù)傳感器獲取故障診斷信息，若由于傳感器故障或數(shù)據(jù)傳送堵塞等原因， 就無法及時地獲取獲得有用的數(shù)據(jù)，這種情形在醫(yī)學診斷，供應鏈管理及交通管理等 眾多領(lǐng)域都是不可避免的。因而如何使用粗糙集理論處理具有缺損數(shù)據(jù)的信息系統(tǒng)， 對于粗糙集理論的發(fā)展具有極其重要的意義，同時這也是進一步將粗糙集理論推向?qū)?用的關(guān)鍵步驟之一。本文將具有缺損數(shù)據(jù)的信息系統(tǒng)稱為不完備信息系統(tǒng)，這種不完 備信息系統(tǒng)正是本文的主要研究對象。 1 4 2主要研究內(nèi)容 本文在不完備信息系統(tǒng)中，以知識獲取為目的，以粗糙集理論為數(shù)學工具，對不 完備信息系統(tǒng)中的各種拓展粗糙集模型進行了研究。主要內(nèi)容總結(jié)如下： 1 ) 當不完備信息系統(tǒng)中所有的未知屬性值都是缺席型時，提出了差異關(guān)系及基于差 異關(guān)系的粗糙集模型，據(jù)此可以用來獲取不完備決策系統(tǒng)中的否定規(guī)則； 2 ) 在不完備信息系統(tǒng)中提出了可變精度分類粗糙集模型的概念，證明了基于容差關(guān) 系、非對稱相似關(guān)系的粗糙集模型是可變精度分類關(guān)系粗糙集模型的特例； 3 ) 在同時具有遺漏型和缺席型未知屬性值的廣義不完備信息系統(tǒng)中，分析了原有特 征關(guān)系分類的不足之處，進而提出了3 種不同形式的特征關(guān)系，并對基于不同特 征關(guān)系的粗糙集模型進行了對比分析； 4 ) 在具有遺漏型未知屬性值的不完備信息系統(tǒng)中，提出了t 和、【描述子的概念，討論 了如何求得t 和、 約簡描述子的分辨矩陣方法，相對于原有的擴展優(yōu)勢關(guān)系來說， 使用t 和上描述子的概念，不僅可以消除決策規(guī)則中的未知屬性值，還可以獲得包 含更為豐富信息的決策規(guī)則； 5 ) 在具有缺席型未知屬性值的不完備信息系統(tǒng)中，提出了相似優(yōu)勢關(guān)系的概念，相 似優(yōu)勢關(guān)系融合了傳統(tǒng)非對稱相似關(guān)系和優(yōu)勢關(guān)系的特性，是這兩種關(guān)系的廣義 化表現(xiàn)形式；根據(jù)基于相似優(yōu)勢關(guān)系的粗糙集模型，提出了幾種近似分布約簡的 概念； 6 ) 將基于相似優(yōu)勢關(guān)系的粗糙集模型引入不完備模糊決策系統(tǒng)中，進而討論了知識 約簡與最優(yōu)規(guī)則獲取的問題； l 緒論博士論文 7 ) 由于區(qū)間值也代表了一種形式的不完備信息，因而研究了區(qū)間值信息系統(tǒng)中的優(yōu) 勢關(guān)系粗糙集模型問題。在區(qū)間值信息系統(tǒng)中，不僅提出了6 種形式的相對約簡 以獲取最優(yōu)決策規(guī)則，而且進一步考慮對象與對象之間的優(yōu)勢程度，據(jù)此構(gòu)建了 模糊粗糙集模型以進行區(qū)間值信息系統(tǒng)中的知識獲取。 1 4 3本文組織結(jié)構(gòu) 全文共分七章。 第一章緒論 概述了粗糙集理論的、發(fā)展歷程，介紹了其基本理論和方法，闡述了本文的研究 背景和研究內(nèi)容。 第二章不完備信息系統(tǒng) 在不完備信息系統(tǒng)中提出了基于差異關(guān)系，可變精度分類的粗糙集模型；分析了 集值信息系統(tǒng)中基于不同二元關(guān)系的粗糙集模型的關(guān)系。 第三章廣義不完備信息系統(tǒng)與特征關(guān)系 對于同時具有遺漏型和缺席型未知屬性值的廣義不完備信息系統(tǒng)，提出了3 種不 同形式的特征關(guān)系及相應的粗糙集模型。 第四章不完備信息系統(tǒng)中的擴展優(yōu)勢關(guān)系與最優(yōu)可信規(guī)則 在具有遺漏型未知屬性值的不完備信息系統(tǒng)中，提出了t 和j ，描述子的概念，討論 了如何根據(jù)t 和i 描述子獲取不完備決策系統(tǒng)中的最優(yōu)“a tl e a s t ”和“a tm o s t ”確定規(guī)則。 第五章基于相似優(yōu)勢關(guān)系的粗糙集模型 在具有缺席型未知屬性值的不完備信息系統(tǒng)中，提出了相似優(yōu)勢關(guān)系的概念，根 據(jù)基于相似優(yōu)勢關(guān)系的粗糙集模型，提出了4 種形式的近似分布約簡：在具有缺席型 未知屬性值的不完備模糊系統(tǒng)中，研究了基于相似優(yōu)勢關(guān)系的粗糙模糊集與知識約簡 等問題。 第六章區(qū)間值信息系統(tǒng)中的優(yōu)勢關(guān)系粗糙集模型 在區(qū)間值決策系統(tǒng)中，首先根據(jù)優(yōu)勢關(guān)系，提出了6 種不同形式的相對約簡以獲 取簡化的決策規(guī)則；接著，考慮對象與對象之間的優(yōu)勢程度，將模糊粗糙集模型引入 區(qū)間值決策系統(tǒng)以進行知識獲取。 第七章結(jié)束語 總結(jié)了全文并對下一步的研究工作進行了展望。 1 2 博士論文不完備信息系統(tǒng)中粗糙集理論研究 2 不完備信息系統(tǒng) p a w l a k 所提出的經(jīng)典粗糙集理論是建立在不可分辨關(guān)系( 自反、對稱和傳遞) 的 基礎(chǔ)上的，因而主要用來處理具有離散屬性值的完備信息系統(tǒng)。然而遺憾的是，在現(xiàn) 實世界中，由于數(shù)據(jù)測量的誤差、對數(shù)據(jù)的理解或獲取的限制等眾多原因，所面臨的 信息系統(tǒng)往往是不完備的。因此，如何使用粗糙集理論從不完備信息系統(tǒng) 2 6 - 3 5 】 ( i n c o m p l e t ei n f o r m a t i o ns y s t e m ，簡稱l i s ) 中挖掘知識對于粗糙集的發(fā)展具有舉足輕 重的作用。 目前利用粗糙集數(shù)學模型處理i i s 的常用手段有2 種： 1 ) 間接處理【3 6 1 ，這種方法有兩種情形：第一種情形是刪去帶有未知值的實例，但是 這將會丟失數(shù)據(jù)中很多有用的知識；第二種情形是通過一定的方法把不完備信息 系統(tǒng)轉(zhuǎn)化為完備信息系統(tǒng)，即數(shù)據(jù)補齊，但是，補齊處理只是將未知值補以我們 的主觀估計值，這或多或少改變了原始的信息系統(tǒng)中的信息分布，因此不一定完 全符合客觀事實； 2 ) 直接處理，其特點是對經(jīng)典粗糙集理論中相關(guān)概念在不完備信息系統(tǒng)下進行適當 擴充。 值得注意的是由于間接處理方法會損害到數(shù)據(jù)的原有分布特征，挖掘出的規(guī)則往 往帶有不確定性