基于粗糙集理论的属性约简算法

摘 要 在数据处理和智能信息中，基于粗糙集理论的属性约简是非常具有研究价值的。本文介绍了几种主要的属性约简算法，对他们的优缺点进行了概括和分析，并提出了进一步的研究内容。

【关键词】粗糙集；属性约简；正区域；信息熵；差别矩阵

粗糙集理论作为一种新的数学工具，是用于处理模糊、不确定，不完备信息的。它的主要思想是不需要提供知识库以外的任何信息，通过知识约简，所得到的新知识库分类能力不变。目前在机器学习、数据挖掘、智能控制，模式识别等多个领域，甚至几乎所有的信息科学的分支中，粗糙集理论都取得了较好的研究成果。

在粗糙集理论中，属性约简是非常的重要的内容。通常情况下，信息系统的属性集一般是很大的，但是对知识发现来说，并不是所有的属性都一样重要，有的属性绝对必要，有的属性相对必要，有的属性绝对不必要，如何在众多的属性中把不重要甚至冗余的属性去掉而不影响知识的分类，是属性约简的目的。经过属性约简，知识得到简化，而人们所需要的基本信息也没有丢失。人们一直都在寻求的目标是求得信息系统的一个最小属性约简，或者求得信息系统的所有属性约简。但遗憾的是属性约简的搜索优化过程是多约束多目标的，所以作为很早就已经被学者证明了的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