Robust and Sparse Fuzzy K-Means Clustering

Jinglin Xu, Junwei Han, Kai Xiong, Feiping NieIJCAI 2016

Introduction

Clustering is a cornerstone of unsupervised learning, yet traditional methods like K-Means and Fuzzy C-Means (FCM) often struggle with the imperfections of real-world data. Specifically, these algorithms are highly sensitive to outliers and often produce dense membership matrices where every data point is associated with every cluster. This research, presented at IJCAI-16 by researchers from Northwestern Polytechnical University, introduces Robust and Sparse Fuzzy K-Means (RSFKM), a novel framework designed to address these limitations by integrating robust loss functions with sparsity-inducing regularization.

Problem Statement

Standard partition-based clustering algorithms suffer from two primary drawbacks:

  1. Outlier Sensitivity: The use of squared Euclidean distance means that outliers exert a disproportionate influence on cluster centroids, leading to biased results.
  2. Lack of Sparsity: In FCM, membership degrees are typically non-zero for all clusters. In high-dimensional datasets or those with many categories, this "everything is everywhere" phenomenon obscures the true underlying structure and complicates interpretation.

Methodology

The RSFKM algorithm optimizes a new objective function that balances data fidelity with a penalty for non-sparse memberships.

Robust Loss Functions

To mitigate the impact of noise, the authors replace the standard squared error with robust alternatives:

  • $\ell_{2,1}$-norm: Reduces the influence of outliers by using linear rather than quadratic error scaling.
  • Capped $\ell_1$-norm: Provides an even more resilient approach by capping the error at a threshold $\epsilon$. Points exceeding this threshold are treated as outliers and effectively ignored during centroid calculation.

Sparsity through Regularization

By incorporating a Frobenius norm penalty ($\parallel U \parallel_F^2$) on the membership matrix $U$, the algorithm naturally pushes smaller membership values toward zero. This ensures that each data point is only associated with a small number of relevant clusters.

Comparison of membership values across different clustering algorithms. RSFKM (d) demonstrates superior sparsity compared to FCM (b) and AFKM (c).

Experimental Evaluation

The performance of RSFKM was validated on several benchmark datasets, including the COIL-20 and COIL-100 object image libraries and various subsets of the MNIST handwritten digit database, such as MINIST-2K2K, MINIST-10K, and the full MINIST-ORIG (70,000 samples).

Results and Discussion

RSFKM consistently outperformed baseline methods in terms of Accuracy (ACC) and Normalized Mutual Information (NMI). For instance, on the COIL-20 dataset, RSFKM achieved an accuracy of 67.06%, a marked improvement over K-Means (59.71%) and FCM (63.96%).

Furthermore, the algorithm exhibits excellent convergence properties. Despite the complexity of the robust loss functions, the iterative re-weighted optimization scheme ensures rapid convergence, making the method computationally viable for large-scale applications.

Convergence curves for RSFKM across different datasets, showing the objective function value decreasing over iterations.

Conclusion

RSFKM represents a significant advancement in fuzzy clustering. By combining robust norms to handle outliers and regularization to enforce membership sparsity, it provides a more accurate and interpretable tool for analyzing messy, real-world data. Future research directions include developing automated strategies for parameter selection to enhance the algorithm's "plug-and-play" capabilities for practitioners.

Summary updated

BibTeX
@inproceedings{xu2016robust,
  author = {Jinglin Xu and Junwei Han and Kai Xiong and Feiping Nie},
  title = {{Robust and Sparse Fuzzy K-Means Clustering}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure