A Novel Approach Based on Rough Conditional Entropy for Attribute Reduction

Abstract:

Z. Pawlak’s rough set theory has been widely applied in analyzing ordinary information systems and decision tables. While few studies have been conducted on attribute selection problem in incomplete decision systems because of its complexity. Therefore, it is necessary to investigate effective algorithms to tackle this issue. In this paper, In this paper, a new rough conditional entropy based uncertainty measure is introduced to evaluate the significance of subsets of attributes in incomplete decision systems. Moreover, some important properties of rough conditional entropy are derived and three attribute selection approaches are constructed, including an exhaustive approach, a heuristic approach, and a probabilistic approach. In the end, a series of experiments on practical incomplete data sets are carried out to assess the proposed approaches. The final experimental results indicate that two of these approaches perform satisfyingly in the process of attribute selection in incomplete decision systems.

• Periodical: Applied Mechanics and Materials (Volumes 644-650)
• Pages: 1607-1619
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.644-650.1607
• Online since: September 2014
• Authors: Tao Yan*, Chong Zhao Han
• Keywords: Attribute Selection, Conditional Entropy, Incomplete Decision System

References

[1] Z. Pawlak. Rough classification. International Journal of Human-Computer Studies 51 (1999), pp.369-383.

[2] Z. Pawlak. Rough classification. International Journal of Man-Machine Studies 20 (1984), pp.469-483.

DOI: 10.1016/s0020-7373(84)80022-x

[3] Z. Pawlak. Rough sets. International Journal of Computer & Information Sciences 11 (1982), pp.341-356.

[4] Y. Xu, L.S. Li, and X.J. Li. Generalized Rough Set Model Based on Set Pair Connection Degree. in Control Conference, 2007. CCC 2007. Chinese, (2007).

DOI: 10.1109/chicc.2006.4347103

[5] Z. Xiaohong, and Y. Gang. Generalized Rough Set Model on De Morgan Algebras. in IEEE International Conference on Granular Computing, 2007. GRC 2007., (2007).

DOI: 10.1109/grc.2007.21

[6] S. Trabelsi, Z. Elouedi, and P. Lingras. Classification systems based on rough sets under the belief function framework. International Journal of Approximate Reasoning 52 (2011), pp.1409-1432.

DOI: 10.1016/j.ijar.2011.08.002

[7] K. Kaneiwa. A rough set approach to multiple dataset analysis. Applied Soft Computing 11 (2011), pp.2538-2547.

DOI: 10.1016/j.asoc.2010.08.021

[8] S. Liang, H. Chong-Zhao, D. Ning, and S. Jian-Jing. Feature Selection Based on Bhattacharyya Distance: A Generalized Rough Set Method. in The Sixth World Congress on Intelligent Control and Automation, 2006. WCICA 2006., (2006).

DOI: 10.1109/wcica.2006.1713976

[9] S. Liang, H. Chongzhao, and L. Ming. Knowledge discovery-based multiple classifier fusion: a generalized rough set method. in 9th International Conference on Information Fusion, 2006, (2006).

DOI: 10.1109/icif.2006.301558

[10] L. Zhengcai, and Q. Zheng. Rule Extraction from Incomplete Decision System Based on Novel Dominance Relation. in 4th International Conference on Intelligent Networks and Intelligent Systems (ICINIS), 2011, (2011).

DOI: 10.1109/icinis.2011.46

[11] S. Parsons, M. Kubat, and M. Dohnal. A rough set approach to reasoning under uncertainty. Journal of Experimental & Theoretical Artificial Intelligence 7 (1995), pp.175-193.

DOI: 10.1080/09528139508953805

[12] S. Parsons, and M. Kubat. A 1st-order logic for reasoning under uncertainty using rough sets. Journal of Intelligent Manufacturing 5 (1994), pp.211-223.

DOI: 10.1007/bf00123694

[13] J.H. Dai, W.T. Wang, Q. Xu, and H.W. Tian. Uncertainty measurement for interval-valued decision systems based on extended conditional entropy. Knowledge-Based Systems 27 (2012), pp.443-450.

DOI: 10.1016/j.knosys.2011.10.013

[14] L. Yunxiang, C. Yan, and Y. Xinxin. Study of Metrics System for Information Fusion Evaluation Methodology Based on Rough Set Theory in Intelligent Decision-Making. 2010International Conference on Management and Service Science (MASS 2010) (2010).

DOI: 10.1109/icmss.2010.5578398

[15] A. Skowron, and P. Wasilewski. Toward interactive rough-granular computing*. Control and Cybernetics (2011), pp.213-235.

[16] A. Skowron, J. Stepaniuk, and R. Swiniarski. Approximation Spaces in Rough-Granular Computing. Fundamenta Informaticae (2010), pp.141-157.

DOI: 10.3233/fi-2010-267

[17] Y. Xiaoping, T. Yong, J. Yongjie, X. Jun, and B. Yong. Incomplete information systems based on the set values of attributes. in The 8th International Conference on Computer Supported Cooperative Work in Design, 2004. Proceedings., (2004).

DOI: 10.1109/cacwd.2004.1349288

[18] W. Wei-Zhi, and X. Yon-Hong. On two types of generalized rough set approximations in incomplete information systems. in IEEE International Conference on Granular Computing, 2005 , (2005).

DOI: 10.1109/grc.2005.1547290

[19] L. Guilong. A comparison of two types of generalized rough sets. in IEEE International Conference on Granular Computing (GrC), 2011, (2011).

DOI: 10.1109/grc.2011.6122634

[20] I. Yanto, P. Vitasari, T. Herawan, and M.M. Deris. Applying variable precision rough set model for clustering student suffering study's anxiety. Expert Systems with Applications 39 (2012), pp.452-459.

DOI: 10.1016/j.eswa.2011.07.036

[21] W. Wei-Zhi. Knowledge acquisition in incomplete information systems based on variable precision rough set model. in Proceedings of 2005 International Conference on Machine Learning and Cybernetics, 2005., (2005).

DOI: 10.1109/icmlc.2005.1527318

[22] M. Zhang, C. Jia-Xing, and W. Hong-Jun. The research on the classification of the incomplete information system. in Proceedings of 2004 International Conference on Machine Learning and Cybernetics, 2004., (2004).

DOI: 10.1109/icmlc.2004.1380485

[23] M. Kryszkiewicz. Rules in incomplete information systems. Information Sciences 113 (1999), pp.271-292.

DOI: 10.1016/s0020-0255(98)10065-8

[24] P. Luukka. Feature selection using fuzzy entropy measures with similarity classifier. Expert Systems with Applications 38 (2011), pp.4600-4607.

DOI: 10.1016/j.eswa.2010.09.133

[25] H. Tian, and H. Rybinski. A New Approach to Computing Weighted Attributes Values in Incomplete Information Systems. in ICHIT '06. International Conference on Hybrid Information Technology, 2006., (2006).

DOI: 10.1109/ichit.2006.253622

[26] H. Bing, G. Ling, and Z. Xian-zhong. Approximation Reduction Based on Similarity Relation. in Fourth International Conference on Fuzzy Systems and Knowledge Discovery, 2007. FSKD 2007., (2007).

DOI: 10.1109/fskd.2007.191

[27] A. Skowron, and Z. Pawlak. Rough sets: Some extensions. Information Sciences 177 (2007), pp.28-40.

DOI: 10.1016/j.ins.2006.06.006

[28] Y.H. Qian, J.Y. Liang, W. Pedrycz, and C.Y. Dang. An efficient accelerator for attribute reduction from incomplete data in rough set framework. Pattern Recognition 44 (2011), pp.1658-1670.

DOI: 10.1016/j.patcog.2011.02.020

[29] D.Q. Miao, Y. Zhao, Y.Y. Yao, H.X. Li, and F.F. Xu. Relative reducts in consistent and inconsistent decision tables of the Pawlak rough set model. Information Sciences 179 (2009), pp.4140-4150.

DOI: 10.1016/j.ins.2009.08.020

[30] E. Xu, T. Shao-Cheng, W. Yuan, X. Shang, and L. Peng. Approach to Missing Data Recovery. in International Symposium on Electronic Commerce and Security, 2008, (2008).

[31] M. Kryszkiewicz. Rough set approach to incomplete information systems. Information Sciences 112 (1998), pp.39-49.

DOI: 10.1016/s0020-0255(98)10019-1

[32] B.K. Patra, and S. Nandi. Fast Single-Link Clustering Method Based on Tolerance Rough Set Model, Springer-Verlag Berlin, Berlin (2009).

[33] J. Tang, K. She, and W. Zhu. A new type of covering-based rough fuzzy set model. Control and Decision 27 (2012), pp.1653-1662.

[34] J. Tang, K. She, F. Zhu, and K. Li. Covering-based rough set model based on set-valued mapping. Computer Engineering and Applications 47 (2011), pp.30-34.

[35] B. Huang, H.X. Li, and D.K. Wei. Dominance-based rough set model in intuitionistic fuzzy information systems. Knowledge-Based Systems 28 (2012), pp.115-123.

DOI: 10.1016/j.knosys.2011.12.008

[36] Z. Rong, L. Bin, and L. Sifeng. A Multi-attribute Auction Model by Dominance-based Rough Sets Approach. Computer Science and Information Systems 7 (2010), pp.843-858.

DOI: 10.2298/csis090804025r

[37] M. Kryszkiewicz. Generalized rules in incomplete information systems. Foundations of Intelligent Systems. 10th International Symposium, ISMIS '97. Proceedings (1997), pp.421-430.

[38] M. Kryszkiewicz. Generation of rules from incomplete information systems. Principles of Data Mining and Knowledge Discovery 1263 (1997), pp.156-166.

DOI: 10.1007/3-540-63223-9_115

[39] Y. Qian, J. Liang, D. Li, F. Wang, and N. Ma. Approximation reduction in inconsistent incomplete decision tables. Knowledge-Based Systems 23 (2010), pp.427-433.

DOI: 10.1016/j.knosys.2010.02.004

[40] J.C. Xu, and L. Sun. Knowledge Entropy and Feature Selection in Incomplete Decision Systems. Applied Mathematics & Information Sciences 7 (2013), pp.829-837.

DOI: 10.12785/amis/070255

[41] Z. Rong, and E.A. Hansen. Breadth-first heuristic search. Artificial Intelligence 170 (2006), pp.385-408.

DOI: 10.1016/j.artint.2005.12.002

[42] T.A. Akanmu, S.O. Olabiyisi, E.O. Omidiora, C.A. Oyeleye, M.A. Mabayoje, and A.O. Babatunde. Comparative study of complexities of breadth-first search and depth-first search algorithms using software complexity measures. Proceedings of the World Congress on Engineering 2010. WCE 2010 (2010).

[43] G. Nandi. An enhanced approach to Las Vegas Filter (LVF) feature selection algorithm. Proceedings 2011 2nd National Conference on Emerging Trends and Applications in Computer Science (NCETACS 2011) (2011), 3 pp. -3 pp.

DOI: 10.1109/ncetacs.2011.5751392