Multi-objective Semi-supervised clustering for finding predictive clusters

Zahra Ghasemi, Hadi Akbarzadeh Khorshidi, Uwe AickelinExpert Systems with Applications 2022 · OpenReview

Abstract

This study introduces a semi-supervised clustering framework designed to identify clusters that are both spatially compact and highly predictive of a continuous outcome variable. By formulating clustering as a multi-objective optimization problem, the researchers utilize the Non-dominated Sorting Genetic Algorithm II (NSGA-II) alongside local regression to minimize both cluster deviation and prediction error. Evaluation across five real-world datasets demonstrates that this approach significantly outperforms traditional single-objective clustering methods in predictive accuracy.

The Challenge of Predictive Clustering

Traditional clustering is typically an unsupervised task, grouping data points based solely on feature similarity. While effective for finding natural structures, these groupings often fail to align with specific target variables, such as predicting housing prices or patient survival times. Standard semi-supervised methods often rely on discrete labels or constraints, leaving a gap for methods that can leverage continuous outcome variables to guide the clustering process.

This research addresses the question: How can we partition data so that observations in each cluster are similar to each other while simultaneously maximizing the accuracy of outcome predictions within those clusters?

Methodology: Multi-objective Optimization and Local Regression

The authors frame this challenge as a multi-objective optimization problem with two competing goals:

  1. Minimize Deviation: Ensuring clusters are compact (using a k-medians cost function).
  2. Minimize Prediction Error: Ensuring clusters are informative (using Mean Absolute Error).

To navigate the trade-off between these objectives, the model employs the Non-dominated Sorting Genetic Algorithm II (NSGA-II) to identify a Pareto front of optimal solutions. A key innovation in this approach is the use of Local Regression (LR). Instead of treating a cluster label as a simple categorical predictor, the model fits a unique multiple linear regression equation to each cluster. This allows the algorithm to capture distinct functional relationships between features and outcomes within different data subgroups.

The mapping process from a genetic chromosome (genotype) to a directed graph and finally to distinct data clusters.

Key Insights: Functional vs. Spatial Similarity

A core finding of this study is the distinction between spatial similarity and functional similarity. Two data points may be close in feature space (spatial similarity) but belong to different "functional" groups where the relationship between features and the outcome variable differs significantly.

A 3D visualization showing how a single spatial cluster (B) can be split into two functional sub-clusters (B1 and B2) based on different regression planes for the outcome variable (Z).

By incorporating prediction error into the clustering phase, the model can identify these hidden functional subtypes. For example, as shown in Figure 1, a seemingly uniform group can be split into subgroups (B1 and B2) that follow different predictive trends, a nuance that unsupervised methods would overlook.

Performance and Results

The researchers evaluated eight model configurations across five UCI datasets, including Boston Housing and Airfoil Self-Noise. The key results include:

  • Superiority of Local Regression: Fitting regression models within clusters (LR) proved far more effective than using clusters as simple categorical predictors (CP).
  • Multi-objective Advantage: The multi-objective approach consistently outperformed single-objective models. On the Airfoil dataset, the multi-objective model achieved a Mean Absolute Error (MAE) of 6.24, compared to 14.02 for the clustering-only version.
  • Optimal Configuration: "Model 3," which utilized Random Selection of Observations (RSO) for initialization and Crossover/Mutation for updates, emerged as the most robust performer.

Conclusion

This multi-objective approach successfully bridges the gap between clustering and regression. By identifying clusters that are functionally similar, the method provides a powerful tool for discovering meaningful subgroups in complex datasets. Future work will focus on enhancing the model's robustness against data uncertainty and exploring non-linear local models within clusters to capture even more complex relationships.

Summary updated

Abstract

Highlights•Finding dense clusters which are informative toward the outcome variable.•Finding optimal solutions using evolutionary algorithms.•Comparison of singe-objective and multi-objective optimization methods.
BibTeX
@article{ghasemi2022multi,
  author = {Zahra Ghasemi and Hadi Akbarzadeh Khorshidi and Uwe Aickelin},
  title = {{Multi-objective Semi-supervised clustering for finding predictive clusters}},
  journal = {Expert Systems with Applications},
  year = {2022},
  url = {https://openreview.net/forum?id=S8xc50HfTC},
}
Figure