research-article

A Complexity Theoretical Study of Fuzzy K-Means

Authors:

Johannes Blömer,

Kathrin BujnaAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 16, Issue 4

Article No.: 53, Pages 1 - 25

https://doi.org/10.1145/3409385

Published: 16 September 2020 Publication History

Abstract

The fuzzy K-means problem is a popular generalization of the well-known K-means problem to soft clusterings. In this article, we present the first algorithmic study of the problem going beyond heuristics. Our main result is that, assuming a constant number of clusters, there is a polynomial time approximation scheme for the fuzzy K-means problem. As a part of our analysis, we also prove the existence of small coresets for fuzzy K-means. At the heart of our proofs are two novel techniques developed to analyze the otherwise notoriously difficult fuzzy K-means objective function.

References

[1]

A. Aggarwal, A. Deshpande, and R. Kannan. 2009. Adaptive sampling for k-means clustering. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Science, Vol. 5687. Springer, 15--28.

Digital Library

[2]

P. Awasthi, M. Charikar, R. Krishnaswamy, and A. K. Sinop. 2015. The hardness of approximation of Euclidean k-means. In Proceedings of the 31st International Symposium on Computational Geometry (SoCG’15). 754–767.

[3]

C. Bajaj. 1988. The algebraic degree of geometric optimization problems. Discrete 8 Computational Geometry 3, 2 (Jan. 1988), 177--191.

[4]

J. C. Bezdek, R. Ehrlich, and W. Full. 1984. FCM: The fuzzy -means clustering algorithm. Computers 8 Geosciences 10, 2 (1984), 191--203.

[5]

J. C. Bezdek, R. J. Hathaway, M. J. Sabin, and W. T. Tucker. 1987. Convergence theory for fuzzy c-means: Counterexamples and repairs. IEEE Transactions on Systems, Man and Cybernetics 17, 5 (Sept. 1987), 873--877.

Digital Library

[6]

J. Blömer, S. Brauer, and K. Bujna. 2016. A theoretical analysis of the fuzzy K-means problem. In Proceedings of the 2016 IEEE 16th International Conference on Data Mining (ICDM’16). 805--810.

[7]

J. Blömer, S. Brauer, and K. Bujna. 2018. Coresets for fuzzy -means with applications. In Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC’18).

[8]

J. Blömer, C. Lammersen, M. Schmidt, and C. Sohler. 2016. Theoretical analysis of the k-means algorithm—A survey. In Algorithm Engineering. Springer International, 81--116.

[9]

S. Brauer. 2019. Classification and Approximation of Geometric Location Problems. Ph.D. Dissertation. Paderborn University.

[10]

K. Chen. 2009. On coresets for K-median and K-means clustering in metric and Euclidean spaces and their applications. SIAM Journal on Computing 39, 3 (Jan. 2009), 923--947.

Digital Library

[11]

D. Dembélé and P. Kastner. 2003. Fuzzy C-means method for clustering microarray data. Bioinformatics 19, 8 (May 2003), 973--980.

[12]

J. C. Dunn. 1973. A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters. Journal of Cybernetics 3, 3 (Jan. 1973), 32--57.

[13]

D. Feldman and M. Langberg. 2011. A unified framework for approximating and clustering data. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC’11). ACM, New York, NY, 569--578.

Digital Library

[14]

D. Feldman, F. Matthew, and A. Krause. 2011. Scalable training of mixture models via coresets. In Advances in Neural Information Processing Systems 24, J. Shawe-Taylor, R. S. Zemel, P. L. Bartlett, F. Pereira, and K. Q. Weinberger (Eds.). Curran Associates, Inc., 2142--2150.

Digital Library

[15]

Dan Feldman, Morteza Monemizadeh, and Christian Sohler. 2007. A PTAS for K-means clustering based on weak coresets. In Proceedings of the 23rd Annual Symposium on Computational Geometry (SCG’07). ACM, New York, NY, 11--18.

Digital Library

[16]

D. Feldman, M. Schmidt, and C. Sohler. 2013. Turning big data into tiny data: Constant-size coresets for K-means, PCA and projective clustering. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’13). 1434--1453.

Digital Library

[17]

S. Har-Peled and A. Kushal. 2005. Smaller coresets for K-median and K-means clustering. In Proceedings of the 21st Annual Symposium on Computational Geometry (SCG’05). ACM, New York, NY, 126--134.

Digital Library

[18]

S. Har-Peled and S. Mazumdar. 2003. Coresets for k-means and k-median clustering and their applications. In Proceedings of the 36th Annual ACM Sympososium on Theory of Computing. 291--300.

Digital Library

[19]

R. J. Hathaway and J. C. Bezdek. 1986. Local convergence of the fuzzy c-means algorithms. Pattern Recognition 19, 6 (1986), 477--480.

[20]

R. J. Hathaway and J. C. Bezdek. 1988. Recent convergence results for the fuzzy c-means clustering algorithms. Journal of Classification 5, 2 (Sept. 1988), 237--247.

[21]

D. Haussler. 1992. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Information and Computation 100, 1 (1992), 78--150.

Digital Library

[22]

K. Hirota and W. Pedrycz. 1999. Fuzzy computing for data mining. Proceedings of the IEEE 87, 9 (1999), 1575–1600.

[23]

F. Hoppner and F. Klawonn. 2003. A contribution to convergence theory of fuzzy c-means and derivatives. IEEE Transactions on Fuzzy Systems 11, 5 (Oct. 2003), 682--694.

Digital Library

[24]

M. Inaba, N. Katoh, and H. Imai. 1994. Applications of weighted Voronoi diagrams and randomization to variance-based K-clustering. In Proceedings of the 10th Annual Symposium on Computational Geometry (SoCG’94). ACM, New York, NY, 332--339.

Digital Library

[25]

W. B. Johnson and J. Lindenstrauss. 1984. Extensions of Lipschitz maps into a Hilbert space. Contemporary Mathematics 26 (1984), 189--206.

[26]

T. Kim, J. C. Bezdek, and R. J. Hathaway. 1988. Optimality tests for fixed points of the fuzzy c-means algorithm. Pattern Recognition 21, 6 (1988), 651--663.

Digital Library

[27]

S. Lloyd. 1982. Least squares quantization in PCM. IEEE Transactions on Information Theory 28, 2 (March 1982), 129--137.

Digital Library

[28]

Mario Lucic, Olivier Bachem, and Andreas Krause. 2016. Strong coresets for hard and soft Bregman clustering with applications to exponential family mixtures. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS’16). 1--9.

[29]

M. R. Rezaee, P. M. J. van der Zwet, B. P. F. Lelieveldt, R. J. van der Geest, and J. H. C. Reiber. 2000. A multiresolution image segmentation technique based on pyramidal segmentation and fuzzy clustering. IEEE Transactions on Image Processing 9, 7 (July 2000), 1238--1248.

Digital Library

Cited By

Han JRyan CTong X(2024)Wasserstein gradient flow for optimal probability measure decompositionSSRN Electronic Journal10.2139/ssrn.4831118Online publication date: 2024
https://doi.org/10.2139/ssrn.4831118
Yang BTian YWang JHu XAn S(2022)How to improve urban transportation planning in big data era? A practice in the study of traffic analysis zone delineationTransport Policy10.1016/j.tranpol.2022.08.002127(1-14)Online publication date: Oct-2022
https://doi.org/10.1016/j.tranpol.2022.08.002

Index Terms

A Complexity Theoretical Study of Fuzzy K-Means
1. Theory of computation
  1. Theory and algorithms for application domains
    1. Machine learning theory
      1. Unsupervised learning and clustering

Recommendations

Proficient Normalised Fuzzy K-Means With Initial Centroids Methodology

This article describes how data is relevant and if it can be organized, linked with other data and grouped into a cluster. Clustering is the process of organizing a given set of objects into a set of disjoint groups called clusters. There are a number ...
Clustering of Image Data Set Using K-Means and Fuzzy K-Means Algorithms
CICN '10: Proceedings of the 2010 International Conference on Computational Intelligence and Communication Networks

Clustering or data grouping is a key initial procedure in image processing. In present scenario the size of database of companies has increased dramatically, these databases contain large amount of text, image. They need to mine these huge databases and ...
Effect of cluster size distribution on clustering: a comparative study of k-means and fuzzy c-means clustering
Abstract
Data distribution has a significant impact on clustering results. This study focuses on the effect of cluster size distribution on clustering, namely the uniform effect of k-means and fuzzy c-means (FCM) clustering. We first provide some related ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 16, Issue 4

October 2020

404 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/3407674

Editor:
Aravind Srinivasan
University of Maryland, USA

Issue’s Table of Contents

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 September 2020

Accepted: 01 June 2020

Revised: 01 November 2019

Received: 01 December 2018

Published in TALG Volume 16, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

German Research Foundation (DFG)

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
151
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Han JRyan CTong X(2024)Wasserstein gradient flow for optimal probability measure decompositionSSRN Electronic Journal10.2139/ssrn.4831118Online publication date: 2024
https://doi.org/10.2139/ssrn.4831118
Yang BTian YWang JHu XAn S(2022)How to improve urban transportation planning in big data era? A practice in the study of traffic analysis zone delineationTransport Policy10.1016/j.tranpol.2022.08.002127(1-14)Online publication date: Oct-2022
https://doi.org/10.1016/j.tranpol.2022.08.002

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Figures

Tables

Media

View Issue’s Table of Contents