邬阳阳，郭文强，汤建国，任 艳

（新疆财经大学计算机科学与工程学院，新疆乌鲁木齐830012）

经典粗糙集（Pawlak粗糙集）最初由波兰学者提出，是处理不确定性信息的强有力工具[1-4]，但建立在严格等价关系之上的Pawlak 粗糙集理论仅适用于处理离散型数据.为了有效处理实际应用中更为复杂的数据（多媒体数据、基因数据、金融数据等），一些学者将Pawlak 粗糙集模型进行拓展和延伸，提出许多新粗糙集模型，如：模糊粗糙集[5-6]、覆盖粗糙集[7-8]、邻域粗糙集[9-11]、决策粗糙集[12]、变精度粗糙集[13]、多粒度粗糙集[14]等.这些拓展粗糙集模型大大拓宽了粗糙集理论的适用范围，在诸如信息科学[15-17]、管理学[18-20]、金融[21-22]、医学[23-25]等领域得以广泛应用，其属性约简算法作为数据预处理的有效方法也受到国内外学术界的广泛关注.

属性约简也称特征选择，指的是从原始属性集合中选出具有代表性的属性子集，是粗糙集理论研究的重点内容之一.特征选择可以在不影响最终决策质量的前提下，有效去除数据的噪声和冗余特征，提高学习效率[26]. 目前，各国学者经过不断努力，基于概念格、决策树、随机森林、支持向量机、粗糙集等理论设计出各类特征选择算法. 其中，基于粗糙集理论的特征选择算法不仅可以求解最优或次优约简结果，而且能够在所选特征的基础之上构造出较高质量的分类器[27]，在模糊、不一致信息分析处理中表现出较强的数据处理能力. 随着人工智能、模式识别、数据挖掘等技术的迅速崛起，基于粗糙集的属性约简算法在数据处理中发挥了重要作用.

现阶段，粗糙集属性约简得以广泛研究，研究人员设计出很多高效的属性约简算法，其约简理论也逐步完善，但约简算法在运行效率、精确度、复杂数据处理等多方面还存在一些不足之处，有待于进一步研究.文献[28-30]对Pawlak粗糙集属性约简研究成果作了系统总结和分析，为研究粗糙集属性约简算法提供了有益借鉴.但作为粗糙集约简理论重要组成部分的拓展粗糙集模型属性约简算法在算法设计方面也取得了丰硕的研究成果，却尚未有文献对其进行系统梳理和分析. 针对上述问题，本文选取属性约简算法研究较为充分的几类拓展粗糙集模型，依据一定标准对各类模型的属性约简算法进行分类，并在此基础上按照某个相对清晰的研究主线对一些经典算法进行详细分析.

1 属性约简算法

粗糙集属性约简算法大致可以分为两类：一类是基于代数观的属性约简算法，其典型代表是基于正域的属性约简算法[31]和基于辨识矩阵的属性约简算法[32]；另一类是基于信息论的属性约简算法[33].粗糙集的研究者将这些经典属性约简方法或约简思想融入到拓展粗糙集属性约简算法的设计中，提出了一系列高效实用的属性约简算法.

1.1 模糊粗糙集属性约简算法

为了解决连续型和混合型数据离散化过程中信息损失的问题，Dubois和Prade利用模糊集理论和粗糙集理论在数据处理上的互补性提出了模糊粗糙集模型[5-6].模糊粗糙集在一定程度上拓宽了Pawlak粗糙集的应用范围，对复杂数据的处理有着重要意义.当前研究较为充分的模糊粗糙集属性约简算法主要有基于辨识矩阵、属性依赖度和信息观三类.

1.1.1 基于辨识矩阵的属性约简算法

基于辨识矩阵的属性约简算法是一类经典约简算法.尽管此类约简算法的时间复杂度和空间复杂度都比较高，但有着严谨的数学基础. 其主要设计思路是结合一些数理理论或智能算法从算法运行效率方面对经典约简算法进行优化或改进.基于辨识矩阵的模糊粗糙集属性约简算法首先由Tsang 等人[34]和Jensen 等人[35]提出，但此后的研究者主要对Jensen 等人提出的模糊粗糙集快速属性约简算法（FRQR）进行了改进. Jensen 等人提出模糊辨识矩阵定义，并用其设计出计算属性约简的启发式算法，时间复杂度为O( ||C2||U2)，但该算法在计算依赖度时会消耗大量时间，不适用于处理大规模数据.Anaraki等人[36]指出在多个属性子集的属性依赖度相等的情况下，用FRQR算法求得的最终约简结果未必是最优约简，于是将模糊粗糙依赖度与基于关联关系的启发式相结合，在FRQR算法的基础之上提出两类属性约简算法，但算法的最大时间复杂度仍不低于O( ||C2||U2).陈俞等人[37]则把随机抽样理论融入到模糊粗糙集约简算法的设计中，提出统计属性约简的概念，利用抽样方法计算估计值，并将估计值排序，设计出适用于大规模数据的序约简算法.相对于传统属性约简方法，该算法减少了时间和空间消耗，但约简精度有时会降低，时间复杂度为O( max(2k |C|2|U |), |C|2|S|2). 另外，Chen 等人[38]发现通过计算辨识矩阵中所有极小元素即可得到最优约简，而不必计算辨识矩阵中所有元素，并基于此改进了属性约简算法，运行效率得到进一步提高，时间复杂度降为O( ||C ||U2).Chen等人[39]指出上述属性约简算法多是从全局角度出发设计的，并不能刻画关键条件属性对特殊决策类的影响，所以从局部优化的角度出发，基于辨识矩阵设计出属性约简算法.该算法在克服全局约简算法缺点的同时也进一步提高了算法的运行效率，其时间复杂度为O( ||C ||U2).

1.1.2 基于属性依赖度的属性约简算法

基于属性依赖度的属性约简算法并非结构化方法，在某些特殊情况下无法得到真正约简. 但这种方法约简效率较高，是粗糙集属性约简算法的重要类型之一. 在模糊粗糙集理论中，这类约简算法主要是针对Shen等人[40]提出的算法在解空间搜索过程中时间复杂度过高的问题，运用不同方法对原算法进行优化，将时间复杂度从指数级降到平方级.Shen 等人将经典粗糙集中依赖度的定义扩展到模糊粗糙集中，给出模糊粗糙集的依赖度定义，并提出基于依赖度的模糊粗糙集属性约简算法（FRSAR），时间复杂度为O( ( |U|2+ |U |) 2 )，但该算法搜索整个解空间的时间复杂度为O(2||U). Bhatt 等人[41]借助紧计算域重新定义模糊粗糙集，提出基于模糊粗糙集紧计算域的属性约简算法，将搜索解空间的时间复杂度降为O( ||U2)，但改进后的算法并不能处理条件属性和决策属性均为连续型数值类型的决策表. 印勇等人[42]利用三角隶属函数模糊化决策表的连续属性，并从全部条件属性出发，利用依赖度去除不会影响决策表信息量的属性，达到了降低搜索解空间时间消耗的目的，算法的时间复杂度为O( ||U2). 周志平等人[43]指出文献[40]中定义的模糊算子并不严格，所以重新给出模糊近似算子的定义，并重新界定了模糊粗糙集相对约简的概念，在此基础上设计了模糊粗糙集属性约简算法.该算法提高了分类精度，为处理更为复杂的数据提供了新方法，搜索解空间的时间复杂度为O( ||U2). 王世强等人[44]对模糊粗糙集属性依赖度概念进行扩展，重新定义候选属性集和冗余属性集，并两次使用属性间依赖度这一概念设计出属性约简算法，有效减少了冗余属性，属性集依赖计算的复杂度从指数级下降为平方级，即从O(2||U)降低到O( ||U2).

1.1.3 基于信息观的属性约简算法

粗糙集在信息观下的表示与其代数表示是完全等价的. 另外，基于信息观表示的属性约简算法更具直观性，因此一部分研究者从信息观角度出发，设计了模糊粗糙集属性约简算法，主要研究思路是从多种信息熵出发，或对原有约简算法进行优化，或在信息观下对模糊粗糙集属性约简重新进行定义.Hu等人[45]引入信息测度来描述模糊等价关系，重新对混合数据的属性依赖度、约简以及相对约简进行定义，设计出处理混合数据的启发式属性约简算法.该算法首次从信息论角度研究模糊粗糙集属性约简问题，具有重要的理论意义，但文中使用的条件熵并不适用于广义模糊决策系统[46].另外，文献中定义的条件熵在一般模糊决策系统中并不满足单调性[47].为解决上述两个问题，Zhang等人[47]重新给出条件信息熵概念，并设计了相应的属性约简算法. 徐菲菲等人[48]把Pawlak 粗糙集中的条件熵、知识熵推广到模糊粗糙集中，从信息量角度度量模糊决策表的属性重要度，提出约简模糊决策表的启发式算法. 该算法在多数情况下能够得到最小约简. 徐菲菲等人[49]指出文献[48]中基于互信息的属性约简算法在数据属性较多时计算复杂度过高，所以在属性约简算法设计过程中采用最大相关性的评价标准和删除依赖度较高属性的方法设计出约简效率较高的算法. 潘瑞林等人[50]将α 信息熵概念引入到模糊粗糙集属性约简理论中，结合模糊相似关系重新定义了属性重要度，并以此作为启发信息设计出较为高效的属性约简算法，但文献中并没有对参数的取值原则进行详细探讨.

此外，一些研究者将多重聚类[51]、散度测度[52]、距离测度[53]、极大辨识对[54]、并行计算[55]、增量计算[56-57]等多种方法引入到模糊粗糙集属性约简理论中，从多个角度设计了模糊粗糙集属性约简算法.

1.2 覆盖粗糙集属性约简算法

Zakowski[7]于1983 年将Pawlak 粗糙集中的等价关系替换为覆盖关系，首先开启了覆盖粗糙集理论的研究工作. 同Pawlak 粗糙集模型相比，覆盖粗糙集模型较为复杂，其约简理论由两部分组成：第一部分是覆盖元约简，通过去除论域中代表知识粒的冗余元找到上、下近似集不变的极小覆盖；第二部分是覆盖族约简（属性约简），即删除集族中冗余覆盖.覆盖族约简是本文讨论的重点. 目前，研究较为广泛的覆盖粗糙集属性约简算法主要包括了基于辨识矩阵和信息观的两类.

1.2.1 基于辨识矩阵的属性约简算法

覆盖粗糙集模型类型较多，又有新模型不断被提出，导致一部分属性约简算法并不具有普遍性.基于辨识矩阵的属性约简算法在运行过程中需要消耗大量时间和空间，研究者多以降低时间复杂度为研究主线，对基于辨识矩阵的约简算法进行优化.Chen 等人[58]定义协调和不协调覆盖粗糙集决策信息系统，给出属性约简的充分必要条件，并将辨识矩阵应用到覆盖粗糙集约简算法设计过程中，算法的时间复杂度为O( ||U2× ||Δ2).Wang等人[59]定义了覆盖决策系统以及覆盖决策系统的相对约简，并对辨识矩阵进行改进，在此基础上提出覆盖粗糙集属性约简算法，时间复杂度小于O( ||U2× ||Δ2)，但该算法在约简过程中需要计算所有元素，增加了计算量，计算效率有待于进一步提高.Li等人[60]研究发现文献[58]中的算法在约简过程中并不需要计算所有元素，而只需求解极小元素就能得到决策信息系统的全部约简. 由此，给出求解极小元素的算法以及求全部覆盖的约简算法.该约简算法可以节约大量存储空间和运行时间，计算复杂度度降为O( ||U2× ||Δ ). 类似于文献[60]中的算法优化方法，Dong 等人[61]指出文献[59]中的算法在约简时仅需计算极小元素就可以求解所有约简属性，并设计出覆盖粗糙集属性约简算法，该算法最大时间复杂度为O( ||U2× ||Δ ). Wang 等人[62]利用覆盖粗糙集相关性质设计的属性约简算法减少了样本邻域的比较次数，达到了对文献[58]所定义的协调覆盖系统辨识矩阵与非协调覆盖系统辨识矩阵简化的目的，约简算法的时间复杂度为O( ||U2× ||Δ ). Tan 等人[63]引入新的矩阵和矩阵运算，借助新矩阵方法能够有效求解覆盖信息系统的最大和最小描述，降低了求解所有属性约简或最优属性约简的复杂度，算法 时 间 复 杂 度 为 O(U|2|C |+|U|2( |Δ |-i) ),与文献[58]中的约简算法相比，该算法的约简效率有了进一步提高.

1.2.2 基于信息观的属性约简算法

另一类重要的覆盖粗糙集属性约简算法是基于信息观点的约简算法.此类算法并没有明显研究主线，一部分算法是对Li等人[64]提出的算法进行改进，还有部分算法是通过引入其他理论进一步完善信息观下覆盖粗糙集的属性约简理论. Li等人通过定义信息熵、条件熵设计了针对协调决策表的属性约简算法，并基于限制条件熵提出不协调决策表的约简算法，最后还给出既适用于协调决策表也适用于不协调决策表的约简算法.这些算法都是Pawlak粗糙集约简理论在信息观下的自然推广. 覃丽珍等人[65]指出文献[64]中定义的三类信息熵（限制互信息、限制信息熵和限制条件信息熵）并不具备严格的非负性或单调性，因此重新给出三类信息熵的定义，并用其度量条件覆盖的重要性，设计了不协调覆盖决策系统的属性约简算法.该算法可以避免出现原算法无法度量条件覆盖重要度的现象. 夏秀云等人[66]引入覆盖交集方法，从条件信息熵角度探讨了协调决策表的相关性质，给出覆盖粗糙集属性约简的充分必要条件，并在信息观下提出约简协调覆盖粗糙集冗余或不必要属性的方法. 张燕兰等人[67]从信息量的角度提出不必要覆盖粗糙集、必要覆盖粗糙集和核心三个概念，并对覆盖协调集的判定定理和覆盖的重要度进行定义，从而设计出基于信息观的属性约简算法. 覃丽珍等人[68]将信息量这一概念引入覆盖粗糙集，在此基础上给出覆盖协调集和覆盖约简的判定定理，并用信息量度量覆盖的重要性，最后结合辨识矩阵方法设计出完备的覆盖约简算法.该算法在搜索过程中可以逐步删除冗余或不重要的覆盖，提高了算法的约简效率.

另外，一些学者结合正态分布测量误差[69]、相关族[70]、网络拓扑[71]、超图模型[72]、增量学习[73-74]等理论提出了其他类型的属性约简算法.

1.3 邻域粗糙集属性约简算法

2008 年，胡清华等人[11]在Lin[9]、Yao[10]所提理论的基础上，将邻域模型和粗糙集模型相结合，对邻域粗糙集模型进行详细阐述，正式提出邻域粗糙集模型.邻域粗糙集用邻域关系和距离替代Pawlak粗糙集中较为严格的等价关系，弥补了Pawlak 粗糙集由于数据离散化导致信息损失的缺陷.部分学者对邻域粗糙集属性约简进行了研究，现有邻域粗糙集属性约简算法的设计思路基本上是改进或优化胡清华提出的两类属性约简算法.

1.3.1 基于属性重要度的属性约简算法

第一类属性约简算法主要是从算法的时间复杂度这一方面对胡清华等人[11]提出的基于正域的属性约简算法进行改进.胡清华等人针对邻域粗糙集模型提出邻域粗糙集属性约简算法.该算法以属性重要度为选择条件，约简过程中需进行大量重复的邻域计算，时间复杂度为O( ||C ||U2)，约简效率并不理想.接着，胡清华等人[75]又设计出前向搜索邻域粗糙集属性约简快速算法（FARNeMF）. 此算法充分利用邻域粗糙集固有的数学性质，即设计算法时仅考虑负域中的样本，在一定程度上提高了计算速度，但约简过程中负域样本的邻域划分操作仍需消耗大量时间，导致算法时间复杂度并未降低，仍为O( ||C ||U2).为提高属性约简算法的效率，李三乐[76]对FARNeMF 算法进行了改进，新算法将计算相对核作为起点，并在属性约简过程中运用删除法，减少了属性约简的时间消耗.该算法不仅能够求得最小属性约简，效率也得到一定程度的提高，最大时间复杂度为O( ||C ||U2).为进一步降低算法的时间复杂度，Liu 等人[77]给出一种快速属性约简算法，该算法在进行约简操作前首先对样本进行划分，并在计算某个样本的邻域时省去与不相邻样本进行比较这一步骤，进一步减少了计算量，计算复杂度下降为O( ||C2||U ).另外，还有学者从约简精确度、邻域半径和算法适用范围等方面对基于正域的属性约简算法进行改进. 徐波等人[78]指出文献[11]中算法的邻域半径是固定不变的，这会使得约简结果的精确性和适应性受到影响. 于是，在信息权重的基础上提出加权依赖度，设计出基于加权依赖度的属性约简算法，约简结果的精确度得到了提高，但时间复杂度增大到O2 |C |-k)(k+1) |U|2)，其中k 为约简属性子集的属性数量. 段洁等人[79]将邻域粗糙集同多标记学习相结合，重新定义依赖度和下近似，并在FARNeMF算法的基础上设计出适用于多标记学习任务的前向贪心算法，时间复杂度为O(N2Lnlogn)（其中n为决策表中样本个数，N表示标记个数，L为特征属性个数）.

1.3.2 基于信息观的属性约简算法

第二类属性约简算法主要是在Hu 等人[80]提出的属性约简算法的基础上，从约简效率、约简精度或算法的适用范围等一个或几个方面进行优化或改进. Hu等人定义了邻域信息熵，引入邻域互信息的概念，并以邻域互信息为启发信息设计出属性约简算法.该算法从Pawlak粗糙集属性约简算法中获得启发，将信息熵这一概念引入到邻域粗糙集约简理论中，并对邻域互信息的性质进行详细探讨，为在信息观下研究邻域粗糙集属性约简理论做了开创性工作. 李少年等人[81]从邻域区间内决策属性值分布出发，考察其变化对信息熵的影响，提出信息观下不确定性的度量方法，同时在约简算法的设计中仅考虑负域内的样本，在一定程度上提高了算法的约简效率.续欣莹等人[82]定义了不一致邻域，利用相关性质加快信息熵的计算速度，并结合辨识矩阵设计出基于信息观的邻域决策系统属性约简算法，但文中没有说明算法在不同分类器下分类精度不同的原因.王光琼[83]将邻域条件熵和邻域近似精度结合提出组合信息熵这一概念，可以从知识不确定性和集合不确定性两个方面度量属性的重要程度，实验表明基于邻域组合熵的属性约简算法可以提高约简结果的精度.张宁等人[84]引入测度，结合邻域近似精度和邻域条件熵给出邻域近似条件熵的定义，并利用邻域近似条件熵的单调性设计出一种启发式算法.该算法能够克服单纯基于代数观或信息观的属性约简算法的缺点，但算法时间复杂度过高，不适合用来处理大规模数据.Lin等人[85]指出以往的邻域粗糙集属性约简算法仅适用于单标签学习任务，所以从不同认知角度（悲观、乐观、中立）重新定义了邻域信息熵以及相关概念，并提出优化函数来度量候选属性重要性的方法，进而设计出相应的属性约简算法.

除上述研究较为充分的两类邻域粗糙集属性约简算法外，还有学者结合布尔矩阵[86]、邻域区分度[87]、并行计算[88]、增量学习[89]、粒计算[90]等理论设计了属性约简算法.

1.4 决策粗糙集属性约简算法

Yao 等人通过将Bayes 风险决策思想引入到粗糙集模型中提出决策粗糙集[12]. 决策粗糙集在分类决策问题处理过程中表现出更强的抗噪声能力以及风险代价敏感性，一经提出就成为了粗糙集领域的研究热点. 由于引入概率阈值，决策粗糙集的决策域（正域或非负域）不再具备单调性，其属性约简理论相对复杂. 本文采用文献[91]和文献[92]的观点，即从决策粗糙集属性约简目标出发，将决策粗糙集属性约简算法大致分为两类：标准保持的属性约简算法和标准优化的属性约简算法.

1.4.1 标准保持的属性约简算法

标准保持的属性约简的基本思想是将属性约简视为不确定性度量的保持[92]. 这类算法主要从分析一些经典属性约简算法的不足出发，引入一些概念，并重新定义决策粗糙集属性约简. Li 等人[93]对比分析了经典粗糙集和决策粗糙集正域的单调性，发现决策粗糙集的正域随着属性的减少可能是递增的，并对基于正域的决策粗糙集约简重新进行定义，提出基于正域基数的非单调性启发式属性约简算法.黄国顺[94]指出文献[93]中的正域受阈值取值的影响，且仅进行集合基数比较可能会出现可信度高的正规则在约简后发生变化的情况. 基于以上原因，给出保正域不变的属性约简定义，并讨论了基于辨识矩阵的计算方法. 马希骜等人[95]为达到保证每个决策类的决策域不发生变化的目的，提出决策域（正域、非负域）分布保持的约简定义，并定义正域和非负域条件信息量，将其作为启发式信息以降低算法设计的难度，最后结合遗传算法设计出决策域保持的属性约简算法. Wang 等人[96]指出决策域具有非单调性，这使得基于决策域的启发式算法在约简过程中可能会出现过约简现象，于是引入(α,β)正域、边界域、负域保持约简的概念，并在属性约简定义中使用不同的阈值对，最后结合信息观设计出属性约简算法.Gao等人[92]提出极大决策熵概念，用其来测量不确定性，并定义了正域、边界域和负域保持约简.设计的约简算法不仅最大化了约简与类属性的相关性，也最小化了条件属性的冗余.

1.4.2 标准优化的属性约简算法

标准优化的属性约简算法设计的基础是将决策粗糙集属性约简看作是不确定性度量的优化问题.这类属性约简算法不仅包括用辨识矩阵、粒子群算法和回溯算法等方法优化属性约简过程的算法，还包括决策代价最小化的属性约简算法.Zhao等人[91]将经典粗糙集属性约简的辨识矩阵方法引入到决策粗糙集模型中，定义了基于正决策的辨识矩阵和一般决策的辨识矩阵，设计出正域保持的属性约简算法. 但该算法扩大了正域，有可能会增加决策风险.Stevanovic 等人[97]引入粒子群算法，基于规则退化和决策粗糙集属性代价设计出适应度函数，并通过把个体特征置信度加入到置信函数对原适应度函数进行改进，最后提出两个基于粒子群算法的决策粗糙集属性约简算法. 张智磊等人[98]从决策风险角度出发求解决策粗糙集的最小属性约简，设计出相应的适应度函数，并借助回溯搜索算法在全局搜索方面的优良性能提出决策粗糙集属性约简算法.该算法可以求解出较多最小属性约简. Jia 等人[99]通过分析现存决策粗糙集属性约简定义指出决策单调作为约简标准较为主观，所以将决策代价作为客观标准给出属性约简定义，并利用遗传算法和模拟退火算法求解最小化属性约简的代价，提出了决策粗糙集的最小代价属性约简算法. Bi 等人[100]指出文献[99]中的约简算法仅将决策代价作为启发信息，没有考虑所选属性的分类能力，于是引入互信息重新定义了属性重要度.同时该算法应用极大相关性和极大重要性近似计算条件属性和决策属性间的互信息，降低了计算的复杂度.

此外，一些学者或将决策规则和决策代价相结合[101]，或从多种代价出发[102]，或从提高属性约简效率出发[103]，或从局部视角出发[104-105]设计了决策粗糙集属性约简算法.

1.5 变精度粗糙集属性约简算法

为了有效处理噪声数据，Ziarko 于1993 年引入包含度β，将Pawlak 粗糙集模型中严格的包含关系替换为部分包含关系，提出了变精度粗糙集模型[13].作为一类特殊的概率粗糙集模型，变精度粗糙集模型中阈值的存在使其正域、边界域、负域并不具备单调性. 因此，Pawlak 粗糙集属性约简理论的一些经典约简思想和方法无法被直接引入到变精度粗糙集模型中.

早期的变精度粗糙集属性约简算法存在一定缺陷，约简算法的设计经历了一个探索和修正过程.Ziarko引入依赖函数，率先提出了变精度粗糙集的β约简定义[13]，是一项开创性工作，但β约简会产生约简异常现象. Kryszkiewicz[106]给出变精度粗糙集相对正域层次的属性约简定义，虽然该定义可以保证各个决策类的下近似不发生变化，但却没有考虑到阈值β 的区间概念，导致约简结果出现异常. Beynon[107]在Ziarko 约简定义的基础上，将原来固定阈值β扩展到一个区间，重新给出属性约简定义，提出了变精度粗糙集区间约简模型，但区间约简依然存在区间异常、分类异常等约简异常. Mi 等人[108]指出β 约简不能保持各个下近似不变，可能会导致错误约简，并提出变精度粗糙集β上（下）分布约简算法.此算法可以使每个决策类的上（下）近似保持不变，约简后导出的决策规则与原决策表导出的规则兼容，但它不适用于不完备决策表.为解决这一问题，赵亚娣等人[109]基于相容关系定义了β上（下）分布约简，并利用差别矩阵构造出约简算法，但该算法在处理不协调决策表时会出现约简错误. 接着，林春杰等人[110]证明了β 上（下）分布约简的判定定理，并在改进的上、下分布辨识矩阵的基础上导出可辨识公式，进一步完善了不完备决策表的约简理论.另外，曾子林等人[111]给出约简算法应满足的四条性质，又从逻辑角度出发重新对变精度粗糙集理论进行解释，并在此逻辑解释下提出变精度粗糙集的上（下）分布约简算法. Liu 等人[112]从正域集合覆盖的角度研究约简算法，提出基于集合覆盖的约简算法，用来求解β 下分布约简，为变精度粗糙集属性约简问题的研究提供了新思路.

同时许多研究者从其他角度研究变精度粗糙集的属性约简问题，提出多种其他类型的变精度粗糙集属性约简算法[113-118]，进一步丰富了变精度粗糙集属性约简理论.

2 问题和方向

拓展粗糙集是Pawlak 粗糙集在实际应用中的自然推广，拓宽了粗糙集在处理现实数据方面的应用范围，为有效处理不同场景下不确定性信息提供了强有力的理论支撑.作为粗糙集主要研究内容之一的属性约简在拓展粗糙集模型中也得以广泛研究，但同Pawlak 粗糙集属性约简理论相比，拓展粗糙集属性约简理论并不完善，同时也为了有效应对各类复杂数据处理过程中存在的挑战，仍需对拓展粗糙集属性约简算法作进一步研究.

第一，借鉴Pawlak 粗糙集属性约简算法的设计思路和算法思想完善拓展粗糙集属性约简理论.许多拓展粗糙集属性约简算法的设计方法是直接从Pawlak 粗糙集借鉴而来的，如基于信息熵、辨识矩阵、正域等的属性约简方法. 因此，一方面对Pawlak粗糙集属性约简算法进行研究，将一些较为有效的思想方法推广到各类拓展粗糙集是研究拓展粗糙集属性约简算法的常规且重要的研究思路.同时也要注意一部分拓展粗糙集模型也有其特殊性，比如：覆盖粗糙集模型具有多样性，决策粗糙集并不具备Pawlak 粗糙集所具有的单调性. 所以简单的平移策略并不适用于所有拓展粗糙集模型约简算法的设计. 在设计属性约简算法时，要根据模型的具体性质设计相应的属性约简算法. 另一方面，粗糙集属性约简算法是NP-hard 问题[119]，借助一些优化方法（模拟退火算法、粒子群算法、人工鱼群算法等）对拓展粗糙集的经典属性约简算法进行优化或改进也是拓展粗糙集属性约简理论的一个研究方向.

第二，大数据的处理.在当今信息爆炸的时代，大数据呈现出5V特征（数据量大、数据结构复杂、数据呈动态变化、数据的价值性、数据的真实性）.将粗糙集应用于大数据预处理，对机器学习、模式识别以及金融、管理等各个领域的数据分析具有重要意义. 一些学者将拓展粗糙集模型与并行计算、增量学习、粒计算等理论结合，主要针对大数据三个特征（海量、动态、多样）中的某个特征设计出相应的属性约简算法，这些算法较之于基于Pawlak 粗糙集的属性约简算法更适合处理大数据，但算法却不适用于具备多种特征的复杂数据，所以融合多种理论设计出适用于复杂数据处理的属性约简算法是一个亟需解决的问题.

第三，特殊类型数据的处理. 现实生活中的应用场景复杂，需要处理的数据类型多样，而以往设计的多数属性约简方法并不适用于某些特殊类型的数据.这在一定程度上限制了粗糙集属性约简理论在处理实际数据中的使用范围. 根据数据的具体特征，选择合适的粗糙集模型，并结合其他理论方法设计相应的属性约简算法对于实际问题的解决以及粗糙集属性约简理论的完善都有着重要意义，如：部分标记数据在现实应用中广泛存在，如何结合半监督学习的一些理论设计出适用于部分标记数据的高效属性约简算法是一个热点研究问题.

3 结语

粗糙集模型的属性约简算法在理论研究方面取得了丰硕成果，在实际数据处理中也发挥了巨大作用.本文详细总结分析了模糊粗糙集、覆盖粗糙集、邻域粗糙集、决策粗糙集、变精度粗糙集等几类拓展粗糙集模型的经典属性约简算法和一些最新研究成果，并对拓展粗糙集属性约简的未来研究方向进行了展望，或为拓展粗糙集模型属性约简算法的研究提供借鉴.