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

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.

Authors:

• Mafarja Majdi
• Salwani Abdullah
• Najmeh S. Jaddi

Keywords:

• Rough Set Theory
• Attribute Reduction
• Fuzzy Logic
• Memetic Algorithms
• Record to Record Algorithm
• Great Deluge Algorithm.

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.