Acta Scientific Computer Sciences

Research Article Volume 3 Issue 2

Reducing Time Complexity of the Fuzzy C-Means Algorithm: Case Studies

Amrita Bhattacherjee1* and Sugata Sanyal2

1Department of Statistics, St. Xavier’s College, Kolkata, India
2Professor (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.




Metrics

Acceptance rate35%
Acceptance to publication20-30 days

Indexed In




News and Events


  • Certification for Review
    Acta Scientific certifies the Editors/reviewers for their review done towards the assigned articles of the respective journals.
  • Submission Timeline for Upcoming Issue
    The last date for submission of articles for regular Issues is February 15, 2023.
  • Publication Certificate
    Authors will be issued a "Publication Certificate" as a mark of appreciation for publishing their work.
  • Best Article of the Issue
    The Editors will elect one Best Article after each issue release. The authors of this article will be provided with a certificate of “Best Article of the Issue”.
  • Welcoming Article Submission
    Acta Scientific delightfully welcomes active researchers for submission of articles towards the upcoming issue of respective journals.
  • Contact US