Model Selection Strategies for Determining the Optimal Number of Overlapping Clusters in Additive Overlapping Partitional Clustering

Julian Rossbroich, Jeffrey Durieux, Tom F. WilderjansJ. Classif 2022 · DOI · OpenReview

Abstract

Determining the optimal number of clusters ($K$) is a fundamental challenge in cluster analysis, particularly in overlapping models where objects can belong to multiple groups. This paper evaluates 13 model selection strategies for the Additive Profile Clustering (ADPROCLUS) model. By introducing a minimal stochastic extension to the deterministic ADPROCLUS framework, we enable the use of likelihood-based information criteria. Through an extensive simulation study, we demonstrate that the Convex Hull (CHull) method, especially when combined with a likelihood-based fit measure, significantly outperforms traditional indices and standard information criteria in identifying the true cluster structure.

Introduction

In many real-world applications, data points do not fit neatly into mutually exclusive categories. For instance, a patient may exhibit symptoms of multiple disorders, or a consumer may belong to several market segments. Overlapping clustering models, such as ADPROCLUS, accommodate this complexity. However, a persistent problem in applying these models is the selection of the optimal number of clusters ($K$). Selecting too few clusters leads to an under-representation of the data structure, while selecting too many results in overfitting noise. While numerous heuristics exist for non-overlapping clustering (e.g., $K$-means), systematic guidelines for overlapping models have been largely absent until now.

Methodology

To address the model selection problem, the authors extended the traditionally deterministic ADPROCLUS model. By assuming that residuals follow a normal distribution, they derived a likelihood function. This stochastic extension allows for the application of information-theoretic measures that were previously unavailable for this model type.

The study evaluated 13 distinct strategies categorized into three groups:

  1. Information Criteria: AIC, BIC, AICc, and the Hannan-Quinn Measure (HQM).
  2. Heuristic and Index Methods: The CHull method (an automated "elbow" detection technique), the Calinski-Harabasz Index, the Dunn Index, the Krzanowski-Lai Index, and Average Silhouette Width.
  3. Cross-Validation: Two novel instability-based cross-validation strategies specifically adapted for the ADPROCLUS framework.

The performance of these strategies was tested using a large-scale simulation study. The researchers generated 840 datasets, varying parameters such as data size ($200 \times 15$ and $400 \times 15$), the true number of clusters (3 or 5), the degree of overlap (0%, 35%, and 75%), noise levels (10%, 40%, and 70% of total variance), and overlap complexity.

Results and Key Insights

The simulation results revealed clear performance differences among the strategies. The CHull method using Negative Log-Likelihood (NLL) emerged as the superior strategy, achieving an overall accuracy of 63.8% for overlapping data and 75.8% for non-overlapping data. The least-squares version, CHull LSQ, followed closely with 60.3% accuracy.

In contrast, standard information criteria performed poorly. BIC, in particular, showed an abysmal accuracy of 11.3%, consistently underestimating the number of clusters. AIC performed better at 48.2% but still lagged behind the CHull methods. Traditional indices like Silhouette Width and Calinski-Harabasz, which are common in $K$-means applications, were found to be largely ineffective in the overlapping context.

A critical finding was the impact of the "complexity penalty." Standard criteria like AIC and BIC treat every binary membership assignment as a full parameter, leading to an over-penalization of model complexity. Post-hoc analysis suggested that weighting model complexity by a factor of approximately 0.625 would significantly improve AIC's performance, indicating that binary memberships should not be treated as equivalent to real-valued parameters in terms of complexity.

Discussion and Conclusion

The study highlights that noise is a significant barrier to accurate model selection; at 70% noise levels, nearly all strategies failed to recover the true cluster count. For practitioners, the CHull NLL method is recommended as the most robust tool for navigating the trade-off between model fit and complexity in ADPROCLUS.

Future research should focus on refining the theoretical definition of "model complexity" for overlapping structures and improving the computational scalability of ADPROCLUS, as fitting multiple models for selection remains computationally intensive (taking up to 30 hours for moderate datasets).

Summary updated

Abstract

In various scientific fields, researchers make use of partitioning methods (e.g., K-means) to disclose the structural mechanisms underlying object by variable data. In some instances, however, a grouping of objects into clusters that are allowed to overlap (i.e., assigning objects to multiple clusters) might lead to a better representation of the underlying clustering structure. To obtain an overlapping object clustering from object by variable data, Mirkin’s ADditive PROfile CLUStering (ADPROCLUS) model may be used. A major challenge when performing ADPROCLUS is to determine the optimal number of overlapping clusters underlying the data, which pertains to a model selection problem. Up to now, however, this problem has not been systematically investigated and almost no guidelines can be found in the literature regarding appropriate model selection strategies for ADPROCLUS. Therefore, in this paper, several existing model selection strategies for K-means (a.o., CHull, the Caliński-Harabasz, Krzanowski-Lai, Average Silhouette Width and Dunn Index and information-theoretic measures like AIC and BIC) and two cross-validation based strategies are tailored towards an ADPROCLUS context and are compared to each other in an extensive simulation study. The results demonstrate that CHull outperforms all other model selection strategies and this especially when the negative log-likelihood, which is associated with a minimal stochastic extension of ADPROCLUS, is used as (mis)fit measure. The analysis of a post hoc AIC-based model selection strategy revealed that better performance may be obtained when a different—more appropriate—definition of model complexity for ADPROCLUS is used.
BibTeX
@article{rossbroich2022model,
  author = {Julian Rossbroich and Jeffrey Durieux and Tom F. Wilderjans},
  title = {{Model Selection Strategies for Determining the Optimal Number of Overlapping Clusters in Additive Overlapping Partitional Clustering}},
  journal = {J. Classif.},
  year = {2022},
  doi = {10.1007/s00357-021-09409-1},
}
Figure