A modification of the k-means method for quasi-unsupervised learning

David Rebollo-Monedero, Marc Solé, Jordi Nin, Jordi Forné

Research output: Indexed journal article Articlepeer-review

8 Citations (Scopus)


Since the advent of data clustering, the original formulation of the clustering problem has been enriched to incorporate a number of twists to widen its range of application. In particular, recent heuristic approaches have proposed to incorporate restrictions on the size of the clusters, while striving to minimize a measure of dissimilarity within them. Such size constraints effectively constitute a way to exploit prior knowledge, readily available in many scenarios, which can lead to an improved performance in the clustering obtained. In this paper, we build upon a modification of the celebrated k-means method resorting to a similar alternating optimization procedure, endowed with additive partition weights controlling the size of the partitions formed, adjusted by means of the Levenberg-Marquardt algorithm. We propose several further variations on this modification, in which different kinds of additional information are present. We report experimental results on various standardized datasets, demonstrating that our approaches outperform existing heuristics for size-constrained clustering. The running-time complexity of our proposal is assessed experimentally by means of a power-law regression analysis.

Original languageEnglish
Pages (from-to)176-185
Number of pages10
JournalKnowledge-Based Systems
Publication statusPublished - Jan 2013
Externally publishedYes


  • Clustering
  • Constrained clustering
  • Loyd algorithm
  • Quasi-unsupervised learning
  • Size constraints
  • k-Means method


Dive into the research topics of 'A modification of the k-means method for quasi-unsupervised learning'. Together they form a unique fingerprint.

Cite this