Abstract
This paper critically analyzes reduct construction methods at two levels. At a high level, one can abstract commonalities from the existing algorithms, and classify them into three basic groups based on the underlying control structures. At a low level, by adopting different heuristics or fitness functions for attribute selection, one is able to derive most of the existing algorithms. The analysis brings new insights into the problem of reduct construction, and provides guidelines for the design of new algorithms.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Bazan, J.G., Nguyen, H.S., Nguyen, S.H., Synak, P., Wroblewski, J.: Rough set algorithms in classification problem. In: Polkowski, L., Tsumoto, S., Lin, T.Y. (eds.) Rough Set Methods and Applications, pp. 49–88 (2000)
Beaubouef, T., Petry, F.E., Arora, G.: Information-theoretic measures of uncertainty for rough sets and rough relational databases. Information Sciences 109, 185–195 (1998)
Blum, A.L., Langley, P.: Selection of relevant features and examples in machine learning. Artificial Intelligence, 245–271 (1997)
Devijver, P.A., Kittler, J.: Pattern Recognition: A Statistical Approach. Prentice-Hall, New York (1982)
Grzymala-Busse, J.W.: LERS - A system for learning from examples based on rough sets. In: Slowinski, R. (ed.) Intelligent Decision Support, pp. 3–18. Kluwer Academic Publishers, Boston (1992)
Hoa, N.S., Son, N.H.: Some efficient algorithms for rough set methods. In: Proceedings of the Conference of Information Processing and Management of Uncertainty in Knowledge-based Systems, pp. 1451–1456 (1996)
Hu, X.: Using rough sets theory and database operations to construct a good ensemble of classifiers for data mining applications. In: Proceedings of ICDM, pp. 233–240 (2001)
Hu, X., Cercone, N.: Learning in relational databases: a rough set approach. International Journal of Computation Intelligence 11, 323–338 (1995)
Jain, A.K., Zongker, D.: Feature selection: evaluation, application and small sample performance. IEEE Transactions on Pattern Analysis and Machine Intelligence 19, 153–158 (1997)
Jenson, R., Shen, Q.: A rough set-aided system for sorting WWW bookmarks. In: Zhong, N., et al. (eds.) Web Intelligence: Research and Development, pp. 95–105 (2001)
John, G.H., Kohavi, R., Pfleger, K.: Irrelevant features and the subset selection problem. In: Proceedings of the Eleventh International Conference on Machine Learning, pp. 121–129 (1994)
Kohavi, R., John, G.H.: Wrappers for feature subset selection. Artificial Intelligence, 273–324 (1997)
Koller, D., Sahami, M.: Toward optimal feature selection. In: Proceedings of the Thirteenth International Conference of Machine Learning, pp. 284–292 (1996)
Mi, J.S., Wu, W.Z., Zhang, W.X.: Approaches to knowledge reduction based on variable precision rough set model. Information Sciences 159, 255–272 (2004)
Miao, D., Hou, L.: A comparison of rough set methods and representative inductive learning algorithms. Fundamenta Informaticae 59, 203–219 (2004)
Miao, D., Wang, J.: An information representation of the concepts and operations in rough set theory. Journal of Software 10, 113–116 (1999)
Pawlak, Z.: Rough Sets: Theoretical Aspects of Reasoning About Data. Kluwer, Boston (1991)
Portinale, L., Saitta, L.: Feature selection, Technical report, D14.1, University of Dortmund (2002)
Rauszer, C.: Reducts in information systems. Foundamenta Informaticae 15, 1–12 (1991)
Shen, Q., Chouchoulas, A.: A modular approach to generating fuzzy rules with reduced attributes for the monitoring of complex systems. Engineering Applications of Artificial Intelligence 13, 263–278 (2000)
Skowron, A., Rauszer, C.: The discernibility matrices and functions in information systems. In: Slowiński, R. (ed.) Intelligent Decision Support, Handbook of Applications and Advances of the Rough Sets Theory. Kluwer, Dordrecht (1992)
Slezak, D.: Various approaches to reasoning with frequency based decision reducts: a survey. In: Polkowski, L., Tsumoto, S., Lin, T.Y. (eds.) Rough set methods and applications, pp. 235–285 (2000)
Swiniarski, R.W.: Rough sets methods in feature reduction and classification. International Journal of Applied Mathematics and Computer Science 11, 565–582 (2001)
Wang, G., Yu, H., Yang, D.: Decision table reduction based on conditional information entropy. Chinese Journal of Computers 25, 759–766 (2002)
Wang, J., Wang, J.: Reduction algorithms based on discernibility matrix: the ordered attributes method. Journal of Computer Science and Technology 16, 489–504 (2001)
Wong, S., Ziarko, W.: On optimal decision rules in decision tables. Bulletin of the Polish Academy of Sciences and Mathematics, 693–696 (1985)
Yu, H., Yang, D., Wu, Z., Li, H.: Rough set based attribute reduction algorithm. Computer Engineering and Applications 17, 22–47 (2001)
Zhao, M.: Data Description Based on Reduct Theory, Ph.D. Thesis, Institute of Automation, Chinese Academy of Sciences (2004)
Zhao, K., Wang, J.: A reduction algorithm meeting users’ requirements. Journal of Computer Science and Technology 17, 578–593 (2002)
Ziarko, W.: Rough set approaches for discovering rules and attribute dependencies. In: Klösgen, W., Żytkow, J.M. (eds.) Handbook of Data Mining and Knowledge Discovery, pp. 328–339 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Yao, Y., Zhao, Y., Wang, J. (2008). On Reduct Construction Algorithms. In: Gavrilova, M.L., Tan, C.J.K., Wang, Y., Yao, Y., Wang, G. (eds) Transactions on Computational Science II. Lecture Notes in Computer Science, vol 5150. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-87563-5_6
Download citation
DOI: https://doi.org/10.1007/978-3-540-87563-5_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-87562-8
Online ISBN: 978-3-540-87563-5
eBook Packages: Computer ScienceComputer Science (R0)