Abstract
Missing data has a ubiquitous presence in real-life applications of machine learning techniques. Imputation methods are algorithms conceived for restoring missing values in the data, based on other entries in the database. The choice of the imputation method has an influence on the performance of the machine learning technique, e.g., it influences the accuracy of the classification algorithm applied to the data. Therefore, selecting and applying the right imputation method is important and usually requires a substantial amount of human intervention. In this paper we propose the use of genetic programming techniques to search for the right combination of imputation and classification algorithms. We build our work on the recently introduced Python-based TPOT library, and incorporate a heterogeneous set of imputation algorithms as part of the machine learning pipeline search. We show that genetic programming can automatically find increasingly better pipelines that include the most effective combinations of imputation methods, feature pre-processing, and classifiers for a variety of classification problems with missing data.
Introduction
Missing data is a pervasive challenge in data science, often resulting from sensor failures, human error, or incomplete surveys. These "holes" in a dataset can significantly degrade the performance of machine learning models or prevent them from running entirely. The standard remedy is imputation—the process of estimating and filling in missing values based on available data.
However, selecting the optimal imputation method is not straightforward. According to the "No Free Lunch" theorem, no single imputer is universally superior; the effectiveness of a method like Mean Imputation versus a complex model like MICE depends heavily on both the dataset's characteristics and the downstream classifier. Traditionally, this selection process has relied on manual trial-and-error. This study explores automating this selection by integrating imputation directly into the evolutionary search for machine learning pipelines.
Methodology
The researchers utilized the Tree-based Pipeline Optimization Tool (TPOT), which employs Genetic Programming (GP) to evolve machine learning pipelines. In this framework, a pipeline is represented as a tree structure that undergoes evolutionary operations such as crossover (swapping pipeline segments) and mutation (randomly altering a step) to maximize predictive accuracy.
The primary contribution of this work is the expansion of TPOT's search space to include a dedicated imputation layer. As shown in Figure 1, the GP algorithm now selects from a diverse set of components:
- Imputation Methods: Simple strategies (Mean, Median, Most Frequent, Max Value) and complex statistical models (MICE and Expectation-Maximization).
- Feature Selection and Preprocessing: Various scalers and selection algorithms.
- Classification Methods: A wide array of models including Random Forests, Gradient Boosting, and Naïve Bayes.
Experimental Setup
The approach was evaluated using 23 representative datasets from the Penn Machine Learning Benchmark (PMLB), ranging in size and complexity. To simulate real-world conditions, the researchers manually injected 7% missing data into these complete datasets using a "Missing Completely At Random" (MCAR) pattern. The GP algorithm was then tasked with evolving pipelines over 50 generations to find the best "imputer + classifier" combination for each dataset.
Key Insights and Results
The Robustness of Gradient Boosting
One of the most significant findings was the emergence of Gradient Boosting (GB) as a highly robust classifier. GB consistently produced high-quality results across various imputation methods, showing less sensitivity to the specific choice of imputer than other algorithms.
Simple vs. Complex Imputers
Interestingly, simple methods like "Most Frequent" imputation frequently appeared in the top-performing pipelines. The authors suggest that at a 7% missingness rate, complex methods like MICE may introduce unnecessary noise or computational overhead without providing a proportional gain in accuracy. This highlights the importance of the automated search in finding the most efficient solution for the specific level of data corruption.
Performance Recovery
Statistical analysis using the Dunn test revealed that in 13 out of 23 databases, there was no significant difference in accuracy between the pipelines trained on imputed data and those trained on the original, complete data. This demonstrates that the GP-evolved pipelines were highly effective at "softening" the impact of missing data, restoring the model's performance to near-baseline levels.
Conclusion and Future Work
This study demonstrates that genetic programming can successfully automate the selection of imputation strategies, removing a significant manual burden from the data science workflow. While the results are promising at a 7% missingness rate, future work will explore higher thresholds of missing data where complex imputers are expected to play a more critical role. Additionally, the researchers aim to implement multi-objective optimization to balance classification accuracy with the computational cost of complex imputation methods.
Summary updated