基于粗糙集和規(guī)則樹的增量式知識獲取算法

電子通信論文編號:TX051        論文字數(shù):26418,頁數(shù):45

目    錄
摘要   1
Abstract   2
第一章  緒論  1
1.1引言  1
1.2 粗糙集理論及應(yīng)用的發(fā)展狀況   1
1.3 論文背景及工作內(nèi)容   2
1.4 論文組織與結(jié)構(gòu)   4
第二章 粗糙集理論基礎(chǔ)  4
2.1引言   4
2.2 粗糙集的基本概念   4
2.2.1知識和不分明關(guān)系   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 小結(jié)   10
第三章 基于合并規(guī)則的決策表求核方法  10 
3.1  引言  10
3.2  合并規(guī)則及其性質(zhì)   11
3.3  S與S/在求核問題上的等價性分析  12
3.4  基于記錄合并的屬性求核算法  14
3.4.1 基于記錄合并的屬性求核算法  14
3.4.2 算法復(fù)雜度分析   15
3.5 實驗結(jié)果   16
3.6 小結(jié)   17
第四章  基于粗糙集和規(guī)則樹的增量式知識獲取算法   18
4.1 增量式知識獲取算法討論  18
4.1.1引言   18
4.1.2 一般值約簡算法[21  18
4.1.3 歸納值約簡算法[21]   19
4.1.4 ID3、ID4和ID5R算法[15,16]   19
4.1.5 概念格上規(guī)則提取的漸進式算法[20]   24
4.1.6 幾種增量式學(xué)習(xí)算法的比較   26
4.2  基于粗糙集和規(guī)則樹的增量式知識獲取算法   27
4.2.1 引言   27
4.2.2 規(guī)則樹 27
4.2.3算法的幾個策略 28
4.2.4 算法描述 31
4.2.5算法復(fù)雜度分析  31
4.2.6 算法性能分析  32
4.3 RRIA算法測試   32
4.3.1引言    32
4.3.2 測試1：RRIA和粗糙集非增量式知識獲取算法的比較測試   32
4.3.3測試2：RRIA和ID4算法的比較   33
4.4 小結(jié)   35
第五章 結(jié)論   36
致謝   37
參考文獻   38

摘要
粗糙集理論是一種新的處理模糊和不確定知識的軟計算工具。它能有效地分析和處理不精確、不一致、不完整等各種不完備信息，并從中發(fā)現(xiàn)隱含的知識，揭示潛在的規(guī)律，近年來在機器學(xué)習(xí)、數(shù)據(jù)挖掘等多個領(lǐng)域得到廣泛應(yīng)用。
粗糙集是知識獲取的一種方法。作為當前的研究熱點，在知識獲取的研究中尚存在一些問題未能解決，我們對其中兩個主要問題——求核問題和增量式知識獲取模型進行了研究和討論，得到了較好的結(jié)果。
屬性約簡是知識獲取中最重要的部分之一。決策表核屬性的確定往往是信息約簡過程的出發(fā)點和關(guān)鍵。以前的可辨識矩陣求核算法由于忽略了某些因素而產(chǎn)生錯誤結(jié)果，葉東毅在新的求核算法中雖然把錯誤改正了，但算法復(fù)雜度明顯提高。本文在定義的合并規(guī)則的基礎(chǔ)上提出一種求核算法，該算法不僅改正了以前可辨識矩陣求核法的錯誤，而且在性能上優(yōu)于葉東毅和Hu Xiaohua的求核算法。
近幾年在粗糙集理論研究中對求解屬性的最小約簡或較小約簡以及求取最簡規(guī)則集[1～3]的算法已經(jīng)進行了一些研究，但這些研究都是針對靜態(tài)數(shù)據(jù)的。而數(shù)據(jù)庫是動態(tài)的，因此許多研究者建議[4～6]，數(shù)據(jù)庫知識發(fā)現(xiàn)算法應(yīng)該是增量式的。屬性最小約簡的增量式算法以及增量式更新概念格的算法已經(jīng)開始被研究，但對于增量式的知識獲取算法的研究工作還比較少。在以上工作的基礎(chǔ)上，本文研究了增量式知識獲取問題，發(fā)現(xiàn)當把知識的樹結(jié)構(gòu)和粗糙集的知識獲取思想進行結(jié)合后，對于增量式學(xué)習(xí)的數(shù)據(jù)可以取得好的學(xué)習(xí)效果。在此基礎(chǔ)上，我們提出基于粗糙集和規(guī)則樹的增量式知識獲取算法(RRIA)。實驗表明，RRIA比傳統(tǒng)粗糙集知識獲取算法不僅具有更快的學(xué)習(xí)速度，而且生成的規(guī)則對樣本的識別率可以達到甚至超過傳統(tǒng)粗糙集知識獲取算法；同時，我們還把RRIA算法與ID4算法進行了比較測試，結(jié)果表明RRIA算法無論規(guī)則的質(zhì)量還是正確識別率都優(yōu)于ID4算法。

關(guān)鍵詞：  粗糙集   核屬性  知識約簡  可辨識矩陣  規(guī)則樹   判定樹   增量式學(xué)習(xí) 

Abstract
Rough set theory is emerging as a new tool for dealing with fuzzy and uncertain data. It is very efficient to analyse and process imprecise and imperfect data. It can find potential knowledge and rule from data. In recent years，it has been studied and applied in many fields such as machine learning，data mining and etc.
Knowledge acquision is one of the most important part of rough set，and it is also the focus of researching. There are some problems in knowledge acquisition that need to be solved. We deal with two key problems in this paper，that is，computation of attribute core and incremental aquisition of knowledge.
Attribute reduction is one of the most important parts in knowledge acquisition. The core attributes of a decision table are often the start and key of many information reduction procedures. Hu’s method of computating core attributes based on discernibility matrix was wrong because of ignoring some factors. The error was corrected by Ye Dongyi，but his alogrithm’s complexity was too high. In this paper，we present a new algorithm based on objects，combination. The algorithm corrects Hu’s error and its complexity is lower than Ye’s method and Hu’s method.
In resent years，many rough set based algorithms for computing the smallest or smaller reduction of attributes and knowledge acquisition are developed[1～3]. They are almost based on static data. However，real databases are always dynamic. So，many researchers[4～6] suggest that knowledge acquisition in databases should be incremental. Incremental arithmetic for the smallest reduction of attributes and incremental algorithm of rule extraction based on concept lattice have been developed，but there are few incremental rough set based algorithms about knowledge acquisition. On the basis of former results，we develop a rough set and rule tree based incremental knowledge acquisition algorithm (RRIA) in this paper. Simulation results show that our algorithm can learn more quickly than classical rough set based knowledge acquisition algorithms，and the performance of knowledge learned by our algorithm can be the same as or even better than classical rough set based knowledge acquisition algorithms. Besides，we compare our algorithm with ID4 algorithm. The results show that the rule quality and the recognition rate of our algorithm are both better than ID4.
Key words: Rough Set  Core Attribute  Knowledge Reduction  Discernibility Matrix  Rough set  Independent learning  Knowledge acquisition