基于Rough Sets的特征选择研究进展

梁吉业，李超伟，魏巍

（1.山西大学 计算智能与中文信息处理教育部重点实验室，山西 太原 030006;2.山西大学 计算机与信息技术学院，山西 太原 030006）

基于Rough Sets的特征选择研究进展

梁吉业1，2，李超伟1，2，魏巍1，2

（1.山西大学 计算智能与中文信息处理教育部重点实验室，山西 太原 030006;2.山西大学 计算机与信息技术学院，山西 太原 030006）

特征选择是机器学习领域中的重要研究问题.作为一种重要的特征选择方法，属性约简正在受到越来越多的关注，在许多应用领域已经得到了广泛应用.文章对基于Rough Sets理论的特征选择算法作了系统的回顾和分析，具体包括启发式属性约简、基于区分矩阵的属性约简和扩展粗糙集模型的属性约简三个方面.此外，论文还给出了粗糙特征选择算法的几种常见应用，并对该领域的进一步发展进行了展望.

特征选择;粗糙集;属性约简;区分矩阵;启发式搜索

0 引言

2011年出版的《Science》杂志在社论中指出，“数据推动着科学的发展”［1］.随着计算机技术、网络技术的不断发展和普及，数据的采集和存储变得更为便利和快捷，这使得数据的规模不断增长，形成了高维海量的数据信息.这些数据中承载着大量的有效信息，在方便人类发展的同时却也为许多应用领域带来了更严峻的挑战，即如何保留复杂数据中的有效信息以及如何从这些数据发现有价值的知识［2－3］.美国学者Mjolsness和Decoste［4］在《Science》杂志上系统地分析了机器学习在科学研究各个阶段扮演的重要角色，认为机器学习技术能够在各个方面协助众多研究者加速科研进程.

特征选择是机器学习领域中一种常用的数据处理技巧，也是该领域中一个极具挑战性的问题.特征选择通过消除无关和冗余特征，来提高知识发现的效率以及改善分类器的性能.波兰学者Pawlak提出的粗糙集理论（Rough Sets Theory）［5］是一种相对较新的处理不确定和不精确信息的软计算工具，并已广泛应用于构造特征选择算法，逐渐成为一种重要的特征选择理论框架.基于粗糙集理论的特征选择称为属性约简，它是在保持原始数据的属性区分能力不变的前提下，选择具有最小特征（属性）数的特征子集.

由于粗糙集理论思想新颖、方法独特，众多研究者在近二十年里发展了大量的、可行的、有效的属性约简算法［6－8］.Skowron给出了基于区分矩阵的方法来求解给定信息系统的所有约简，但由于求解所有约简是一个NP-Hard问题［9］，众多研究者进行了更为系统的研究.比如，针对处理大规模数据集计算耗时过大的问题，许多学者提出了启发式的搜索机制来寻找一个单一的约简结果，从而有效降低计算代价.许多基于不同目标函数定义的启发式约简算法被提出，这些算法从许多不同的角度来寻找满足目标函数的约简结果.此外，其他的一些学者通过进一步分析区分矩阵的定义，构造了新的区分矩阵，并在此基础上提出了许多新的基于区分矩阵的属性约简算法.在粗糙集理论的发展中，为从各类数据中获取有用知识，众多学者在经典的Pawlak粗糙集模型基础上，拓展了新的粗糙集模型（模糊粗糙集、优势关系粗糙集、决策理论粗糙集、变精度粗糙集等）.基于拓展的粗糙集模型，相应的属性约简算法都有相应的研究成果.

随着粗糙集理论的快速发展，针对粗糙特征选择算法的研究在理论和应用上都已取得了很多成果.本文的主要目的是从特征选择的视角对粗糙集理论中的属性约简算法进行系统的分析.本文回顾并总结了已有的研究成果，并指出了进一步的研究方向，希望进一步推动并促进这一领域的研究工作.

1 粗糙特征选择算法

属性约简是粗糙集理论的核心概念之一，它是在保持原始数据的属性区分能力不变的前提下，选择具有最小特征（属性）数的特征子集.经典的属性约简定义需要满足两个条件：（1）选择到的属性子集与原始的属性集具有相同的区分能力;（2）选择到的属性子集中不存在冗余的属性.基于该定义，许多学者发展了各种各样的约简算法.本节从三个方法阐述已有的属性约简的研究成果，分别是启发式的属性约简、基于区分矩阵的属性约简和拓展粗糙集模型中的属性约简算法.

1.1 启发式属性约简算法

问题求解中为减小搜索范围而需要利用某些已知的、有关具体问题领域的特性信息，这种信息叫做启发式信息，利用启发信息的搜索方法叫做启发式搜索方法.由于该方法实现过程比较简单而且快速，在实际中应用非常广泛，如向前（向后）贪婪选择、Relief方法等［10－11］.但是，启发式搜索方法作为一种近似算法，通常不能得到最优解，只能得到近似于最优解的解.随着粗糙集理论的提出以及对属性约简方法的深入探索，一些学者将启发式搜索方法引入到属性约简的求解中，构造了启发式属性约简的求解机制.需要指出的是启发式属性约简算法得到的约简结果可能具有冗余属性，可通过一个回溯的过程予以消除.

Hu和Cercone将启发式搜索方法引入到属性约简的求解中［12］，提出了基于正区域的启发式属性约简算法.该算法将属性的重要度作为启发式信息，属性的重要度定义为去掉该属性后正区域变化的大小.该算法比较简单、直观，以核属性为求解约简结果的出发点，按照属性的重要度从大到小逐个加入属性，直到约简结果的属性依赖度与原始属性的属性依赖度相同为止.为删除所得约简结果中的冗余属性，该算法接着检查所得结果中的每个属性，如果删除该属性后约简结果的属性依赖度不变，则表明该属性是冗余的，进而删除该属性.

熵是起源于经典热力学中的一个概念，用于度量系统的无序和混乱程度.Shannon将熵引入到度量离散型随机变量的随机性大小，称为信息熵（Shannon熵）.随着粗糙集理论的发展，信息熵已经被广泛应用于度量粗糙集意义下信息系统的不确定性.王国胤等从信息论的角度分析了粗糙集属性约简［13－14］，并提出了基于Shannon条件熵的决策表启发式属性约简算法.该算法基于Shannon条件熵来构造属性重要度，以决策表核属性集为起点，逐次选择属性重要度最大的属性添加到核属性中，直至满足得到的约简结果的条件熵与原始所有条件属性的熵相等为止.考虑到Shannon熵并不能用于度量粗糙集的模糊性，梁吉业等将互补熵引入到粗糙集理论中［15－16］.互补熵不仅可以用于度量一个粗糙集的模糊性，也可以度量信息系统的不确定性.基于互补熵设计的启发式属性约简算法主要通过保持给定目标决策的条件互补熵不变，来寻找相应的约简结果［15－16］.此外，从知识含量的角度，钱宇华等根据等价类中可区分对象的对数提出了组合熵的概念［17］，并设计了基于组合熵的启发式属性约简算法.该算法可以有效地删除冗余属性，得到满足目标决策的条件组合熵不变的属性子集.通过分析条件属性与决策属性之间的互信息，苗夺谦等将添加某个条件属性引起的互信息的变化大小作为属性重要量［18］，从信息的角度，提出了一种基于互信息的知识相对约简的启发式属性约简算法.

上述的启发式约简都致力于降低粗糙特征选择过程中的计算耗时，提高计算效率，并取得了一定的研究成果.近年来，随着信息技术及数据处理工具的迅速发展，大规模高维数据集的不断涌现为粗糙特征选择技术提出了更严峻的挑战.为此，刘少辉等通过深入分析粗糙集理论中不可区分关系的性质，给出了一种新的快速计算正区域的方法;并在此基础上设计了正区域的渐增式计算方法，进而提出了一种高效的属性约简算法［19］.比较原有的启发式约简算法，该算法可找到给定决策表的一个完备约简（Pawlak约简）.徐章艳等通过将基数排序思想引入到等价划分的求解中，提出了一种时间复杂度为 max（OC｜C｜｜u｜，O（｜c｜2｜u／c｜）λ）的快速属性约简算法，有效地降低了约简求解的计算耗时［20］.刘勇等通过证明不协调对象与正区域的等价关系，提出了基于Hash的正区域的求解算法，并在此基础上设计了基于二次Hash的属性约简算法［21］.较原有的约简算法，上述几种高效算法在时间和空间复杂度上都取得了了一定程度的优化.

为进一步有效提高启发式属性约简的计算效率，钱宇华和梁吉业等［22］提出了一种基于正向近似的属性约简加速器，并将加速器应用到启发式属性约简算法（包括文献［18-19］中的算法）中，设计了一系列的属性约简加速器算法.值得指出的是，这是一种通用的启发式属性约简加速器.文献［12，14-15，17］中的约简算法或者是基于其他属性重要度构造的启发式约简算法均可以借鉴文献［22］中的方法设计新的加速算法.加速算法不仅可以有效降低约简求解过程中的计算耗时，而且可以找到与原算法相同的约简结果.文献［22］从理论分析和实验结果都有效证明了加速算法的可行性和高效性.此外，在文献［23-24］中，钱宇华和梁吉业进一步设计了含缺失数据决策表的属性约简算法加速器，有效提高了含缺失数据意义下求解属性约简的计算效率.

由于实际应用中，真实的数据往往是不断增加的，当数据动态增加后，数据库的更新会直接导致其信息结构的变化.类似地，在基于动态数据表的属性约简求解中，数据表的不断更新同样会影响相应的约简结果.然而，重新执行相关属性约简算法显然是耗时的，为了高效的获取新的约简结果，一些学者提出了增量式的属性约简求解算法.胡峰和王国胤等设计了基于正区域的增量式属性约简算法，该算法主要通过分析新增对象后正区域的变化来更新原有的约简结果［25］.此外，通过讨论新增单个对象后条件类和决策类的变化，梁吉业和魏巍等分析了互补熵的增量机制［26］，并给出了一种基于条件互补熵的增量核求解算法，该算法可以得到信息观下的增量属性核.

1.2 基于区分矩阵的属性约简方法

区分矩阵是粗糙集理论中的核心概念之一.Skowron和Rauszer利用任意两个对象之间的不同属性描述数据集中蕴涵的分类知识，提出了区分矩阵的概念［27］.并提出了基于区分矩阵来求解信息系统的完备约简的方法.该方法可以得到给定信息系统的所有约简，但是计算耗时过大，众多学者发展了一系列的基于区分矩阵的属性约简算法.通常基于区分矩阵的粗糙集特征选择算法分为两类：一类是通过构造区分函数，并计算区分函数的蕴涵来获取约简结果，这类算法可以得到给定信息系统的所有约简，是一种完备算法;另一类是基于区分矩阵来构造属性的重要度，进而设计相应的属性约简算法.

Skowron提出的区分矩阵是基于信息系统构造的，Hu和Cercone将区分矩阵的概念扩展到决策表中［28］，定义了决策表的区分矩阵，也是目前应用较为广泛的一种区分矩阵.叶东毅等分析了利用Hu的区分矩阵求解不协调决策表的核属性时会得不到正确的核，并改进了Hu的区分矩阵［29］.但是该方法在定义区分矩阵中的矩阵元素时增加了计算复杂度.为此，杨明等提出了新的求解区分矩阵的方法，该方法的空间复杂度低于Hu和叶东毅的区分矩阵，且计算量小于叶东毅的区分矩阵，为粗糙集中核的求解提供了新的理论基础［30］.针对上述几种区分矩阵，王国胤等在文献［31］中对不同的区分函数得到的核属性之间的包含关系作了进一步的讨论.

针对利用区分矩阵来处理大规模数据耗时过大的缺陷，王珏等对Skowron定义的区分矩阵进行简化，使得每个属性在区分矩阵中只出现一次，称为Quasi－区分矩阵;并通过给定数据表中属性的排序设计了基于Quasi-区分矩阵的属性序算法［32］.该方法在面向用户的数据挖掘中具有重要的意义［33］.胡峰、王国胤等提出了属性序下的处理海量数据的快速属性约简算法［34］.该算法通过融入分治的思想，提出了分治策略的属性约简算法，极大地提高了给定属性排序下的约简求解的计算效率.

针对动态增加数据集，一些学者也提出了许多基于区分矩阵的增量式属性约简算法.杨明等提出一种基于改进区分矩阵的核属性增量式更新算法［35］，该算法在更新区分矩阵时仅需插入某一行和某一列，或删除某一行并修改相应的列，因而提高了属性核的更新效率，该算法可以得到代数观下决策表的增量属性核.在此基础上，杨明等提出了一种基于改进区分矩阵的属性约简增量式更新算法，该算法可通过快速更新区分矩阵［36］，利用原有的属性约简有效地进行属性约简的增量式更新，可提高属性约简的更新效率.

1.3 基于扩展粗糙集模型的属性约简方法

实际应用中，数据库中的数据不只规模会不断增大，所存储数据也会越来越复杂.例如：数值型、名义型、模糊型、区间型、集值型、缺失数据、噪音数据、不完备数据等经典粗糙集理论无法解决的问题.为此在近年来的研究中，出现了许多粗糙集的扩展模型，如：邻域粗糙集、模糊粗糙集、决策粗糙集、变精度粗糙集、优势关系粗糙集、基于覆盖的粗糙集等各种拓展的粗糙集模型.

Pawlak的经典粗糙集理论是采用等价关系将论域中的对象粒化为若干等价类，作为描述论域中目标概念的基本信息粒子.对给定的目标概念，定义了两个等价类的并集：下近似和上近似来逼近这个目标概念［37］.由于Pawlak粗糙集要求由等价关系的基本信息粒子完全被包含或完全不被包含于待逼近的目标概念，这导致该模型在应用中不能有效地处理数据库中的噪声数据.为了解决Pawlak粗糙集模型对数据噪声敏感的问题，Ziarko提出了变精度粗糙集模型的定义［38］.变精度粗糙集重新定义了Pawlak粗糙集的上下近似，即，一个等价类中只要大部分样本被包含在待逼近的粗糙集中，这个等价类就可以被划入粗糙集的正域;反之，这个等价类就应该被划入粗糙集的负域.变精度粗糙集降低了噪声数据对待逼近目标概念的影响，从而方便了求解带有噪声数据的数据表的属性约简结果.变精度粗糙后来被进一步拓展为Bayes粗糙集模型和概率粗糙集模型［39－41］，这两种模型都是从概率论的视角出发来处理不确定性的.Yao和Zhao在文献［42］中提出了决策理论粗糙集模型，该理论改变了以决策正域为评价机制的思想，而以多数决策原则产生的总的决策错误率为标准来定义属性的评价标准［43］.基于决策理论粗糙集模型，Yao等设计了基于正区域的属性约简算法［44］.

由于Pawlak粗糙集、决策理论粗糙集模型以及变精度粗糙集等都只能处理符号数据，对于数值型数据只能先进行离散化处理才能利用上述模型来求解属性约简.为此，一些学者将邻域系统的概念引入粗糙集理论，提出了邻域粗糙集模型［45－46］，邻域系统的引入使得Pawlak粗糙集可以有效处理数值数据.胡清华等在文献［47-48］中重新定义并解释了邻域粗糙集模型，提出了基于邻域粒化和粗糙逼近的数值属性约简算法.王熙照等为解决粗糙集对模糊值属性处理能力较弱的缺陷，提出了模糊不可区分关系的概念.并将约简、核、相对约简与相对核及规则等概念推广到模糊环境下，提出了一种有效的模糊信息表的启发式算法［49］.为有效利用粗糙集理论来处理混合数据.胡清华等［50－51］等将Dubois和Prade［52］的模糊粗糙集引入到属性约简中，提出了模糊粗糙集背景下的相对正域、信息量等定义，并将其用于特征子集的评价，设计了面向混合数据的粗糙特征选择算法.

此外，研究者还针对不同的问题提出了一些其它的粗糙集模型，例如优势关系粗糙集模型［53］、多粒度粗糙集模型［54］、基于覆盖的粗糙集模型［55－56］等等，并基于这些粗糙集模型发展了相关的属性约简算法.这些研究成果对开拓粗糙集理论的应用具有重要的意义.

粗糙集理论由于其在知识发现中的应用而受到广泛的关注，迅速发展为一种处理模糊、不确定信息的软计算工具.粗糙特征选择算法已被广泛应用于许多领域，作为粗糙集理论中的关键问题之一，下一节我们将列举几种代表性的应用进行评述.

2 粗糙特征选择算法的应用

基于粗糙集理论的特征选择已广泛应用于许多领域，本节简要介绍其在入侵检测、医疗诊断、故障诊断和图像处理几个方面的一些研究成果.

2.1 入侵检测

入侵检测指对计算机或计算机网络系统的攻击行为进行检测，通常有误用检测和异常检测两类方法.在入侵检测的过程中，利用基于粗糙集的特征选择算法，对提取的网络特征进行选择后，再通过支持向量机进行分类训练，不仅可以减少计算量，而且克服了特征重要度衡量指标制定过程中的主观随意性.蔡忠闽等［57］将粗糙集理论引入入侵检测中的进程正常模型的建模过程，利用基于粗糙集的特征选择方法对训练数据集进行简化，然后基于特征子集生成预测规则集.将基于此模型的异常检测算法用于实时检测，对系统性能的影响很小，是一种高效低负荷的检测方法.文献［58］针对入侵数据量大、特征数目繁多、连续性属性多的特点，引入邻域粗糙集约简模型，构造了一种基于邻域粗糙集模型和粒子群优化的特征选择算法，仿真实验证明了该特征选择方法的有效性.

2.2 医疗诊断

随着医疗技术的进步和各种医疗诊断设备的发展，医疗诊断中出现了空前增长的海量医学数据，这些数据通常具有不完整、不确定、冗余等特点.因此，利用先进的计算机和信息处理技术等综合开发可有效利用海量医疗数据信息，并实现诊断准确率高的智能医疗诊断系统，已成为当今医疗事业发展的一个至关重要的研究课题.而粗糙集理论的特点之一就是具有良好的数据处理能力，为此众多学者将粗糙集理论应用并拓展到处理各种类型的医疗数据中，并取得了成功的研究成果.Nakayama等将经典粗糙集模型拓展到处理连续属性取值的医疗数据（糖尿病人病变数据）的分析中［59］，建立了相应的规则提取机制，并对实际数据进行了有效的预测.此外，通过构建相关的医疗知识库，基于粗糙集理论进行属性约简，从而降低诊断难度，提高诊断速度.Thangavel和Pethalakshmi基于模糊粗糙集提出一个从信息系统中进行特征选择的快速约简算法［60］，并对大规模医疗数据库的实际数据进行测试，有效验证了该算法的有效性和可行性.

2.3 故障诊断

在诊断过程中，描述机器运行的特征很多，有些特征是相关的，有些是独立的.相关特征往往会产生冗余信息，同时会增加计算工作量，需要加以消除，基于粗糙集的特征选择正好为去除这种冗余特征提供了有效的工具.Tay等将基于粗糙集的特征选择应用于柴油机的故障诊断中取得了较好的应用效果［61］.Haiying等提出了基于粗糙集理论的变电站分层错误诊断新方法模型，也取得了较好的应用［62］.

2.4 图像处理

目前，粗糙集理论与计算机图像处理的结合已经成为计算机图像处理的一个新的研究方向.利用粗糙集理论可对图像特征进行约简，从而达到对图像特征进行降维的目的.Swiniarski将基于粗糙集的特征选择应用于人脸识别过程中［63］，有效降低了图像特征的维数，且分类精度可以达到97.3%.胡静等［64］提出了一种基于相容关系粗糙集进行图形图像预检索的新方法，仿真实验有效验证了该方法的可行性，有效提高了图形图像的检索效率.文献［65］介绍了粗糙集属性约简在处理乳房X线照片中的相关应用.

从应用领域来看，基于粗糙集的属性约简除了在上述入侵检测、医疗诊断、故障诊断和图像处理外，许多学者还成功应用到文本分类［66］、网页分类［67］、基因分析［68］及网络支持系统［69］等领域，都取得了较好的效果.

3 总结与展望

本文从启发式属性约简、基于区分矩阵的属性约简和拓展粗糙集模型的属性约简三个方面总结了目前粗糙特征选择算法及其应用的研究进展.然而，随着目前信息处理中数据的海量性、高维性、动态性与多源性越来越突显，和经典特征选择算法一样，粗糙特征选择算法也遇到了前所未有的挑战.目前，主要应关注以下几个方面的研究.

（1）多源信息系统背景下的特征选择方法;

（2）基于多粒度认知策略设计海量数据的在线特征选择算法;

（3）基于特征选择的高维数据分析方法;

（4）动态数据的特征选择与动态更新方法.

［1］Staff S.Challenges and Opportunities［J］.Science，2011，6018（331）：692-693.

［2］Liu H，Motoda H.Feature Selection for Knowledge Discovery and Data Mining［M］.Boston：Kluwer Academic Publishers，1998.

［3］Tsumoto S.Automated Discovery of Medical Expert System Rules from Clinical Databases Based on Rough Set［C］／／Proceedings of Second International Conference on Knowledge Discovery and Data Mining，USA，1996，32：63-72.

［4］Mjolsness E，Decoste D.Machine Learning for Science：State of the Art and Future Prospects［J］.Science，2001，293（14）：2051-2055.

［5］Pawlak Z.Rough Sets：Theoretical Aspects and Reasoning about Data［M］.Boston：Kluwer Academic Publishers，1991.

［6］刘清.Rough集及 Rough推理［M］.北京：科学出版社，2001：88-136.

［7］张文修，吴伟志，梁吉业，等.粗糙集理论与方法［M］.北京：科学出版社，2001：128-209.

［8］张文修，仇国芳.基于粗糙集的不确定决策［M］.北京：清华大学出版社，2005：106-232.

［9］Lin T Y，Cercone N.Rough Sets and Data Mining：Analysis of Imprecise Data［M］.Boston：Kluwer Academic Publishers，1997.

［10］Kira K，Rendell L A.The Feature Selection Problem：Traditional Methods and a New Algorithm［C］／／Proceedings of 9th National Conference on Artificial Intelligence，1992：129-134.

［11］Kononenko I.Estimating Attributes：Analysis and Extension of Relief［C］／／Proceedings of European Conference on Machine Learning，1994：171-182.

［12］Hu X H，Cercone N.Learning in Relational Databases：A Rough Set Approach［J］.InternationalJournalofComputationalIntelligence，1995，11（2）：323-338.

［13］王国胤.决策表核属性的计算方法［J］.计算机学报，2003，26（5）：611-615.

［14］王国胤，于洪，杨大春.基于条件信息熵的决策表约简［J］.计算机学报，2002，25（7）：759-766.

［15］Liang J Y，Chin K S，Dang C Y，etal.A New Method For Measuring Uncertainty and Fuzziness in Rough Set Theory［J］.InternationalJournalofGeneralSystems，2002，31（4）：331-342.

［16］Liang J Y，Xu Z B.The Algorithm on Knowledge Reduction in Incomplete Information Systems［J］.InternationalJournalofUncertainty，FuzzinessandKnowledge-BasedSystems，2002，10（1）：95-103.

［17］Qian Y H，Liang J Y.Combination Entropy and Combination Granulation in Rough Set Theory［J］.InternationalJournalofUncertainty，FuzzinessandKnowledge-BasedSystems，2008，16（2）：179-193.

［18］苗夺谦，胡桂荣.知识约简的一种启发式算法［J］.计算机研究与发展，1999，36（6）：681-684.

［19］刘少辉，盛秋戬，吴斌，等.Rough集高效算法的研究［J］.计算机学报，2003，26（5）：524-529.

［20］徐章艳，刘作鹏，杨炳儒，等.一个复杂度为 max（O（｜C｜｜U｜），O（｜C｜2｜U／C｜））的快速属性约简算法［J］.计算机学报，2006，29（3）：391-399.

［21］刘勇，熊蓉，褚健.Hash快速属性约简算法［J］.计算机学报，2009，32（8）：1493-1499.

［22］Qian Y H，Liang J Y，Pedrycz W，etal.Positive Approximation：An Accelerator for Attribute Reduction in Rough Set Theory［J］.ArtificialIntelligences，2010，174（9-10）：597-618.

［23］Qian Y H，Liang J Y，Pedrycz W，etal.An Efficient Accelerator for Attribute Reduction from Incomplete Data in Rough Set Framework［J］.PatternRecognition，2011，44：1658-1670.

［24］钱宇华，梁吉业，王锋.面向非完备决策表的正向近似特征选择加速算法［J］.计算机学报，2011，34（3）：435-442.

［25］Hu F，Wang G Y，Huang H，etal.Incremental Attribute Reduction Based on Elementary Sets［C］／／Proceedings of the 10th International Conference on Rough Sets，Fuzzy Sets，Data Mining and Granular Computing，Regina，Canada，2005：185-193.

［26］梁吉业，魏巍，钱宇华.一种基于条件熵的增量核求解方法［J］.系统工程理论与实践，2008（4）：81-89.

［27］Skowron A，Rauszer C.The Discernibility Matrices and Functions in Information Tables［J］.IntelligentDecisionSupport：HandbookofApplicationsandAdvancesofRoughSetTheory，1992：331-362.

［28］Hu X H，Cercone N.Learning in Relational Databases：A Rough Set Approach［J］.InternationalJournalofComputationalIntelligence，1995，11（2）：323-338.

［29］叶东毅，陈昭炯.一个新的差别矩阵及其求核方法［J］.电子学报，2002，30（7）：1086-1088.

［30］杨明，孙志军.改进的差别矩阵及其求核方法［J］.复旦大学学报：自然版，2004，43（5）：865-868.

［31］Wang G Y.Attribute Core of Decision Table［C］／／Proceedings of the Third International Conference on Rough Sets and Current Trends in Computing（RSCTC2002），LNCS2475，USA，2002：213-217.

［32］Wang Jue，Wang Ju.Reduction Algorithms Based on Discernibility Matrix：The Ordered Attributes Method［J］.Journal ofComputerScienceandTechnology，2001，16（6）：489-504.

［33］Han S Q，Wang J.Reduct and Attribute Order［J］.JournalofComputerScienceandTechnology，2004，19（4）：429-449.

［34］胡峰，王国胤.属性序下的快速约简算法［J］.计算机学报，2007，30（8）：1429-1435.

［35］杨明.一种基于改进差别矩阵的核增量式更新算法［J］.计算机学报，2006，29（3）：407-413.

［36］杨明.一种基于改进差别矩阵的属性约简增量式更新算法［J］.计算机学报，2007，30（5）：815-822.

［37］YAO Y Y.Information Granulation and Rough Set Approximation［J］.InternationalJournalofIntelligentSystems，2001，16（1）：87-104.

［38］Ziarko W.Variable Precision Rough Sets Model［J］.JournalofComputerandSystemSciences，1993，40：39-59.

［39］Yao Y Y.Probabilistic Approaches to Rough Sets［J］.ExpertSystems，2003，20（5）：287-297.

［40］Slezak D.Rough Sets and Bayes Factor［C］／／Lecture Notes in Computer Science.Transactions on Rough Sets III，2005，3400：202-209.

［41］Slezak D，Ziarko W.The Investigation of the Bayesian Rough Set Model［J］.InternationalJournalofApproximateReasoning，2005，40：81-91.

［42］Yao Y Y，Wong S K M，Lingras P.A Decision-theoretic Rough Set Model［C］／／Proceedings of the Fifthe International Symposium on Methodologies for Intelligent Systems，Methodologies for Intelligent Systems 5，Knoxville Tennessee，1990：17-24.

［43］Yao Y Y，Wong S K M.A Decision Theoretic Framework for Approximating Concepts［J］.InternationalJournalof Man-MachineStudies，1992，37（6）：793-809.

［44］Yao Y Y，Zhao Y.Attribute Reduction in Decision-theoretic Rough Set Models ［J］.InformationSciences，2008，178：3356-3373.

［45］Lin T Y，Liu Q，Huang K J.Rough Sets Neighborhood Systems and Approximation［C］／／Proceedings of the Fifthe International Symposium on Methodologies for Intelligent Systems，Methodologies for Intelligent Systems 5，Knoxville Tennessee，1990：130-141.

［46］Lin T Y.Neighborhood Systems and Relational Database［C］／／Proceedings of the 1988 ACM 16th Annual Conference on Computer Science，1988：725-726.

［47］胡清华，于达仁，谢宗霞.基于邻域粒化和粗糙逼近的数值属性约简［J］.软件学报，2008，19（3）：640-649.

［48］Hu Q H，Yu D R，Liu J，etal.Neighborhood Rough Set Based Heterogeneous Feature Subset Selection［J］.Information Sciences，2008，178：3577-3594.

［49］王熙照，赵素云，王静红.基于Rough集理论的模糊值属性信息表简化方法［J］.计算机研究与发展，2004，41（11），1974-1981.

［50］Hu Q H，Yu D R，Xie Z X.Information-Preserving Hybrid Data Reduction Based on Fuzzy-Rough Techniques［J］.PatternRecognitionLetters，2006，27（5）：414-423.

［51］Hu Q H，Xie Z X，Yu D R.Hybrid Attribute Reduction Based on A Novel Fuzzy-Rough Model and Information Granulation［J］.PatternRecognition，2007，40：3509-3521.

［52］Dubois D，Prade H.Rough Fuzzy Sets and Fuzzy Rough Sets［J］.InternationalJournalofGeneralSystems，1990，17：191-208.

［53］Greco S，Matarazzo B，Slowinski R.Rough Approximation of A Preference Relation by Dominance Relations［J］.EuropeanJournalofOperationalResearch，1999，117（1）：63-83.

［54］Qian Y H，Liang J Y，Yao Y Y，etal.MGRS：A Multi-granulation Rough Set［J］.InformationSciences，2010，180：949-970.

［55］Zhu W，Wang F Y.On Three Types of Covering-based Rough Sets［J］.IEEETransactionsonKnowledgeandDataEngineering，2007，19（8）：1131-1144.

［56］Li T J.Generalized Fuzzy Rough Approximation Operators Based on Fuzzy Coverings［J］.InternationalJournalofApproximateReasoning，2008，43（3）：836-856.

［57］蔡忠闽，管晓宏，邵萍，等.基于粗糙集理论的入侵检测新方法［J］.计算机学报，2003，26：361-366.

［58］陈仕涛，陈国龙，郭文忠，等.基于粒子群优化和邻域约简的入侵检测日志数据特征选择［J］.计算机研究与发展，2010，47（7）：1261-1267.

［59］Nakayama H，Hattori Y，Ishii.Rule Extraction Based on Rough Set Theory and Its Application to Medical Data Analysis［C］／／Proceedings of IEEE SMC ’995’，1999：924-929.

［60］Thangavel K，Pethalakshmi A.Feature Selection for Medical Database using Rough System［J］.InternationalJournalon ArtificialIntelligenceandMachineLearning，2005，6（1）：11-17.

［61］Tay F E H，Shen L X.Fault Diagnosis Based on Rough Set Theory［J］.EngineeringApplicationsofArtificialIntelligence，2003，16：39-43.

［62］Dong H Y，Zhang Y B，Xue J Y.Hierarchical Fault Diagnosis for Substation Based on Rough Set［C］／／International Conference on Power System Technology，Kunming，China，2002，4：2318-2321.

［63］Swiniarski R W.Rough Sets Methods in Feature Reduction and Classification［J］.InternationalJournalonApplied MathematicsandComputerScience，2001，11（3）：565-582.

［64］胡静，曹先彬，王煦法.基于相容粗糙集的图形图像信息预检索［J］.计算机辅助设计与图形学学报，2002，14（3），242-246.

［65］Thangavel K，Karnan M，Pethalakshmi A.Performance Analysis of Rough Reduct Algorithms in Mammogram［J］.InternationalJournalonGlobalVisionandImageProcessing，2005，5（8）：13-21.

［66］卢娇丽，郑家恒.基于粗糙集的文本分类方法研究［J］.中文信息学报，2005，19（2），66-70.

［67］Jensen R，Shen Q.Fuzzy Rough Attribute Reduction with Application to Web Categorization［J］.FuzzySetsandSystem，2004，141：649-485.

［68］Saeys Y，Inza I，Lamnaga P.A Review of Feature Selection Techniques in Bioinformatics［J］.Bioinformatics，2007，23：2507-2517.

［69］Yao J T，Herbert J P.Web-Based Support Systems with Rough Set Analysis［C］／／KRYSZKIEWICZ M.Proceedings of International Conference on Rough Sets and Intelligent Systems Paradigms 2007，Lecture Notes in Artificial Intelligence 4585.Berlin：Springer，2007：360-370.

Advanced in Feature Selection Based on Rough Sets

LIANG Ji-ye1，2，LI Chao-wei1，2，WEI Wei1，2
（1.KeyLaboratoryofMinistryofEducationforComputationIntelligence＆ChineseInformationProcessing，ShanxiUniversity，Taiyuan030006，China;2.SchoolofComputer＆InformationTechnology，ShanxiUniversity，Taiyuan030006，China）

Feature selection is an important issue in the field of machine learning.As a significant feature selection algorithm，attribute reduction has attracted much attention and been applied in many areas.This paper systematically reviews and analyzes the feature selection algorithms based on rough set theory，which are introduced from three aspects：heuristic attribute reduction，attribute reduction based on discernibility matrix and reduction for generalized rough set models.In addition，the paper concludes some common applications of rough feature selection algorithms，and gives a prospect for the further development.

feature selection;rough sets;attribute reduction;discernibility matrix;heuristic search

TP18

A

0253-2395（2012）02-0211-08＊

2012-03- 10;

2012-03-19

国家自然科学基金（71031006）;国家973计划前期研究专项课题（2011CB311805）

梁吉业（1962－），男，山西晋城人，博士，教授，研究领域：计算智能、数据挖掘、机器学习等.E-mail：ljy＠sxu.edu.cn