Amrita Bhattacherjee¹* and Sugata Sanyal²

¹Department of Statistics, St. Xavier’s College, Kolkata, India
²Professor (Retired), School of Technology and Computer Science, Tata Institute of Fundamental Research, Mumbai, India

*Corresponding Author: Amrita Bhattacherjee, Department of Statistics, St. Xavier’s College, Kolkata, India.

Received: November 30, 2021; Published: January 18, 2022

Abstract

The Fuzzy C-Means clustering technique is one of the most popular soft clustering algorithms in the field of data segmentation. However, its high time complexity makes it computationally expensive, when implemented on very large datasets. Kolen and Hutcheson (2002) [1] proposed a modification of the FCM Algorithm, which dramatically reduces the runtime of their algorithm, making it linear with respect to the number of clusters, as opposed to the original algorithm which was quadratic with respect to the number of clusters. This paper proposes further modification of the algorithm by Kolen., et al. by suggesting effective seed initialisation (by Fuzzy C-Means++, proposed by Stetco., et al. [2]) before feeding the initial cluster centers to the algorithm. The resultant model converges even faster. Empirical findings are illustrated using two synthetic and two real-world datasets.

Keywords: Clustering; Fuzzy Partitions; Time Complexity; Fuzzy C-Means Algorithm; Unsupervised Machine Learning

References

1. Kolen John F and Tim Hutcheson. "Reducing the time complexity of the fuzzy c-means algorithm”. IEEE Transactions on Fuzzy Systems2 (2002): 263-267.
2. Stetco Adrian., et al. "Fuzzy C-means++: Fuzzy C-means with effective seeding initialization”. Expert Systems with Applications21 (2015): 7541-7548.
3. Bezdek James C., et al. "FCM: The fuzzy c-means clustering algorithm”. Computers and Geosciences2-3 (1984): 191-203.
4. Cannon Robert L., et al. "Efficient implementation of the fuzzy c-means clustering algorithms”. IEEE Transactions on Pattern Analysis and Machine Intelligence 2 (1986): 248-255.
5. Tolias Yannis A and Stavros M Panas. "On applying spatial constraints in fuzzy image clustering using a fuzzy rule-based system”. IEEE Signal Processing Letters10 (1998): 245-247.
6. Kamel Mohamed S and Shokri Z Selim. "New algorithms for solving the fuzzy clustering problem”. Pattern Recognition3 (1994): 421-428.
7. Cheng Tai Wai., et al. "Fast fuzzy clustering”. Fuzzy Sets and Systems1 (1998): 49-56.
8. Hore Prodip., et al. "Single pass fuzzy c means”. 2007 IEEE International Fuzzy Systems Conference. IEEE (2007).
9. Hung Ming-Chuan and Don-Lin Yang. "An efficient fuzzy c-means clustering algorithm”. Proceedings 2001 IEEE International Conference on Data Mining. IEEE (2001).
10. Arthur David and Sergei Vassilvitskii. “k-means++: The advantages of careful seeding”. Stanford (2006).
11. Zadeh Lotfi A. "Fuzzy Sets, Information and Control”. MathSciNet zbMATH 8 (1965): 338-353.
12. https://archive.ics.uci.edu/ml/datasets/iris
13. https://archive.ics.uci.edu/ml/datasets/wine

Citation

Citation: Amrita Bhattacherjee and Sugata Sanyal. “Reducing Time Complexity of the Fuzzy C-Means Algorithm: Case Studies". Acta Scientific Computer Sciences 3.2 (2022): 23-33.

Copyright

Copyright: © 2022 Amrita Bhattacherjee and Sugata Sanyal. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.