Resampling for Fuzzy Clustering

Christian BorgeltInt. J. Uncertain. Fuzziness Knowl. Based Syst 2007 · DOI

TL;DR

This paper explores how to automatically determine the optimal number of clusters in fuzzy clustering by measuring the stability of clustering results across different subsamples of the data. It finds that the Hubert index, when combined with specific t-norms, is a robust and effective measure for this task, offering a reliable way to select the "best" number of clusters.

What Problem Does This Paper Address?

A fundamental challenge in prototype-based clustering algorithms, including fuzzy c-means, is that they require the number of clusters to be specified in advance. While various evaluation measures exist to help select the best number of clusters after running the algorithm multiple times with different cluster counts, these measures can be sensitive to the specific algorithm and data. This paper addresses the need for a more robust and generalizable method for determining the optimal number of clusters, particularly for fuzzy clustering, by leveraging the concept of resampling. The core idea is that if the "true" number of clusters is used, clustering results should be consistent across different subsets of the data. Conversely, a "wrong" number of clusters should lead to unstable and varying results, which can be quantified.

Methods

The paper proposes adapting resampling techniques, commonly used in crisp clustering, to fuzzy and probabilistic clustering. The core method involves:

  • Subsampling: Creating multiple smaller datasets by drawing samples without replacement from the original dataset.
  • Clustering: Running the fuzzy clustering algorithm (e.g., fuzzy c-means) on both the full dataset and each subsample, using the same number of clusters for each run.
  • Comparison: Comparing the resulting cluster partitions from the full dataset and each subsample using various similarity measures.
  • Stability Assessment: Averaging the similarity scores across all subsamples to obtain a "stability measure" for a given number of clusters. The number of clusters yielding the highest stability is considered optimal.

The paper also delves into the nuances of comparing fuzzy partitions by:

  • Generalizing Measures: Adapting measures originally designed for crisp partitions (like accuracy and F1-score) to fuzzy membership degrees by using t-norms (e.g., min, product, Lukasiewicz) to combine fuzzy statements.
  • Introducing New Measures: Proposing a simple mean squared difference comparison for partition matrices.
  • Comparing Coincidence Matrices: Extending the comparison of coincidence matrices (cluster connectivity matrices) using various statistics and t-norms.

Datasets

The experiments were conducted on five datasets:

  • Three artificial 2D datasets with 400 data points each, featuring 3, 4, and 6 spherical clusters (equally or differently populated).
  • One artificial 3D dataset with 400 data points and 5 equally populated ellipsoidal clusters.
  • The well-known wine dataset from the UCI machine learning repository, using attributes 7, 10, and 13.

Key Insights and Ideas

  • Resampling is transferable: The core idea of using resampling to assess clustering stability is shown to be effective for fuzzy clustering, not just crisp clustering.
  • T-norm choice matters: The selection of t-norms for combining fuzzy membership degrees and coincidence matrix entries significantly impacts the performance of the similarity measures. Not all combinations work well.
  • Hubert Index shines: The Hubert index, particularly when parameterized with the nil-potent minimum or Łukasiewicz t-norm for membership degrees, emerges as a robust and reliable measure for determining the optimal number of clusters.
  • Simplicity can be effective: The newly introduced mean squared difference comparison for partition matrices also performs reliably and is a strong contender due to its simplicity.
  • Data characteristics influence results: The paper notes that measures can struggle with certain data characteristics, such as ellipsoidal cluster shapes, potentially leading to alternative interpretations of the optimal cluster number.

Key Results

The paper presents extensive experimental results in Tables 3 and 4, summarizing the performance of various measures and t-norm combinations across different datasets. The findings indicate:

  • The Hubert index, with specific t-norm combinations (nil-potent minimum or Łukasiewicz for membership degrees), consistently achieves high grades (5-6) for finding the correct cluster number across most datasets.
  • The mean squared difference measure also performs well, often achieving grades of 4-5.
  • Other measures, like accuracy and F1-score, show more variability in their performance depending on the t-norm used and the dataset.
  • The wine dataset results suggest that for certain data structures, the algorithm might identify a higher number of clusters than the inherent classes, possibly due to ellipsoidal cluster shapes.

Limitations and Future Work

  • T-norm interaction complexity: The paper highlights that combining t-norms for different parts of the comparison (membership degrees vs. coincidence matrices) is not straightforward, and some combinations do not yield good results. Further exploration of these interactions could be beneficial.
  • Measure selection is crucial: The authors emphasize that careful selection of the relative cluster evaluation measure and its parameterization (t-norms) is critical for the success of the resampling approach in fuzzy clustering.
  • Future work: While the paper demonstrates the applicability of resampling, further research could explore a wider range of resampling strategies (e.g., bootstrapping) and more advanced similarity measures to further enhance robustness and accuracy. The paper also implicitly suggests that understanding how cluster shape influences the choice of measures is an area for continued investigation.

Summary updated

BibTeX
@article{borgelt2007resampling,
  author = {Christian Borgelt},
  title = {{Resampling for Fuzzy Clustering}},
  journal = {Int. J. Uncertain. Fuzziness Knowl. Based Syst.},
  year = {2007},
  doi = {10.1142/s0218488507004893},
}
Figure