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

Alexander Kel’manov, Vladimir Khandeev

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

Аннотация

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.

Язык оригиналаанглийский
Название основной публикацииNumerical Computations
Подзаголовок основной публикацииTheory and Algorithms - 3rd International Conference, NUMTA 2019, Revised Selected Papers
РедакторыYaroslav D. Sergeyev, Dmitri E. Kvasov
ИздательSpringer Gabler
Страницы394-399
Число страниц6
ISBN (печатное издание)9783030406158
DOI
СостояниеОпубликовано - 1 янв 2020
Событие3rd Triennial International Conference and Summer School on Numerical Computations: Theory and Algorithms, NUMTA 2019 - Crotone, Италия
Продолжительность: 15 июн 201921 июн 2019

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том11974 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция3rd Triennial International Conference and Summer School on Numerical Computations: Theory and Algorithms, NUMTA 2019
СтранаИталия
ГородCrotone
Период15.06.201921.06.2019

Fingerprint Подробные сведения о темах исследования «Exact Linear-Time Algorithm for Parameterized K-Means Problem with Optimized Number of Clusters in the 1D Case». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать