Similarity-Driven Cluster Merging Method for Unsupervised Fuzzy Clustering

Xuejian Xiong, Kap Luk ChanUAI 2004

TL;DR

This paper introduces a novel "similarity-driven cluster merging" (GFC-SD) method for unsupervised fuzzy clustering. It addresses the challenge of automatically determining the optimal number of clusters by starting with an over-specified number and adaptively merging similar clusters based on a new similarity criterion, leading to more robust and efficient clustering.

What Problem Does This Paper Address?

Unsupervised fuzzy clustering algorithms, while powerful for data analysis, face several challenges. A significant one is "cluster validation," specifically determining the optimal number of clusters ($c$) in a dataset. Traditional methods often involve repeatedly running the clustering algorithm for a range of $c$ values and evaluating a global validity measure, which is computationally expensive and may not always yield accurate results. Furthermore, existing cluster merging methods are often tied to specific clustering procedures, limiting their general applicability. This paper aims to provide a more efficient and robust approach to cluster validation by proposing a dynamic, yet static-validation-like, cluster merging strategy that can be integrated with fuzzy clustering algorithms.

Methods

The core of the proposed method is the Similarity-Driven Cluster Merging Criterion. This criterion is based on a fuzzy cluster similarity matrix (FR), which quantifies the similarity between any two clusters $P_i$ and $P_j$. The similarity is calculated using the fuzzy dispersion of each cluster ($dp_i$, $dp_j$) and the distance between their prototypes ($dv_{ij}$). Specifically, $FR_{ij} = \frac{dp_i + dp_j}{dv_{ij}}$.

The merging process starts with an over-specified number of clusters ($c_{max}$). Pairs of clusters with an $FR_{ij}$ value below a certain threshold ($T$) are considered "completely separated." If $FR_{ij}$ is above $T$, the clusters are merged. The paper suggests an adaptive threshold mechanism, with initial values $T_1=1$ and $T_2=2$, allowing for a more nuanced merging decision.

Additionally, the paper proposes a Modified Generalized Objective Function for fuzzy clustering. This function incorporates a p-norm distance measure and principal components of clusters. The principal components, determined automatically using the Minimum Description Length (MDL) criterion, help to emphasize the directions of maximum data scatter within a cluster, potentially improving convergence speed and robustness, especially for high-dimensional data.

Datasets

The paper evaluates the proposed GFC-SD algorithm on three datasets:

  • Artificial Data Set with Uneven-Distributed Groups: This dataset is synthetically generated from normal distributions with varying densities (one group much larger than others) to test robustness to uneven cluster densities.
  • IRIS Data Set: A standard benchmark dataset from the UCI Machine Learning Repository, used to evaluate the algorithm's ability to correctly identify known cluster structures.
  • Gene Expression Data Set (Serum Data): A real-world dataset consisting of gene expression levels from 517 genes across 13 experiments, used to assess performance on high-dimensional data and its ability to find biologically relevant clusters.

Key Insights and Ideas

  • Adaptive Cluster Merging: The similarity-driven merging criterion, by considering both cluster dispersion and prototype distance, offers a more nuanced way to decide when clusters should be merged compared to simple distance-based methods.
  • Robustness to Initialization: The GFC-SD algorithm demonstrates significantly less sensitivity to random initialization compared to traditional FCM, leading to more consistent and reliable results.
  • Automatic Feature Selection: The incorporation of principal components into the objective function acts as a form of automatic feature selection, potentially improving efficiency and performance, especially in high-dimensional spaces.
  • Computational Efficiency: By merging clusters iteratively rather than re-running the entire clustering process for each potential $c$, the GFC-SD algorithm significantly reduces computational load.

Key Results

  • Artificial Data: GFC-SD correctly identified the four underlying clusters in the unevenly distributed artificial dataset, outperforming FCM-Xie, which incorrectly detected only two clusters.
  • IRIS Data: GFC-SD accurately identified the three classes of the IRIS dataset with 93.33% accuracy, whereas FCM-Xie struggled to find the correct number of clusters.
  • Gene Expression Data: For the serum dataset, GFC-SD automatically determined the correct number of 10 gene clusters, aligning with previous biological findings. In contrast, FCM-Xie identified only two clusters.
  • Computational Load: GFC-SD was significantly faster than FCM-Xie for the gene expression data, taking approximately 1.19 x 10^2 seconds compared to 3.10 x 10^3 seconds for FCM-Xie. The paper also notes that GFC-SD's computational load was roughly half that of a conventional FCM-Xie approach for a similar task.

Limitations and Future Work

  • Threshold Selection: While the paper proposes adaptive thresholds ($T_1, T_2$) and suggests fixing $T_1=1$, the optimal choice of these thresholds might still depend on the specific dataset characteristics. The paper mentions that the value of $T$ can affect the final solution and speed.
  • Parameter Tuning: Like most clustering algorithms, GFC-SD still requires setting parameters such as the fuzziness parameter ($m$), the weight for the principal component term ($g$), and the initial range for $r$ ($r_1$).
  • Future Work: The paper implicitly suggests that further exploration of adaptive thresholding strategies and parameter optimization could enhance the algorithm's performance. The integration of this merging method with other clustering paradigms could also be a fruitful area for future research.

Summary updated

BibTeX
@inproceedings{xiong2004similarity,
  author = {Xuejian Xiong and Kap Luk Chan},
  title = {{Similarity-Driven Cluster Merging Method for Unsupervised Fuzzy Clustering}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2004},
}
Figure