粗糙集理論研究.doc
約46頁DOC格式手機打開展開
粗糙集理論研究,頁數(shù) 46 字數(shù) 26415摘要碩士學位研究成果粗糙集理論是一種新的處理模糊和不確定知識的軟計算工具。它能有效地分析和處理不精確、不一致、不完整等各種不完備信息，并從中發(fā)現(xiàn)隱含的知識，揭示潛在的規(guī)律，近年來在機器學習、數(shù)據(jù)挖掘等多個領域得到廣泛應用。粗糙集是知識獲取的一種方法。作為當前的研究熱點，在知識獲...
內(nèi)容介紹
此文檔由會員 天緣 發(fā)布
粗糙集理論研究
頁數(shù) 46 字數(shù) 26415
摘要
碩士學位研究成果
粗糙集理論是一種新的處理模糊和不確定知識的軟計算工具。它能有效地分析和處理不精確、不一致、不完整等各種不完備信息，并從中發(fā)現(xiàn)隱含的知識，揭示潛在的規(guī)律，近年來在機器學習、數(shù)據(jù)挖掘等多個領域得到廣泛應用。
粗糙集是知識獲取的一種方法。作為當前的研究熱點，在知識獲取的研究中尚存在一些問題未能解決，我們對其中兩個主要問題——求核問題和增量式知識獲取模型進行了研究和討論，得到了較好的結果。
屬性約簡是知識獲取中最重要的部分之一。決策表核屬性的確定往往是信息約簡過程的出發(fā)點和關鍵。以前的可辨識矩陣求核算法由于忽略了某些因素而產(chǎn)生錯誤結果，葉東毅在新的求核算法中雖然把錯誤改正了，但算法復雜度明顯提高。本文在定義的合并規(guī)則的基礎上提出一種求核算法，該算法不僅改正了以前可辨識矩陣求核法的錯誤，而且在性能上優(yōu)于葉東毅和Hu Xiaohua的求核算法。
近幾年在粗糙集理論研究中對求解屬性的最小約簡或較小約簡以及求取最簡規(guī)則集[1～3]的算法已經(jīng)進行了一些研究，但這些研究都是針對靜態(tài)數(shù)據(jù)的。而數(shù)據(jù)庫是動態(tài)的，因此許多研究者建議[4～6]，數(shù)據(jù)庫知識發(fā)現(xiàn)算法應該是增量式的。屬性最小約簡的增量式算法以及增量式更新概念格的算法已經(jīng)開始被研究，但對于增量式的知識獲取算法的研究工作還比較少。在以上工作的基礎上，本文研究了增量式知識獲取問題，發(fā)現(xiàn)當把知識的樹結構和粗糙集的知識獲取思想進行結合后，對于增量式學習的數(shù)據(jù)可以取得好的學習效果。在此基礎上，我們提出基于粗糙集和規(guī)則樹的增量式知識獲取算法(RRIA)。實驗表明，RRIA比傳統(tǒng)粗糙集知識獲取算法不僅具有更快的學習速度，而且生成的規(guī)則對樣本的識別率可以達到甚至超過傳統(tǒng)粗糙集知識獲取算法；同時，我們還把RRIA算法與ID4算法進行了比較測試，結果表明RRIA算法無論規(guī)則的質量還是正確識別率都優(yōu)于ID4算法。
關鍵詞： 粗糙集，核屬性，知識約簡，可辨識矩陣，規(guī)則樹，判定樹 增量式學習
目 錄
第一章 緒論 1
1.1引言 1
1.2 粗糙集理論及應用的發(fā)展狀況 1
1.3 論文背景及工作內(nèi)容 2
1.4 論文組織與結構 4
第二章 粗糙集理論基礎 4
2.1引言 4
2.2 粗糙集的基本概念 4
2.2.1知識和不分明關系 4
2.2.2粗糙集與近似 5
2.2.3近似精度 6
2.3決策表、約簡、核 6
2.3.1決策表 6
2.3.2約簡與核 7
2.4可辨識矩陣 8
2.5屬性重要性 9
2.6 規(guī)則集 10
2.7 小結 10
第三章 基于合并規(guī)則的決策表求核方法 5
3.1 引言 5
3.2 合并規(guī)則及其性質 5
3.3 S與S/在求核問題上的等價性分析 6
3.4 基于記錄合并的屬性求核算法 8
3.4.1 基于記錄合并的屬性求核算法 8
3.4.2 算法復雜度分析 9
3.5 實驗結果 10
3.6 小結 11
第四章 基于粗糙集和規(guī)則樹的增量式知識獲取算法 12
4.1 增量式知識獲取算法討論 12
4.1.1引言 12
4.1.2 一般值約簡算法[21] 12
4.1.3 歸納值約簡算法[21] 13
4.1.4 ID3、ID4和ID5R算法[15,16] 13
4.1.5 概念格上規(guī)則提取的漸進式算法[20] 18
4.1.6 幾種增量式學習算法的比較 20
4.2 基于粗糙集和規(guī)則樹的增量式知識獲取算法 21
4.2.1 引言 21
4.2.2 規(guī)則樹 21
4.2.3算法的幾個策略 22
4.2.4 算法描述 25
4.2.5算法復雜度分析 25
4.2.6 算法性能分析 26
4.3 RRIA算法測試 26
4.3.1引言 26
4.3.2 測試1：RRIA和粗糙集非增量式知識獲取算法的比較測試 26
4.3.3測試2：RRIA和ID4算法的比較 27
4.4 小結 28
第五章 結論 30
致謝 31
參考文獻 32
參考文獻
[1] Hu，X. H.，Cercone，N.，Learning in Relational Databases: A Rough Set Approach. Inter. J. of Computational Intelligence，11(2)，pp.323~338，1995。
[2] Jelonek，Krawiec，K.，Slowinski，R.，Rough Set Reduction of Attributes and Their Domains for Neural networks，Computational Intelligence，11(2)，pp. 339~347，1995。
[3] 苗奪謙，Rough Set理論及其在機器學習中的應用研究，中國科學院自動化所博士學位論文，1997.6。
[4] Fayyad，U. M.，Piatetsky-Shapiro，L.，Smyth，P.，Uthurusamy，R.，Advances in Knowledge Discovery and Data Mining，Melno Park，California: AAAI Press/The MIT Press，1996.
[5] Cercone，V.，Tsuchiya，M.，Luesy Editor’s Introduction，IEEE Transations on Knowledge and Data Engineering，5(6)，pp.901~902，1993。
頁數(shù) 46 字數(shù) 26415
摘要
碩士學位研究成果
粗糙集理論是一種新的處理模糊和不確定知識的軟計算工具。它能有效地分析和處理不精確、不一致、不完整等各種不完備信息，并從中發(fā)現(xiàn)隱含的知識，揭示潛在的規(guī)律，近年來在機器學習、數(shù)據(jù)挖掘等多個領域得到廣泛應用。
粗糙集是知識獲取的一種方法。作為當前的研究熱點，在知識獲取的研究中尚存在一些問題未能解決，我們對其中兩個主要問題——求核問題和增量式知識獲取模型進行了研究和討論，得到了較好的結果。
屬性約簡是知識獲取中最重要的部分之一。決策表核屬性的確定往往是信息約簡過程的出發(fā)點和關鍵。以前的可辨識矩陣求核算法由于忽略了某些因素而產(chǎn)生錯誤結果，葉東毅在新的求核算法中雖然把錯誤改正了，但算法復雜度明顯提高。本文在定義的合并規(guī)則的基礎上提出一種求核算法，該算法不僅改正了以前可辨識矩陣求核法的錯誤，而且在性能上優(yōu)于葉東毅和Hu Xiaohua的求核算法。
近幾年在粗糙集理論研究中對求解屬性的最小約簡或較小約簡以及求取最簡規(guī)則集[1～3]的算法已經(jīng)進行了一些研究，但這些研究都是針對靜態(tài)數(shù)據(jù)的。而數(shù)據(jù)庫是動態(tài)的，因此許多研究者建議[4～6]，數(shù)據(jù)庫知識發(fā)現(xiàn)算法應該是增量式的。屬性最小約簡的增量式算法以及增量式更新概念格的算法已經(jīng)開始被研究，但對于增量式的知識獲取算法的研究工作還比較少。在以上工作的基礎上，本文研究了增量式知識獲取問題，發(fā)現(xiàn)當把知識的樹結構和粗糙集的知識獲取思想進行結合后，對于增量式學習的數(shù)據(jù)可以取得好的學習效果。在此基礎上，我們提出基于粗糙集和規(guī)則樹的增量式知識獲取算法(RRIA)。實驗表明，RRIA比傳統(tǒng)粗糙集知識獲取算法不僅具有更快的學習速度，而且生成的規(guī)則對樣本的識別率可以達到甚至超過傳統(tǒng)粗糙集知識獲取算法；同時，我們還把RRIA算法與ID4算法進行了比較測試，結果表明RRIA算法無論規(guī)則的質量還是正確識別率都優(yōu)于ID4算法。
關鍵詞： 粗糙集，核屬性，知識約簡，可辨識矩陣，規(guī)則樹，判定樹 增量式學習
目 錄
第一章 緒論 1
1.1引言 1
1.2 粗糙集理論及應用的發(fā)展狀況 1
1.3 論文背景及工作內(nèi)容 2
1.4 論文組織與結構 4
第二章 粗糙集理論基礎 4
2.1引言 4
2.2 粗糙集的基本概念 4
2.2.1知識和不分明關系 4
2.2.2粗糙集與近似 5
2.2.3近似精度 6
2.3決策表、約簡、核 6
2.3.1決策表 6
2.3.2約簡與核 7
2.4可辨識矩陣 8
2.5屬性重要性 9
2.6 規(guī)則集 10
2.7 小結 10
第三章 基于合并規(guī)則的決策表求核方法 5
3.1 引言 5
3.2 合并規(guī)則及其性質 5
3.3 S與S/在求核問題上的等價性分析 6
3.4 基于記錄合并的屬性求核算法 8
3.4.1 基于記錄合并的屬性求核算法 8
3.4.2 算法復雜度分析 9
3.5 實驗結果 10
3.6 小結 11
第四章 基于粗糙集和規(guī)則樹的增量式知識獲取算法 12
4.1 增量式知識獲取算法討論 12
4.1.1引言 12
4.1.2 一般值約簡算法[21] 12
4.1.3 歸納值約簡算法[21] 13
4.1.4 ID3、ID4和ID5R算法[15,16] 13
4.1.5 概念格上規(guī)則提取的漸進式算法[20] 18
4.1.6 幾種增量式學習算法的比較 20
4.2 基于粗糙集和規(guī)則樹的增量式知識獲取算法 21
4.2.1 引言 21
4.2.2 規(guī)則樹 21
4.2.3算法的幾個策略 22
4.2.4 算法描述 25
4.2.5算法復雜度分析 25
4.2.6 算法性能分析 26
4.3 RRIA算法測試 26
4.3.1引言 26
4.3.2 測試1：RRIA和粗糙集非增量式知識獲取算法的比較測試 26
4.3.3測試2：RRIA和ID4算法的比較 27
4.4 小結 28
第五章 結論 30
致謝 31
參考文獻 32
參考文獻
[1] Hu，X. H.，Cercone，N.，Learning in Relational Databases: A Rough Set Approach. Inter. J. of Computational Intelligence，11(2)，pp.323~338，1995。
[2] Jelonek，Krawiec，K.，Slowinski，R.，Rough Set Reduction of Attributes and Their Domains for Neural networks，Computational Intelligence，11(2)，pp. 339~347，1995。
[3] 苗奪謙，Rough Set理論及其在機器學習中的應用研究，中國科學院自動化所博士學位論文，1997.6。
[4] Fayyad，U. M.，Piatetsky-Shapiro，L.，Smyth，P.，Uthurusamy，R.，Advances in Knowledge Discovery and Data Mining，Melno Park，California: AAAI Press/The MIT Press，1996.
[5] Cercone，V.，Tsuchiya，M.，Luesy Editor’s Introduction，IEEE Transations on Knowledge and Data Engineering，5(6)，pp.901~902，1993。
