IDEAS home Printed from https://ideas.repec.org/a/spr/joheur/v22y2016i2d10.1007_s10732-015-9307-0.html
   My bibliography  Save this article

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

Author

Listed:
  • Mateus Rocha de Paula

    (The University of Newcastle)

  • Regina Berretta

    (The University of Newcastle)

  • Pablo Moscato

    (The University of Newcastle)

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.

Suggested Citation

  • Mateus Rocha de Paula & Regina Berretta & Pablo Moscato, 2016. "A fast meta-heuristic approach for the $$(\alpha ,\beta )-k$$ ( α , β ) - k -feature set problem," Journal of Heuristics, Springer, vol. 22(2), pages 199-220, April.
    • Handle: RePEc:spr:joheur:v:22:y:2016:i:2:d:10.1007_s10732-015-9307-0
    DOI: 10.1007/s10732-015-9307-0
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10732-015-9307-0
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10732-015-9307-0?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Fred Glover, 1989. "Tabu Search---Part I," INFORMS Journal on Computing, INFORMS, vol. 1(3), pages 190-206, August.
    2. Timothy G Lesnick & Spiridon Papapetropoulos & Deborah C Mash & Jarlath Ffrench-Mullen & Lina Shehadeh & Mariza de Andrade & John R Henley & Walter A Rocca & J Eric Ahlskog & Demetrius M Maraganore, 2007. "A Genomic Pathway Approach to a Complex Disease: Axon Guidance and Parkinson Disease," PLOS Genetics, Public Library of Science, vol. 3(6), pages 1-12, June.
    3. Fred Glover, 1990. "Tabu Search—Part II," INFORMS Journal on Computing, INFORMS, vol. 2(1), pages 4-32, February.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Cazzaro, Davide & Fischetti, Martina & Fischetti, Matteo, 2020. "Heuristic algorithms for the Wind Farm Cable Routing problem," Applied Energy, Elsevier, vol. 278(C).
    2. Huang, Yeran & Yang, Lixing & Tang, Tao & Gao, Ziyou & Cao, Fang, 2017. "Joint train scheduling optimization with service quality and energy efficiency in urban rail transit networks," Energy, Elsevier, vol. 138(C), pages 1124-1147.
    3. B Dengiz & C Alabas-Uslu & O Dengiz, 2009. "Optimization of manufacturing systems using a neural network metamodel with a new training approach," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(9), pages 1191-1197, September.
    4. S-W Lin & K-C Ying, 2008. "A hybrid approach for single-machine tardiness problems with sequence-dependent setup times," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(8), pages 1109-1119, August.
    5. Joseph B. Mazzola & Robert H. Schantz, 1997. "Multiple‐facility loading under capacity‐based economies of scope," Naval Research Logistics (NRL), John Wiley & Sons, vol. 44(3), pages 229-256, April.
    6. Abdmouleh, Zeineb & Gastli, Adel & Ben-Brahim, Lazhar & Haouari, Mohamed & Al-Emadi, Nasser Ahmed, 2017. "Review of optimization techniques applied for the integration of distributed generation from renewable energy sources," Renewable Energy, Elsevier, vol. 113(C), pages 266-280.
    7. Masoud Yaghini & Mohammad Karimi & Mohadeseh Rahbar, 2015. "A set covering approach for multi-depot train driver scheduling," Journal of Combinatorial Optimization, Springer, vol. 29(3), pages 636-654, April.
    8. Chris S. K. Leung & Henry Y. K. Lau, 2018. "Multiobjective Simulation-Based Optimization Based on Artificial Immune Systems for a Distribution Center," Journal of Optimization, Hindawi, vol. 2018, pages 1-15, May.
    9. Ilfat Ghamlouche & Teodor Gabriel Crainic & Michel Gendreau, 2003. "Cycle-Based Neighbourhoods for Fixed-Charge Capacitated Multicommodity Network Design," Operations Research, INFORMS, vol. 51(4), pages 655-667, August.
    10. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part II: Metaheuristics," Transportation Science, INFORMS, vol. 39(1), pages 119-139, February.
    11. Andaryan, Abdullah Zareh & Mousighichi, Kasra & Ghaffarinasab, Nader, 2024. "A heuristic approach to the stochastic capacitated single allocation hub location problem with Bernoulli demands," European Journal of Operational Research, Elsevier, vol. 312(3), pages 954-968.
    12. Panta Lučić & Dušan Teodorović, 2007. "Metaheuristics approach to the aircrew rostering problem," Annals of Operations Research, Springer, vol. 155(1), pages 311-338, November.
    13. Daniel O’Malley & Velimir V Vesselinov & Boian S Alexandrov & Ludmil B Alexandrov, 2018. "Nonnegative/Binary matrix factorization with a D-Wave quantum annealer," PLOS ONE, Public Library of Science, vol. 13(12), pages 1-12, December.
    14. Marco Antonio Boschetti & Vittorio Maniezzo, 2022. "Matheuristics: using mathematics for heuristic design," 4OR, Springer, vol. 20(2), pages 173-208, June.
    15. C-H Lan & C-C Chen, 2007. "Optimal purchase of two-itemized drugs for a disease," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(3), pages 309-316, March.
    16. G Lulli & U Pietropaoli & N Ricciardi, 2011. "Service network design for freight railway transportation: the Italian case," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(12), pages 2107-2119, December.
    17. Sadan Kulturel-Konak & Bryan A. Norman & David W. Coit & Alice E. Smith, 2004. "Exploiting Tabu Search Memory in Constrained Problems," INFORMS Journal on Computing, INFORMS, vol. 16(3), pages 241-254, August.
    18. Ouzineb, Mohamed & Nourelfath, Mustapha & Gendreau, Michel, 2008. "Tabu search for the redundancy allocation problem of homogenous series–parallel multi-state systems," Reliability Engineering and System Safety, Elsevier, vol. 93(8), pages 1257-1272.
    19. İlker Küçükoğlu & Nursel Öztürk, 2019. "A hybrid meta-heuristic algorithm for vehicle routing and packing problem with cross-docking," Journal of Intelligent Manufacturing, Springer, vol. 30(8), pages 2927-2943, December.
    20. J Brimberg & P Hansen & G Laporte & N Mladenović & D Urošević, 2008. "The maximum return-on-investment plant location problem with market share," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(3), pages 399-406, March.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:joheur:v:22:y:2016:i:2:d:10.1007_s10732-015-9307-0. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.