基于粗糙集理論的屬性約簡算法

摘 要 在數據處理和智能信息中，基于粗糙集理論的屬性約簡是非常具有研究價值的。本文介紹了幾種主要的屬性約簡算法，對他們的優缺點進行了概括和分析，并提出了進一步的研究內容。

【關鍵詞】粗糙集；屬性約簡；正區域；信息熵；差別矩陣

粗糙集理論作為一種新的數學工具，是用于處理模糊、不確定，不完備信息的。它的主要思想是不需要提供知識庫以外的任何信息，通過知識約簡，所得到的新知識庫分類能力不變。目前在機器學習、數據挖掘、智能控制，模式識別等多個領域，甚至幾乎所有的信息科學的分支中，粗糙集理論都取得了較好的研究成果。

在粗糙集理論中，屬性約簡是非常的重要的內容。通常情況下，信息系統的屬性集一般是很大的，但是對知識發現來說，并不是所有的屬性都一樣重要，有的屬性絕對必要，有的屬性相對必要，有的屬性絕對不必要，如何在眾多的屬性中把不重要甚至冗余的屬性去掉而不影響知識的分類，是屬性約簡的目的。經過屬性約簡，知識得到簡化，而人們所需要的基本信息也沒有丟失。人們一直都在尋求的目標是求得信息系統的一個最小屬性約簡，或者求得信息系統的所有屬性約簡。但遺憾的是屬性約簡的搜索優化過程是多約束多目標的，所以作為很早就已經被學者證明了的NP-Hard問題，屬性約簡的研究是非常具有挑戰性的，是很值得我們去研究的。

1 幾種主要的屬性約簡算法的研究

經過國內外學者幾十年的不斷努力，研究出很多屬性約簡算法，它們大部分是啟發式算法。

1.1 基于正區域的屬性約簡算法

基于正區域的屬性約簡算法是Pawlak提出來的一種啟發式算法，也稱為Pawlak屬性重要度屬性約簡算法。這種方法的基本思路是首先定義一個屬性重要度的函數，計算出各個屬性的重要度，按屬性重要度的值從大到小選取屬性依次并入約簡集合中。這種求解方法具有重大的理論指導意義。該算法要求考察條件屬性集的冪集中的所有元素，優點是它找到的一定是最優屬性約簡或者次優屬性約簡，缺點是可能尋解失敗即不一定能找到，而且此方法計算速度慢，因為它的時間復雜度是指數級，不容易在計算機上實現，所以在實際應用中受到限制。

基于正區域的屬性約簡算法的步驟：

1.4 其他屬性約簡算法

除了不斷改進上述幾種比較主要的算法，為了得到更好的屬性約簡結果，提高算法的效率，學者們還提出了很多其它算法。例如基于遺傳算法的屬性約簡、基于免疫原理的屬性約簡，基于粒子群優化的屬性約簡、基于蟻群優化的屬性約簡，基于模糊粗糙集的屬性約簡，基于概念格的屬性約簡，增量式屬性約簡。

2 有待進一步研究的內容

（1）高效的屬性約簡算法。雖然學者們不斷研究出新的算法，想了很多辦法去提高屬性約簡算法的效率，但并沒有取得突破性的進展，所以新的更高效的屬性約簡算法仍然是值得研究的課題。

（2）對動態數據的研究。在現實生活中，人們會經常對數據庫中的數據進行添加、刪除和修改等操作，數據是不斷更新的。所以大型數據庫的動態知識約簡，也是目前需要重點研究的方面。

（3）適合大數據集的屬性約簡方法。現實生活中，隨著數據庫技術的迅速發展和廣泛應用，數據庫里的數據爆炸式增長，人們迫切需要能從海量數據中找出有用信息的有效約簡方法，處理大數據集需要占用大量內存空間，而恰恰在空間復雜度上，傳統的屬性約簡方法考慮不夠，目前并沒有非常合適處理海量數據的屬性約簡算法。努力尋找適合大數據集的屬性約簡方法，是很多研究人員努力的方向。

（4）目前屬性約簡一般處理的是離散值，當屬性是一個連續值時，研究如何將連續數據合理地離散化，以便更好的從信息系統中獲取知識也是很重要的。

參考文獻

[1]Pawlak Z.Rough sets.International Journal of Computer and Information Sciences，1982，11（01）：341-356.

[2]王國胤.Rough集理論與知識獲取[M].西安：西安交通大學出版社，2001.

[3]張文修，吳偉志，梁吉業等.粗糙集理論與方法[M].北京：科學出版社，2001.

[4]Wang S K M，Ziarko W.On Optimal Decision Rules in Deci-sion Tables[J].Bulletin of Polish Academy of Sciences，1985，33：693-676.

[5]Pawlak Z.Rough Sets：Theoretical Aspects of Reasoning about Data.Boston：Kluwer Academic Publishers，1991.

[6]Skowron A，Rauszer C.the discernibilinity matrices and functions in information systems. In：R.Slowincki（ed），Intelligent decision support-handbook of applications and advances of therough sets theory.Dordrecht. Kluwer Press，1992，331-362.

[7]Hu X H，Cercone N.Learning in relational databases：a rough set approach. International Journal of computational intelligence，1995，11（03）：323-338.

[8]苗奪謙，王玨.粗糙集理論中概念與運算的信息表示[N].軟件學報，1999，10（02）：113-116.

[9]苗奪謙，胡桂榮.知識約簡的一種啟發式算法[J].計算機研究與發展， l999，36（06）：681-684.

[10]Wroblewski J.Finding Minimal Reducts Using Genetic Algorithm. Proceedings of the International Workshop on Rough Sets Soft ComPuting at Second Annual Joint Conference on Information Sciences（JCIS95），1995，186-189.

[11]向長城，黃席樾，楊祖元，等.基于免疫算法的粗糙集知識約簡[J].計算機仿真，2007，24（11）：155-158.

[12]葉東毅，廖建坤.基于二進制粒子群優化的一個最小屬性約簡算法[J].模式識別與人工智能，2007，20（03）：295-300.

[13]Ke L J，Feng Z R，Ren Z G.An efficient ant colony optimization Approach to attribute reduction in rough set theoy. pattern Recogni tLett， 2008，29（9）：1351-1357.

[14]Jensen R， Shen Q. New approaches to fuzzy-rough feature selection[J].IEEE Transactions on Fuzzy Systems，2009，17（04）：824-838.

[15]王霞，張文修.概念格的屬性約簡與屬性特征[J].計算機工程與應用，2008，44（12）：1-4.

[16]楊明.一種基于改進差別矩陣的屬性約簡增量式更新算法[J].計算機學報，2007，30（05）：815-822.

作者簡介

周彤（1976-），女，湖南省桂東縣人。碩士學位。講師。研究方向為粗糙集理論、數據挖掘。

作者單位

湘南學院軟件與通信工程學院 湖南省郴州市 423000