A fast meta-heuristic approach for the $$(\alpha,\beta )-k$$ ( α, β ) - k -feature set problem

Mateus Rocha de Paula (), Regina Berretta () and Pablo Moscato ()
Additional contact information
Mateus Rocha de Paula: The University of Newcastle
Regina Berretta: The University of Newcastle
Pablo Moscato: The University of Newcastle

Journal of Heuristics, 2016, vol. 22, issue 2, No 4, 199-220

Abstract: Abstract The feature selection problem aims to choose a subset of a given set of features that best represents the whole in a particular aspect, preserving the original semantics of the variables on the given samples and classes. In 2004, a new approach to perform feature selection was proposed. It was based on a NP-complete combinatorial optimisation problem called ( $$\alpha ,\beta $$ α , β )-k-feature set problem. Although effective for many practical cases, which made the approach an important feature selection tool, the only existing solution method, proposed on the original paper, was found not to work well for several instances. Our work aims to cover this gap found on the literature, quickly obtaining high quality solutions for the instances that existing approach can not solve. This work proposes a heuristic based on the greedy randomised adaptive search procedure and tabu search to address this problem; and benchmark instances to evaluate its performance. The computational results show that our method can obtain high quality solutions for both real and the proposed artificial instances and requires only a fraction of the computational resources required by the state of the art exact and heuristic approaches which use mixed integer programming models.

Keywords: $$(\upalpha; \upbeta )$$ ( α; β ) -k Feature set problem; GRASP; Tabu search; Metaheuristics; Set multi cover problem (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-015-9307-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:22:y:2016:i:2:d:10.1007_s10732-015-9307-0

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-015-9307-0

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().