基于多特定决策类的不完备决策系统正域约简

孔贺庆 张楠 岳晓冬 童向荣 于天佑

摘 要：现有的属性约简方法大部分关注决策系统中的所有决策类，而在实际决策过程中决策者往往仅关注决策系统中的一种或几种决策类。针对上述问题，提出基于多特定决策类的不完备决策系统正域约简的理论框架。首先，给出不完备决策系统单特定决策类正域约简的概念;第二，将单特定决策类正域约简推广到多特定决策类，构造了相应的差别矩阵及区分函数;第三，分析并证明了相关定理，提出基于差别矩阵的不完备决策系统多特定决策类正域约简算法（PRMDM）;最后，选取4组UCI数据集进行实验。在数据集Teachingassistantevaluation、House、Connectionistbench和Cardiotocography上，基于差别矩阵的不完备决策系正域约简算法（PRDM）的平均约简长度分别为4.00、13.00、9.00和20.00，PRMDM算法（多特定决策类中决策类数目为2）的平均约简长度分别为3.00、8.00、8.00和18.00。实验结果验证了PRMDM算法的有效性。

关键词：粗糙集;不完备决策系统;多特定决策类;正域约简;差别矩阵

中图分类号：TP181

文献标志码：A

英文标题

Abstract： The existing attribute reduction algorithms mostly focus on all decision classes in decision systems， but in actual decision process， decision makers may only focus on one or several decision classes in the decision systems. To solve this problem， a theoretical framework of positive region preservation reduction based on multispecific decision classes in incomplete decision systems was proposed. Firstly， the positive region preservation reduction for single specific decision class in incomplete decision systems was defined. Secondly， the positive region preservation reduction for single specific decision class was extended to multispecific decision classes， and the corresponding discernibility matrix and function were constructed. Thirdly， with related theorems analyzed and proved， an algorithm of Positive region preservation Reduction for Multispecific decision classes reduction based on Discernibility Matrix in incomplete decision systems （PRMDM） was proposed. Finally， four UCI datasets were selected for experiments. On Teachingassistantevaluation， House， Connectionistbench and Cardiotocography dataset， the average reduction length of Positive region preservation Reduction based on Discernibility Matrix in incomplete decision systems （PRDM） algorithm is 4.00， 13.00， 9.00 and 20.00 respectively while that of the PRMDM algorithm （with decision classes in the multispecific decision classes is 2） is 3.00， 8.00， 8.00 and 18.00 respectively. The validity of PRMDM algorithm is verified by experimental results.

英文關键词Key words： rough set; incomplete decision system; multispecific decision classes; positive region preservation reduction; discernibility matrix

0 引言

1982年由波兰科学家Pawlak提出的粗糙集理论[1-6]是一种重要的知识推理工具，作为一种求取集合近似的方法，该理论现已应用于机器学习、数据挖掘、模式识别、智能信息处理等领域。属性约简[7-13]是粗糙集理论的重要研究内容之一，属性约简通过删除冗余属性得到保持原决策系统某种分类信息不变的最小属性子集。

在决策系统中，若决策系统中条件属性值存在缺失，则称该决策系统为不完备决策系统。在现实生活中，存在一定数量的不完备信息。目前，相关学者对不完备决策系统下的属性约简进行了大量的研究，并将经典Pawlak粗糙集模型进行推广，取得了一系列成果： 1998年，Kryszkiewicz[14]在不完备决策系统下引入广义决策保持约简，介绍了相关决策规则的提取，并提出了基于差别矩阵[15]的广义决策保持约简方法; 2002年，Liang等[16]基于粗糙熵提出不完备决策系统的知识约简的启发式算法。2003年，周献中等[17]100-104在不完备决策系统下提出分配约简; 2005年，黄兵等[17]52-56提出不完备决策系统的上下近似约简，并给出求解所有决策类约简的差别矩阵方法; 2010年，Qian等[18]基于极大相容块在不协调不完备决策系统下提出上下近似约简的概念，并构造了相应的差别矩阵;2014年，Shu等[19]在不完备决策系统下提出通过评估候选属性重要度快速求取属性约简的方法;2015年，Qian等[20]提出动态不完备决策系统下基于紧凑差别矩阵的特征选择方法。

在属性约简中，正域约简针对所有决策属性的决策类，约简结果保证了整个决策系统约简前后正域不变。在实际应用中，决策者往往仅关注于决策系统中的一种或几种决策类。例如，在医疗诊断中，多种症状构成条件属性集，不同类型的疾病构成不同的决策值，医生通常建议根据不同类型的疾病寻找不同的发病原因。2005年，Chen等[21]提出决策系统中局部约简的概念，与定义决策系统所有决策类的约简不同，局部约简只定义部分决策类的约简; 2017年，Yao等[22]在完备决策系统下定义了特定决策类的正域约简，提出特定决策类正域约简的判定定理，并讨论了特定决策类正域约简与所有决策类正域约简的关系; 2017年，Liu等[23]在完备系统下提出第l决策类约简和β约简的概念，并给出了基于差别矩阵的约简算法。

基于上述研究，文献[17]对不完备决策系统的所有决策类的约简进行了讨论，文献[22-23]在完备决策系统下对单特定决策类的正域约简进行了研究。由于在实际应用中存在大量的不完备数据，且决策者往往倾向于关注部分决策类，现有的不完备决策系统的正域约简方法针对上述情况讨论较少。另外，基于差别矩阵的约简方法可以求取所有约简，用户可以根据个人偏好选择具有自身偏好的约简，并且通过所有约简可以求取最短约简。为此，本文提出了基于多特定决策类的不完备决策系統正域约简的理论框架，当选取的多特定决策类中决策类数目为1时，基于多特定决策类的不完备决策系统正域约简退化为不完备决策系统单特定决策类的正域约简;当选取的多特定决策类为决策系统中所有决策类时，基于多特定决策类的不完备决策系统正域约简退化为不完备决策系统所有决策类的正域约简。首先，本文介绍了不完备决策系统的相关概念;然后，定义了不完备决策系统的多特定决策类的正域约简，构造了相应的差别矩阵及区分函数，提出了基于差别矩阵的不完备决策系统多特定决策类正域约简算法（Positive region preservation Reduction for Multispecific decision classes reduction based on Discernibility Matrix in incomplete decision systems， PRMDM）;最后，实验验证了PRMDM算法的有效性。

由于实验采用标准UCI数据集，预处理后数据集中的决策系统是完备决策系统，所以需要将完备决策系统转换为不完备决策系统。本文采用文献[19]中的方式对数据集进行处理，具体处理方式为：数据集中除决策属性外，每一列随机缺失10%的属性值，缺失值在决策系统中用表示。处理后的数据集详见https：//github.com/KInfinite/datasets。

3.1 约简结果对比

选取4组UCI数据集进行约简结果对比，约简结果如表3所示。其中，表3中“所有决策类约简”对应PRDM算法的约简结果，“单特定决策类约简”对应多特定决策类中决策数目为1时PRMDM算法的约简结果，“多特定决策类约简”对应多特定决策类中决策类数目为2 时PRMDM算法的约简结果。表4列出了约简数目及平均约简长度，其中，表4中“所有决策类约简”和“特定决策类约简”分别对应PRDM算法和PRMDM算法的约简数目和平均约简长度。

由表4可知，对于数据集Teachingassistantevaluation、House、Connectionistbench和Cardiotocography，当所选多特定决策类中决策类数为1或2时，PRMDM算法的平均约简长度小于PRDM算法的平均约简长度。

3.2 约简效率对比

本节选取4组UCI数据集分别按照对象个数递增和属性个数递增的方式进行约简效率对比。约简效率如图1和图2所示，其中，图1和图2中“所有决策类”的约简耗时曲线对应PRDM算法的约简耗时，图1和图2中“决策类1”“决策类2”和“决策类：1，2”的约简耗时曲线对应PRMDM算法的约简耗时。在数据集按照对象个数递增的方式进行约简效率对比的实验中，对于每个数据集，将数据集分成10等份，第1份构成1号数据集，第1份和第2份构成2号数据集，以此类推，10号数据集即为完整的数据集。

图1是各数据集随对象数目增加约简耗时的变化曲线，随着对象数目的增加，约简耗时逐渐增加。图2是各数据集随属性数目增加约简耗时的变化曲线，随着属性数目的增加，约简耗时逐渐增加。由于在属性数目较少时，区分函数相对简单，求解区分函数所需的时间较少，所以在属性增加的前期阶段约简耗时无明显增加，在属性增加的后期阶段，由于区分函数相对复杂，求解区分函数所需的时间逐渐增加，所以约简耗时不断增加。

虽然PRDM算法及PRMDM算法的时间复杂度均为O（|C||U|2），但通过图1和图2可以发现，当选取的多特定决策类中决策类的数目远少于决策系统中所有决策类的数目时，PRMDM算法在约简效率上高于PRDM算法。例如，数据集Connectionistbench和Cardiotocography中的所有决策类的数目分别为11和10，对于每个数据集，当选取的多特定决策类中决策类的数目分别为1和2时，PRMDM算法在约简效率上高于PRDM算法，这是由于当选取的多特定决策类中决策类的数目远少于决策系统中所有决策类的数目时，多特定决策类正域约简的差别矩阵中非空差别属性集的数目小于所有决策类正域约简的差别矩阵中非空差别属性集的数目，所以PRMDM算法在构造差别矩阵的耗时上少于PRDM算法。另外，由于多特定决策类正域约简的差别矩阵中非空差别属性集的数目小于所有决策类正域约简的差别矩阵中非空差别属性集的数目，所以多特定决策类正域约简的区分函数中合取项的数目小于所有决策类正域约简的区分函数中合取项的数目，从而PRMDM算法在将区分函数转化为极小析取范式的耗时上少于PRDM算法。需要注意的是，只有当选取的多特定决策类中决策类的数目远少于决策系统中所有决策类的数目时，PRMDM算法在约简效率上才能高于PRDM算法;当PRMDM算法中选取的多特定决策类为决策系统中的所有决策类时，PRMDM算法退化为PRDM算法，此时PRMDM算法相比PRDM算法在约简效率上并无提升。

4 结语

本文提出了基于多特定决策类的不完备决策系统正域约简的理论框架，定义了不完备决策系统单特定决策类正域约简，构造了相应的差别矩阵及区分函数，提出了基于差别矩阵的不完备决策系统多特定决策类正域约简算法。本文选取4组UCI数据集进行实验，实验结果验证了本文所提算法的有效性。由于本文提出的算法是基于差别矩阵的约简算法，为提高算法的约简效率，下一步将研究差别矩阵的优化问题。

参考文献 （References）

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

[2] 王国胤，姚一豫，于洪.粗糙集理论与应用研究综述[J].计算机学报，2009，32（7）：1229-1246.（WANG G Y， YAO Y Y， YU H. A survey on rough set theory and applications [J]. Chinese Journal of Computers， 2009， 32（7）： 1229-1246.）

[3] 于洪，王國胤，姚一豫.决策粗糙集理论研究现状与展望[J].计算机学报，2015，38（8）：1628-1639.（YU H， WANG G Y， YAO Y Y. Current research and future perspectives on decisiontheoretic rough sets [J]. Chinese Journal of Computers， 2015， 38（8）： 1628-1639.）

[4] LIANG D C， LIU D， PEDRYCZ W， et al. Triangular fuzzy decisiontheoretic rough sets [J]. International Journal of Approximate Reasoning， 2013， 54（8）： 1087-1106.

[5] ZHANG Q H， ZHANG P， WANG G Y. Research on approximation set of rough set based on fuzzy similarity [J]. Journal of Intelligent and Fuzzy Systems， 2017， 32（3）： 2549-2562.

[6] QIN K Y， YANG J L， PEI Z. Generalized rough sets based on reflexive and transitive relations [J]. Information Sciences， 2008， 178（21）： 4138-4141.

[7] MIAO D Q， ZHAO Y， YAO Y Y， et al. Relative reducts in consistent and inconsistent decision tables of the Pawlak rough set model [J]. Information Sciences， 2009， 179（24）： 4140-4150.

[8] WANG F， LIANG J Y， QIAN Y H. Attribute reduction： a dimension incremental strategy [J]. KnowledgeBased Systems， 2013， 39： 95-108.

[9] WU W Z， Q Y H， LI T J， et al. On rule acquisition in incomplete multiscale decision tables [J]. Information Sciences， 2017， 378： 282-302.

[10] CHEN H M， LI T R， CAI Y， et al. Parallel attribute reduction in dominancebased neighborhood rough set [J]. Information Sciences， 2016， 373： 351-368.

[11] LIU D， LI T R， ZHANG J B. Incremental updating approximations in probabilistic rough sets under the variation of attributes[J]. KnowledgeBased Systems， 2015， 73： 81-96.

[12] MIN F， ZHANG Z H， DONG J. Ant colony optimization with partialcomplete searching for attribute reduction [J]. Journal of Computational Science， 2018， 25： 170-182.

[13] ZHU W， WANG F Y. Reduction and axiomization of covering generalized rough sets[J]. Information Sciences， 2003， 152（2）： 217-230.

[14] KRYSZKIEWICZ M. Rough set approach to incomplete information systems [J]. Information Sciences， 1998， 112（1/2/3/4）： 39-49.

[15] SKOWRON A， RAUSZER C. The discernibility matrices and functions in information systems [M]// SLOWINSKI R. Intelligent Decision Support： Handbook of Applications and Advances of the Rough Sets Theory. Dordrecht： Kluwer Academic Publishers， 1992： 331-362.

[16] LIANG J Y， XU Z B. The algorithm on knowledge reduction in incomplete information systems [J]. International Journal of Uncertainty， Fuzziness and KnowledgeBased Systems， 2002， 10（1）： 95-103.

[17] 周獻中，黄兵，李华雄，等.不完备信息系统知识获取的粗糙集理论与方法[M].南京：南京大学出版社，2010：52-104.（ZHOU X Z， HUANG B， LI H X， et al. Rough Set Theory and Method of Knowledge Acquisition in Incomplete Information Systems [M]. Nanjing： Nanjing University Press， 2010： 52-104.）

[18] QIAN Y H， LIANG J Y， LI D Y， et al. Approximation reduction in inconsistent incomplete decision tables [J]. KnowledgeBased Systems， 2010， 23（5）： 427-433.

[19] SHU W H， QIAN W B. A fast approach to attribute reduction from perspective of attribute measures in incomplete decision systems[J]. KnowledgeBased Systems， 2014， 72： 60-71.

[20] QIAN W B， SHU W H， XIE Y H， et al. Feature selection using compact discernibility matrixbased approach in dynamic incomplete decision system [J]. Journal of Information Science and Engineering， 2015， 31（2）： 509-527.

[21] CHEN D G， TSANG E C C. On the local reduction of information system [C]// Proceedings of the 2005 International Conference on Advances in Machine Learning and Cybernetics. Heidelberg： SpringerVerlag， 2006： 588-594.

[22] YAO Y Y， ZHANG X Y. Classspecific attribute reducts in rough set theory [J]. Information Sciences， 2017， 418/419： 601-618.

[23] LIU G L， HUA Z， ZOU J Y. Local attribute reductions for decision tables[J]. Information Sciences， 2017， 422： 204-217.