Attribute reduction of relative indiscernibility relation and discernibility relation in relation decision system

doi:10.11772/j.issn.1001-9081.2019030438

Abstract

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 (BⅡND) 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, BⅡND 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

摘要： 针对相对不可区分和区分关系约简的问题提出相应的算法。首先，考虑等价关系中相对不可区分关系的约简，提出一种新的辨识矩阵，并在此基础上得到了一种约简算法，通过关系的补关系提出相对区分关系的约简算法。然后，将相对不可区分关系等概念推广到一般关系。对于关系决策系统的相对不可区分关系约简给出了相应的辨识矩阵，并利用关系的补关系得到了相对区分关系约简的辨识矩阵，从而得到了两者的约简算法。最后，在选取的UCI数据集上，对提出的算法进行验证。在等价关系上，基于绝对约简的相对不可区分关系的约简（EQIND）算法与相对不可区分一般关系的约简（BⅡND）算法所得约简相同，基于绝对约简的相对区分关系的约简（EQDIS）算法与相对区分一般关系的约简（BIDIS）算法所得约简相同；同时算法BⅡND、BIDIS可以对不完备决策表进行约简。实验结果验证了所提算法的可行性。

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

CLC Number:

TP18

LI Xu, RONG Zijing, RUAN Xiaoxi. Attribute reduction of relative indiscernibility relation and discernibility relation in relation decision system[J]. Journal of Computer Applications, 2019, 39(10): 2852-2858.

李旭, 荣梓景, 阮晓曦. 关系决策系统中相对不可区分和区分关系的约简[J]. 计算机应用, 2019, 39(10): 2852-2858.

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.)