基于粗糙集的动态特征选择算法研究

董雪

关键词：粗糙集；动态；特征选择；信息量；可分辨矩阵；正域

１ 引言

所谓特征选择，顾名思义是从原始特征空間中筛选与任务相关的特征，剔除无关、冗余及噪声特征等［１］。 在大数据时代下，由于信息量急速增加，数据集的构成具有动态变化和不确定性的特征，传统特征选择方法普遍面临不能适应的问题［２］。 粗糙集理论作为一种数据分析理论，是一种处理不精确、不确定与不完全数据的数学方法，被广泛应用于知识发现、模式识别、生物学及数据挖掘等领域，使得应用粗糙集理论解决数据特征选择面临的上述不确定性问题成为可能。 本文主要对粗糙集理论下的动态特征选择方法进行研究和分析，总结现有的动态特征选择方法，并对动态特性选择发展趋势进行预测。

２ 相关概念

２．１ 粗糙集

信息系统 Ｓ ＝ （Ｕ，Ａ，Ｖ，ｆ），其中 Ｕ ＝ ｛ ｘ１ ，ｘ２ ，…，ｘｎ ｝是对象集，Ｘ?Ｕ，Ｕ ｜ Ａ 是 Ｕ 的一个划分，Ｘ 的上下近似分别定义为

２．２ 基于粗糙集的动态特征选择框架

与静态数据不同，动态数据常常在变化，且动态特征选择的算法实现难度更高。 基于粗糙集的动态特征选择是指对动态变化的数据进行特征选择。 目前，相关研究大都是基于增量方法来处理动态数据的变化，即充分利用历史信息，提高特征选择效率。 动态特征选择框架如图 １ 所示，相关学者研究的算法属于框架中的搜索策略步骤。

３ 粗糙集背景下动态特征选择算法

基于动态特征的选择，若仍使用经典的非增量特征选择来处理，则会导致运行速度较慢，因此，学者设计了许多增量特征选择算法去解决动态变化数据特征选择的问题，归纳总结出动态特征选择算法分为三类，即基于可分辨矩阵的动态特征选择［４］、基于信息表示的动态特征选择［５］ 和基于正区域的动态特征选择［６］

３．１ 。 基于可分辨矩阵的动态特征选择方法

３．１．１ 基本思路

主要思路是“以不变应万变”，即针对数据每次的变化，不须重新计算可分辨矩阵，只须在原来的可分辨矩阵上增加或删除列，并对新矩阵进行核特征的修正，可以大大减少计算量。 在实际应用中，将增加的新样本与原有样本比较， 可分辨矩阵随之增加列（行），对其他元素没有影响。

３．１．２ 研究进展

可分辨矩阵可以标识条件属性与决策属性之间的关系，自张春英等提出基于粗集理论中的可分辨矩阵的动态特征提取算法后，滕宝等［７］基于 Ｓ?粗集和可分辨矩阵提出一种动态特征选择算法，用来解决单向特征迁移集合的动态变化问题，但由于每添加一个样本就需要扫描一次可分辨矩阵，使算法的搜索空间大大增加。 基于此，钱文彬等［８］提出一种快速的动态特征选择矩阵算法，构造了简化矩阵，有效地缩小了算法的搜索空间；ＷＥＩ 等［９］ 基于可分辨矩阵，提出一种增量式动态属性特征选择； ＦＥＬＩＸ 等［１０］ 提出基于二进制的差别矩阵，使差别矩阵元素由 ０ 和 １ 组成，把存储空间缩小至原来的一半；ＸＵ 等［１１］ 更进一步地提出基于 ０?１ 整数规划的动态特征选择算法；在许多情况下，数据集往往通过引入一组数据而不是逐个引入单个对象来扩展，ＭＡ 等［１２］提出一种压缩的二进制可分辨矩阵，很好地解决了这个问题；景运革［１３］ 基于知识粒度提出一种高效动态特征选择算法，在此基础上，提出针对删除式动态变化的特征选择原理及算法；在大数据时代下，随着数据的维度不断增加，计算也随之复杂，ＺＨＯＵ 等把多维数据划分为多个子集，利用现有子集及它们的核进行计算，避免重复计算，降低了时间复杂度。

３．２ 基于信息 。 表示的动态特征选择方法

３．２．１ 基本思路

根据知识信息量或者属性重要度以及信息熵依次剔除无关特征，利用新增的对象对原有的信息量进行修正，利用原有的信息量的结果递归计算信息系统变化后的信息量，并有效利用上一次的特征选择结果很快地求出新的特征选择。

３．２．２ 研究进展

在信息系统不断变化的情况下，刘山等［１４］ 利用新增对象对原有信量进行修正，对原有信息量的结果进行递归计算，缩减了计算量，提高了效率；对于不确定信息系统，陈亮等［１５］定义了一种等价关系，以等价类决定属性的条件信息量来定义属性的重要度；针对多个对象被添加到一个决策表，ＬＩＡＮＧ 等［１６］ 提出一种基于信息熵的分组增量粗特征选择算法；王永生等［１７］以信息粒度为启发信息，提出一种使得提取效果有较好传承性的动态特征提取算法；对于不完备信息系统，大多数学者集中于研究动态增加时的特征选择。 基于此，董惠玉［１８］ 提出一种不完备信息系统的减少式特征选择算法；当只考虑已选特征和类别之间的动态变化信息量时，会使得特征选择的分类准确率下降，陈永波等［１９］ 结合已选特征与候选特征的交互相关性来选择相关特征，与此同时，剔除无关特征和冗余特征，提出一种基于动态相关性的特征选择算法．

３．３ 基于正区域的动态特征选择方法

３．３．１ 基本思路

此类方法不需要建立可分辨矩阵，只对等价类进行划分，降低了时间和空间复杂度。 首先计算原始数据和动态数据的正域，然后依据两种重要度及特征选择搜索策略分别设计相应的特征提取算法，最后基于启发性动态特征选择算法，即依据特征重要度来选择特征子集的元素。 比较动态数据提取特征前后的重要度变化情况，变化越大，说明重要度越高，就将该特征加入特征子集中，反之则不加。

３．３．２ 研究进展

最初相关学者仅基于信息系统的不可分辨等价关系来规定正域，随着粗糙集的逐渐成熟，有学者提出了很多基于粗糙集的动态特征选择算法，如张春英等［２０］针对集合元素的迁入与迁出，提出双向概率 ＰＳ?粗糙集，并在此基础上提出一种动态三支决策，有效提高提取特征的效率；但粗糙集只能直接处理离散化的数据，连续型数据进行离散化处理时会造成信息损失，ＳＵＮ 等［２１］ 根据模糊集只关注知识模糊性这一特点，提出了模糊决策粗糙集模型，为动态特征选择提供一个可以直接处理连续型数据的模型；在此启发下，针对大规模直觉模糊信息系统数据量大、特征维数高、动态性强等特点，ＺＨＡＮＧ 等［２２］ 基于直觉模糊粗糙集的相似关系和广义动态抽样理论，提出了一种广义的动态特征选择算法，同时解决了直觉模糊粗糙集无法处理大数据集的问题。

３．４ 三种方法的适用类型及优缺点

基于可分辨矩阵的动态特征选择方法、基于信息表示的动态特征选择方法和基于正区域的动态特征选择方法的适用类型及优缺点对比［２３］如表 １ 所列。

４ 发展趋势

针对动态数据中样本对象动态变化、特征维度动态变化及特征值的动态变化三种变化情形，可以设计出多种不同的算法。 基于此，可以考虑如何利用上述三种动态特征选择方法设计针对性算法，使效率更高。 在大数据环境下，很多信息系统是不完备的，但目前针对不完备的动态信息系统进行特征提取研究较少，这是目前动态特征选择的一大发展趋势。 由于模糊集具有只对知识的模糊性感兴趣的良好特性，因此，如何更好地利用粗糙集理论与模糊集理论的高效结合也是动态特征选择的又一研究方向。

５ 结束语

随着学者的不断探索和研究，动态特征选择算法越来越多，但由于数据的多样性及复杂性，使得现有算法性能不佳，动态数据特征选择方法仍面临巨大挑战。