基于粗糙集和Trie樹(shù)的知識(shí)約簡(jiǎn)方法研究.pdf

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

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

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