---
_id: '2367'
abstract:
- lang: eng
  text: One of the most popular fuzzy clustering techniques is the fuzzy K-means algorithm
    (also known as fuzzy-c-means or FCM algorithm). In contrast to the K-means and
    K-median problem, the underlying fuzzy K-means problem has not been studied from
    a theoretical point of view. In particular, there are no algorithms with approximation
    guarantees similar to the famous K-means++ algorithm known for the fuzzy K-means
    problem. This work initiates the study of the fuzzy K-means problem from an algorithmic
    and complexity theoretic perspective. We show that optimal solutions for the fuzzy
    K-means problem cannot, in general, be expressed by radicals over the input points.
    Surprisingly, this already holds for simple inputs in one-dimensional space. Hence,
    one cannot expect to compute optimal solutions exactly. We give the first (1+eps)-approximation
    algorithms for the fuzzy K-means problem. First, we present a deterministic approximation
    algorithm whose runtime is polynomial in N and linear in the dimension D of the
    input set, given that K is constant, i.e. a polynomial time approximation scheme
    (PTAS) for fixed K. We achieve this result by showing that for each soft clustering
    there exists a hard clustering with similar properties. Second, by using techniques
    known from coreset constructions for the K-means problem, we develop a deterministic
    approximation algorithm that runs in time almost linear in N but exponential in
    the dimension D. We complement these results with a randomized algorithm which
    imposes some natural restrictions on the sought solution and whose runtime is
    comparable to some of the most efficient approximation algorithms for K-means,
    i.e. linear in the number of points and the dimension, but exponential in the
    number of clusters.
author:
- first_name: Johannes
  full_name: Blömer, Johannes
  id: '23'
  last_name: Blömer
- first_name: Sascha
  full_name: Brauer, Sascha
  id: '13291'
  last_name: Brauer
- first_name: Kathrin
  full_name: Bujna, Kathrin
  last_name: Bujna
citation:
  ama: 'Blömer J, Brauer S, Bujna K. A Theoretical Analysis of the Fuzzy K-Means Problem.
    In: <i>2016 IEEE 16th International Conference on Data Mining (ICDM)</i>. IEEE;
    2016:805-810. doi:<a href="https://doi.org/10.1109/icdm.2016.0094">10.1109/icdm.2016.0094</a>'
  apa: 'Blömer, J., Brauer, S., &#38; Bujna, K. (2016). A Theoretical Analysis of
    the Fuzzy K-Means Problem. In <i>2016 IEEE 16th International Conference on Data
    Mining (ICDM)</i> (pp. 805–810). Barcelona, Spain: IEEE. <a href="https://doi.org/10.1109/icdm.2016.0094">https://doi.org/10.1109/icdm.2016.0094</a>'
  bibtex: '@inproceedings{Blömer_Brauer_Bujna_2016, title={A Theoretical Analysis
    of the Fuzzy K-Means Problem}, DOI={<a href="https://doi.org/10.1109/icdm.2016.0094">10.1109/icdm.2016.0094</a>},
    booktitle={2016 IEEE 16th International Conference on Data Mining (ICDM)}, publisher={IEEE},
    author={Blömer, Johannes and Brauer, Sascha and Bujna, Kathrin}, year={2016},
    pages={805–810} }'
  chicago: Blömer, Johannes, Sascha Brauer, and Kathrin Bujna. “A Theoretical Analysis
    of the Fuzzy K-Means Problem.” In <i>2016 IEEE 16th International Conference on
    Data Mining (ICDM)</i>, 805–10. IEEE, 2016. <a href="https://doi.org/10.1109/icdm.2016.0094">https://doi.org/10.1109/icdm.2016.0094</a>.
  ieee: J. Blömer, S. Brauer, and K. Bujna, “A Theoretical Analysis of the Fuzzy K-Means
    Problem,” in <i>2016 IEEE 16th International Conference on Data Mining (ICDM)</i>,
    Barcelona, Spain, 2016, pp. 805–810.
  mla: Blömer, Johannes, et al. “A Theoretical Analysis of the Fuzzy K-Means Problem.”
    <i>2016 IEEE 16th International Conference on Data Mining (ICDM)</i>, IEEE, 2016,
    pp. 805–10, doi:<a href="https://doi.org/10.1109/icdm.2016.0094">10.1109/icdm.2016.0094</a>.
  short: 'J. Blömer, S. Brauer, K. Bujna, in: 2016 IEEE 16th International Conference
    on Data Mining (ICDM), IEEE, 2016, pp. 805–810.'
conference:
  end_date: 2016-12-15
  location: Barcelona, Spain
  name: IEEE 16th International Conference on Data Mining (ICDM)
  start_date: 2016-12-12
date_created: 2018-04-17T11:46:07Z
date_updated: 2022-01-06T06:55:58Z
department:
- _id: '64'
doi: 10.1109/icdm.2016.0094
keyword:
- unsolvability by radicals
- clustering
- fuzzy k-means
- probabilistic method
- approximation algorithms
- randomized algorithms
language:
- iso: eng
page: 805-810
publication: 2016 IEEE 16th International Conference on Data Mining (ICDM)
publication_identifier:
  isbn:
  - '9781509054732'
publication_status: published
publisher: IEEE
status: public
title: A Theoretical Analysis of the Fuzzy K-Means Problem
type: conference
user_id: '25078'
year: '2016'
...