Machine learning with incomplete datasets using multi-objective optimization models

Hadi Akbarzadeh Khorshidi, Michael Kirley, Uwe Aickelin

TL;DR

This paper introduces an "online" machine learning framework that performs data imputation and model selection simultaneously using multi-objective optimization. By treating missing data handling and classification as a joint optimization problem, the authors eliminate the need for separate, offline preprocessing steps, resulting in a robust model that maintains high accuracy even when up to 50% of the data is missing.

What Problem Does This Paper Address?

Most machine learning algorithms are designed for "complete" datasets. In the real world—particularly in medical informatics—missing values are the rule rather than the exception. Traditionally, researchers handle this in one of two ways: they either discard incomplete records (which wastes valuable information) or perform "offline" imputation, where they guess the missing values before training the model.

The authors identify a major flaw in the offline approach: the imputation process is disconnected from the prediction task. You might choose an imputation method that looks good statistically but actually introduces noise that hurts your specific classifier. Furthermore, the standard pipeline involves four distinct, cumbersome steps: imputing training data, training the model, imputing test data, and finally predicting. This paper proposes a way to collapse these steps into a single, unified process.

Methods

The researchers developed a multi-objective optimization model that searches for the best parameters for both imputation and classification at the same time.

  • The Engine: They use the NSGA-II (Non-dominated Sorting Genetic Algorithm II), an evolutionary algorithm that finds a "Pareto front"—a set of optimal solutions representing the best trade-offs between two competing goals.
  • Imputation: They utilize Fuzzy Clustering. Instead of assigning a point to one cluster, it assigns "degrees of membership." The model optimizes cluster centers and the "fuzziness" parameter to fill in missing values.
  • Classification: They use Support Vector Machines (SVM). The algorithm tunes the SVM’s flexibility ($C$) and kernel parameters (like $\gamma$ or polynomial degree) simultaneously with the imputation parameters.
  • Objective Functions: The model tries to satisfy two goals:
  • Maximize Imputation Quality: The authors tested three different formulations: Cluster Validity (Average Silhouette Width), Correlation (maximizing the link between train and test sets), and Variance Ratio.
  • Minimize Classification Error: Measured via 10-fold cross-validation on the training set.

Datasets

The model was evaluated using three classic benchmarks from the UCI repository:

  • Iris: Small, numerical, 3 classes.
  • Zoo: Small, mostly categorical, 7 classes.
  • Sonar: Larger, 60 numerical features, 2 classes.

To stress-test the model, the authors generated 30 different scenarios for each dataset, varying the missingness ratio (from 1% to 50%) and the missingness pattern (simple, medium, or complex).

Key Insights and Ideas

  • The "Online" Advantage: By optimizing imputation for the classifier, the model ensures that the filled-in values are those most helpful for making accurate predictions.
  • Pareto Efficiency: There isn't just one "right" answer. The model provides a range of solutions. A researcher can choose a solution that prioritizes highly reliable imputation or one that pushes for maximum classification accuracy.
  • Consistency Across Metrics: Interestingly, all three proposed imputation objective functions (ASW, Correlation, and Variance Ratio) performed similarly well. This suggests the framework is robust to how "good imputation" is mathematically defined.
  • Medical Relevance: The authors highlight that in fields like cancer research, every single patient record is precious and expensive. This method allows researchers to keep every record, even if it's partially incomplete, without sacrificing the integrity of the machine learning model.

Key Results

  • Minimal Accuracy Loss: Even with significant missing data, the classification error on the imputed test data was only about 3% higher than if the data had been perfectly complete.
  • Outperforming the Baseline: When compared to existing literature on Train Subset Selection (TSS), this model achieved lower or equal test errors on the Zoo and Sonar datasets, despite the fact that the comparison models were working with complete data.
  • Robustness: The model's performance remained stable across different types of missingness (Missing at Random vs. Uniformly Distributed), proving it can handle various real-world data failure modes.

Limitations and Future Work

  • Scalability: The authors noted that as the number of records and features increases (as seen with the Sonar dataset), the implementation time grows significantly. The current evolutionary approach might be slow for "Big Data" applications.
  • Algorithm Scope: The study focused specifically on Fuzzy Clustering and SVMs. While effective, the framework hasn't yet been tested with other popular architectures like Random Forests or Deep Neural Networks.
  • Future Directions: The authors suggest extending the model to include feature selection (deciding which variables are even worth keeping) and model pruning as additional objectives in the optimization process.

Summary updated

Abstract

Machine learning techniques have been developed to learn from complete data. When missing values exist in a dataset, the incomplete data should be preprocessed separately by removing data points with missing values or imputation. In this paper, we propose an online approach to handle missing values while a classification model is learnt. To reach this goal, we develop a multi-objective optimization model with two objective functions for imputation and model selection. We also propose three formulations for imputation objective function. We use an evolutionary algorithm based on NSGA II to find the optimal solutions as the Pareto solutions. We investigate the reliability and robustness of the proposed model using experiments by defining several scenarios in dealing with missing values and classification. We also describe how the proposed model can contribute to medical informatics. We compare the performance of three different formulations via experimental results. The proposed model results get validated by comparing with a comparable literature.
BibTeX
@inproceedings{khorshidi2020machine,
  author = {Hadi Akbarzadeh Khorshidi and Michael Kirley and Uwe Aickelin},
  title = {{Machine learning with incomplete datasets using multi-objective optimization models}},
  booktitle = {IJCNN},
  year = {2020},
  url = {https://openreview.net/forum?id=sPMgSxi6Pr},
}

Loading related content...

Figure