Generalized binary discernibility matrix for attribute reduction in incomplete information systems

doi:10.1016/S1005-8885(17)60224-3

中国邮电高校学报(英文版) ›› 2017, Vol. 24 ›› Issue (4): 57-68.doi: 10.1016/S1005-8885(17)60224-3

• Artificial Intelligence • 上一篇下一篇

Generalized binary discernibility matrix for attribute reduction in incomplete information systems

马福民¹,张腾飞²

1. 南京财经大学
2. 南京邮电大学

收稿日期:2017-01-10 修回日期:2017-06-19 出版日期:2017-08-30 发布日期:2017-08-30
通讯作者: 马福民 E-mail:fmmatj@126.com
基金资助:
国家自然科学基金重点项目

Generalized binary discernibility matrix for attribute reduction in incomplete information systems

Received:2017-01-10 Revised:2017-06-19 Online:2017-08-30 Published:2017-08-30
Contact: Fu-Min MA E-mail:fmmatj@126.com
Supported by:
National Science Foundation of China

摘要/Abstract

摘要： To extract and express the knowledge hidden in information systems, discernibility matrix and its extensions were introduced and applied successfully in many real life applications. Binary discernibility matrix, as a representative approach, has many interesting superior properties and has been rapidly developed to find intuitive and easy to understand knowledge. However, at present, the binary discernibility matrix is mainly adopted in the complete information system. It is a challenging topic how to achieve the attribute reduction by using binary discernibility matrix in incomplete information system. A form of generalized binary discernibility matrix is further developed for a number of representative extended rough set models that deal with incomplete information systems. Some useful properties and criteria are introduced for judging the attribute core and attribute relative reduction. Thereafter, a new algorithm is formulated which supports attribute core and attribute relative reduction based on the generalized binary discernibility matrix. This algorithm is not only suitable for consistent information systems but also inconsistent information systems. The feasibility of the proposed methods was demonstrated by worked examples and experimental analysis.

关键词: rough sets, generalized binary discernibility matrix, attribute relative reduction, incomplete information system

Abstract: To extract and express the knowledge hidden in information systems, discernibility matrix and its extensions were introduced and applied successfully in many real life applications. Binary discernibility matrix, as a representative approach, has many interesting superior properties and has been rapidly developed to find intuitive and easy to understand knowledge. However, at present, the binary discernibility matrix is mainly adopted in the complete information system. It is a challenging topic how to achieve the attribute reduction by using binary discernibility matrix in incomplete information system. A form of generalized binary discernibility matrix is further developed for a number of representative extended rough set models that deal with incomplete information systems. Some useful properties and criteria are introduced for judging the attribute core and attribute relative reduction. Thereafter, a new algorithm is formulated which supports attribute core and attribute relative reduction based on the generalized binary discernibility matrix. This algorithm is not only suitable for consistent information systems but also inconsistent information systems. The feasibility of the proposed methods was demonstrated by worked examples and experimental analysis.

Key words: rough sets, generalized binary discernibility matrix, attribute relative reduction, incomplete information system

中图分类号:

TP18

参考文献

1. Pawlak Z, Skowron A. Rough sets: some extensions. Information Science, 2007, 177(1): 28-40

2. Xu W H, Li Y, Liao X W. Approaches to attribute reductions based on rough set and matrix computation in inconsistent ordered information systems. Knowledge-Based Systems, 2012, 27: 78-91

3. Skowron A, Rauszer C. The discernibility matrices and functions in information systems. Theory and Decision Library. 1992, 11: 331-362

4. Wang J, Wang J. Reduction algorithms based on discernibility matrix: the ordered attribute method. Journal of Computer Science and Technology, 2001, 16(6): 489-504

5. Felix R, Ushio T. Rough sets-based machine learning using a binary discernibility matrix. Proceedings of the 2nd International Conference on Intelligent Processing and Manufacturing of Materials (IPMM’99): Vol 1, Jul 10-15, 1999, Honolulu, HI, USA. Piscataway, NJ, USA: IEEE, 1999: 299-305

6. Lazo-Cortés M S, Martínez-Trinidad J F, Carrasco-Ochoa J A, et al. A new algorithm for computing reducts based on the binary discernibility matrix. Intelligent Data Analysis. 2016, 20(2): 317-337

7. Zhang T F, Yang X X, Ma F M. Algorithm for attribute relative reduction based on generalized binary discernibility matrix. Proceedings of the IEEE 26th Chinese Control and Decision Conference (CCDC’14), May 31-Jun 2, 2014, Changsha, China. Piscataway, NJ, USA: IEEE, 2014: 2626-2631

8. Zhang J B, Li T R, Ruan D, et al, Rough sets based matrix approaches with dynamic attribute variation in set-valued information systems. International Journal of Approximate Reasoning, 2012, 53(4): 620-635

9. Hu X H, Cercone N. Learning in relational databases: a rough set approach. Computational Intelligence, 1995, 11(2): 323-338

10. Ye D Y, Chen Z J. A new discernibility matrix and the computation of a core. Acta Electronic Sinica, 2002, 30(7): 1086-1088 (in Chinese)

11. Yao Y Y, Zhao Y. Discernibility matrix simplification for constructing attribute reducts. Information Science, 2009, 179(7): 867-882

12. Yang M, Yang P. A novel approach to improving C-tree for feature selection. Applied Soft Computing, 2011, 11(2): 924-931

13. Zhi T Y, Miao D Q. The binary discernibility matrix’s transformation and high efficiency attributes reduction algorithm’s conformation. Computer Science, 2002, 29(2): 140-142 (in Chinese)

14. Ye D Y, Chen Z J. Inconsistency classification and discernibility- matrix-based approaches for computing an attribute core. Proceedings of the 2003 International Workshop on Rough Sets, Fuzzy Sets, Data Mining, and Granular-Soft Computing (RSFDGrC’03), May 26-29, 2003, Chongqing, China. LNCS 2639. Berlin, Germany: Springer-Verlag, 2003: 269-273

15. Chen H H, Pei Z, Zhang L. Knowledge reduction based on binary discernibility matrix in variable precision rough set. Proceedings of the 2006 International Symposium on Communications and Information Technologies (ISCIT’06), Oct 18-20, 2006, Bangkok, Thailand. Piscataway, NJ, USA: IEEE, 2006: 949-954

16. Wang X Y, Yang S C, Ji B. Research on attribute reduction based on variable precision rough sets model. Proceedings of the IEEE 2011 International Conference on Computer Science and Automation Engineering (CSAE’11): Vol 1, Jun 10-12, 2011, Shanghai, China. Piscataway, NJ, USA: IEEE, 2011: 413-416

17. Yang Y Y, Chen D G, Dong Z. Novel algorithms of attribute reduction with variable precision rough set model. Neurocomputing, 2014, 139: 336-344

18. Zhang T F, Yang X X, Ma F M. Improved algorithm for attribute core computing based on binary discernibility matrix. Proceedings of the 33rd Chinese Control Conference (CCC’14), Jul 28-30, 2014, Nanjing, China. Piscataway, NJ, USA: IEEE, 2014: 7400-7404

19. Lazo-Cortés M S, Martínez-Trinidad J F, Carrasco-Ochoa J A, et al. On the relation between rough set reducts and typical testors. Information Science, 2015, 294: 152-163

20. Yan T, Han C Z. A novel approach of rough conditional entropy-based attribute selection for incomplete decision system. Mathematical Problems in Engineering, 2014: Article 728923/1-15

21. Kryszkiewicz M. Rough set approach to incomplete information systems. Information Science, 1998, 112(1): 39-49

22. Meng Z Q, Shi Z Z. A fast approach to attribute reduction in incomplete decision systems with tolerance relation-based rough sets. Information Science, 2009, 179(16): 2774-2793

23. Dai J H, Wang W T, Xu Q. An uncertainty measure for incomplete decision tables and its applications. IEEE Transactions on Cybernetics, 2013, 43(4): 1277-1289

24. Zhao H, Qin K Y. Mixed feature selection in incomplete decision table. Knowledge-Based Systems, 2014, 57: 181-190

25. Shu W H, Qian W B. A fast approach to attribute reduction from perspective of attribute measures in incomplete decision systems. Knowledge-Based Systems, 2014, 72: 60-71

26. Wang G Y, Guan L H. Data-driven valued tolerance relation. Proceedings of the 2012 International Conference on Rough Sets and Knowledge Technology (RSKT’12): Aug 17-20, 2012, Chengdu, China. LNCS 7414. Berlin, Germany: Springer-Verlag, 2012: 11-19

27. Wang G Y. Extension of rough set under incomplete information systems. Journal of Computer Research and Development, 2002, 39(10): 1238-1243 (in Chinese)

28. Sheng L, Yang H Z. Extended rough set model based on completed tolerance relation. Control and Decision, 2008, 23(3): 258-262 (in Chinese).

29. Qian Y H, Liang J Y, Li D Y, et al. Approximation reduction in inconsistent incomplete decision tables. Knowledge-Based Systems, 2010, 23: 427-433

30. Ma L W. On some types of neighborhood-related covering rough sets. International Journal of Approximate Reasoning, 2012, 53(6): 901-911

31. Tang J G, She K, Zhu W L. Covering-based rough sets based on the refinement of covering-element. International Journal of Computational and Mathematical Sciences. 2011, 5(4): 198-208

32. Xu J C, Sun L. Knowledge entropy and feature selection in incomplete decision systems. Applied Mathematics and Information Sciences, 2013, 7(2): 829-837

33. Clark P G, Grzymala-Busse J W, Rzasa W. A comparison of two MLEM2 rule induction algorithms extended to probabilistic approximations. Journal of Intelligent Information Systems, 2016, 41(3): 515-529

34. Huang W T, Wang W J, Zhao X Z. Rule extraction method in incomplete decision table for fault diagnosis based on discernibility matrix primitive. Proceedings of the 3rd International Conference on Rough Sets and Knowledge Technology (RSKT’08), May 17-19, 2008, Chengdu, China. LNCN 5009. Berlin, Germany: Springer-Verlag, 2008: 755-762

35. Yan D Q, Li K Q, Chi Z X. Soft discernibility matrix and attribute reduction for information systems. Journal on Communications, 2009, 30(8): 45-50 (in Chinese)

36. Yao Y Y, Zhao Y. Discernibility matrix simplification for constructing attribute reducts. Information Sciences, 2009, 179(7): 867-882

37. Zhang Q G, Zheng X F. Discernibility matrix algorithm of attribute reduction based on knowledge granulation in incomplete decision table. Computer Science, 2012, 39(2): 209-212 (in Chinese)

38. Lang G M, Li Q G, Guo L K. Discernibility matrix simplification with new attribute dependency functions for incomplete information systems. Knowledge and Information Systems, 2013, 37: 611-638

39. Qian W B, Shu W H, Xie Y H, et al. Feature selection using compact discernibility matrix-based approach in dynamic incomplete decision system. Journal of Information Science and Engineering, 2015, 31(2): 509-527

[1]	何明枢, 金磊, 王小娟, 李源. Web log classification framework with data augmentation based on GANs[J]. 中国邮电高校学报(英文版), 2020, 27(5): 34-46.
[2]	季一木, 李可, 刘尚东, 刘强, 尧海昌, 李奎. Collaborative filtering recommendation algorithm based on interactive data classification[J]. 中国邮电高校学报(英文版), 2020, 27(5): 1-12.
[3]	杨健健张强王晓林杜毅博王超吴淼. Research on equipment fault diagnosis method based on random stochastic adaptive particle swarm optimization [J]. 中国邮电高校学报(英文版), 2020, 27(4): 17-25.
[4]	Zhai Qi, Jiang Mingyan. Supervised learning of enhancing convolutional Hash for image retrieval[J]. 中国邮电高校学报(英文版), 2019, 26(4): 51-61.
[5]	Pang Hao, Bu Yunyun, Wang Cong, Xiao Hui. Automatic detection of breast nodule in the ultrasound images using CNN[J]. 中国邮电高校学报(英文版), 2019, 26(2): 9-16.
[6]	Yang Ridong, Zhang Shiyu, Li Lin, Wang Zhe, Zhou Yi. Using boosting tree to learn imbalanced data[J]. 中国邮电高校学报(英文版), 2019, 26(2): 43-51.
[7]	He Jin, Wang Cong, Chen Zhao. Pulmonary tuberculosis detection model of chest X-ray images using convolutional neural network[J]. 中国邮电高校学报(英文版), 2018, 25(6): 1-6.
[8]	Yang Chen. Consortium blockchains-based deep deterministic policy gradient algorithm for optimal electricity trading among households[J]. 中国邮电高校学报(英文版), 2018, 25(6): 7-20.
[9]	姜晓庆夏克文林永良白建川. Noisy speech emotion recognition using sample reconstruction and multiple-kernel learning[J]. 中国邮电高校学报(英文版), 2017, 24(2): 1-9.
[10]	李端张洪欣李强 Zhao Xinjie He Pengfei. Electromagnetic side_channel attack based on PSO Directed Acyclic Graph SVM[J]. Acta Metallurgica Sinica(English letters), 2015, 22(5): 10-15.
[11]	平源周亚建薛超杨义先. Efficient representation of text with multiple perspectives[J]. Acta Metallurgica Sinica(English letters), 2012, 19(1): 101-111.
[12]	马盈仓何华灿. Axiomatization for 1-level universal AND operator[J]. Acta Metallurgica Sinica(English letters), 2008, 15(2): 125-129.

Generalized binary discernibility matrix for attribute reduction in incomplete information systems

Generalized binary discernibility matrix for attribute reduction in incomplete information systems

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 12

编辑推荐

Metrics

本文评价