×

A rough set approach to feature selection based on scatter search metaheuristic. (English) Zbl 1294.93074

Summary: Rough set theory is an effective method to feature selection, which has recently fascinated many researchers. The essence of rough set approach to feature selection is to find a subset of the original features. It is, however, an NP-hard problem finding a minimal subset of the features, and it is necessary to investigate effective and efficient heuristic algorithms. This paper presents a novel rough set approach to feature selection based on scatter search metaheuristic. The proposed method, called Scatter Search rough set Attribute Reduction (SSAR), is illustrated by 13 well known datasets from UCI machine learning repository. The proposed heuristic strategy is compared with typical attribute reduction methods including genetic algorithm, ant colony, simulated annealing, and Tabu search. Computational results demonstrate that our algorithm can provide efficient solution to find a minimal subset of the features and show promising and competitive performance on the considered datasets.

MSC:

93E03 Stochastic systems in control theory (general)
90C59 Approximation methods and heuristics in mathematical programming
68T05 Learning and adaptive systems in artificial intelligence
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Pawlak Z, Rough sets, International Journal of Computer and Information Sciences, 1982, 11: 341-356. · Zbl 0501.68053 · doi:10.1007/BF01001956
[2] Pawlak Z, Rough Sets: Theoretical Aspects of Reasoning About Data, Kluwer Academic Publishers, Boston, 1991. · Zbl 0758.68054 · doi:10.1007/978-94-011-3534-4
[3] Pawlak Z and Skowron A, Rough Set Methods and Applications: New Developments in Knowledge Discovery in Information Systems, Studies in Fuzziness and Soft Computing, Physica-Verlag, Berlin, 2000.
[4] Swiniarski R W and Skowron A, Rough set methods in feature selection and recognition, Pattern Recognition Letters, 2003, 24: 833-849. · Zbl 1053.68093 · doi:10.1016/S0167-8655(02)00196-4
[5] Jensen R and Shen Q, Semantics-preserving dimensionality reduction: Rough and fuzzy-roughbased approaches, IEEE Trans. on Knowledge and Data Engineering, 2004, 16: 1457-1471. · doi:10.1109/TKDE.2004.96
[6] Wong S K M and Ziarko W, On optional decision rules in decision tables, Bull. Polish Acad. Sci., 1985, 33: 693-696. · Zbl 0606.68091
[7] Osman I H and Kelly J P, Meta-Heuristics: Theory and Applications, Kluwer Academic Publishers, Boston, 1996. · Zbl 0869.00056 · doi:10.1007/978-1-4613-1361-8
[8] Wro’blewski, J., Finding minimal reducts using genetic algorithms, 186-189 (1995)
[9] Zhai L Y, Khoo L P, and Fok S C, Feature extraction using rough set theory and genetic algorithms — An application for the simplification of product quality evaluation, Computers and Industrial Engineering, 2002, 43: 661-676. · doi:10.1016/S0360-8352(02)00131-6
[10] Ke L J, Feng Z R, and Ren Z G, An efficient ant colony optimization approach to attribute reduction in rough set theory, Pattern Recognition Letters, 2008, 29: 1351-1357. · doi:10.1016/j.patrec.2008.02.006
[11] Hedar A, Wang J, and Fukushima M, Tabu search for attribute reduction in rough set theory, Soft Computing, 2008, 12: 909-918. · Zbl 1151.68643 · doi:10.1007/s00500-007-0260-1
[12] Laguna M and Marti R, Scatter Search: Methodology and Implementations, C. Kluwer Academic Publishers, Boston, 2003. · doi:10.1007/978-1-4615-0337-8
[13] Rego C and Alidaee B, Metaheursitic Optimization via Memory and Evolution, Springer-Verlag, Berlin, 2005. · Zbl 1058.90006
[14] Glover F, Heuristics for integer programming using surrogate constraints, Decision Sciences, 1977, 8: 156-166. · doi:10.1111/j.1540-5915.1977.tb01074.x
[15] Manish S, Rough-fuzzy functions in classification, Fuzzy Sets and Systems, 2002, 132: 353-369. · Zbl 1008.68582 · doi:10.1016/S0165-0114(02)00119-7
[16] Pal S K, Shankar B U, and Mitra P, Granular computing, rough entropy, and object extraction. Pattern Recognition Letters, 2005, 26(16) 2509-2517. · doi:10.1016/j.patrec.2005.05.007
[17] Liang J Y and Shi Z Z, The information entropy, rough entropy, and knowledge granulation in rough set theory, International Journal of Uncertainty, Fuzziness, and Knowledge-Based Systems, 2004, 12: 56-67. · Zbl 1074.68072 · doi:10.1142/S0218488504002631
[18] Glover F, Surrogate constraints, Operations Research, 1968, 16: 741-749. · Zbl 0165.22602 · doi:10.1287/opre.16.4.741
[19] Glover F, A template for scatter search and path relinking, artificial evolution, Hao J K, Lutton E, Schoenauer M, Snyers D, Lecture Notes in Computer Science 1363, Springer, 1998, 125-137.
[20] Glover F, Laguna M, and Mart R, Scatter search and path relinking: Advances and applications, Glover F, Kochenberger G A, Handbook of Metaheuristics, Kluwer Academic Publishers, Boston, 2003. · Zbl 1041.90074
[21] Jensen, R.; Shen, Q., Finding rough set reducts with ant colony optimization, 15-22 (2003)
[22] Glover F and Kochenberger G A, Handbook of Metaheuristics, Kluwer Academic Publishers, Boston, 2003. · Zbl 1058.90002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.