Exact Linear-Time Algorithm for Parameterized K-Means Problem with Optimized Number of Clusters in the 1D Case

Alexander Kel’manov, Vladimir Khandeev

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Abstract

We consider a well-known strongly NP-hard K-Means problem. In this problem, one needs to partition a finite set of N points in Euclidean space into K non-empty clusters minimizing the sum over all clusters of the intracluster sums of the squared distances between the elements of each cluster and its centers. The cluster’s center is defined as the centroid (geometrical center). We analyze the polynomial-solvable one-dimensional case of the problem and propose a novel parameterized approach to this case. Within the framework of this approach, we, firstly, introduce a new parameterized formulation of the problem for this case and, secondly, we show that our approach and proposed algorithm allows one to find an optimal input data partition and, contrary to existing approaches and algorithms, simultaneously find an optimal clusters number in (formula presented) time.

Original languageEnglish
Title of host publicationNumerical Computations
Subtitle of host publicationTheory and Algorithms - 3rd International Conference, NUMTA 2019, Revised Selected Papers
EditorsYaroslav D. Sergeyev, Dmitri E. Kvasov
PublisherSpringer Gabler
Pages394-399
Number of pages6
ISBN (Print)9783030406158
DOIs
Publication statusPublished - 1 Jan 2020
Event3rd Triennial International Conference and Summer School on Numerical Computations: Theory and Algorithms, NUMTA 2019 - Crotone, Italy
Duration: 15 Jun 201921 Jun 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11974 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference3rd Triennial International Conference and Summer School on Numerical Computations: Theory and Algorithms, NUMTA 2019
CountryItaly
CityCrotone
Period15.06.201921.06.2019

Keywords

  • K-Means
  • Linear-time algorithm
  • One-dimensional case
  • Parameterized approach

OECD FOS+WOS

  • 1.02 COMPUTER AND INFORMATION SCIENCES
  • 1.01 MATHEMATICS

Fingerprint

Dive into the research topics of 'Exact Linear-Time Algorithm for Parameterized K-Means Problem with Optimized Number of Clusters in the 1D Case'. Together they form a unique fingerprint.

Cite this