Abstract
As the object of study incomplete decision table, with the study of the notion of conflict region, the definition of attribution reduction based on conflict region in incomplete decision table is provided. it is proved that the attribute reduction is equivalent to the attribute reduction based on positive region, at the same time ,a new attribute reduction algorithm which is in incomplete decision table is designed, whose time complexity is O(|K||C|2|U|)(|K| = max{|T c (x i )|,x i ∈ U}) .Finally, an example is used to illustrate the efficiency of the new algorithm.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Pawlak, Z., Skowron, A.: Rudiments of rough sets. Information Science 117, 3–37 (2007)
Pawlak, Z., Wong, S.K.M., Ziarko, W.: Rough sets: probabilistic versus deterministic approach. Computational Intelligence 29, 81–95 (1988)
Hu, F., Huang, H., Wang, G.Y.: Granular Computing in Incomplete Information Systems. Mini-Micro Systems 26, 1335–1339 (2005)
He, W., Liu, C.Y., Zhao, J.: An algorithm of Attributes Reduction in Incomplete Information System. Computer Science 31, 117–119 (2004)
Shu, W.H., Xu, Z.Y., Qian, W.B.: Attribution reduction algorithm based on discernibility matrix of incomplete decision table. Computer Engineering and Applications 47, 105–110 (2011)
Huang, B., Zhou, X.Z., Zhang, R.R.: Attribution reduction algorithm based on information content in incomplete information Systems. Systems Engineering Theory and Practice 25, 55–60 (2005)
Ge, H., Li, L.S., Yang, C.J.: An Efficient Attribute Reduction Algorithm Based on Conflict Region. Chinese Journal of Computers 35, 342–350 (2012)
Shu, W.H., Xu, Z.Y., Qian, W.B.: Quick Attribution Reduction Algorithm Based on Incomplete Decision Table. Journal of Chinese Computer Systems 32, 1867–1871 (2011)
Wong, S.K.M., Ziarko, W.: Optimal decision rules in decision table. Bulletin of Polish Academy of Sciences 33, 693–696 (1985)
Wang, W., Xu, Z.Y., Li, X.Y.: Attribute reduction algorithm based on object matrix in incomplete decision table. Computer Science 39, 201–204 (2012)
Pawlak, Z.: Rough sets. International Journal of Computer and Information Sciences 11, 341–356 (1982)
Skowron, A., Rauszer, C.: The Discernibility Functions Matrics and Functions in Information Systems. In: Slowinski, R. (ed.) Intelligent Decision Support - Handbook of Applications and Advances of the Rough Sets Theory, pp. 331–362. Kluwer Academic Publisher, Dordrecht (1992)
Hu, X.H., Cercone, N.: Learning in Relational Database: A Rough Set Approach. International Journal of Computional Intelligence 11(2), 323–338 (1995)
Nguyen, H.S., Nguyen, S.H.: Some Efficient Algorithms for Rough Set Methods. In: The Sixth International Conference, Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU 1996), Granada, Spain, July 1-5, vol. 2, pp. 1451–1456 (1996)
Wang, G.Y., Yu, H., Yang, D.C.: Decision Table Reduction Based on Conditional Information Entropy. Chinese Journal of Computers 25(7), 759–766 (2002)
Liu, S.H., Cheng, Q.J., Shi, Z.Z.: A New Method for Fast Computing Positve Region. Journal of Computer Research and Development 40(5), 637–642 (2003)
Wang, J., Wang, J.: Reduction Algorithms Based on Discernibility Matrix: the Ordered Attributed Method. Journal of Computer Science and Technology 11(6), 489–504 (2001)
Zhao, M., Wang, J.: The Data Description Based on Reduct. PhD Thesis, Institute of Automation, Chinese Academy of Sciences, Beijing, China (2004) (in Chinese)
Moshkov, M.J., Piliszczuk, M., Zielosko, B.: On Partial Covers, Reducts and Decision Rules with Weights. In: Peters, J.F., Skowron, A., Düntsch, I., Grzymała-Busse, J.W., Orłowska, E., Polkowski, L. (eds.) Transactions on Rough Sets VI. LNCS, vol. 4374, pp. 211–246. Springer, Heidelberg (2007)
Qin, Z.R., Wu, Y., Wang, G.Y.: A Partition Algorithm for Huge Data Sets Based on Rough Set. Pattern Recognition and Artificial Intelligence 19(2), 249–256 (2006)
Hu, F., Wang, G.Y.: Analysis of the Complexity of Quick Sort for Two Dimension Table. Chinese Journal of Computers 30(6), 963–968 (2007) (in Chinese)
Hu, F., Wang, G., Xia, Y.: Attribute Core Computation Based on Divide and Conquer Method. In: Kryszkiewicz, M., Peters, J.F., Rybiński, H., Skowron, A. (eds.) RSEISP 2007. LNCS (LNAI), vol. 4585, pp. 310–319. Springer, Heidelberg (2007)
Wang, G.Y.: Rough Set Theory and Knowledge Acquisition. Xi’an Jiaotong University Press, Xi’an (2001) (in Chinese)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Xu, Z., Zhou, J., Zhang, C. (2013). A Quick Attribute Reduction Algorithm Based on Incomplete Decision Table. In: Yang, Y., Ma, M., Liu, B. (eds) Information Computing and Applications. ICICA 2013. Communications in Computer and Information Science, vol 391. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-53932-9_49
Download citation
DOI: https://doi.org/10.1007/978-3-642-53932-9_49
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-53931-2
Online ISBN: 978-3-642-53932-9
eBook Packages: Computer ScienceComputer Science (R0)