关系决策系统中相对不可区分和区分关系的约简

李旭 荣梓景 阮晓曦

摘 要：针对相对不可区分和区分关系约简的问题提出相应的算法。首先，考虑等价关系中相对不可区分关系的约简，提出一种新的辨识矩阵，并在此基础上得到了一种约简算法，通过关系的补关系提出相对区分关系的约简算法。然后，将相对不可区分关系等概念推广到一般关系。对于关系决策系统的相对不可区分关系约简给出了相应的辨识矩阵，并利用关系的补关系得到了相对区分关系约简的辨识矩阵，从而得到了两者的约简算法。

最后，在选取的UCI数据集上，对提出的算法进行验证。在等价关系上，基于绝对约简的相对不可区分关系的约简（EQIND）算法与相对不可区分一般关系的约简（BIIND）算法所得约简相同， 基于绝对约简的相对区分关系的约简（EQDIS）算法与相对区分一般关系的约简（BIDIS）算法所得约简相同;同时算法BIIND、BIDIS可以对不完备决策表进行约简。实验结果验证了所提算法的可行性。

关键词： 粗糙集;不可区分关系;区分关系;关系决策系统;属性约简

中图分类号：TP18

文献标志码：A

Abstract： Corresponding reduction algorithms for relative indiscernibility and discernibility relation were proposed. Firstly， considering the reduction of the relative indiscernibility relation in equivalence relation， the corresponding discernibility matrix was proposed and a reduction algorithm was proposed based on the matrix. Then， a reduction algorithm for relative discernibility relation was proposed according to the complementary relationship of the relation. Secondly， the concepts such as relative indiscernibility relation were expanded to the general relation. The corresponding discernibility matrix was proposed for the relative indiscernibility relation reduction in the relation decision system， and the corresponding discernibility matrix for the relative discernibility relation reduction was obtained by using the complementary relationship of the relation， so the reduction algorithms for both relations were obtained. Finally， the proposed algorithms were verified on the selected UCI datasets. In the equivalence relation，

the algorithm of the relative EQuivalence INDiscernibility relation reduction based on absolute reduction （EQIND） and the algorithm of the relative BInary INDiscernibility relation reduction （BIIND） have the same results. The algorithm of the relative EQuivalence DIScernibility relation reduction based on absolute reduction （EQDIS） and the algorithm of the relative BInary DIScernibility relation reduction （BIDIS） have the same results. Meanwhile， BIIND and BIDIS are suitable for the incomplete decision table. The feasibility of the proposed algorithms were verified by the experimental results.

Key words：  rough set; indiscernibility relation; discernibility relation; relation decision system; attribute reduction

0 引言

粗糙集理論[1]作为处理不确定性、不一致问题的数据分析处理理论，在1982年由波兰学者Pawlak提出。属性约简是粗糙集理论研究中的核心问题之一，其主要思想是根据某种特定规则，在保持论域中的对象分类不变的前提下，删除冗余属性。现阶段属性约简理论研究已取得了重大进展，例如，正域约简[2-3]、变精度约简[4]、分配约简[5]、覆盖约简[6-7]、局部约简[8]等。许多学者在等价关系的基础上对属性约简进行了广泛深入的讨论，然而当数据存在不完备、不一致现象时，通常诱导不出等价关系，于是学者通过容差关系[9]、限制容差关系[10]、相似关系[11]等非等价的二元关系拓宽了属性约简的研究范围。目前，文献[12]根据条件（决策）属性在论域中所决定的关系，给出了一般关系并在该关系下讨论了属性约简。文献[13]将正域约简推广至一般关系决策系统，并给出了严格证明。文献[14]在决策表中提出了不可区分关系及区分关系的约简，同时，在信息表中给出了关于区分和不可区分的4个关系，并研究了4个关系的相关性质。文献[15]针对不完备信息系统给出了不可区分关系，但未提出约简的概念。文献[16]在信息表中运用启发式约简算法得到了区分关系的约简。文献[17]在决策表中进一步研究了不可区分关系和区分关系两者的约简，给出了相应的辨识矩阵，并得到了相应的约简算法。许多学者采用启发式算法，因为启发式约简算法能得到约简，但并不能得到所有约简;而关于辨识矩阵[18-19]得到约简的方法虽然需要严密的数学论证，且计算复杂度较高，但能得到全部约简。因此，本文使用基于辨识矩阵的约简方法，即通过构建辨识矩阵将辨识函数从合取范式转化为析取范式，从而得到全部约简。

最初不可区分关系和区分关系两者的属性约简研究是在等价关系的基础上实现的。

基于决策约简，本文提出了相对不可区分关系的约简（EQuivalence INDiscernibility relation reduction based on absolute reduction， EQIND）算法和相对区分关系的约简（EQuivalence DIScernibility relation reduction based absolute reduction， EQDIS）算法。

因为很多类型决策表的数据不完备，还有数值型数据、混合型数据等问题，通常不能诱导出等价关系。因此需要考虑一般关系上的不可区分关系和区分关系。本文在文献[14]概念的基础上，提出了一般关系决策系统的相对不可区分关系及相对区分关系。

将等价关系上的4个概念推广到一般关系，同时在关系决策系统中，提出了相对不可区分关系约简（BInary INDiscernibility Relation Reduction， BIIND）。利用关系的补关系作为关系的概念及相对不可区分关系约简所对应的辨识矩阵，提出了相对区分关系约简（BInary DIScernibility Relation Reduction， BIDIS）。此外，作为本文提出的约简算法的应用，给出了不完备决策表中相对不可区分及区分关系的约简。

算法适用于一致决策表，也适用于不一致决策表。若假设在步骤3中，绝对约简集中存在{a1，a3，d}，{a1，a3，a4}，删除{d}后得{a1，a3}，{a1，a3，a4}，因为a1∧a3∧a4a1∧a3，所以在析取范式中删除合取式{a1，a3，a4}。即在绝对约简集中删除{a1，a3，a4}后得相对不可区分关系的所有约简。

3 决策表中的相对区分关系的约简

在决策表中，现讨论对象之间另一种重要的关系。相对不可区分的补关系就是相对区分关系，因而通过考虑关系的补关系的概念，提出本章的约简相对应的辨识矩阵。

决策表（U，C∪D）中相对区分关系的约简就是考虑把补关系作为新关系的相对不可区分约简，即决策表（U，C′∪D′）中相对不可区分关系的约简，其中，当a′∈C′，条件属性a′在U上的等价关系为Ra′，它与Ra互补。当d′∈D′，决策属性d′在U上的等价关系为Rd′，它与Rd互补。

设（U，C∪D）是决策表，为得到相对区分关系的约简，现定义辨识矩阵为M"nn=（m"ij）n×n，其中：m"ij是矩阵的元素;n是论域中对象数。

4 关系决策系统中相对不可区分关系的约简

在信息系统中，当将二元关系推广为一般关系时，本章提出了4种关于关系的概念。同时，在关系决策系统中，给出了相对不可区分关系的定义及其约简，并证明了其对应的辨识矩阵。

定义6 设（U，C）是关系系统，属性集C由U上的关系RC构成，对于任意（x， y）∈U×U，现定义如下4种关系：

1）若有RC={（x， y）∈U×Ua∈C，（x， y）∈Ra}，称RC是由C确定的不可区分关系。

2）若有WRC={（x， y）∈U×Ua∈C，（x， y）∈Ra}，称WRC是由C确定的弱不可区分关系。

3）若有R′C={（x， y）∈U×Ua∈C，（x， y）Ra}，称R′C是由C确定的区分关系。

4）若有WR′C={（x， y）∈U×Ua∈C，（x， y）Ra}，称WR′C是由C确定的弱区分关系。

定义7 设（U，C∪D）为关系决策系统，条件属性集C和决策属性集D决定U上一般关系RC，RD，（x， y）∈U×U，RC∩RD={（x， y）a∈C，（x， y）∈Ra∧（x， y）∈RD}，称RC∩RD是由条件属性集C确定的相对不可区分关系。

由定义6知，当存在a∈C时，关系Ra决定的相对不可区分关系为：

定义8 设（U，C∪D）为关系决策系统，当BC时，若B满足下列两条件，称B是C相对不可区分关系的约简：

推论4 设（U，C∪D）为关系决策系统，BC，B是C相对不可区分关系约简的充要条件是：B是C中满足条件gij∩B≠的最小子集。

算法3 BIIND。

输入 关系决策系统（U，C∪D）。

输出 相对不可区分关系的全部约简。

步骤1 对于任意对象，根据条件属性集、决策属性集，构建辨识矩阵Gnn=（gij）n×n;

步骤2 构造辨识函数f=∏（∑gij≠gij），并把辨识函数f从合取范式转化为析取范式的形式;

步骤3 通过析取范式∑li=1（∏ Bi）得到B1，B2，…，Bl，算法结束。

1）根据算法3，构建6×6的辨识矩阵：

本章提所涉的关系是对文献[14，17]中的进一步研究，文献[17]中约简基于的二元关系是等价关系，而本章中的相对不可区分关系不需要满足自反性、对称性、传递性中任何性质。例如，当（x，x）∈IndC（D）时，推广后，（x，x）∈RC∩RD或（x，x）RC∩RD。文献[17]中的约简算法仅能处理决策表中诱导出的等价关系，无法处理决策表中诱导出的对称关系、容差关系等二元關系。而算法3能够处理决策表诱导出的上述所有二元关系，因此，基于等价关系的相对不可区分关系约简是本章的特例。

5 关系决策系统中相对区分关系的约简

在一般关系上，本章提出了相对区分关系的定义。为得到其约简，证明了相应的辨识矩阵。

定義11 设（U，C∪D）为关系决策系统，当BC时，若B满足下列两条件，称B是C相对区分关系的约简：

1）根据算法4，构建6×6的辨识矩阵：

对于不可区分关系和区分关系，则仅需证两者约简中相应的任意一个辨识矩阵，同时引入补关系的概念，得另一约简相应的辨识矩阵。本章中定义的相对区分关系是对概念的进一步推广。同时，相较于文献[17]算法仅能处理等价类，本章所提出的算法可以处理包括等价关系在内的二元关系。例如，在不完备决策表（见表2）中通常不能诱导出等价关系，因而文献[17]算法不适用，通过使用本文所提的算法3、算法4可以解决该问题。

6 实例分析

从UCI数据集中选取了3个数据集（Zoo、Hepatitis和Statlog（Heart））（见表3）进行实验，以验证本文算法的有效性和可行性。程序运行环境：Intel Core i5-2440 CPU 3.10GHz，Windows10 64位，算法为Python代码实现。

因Hepatitis数据集中的数据存在缺失现象，因而通常不能诱导出等价关系。算法1、算法2是基于等价关系对决策表进行得约简，因而该表不适用。而对于算法3、算法4，已将等价关系推广至一般关系（即不需要满足自反性、对称性、传递性的任意性质），因此可对数据集中所给出的决策表进行相对不可区分约简和相对可区分约简。

约简结果如表4所示，从中可看出，算法1和算法3在完备数据集（Zoo、Statlog（Heart））上约简结果相同，算法2和算法4在完备数据集上约简结果相同。属性个数为约简结果的基，约简集个数是在相同的基下约简个数。例如，在Zoo数据集上，运用算法2得到375个约简结果，其中：当约简的基为2时有6个约简;当约简的基为3时有369个约简。

数据集算法属性个数约简集个数约简举从实验结果可看出：在决策表中，二元关系是等价关系时，本文所提出的算法1和算法2是可行的。在关系决策系统中，即二元关系是一般关系时，本文所提出的算法3和算法4是可行的。综上所述，实验结果验证了本文所提出4个算法的可行性。

7 结语

本文在关系系统上，首先提出了弱不可区分关系、不可区分关系、弱区分关系及区分关系等4个概念。其次，在关系决策系统中，提出了相对不可区分一般关系、相对区分一般关系两者的概念，及两者约简的定义，并证明了约简对应的辨识矩阵。最后，通过举例说明本文所提出的约简是对文献[14，17]所给出的约简的推广。

参考文献（References）

[1] PAWLAK Z. Rough sets： theoretical aspect of reasoning about data[M]. Dordrecht： Kluwer Academic Publishers， 1991： 9-42.

[2] PAWLAK Z， SOWINSKI R. Rough set approach to multi-attribute decision analysis[J]. European Journal of Operational Research， 1994， 72（3）： 443-459.

[3] 张文修， 梁怡， 吴伟志. 信息系统与知识发现[M]. 北京： 科学出版社， 2003： 42-55. （ZHANG W X， LIANG Y， WU W Z. Information System and Knowledge Discovery[M]. Beijing： Science Press， 2003： 42-55.）

[4] INUIGUCHI M. Several approaches to attribute reduction in variable precision rough set model[C]// Proceedings of the 2005 International Conference on Modeling Decisions for Artificial Intelligence， LNCS 3558. Berlin： Springer， 2005： 215-226.

[5] LIU G. Assignment reduction of relation decision systems[C]// Proceedings of the 2017 International Joint Conference on Rough Sets， LNCS 10313. Cham： Springer， 2017： 384-391.

[6] CHEN D G， WANG C， HU Q. A new approach to attribute reduction of consistent and inconsistent covering decision systems with covering rough sets[J]. Information Sciences， 2007， 177（17）： 3500-3518.

[7] WANG C， SHAO M， SUN B， et al. An improved attribute reduction scheme with covering based rough sets[J]. Applied Soft Computing， 2015， 26： 235-243.

[8] LIU G， HUA Z， ZOU J. Local attribute reductions for decision tables[J]. Information Sciences， 2018， 422： 204-217.

[9] FENG Q， LI R. Discernibility matrix based attribute reduction in intuitionistic fuzzy decision systems[C]// Proceedings of the 2013 International Workshop on Rough Sets， Fuzzy Sets， Data Mining， and Granular-Soft Computing， LNCS 8170. Berlin： Springer， 2013： 147-156.

[10] 王超， 罗可. 不完备信息系统中基于限制容差关系的属性约简方法[J]. 计算机应用， 2011， 31（12）： 3236-3239. （WANG C， LUO K. Attributes reduction method based on limited tolerance relation in incomplete information system[J]. Journal of Computer Applications， 2011， 31（12）： 3236-3239.）

[11] YANG X， YANG J， WU C， et al. Dominance-based rough set approach and knowledge reductions in incomplete ordered information system[J]. Information Sciences， 2008， 178（4）： 1219-1234.

[12] LIU G L. Attribute reduction approaches for general relation decision systems[J]. Pattern Recognition Letters， 2015， 65： 81-87.

[13] LIU G， HUA Z， CHEN Z. A general reduction algorithm for relation decision systems and its applications[J]. Knowledge-Based Systems， 2017， 119： 87-93.

[14] ZHAO Y， YAO Y Y， LUO F. Data analysis based on discernibility and indiscernibility[J]. Information Sciences， 2007， 177（22）： 4959-4976.

[15] 杨霁琳， 秦克云， 裴峥. 不完备信息系统中的不可区分关系[J]. 计算机工程， 2010， 36（13）： 4-6. （YANG J L， QIN K Y， PEI Z. Indiscernibility relation in incomplete information system[J]. Computer Engineering， 2010， 36（13）： 4-6.）

[16] 陈鑫影， 邱占芝. 基于可分辨关系的知识约简[J]. 计算机工程， 2010， 36（4）： 53-55. （CHEN X Y， QIU Z Z. Knowledge reduction based on distinguishable relation[J]. Computer Engineering， 2010， 36（4）： 53-55.）

[17] 秦克云， 敬思惠. 决策系统基于不可区分关系及区分关系的约简[J]. 计算机科学， 2018， 45（6）： 247-250. （QING K Y， JING S H. Attribute reduction of decision systems based on indiscernibility relation and discernibility relation[J]. Computer Science， 2018， 45（6）： 247-250.）

[18] SKOWRON A. Boolean reasoning for decision rules generation[C]// Proceedings of the 1993 International Symposium on Methodologies for Intelligent Systems. Berlin： Springer， 1993： 295-305.

[19] SKOWRON A， RAUSZER C. The discernibility matrices and functions in information systems [M]// SLOWINSKI R. Intelligent Decision Support. Berlin： Springer， 1992： 331-362.

[20] 榮梓景. 关系决策系统的分布约简[J]. 计算机工程与应用， 2018， 54（17）： 62-66. （RONG Z J. Distribution reduction algorithms for relational decision systems[J]. Computer Engineering and Applications， 2018， 54（17）： 62-66.）