粗糙近似算子的性質與公理化刻畫【畢業(yè)論文】

1、<p>　　本科畢業(yè)設計(論文)</p><p>　題 目：粗糙近似算子的性質與公理化刻畫</p><p>　學 院：</p><p>　學生姓名：</p><p>　專 業(yè)：信息與計算科學</p><p>　班 級：</p><p>　指導教師：</p&

2、gt;<p>　起止日期：</p><p><b>　　摘要</b></p><p>　　粗糙集理論是一種研究不完整、不確定知識處理的數學工具, 近幾年來在機器學習、知識發(fā)現、算法研究、工程應用、決策支持系統(tǒng)以及模式識別等應用中取得了較好的成果. 在Pswlsk粗糙集理論中, 下近似和上近似并非最基本的概念, 粗糙集理論中所產生的代數系統(tǒng)是最主要的研究,

3、 利用一個公理化來刻畫上、下近似算子, 表示公理集和這個條件下所產生的代數系統(tǒng)之間的聯(lián)系的粗糙集理論研究方法被稱為公理化方法. 本文主要研究粗糙近似算子的性質與公理化刻畫. 在粗糙集理論中有兩種方法來推廣定義近似算子: 構造性方法和公理化方法. 給出了在一般模糊環(huán)境下各種粗糙近似算子的定義, 得到了這些近似算子的表示.</p><p>　　關鍵詞: 粗糙集; 近似算子; 近似空間; 公理化刻畫</p>

4、<p>　　Rough approximation operator properties and axiomatic characterization</p><p><b>　　Abstract</b></p><p>　　Rough Set Theory is a kind of mathematical tool to deal with the

5、 incomplete and indefinite knowledge processing, which has borne fruit recently in the application to machine learning, knowledge discovery, algorithm research, engineering application, decision supporting system and pat

6、tern recognition. Lower approximation and upper approximation are not the most basic concepts in Pawlak’s Rough Set Theory while algebra system induced by that theory is the main idea which uses axiomatization to dep<

7、/p><p>　　Keywords: Rough set; Approximation operators; Approximation space; Axiomatic depiction</p><p><b>　　目錄</b></p><p><b>　　摘要0</b></p><p>　　Ab

8、stractII</p><p><b>　　1 前言1</b></p><p>　　1.1 粗糙集的簡介1</p><p>　　1.2 公理化方法的應用1</p><p>　　1.3 論文的組織結構2</p><p>　　2粗糙近似算子及其性質3</p><

9、p>　　2.1 廣義粗糙近似算子的定義3</p><p>　　2.2 粗糙近似算子與二元關系的等價刻畫6</p><p>　　3粗糙近似算子的公理化刻畫10</p><p>　　3.1 近似算子的公理化刻畫10</p><p>　　3.2 粗糙集理論的公理化刻畫11</p><p><b&

10、gt;　　4 小結17</b></p><p><b>　　參考文獻18</b></p><p><b>　　致謝19</b></p><p><b>　　1 前言</b></p><p>　　1.1 粗糙集的簡介</p><p>　

11、　1982年, 波蘭數學家Pawlak Z發(fā)表了經典論文Rough Sets, 粗糙集理論于此誕生. 在這之后, 許多數學家, 計算機研究人員和邏輯學家對粗糙集產生了很大的興趣, 并在粗糙集的理論和應用方面做了大量的研究. 1991年Pawlak Z的專著出版, 使得粗糙集在各個領域中的應用向前推進. 此后也召開了一些粗糙集的會議, 第一屆關于粗糙集理論國際學術會議在波蘭召開. 1995年, ACM Communication將其列為新

12、浮現的計算機科學的研究課題. 1998年, 國際信息科學雜志(Information Sciences)還為粗糙集理論的研究出了一期專輯. 這些大大地促進了粗糙集的發(fā)展.</p><p>　　粗糙集的實用性很強, 粗糙集從產生到現在雖然只有短暫的十幾年的時間, 但是已經取得了很多的成果. 它在機器學習、知識發(fā)現與數據挖掘、模式識別、決策分析、本體近似等領域廣泛應用, 粗糙集理論的研究逐漸趨于熱化.</p&g

13、t;<p>　　1.2 公理化方法的應用</p><p>　　在Pawlak粗糙集模型中, 等價關系在論域上有著至關重要的作用. 劃分在等價關系上的形成, 構造了論域上的上、下近似算子. 用來刻畫不精確的概念, 并且進一步的研究相應的知識來獲取問題. 但在很多實際的問題中, 很難構造對象之間的等價關系, 或者對象之間在本質上并不存在等價關系. 為了推廣粗糙集理論的應用范圍, 根據具體的問題, 人們

14、對Pawlak粗糙集模型進行了許多形式的推廣. </p><p>　　通常研究粗糙集近似算子有兩種方法: 構造性方法與公理化方法. 構造性方法的主要思路是從給定的近似空間出發(fā)去研究粗糙集和近似算子, 然后導出粗糙集代數系統(tǒng)[6,7]. 公理化方法的基本要素是滿足某些公里集的近似算子, 即事先給定粗糙集代數系統(tǒng), 然后再去找通過構造性方法定義的近似算子以及由它導出的粗糙集的二元關系, 這個就是事先就給定的一個近似算

15、子和粗糙集代數系統(tǒng).</p><p>　　最早研究粗糙集用公理化方法的是我國的劉清及其國際合作者Lin[8], 因為他們得出的的公理集是不獨立的, 祝峰與何華燦[9]就對公理化方法又進行了改進. Thieie[10]與Yao[11]分別對于一般關系下的經典粗糙近似算子與公理化作了比較完整的刻畫.</p><p>　　研究粗糙集結構主要有構造性方法和公理化方法. 研究粗糙集理論的大部分前期的

16、工作都是構造性方法, 這種方法具有較強的應用背景, 因為一些實際例子的需要, 也常常產生一些問題, 它的缺點是不易比較深入了解粗糙集的代數結構. 與構造性不同, 用公理化方法研究粗糙集就少了很多工作, 公理化方法所顯示的形式的簡潔性、條理性和結構的和諧性確實符合美學上的要求, 因而為數學活動中貫徹審美原則提供了范例</p><p>　　1.3 論文的組織結構</p><p>　　本文用構

17、造性方法和公理化研究粗糙集, 由一個一般二元經典關系出發(fā)構造性定義一對對偶粗糙近似算子, 討論了粗糙近似算子的性質, 并且由各種類型的二元關系通過構造得到各種類型的粗糙集代數, 用公理形式定義粗糙近似算子. 對于各種粗糙近似算子的公理化刻畫做了總結, 在有限論域中給出了經典粗糙近似算子的構造性定義并獲得刻畫這些近似算子的獨立公理集. 闡明了近似算子的公理集可以保證找到相應的二元經典關系, 使得由關系通過構造性方法定義的粗糙近似算子恰好

18、就是用公理化定義的近似算子.</p><p>　　2 廣義粗糙近似算子及其性質</p><p>　　2.1 廣義粗糙近似算子的定義</p><p>　　定義2.1 設和是兩個非空有限論域. 稱子集表示的冪集是從到上的一個經典二元關系. 稱關系是串行的(serial), 若對于任意存在使得; 若, 稱是上的一個二元關系. 稱是自反的, 若對于任意有; 稱對稱的, 若

19、對于任意, 蘊含; 稱是傳遞的, 若對于任意,和蘊含; 稱是歐幾里得的(Euclidean), 若對于任意, 和蘊含; 稱是等價的, 若是自反、對稱和傳遞的二元關系.</p><p>　　設是從到上的一個二元關系. 我們定義一個集值函數如下:</p><p><b>　　, .</b></p><p>　　稱為關于的后繼領域. 顯然, 任意一個

20、從到的集值函數都可以定義一個二元關系. 由集值函數, 我們可以定義一個基本集分配（又稱為關系劃分函數）,</p><p><b>　　, .</b></p><p><b>　　易證滿足性質:</b></p><p>　　(J1) , </p><p><b>　　(J2) .&l

21、t;/b></p><p>　　定義2.2 設是從到上的一個經典二元關系, 稱三元組是一個廣義經典近似空間. 對于任意, 關于的下似和上似分別定義如下:</p><p><b>　　,</b></p><p><b>　　.</b></p><p>　　稱是關于的（廣義）粗糙集,分別稱和為下

22、近似算子和上近似算子. </p><p>　　顯然, 如果, 是上的等價關系, 那么對于有, </p><p><b>　　,</b></p><p><b>　　.</b></p><p>　　故廣義近似算子是Pawlak經典近似算子的推廣形式.</p><p>　　定理2

23、.1 [12-14] 設和是從到上的二元經典關系, 那么廣義粗糙近似算子滿</p><p>　　足以下性質: 對于,</p><p><b>　　(LP) ,</b></p><p><b>　　(UP) ;</b></p><p><b>　　(L1) ,</b></

24、p><p><b>　　(U1) ;</b></p><p><b>　　(L2) ,</b></p><p><b>　　(U2) ;</b></p><p><b>　　(L3) ,</b></p><p><b>　　(

25、U3) ;</b></p><p><b>　　(L4) ,</b></p><p><b>　　(U4) ;</b></p><p><b>　　(L5) ,</b></p><p><b>　　(U5) .</b></p>&

26、lt;p>　　定理2.2 設是有限非空論域, 是上的二元關系, 則:</p><p><b>　　(1) , ;</b></p><p><b>　　(2) , ;</b></p><p>　　(3) , ; , ;</p><p><b>　　(4) , , ;</b&g

27、t;</p><p>　　(5) , , , ;</p><p>　　其中是任意指標集, 性質(1)稱為近似算子的對偶性質.</p><p>　　證明(1) 設, 因為</p><p><b>　　,</b></p><p>　　所以. 用代替中的即得.</p><p>　

28、　(2) 若, 則存在, 由定義得, 矛盾！所以. 由得, 即, 從而.</p><p><b>　　(3) 因為</b></p><p><b>　　,</b></p><p><b>　　所以.</b></p><p><b>　　同理,</b><

29、;/p><p><b>　　,</b></p><p><b>　　,</b></p><p><b>　　所以.</b></p><p>　　(4) , 由定義, 而,于是, 從而, 所以, . 由對偶性質和易推得.</p><p>　　(5) 由和性質(

30、4)得到, 從而. 同理可得.</p><p>　　引理2.1 設是有限非空論域, 是上的二元關系, 則, 有</p><p><b>　　.</b></p><p>　　證明 因為對于任意,</p><p><b>　　所以, </b></p><p><b>

31、　　.</b></p><p>　　2.2 粗糙近似算子與二元關系的等價刻畫</p><p>　　定理2.3 設是有限非空論域, 是上的二元關系, 則以下等價:</p><p><b>　　(1) 是串行的;</b></p><p><b>　　(2) ;</b></p>

32、<p><b>　　(3) ;</b></p><p><b>　　(4) .</b></p><p>　　證明 “(1) (2)” , 通過定義知. 因為是串行的, 即, 因此, 即, 故.</p><p>　　“(2) (1)” 反證, 若存在, 使, 由,, 即, , 因此, 這與(2)成立矛盾, 所

33、以是串行的.</p><p>　　“(2) (3)” 利用定理2.2的對偶性質有</p><p>　　即(2) (3).</p><p>　　“(3) (4)” 利用定理2.2的對偶性質有</p><p><b>　　.</b></p><p>　　定理2.4 設是有限非空論域, 是上的二

34、元關系, 則以下等價:</p><p><b>　　(1) 是自反的;</b></p><p><b>　　(2) , ;</b></p><p><b>　　(3) , .</b></p><p>　　證明 “(1) (2)” 設, 由定義得. 又因為是自反的, 所以, 從

35、而, 因此.</p><p>　　“(2) (3)” , 由(2)得, 從而由對偶性質得</p><p><b>　　.</b></p><p>　　“(3) (1)” , 由(3)得, 由定理2.2可得, 從而, 所以是自反的.</p><p>　　定理2.5 設是有限非空論域, 是上的二元關系, 則以下等價:&

36、lt;/p><p>　　(1) 是逆串行的;</p><p><b>　　(2) ,;</b></p><p><b>　　(3) .</b></p><p>　　證明 由定理2.2得, </p><p>　　是逆串行 , </p><p&

37、gt;<b>　　.</b></p><p>　　定理2.6 設是有限非空論域, 是上的二元關系, 則以下等價:</p><p>　　(1) 是傳遞的; </p><p><b>　　(2) , ;</b></p><p><b>　　(3) , .</b></p>

38、;<p>　　證明 “(1) (2)” , 由定義知, 于是有, 由下近似的定義得, 由的任意性得, 所以, 因此, </p><p><b>　　.</b></p><p>　　“(2) (3)” 由定理2.2和對偶性質(1)得</p><p><b>　　.</b></p><p&

39、gt;　　“(3) (1)” 若, , 由定理2.2知, 且, 從而, 由上近似的定義知, 又由于(3)成立, 因此, 于是由定理2.2得. 又, 得到, 即是傳遞的.</p><p>　　定理2.7 設是有限非空論域, 是上的二元關系, 則以下等價:</p><p><b>　　(1) 是對稱的;</b></p><p><b>

40、;　　(2) , ;</b></p><p><b>　　(3) , .</b></p><p>　　證明 “(1) (2)” 若對于任意, 由于是對稱的, 因此.</p><p>　　, 于是. 由的任意性得,從而由下近似的定義知, 故.</p><p>　　“(2) (1)” 設, . 由(2)知,

41、得</p><p><b>　　,</b></p><p><b>　　由</b></p><p><b>　　,</b></p><p><b>　　所以是對稱的.</b></p><p>　　“(2) (3)” 由定理2.2的

42、對偶性(1)得</p><p><b>　　.</b></p><p>　　定理2.8 設是有限非空論域, 是上的二元關系, 則以下等價:</p><p>　　(1) 是歐幾里得的; </p><p><b>　　(2) , ; </b></p><p><b>

43、　　(3) , .</b></p><p>　　證明 “(1) (2)” 設, 由上近似的定義得, , 由于是歐幾里得的關系, 所以, 于是, 從而由上近似定義得. 由的任意性得, 再由下近似定義得, 所以.</p><p>　　“(2) (1)” 設, 由定理2.2知, 于是由(2)成立得, 從而由下近似的定義, 這樣就有, 再由定理2.2得, 即, 這樣證明了是歐幾里得

44、關系.</p><p>　　“(2) (3)” 由定理2.2的對偶性質(1)即得.</p><p>　　3 粗糙近似算子的公理化刻畫</p><p>　　3.1 近似算子的公理化刻畫</p><p>　　定義3.1 算子稱為是對偶的, 如果, 它們滿足</p><p><b>　　(L0) </b&g

45、t;</p><p><b>　　(H0) </b></p><p>　　由的對偶性, 我們可以用其中的一個來定義另一個. 比如就是, 就是.</p><p>　　重復使用一元算子, 可以被認為是算子的復合, 如是和的復合. 由對偶性:</p><p>　　定義3.2 設是一對對偶算子, 如果滿足公理</p>

46、<p><b>　　(L1) .</b></p><p><b>　　(L2) .</b></p><p><b>　　或者等價地, 滿足</b></p><p><b>　　(H1) .</b></p><p><b>　　(H2

47、) .</b></p><p>　　則系統(tǒng)稱為一個粗糙集代數, 稱為近似算子.</p><p>　　3.2 粗糙集理論的公理化刻畫</p><p>　　定理3.1 設是一對對偶的一元算子, 則存在一個上的二元關系使得, 對任意集都成立的充分必要條件是滿足性質:</p><p><b>　　(L1) .</b>

48、</p><p><b>　　(H1) . </b></p><p><b>　　(L2) . </b></p><p><b>　　(H2) .</b></p><p>　　證明 必要性由定理2.2即得.</p><p>　　充分性: 設滿足和, 利

49、用我們可以構造上的一個二元關系如下:</p><p><b>　　.</b></p><p>　　所以, . 等價的, 這個式子可以寫成. 由定義2.2可知, , 對單元集有,</p><p><b>　　.</b></p><p>　　由公理及論域的有限性, , 我們有</p>&l

50、t;p><b>　　.</b></p><p>　　故. 由對偶性易證.</p><p>　　可獲得粗糙集代數中的若干公理:</p><p><b>　　(D) </b></p><p><b>　　(T) </b></p><p><b

51、>　　(T’) </b></p><p><b>　　(B) </b></p><p><b>　　(B’) </b></p><p><b>　　(4) </b></p><p><b>　　(4’) </b></p>

52、<p><b>　　(5) </b></p><p><b>　　(5’) </b></p><p>　　定理3.2 設是一對近似算子, 即滿足</p><p><b>　　(L1) .</b></p><p><b>　　(L2) .</b&g

53、t;</p><p><b>　　滿足</b></p><p><b>　　(H1) .</b></p><p><b>　　(H2) .</b></p><p>　　且, 則存在一個上的串行關系使得</p><p>　　對所有的成立的充分必要條件是和滿

54、足</p><p><b>　　(D) .</b></p><p>　　證明 （必要性） 設是上的串行關系, 令, , 若</p><p><b>　　, </b></p><p>　　因為是串行的, 所以存在, 又由集的定義條件, 知,故, 所以有.</p><p>　　

55、（充分性） 由定理3.1, 對偶公理及公理(L1), (L2), (H1)及(H2)保證了上二元關系的存在性, 且使得, . 如果, 滿足, 由</p><p>　　故對, 使得. 由的構造, , 故是串行的.</p><p>　　定理3.3 設是一對對偶算子, 即滿足</p><p><b>　　(L1) .</b></p>

56、<p><b>　　(L2) .</b></p><p><b>　　滿足</b></p><p><b>　　(H1) . </b></p><p><b>　　(H2) .</b></p><p>　　且, 則存在一個上的自反關系使得&l

57、t;/p><p>　　對所有的成立的充分必要條件是和滿足</p><p><b>　　(T’) .</b></p><p>　　證明 （必要性） 設是上的自反關系. 令, , , 若,由的自反性, . 由的定義, 知. 故(T’)成立.</p><p>　?。ǔ浞中裕?, 滿足(T’), 由的任意性, ,</p&g

58、t;<p><b>　　即, 故是自反的.</b></p><p>　　定理3.4 設是一對對偶算子, 即滿足</p><p><b>　　(L1) .</b></p><p><b>　　(L2) .</b></p><p><b>　　滿足<

59、/b></p><p><b>　　(H1) .</b></p><p><b>　　(H2) .</b></p><p>　　且, 則存在一個上的對稱關系使得</p><p>　　對所有的成立的充分必要條件是和滿足</p><p><b>　　(B’) .&

60、lt;/b></p><p>　　證明 （必要性）設是上的自反關系, 令, . , 若,則, 如果, 由的對稱性可得, 故滿足定義即. 所以, 即(B)成立.</p><p>　?。ǔ浞中裕?滿足(B), , 設即. 由公理(B),</p><p>　　這意味著, 即, 故是對稱的.</p><p>　　定理3.5 設是一對對偶算子,

61、 即滿足</p><p><b>　　(L1) .</b></p><p><b>　　(L2) .</b></p><p><b>　　滿足</b></p><p><b>　　(H1) .</b></p><p><b&g

62、t;　　(H2) .</b></p><p>　　且, 則存在一個上的傳遞關系使得</p><p>　　對所有的成立的充分必要條件是和滿足</p><p><b>　　(4’) .</b></p><p>　　證明 （必要性） 設是上的傳遞關系, 令, . 對, 若, 來證明. 為此需證對, 為. 事實上,

63、對, 若, 因是傳遞的, 故, 又因為, 所以, 所以, 這表明, 故(4)成立.</p><p>　?。ǔ浞中裕?,滿足(4’) . 對, 設, 進一步假設, 則, 而公理(H2)蘊涵算子是單調的, 故. 由公理(4’)可知. 又由知, 故. 所以, 即傳遞.</p><p>　　定理3.6 設是一對對偶算子, 即滿足</p><p><b>　　(L

64、1) .</b></p><p><b>　　(L2) .</b></p><p><b>　　滿足</b></p><p><b>　　(H1) .</b></p><p><b>　　(H2) .</b></p><p&

65、gt;　　且, 則存在一個上的歐幾里得關系使得</p><p>　　對所有的成立的充分必要條件是和滿足</p><p><b>　　(5’) .</b></p><p>　　證明 （必要性） 設是上的歐幾里得關系, 令. , 若, 來證明, 即對, 若. 因為, 故存在且, 又因是歐幾里得的, 故, 由的定義條件可知. 故(5)成立.</

66、p><p>　?。ǔ浞中裕?,滿足. , 設, 進一步假設, 則. 由公理(5), 得</p><p><b>　　又因為</b></p><p><b>　　故</b></p><p><b>　　故</b></p><p><b>　　所以是歐

67、幾里得的.</b></p><p><b>　　5小結</b></p><p>　　本文對于各種粗糙近似算子的公理化刻畫做了總結,主要研究粗糙近似算子的性質與公理化刻畫. 用構造性方法和公理化研究了粗糙集, 由一個一般的二元關系出發(fā)構造性地定義了一對對偶算子, 討論了粗糙近似算子的性質, 并且由各種類型的二元關系通過構造得到各種類型多的粗糙集代數, 用公理

68、形式定義粗糙近似算子. 對于各種粗糙近似算子的公理化刻畫做了總結, 在有限論域中給出了經典粗糙近似算子的構造性定義并獲得刻畫這些近似算子的獨立公理集. 闡明了近似算子的公理集可以保證找到相應的二元經典關系, 使得由關系通過構造性方法定義的粗糙近似算子恰好就是用公理化定義的近似算子. 參考文獻</p><p>　　Z. Pawlak, Rough sets [J]. International Journal of

69、 Computer and Information Sciences. 1982, 11(5): 341~356.</p><p>　　Z. Pawlak, Rough Sets—Theoretical Aspects of Reasoning about Data [M]. Boston: Kluwer Academic Publishers, 1991.</p><p>　　C. C.

70、 Chan. A rough set approach to attribute generalization in datamining [J]. Journal of Information Sciences, 1998, 107: 169~176.</p><p>　　D. Mcsherry, Knowledge discovery by inspection [J]. Decision Support S

71、ystems. 1997, 21: 43~47.</p><p>　　張文修, 吳偉志, 梁吉業(yè)等. 粗糙集理論與方法 [M]. 北京: 科學出版社. 2001.</p><p>　　D. Dubois, Prade H. Rough fuzzy sets and fuzzy rough sets [J]. International Journal of General Systems,

72、 1990, 17: 191~208.</p><p>　　W.Z. Wu, W.X. Zhang. Neighborhood operator systems and approximations[J]. Information Sciences. 2002, 144 :201 ~ 217</p><p>　　T.Y Lin, Q Lin. Rough approximate

73、operators :axiomatic rough set theory [M]. In :Ziarko W ed. Rough Sets, Fuzzy Set and Knowledge Discovery, Berlin:Springer,1994,256~260</p><p>　　祝 峰, 何華燦. 粗集的公理化. 計算機學報. 2000, 33: 330 ~ 333</p&g

74、t;<p>　　H. ThieIe. On axiomatic characterisations of crisp approximation operators[J]. Information Sciences. 2000, 129: 221 ~ 226</p><p>　　Y.Y. Yao. Constructive and aIgebraic methods of the theory of

75、 rough sets [J]. JournaI of Information Sciences. 1998, 109: 21~ 47</p><p>　　Y.Y. Yao. Constructive and algebraic methods of theory of rough sets [J]. Journal of Information Sciences. 1998, 109: 21~47.</p

76、><p>　　Y.Y. Yao. Relational interpretations of neighbrohood operators and rough set approximation operators [J]. Information Sciences. 1998, 111: 239~259.</p><p>　　Y.Y. Yao. Two views of the theory

77、 of rough sets in finite universes [J]. International Journal of Approximate Reasoning. 1996, 15: 291~317.</p><p><b>　　致謝</b></p><p>　　本人在撰寫論文的過程中, 得到了許多老師和同學的熱心幫助. 這次論文的成功撰寫, 凝結了我四年

78、大學生涯的心血. 感謝所有傳授我知識的老師, 感謝所有關心過我, 幫助過我的恩師們. 這里, 我要特別感謝吳老師和徐老師對我的悉心指導和嚴格要求, 使我完成了論文的研究工作, 提高了論文的寫作水平和研究問題的能力. 此外, 吳老師和徐老師詳盡的審閱了論文初稿, 給我提出了寶貴的修改意見, 對英文翻譯也進行了逐字逐句的修改與校正. 兩位老師嚴謹的治學態(tài)度和誨人不倦的師德作風使我受益終身, 再次向兩位老師表示衷心的感謝. </p>