Experiments with a non-convex variance-based clustering criterion

Rodrigo F. Toso, Evgeny V. Bauman, Casimir A. Kulikowski, Ilya B. Muchnik

Research output: Chapter in Book/Report/Conference proceedingChapter


This paper investigates the effectiveness of a variance-based clustering criterion whose construct is similar to the popular minimum sum-of-squares or k-means criterion, except for two distinguishing characteristics: its ability to discriminate clusters by means of quadratic boundaries and its functional form, for which convexity does not hold. Using a recently proposed iterative local search heuristic that is suitable for general variance-based criteria—convex or not, the first to our knowledge that offers such broad support—the alternative criterion has performed remarkably well. In our experimental results, it is shown to be better suited for the majority of the heterogeneous real-world data sets selected. In conclusion, we offer strong reasons to believe that this criterion can be used by practitioners as an alternative to k-means clustering.

Original languageEnglish (US)
Title of host publicationSpringer Optimization and Its Applications
PublisherSpringer International Publishing
Number of pages12
StatePublished - 2014

Publication series

NameSpringer Optimization and Its Applications
ISSN (Print)1931-6828
ISSN (Electronic)1931-6836

All Science Journal Classification (ASJC) codes

  • Control and Optimization


  • Clustering
  • Iterative local search
  • Variance-based discriminants


Dive into the research topics of 'Experiments with a non-convex variance-based clustering criterion'. Together they form a unique fingerprint.

Cite this