（計算機軟件與理論專業(yè)論文）基于粗糙集的啟發(fā)式屬性約簡與規(guī)則提取研究.pdf

摘要 粗糙集理論是一種新的刻畫不完整性和不確定性的數(shù)學工具。知識約簡是粗糙集理 論研究的核心問題之一。目前，粗糙集理論正在被廣泛應用于人工智能、模式識別等很 多領域。本文對屬性約簡與決策樹規(guī)則簡化進行了深入研究： 針對不一致決策表，為克服區(qū)分矩陣方法時間復雜度隨系統(tǒng)大小增加而指數(shù)增氏的 缺陷，以知識的包含度為基礎，將一致與不一致對象分開，給出分布約簡的數(shù)學判定定 理，設計了一種求分布約簡的啟發(fā)式算法。實踐表明該方法能夠獲取較小的約簡。 為彌補現(xiàn)有信息論方法的局限性，定義了一種新的條件熵概念，并且給出了以不等 式為條件的約簡判定定理，提出了一種相對屬性約簡的啟發(fā)式算法。實例分析的結果表 明，該方法提高了運行效率，有助于搜索最小或次優(yōu)知識約簡?；谏厦娴乃枷胗痔岢?r 基于決策熵的約簡算法，實驗結果表明該算法也能取得較好的效果。 分析了基于正區(qū)域方法的不足，提出了決策強度的代數(shù)定義，并證明了知識的決策 強度隨信息粒度變小而非單調(diào)遞減的規(guī)律，設計了基于決策強度的約簡算法。u c i 離散 數(shù)據(jù)集實驗比較的結果表明，該算法計算直觀有效。 針對現(xiàn)有值約簡算法提取規(guī)則仍存在冗余與計算復雜度較大等問題，引入決策樹分 類規(guī)則學習方法，定義了一種能反映決策能力實質(zhì)的新的條件熵，對傳統(tǒng)啟發(fā)式方法中 選擇屬性的標準進行改進，構造決策樹，設計規(guī)則約簡過程。該方法的優(yōu)點在于構造決 策樹與提取規(guī)則之前不進行屬性約簡，也能獲取簡潔有效的規(guī)則。為彌補知識粗糙熵的 局限性，提出決策熵概念，以條件屬性子集的決策熵來度量其對決策分類的重要性，自 頂向下遞歸構造決策樹，簡化規(guī)則。通過實例分析說明了該算法的有效性。 關鍵詞：粗糙集，決策表，屬性約簡，規(guī)則提取，決策樹 a b s t r a c t r o u g hs e t st h e o r y , i n t r o d u c e db yz ，p a w l a k ，i san e wm a t h e m a t i c a lt o o lt od e a lw i t hv a g u e n e s sa n d u n c e r t a i n t y k n o w l e d g er e d u c t i o n i so n eo f t h em a i nt o p i c si nt h es t u d yo fr o u g hs e t st h e o r yi th a sr e c e i v e d m u c ha t t e n t i o no f t h er e s e a r c h e r sa r o u n dt h ew o r l d a tp r e s e n t ，r o u g hs e t st h e o r yh a sb e e na p p l i e dt om a n y a r e a s s u c c e s s f u l l yi n c l u d i n ga r t i f i c i a li n t e l l i g e n c e ，p a t t e r nr e c o g n i t i o n a n ds oo n t h er e s e a r c ha n d i n n o v a t i v er e s u l t sa r ef o c u s e do na t t r i b u t er e d u c t i o na n dr u l e se x t r a c t i o no fd e c i s i o nt r e ea sf o l l o w s i ni n c o n s i s t e n td e c i s i o nt a b l e ，t oo v e r c o m et h ed i s a d v a n t a g eo fo r d e r e dr e d u c t i o nw h i c hi sb a s e do n t h ed i s c e r n i b i l i t ym a t r i xa st h et e m p o r a lc o m p l e x i t yi si n c r e s c e n te x p o n e n t i a la l o n gw i t ht h es i z eo f d e c i s i o nt a b l e s ，an e ws i g n i f i c a n c eo f a t t r i b u t ei sd e f i n e d ，w h i c hi so nt h eb a s i so f t h ei n c l u s i o nd e g r e ew i t h s e p a r a t i n gc o n s i s t e n to b j e c t sf o r mi n c o n s i s t e n to b j e c t s ，s ot h ej u d g m e n tt h e o r e m w i t hr e s p e c tt od i s t r i b u t i o n r e d u c t i o ni so b t a i n e d ，a n dah e u r i s t i ca l g o r i t h mi sp r o p o s e d f i n a l l y , t h ee x p e r i m e n t a la n a l y s i so ft h i s a l g o r i t h ms h o w st h a ti tc a no b t a i nm e a n i n g f u la n ds m a l lr e l a t i v er e d u c t i o n t oe l i m i n a t et h el i m i t a t i o n so ft h ec u r r e n tc o n d i t i o n a le n g o p y , an e wc o n d i t i o n a le n t r o p yi sd e f i n e d w i t hs e p a r a t i n gc o n s i s t e n to b j e c t sf o r mi n c o n s i s t e n to b j e c t s ，a n dt h ej u d g m e n tt h e o r e mw i t hr e s p e c tt o k n o w l e d g er e d u c t i o ni so b t a i n e df r o mi n e q u a l i t y ah e u r i s t i ca l g o r i t h mi sp r o p o s e d t h ee x a m p l ei sg i v e n a n dt h ea n a l y s e ss h o wt h a tt h ep r o p o s e dh e u r i s t i ci n f o r m a t i o ni sb e t t e ra n dm o r ee f f i c i e n tt h a nt h eo t h e r s ， a n dt h em e t h o dh e r er e d u c e st h et e m p o r a lc o m p l e x i t ya n di m p r o v e st h eo p e r a t i n ge f f i c i e n c y e x p e r i m e n t a l r e s u l t sp r o v et h ev a l i d i t yo ft h i sr e d u c t i o nm e t h o di ns e a r c h i n gt h em i n i m a lo ro p t i m a lr e d u c t i o n s oi t e n l a r g e st h ea p p l i c a t i o na r e ao fr o u g hs e t st h e o r y b a s e do nt h ef o r em e n t i o n e di d e a l ，an e wr e d u c t i o n a l g o r i t h ma b o u td e c i s i o ni n f o r m a t i o ne n t r o p yi sp r o p o s e d t h ee x p e r i m e n t a lr e s u l ts h o w st h a tt h i sm e t h o d i sv e r ye f f e c t i v ea n du s e f u l t oe l i m i n a t et h ed i s a d v a n t a g e so f c l a s s i c a lr o u g hr e d u c t i o na l g o r i t h m sb a s e do np o s i t i v er e g i o n ，an e w d e c i s i o np o w e rd e f i n i t i o no fa l g e b r ai sp r o p o s e d ，a n dt h en e ws i g n i f i c a n c eo fa na t t r i b u t ei sd e f i n e d t h e c o n c l u s i o nt h a td e c i s i o np o w e ro fk n o w l e d g ed e c r e a s e sn o n - m o n o t o n o u s l ya st h ei n f o r m a t i o ng r a n u l a r i t i e s b e c o m ef i n e ri so b t a i n e d ，a n dah e u r i s t i ca l g o r i t h mi sp r o p o s e d f i n a l l y , t h er e d u c t i o nc o m p a r i s o nr e s u l t so f u c ld i s c r e t ed a t a b a s e su s i n gf o u ra l g o r i t h m ss h o wt h a ti ti sd i r e c ta n dp r a c t i c a l t or e m e d ys o m ed e f i c i e n c i e so f t h ec u r r e n tv a l u er e d u c t i o na l g o r i t h m sw i t ha t t r i b u t er e d u n d a n c y , r u l e s i i r e d u n d a n c y , a n dl a r g ec o m p u t a t i o n a lc o m p l e x i t y , t h el a t e s td e c i s i o nt r e ec l a s s i f i c a t i o nr u l em e t h o di s i n t r o d u c e d ，a n dan e w h e u d s t i cf u n c t i o nt ob u i l dd e c i s i o nt r e e si sp r o p o s e dt oe x t r a c td e c i s i o nr u l e s t om a k eu pt h es h o r t c o m i n go ft h ec u l t e n ti n f o r m a t i o ne n t r o p yf o re m i m a f i n gd e c i s i o na b i l i t y , an e w c o n d i t i o n a le n t r o p yi sd e f i n e d ，a n dt h ea t t r i b u t es e l e c t i o nm e t r i co ft r a d i t i o n a lh e u r i s t i ca l g o r i t h mi s m o d i f i e d ，s ot h en e wi m p r o v e ds i g n i f i c a n c eo fa na t t r i b u t ei sp r o p o s e d f i n a l l y ，ah e u r i s t i ca l g o r i t h mf o r r u l e se x t r a c t i o no fd e c i s i o nt r e ei sd e s i g n e d t h eb e n e f i to ft h i sr e d u c t i o nm e t h o di st h a ti tn e e d n ta t t r i b u t e r e d u c t i o nb e f o r ee x t r a c t i n gd e c i s i o nr u l e s t h ee x p e r i m e n ta n dc o m p a r i s o ns h o wt h a tt h ea l g o r i t h m p r o v i d e sm o r ep r e c i s ea n ds i m p l ed e c i s i o nr u l e s o nt h eb a s eo ft h ef o r em e n t i o n e di d e a l ，an e w d e c i s i o n i n f o r m a t i o ne n t r o p yi sp r o p o s e d i nt h ep r o c e s so f d e c i s i o nt r e eb u i l d i n gs t e pb ys t e ph o t t o m - u p ，c o n d i t i o n a t t r i b u t e sa r ec o n s i d e r e dt oe s t i m a t et h es i g n i f i c a n c ef o rd e c i s i o nc l a s s e s ap r o c e d u r ef o rr e d u c t i o no f t r a v e r s i n gd e c i s i o nr u l e si sa l s oc o n s t r u c t e d ，a n dh e l p st og e tm o r ep r e c i s er u l e s k e yw o r d s tr o u g hs e t s ，d e c i s i o nt a b l e ，a t t r i b u t er e d u c t i o n ，r u l e se x t r a c t i o n ，d e c i s i o nt r e e i i i 獨創(chuàng)性聲明與論文使用授權說明 獨創(chuàng)性聲明 本人鄭重聲明：所呈交的學位論文是我個人在導師指導下進行的研究 工作及取得的研究成果。盡我所知，除了文中特別加以標注和致謝的地方 外，論文中不包含其他人已經(jīng)發(fā)表或撰寫的研究成果，也不包含為獲得河 南師范大學或其他教育機構的學位或證書所使用過的材料。與我一同工作 的同志對本研究所做的任何貢獻均已在論文中作了明確的說明并表示了謝 意。 簽名么乏直二幺a ! 日期：盈12 ：笸： 蘭 關于論文使用授權的說明 本人完全了解河南師范大學有關保留、使用學位論文的規(guī)定，即：有 權保留并向國家有關部門或機構送交論文的復印件和磁盤，允許論文被查 閱和借閱。本人授權河南師范大學可以將學位論文的全部或部分內(nèi)容編入 有關數(shù)據(jù)庫進行檢索，可以采用影印、縮印或掃描等復制手段保存、匯編 學位論文。( 保密的學位論文在解密后適用本授權書) b、 簽名：石臼二魅 導師簽名： 壘歪絲! 至日期：叢翌z ：! ：坐 第一章緒論 第一章緒論 1 1 研究的目的與意義 由于計算機科學與技術的發(fā)展，特別是計算機網(wǎng)絡的發(fā)展，每時每日都為人們提供 了大量的信息，一方面人們可以從中獲取更多更有用的知識，另一方面，也使大量知識 掩蓋在海量信息之中，人們不易從中辨析。在這種矛盾中，智能信息處理成為當前信息 科學理論與應用領域中一個嶄新的研究熱點。特別是最近2 0 年間，人們在專家系統(tǒng)、 知識工程、人工神經(jīng)網(wǎng)絡、模糊集等領域不斷實踐與探索，取得了很多很好的成績。隨 著數(shù)據(jù)庫技術的不斷發(fā)展及數(shù)據(jù)庫管理系統(tǒng)的廣泛應用，數(shù)據(jù)庫中存儲的數(shù)據(jù)量急劇增 大，然而，人們處理與分析數(shù)據(jù)的能力卻是相當有限的。如何從大量的、雜亂無章的、 強干擾的數(shù)據(jù)( 海量數(shù)據(jù)) 中挖掘潛在的有利用價值的信息( 知識) ，是人類的智能信 息處理能力面臨的前所未有的挑戰(zhàn)，與此同時數(shù)據(jù)庫知識發(fā)現(xiàn)( k n o w l e d g ed i s c o v e r yi n d a t a b a s e , k d d ) 技術應運而生。目前，知識發(fā)現(xiàn)( 知識約簡、規(guī)則提取、數(shù)據(jù)挖掘、 機器學習) 受到人工智能( a r t i f i c i a li n t e l l i g e n c e ，a i ) 學界的廣泛重視，如何高效地處理 分布、實時海量數(shù)據(jù)成為當前知識發(fā)現(xiàn)中各種不同方法的研究熱點，其中粗糙集方法是 主要方法之一。 1 9 6 5 年，當美國控制論專家l a z a d e h 1 】提出模糊( 用英文詞f u z z y 翻譯德文v a g u e ) 集的概念后，不少計算機科學家和邏輯學家試圖依此概念來解決1 9 0 4 年謂詞創(chuàng)始人 g f r e g e 提出的含糊( 德文v a g u e ) 概念問題，但遺憾的是模糊集理論是不可計算的，即 模糊集沒有給出數(shù)學公式描述這一含糊概念，因此無法計算出其中包含的含糊元素數(shù) 目。1 9 8 2 年，波蘭科學家z p a w l a k 針對g f r e g e 的邊界線區(qū)域思想提出粗糙( r o u g h 是 波蘭人對v a g u e 的翻譯) 集理論 2 1 ，粗糙集有確定的數(shù)學公式來描述含糊概念，它認為 邊界線區(qū)域是上近似集與下近似集之間的差集，無法確認的個體都歸屬于邊界線區(qū)域， 而上近似集與下近似集都可以通過等價關系給出確定的數(shù)學公式描述，所以含糊元素數(shù) 目可以被計算出來，即在真假二值之間的含糊程度可以計算，從而實現(xiàn)了g f r e g e 的邊 界線思想。 本研究得到河南省自然科學基金項目( 0 5 1 1 0 1 1 5 0 0 ) 和河南省高校新世紀優(yōu)秀人才支持計劃( 2 0 響珊唧】9 ) 資助。 第一章緒論 粗糙集理論是建立在分類機制的基礎上的，它將分類理解為在特定空間上的等價關 系，而等價關系構成了對該空間的劃分1 3 1 。其將知識理解為對數(shù)據(jù)的劃分，每一被劃分 的集合稱為概念，并從新的角度認識知識，認為概念的不精確性是由知識的粒度過粗引 起的。粗糙集理論認為知識即是將對象進行分類的能力，假定全域里的元素具有必要的 信息或知識，通過這些知識能夠?qū)⑵鋭澐值讲煌念悇e；若對兩個對象具有相同的信息， 則它們就是不可區(qū)分的( 即根據(jù)已有的信息不能夠?qū)⑵鋭澐珠_) ，顯然這是一種等價關 系1 4 】。不可區(qū)分關系是粗糙集理論最基本的概念，在此基礎上引入了成員關系、上近似 與下近似等概念來刻畫不精確性與模糊性，使得粗糙集理論能夠有效地逼近這些概念。 粗糙集理論的主要思想是利用已知的知識庫，將不精確或不確定的知識用已知知識 庫中的知識來近似刻畫【5 】。其要點是將分類與知識聯(lián)系在一起，作為一種數(shù)學理論，它 使用等價關系來形式化地表示分類，這樣，知識就可以理解為使用等價關系集對離散表 示的空間進行劃分，即知識就是等價關系集對空間劃分的結果嘲。粗糙集理論的主要興 趣在于它恰好反映了人們用粗糙集方法處理不分明問題的常規(guī)性，即以不完全信息或知 識去處理一些不分明現(xiàn)象的能力，或依據(jù)觀察、度量到的某些不確定結果進行分類數(shù)據(jù) 的能力【4 】。并能對不完整數(shù)據(jù)進行分析、推理，發(fā)現(xiàn)數(shù)據(jù)間的關系，提取有用的特征， 簡化信息處理，進而研究不精確、不確定知識的表達、學習與歸納等。 粗糙集理論作為一種新的處理不精確、不確定與不完全數(shù)據(jù)的數(shù)學方法，與其他處 理不確定與不精確問題理論最顯著的區(qū)別是它無需提供問題所需處理的數(shù)據(jù)集合之外 的任何先驗信息，所以可以說對問題不確定性的描述或處理是比較客觀的。由于該理論 未能包含處理不精確或不確定原始數(shù)據(jù)的機制，其與概率論、模糊數(shù)學及證據(jù)理論等處 理不確定或不精確問題的理論有很強的互補性。由于它在機器學習與知識發(fā)現(xiàn)、數(shù)據(jù)挖 掘、決策支持與分析、專家系統(tǒng)、歸納推理、模式識別等方面的廣泛應用，現(xiàn)已成為一 個熱門的研究領塒6 】。 粗糙集理論似乎特別適合于數(shù)據(jù)簡化、數(shù)據(jù)近似分類和數(shù)據(jù)相關性、數(shù)據(jù)意義、數(shù) 據(jù)相似或差別及數(shù)據(jù)模式的發(fā)現(xiàn)等 7 1 。粗糙集理論是對信息進行分析推理、發(fā)現(xiàn)數(shù)據(jù)間 關系，提取特征、進行知識約簡的有力工具。所以，研究粗糙集理論在知識發(fā)現(xiàn)中的應 用，將會大大促進知識發(fā)現(xiàn)技術的進步，該研究有著廣闊的發(fā)展前景。而經(jīng)典的屬性約 簡定義對噪聲數(shù)據(jù)的抗干擾能力十分薄弱，往往導致提取的規(guī)則集丟失許多有用的信 息：且目前多數(shù)學者都將精力集中在屬性約簡算法的提出和改進上，但屬性值約簡也是 2 第一章緒論 決策規(guī)則挖掘過程中的關鍵步驟。因此，尋求快速的值約簡算法可以盡快地獲取最小決 壤規(guī)則集，以馕鑫效地斂出毫疆量的決策。離效漿羼性縫筠與嫂雯哇提取技本是糧糙集瓔 論應用予知識發(fā)現(xiàn)領域的基礎，也是當前粗糙集理論研究的主簧方向。 終冀一耱耨戇智襞計算方法，翟糙集理論懣在誨多瓣學與誓程頒域孛霉到了廣泛戇 應用，其中屬性約簡與決策規(guī)則提取技術仍是粗糙集理論研究的核心內(nèi)容，也是河南省 鑫然科學基金磺目磷究酌一部分內(nèi)容。 l 。2 糕糙集理論研究的歷史與現(xiàn)狀 2 0 世紀7 0 年代初，波蘭學稽z p a w l a k 和波蘭科學院、華沙大學的邏輯家們組成了 研究小綴，對信息系統(tǒng)邏輯特餓進行了長期的熬礎性研究。德們針對秩實驗中得到的班 數(shù)據(jù)形式表述的不精確蠛、不確定性和不完整牲的信息與知識，進行了分類分柝，為糖 糙集理論的產(chǎn)生奠定了基礎。到了8 0 年代，糨糙集理論引起了各國學術界的熏視，許 多數(shù)學家、邏驥學家與詩冀壤磺突人員懟齷糙集理論及其應用產(chǎn)生了極大興趣，蒡進露 了廣泛深入的研究。 致1 9 9 2 年至今，繇年郝秘秀菇鼗禳集為圭蘧豹謦際會議，箍動了程糙集理論熬強 展與應用。國際上成立了粗糙黛學術研究會，參加的成員來自波蘭、美國、加拿大、日 本、挪威、俄羅斯、烏克蘭與印度等國家弼。秘蘺，藕糙集理論己成為入工智能領域巾 一個較新的學術熱點，引起了越來越多的科研人員的關注。在國內(nèi)也成囊了“中國r o u g h 榘與軟計算學米研討會( c r s s c ) ”，從2 0 0 1 年至今融經(jīng)連續(xù)召開六屆“r o u g h 集島 軟詩算拳術磅討會”。隨著c r s s c 系歹# 磅 重會在規(guī)模與質(zhì)量上均呈良好鮑增長趨勢， 此領域的研究工作發(fā)展也很快。2 0 0 3 年成立了中國人工智能學會粗糙黛與軟計算專業(yè)委 覆會，耀耱集聯(lián)論戇磷究獲基雯秀器輊大，醭究戲采在深度與廣發(fā)上旁了更大懿發(fā)震。 下麗給出粗糙集理論研究的歷史與現(xiàn)狀大搴記： 1 9 9 1 年，z p a w l a k 教授密敝了第一本關予穰糙集豹專著 3 1 ，成為耩糙集邋論研究的 第一個羼程碑，奠定了粗糙集理論的基礎。 1 9 9 2 年，i l s l o w i n s k i 主編豹關予租糙集威用及其與相關方法眈較研究的論文集出 版【9 1 ，對這一時期的工根成果饞了很好的總結，推動了國際上對粗糙集理論與應用領域 的深入研究，掀起了研究粗糙集理論的高潮。 在囂際上，1 9 9 2 冬波蘭k i e k r z 瑤努了第一藩國黲凝糙集學零磋討會，這次會議麓 3 第一章緒論 重討論了集合近似定義的基本思想及其應用。 1 9 9 3 年，在加拿大b 齜昭開了第二屆國際粗糙集與知識發(fā)現(xiàn)研討會。這次會議的主 題是粗糙集、模糊集與知識發(fā)現(xiàn)。這次會議積極推動了國際上對粗糙集理論與應用的研 究。由于當時正值數(shù)據(jù)庫知識發(fā)現(xiàn)成為研究的熱門話題，一些著名知識發(fā)現(xiàn)學者參加了 這次會議，并且介紹了許多擴展粗糙集理論的知識發(fā)現(xiàn)方法與系統(tǒng)。 1 9 9 4 年，在美國s a n j o s e 召開了第三屆國際粗糙集與軟計算研討會，這次會議主要 探討了粗糙集與模糊邏輯、神經(jīng)網(wǎng)絡、進化理論等的融合問題。 1 9 9 5 年，z p a w l a k 等在c o m m u n i c a t i o n so f t h ea c m 上發(fā)表了“r o u g hs e t s ”i 塒， 文章概括性介紹了作為目前人工智能應用新技術之一的粗糙集理論的基本概念以及它 在知識獲取、機器學習、決策分析和知識發(fā)現(xiàn)等領域的具體研究項目和進展。 1 9 9 5 年，a c mc o m m u n i c a t i o n s 將粗糙集列為新浮現(xiàn)的計算機科學的研究課題。 1 9 9 5 年，在美國w i l m i n g t o n 召開了第四屆國際粗糙集研討會，在這次會議上，對 粗糙集合與軟計算方法的基本觀點與關系展開了激烈的探討。 1 9 9 6 年，在日本東京召開了第五屆國際粗糙集研討會，這次會議推動了亞洲地區(qū)對 粗糙集理論與應用的研究。 1 9 9 8 年，國際信息科學雜志( i n t e r n a t i o n a lj o u m a lo f i n f o r m a t i o ns c i e n c e s ) 為粗糙集 理論的研究出了一期專輯。 1 9 9 8 年，在波蘭召開了第一屆國際粗糙集與計算的當前趨勢學術會議。 1 9 9 9 年，在日本召開了第七屆國際粗糙集、模糊集，數(shù)據(jù)挖掘和粒度一軟計算會 議，主要闡述了當前粗糙集、模糊集的研究現(xiàn)狀與發(fā)展趨勢。 2 0 0 0 年，在加拿大召開了第二屆國際粗糙集與計算的當前趨勢學術會議。 2 0 0 3 年，在重慶郵電大學召開了第九屆國際粗糙集、模糊集、數(shù)據(jù)挖掘與粒計算學 術會議。 2 0 0 4 年，國際粗糙集協(xié)會主辦的第一本租糙集國際期刊( a d v a n c e si n r o u g hs e t s ) 出版發(fā)行。 2 0 0 4 年，在瑞典召開了第四屆國際粗糙集與計算的當前趨勢學術會議。 2 0 0 5 年，在加拿大召開了第十屆國際粗糙集、模糊集、數(shù)據(jù)挖掘與粒計算學術會議。 2 0 0 6 年，在美國g e o r g i as t a t eu n i v e r s i t y 召開了第二屆粒計算國際會議。 2 0 0 6 年，在日本k o b e 召開了第五屆國際粗糙集與計算的當前趨勢學術會議。 4 第一章緒論 波蘭華沙大學、工業(yè)大學、信息技術與管理大學和加拿大r e g i n a 大學、圣瑪麗大學 以及英 雪e d i n b u r g h 大學、u l s t e r ：r 學、c a r d i f f 大學等對粗糙集理論都有深入的研究。 在國內(nèi)，2 0 0 1 年重慶郵電大學召開了第一屆中國r o u g h 集與軟計算學術研討會， 以便國內(nèi)學者共同理解和探討粗糙集理論及應用研究的新內(nèi)容與新方法，推動了粗糙集 理論及其應用在國內(nèi)的研究與發(fā)展。 2 0 0 2 年，在蘇州大學召開了第二屆中國r o u g h 集與軟計算學術研討會。 2 0 0 3 年，在重慶郵電大學召開了第三屆中國r o u g h 集與軟計算學術研討會。 2 0 0 4 年，在浙江海洋學院召開了第四屆中國r o u g h 集與軟計算學術研討會。 2 0 0 5 年，在清華大學召開了第一屆粒計算國際會議。 2 0 0 5 年，在鞍山科技大學召開了第五屆中國r o u g h 集與軟計算學術研討會。 2 0 0 6 年，在浙江師范大學召開了第六屆中國r o u g h 集與軟計算學術研討會。 2 0 0 6 年，在南昌大學召開了r o u g h 集前景粒計算理論國際論壇。 2 0 0 6 年，在重慶郵電大學召開了第一屆粗糙集與知識技術國際會議。 2 0 0 7 年，擬定在山西大學召開第七屆中國r o u g h 集與軟計算學術會議，第一屆中 國w e b 智能學術研討會和第一屆中國粒計算學術研討會。 目前，仍有許多重要的國際國內(nèi)學術會議繼續(xù)把粗糙集理論研究列入主要內(nèi)容之 一。在中國幾乎所有重要的計算機學術期刊均刊登有粗糙集理論的學術論文。從研究地 域來看，歐洲學者比較注重理論研究，北美學者比較注重應用，日本學者在粗糙集與概 率論相結合以及在醫(yī)學的應用方面比較突出，國內(nèi)在知識約簡、與信息論結合、粗糙邏 輯、粒計算、知識的不確定性研究方面取得了較大的成果。對粗糙集理論的知識表示與 處理不確定性問題數(shù)學方法的關系，近年來國內(nèi)的研究也發(fā)展迅速，出現(xiàn)很多綜述性報 告及中文著作 4 - g , l l - l g 。粗糙集理論已成為當前信息科學最為活躍的研究領域之一。 粗糙集理論經(jīng)過國內(nèi)外眾多研究人員2 0 多年的共同努力，不但為信息科學和認知 科學提供了新的科學邏輯與研究方法，還為智能決策提供了有效的處理技術。作為一種 新的知識發(fā)現(xiàn)方法，粗糙集理論不僅在數(shù)學理論上不斷得到完善，而且在其它研究領域 中也得到了成功的應用 3 5 - 2 3 ，如機器學習、決策分析、近似推理、圖象處理、醫(yī)療診斷、 金融數(shù)據(jù)分析、專家系統(tǒng)、沖突分析、過程控制和數(shù)據(jù)庫知識發(fā)現(xiàn)等領域。目前，粗糙 集理論自身已成為完整、獨立的科學領域。粗糙集理論模型也得到不斷的完善和發(fā)展， 并逐漸滲透到很多學科。此外，粗糙集理論與其他軟計算理論形成了共同發(fā)展和優(yōu)勢互 篁= ：童矍笙 補的局面，諸如與f u z z y 集、d y n a m i cf u z z y 集、粒計算、遺傳算法、神經(jīng)網(wǎng)絡等軟計 簇理論粥3 0 l ，已經(jīng)成為巍茛國內(nèi)終詩箕壤及楣關專業(yè)的疆究熱焱。國內(nèi)終學者魄公認穩(wěn) 糙集理論是研究數(shù)據(jù)挖掘、知識約簡與粒計算的理論基礎。 1 3 藕糙集理論的優(yōu)點與特點 采耀耀糙爨疆論終雋疆究煞識發(fā)璇王其其竅專年多錢熹嘲： ( 1 ) 粗糙集理論包括了知識的一種形式模理，這種模型將知識定義為不w 區(qū)分關 系豹一個族集，遮贛使知識其鴦了一耱院較清辯的數(shù)學意義，勢且稷方梗瑁數(shù)學方法來 分析處理。 ( 2 ) 粗糙集理論在數(shù)學上非常嚴密，有套處理數(shù)據(jù)分類問題的數(shù)學方法，尤其 楚當數(shù)據(jù)具有噪聲干擾、不完全性或不糖確性時。 ( 3 ) 粗糙熊僅僅分析隱藏在數(shù)據(jù)中的事實，沒有校正數(shù)據(jù)中所表現(xiàn)的不一致性， 一般只將瘊生戲驗援烈分為確定與不確定載烈。 ( 4 ) 粗糙集理論的實用性非常強，它是為開發(fā)自動規(guī)則嫩成系統(tǒng)而提出的，因而 它豹臻究完全楚應躉靜鞭動。 ( s ) 基于粗糙集的計算方法非常邋合于并行處理，粗糙集計算機的研制工作已在 進行之中，并取得了一定成果。 ( 6 ) 粗糙集理論與模糊邏輯、神經(jīng)網(wǎng)絡、概率推理、信度照絡、連接計算、遺傳 算法、溉沌理論一起形成了軟計算方法的基礎，為問題的處理提供了魯棒性強、成本較 低的鷦次方寨。 粗糙集理論具有很多自己的特點酆n ，歸納如下； 1 ) 甏穗集苓霉簧經(jīng)囂辮攘售惑絨先驗懿鎮(zhèn)。摸凝集與概率統(tǒng)謗方法都楚處瑾零 確定信息時常用的方法，但這些方法需蒙一些數(shù)據(jù)的附加信息或先驗知識，如模糊隸屬 函數(shù)、穰率分露等，這藏信愨鴦囂季并不容易得翔。褪糙集分拆方法莰弱靂數(shù)據(jù)本身提供 的信息，無須任何先驗知識，這是和模糊理論及證據(jù)理論最主疆的區(qū)別。 ( 2 ) 粗糙集是一個強大的數(shù)據(jù)分析工具。它能表達和處理不完備信息，熊在保留 關鍵信惑的前提下對數(shù)據(jù)進行化簡并求得知識煦最小表達，能識別并詳估數(shù)據(jù)之間的依 賴關系，揭示出概念的簡單模式，并能從經(jīng)驗數(shù)據(jù)中獲取易于證實的規(guī)則知識，特別邋 會手磐熊控割， 6 第一章緒論 ( 3 ) 粗糙集與模糊集分別刻畫了不完備信息的兩個方面。粗糙集以不可區(qū)分關系 為基礎，側重分類，模糊集基于元素對集合隸屬程度的不同，強調(diào)集合本身的含混性 ( v a g u e n e s s ) 。從粗糙集的觀點看，粗糙集合不能清晰定義的原因是缺乏足夠的論域知 識，但可以用一對清晰集合逼近。文獻【2 4 】闡述了粗糙集與模糊集的內(nèi)在聯(lián)系及模糊粗 糙集( f u z z y - r o u g hs e t ) 的概念。粗糙集與證據(jù)理論也有一些相互交疊之處，在實際應 用中可以相互補充。 粗糙集理論所具有的獨特分析視角不僅可以克服傳統(tǒng)不確定性處理方法的不足，而 且與其它分析方法有機結合，有望進一步增強對不確定問題的處理能力。粗糙集理論對 于人工智能與認知科學是十分重要的，自提出以來一直受到模糊數(shù)學創(chuàng)始人l a z a d c h 的重視，并給與很高的評價。近年來，粗糙集理論憑借自己獨特的優(yōu)勢，開始逐漸應用 到知識發(fā)現(xiàn)的各個領域中，在對大型數(shù)據(jù)庫中不完整數(shù)據(jù)進行分析學習方面具有廣泛的 應用前景及實用價值。粗糙集理論不僅為信息科學與認知科學提供了新的科學邏輯和研 究方法，而且為智能信息處理提供了有效的處理技術。 1 4 粗糙集理論的研究方向 1 4 1 粗糙集理論的理論研究 目前，粗糙集在知識發(fā)現(xiàn)中的理論研究主要集中在數(shù)學性質(zhì)、模型拓展、有效性算 法、與其它多種不確定智能分析方法的融合、多a g e n t 中的粗糙集、粒計算等方面。 ( 1 ) 粗糙集理論數(shù)學性質(zhì)方面的研究主要是對粗糙集理論中知識的不確定性問題 進行理論研究，包括討論粗糙集代數(shù)結構1 3 2 、拓撲結構【3 3 】、粗糙邏輯 3 4 1 、粗糙集的收 斂性1 3 5 l 以及信任函數(shù)( b e l i e f f u n c t i o n s ) 【3 q 問題。隨著租糙結構與代數(shù)結構、拓撲結構、 序結構等各種結構的不斷整合，必將推動粗糙集理論的快速發(fā)展1 1 2 1 。 ( 2 ) 粗糙集理論模型拓展方面的研究包括可變精度模型( v a r i a b l ep r e c i s i o nr o u g h s e t s , v p r s ) 3 7 1 、相似模型( r s tb a s e d0 1 1s i m i l a r i t yr e l a t i o n ) 【3 硼和連續(xù)屬性離散化模 型1 3 9 1 。主要解決粗糙集理論應用于數(shù)據(jù)分析時，遇到的數(shù)據(jù)噪聲、數(shù)據(jù)不完備和連續(xù)數(shù) 據(jù)離散化等問題。 ( 3 ) 粗糙集理論中有效性算法的研究是粗糙集合在a j 方向上研究的一個主要方 向。目前，該研究主要集中在導出規(guī)則的增量式算法 4 0 1 、約簡的高效啟發(fā)式算法【4 1 。4 3 1 、 粗糙集合基本運算的并行算澍4 4 1 以及現(xiàn)有算法的改進1 4 5 1 。 7 第一章緒論 ( 4 ) 在粗糙集理論與其他不確定智能分析方法之間關系的研究中，目前主要討論 它與模糊集理論1 2 a , - 2 7 1 、d - s ( d e m p s t e r - s h a f e r ) 誕據(jù)理涂l “、毒孛經(jīng)鼴終p 磚、絞謗方法1 4 s l 和信息論的相置滲透與補充，研究怎樣將粗糙集與其他不確定分析方法結合起來以取得 燹好戇效鬃。 ( 5 ) 在多a g e n t 系統(tǒng)中粗糙集研究的焦點是多a g e n t 系統(tǒng)基于粗糙集的推理和規(guī) 辯合成策賂l 嘲。 ( 6 ) 粒度計算也怒粗糙集的一個新的發(fā)展方向【矬蝴。 1 4 2 糨糙集理論的腋用研究 粗糙集是發(fā)現(xiàn)知識、輔助決策斡有效工具，具有鱉實的理論基礎。褪糙集璦論自掇 斑以來，b 在許多領域中得到了應用。嗣前，黢蓑?qū)γ夭诩碚撗芯康牟粩嗌钊?，粗?集的應用領域不斷得到了擴展。 返顰來，焱褪糙集驥論發(fā)鼴懿基破上，褪糙集應用方法大缽鴦如下足令方靄 ：s o - 5 1 l ； ( 1 ) 與其它研究方法相結合。例如與模糊集理論、模糊邏輯推理、模態(tài)邏輯、神 經(jīng)網(wǎng)絡、遽轉(zhuǎn)算法等楚璦不確定淫題與較詩算方法的有撬結合，產(chǎn)生了糖模贛理論、凝 神經(jīng)網(wǎng)絡等新的理論和研究方法。 ( 2 ) 應蔫予規(guī)掰學習移凌策表箍強。在縑證筒純螽的決策系統(tǒng)輿有與潦決策系統(tǒng) 相同分類能力的前提條件下，邋過使用知識約筒和范疇約簡，將決策系統(tǒng)簡化井找到最 小( 最綴) 決筑糯貝i j 集合，以選到最大限度泛化的目的。 ( 3 ) 進符知識約鑲。約麓鞭擺對約籬在糨糙集中+ 分重要，它反映了一令決策系 統(tǒng)的本質(zhì)。對條件屬性熊合的約簡，可以保證簡化后的決策系統(tǒng)具有與原決策系統(tǒng)相同 豹分類縫力。扶數(shù)據(jù)頸楚理懿囊度著震住約蕊縫去掉躉余震瞧，提裹系統(tǒng)藩效率。 ( 4 ) 進行屬性相關分析。粗糙集方法中屬性重要程度可以用來衡詹該屬性對分類 懿影確程度，逡蠢對關鍵屬毪精次要屬經(jīng)分麓滋行楚毽，戳褥掰較好豹分類效采。 ( 5 ) 進行數(shù)據(jù)離散化。將糧糙集理論引入數(shù)據(jù)離散化，可以避免離散化的盲e t 性， 在保持原來數(shù)搭分類能力不變酌情況下進行有效的離散化。 ( 6 ) 進行增量式學習。從粳糙集理論的差別矩陣嫩發(fā)，利用與，或邏輯關系求取規(guī) 則描述。新的對象只需強差別矩陣上增加相應的列，即可獲得增量后的規(guī)則。 租糙集理論放誕生要4 現(xiàn)在雖然只有足卡年豹時霹，健蠹于象具有較強的實瘸性，毫 經(jīng)在許多領域獲得了令人鼓舞的成果 6 , 8 1 ： 矗 第一章緒論 ( 1 ) 股票數(shù)據(jù)分析。利用粗糙集方法通過分析股鬃的歷史數(shù)據(jù)，研究股禁價格與 攢數(shù)之瓣瓣藏賴熒系，馱瑟獲褥頸測趣剿，這一矮究戒祭已繕到了華零攆涯券交暴專家 的認可。 ( 2 ) 模式談剮。痰糟褪穩(wěn)燕方法掰究語音諼鬃、箏寫字符浚嗣等溺逶，勢疆彀特 征屬性，從而為計算機的進一步智能化打下基礎。如郵政系統(tǒng)中的信件發(fā)送，信件的分 癸是一個十分繁瑣酌闖麓，知栗剩用租糙集方法識裁密孕寫字符，則信件的分類將變得 十分簡單，進面大大提禽郵政系統(tǒng)的效率，降低費用。 ( 3 ) 地震預報。利用粗糙集方法研究震前的地質(zhì)、氣象數(shù)據(jù)與里氏地震綴別的依 賴關系，從兩為她震預綴提供一定的依攥。 ( 4 ) 沖突分析。應用粗糙集方法融建立了反映以甑列、巴勒斯坦、約旦、埃及、 敘裁耍秘涉特哭控猿等六蓬關予孛袤窩等淹題貉談判模嫠。 ( 5 ) 數(shù)據(jù)庫中的知識發(fā)現(xiàn)。數(shù)據(jù)庫知識發(fā)現(xiàn)( k d d ) 又稱數(shù)據(jù)挖掘( d a t a m i n i n g ) ， 怒當蓊人工餐熊島數(shù)據(jù)海技寒交叉學科瓣研究熟點之一。程糙集方法瑗已成為k d d 豹 一種重黌方法，其導出的知識精練且更便于存儲和使用。 ( 6 ) 專家系統(tǒng)( e x p e r ts y s t e m ，e s ) 。粗糙鬃摘取規(guī)則的特點，為構造e s 知識庫提 供了一條嶄新的途徑。 ( 7 ) 粗糙控制( r o u g hc o n t r 0 1 ) 。糨糙集理論根據(jù)觀測數(shù)據(jù)獲得控制策略的方法被 稱為放藏鍘中學習( l e a r n i n gf r o me x a m p l e s ) ，瘸子譬裁控割載蒎疇。文簌 5 2 1 蔽。露耀糙 控制研究了“小車倒立擺系統(tǒng)”這一經(jīng)熊控制問題，取得了較好的結果。在過裰控制領 域，文獻【5 3 】應翔粒糙集方法成功蘧舞敬壅了水澀窯爐煞控割瓣掰。穰糙控銅豹優(yōu)點怒 簡單迅遮、實現(xiàn)容易，不需要像模糊控制那樣進行模糊化和去模糊化。因此在特別要求 控裁器縮構與算法德單豹場合，采取褪髓控制較為合適。另外，由于控制算法究全來自 觀測數(shù)據(jù)本身，其決策島推理過程可以很容易被檢驗和證實。一種耨的有吸引力的控制 策略“模糊粗糙控制( f u z z y - r o u g hc o n t r 0 1 ) ”正悄然興趣，其主要思路鼴利用糨糙集獲 取模糊按露靚則。 ( 8 ) 醫(yī)療診斷。粗糙集方法根據(jù)以往的病例歸納出診斷規(guī)則，用來指導新的病例。 熱現(xiàn)有豹入王羲濺早產(chǎn)壤磋率只騫1 7 0 o - 3 8 ，應靂疆糙集理論鼙鞋提羯戮6 8 - 9 0 。 ( 9 ) 人工神經(jīng)元網(wǎng)絡( a r t i f i c i a ln e u r a l n e t w o r k ，a n n ) 。訓練時間過于漫長的固有 缺點是翩約a n n 實霜純豹霞素之一。鍛霹戳穰忍租糙裘方法純筒神經(jīng)閼絡巍絳群本數(shù) 譬 第一牽緒論 據(jù)集，在保留重豢信息的前提下消除多余數(shù)據(jù)，使訓練速度提商4 至5 倍。如糶將粗糙 集與a n n 結合起來，兗分剝震耀糙集處理不確定經(jīng)的特長，裁可以增強a n n 豹售患 處理能力。 ( 1 0 ) 決策分輯。纛糙集懿決策麓捌是在分褥羧往經(jīng)驗數(shù)據(jù)豹萋稿上褥囊懿。耱毯 集允許決策對象中存在一些不太明確、不太完整的屬性，彌補了常規(guī)決策方法的不足。 如希貉置塹發(fā)震銀行e t e v a 應廂糖糙集理論漭駒割訂信貸政策，是鞭糙集多礁濺決策 方法的一個成功范例。 粗精集理論的應用領域還包括：近似推理、軟件工程數(shù)據(jù)分析、圈像處理、商業(yè)金 融分拆、硬件實現(xiàn)、材料辯學中的晶體結構分耩、耨?？剂习l(fā)現(xiàn)、預濺建模、結構建模、 過程控制、投票分析、電力系統(tǒng)、破產(chǎn)估計、飛行員評價等。 1 5 粗糙集理論存在的問題 終必一耱豢搴紡，爨糙集農(nóng)實驏痤瘸孛迄遴臻了謬多匿難，存在綴多淘題。關鍵鯔 題主要襲現(xiàn)在以下幾個方面： ( 1 ) 不適合薤理大艇模數(shù)據(jù)。褪麓集本身特煮凌定了宅農(nóng)楚蓮大凝模溺舔薅豹低 效性。因此，需要首先把大型數(shù)據(jù)進行有效處理，而如何進行有效處理脊待進一步研究。 ( 2 ) 不能裔效遣攢述數(shù)據(jù)的不精確性或不確定性。粗糙祭理論在處理數(shù)據(jù)時也裔 許多局限性，糧糙集理論對知識媳不完憋處理怒有效的，但它來包含處理不精確或不確 定原始數(shù)據(jù)的機制，因此，單純的租糙集理論不一定能肖效地描述數(shù)據(jù)不精確域不確定 戇實囂翊題，囂要其它努法