TL;DR
This paper introduces a novel method using Genetic Programming (GP) to automatically generate complex, redundant features. These synthetic features are designed to be challenging for feature selection algorithms, creating valuable benchmark datasets for evaluating and improving these algorithms.
What Problem Does This Paper Address?
Feature selection (FS) is crucial for handling high-dimensional datasets, aiming to remove irrelevant or redundant features to improve model performance and interpretability. While adding irrelevant (noisy) features to datasets for testing FS algorithms is straightforward, creating redundant features that mimic real-world complexity is difficult. Redundant features share significant information with other features, and their automatic generation is essential for creating robust benchmark datasets that can truly challenge and evaluate the effectiveness of FS techniques.
Methods
The core of this work is the Genetic Programming for Redundant Feature Creation (GPRFC) approach. It employs a multi-tree GP representation, where each individual in the GP population consists of multiple trees. Each tree represents a function that transforms a single source feature (X) into a redundant feature (Y). This multi-tree structure allows for the generation of multiple, distinct redundant features from a single source feature, encouraging diversity in the types of redundancy.
The fitness function is key to guiding the GP. It's based on Mutual Information (MI), a measure of dependency between variables. The fitness aims to:
- Maximize MI between the source feature (X) and each generated redundant feature (t).
- Minimize MI between pairs of generated redundant features (t, y). This dual objective ensures that the generated features are highly redundant with the original but less redundant with each other, leading to complex and diverse redundancies. A penalty mechanism is included to ensure a minimum level of redundancy with the source feature.
The function and terminal sets for the GP are carefully chosen to allow for complex, non-linear relationships. The only terminal is the source feature (X). The function set includes various arithmetic, trigonometric, and conditional operators (like sin, tan, log, exp, pow, max, min, and a ternary if operator). To handle potential issues with feature scaling and duplicate values, the source features are scaled to [0, 1] with a small epsilon added, and a small amount of stochastic noise is introduced.
Datasets
The proposed GPRFC method was evaluated on a mix of datasets:
- Classification: Iris, Wine, Vehicle (from the UCI repository).
- Clustering: Two synthetic datasets: 10d10cE (10 dimensions, 10 clusters) and 10d40cE (10 dimensions, 40 clusters), generated using an Ellipsoidal cluster generator.
These datasets were chosen for their varying complexity and number of features, aiming to reduce the computational burden of the GP runs.
Key Insights and Ideas
- GP as a Redundancy Generator: The paper demonstrates that GP, typically used for feature construction, can be effectively repurposed for feature creation (specifically, redundant features).
- MI as a Fitness Metric for Redundancy: Using Mutual Information as the primary driver for the fitness function is a novel and effective way to quantify and optimize for complex feature dependencies.
- Multi-Tree GP for Diversity: The multi-tree representation is crucial for generating a set of redundant features that are not only redundant with the source but also distinct from each other, leading to richer benchmark datasets.
- Challenging Feature Selection: The generated redundant features, particularly on the Vehicle dataset, were shown to significantly mislead a Sequential Floating Forward Search (SFFS) algorithm, indicating their potential to create difficult benchmark scenarios.
Key Results
- High Fitness Achieved: GPRFC achieved good fitness scores (indicating high redundancy) on most datasets, particularly Iris and Vehicle. For example, on the Vehicle dataset, the typical created redundant feature had 35.1% more MI with the source feature than with other created features.
- Minimal Impact on Classification/Clustering Performance: Adding the generated redundant features to datasets generally resulted in only a small drop (2-3%) or even a slight increase in performance for classifiers and clusterers, suggesting the features are redundant rather than outright misleading in a way that degrades performance universally. However, for KNN on Iris and Vehicle, accuracy dropped by 5% and 11% respectively, indicating sensitivity to non-linear feature transformations.
- Feature Selection Difficulty: On the Vehicle dataset, an SFFS algorithm selected significantly fewer features and achieved much lower accuracy on the augmented dataset compared to the original, demonstrating that the generated redundant features can indeed "mislead" FS algorithms.
- Complex, Non-Linear Redundancies: Visualizations of the generated features showed highly varied and complex, non-linear relationships with the source features, confirming they are not trivial.
Limitations and Future Work
- One-to-One Redundancy: The current approach focuses on generating redundant features from a single source feature (one-to-one redundancy). The authors suggest exploring multivariate mutual information for creating more complex, many-to-many redundancies between sets of source features and generated features.
- Fitness Function Refinement: While the current fitness function is effective, further refinement is suggested, particularly considering a "worst-case" scenario where the highest shared MI between any two redundant features is penalized.
- GP Representation Optimization: Investigating different function sets and determining the optimal number of trees (n) for the multi-tree GP representation could further improve results.
- Broader Evaluation: While preliminary results are promising, more extensive testing is needed to definitively prove GPRFC's capability in creating difficult benchmark datasets.
Summary updated