Hybrid Learning Using Genetic Algorithms and Decision Trees for Pattern Classification

IJCAI 1995

TL;DR

This paper introduces a novel hybrid approach that combines Genetic Algorithms (GAs) with Decision Tree learning (ID3) to automatically discover optimal subsets of features for pattern classification. By intelligently searching for the best feature combinations and evaluating them with decision trees, this method achieves improved classification accuracy and simpler models compared to traditional feature selection techniques.

What Problem Does This Paper Address?

Pattern classification, a cornerstone of Artificial Intelligence, often struggles with the sheer volume and complexity of raw data. Identifying the most informative features from a large pool is crucial for building efficient and accurate classifiers. Traditional methods often rely on statistical measures that don't fully capture how features interact or their actual impact on classification performance. This can lead to suboptimal feature sets, resulting in lower accuracy and overly complex models. The paper addresses the challenge of finding not just a good set of features, but an optimal subset that maximizes classification performance while minimizing complexity, especially when dealing with noisy, high-dimensional data and complex feature interactions.

Methods

The core of this paper is a hybrid learning system that integrates two powerful AI techniques:

  • Genetic Algorithms (GAs): GAs are used as a search mechanism. They explore the vast space of all possible feature subsets. Each "individual" in the GA population represents a specific combination of features. The GA evolves these populations over generations, favoring feature subsets that lead to better classification.
  • Decision Tree Learning (ID3): For each feature subset proposed by the GA, an ID3 decision tree is built using the training data corresponding to those features. The performance of this decision tree on unseen data (its classification accuracy) is then used as the "fitness" measure for that feature subset in the GA.

This GA-ID3 process iterates: the GA proposes feature subsets, ID3 evaluates them, and the GA uses this feedback to generate even better subsets. This continues until a satisfactory feature subset is found. The representation for the GA is a simple binary string where each bit indicates whether a particular feature is included or not, allowing for standard GA operations.

Datasets

The authors evaluated their hybrid system on two distinct datasets:

  • Satellite Image Data: This dataset consists of multi-spectral values from Landsat MSS imagery, representing different land cover types. Each example is derived from a 3x3 neighborhood of pixels, with features extracted from four spectral bands. The data includes 4435 learning examples and 2000 test examples, with 36 initial features and 6 decision classes.
  • Facial Image Data: This dataset focuses on eye detection for face recognition. It includes features extracted from facial regions (eyes, nose, and other areas). The dataset comprises 102 learning examples and 52 test examples, with an initial set of 105 features and 3 decision classes.

Key Insights and Ideas

  • Synergy of GA and ID3: The paper demonstrates that combining a global search strategy (GA) with a direct performance evaluation (ID3) is more effective than using either alone or relying on traditional statistical feature ranking. The GA can explore complex, non-linear feature interactions that simpler methods miss.
  • Fitness Function Matters: Using actual classification accuracy on unseen data as the fitness metric for the GA is crucial. This directly links feature subset selection to the ultimate goal of robust classification, unlike methods that use proxy measures.
  • Reduced Complexity, Improved Performance: The hybrid approach not only finds better feature subsets but also leads to simpler decision trees. This is important for interpretability and computational efficiency.
  • Beyond Pairwise Interactions: GAs are well-suited to discover combinations of features that work well together, even if individual features are not highly discriminatory on their own.

Key Results

The GA-ID3 system demonstrated significant improvements on both datasets:

  • Satellite Data: The GA-ID3 system achieved an error rate of 16.9% with 72 nodes in the decision tree. This is better than using all 36 features (18.5% error rate, 99 nodes) and also better than a feature set reduced by independent ranking (17.25% error rate, 83 nodes). The number of features was reduced by 52%.
  • Facial Data: For facial data, the GA-ID3 system achieved a 27.5% error rate with 13 nodes, outperforming the full feature set (38.4% error rate, 8 nodes) and the independently ranked set (38.5% error rate, 11 nodes). The number of features was reduced by 60%.
  • General Trend: Across both datasets, the GA-ID3 approach consistently yielded lower error rates and, in the case of satellite data, significantly reduced tree complexity compared to baseline methods.

Limitations and Future Work

The authors acknowledge that while their approach is promising, the datasets used, though complex for symbolic machine learning, are still "modest" from an image processing perspective. They are actively working on refining the system for larger and more complex problems.

Future work could involve:

  • Richer Feedback from ID3: Currently, only classification accuracy is fed back to the GA. Incorporating information about which features were actually used in the decision tree and their importance could further enhance the GA's search.
  • Exploring Other Induction Algorithms: While ID3 was used, the hybrid framework could potentially be extended to other decision tree algorithms or even different types of classifiers.
  • Investigating Other Feature Interaction Measures: Further research into how to best represent and exploit feature interactions within the GA framework could yield even better results.

Summary updated

BibTeX
@inproceedings{1995hybrid,
  title = {{Hybrid Learning Using Genetic Algorithms and Decision Trees for Pattern Classification}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1995},
}
Figure