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

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

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

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