Selecting Efficient Features via a Hyper-Heuristic Approach

Mitra Montazeri, Mahdieh Soleymani Baghshah, Aliakbar NiknafsarXiv 2016 · OpenReview

TL;DR

This paper introduces a novel "hyper-heuristic" approach for feature selection, a crucial step in machine learning for improving model accuracy and efficiency. By employing a genetic algorithm as a supervisor to intelligently manage a suite of 16 local search heuristics, the proposed method effectively balances exploration and exploitation, outperforming existing techniques on benchmark datasets.

What Problem Does This Paper Address?

In the era of massive datasets, selecting the most informative features is paramount for building accurate and computationally efficient machine learning models. Feature selection aims to identify a subset of features that maximizes predictive performance while minimizing complexity. The challenge lies in the sheer number of possible feature combinations, making exhaustive search computationally infeasible. Traditional heuristic algorithms often struggle to strike the right balance between exploring new areas of the solution space and exploiting promising regions, leading to suboptimal solutions and slow convergence.

Methods

The core innovation of this paper is the application of a hyper-heuristic approach to feature selection. A hyper-heuristic is a meta-level strategy that orchestrates a set of lower-level heuristics. In this work:

  • Supervisor: A Genetic Algorithm (GA) acts as the supervisor. It evolves a population of "chromosomes," where each chromosome represents a sequence of low-level heuristics to be applied. The GA's fitness function is based on the classification accuracy achieved by the selected feature subset.
  • Low-Level Heuristics (Local Searches): A collection of 16 heuristic algorithms are employed as local search operators. These are categorized into two types:
  • Hill Climbing (Exploitation): These heuristics aim to improve the current solution by making small, incremental changes that enhance performance. Examples include Steepest Descent Hill Climbing (SDHC), Next Ascent Hill Climbing (NAHC), Davis' Bit Hill Climbing (DBHC), and Random Mutation Hill Climbing (RMHC).
  • Mutation/Jump (Exploration): These heuristics introduce more significant, often random, changes to the solution to explore new regions of the search space. Examples include Swap Dimension (SWPD), Dimensional Mutation (DIMM), Hypermutation (HYPM), and Mutation (MUTN).
  • Problem Representation: Feature subsets are represented as binary strings, where each bit corresponds to the presence (1) or absence (0) of a feature. The quality of a feature subset is evaluated using a 1-Nearest Neighbor (1NN) classifier.

The hyper-heuristic framework allows the GA to learn which local search heuristics are most effective in different parts of the search space, dynamically adapting its strategy to achieve better results.

Datasets

The proposed method was evaluated on five publicly available datasets from the UCI Machine Learning Repository:

  • Dermatology
  • Spectf
  • Ionoshere
  • Sonar
  • Musk

Key Insights and Ideas

  • Intelligent Orchestration of Heuristics: The paper demonstrates that simply having a collection of heuristics isn't enough; intelligently managing their application is key. The hyper-heuristic framework provides this intelligence.
  • Balancing Exploration and Exploitation: The GA supervisor effectively balances exploring diverse feature subsets (exploration) with refining promising ones (exploitation), a critical factor for overcoming the limitations of traditional heuristics.
  • Adaptability to Search Space Characteristics: By allowing the supervisor to choose local searches based on the current search region and historical performance, the approach can adapt to the unique characteristics of different parts of the feature selection landscape.
  • Feature Selection as a Meta-Problem: Framing feature selection as a problem of selecting and sequencing lower-level heuristics highlights the meta-heuristic nature of the proposed solution.

Key Results

The empirical study showed that the proposed hyper-heuristic approach consistently outperformed recent existing methods on the tested UCI datasets.

  • Accuracy Improvement: The method achieved competitive or superior classification accuracy across all datasets compared to other wrapper and filter-based feature selection techniques.
  • Efficiency: The algorithm demonstrated a good convergence rate, requiring a relatively small number of search iterations (e.g., 200 generations).
  • Feature Reduction: The method effectively reduced the number of features while maintaining or improving classification performance. For instance, on the Dermatology dataset, it achieved an accuracy of 0.9817 with 29 features, outperforming a reference method that used 97.28% accuracy (likely a different metric or evaluation setup, but the paper highlights its own results as superior).

Limitations and Future Work

  • Dataset Specificity: While tested on several datasets, the performance might vary on datasets with different characteristics.
  • Parameter Tuning: The performance of the GA supervisor and the choice of local search heuristics can be sensitive to parameter settings.
  • Future Work: The authors suggest exploring other meta-heuristic algorithms as supervisors and expanding the repertoire of low-level heuristics. Further investigation into the interpretability of the selected feature subsets and their impact on model understanding could also be valuable.

Summary updated

Abstract

By Emerging huge databases and the need to efficient learning algorithms on these datasets, new problems have appeared and some methods have been proposed to solve these problems by selecting efficient features. Feature selection is a problem of finding efficient features among all features in which the final feature set can improve accuracy and reduce complexity. One way to solve this problem is to evaluate all possible feature subsets. However, evaluating all possible feature subsets is an exhaustive search and thus it has high computational complexity. Until now many heuristic algorithms have been studied for solving this problem. Hyper-heuristic is a new heuristic approach which can search the solution space effectively by applying local searches appropriately. Each local search is a neighborhood searching algorithm. Since each region of the solution space can have its own characteristics, it should be chosen an appropriate local search and apply it to current solution. This task is tackled to a supervisor. The supervisor chooses a local search based on the functional history of local searches. By doing this task, it can trade of between exploitation and exploration. Since the existing heuristic cannot trade of between exploration and exploitation appropriately, the solution space has not been searched appropriately in these methods and thus they have low convergence rate. For the first time, in this paper use a hyper-heuristic approach to find an efficient feature subset. In the proposed method, genetic algorithm is used as a supervisor and 16 heuristic algorithms are used as local searches. Empirical study of the proposed method on several commonly used data sets from UCI data sets indicates that it outperforms recent existing methods in the literature for feature selection.
BibTeX
@misc{montazeri2016selecting,
  author = {Mitra Montazeri and Mahdieh Soleymani Baghshah and Aliakbar Niknafs},
  title = {{Selecting Efficient Features via a Hyper-Heuristic Approach}},
  year = {2016},
  eprint = {1601.05409},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1601.05409},
}
Figure