基于粗糙集和Trie樹的知識約簡方法研究.pdf

1、粗糙集理論作為一種新的處理模糊信息和不確定信息的軟計算工具，于1982年由波蘭科學家Z.Pawlak創(chuàng)立。知識約簡是粗糙集理論研究中的核心內(nèi)容之一，如何快速有效地對海量數(shù)據(jù)進行知識約簡，并從中挖掘出有效的知識是粗糙集理論研究的一個熱點。至今，很多學者已提出了大量關(guān)于屬性約簡和屬性值約簡的研究方法。但是，現(xiàn)有的粗糙集知識約簡算法的時間復雜度較高，對于大數(shù)據(jù)集的處理效率不高。這大大的限制了粗糙集的實際應用。因此，研究高效的處理海量數(shù)據(jù)的知識

2、約簡方法很有必要。
　　 Trie樹是一種樹形結(jié)構(gòu)，它是一種哈希樹變種，典型應用于統(tǒng)計、排序和保存大量的字符串，因此經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計。由于它的查詢效率比哈希樹高，如果把它運用到粗糙集知識約簡算法的研究中，則可能得到能處理海量數(shù)據(jù)的快速知識約簡算法。本文結(jié)合Trie樹查找效率高的特點，開展了基于Trie樹以及粗糙集理論的知識約簡算法的研究。首先，將Trie樹用于求取決策表的正區(qū)域中，當決策表中一個對象插入Trie

3、樹時，表現(xiàn)為一個從根節(jié)點到葉子節(jié)點的分支，在葉子節(jié)點計算決策表的正區(qū)域，在此基礎上，結(jié)合貪心算法提出了一種時間復雜度較低的屬性約簡算法。其次，將Trie樹用于屬性約簡后的決策表覆蓋計算，由于屬性值約簡過程中的決策表是一個存在部分缺省值的不完備決策表，當決策表中對象插入Trie樹時，必須考慮Trie樹中的空值節(jié)點與同一層其它兄弟節(jié)點的匹配問題，并同樣在葉子節(jié)點得到?jīng)Q策表的覆蓋，利用此覆蓋計算方法，提出了一種時間復雜度較低的屬性值約簡算法。