基于Tabu搜索的粗糙集屬性約簡算法研究.pdf

1、粗糙集理論是Z.PAWLAK1982年提出的一種處理不精確、噪音的、或不完整的不確定問題的強大工具，在人工智能，認知科學(xué)，或者在不精確知識表示及推理，機器學(xué)習(xí)，知識發(fā)現(xiàn)等眾多領(lǐng)域都有重大的方法論意義。 信息系統(tǒng)的約簡是粗糙集理論的關(guān)鍵，為了從信息系統(tǒng)中提取出知識規(guī)則，我們必須把信息約簡。約簡是在不損失信息表述能力的前提下，求得一個最小屬性集。顯然，屬性約簡是一個提取子集的過程，但同時也是保留了表述能力，具有最小冗余。許多研究者正

2、在研究高效的特征提取算法。這些技術(shù)已經(jīng)成功的應(yīng)用在數(shù)據(jù)約簡，文本分類，文本分析中。 基于記憶的啟發(fā)式搜索是一種很有前景的智能計算工具，如Tabu搜索，在許多組合搜索問題中都表現(xiàn)了優(yōu)異的性能。然而，在信息系統(tǒng)和數(shù)據(jù)挖掘中，他的貢獻仍然遜于其他智能工具，如遺傳算法、神經(jīng)網(wǎng)絡(luò)。本文，我們提出了一種基于Tabu搜索的方法，稱為TSAR（Tabu Search for Attribute Reduction）來解決信息系統(tǒng)的屬性約簡問題。

3、TASR使用0-1變量來表示約簡過程中的解，粗糙集的依賴度函數(shù)用來度量解的質(zhì)量，TSAR的搜索過程是個長期記憶的高性能禁忌搜索，除了使用的鄰域搜索方法，TSAR還運用了廣泛性和集中性的搜索模式。 本文中的TSAR算法使用TS鄰域搜索來解決信息系統(tǒng)的屬性約簡問題，主要基于兩個主要概念：避免訪問已經(jīng)訪問過的解；接受下山移動方法跳出局部最優(yōu)。保留一些歷史信息使搜索進程更智能化，顯然，廣泛性和集中性機制通過保存實時的最優(yōu)約簡和每個屬性的