（應(yīng)用數(shù)學(xué)專業(yè)論文）粗糙集理論及其對信息表處理中的若干問題研究.pdf

國 防 科 學(xué) 技術(shù) 大 學(xué)研 究 生 院 學(xué) 位論 文摘要 粗糙集理論是由波蘭數(shù)學(xué)家z . p a w l a k 于 1 9 8 2 年提出一種新的處理不精確和不確定問題的數(shù)學(xué)工具，近年來得到了迅速地發(fā)展，并在很多領(lǐng)域取得了成功的應(yīng)用。粗糙集理論建立在論域中的不可分辨關(guān)系之上， 用上、下近似來描述概念， 基于粗糙集理論的數(shù)據(jù)分析無需提供任何先驗知識。本文完成的工作和取得的創(chuàng)新在于: 本文揭示了 約簡在數(shù)量上的一個重要性質(zhì)， 給出了又一種屬性重要性的定義以及相應(yīng)的啟發(fā)式算法，并且對算法作了詳細(xì)的分析，在此基礎(chǔ)上還類似討論了相對約簡。 經(jīng)典的粗糙集理論是基于完備信息系統(tǒng)的，然而實際中由于種種原因會碰到不完備信息系統(tǒng)，本文給出了一種不完備信息系統(tǒng)的完備化方法以及其相應(yīng)的規(guī)則提取方法。 近似集是粗糙集理論中的基本概念，本文通過對約簡和近似集的關(guān)系研究，定義了一種新的相對約簡一保近似約簡，并通過實例驗證了保近似約簡的實踐意義。 最后作者規(guī)范地給出了基于序關(guān)系的粗糙集模型并做了相應(yīng)的討論，還給出了一個利用基于序關(guān)系的粗糙集來處理有序信息表的實例。關(guān)鍵詞: 粗糙集理論 信息系統(tǒng) 啟發(fā)式算法 保近似約簡 序關(guān)系. 一一-. 一一. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . -. -一- 第1 貞國 防科 學(xué) 技術(shù) 大 學(xué)研 究 生 院學(xué)位 論 文ab s t r a c t r o u g h s e t t h e o ry , p r o p o s e d b y z . p a w l a k i n 1 9 8 2 , h a s b e c o m e a r e c o g n i z e d a n d w i d e l ys tu d i e d m e t h o d w i t h m a n y p u b l ic a t i o n s in v a r io u s f i e ld s t o d a t e . r o u g h s e t t h e o ry i s a n e wm a t h e m a t i c a l t o o l t o d e a l w i t h t h e v a g u e n e s s a n d u n c e r t a i n t y , i t i s b a s e d o n t h e i n d i s c e rni b i l i t yr e l a t i o n t h a t d e s c r i b e s i n d i s t i n g u i s h a b l e o b j e c t s , a n d c o n c e p t s a r e r e p r e s e n t e d b y l o w e r a n d u p p e ra p p r o x i m a t i o n s . p r e l i m i n a ry i n f o r m a t i o n a b o u t t h e d a t a i s n o t n e e d e d i n r o u g h s e t d a t a a n a l y s i st h e p r i m a ry c o n t r i b u t i o n s o f t h i s t h e s i s i n c l u d e : r e d u c t i o n o f k n o w l e d g e i s o n e o f t h e m o s t i m p o rt a n t t o p i c s i n t h e r e s e a r c h o n r o u g h s e tt h e o ry . a n i m p o rt a n t c h a r a c t e r i s t i c o f r e d u c t i o n r e g a r d i n g t h e n u m b e r i s d e m o n s t r a t e d , f o l l o w e db y a n o t h e r d e f in i t i o n o f a tt r i b u t e s s i g n i f i c a n c e a n d a c c o r d i n g h e u r i s t i c a l g o r i t h m . t h e a l g o r i t h mi s t h o r o u g h l y a n a l y z e d . t h e r e l a t i v e r e d u c t i s d i s c u s s e d i n a s i m i l a r f a s h i o n t h e c l a s s i c a l r o u g h s e t t h e o ry d e v e l o p e d b y p a w l a k i s b a s e d o n c o m p l e t e i n f o r m a t i o ns y s t e m s . i n t h i s t h e s i s a m e t h o d f o r i n c o m p l e t e i n f o r m a t i o n s y s t e m s i s p r o p o s e d . t h e r e l a t i o n s h i p o f r e d u c t a n d r e l a t i v e r e d u c t a n d t h e u p p e r a p p r o x i m a t i o n a n d l o w e ra p p r o x i m a t i o n i s d i s c u s s e d i n t h e t h e s i s , b a s e d o n w h i c h a n o v e l r e l a t i v e r e d u c t - h o l d i n ga p p r o x i m a t i o n r e d u c t i s p r o p o s e d . t h e b e n e f i t s o f h o ld in g a p p r o x i m a t i o n r e d u c t a r e e x p l a i n e dt h r o u g h a n e x a m p l e . a t l a s t t h e . r o u g h s e t s m o d e l b a s e d o n o r d e r r e l a t i o n s i s p r o p o s e d n o r m a t i v e l y a n d d is c u s s e dt h o r o u g h l y w i t h a n e x a m p l e .k e y w o r d s : r o u g h s e t t h e o r y , i n f o r m a t i o n s y s t e m , h e u r i s t i c a l g o r i t h m , h o l d i n g a p p r o x i m a t i o n r e d u c t , o r d e r r e l a t i o n s一 -一-， 第1 1i ;獨創(chuàng)性聲明 本人聲明所呈交的學(xué) 位論文 是我 本人在導(dǎo)師 指導(dǎo)下進(jìn)行的 研究工 作及取得的 研究 成果. 盡我所知， 除了 文中 特別 加以 標(biāo) 注和致謝的 地方外， 論文中 不 包含其 他人已 經(jīng)發(fā)表和撰寫過的 研究成果， 也 不 包 含為獲得國防 科學(xué)技術(shù) 大學(xué) 或 其它教育 機構(gòu)的學(xué) 位或證書而 使用過的 材料. 與我 一同 工作的同志對 本研究 所 做的 任何貢獻(xiàn)均已 在論文中作了 明確的說明 并表示謝意. 學(xué) 位 論文 題目 :粗糙集 理論 及其 對 信 息 表處 理中 的 若干問 題 研究學(xué) 位 論 文 作 者 簽 名 : 冷、 勿 文日 期 :鄉(xiāng) 衫年/ 月 獷 日學(xué)位論文版權(quán)使用授權(quán)書 本人完全了 解國防科學(xué)技術(shù)大學(xué)有關(guān)保留、 使用學(xué)位論文的規(guī)定。 本人授權(quán)國防 科學(xué)技術(shù)大學(xué)可以 保留 并向國 家有關(guān)部門 或機構(gòu)送交論文的復(fù)印 件和電 子文 檔， 允許 論文 被查閱 和借閱; 可以 將學(xué) 位論文 的 全部或部分內(nèi) 容編 入有關(guān) 數(shù) 據(jù)庫進(jìn)行 檢索，可以 采用影印、 縮印 或掃 描等復(fù) 制手段保存、匯 編學(xué) 位 論文 . ( 保密學(xué)位論文在解密后適用本授權(quán)書. 學(xué) 位論文題目 :學(xué)位論文作者簽名:作者指導(dǎo)教師簽名i f 月j 日國 防 科 學(xué) 技 術(shù) 大 學(xué) 研 究 生 院 學(xué) 位 論 文圖表目錄圖2 . 1 顯示屏及其相應(yīng)的信息表_ “ _ ._ _ _ _ . . . _ .表 2 .2 決策表實例. . . 一 . . . . _ . _ . _ . ， . . . . 表2 .3 決 策 規(guī) 則. . . . ， - - ，- ， t表4 . 1 屬性a 上對象的取值 _ . _ _ _ . .， . . 表4 .2 完各化后屬性口 上對象的取值. . . . . .表4 .3 屬性a 上對象的取值. ._ _ _ . . . ， . ， 二表4 .4 完備化后屬性 a 上對象的取值. .表4 .5 己經(jīng)完成完備化的第一，二步. 表4 .6 完備化的第三步 _ _ - . . . . 表4 .7 完備化的第四步 . _ - . . . . . 二表4 . 8 完備化的第五步. . 一 ， . 二價 ， . 表4 .9決 策 規(guī) 則 ，一 ” .“ .“表5 . 1 個 決 策 系 統(tǒng) -， “ . .表 5 2 區(qū)分矩陣. 一. .二 . _. 二表5 .3 d基本范疇的上近似. . . . 二 . . 一表6 . 1有 序 決 策 表.一 ， 卜 一 8.8. 81 41 51 51 51 71 71 81 81 82 42 42 43 0國 防 科 學(xué) 技 術(shù) 大 學(xué) 研 究 生 院 學(xué) 位 論 文第一章緒論 智能信息處理是當(dāng)前信息科學(xué)理論和應(yīng)用研究中的一個熱點領(lǐng)域，隨著過去幾十年中人們在專家系統(tǒng)，知識工程，人工神經(jīng)網(wǎng) 絡(luò)，模糊集合等眾多領(lǐng)域的不斷實踐和探索，取得了很多很好的成績。隨著信息時代的到來，信息量的不斷增長，對信息分析工具的要求也就越來越高，人們希望自 動地從數(shù)據(jù)中 獲取其潛在的依賴模型。這樣，大量的數(shù)據(jù)就無需人的處理，甚至無需人的觀察。因此， 研究能夠從大量信息中形成實際概括 ( 歸納)的系統(tǒng)顯得越來越重要。雖然已經(jīng)有很多對數(shù)據(jù)進(jìn)行分析的簡單統(tǒng)計技術(shù)，但高級的分析技術(shù)還遠(yuǎn)遠(yuǎn)沒有成熟。因此，數(shù)據(jù)信息的產(chǎn)生和對它的理解之間的差距越來越大。 粗糙集理論是波蘭華沙理工大學(xué)p a w l a k 教授在2 0 世紀(jì)8 0 年代初提出的一種研究不完整， 不確定知識和數(shù)據(jù)的表達(dá)， 學(xué)習(xí)， 歸 納的 理論方法 0 。 到1 9 9 0 年前后，由 于該理論在數(shù)據(jù)的決策與分析、模式識別、數(shù)據(jù)挖掘、機器學(xué)習(xí)與知識發(fā)現(xiàn)等方面的成功應(yīng)用，逐漸引起了世界各國學(xué)者的廣泛關(guān)注。 本章首先介紹信息表知識表達(dá)系統(tǒng);1 . 2 節(jié)介紹粗糙集理論的興起:1 . 3 節(jié)介紹粗糙集理論的特點:1 .4 節(jié)介紹粗糙集理論的研究現(xiàn)狀:1 . 5 節(jié)介紹本文的工作和內(nèi)容組織。 1 . 1 信息表知識表達(dá)系統(tǒng) 知識表達(dá)是智能信息處理的關(guān)鍵。 所謂知識獲取， 就是從大量的原始數(shù)據(jù)信息中分析發(fā)現(xiàn)有用的規(guī)律信息，即是將知識從一種原來的表達(dá)形式 ( 原始數(shù)據(jù)表達(dá)形式) 轉(zhuǎn)化為 一種新的目 標(biāo)表達(dá)形式 ( 人類或者計算機便于處理的形式，如邏輯規(guī)則等) 。基于粗糙集理論的 知識發(fā)現(xiàn)，主要是借助信息表這樣一種有效的數(shù)據(jù)知識表達(dá)方式。 信息表知識表達(dá)系統(tǒng)的基本成分是研究對象的集合， 關(guān)于這些對象的知識是通過指定對象的屬性和它們之間的屬性值來描述的。一般地，信息表知識表達(dá)系統(tǒng)s 可以表示為: s= ( u , a , v , f )其中u :對象的集合，也稱為論域;a :屬性集合，a二 cu d，其中c , d分別稱為條件屬性和決策屬性: v 一 u v v 是 屬 性。 的 值 域 : f: ux a - - v 是一個信息函數(shù)，它為每個對象的每個屬性指定屬性值。 通常我們也稱信息表知識表達(dá)系統(tǒng)為信息表或信息系統(tǒng)，特別地，當(dāng)d# o時，也稱信息表知識表達(dá)系統(tǒng)s = ( u , a , v , f ) 為決 策表或決 策系統(tǒng)。 此外， 也常用s 二 ( u , a ) 來代替s二( u, a , v , f ) 。-一一 -一-分- 第. 頁國 防 科 學(xué) 技 術(shù) 大 學(xué) 研 究 生 院 學(xué) 位 論 文 1 . 2 粗糙集理論的興起 粗糙集理論是一種處理含糊、不確定性問題的新型數(shù)學(xué)工其。在知識工程研究中，一直存在著信息的含糊性( v a g u e n e s s ) 等問 題， 人工 智能的 基礎(chǔ)理論之一的 經(jīng)典邏輯不足以解決這些問題。為此，人們先后提出了包括統(tǒng)計方法、模糊集理論、d - s證據(jù)理論等一系列方法， 然而這些方法都有一定的缺陷或者局限， 例如模糊集方法中如何確定成員隸屬度的問 題。 粗糙集方法無需提供問 題所需處理數(shù)據(jù)之外的任何先驗信息， 如統(tǒng)計方法中的先驗概率和模糊集方法中的隸屬度。 粗糙集理論問世以來， 無論是在理論還是應(yīng)用上都得到了迅速的發(fā)展。 它在知識發(fā)現(xiàn)、機器學(xué)習(xí)、 知識獲取、決策分析、 專家系統(tǒng)、 決策支持系統(tǒng)、歸納推理、矛盾歸結(jié)、 模式識別、模糊控制等方面的成功應(yīng)有引起了各國 學(xué)者的廣泛關(guān)注。1 9 9 1 年p a w la k出 版了專著 2 1 ，系統(tǒng)全面地闡述了粗糙集理論，奠定了粗糙集理論的數(shù)學(xué)基礎(chǔ)，該書與 1 9 9 2 年出版的粗糙集理論及應(yīng)用專集 3 較好地總結(jié)了 這一時期粗糙集理論與實踐的 研究成果。自1 9 9 2 年在波蘭k i e k r z 召開第一屆粗糙集國際 研討會后， 每年都要召開以 粗糙集為主題的國際 會 議。 1 9 9 4 年國 際 上 成立了 粗 糙集學(xué) 會 ( i n t e rn a t i o n a l r o u g h s e t s o c ie t y ) 0 1 9 9 5 年a c mc o m m u n i c a t io n 將粗糙集列為新出現(xiàn)的計算機科學(xué)的研究課題。 從 1 9 9 8 年起國際上還兩年召開 一次國 際 會議r s c t c ( r o u g h s e t a n d c u rr e n t t r e n d s in c o m p u t in g ) 。 國內(nèi) 對粗糙集的 研究相對較晚， 但也得到了迅猛的發(fā)展， 尤其是西安交通大學(xué)理學(xué)院信息與系統(tǒng)研究所， 重慶郵電學(xué)院計算機科學(xué)與技術(shù)研究所等單位在這方面投入了大量的工作并取得了豐碩的成果， 到 2 0 0 1 年國內(nèi)己 在該領(lǐng)域出版了四部專著【 4 - 7 。從2 0 0 1 年起我國每年召開一次以 粗糙集為 主 題的“ 中國r o u g h 集與軟 計算 學(xué) 術(shù) 研討 會 ( c r s s c ) , 2 0 0 3 年1 0 月 第三屆c r s s c 還 與國 際 會 議r s f d g r c 2 0 0 3 c 9 i n t e rn a t i o n a l c o n f e r e n c e o n r o u g h s e t s , f u z z ys e t s , d a t a m i n i n g a n d g r a n u la r c o m p u t i n g ) 同 時同 地在 中國 重 慶召 開。 此外， 中國 人s智能學(xué)會粗糙集與軟計算專業(yè)委員會也于2 0 0 3 年 1 1 月成立。 1 . 3 粗糙集理論的特點口 不可分辨關(guān)系 粗糙集理論是建立在給定對論域的劃分基礎(chǔ)之上的。在信息表的處理中，根據(jù)對象所具有的屬性值將其劃分到不同的類別，若兩個對象具有相同的屬性值，那么它們是不可分辨的，即根據(jù)己有的信息不能夠?qū)⑵鋭澐珠_， 實際上這亦是一種等價關(guān)系。不可分辨關(guān)系是粗糙集理論最基本的概念，并在此基礎(chǔ)上引入了上、下近似等基本概念?？谛滦偷某蓡T關(guān)系 對于經(jīng)典集合， 一 個元素要么屬于這個集合，要么不屬于這個集合，也就是說其對應(yīng)的 特征函數(shù)的 值域為 。 ， 1 。 模糊集合對此進(jìn)行了 拓廣， 認(rèn)為 一個元素可以 在 1 定 程度上屬于 一 個集合， 即 其 特征函 數(shù)的 值域為 0 , 1 ， 這 使 得 模糊 集理論能 夠處 理一 定的 模 糊和不 確定問題， 然而 集合成員 對于集合的隸屬度的確定又帶來了 新的問 題，實際上這往往給問題的處理帶來主觀上的人為因素。在粗糙集理論中，成員關(guān)系不再是一個原始的概念，因此無需人為指定一個隸屬度，從而避免了主觀因素的影響。設(shè)pcu . x 二 u，元素x 和集合p國 防 科 學(xué) 技 術(shù) 大 學(xué) 研 究 生 院 學(xué) 位 論 文之間的成員關(guān)系函數(shù)定義為:,u p ( x ) = p 門 a x l e 1 1 x b!其中r 是u上的一個不 可分 辨關(guān)系， 1 x * 表示關(guān)系r 產(chǎn)生 的 包含x 的 等價類。 顯然， 粗糙集成員 關(guān)系函數(shù)的 值域也為1 0 , 1 ， 所不同的是其不是主觀 給定的?？?概念的邊界 知識的粒度性是造成對某些概念不能精確表示的原因。粗糙集理論中的模糊性就是一種基于邊界的概念，為了刻畫模糊性，每個不精確的概念山其上、下近似這一對精確集來刻畫。其中，集合的下近似包含了所有確定屬于集合的元素，而集合的上近似包含了所有可能屬于集合的元素。一個概念的上、下近似之差就是此概念的邊界，即一個集合邊界中的元素不確定屬于或者不屬于該集合。很顯然，若邊界非空，則集合不是一個精確集?？?信息表與數(shù)據(jù)分析 用粗糙集方法進(jìn)行數(shù)據(jù)分析， 一般采用信息表來表示數(shù)據(jù)。信息表通過有限的屬性描述對象， 表達(dá)了 關(guān)于對象的 所有可獲得的信息和知識。 實際上，知識表在很多領(lǐng)域都得到過應(yīng)用。信息表類似關(guān)系數(shù)據(jù)庫模型的表達(dá)方式。粗糙集理論在信息表上，通過屬性值來確定不可分辨關(guān)系，從而分析屬性之間以及屬性值之間的關(guān)系?？?1 . 4 粗糙集理論的研究現(xiàn)狀口 粗糙集近似算子的構(gòu)造性研究 粗糙集近似算子的定義與模型的推廣是粗糙集理論研究的主要方向之一。構(gòu)造性方法是以論域上的二元關(guān)系，領(lǐng)域算子或者布爾代數(shù)作為基本要素，構(gòu)造性的定義算子，然后導(dǎo)出粗糙集代數(shù)系統(tǒng)。文【 8 - 9 1 提出了基于隨機集的粗糙集模型， 用隨機粗糙集同時刻刻畫了集合定性與定量的問題。文【 1 0 1 提出了基于領(lǐng)域算子系統(tǒng)的粗糙集近似算子系統(tǒng)。口 粗 糙 集 的 公 理 化 研 究 1 1-12 1 近似算子的公理化方法與構(gòu)造性方法相反，它不是以 二元關(guān)系為基本要素，它的基本要素是一對滿足某些公理的一元集合算子，即粗糙代數(shù)系統(tǒng)是事先給定的。 近似算子的某些公 理能保證恰好有一些特殊類型的二元關(guān)系的存在， 使得這些關(guān)系通過構(gòu)造性方法產(chǎn)生給定的近似算子?？?粗糙集的代數(shù)問題研究 文 1 3 利用代數(shù)方法討論了兩個信息系統(tǒng)同態(tài)交流下的不變性，文【 1 4 - 1 5 討論了粗糙群的概念及性質(zhì)?？?粗糙集與拓?fù)淇臻g關(guān)系的研究 文【 1 6 討論了粗糙集與拓?fù)淇臻g的關(guān)系， 指出p a w l a k 粗糙集模型等價于一類特殊的拓?fù)淇臻g，一個拓?fù)淇臻g對應(yīng)于一個特殊的一般關(guān)系下的近似空間。國 防 科 學(xué) 技 術(shù) 大 學(xué) 研 究 生 院 學(xué) 位 論 文口 粗糙集的度量與粗糙集理論中不確定性問題的研究 尋求一個度量來刻劃知識的不確定性也是粗糙集理論研究的一個重要方向。 文 1 7 - 1 8 1將包含度理論引入到粗糙集數(shù)據(jù)分析中，證實了粗糙集數(shù)據(jù)分析中的各種度量均可以歸結(jié)為包含度。文【 1 9 對粗糙集理論中的度量進(jìn)行了系統(tǒng)的研究?？?粗糙集與其它方法的融合 文【 2 0 對粗糙集理論與證據(jù)理論的關(guān)系進(jìn)行了系統(tǒng)深入的研究。雖然目 前有很多數(shù)據(jù)分析處理的方法， 但還沒有一種特別有效。文 2 1 將粗糙集理論與模糊集理論進(jìn)行比較，通過粗糙隸屬函數(shù)將模糊集的研究方法引入到粗糙集的研究中?？?知識約簡與數(shù)據(jù)分析的 研究 基于粗糙集理論的知識約簡與數(shù)據(jù)分析是粗糙集理論研究的一個主要方向，是粗糙集理論到應(yīng)用的一個關(guān)鍵過程，也是當(dāng)前最活躍的研究領(lǐng)域之一， 其中的研究熱點包括:屬性 約 簡 2 2 .2 4 ， 不完全 信息表的 處 理 2 5 -2 6 ， 連續(xù) 屬性的 離 散 化 2 7 以 及 對有 序 信息 表 2 8 -2 9 的 處理等。 1 . 5 本文的工作和內(nèi) 容組織 本文對粗糙集理論的討論將重點結(jié)合利用粗糙集理論對信息表的處理，即上節(jié)中最后提到的一些問題。本文的第二章到第六章的內(nèi)容安排如下: 第二章作為本文的基礎(chǔ)部分，介紹了 粗糙集理論的 一些基本概念， 給出上、 下近似等基本概念和一些基本理論，并對這些概念在信息表中的演化作了說明。此外，本章引入了屬性約簡，決策規(guī)則等概念并通過實際的例子作了進(jìn)一步說明。 第三章通過揭示屬性約簡的一個數(shù)值上的特征給出了 屬性約簡的一種啟發(fā)式算法。 第四章簡單介紹了現(xiàn)有對不完備信息表的處理基礎(chǔ)方法， 給出了一種新的信息表缺值和多值處理方法。 第五章對約簡與近似集的關(guān)系作了深入的研究，并在此基礎(chǔ)上提出了一種新的相對約簡一保近似約簡并作討論。 第六章規(guī)范給出了基于序關(guān)系的粗糙集模型并作了相關(guān)討論。 最后結(jié)論部分是本文的工作總結(jié)以及對將來研究的展望。國 防 科 學(xué) 技 術(shù) 大 學(xué) 研 究 生 院 學(xué) 位 論 文第二章粗糙集理論的基本概念 定義非空論域 u上的粗糙集是要借助與 u上特定的二元關(guān)系r ，對任意的x e u,記r ( x ) = ( y e ui x r y ) ，如下給出 對r的一些性質(zhì)的定義: 自 反性d x e u , x e r ( x ) 對稱性b x , y e u , y e r ( x ) = x e r ( y ) 傳遞性b x , y , z e u , y e r ( x ) , z e r ( y ) , = : : e r ( x ) 經(jīng)典的粗糙集模型是基于等價關(guān)系之上的，即 r滿足自 反性，對稱性和傳遞性。記u / r 為r 的 所 有等價 類構(gòu)成的 集合， 其中【 x ， 表示 包 含x e u的r 等 價 類。 這 樣， 對任意的集合xc u可以導(dǎo)出兩個由r的等價類為基本元素構(gòu)成的集合:= u i x x i i x r n x ， 。 = u ( x l , i x, c_ x ) 稱r x為x的 上近似，r x為x的 下 近 似， 很 顯 然有鮮 c xc 欣 。 上、 下 近似是 粗糙集理論中的基本概念，對論域中的子集的認(rèn)識也正是利用其相應(yīng)的上、卜 近似來描述。當(dāng)x恰好能夠表示成某些r的等價類的并時，稱x是r可定義的，即x是r精確集，此時 有夢 = x= n x;當(dāng)x不能 夠 表 示 成r的 等 價 類的 并時， 稱x是r不 可定 義的， 即x是r 粗糙集。 對于粗糙集可以 利用其上、下近似這兩個精確集來近似地表示。 r是論域 u上的一般二元關(guān)系， 則對論域 u的任一子集x關(guān)于關(guān)系r的 上、下近似的定義一般有以下幾種:二 x e u ir ( x ) 二 x )= x c u ir ( x ) n x s d xxr一一r 1 11 了.、r x = u r ( x ) ir ( x ) 二 x )r x 一 u r ( x ) ir ( x ) n x ， 。 了!j，十 、.尹 2 f一 u ir (x ) ir ( x ) 二 x = u r ( x ) 卜 c- x )xx陣.珠陣很明顯當(dāng)r為等價關(guān)系時以上三種定義是等價的。對于信息表知識表達(dá)系統(tǒng)3 = ( u , 刃，以 下假設(shè)任意屬性在論 域的 取值不是唯一的，因為那樣的屬性對于分類沒有意義。關(guān)系i n d ( p ) :則任意非空屬性集p ca 確定了u上 的一個不可區(qū)分( x , y ) e i n d ( p ) g a ( x ) = a ( y ) , d x , y u , a p顯 然in d ( p ) 是u 上的一個等價 關(guān)系， 其等價類u j in d ( p ) 稱為p 的 基 本范疇， 簡記為國防科學(xué)技術(shù) 大學(xué)研 究 生院學(xué)位論文u l p o b xcu , p c_a ( p # 0 ) ， 如下子集:p x= u y e u / p i y (= x ) p x= u y e u / p i y 門 x # o )分別稱為x的p 下近似和p 上近似。當(dāng)x的上、下近似相等，即x能表達(dá)成某些p 基本范疇的并時，稱 x是p可定義的，否則稱 x是p粗糙集。令 o e q c a，如果in d ( q ) z i n d ( q - a ) ，則稱a 是q中必要的，否則 稱a 是q 中 不必要的，q中 所有必要的屬性組成的集合稱為q的核， 記為c o r e ( q ) 。 如果h a c q 都是q 中 必要的， 則稱q 是獨立的;否則 稱q 是 依 賴的。 如果q 是 獨 立的， 且q c_ p c a 滿 足in d ( q ) = in d ( p ) ， 則 稱q 為p 的 一個約簡。p 的所有約簡記為r e d ( p ) ，不難發(fā)現(xiàn)c o r e ( p ) = n re d ( p ) 。 考慮信息系統(tǒng)一個屬性子集對論域的劃分與另一個屬性子集對論域的劃分之間的關(guān)系， 令屬性 集c , d c_ a 非空， 則d 的c 正 域p o s c ( d ) 定義 如 下:p o s , ( d ) = u c xx . u/ d集 合 b c c 是 一 個c 的 d 約 簡( 相 對 約 簡) ， 如 果 有p o s , ( d ) = p o s y ( d ) 且b 是 相 對d 獨 立的，即 p o s b ( d ) * p o s , ， 一 、o n ( d ) , v a e bc 的 所 有d 約 簡 記 為r e d , ( c ) 。 同 樣 有c o r e d ( c ) = 門 r e d d ( c ) ， 其 中 c o r e , ( c ) 定 義 為 : c o r e , ( c ) = ( a e c i p o s ro _ ia t ) ( d ) 3, p o s , ( d ) ) 決 策 表是一 類重 要的 信息 表， 設(shè)s = ( u , a = c u d ) 是 一 個決 策 表， 其中c = ( c . . . c j為 條 件 屬 性 集】d= ( d , ， 一 ， 心) 為 決 策 屬 性集， 且 滿 足c ( ) d = 4 j 令c ( x ) 和d ( x ) 分 別 代表 u / c與 ui d中包含元素 x的等價類 ，則對任意的x e u導(dǎo)出 一 個決策規(guī)則c ( x ) , . . . , c ( x ) - d , ( x ) , . . . , d m ( x )( 簡記為c 一 二 d ) ，定義規(guī)則c - - ) ., d的支持度( s t r e n g t h ) 氏( c , d ) 為:久( c , d )_ 】 c ( x ) 門 d ( x ) i i ui定 義 規(guī) 則c - , d的 確定因 子( c e r t a i n t y f a c t o r ) c e r ( c , d ) 為 :c e r ( c , d ) =i c ( x ) 門 d ( x ) ii c ( x ) i氣( c d )t ( c (x ) )其中、 ( c ( x ) ) = c ( x ) i i uiir ., ( d i c ) ，f a c t o r ) c o v即c e r , ( c ,( c , d ) 為; 確定性因子又可以看作是當(dāng)y e c ( x ) 時y e d ( x ) 的條件概率d ) = n , ( d i c ) 。定義規(guī)則c - , d的覆蓋因子30 1 ( c o v e r a g ec o v , ( c d ) = c ( x ) 門 d ( x ) ii d ( x ) iv , ( c , d )n ( d ( x ) )- 州 -. -.一一- 一.一- 第6貞國防 科 學(xué) 技 術(shù) 大 學(xué) 研 究 生 院學(xué) 位 論文其中s ( d ( x ) ) _ d ( x ) i i ui類似有:c o v , ( c , d ) = 二 ， ( c i d ) 顯 然 ， 對 任 意 的 x e u 規(guī) 則c - , d 的 確 定 因 子c e r ( c , d ) 滿 足 : 0 _ c u , ( c , d ) _ 1 ， 如果決 策 表s = ( u , t 1 = c u d ) 使得 對 任意的x e u 有c e 以 c , d ) = 1 成 立， 即由 該 決 策 表產(chǎn)生的所有規(guī)則都是確定的，稱這樣的決策表為協(xié)調(diào)的，否則稱為不協(xié)調(diào)的。對于協(xié)調(diào)的決策表有p o s , ( d ) = u?？紤]決 策 系 統(tǒng)s = ( u , c , d ) , 設(shè) 有規(guī)則c - ) , d， 則如下 成立 【3 ( 1 .( 1 )藝y e 亡 ( s )( 2 )藝c e r , ( c , d )c e r , ( c , d ).d(x)- ( d ( x ) ) r ( c ( x ) ), . c( . )y e d( = )c e r ( c , d ) 二 ( c ( x ) )c o v y . ( c , d ) . z ( d ( y ) )v e c ( x )代 , ( c , d )= ，三 ，)c y (c , d )c e r ( c , d )c o v , ( c , d ) . ; r ( d ( x ) )c o v , ( c , d ) = 二 ( c ( x ) )c e r , ( c , d ) 二 ( c ( x ) )r ( d ( x ) )q , ( c , d ) r ( c ( x ) )氣( c , d )s ( d ( x ) )3)叼5)6)可以看到上面( 3 ),t質(zhì)都是基于 p a w l a kb x , y u有( 4 ) 式就是 通常的 全概率公 式， 而( 5 ) , ( 6 ) 式則是b a y e s 公式。 這些經(jīng)典粗糙集模型，論域上的等價關(guān)系起著至關(guān)重要的作用，即c ( x ) = c ( y ) 或c ( x ) ( ) c ( y ) = 0d ( x ) 二 d 。 ) 或d ( x 價d 妙) 二 0成立，這正是條件屬性和決策屬性所對應(yīng)的等價關(guān)系對論域劃分結(jié)果。在對不完備信息系統(tǒng)的直接處理方法中， 對 p a w l a k 經(jīng)典粗糙集模型的擴(kuò)充時采用更一般的二元關(guān)系來代替等價關(guān)系， 上面( 1 - 4 ) 式將變得非常復(fù)雜3 2 1 例 2 . 1 圖 2 . 1 左為一個數(shù)字顯示屏，其七個顯示區(qū)域分別用圖示字母表示，于是可以得到信息表 ( 圖2 . 1 右) ，其中論域為該顯示屏可以顯示所有數(shù)字 0 -9 ,屬性分別為七個顯示區(qū)域，屬性值 “ 1 ”表示該區(qū)域 “ 顯示” ，屬性值 ， 0 ”表示該區(qū)域 “ 不顯示”。 對信息表 ( 圖2 . 1 右) ，要利用屬性的取值將0 -9 區(qū)分開是否需要所有的屬性呢?很明 顯， 屬 性a , b , e , g 是必須的， 因為只有a 可以 區(qū) 分7 和1 ， 只有b 可以 區(qū)分6 和8 ,只有e 可以 區(qū) 分8 和9 只有， g 可以 區(qū) 分8 和。 ， 即( a , b , e , g 為 屬 性 集的 核， 然 而屬性a , b , e , g 仍不能 將2 和8 , 3 和9 區(qū)分， 恰好屬性f 可以 將2 和8 , 3 和9 區(qū)分， 這樣便得到屬性集的 一個約簡: ( a , b , 。 、 不g l ， 即 屬性。 、 d 冗余。 也 就是說， 如果實際中c ,d區(qū)域被遮擋或者損壞，并不會影響我們推斷出顯示屏所顯示的內(nèi)容。更進(jìn)一步，我們還可以 得到 如: 介0 且g =1 則 顯示為0 , a = 0 且 g = 0 則顯示為i , a = o 且g = 1 則 顯 示為4等規(guī)則。- -一一 -一一一 第7 0國 防 科 學(xué) 技 術(shù) 大 學(xué) 研 究 生 院 學(xué) 位 論 文圖2 . 1 顯示屏及其相應(yīng)的信息表 例2 . 2 表2 . 2 為對9 8 0 個駕駛案例的調(diào)查情況， 其中事件數(shù)目 就是同一類事件的所含案例個數(shù)。事件編號天氣情況道路情況行車時間事故情況事件數(shù)目薄霧大霧薄霧晴朗大霧薄霧有冰有冰無冰有冰有冰無冰白天夜晚夜晚白天夜晚夜晚發(fā)生發(fā)生發(fā)生沒有沒有沒有8 01 4 04 05 0 02 02 0 0 表2 .2 決策表實例 若把表2 . 2 看成一個決策表，其中條件屬性包括天氣情況、道路情況和行車時間，決策屬性為事故情況。于是可以得到規(guī)則 ( 表 2 . 3 ):規(guī)則確定因子覆蓋因子白天薄霧有冰，發(fā)生事故夜晚大霧有冰，發(fā)生事故夜晚薄霧無冰，發(fā)生事故白天晴朗有冰，沒有事故夜晚大霧有冰，沒有事故夜晚薄霧無冰，沒有事故支持度0 . 0 8 20 . 1 4 31 . 0 0 00. 8 7 7. 0 4 1 0 . 1 6 7j1 0 1 . 0 0 00 . 0 2 0u . 2 0 40 . 1 2 30 . 8 3 30 . 3 0 80 . 5 3 80 . 1 5 40 . 6 9 50 . 0 2 70 . 2 7 8表2 . 3 決策規(guī)則國 防 科 學(xué) 技 術(shù) 大 學(xué) 研 究 生 院 學(xué) 位 論 文第三章約簡的一種啟發(fā)式算法 信息表知識表達(dá)系統(tǒng)屬性的約簡蘊涵系統(tǒng)全部屬性的分類信息，相對約簡則是 滿足了相對正域不變更進(jìn)一步對屬性進(jìn)行約簡，所以信息系統(tǒng)的屬性的約簡和相對約簡至關(guān)重要， 尤 其是找出 所含屬 性最少的 約 簡 和相 對約 簡。 遺憾的 是 這都是n p 難題 3 3 ， 在應(yīng)用中需要借助啟發(fā)式算法來近似求解。本章通過揭示約簡在數(shù)量上的蘊涵的一個重要性質(zhì)，由此給出了又一種屬性重要性的定義及相應(yīng)的啟發(fā)式算法，并對算法進(jìn)行了 詳細(xì)的分析， 本章最后還類似地討論了相對約簡?；?3 . 1 約簡算法3 . 1 . 1基本理論 定 理3 . 1 . 1對信息系統(tǒng)s = ( u , a ) ， 若j u/ 川= n， 則 對任 意的a 的 非 空子 集b 有如下成立:ui b= ui a?！?ui b卜n 證明 : “ 二” : 顯 然 : “ ?！?: 不 妨 設(shè) u i a = u , ( i = 1, 2 , . - - , n ) , u i b = v . ( j = 1 , 2 ， 一 ， ， ) ，由 于 b c a ， 故 b 隊e u i a , 存 在牡 e u i b 使 得魷c 屹 ， 這 樣 ， 總 可 以 找 到稱 的 一 個 排列 使 u ; 二 ， 又 因 0 u ; 一 0 = u ， 于 是 可 得 u i 一 v ，即 u i b = u i a 。 推 論3 . 1 . 1對 信 息系 統(tǒng)s = ( u , a ) . rflu / a l = n， 則b 是a 的 最 小 約 簡 如 果b 滿足 : 1 )i u i b i = n 2 ) i b i= m in i b i ib 二 a , i u i b i= n 在借助啟發(fā)式算法求a的最小約簡時將不能保證所搜索得到子集的最小性，于是問題就 變成 如何 在c o r e ( a ) 的 基礎(chǔ)上 添加 盡可能 少的 屬 性a e a 一 c o r e ( a ) 來 達(dá)到a 的 分 類能力。這樣， 只要對a e a 一 c o r e ( a ) 定義一個重要性算子， 讓它們能夠以 某種順序加到c o r e ( a ) 上去， 那么便總可以 得到一個搜索的結(jié)果。雖然這個結(jié)果不一定是最小約簡， 甚至可能連約簡也不是，但只要定義的重要性算子合理，多項式時間內(nèi)大多數(shù)情況可以 得到較滿意的結(jié)果 3 4 ,2 3 .2 4 13 . 1 . 2算法對b ca ， 定義a e a 一 b 的重 要性 ( s i g n i f i c a n c e ) s g f , ( a ) :s g f b ( a 川 u i ( b v n 川一 u i b i-一 . 一一一一 一一 -. 第9 頁國防 科 學(xué) 技 術(shù) 大學(xué) 研 究生 院 學(xué) 位 論文二 二 二 二 二 二 二 二 二 二 二 二 二 二 二 二 如下給出啟發(fā)式搜索算法: 令b= c o r e ( a ) , ui a 二 n ， ( 1 )如果 u i b 卜n ， 轉(zhuǎn)到( 4 ) ，否則轉(zhuǎn)到( 2 ) : ( 2 )取a , 。 a i s g f b ( a ) = m a x , , ,_ s s g f b ( a ) ) : ( 3 ) : ( u / b gi u / b i + s g f b ( a , ) , b - b u a , ) ， 轉(zhuǎn)到( 1 ) : ( 4 ) : 輸出b。3 . 1 . 3算法分析 接下 來討 論算 法的 復(fù) 雜度b = c o r e ( a ) , u i a 卜n 。 令 u卜n , 川= m，即 u= ( u u 2 + + u n ) , a = a , , a 2 ， 一 ， a . )要 實 現(xiàn)u 的 劃 分 u i b , 顯 然 對 象u ; , u i e u 在 同 一 個b 等 價 類 中 當(dāng) 且 僅 當(dāng) : a k ( u i ) = a k ( u j )( v a k e b , k -l , 2 ， 一 ， i b )文 獻(xiàn) 4 給出了 一 種計 算單 個屬性的 分 類算法， 其在 最 壞 情況下的 時間 為: n ( n - 1 ) i 2 。求集 合b 對u 的 劃 分 u i b 不 同 的 只 是 我 們 在 檢 驗 當(dāng) 前 輸 入 對 象 u , 是 否 屬 于 某 個 類 認(rèn)時 要 看是否有: a k ( u , ) = a , ( 磯)( b a k “ b , k = 1 ， 2 , - 、 ! b i )顯 然 一 旦 出 現(xiàn)a k ( a t ) * a k ( 叭) k 引 b i ) 便 可 以 確 定 u , 0 認(rèn) ， 最 壞 的 情 況 就 是 我 們 每 一 次都 要 進(jìn)行 引次 計算， 從而得 到u i b 的時 間 為i 引-n ( n一 1 ) / 2 。 這即 為 上 述 算 法中 第 一次循環(huán)的第一步的時間。 算 法 第 二 步 實 際 上 就 是 找 到 使 得 在 原 來 分 類 基 礎(chǔ) 上 增 加 類 最 多 的 屬 性 之 一， 是 算 法 的核 心。 為了 詳 細(xì)說明 其實現(xiàn)， 這里討 論連續(xù)的 兩次 循環(huán) 過程， 分別以1 , 1 1 記， 令u i b , 二 以1， 認(rèn) 2 ， . . . u q u l b ,j 卜于 是 屬 性a ,k e a - 共 對 分 類 的 影 響 時 只 需 要 考 慮a , * 分 別 在 每個 等 價 類u , e u i b , ， ( j = 1 , 2 , . . .， i u i b , 1 ) 上 的 劃 分 即 可， 這 正 是 上 面 提 到 的 單 個 屬 性 分類的問題，這樣:s g 瓦( a lk ) 二，u /b ,e( i u , l a , 1 - 1) 一e= t一 ju ,j l a ,k 一 u i b , i在下一次循環(huán)中考慮屬性a tt k e a 一 風(fēng) ， ，影響時只 需 要考 慮該 屬 性分 別 在u i b=ul a i 。 為 “( b it = b , v (a t b ，k = 1 , 2 , ， 二 ， i a 一 b u 1) 對 分 類 的u u , 1l 口 ， ， 中 每 個 等 價 類 土 的 劃 分 。 同 樣 ， 令u . u 7 8 ,u n ; k t ， 認(rèn) lj k 2 , * ， u t ,k lu ,i 。 .。 .國 防 科 學(xué) 技 術(shù) 大 學(xué) 研 究 生 院 學(xué) 位 論 文如果步驟i 中添加的屬性a llk a 一 b ,， 有u ii /k ， l a llka l , = a lk, 使 得i u ,j l a , , . 1= 1 ， 即 u ii)k ， = u ,= u l , i a ll k 由 于那么對任意的a l l k a 一 b ( z a 一 b ,故u ii ;k , i l a ll k - u i j l a il k 就 不 必 重 復(fù) 計 算了 。考 慮 最 壞的清 況， 記: u i b = u , ( j = 1 , 2 ， 一 ， j u i b i ) ， 計 算 一 個 屬 性 重要 性的 時 間r j ) b i i叭1 - ,藝 = n ( n 一 1 ) / 2 一藝同這樣的工作在一次循環(huán)中需要進(jìn)行的次數(shù)為i a - c o r e 洲) - m次， 這樣得到總的時間為: a 一 b ,r : 顯然; + p 21 fi一 告 ，號 ，尋 2 0 /1 2 1 + 1 0 p 4 1 + 1 0且有:產(chǎn)引=( 2 0 p 2 1 + l o iu 4 1 + 1 0 ) + ( 2 0 /1 2, + 1 0 p 42 + 3 0 ) 2 0 產(chǎn) 2 2 + ( ) 產(chǎn) 4 2 + 3 0( 2 0 ,u 2 1 + 1 0 ,u , , + 1 0 ) + ( 2 0 p , + 1 0 # , 2 + 3 0 ) 2 0 # 2 , + 1 0 # 4 , + 1 0( 2 0 # 2 , + 1 0 # 4 1 + 1 0 ) + ( 2 0 # 22 + 1 0 ,u 4 2 + 3 0 ) + ( 1 o p 4 3 + 3 0 ) 1 0 # 2 2 + 1 0 # 4 2 + 3 0( 2 0 # 2 , + 1 0 1u 4 , + 1 0 ) + ( 2 0 # 22 + 1 0 # 4 2 + 3 0 ) + ( 1 o p 4 3 + 3 0 ) 1 0 # 4 3 + 3 0( 2 0 # 2 , + 1 0 # n , + 1 0 ) + ( 2 0 # 2 2 + 1 0 # 4 2 + 3 0 ) + ( 1 o p 4 3 + 3 0 )解得二 # 2 , = 1 / 4 ，f h 2 = 3 / 4 ,從 ， = 1 /