Fuzzy Population-Based Meta-Heuristic Approaches for Attribute Reduction in Rough Set Theory

Authors: Mafarja Majdi, Salwani Abdullah, Najmeh S. Jaddi

Abstract:

One of the global combinatorial optimization problems in machine learning is feature selection. It concerned with removing the irrelevant, noisy, and redundant data, along with keeping the original meaning of the original data. Attribute reduction in rough set theory is an important feature selection method. Since attribute reduction is an NP-hard problem, it is necessary to investigate fast and effective approximate algorithms. In this paper, we proposed two feature selection mechanisms based on memetic algorithms (MAs) which combine the genetic algorithm with a fuzzy record to record travel algorithm and a fuzzy controlled great deluge algorithm, to identify a good balance between local search and genetic search. In order to verify the proposed approaches, numerical experiments are carried out on thirteen datasets. The results show that the MAs approaches are efficient in solving attribute reduction problems when compared with other meta-heuristic approaches.

Keywords: Rough Set Theory, Attribute Reduction, Fuzzy Logic, Memetic Algorithms, Record to Record Algorithm, Great Deluge Algorithm.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1110459

References:

[1] R. Jensen and Q. Shen, "Fuzzy-rough sets for descriptive dimensionality reduction," presented at the Fuzzy Systems, 2002. FUZZ-IEEE'02. Proceedings of the 2002 IEEE International Conference on, 2002.
[2] L. Ke, Z. Feng, and Z. Ren, "An efficient ant colony optimization approach to attribute reduction in rough set theory," Pattern Recognition Letters, vol. 29, 2008, pp. 1351-1357.
[3] S. Theodoridis and K. Koutroumbas, Pattern Recognition, Third ed. Orlando, FL, USA Academic Press, Inc. , 2006.
[4] Z. Pawalk, "Rough sets: theoretical aspects of reasoning about data," ed: Dordrecht: Kluwer Academic Publishers, 1991.
[5] Z. Pawlak, "Rough Sets," International Journal of Information and Computer Sciences, vol. 11, 1982, pp. 341-356.
[6] Z. Pawlak, "Rough sets and data analysis," presented at the Fuzzy Systems Symposium, 1996. 'Soft Computing in Intelligent Systems and Information Processing', 1996.
[7] Z. Pawlak and A. Skowron, "Rudiments of rough sets," Information sciences, vol. 177, 2007, pp. 3-27.
[8] R. W. Swiniarski and A. Skowron, "Rough set methods in feature selection and recognition," Pattern Recognition Letters, vol. 24, 2003, pp. 833-849.
[9] A. Skowron and C. Rauszer, "The discernibility matrices and functions in information systems," Intelligent decision support–Handbook of applications and advances of the rough set theory, 1992, pp. 311–362.
[10] R. Jensen and Q. Shen, "Semantics-Preserving Dimensionality Reduction: Rough and Fuzzy-Rough-Based Approaches," IEEE Trans. on Knowl. and Data Eng., vol. 16, 2004, pp. 1457-1471.
[11] J. G. Bazan, A. Skowron, and P. Synak, "Dynamic Reducts as a Tool for Extracting Laws from Decisions Tables," presented at the Proceedings of the 8th International Symposium on Methodologies for Intelligent Systems, 1994.
[12] J. Wroblewski, "Finding minimal reducts using genetic algorithms," presented at the 2nd Annual Joint Conf. on Information Sciences, Wrightsville Beach, NC, 1995.
[13] A.-R. Hedar, J. Wang, and M. Fukushima, "Tabu search for attribute reduction in rough set theory," Soft Comput., vol. 12, 2006, pp. 909-918.
[14] J. Wang, A.-R. Hedar, G. Zheng, and S. Wang, "Scatter Search for Rough Set Attribute Reduction," presented at the Bio-Inspired Computing: Theories and Applications, 2007. BIC-TA 2007. Second International Conference on, 2007.
[15] S. Abdullah and N. S. Jaddi, "Great Deluge Algorithm for Rough Set Attribute Reduction," in Database Theory and Application, Bio-Science and Bio-Technology. vol. 118, Y. Zhang, A. Cuzzocrea, J. Ma, K.-i. Chung, T. Arslan, and X. Song, Eds., ed: Springer Berlin Heidelberg, 2010, pp. 189-197.
[16] S. K. Jihad and S. Abdullah, "Investigating composite neighbourhood structure for attribute reduction in rough set theory," presented at the Intelligent Systems Design and Applications (ISDA), 10th International Conference, 2010.
[17] Y. Z. Arajy and S. Abdullah, "Hybrid variable neighbourhood search algorithm for attribute reduction in Rough Set Theory," presented at the Intelligent Systems Design and Applications (ISDA), 2010.
[18] S. Abdullah, N. R. Sabar, M. Z. A. Nazri, H. Turabieh, and B. McCollum, "A constructive hyper-heuristics for rough set attribute reduction," presented at the Intelligent Systems Design and Applications (ISDA), 2010.
[19] M. Mafarja and S. Abdullah, "Modified great deluge for attribute reduction in rough set theory," presented at the Fuzzy Systems and Knowledge Discovery (FSKD), 2011.
[20] D. Koller and M. Sahami, "Toward Optimal Feature Selection," presented at the International Conference on Machine Learning 1996.
[21] R. Kohavi and G. H. John, "Wrappers for feature subset selection," Artificial Intelligence vol. 97, 1997, pp. 273-324.
[22] G. H. John, R. Kohavi, and K. Pfleger, "Irrelevant Features and the Subset Selection Problem", 1994.
[23] R. Jensen and Q. Shen, Computational Intelligence and Feature Selection: Rough and Fuzzy Approaches: Wiley-IEEE Press, 2008.
[24] J. Dong, N. Zhong, and S. Ohsuga, "Using Rough Sets with Heuristics for Feature Selection," presented at the Proceedings of the 7th International Workshop on New Directions in Rough Sets, Data Mining, and Granular-Soft Computing, 1999.
[25] J. Bazan, H. S. Nguyen, S. H. Nguyen, P. Synak, and J. Wróblewski, "Rough set algorithms in classification problem," Rough Set Methods and Applications. Physica Verlag, 2000, pp. 49–88.
[26] P. Moscato, "On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts - Towards Memetic Algorithms," California Instiyute of Technology, Pasadena, CA1989.
[27] C. Guerra-Salcedo, S. Chen, D. Whitley, and S. Smith, "Fast and accurate feature selection using hybrid genetic strategies," presented at the Genetic and Evolutionary Computation Conf, 1999.
[28] I. S. Oh, J. S. Lee, and B. R. Moon, "Hybrid genetic algorithms for feature selection," Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 26, 2004, pp. 1424-1437.
[29] N. Krasnogor, "Studies on the Theory and Design Space of Memetic Algorithms" PhD, University of the West of England, 2002, 2002.
[30] W. E. Hart, N. Krasnogor, and J. E. Smith, "Recent Advances in Memetic Algorithms," vol. 166, 2005.
[31] J. H. Holland, Adaptation in natural and artificial systems: MIT Press, 1992.
[32] J. Yang and V. G. Honavar, "Feature Subset Selection Using a Genetic Algorithm," IEEE Intelligent Systems, vol. 13, pp. 44-49, 1998.
[33] Z. Michalewicz, Genetic algorithms+ data structures: Springer, 1996.
[34] L. A. Zadeh, "Fuzzy sets," Information and Control, vol. 8, 1965, pp. 338-353.
[35] R. Jensen and Q. Shen, "New approaches to fuzzy-rough feature selection," Fuzzy Systems, IEEE Transactions on, vol. 17, 2009, pp. 824- 838.
[36] E. Cox, The fuzzy systems handbook: a practitioner's guide to building, using, and maintaining fuzzy systems: Academic Press Professional, Inc., 1994.
[37] H. Zimmermann, Fuzzy Set Theory and its Applications: Kluwer Academic Publishers, Boston, 1996.
[38] G. Dueck, "New Optimization Heuristics The Great Deluge Algorithm and the Record-to-Record Travel," Journal of Computational Physics,, vol. 104, 1993, pp. 86-92.
[39] R. Jensen and Q. Shen, "Finding Rough Set Reducts with Ant Colony Optimization," in Proceedings of the 2003 UK Workshop on Computational Intelligence, ed, 2003, pp. 15–22
[40] A. Øhrn, "Discernibility and rough sets in medicine: tools and applications," Department of Computer and Information Science, Norwegian University of Science and Technology, Trondheim, Norway, 1999.
[41] S. Abdullah, N.R. Sabar, M.Z. Ahmad Nazri, M. Ayob. “An Exponential Monte-Carlo algorithm for feature selection problems”, Computers & Industrial Engineering. vol 67 (2014), pp 160-167.