Abstract
The idea of divide and conquer method is used in developing algorithms of rough set theory. In this paper, according to the partitions of equivalence relations on attributes of decision tables, two novel algorithms for computing attribute core based on divide and conquer method are proposed. Firstly, a new algorithm for computing the positive region of a decision table is proposed, and its time complexity is O(|U|×|C|), where, |U| is the size of the set of objects and C is the size of the set of attributes. Secondly, a new algorithm for computing the attribute core of a decision table is developed, and its time complexity is O(|U|×|C|2). Both these two algorithms are linear with |U|. Simulation experiment results show that the algorithm of computing attribute core is not only efficient, but also adapt to huge data sets.
This paper is partially supported by National Natural Science Foundation of China under Grants No.60373111 and No.60573068, Program for New Century Excellent Talents in University (NCET), Natural Science Foundation of Chongqing under Grant No.2005BA2003, Science & Technology Research Program of Chongqing Education Commission under Grant No.KJ060517.
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.: Rough sets. International Journal of Computer and Information Sciences 11, 341–356 (1982)
Wang, G.Y.: Rough set theory and knowledge acquisition (in Chinese). Xi’an Jiaotong University Press, Xi’an (2001)
Fu, Q.X, Wang, X.D.: Algorithms and data structure (in Chinese). Publishing House of Electronics Industry, Beijing (2003)
Yu, X.X, Cui, G.H, Zhou, H.M.: Fundmental of Computer Algorithms (in Chinese). Huazhong University Press, Wuhan (2001)
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)
Bazan, J., Skowron, A., Synak, P.: Dynamic reductions as tool for exacting laws for decision table. Lecture Note in Artificial Intelligence, vol. 869, pp. 346–355. Springer, Berlin (1994)
Hu, X.H., Cercone, N.: Learning in relational database: A rough set approach. International Journal of Computional Intelligence 11(2), 323–338 (1995)
Jelonek, J., et al.: Rough set reduction of attributes and their domains for neural networks. Computional Intelligence 11(2), 338–347 (1995)
Ziarko, W., Shan, N.: Data-based acquisition and incremental modification classfication rules. Computational Intelligence 11(2), 357–370 (1995)
Nguyen, H.S, Nguyen, S.H.: Some efficient algorithms for rough set methods. In: IPMU”96. Proceedings of the Sixth International Conference, Information Procesing and Management of Uncertainty in Knowledge-Based Systems, Granada, Spain, July 1-5, 1996, vol. 2, pp. 1451–1456 (1996)
Susmaga, R.: Experiments in incremental computation of reducts. In: Skowron, A., Olkowski, A. (eds.) Rough Sets in Data Mining and Knowledge Discovery, Springer, Berlin (1998)
Bazan, B.J H.S., Nguyen, S.H., Nguyen, P.: Rough set algorithms in classification problem. In: Polkowski, L., Tsumoto, S., Lin, T.Y. (eds.) Rough Set Methods and Applications, pp. 49–88. Physica-Verlag, Heidelberg (2000)
Ye, D.Y., et al.: An improvement to Jelonek’s attribute reduction algorithm (in Chinese). Acta Electronica Sinica 28(12), 81–82 (2000)
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)
Liu, S.H., Sheng, Q.J., Wu, B., et al.: Research on efficient algorithms for Rough set methods (in Chinese). Chinese Journal of Computers 30(7), 1086–1088 (2002)
Wang, G.Y., Yu, H., Yang, D.C.: Decision table reduction based on conditional information entropy (in Chinese). Chinese Journal of computer 25(7), 759–766 (2002)
Liu, S.H., Cheng, Q.J., Shi, Z.Z.: A new method for fast computing positve region (in Chinese). Journal of Computer Research and Development 40(5), 637–642 (2003)
Ye, D.Y., Chen, Z.J.: A new discernibility matrix and the computation of a core (in Chinese). Acta Electronica Sinica 30(7), 1086–1088 (2002)
Wang, G.Y.: The computation method of core attribute in decision table (in Chinese). Chinese Journal of Computer 26(5), 611–615 (2003)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hu, F., Wang, G., Xia, Y. (2007). Attribute Core Computation Based on Divide and Conquer Method. In: Kryszkiewicz, M., Peters, J.F., Rybinski, H., Skowron, A. (eds) Rough Sets and Intelligent Systems Paradigms. RSEISP 2007. Lecture Notes in Computer Science(), vol 4585. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73451-2_33
Download citation
DOI: https://doi.org/10.1007/978-3-540-73451-2_33
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73450-5
Online ISBN: 978-3-540-73451-2
eBook Packages: Computer ScienceComputer Science (R0)