基于Rough Set的屬性約簡算法研究.pdf

1、科技的飛速發(fā)展，需要處理的信息量迅速增加，迫切需要一種能從大量科學(xué)數(shù)據(jù)中發(fā)現(xiàn)有價值知識的有效方法。知識發(fā)現(xiàn)是研究如何從大量的、模糊的、隨機(jī)的數(shù)據(jù)中，提取隱含在其中的信息。Rough Set是由波蘭學(xué)者Plawlak.Z在1982年提出的應(yīng)用于不確定知識領(lǐng)域數(shù)據(jù)挖掘的一個數(shù)學(xué)工具?；赗ough Set的屬性約簡是知識發(fā)現(xiàn)的重要內(nèi)容，也是一個NP-hard問題。 總結(jié)了基于Rough Set的一些屬性約簡算法，并且詳細(xì)分析了算法的

2、時間復(fù)雜度和空間復(fù)雜度。在此基礎(chǔ)之上，分析了其中最常用的面向支持度的屬性約簡算法MSA (Maximum Support Algorithm)。它的局限性在于選擇了偏好特征。選擇了重要規(guī)則集中具有最高支持度的特征而不是所有潛在規(guī)則中具有最高質(zhì)量的特征。換句話說，它僅考慮了潛在規(guī)則的局部最佳而沒有考慮全局最佳。訓(xùn)練集可能屬于許多分類。MSA偏好于某一個分類。它將產(chǎn)生一些系列帶有偏差分布式支持度的規(guī)則。更進(jìn)一步，MSA算法有時對兩個具有相同

3、大小的正域和多數(shù)重要規(guī)則的支持度喪失判斷能力。基于上述討論,提出了一種基于Rough Set的啟發(fā)式算法IMSA (Improved Maximum Support Algorithm)來克服上述缺點，且重新定義了啟發(fā)函數(shù)。 最后，開發(fā)了一個簡易的屬性約簡的實驗系統(tǒng)RSS，在屬性約簡算法方面，實現(xiàn)了MSA算法和本文提出的算法；在單個功能方面，實現(xiàn)了分類和近似集等重要概念的求取。利用本系統(tǒng)進(jìn)行實驗分析，得出本文提出的算法在性能方面