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

【關(guān)鍵詞】粗糙集；屬性約簡；正區(qū)域；信息熵；差別矩陣

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

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

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

經(jīng)過國內(nèi)外學者幾十年的不斷努力，研究出很多屬性約簡算法，它們大部分是啟發(fā)式算法。

1.1 基于正區(qū)域的屬性約簡算法

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

基于正區(qū)域的屬性約簡算法的步驟：

1.4 其他屬性約簡算法

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

2 有待進一步研究的內(nèi)容

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

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

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

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

參考文獻

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

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

[3]張文修，吳偉志，梁吉業(yè)等.粗糙集理論與方法[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]苗奪謙，胡桂榮.知識約簡的一種啟發(fā)式算法[J].計算機研究與發(fā)展， 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]葉東毅，廖建坤.基于二進制粒子群優(yōu)化的一個最小屬性約簡算法[J].模式識別與人工智能，2007，20（03）：295-300.

[13]Ke L J，F(xiàn)eng 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-），女，湖南省桂東縣人。碩士學位。講師。研究方向為粗糙集理論、數(shù)據(jù)挖掘。

作者單位

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