Standard

Exact Linear-Time Algorithm for Parameterized K-Means Problem with Optimized Number of Clusters in the 1D Case. / Kel’manov, Alexander; Khandeev, Vladimir.

Numerical Computations: Theory and Algorithms - 3rd International Conference, NUMTA 2019, Revised Selected Papers. ed. / Yaroslav D. Sergeyev; Dmitri E. Kvasov. Springer Gabler, 2020. p. 394-399 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11974 LNCS).

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

Harvard

Kel’manov, A & Khandeev, V 2020, Exact Linear-Time Algorithm for Parameterized K-Means Problem with Optimized Number of Clusters in the 1D Case. in YD Sergeyev & DE Kvasov (eds), Numerical Computations: Theory and Algorithms - 3rd International Conference, NUMTA 2019, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11974 LNCS, Springer Gabler, pp. 394-399, 3rd Triennial International Conference and Summer School on Numerical Computations: Theory and Algorithms, NUMTA 2019, Crotone, Italy, 15.06.2019. https://doi.org/10.1007/978-3-030-40616-5_35

APA

Kel’manov, A., & Khandeev, V. (2020). Exact Linear-Time Algorithm for Parameterized K-Means Problem with Optimized Number of Clusters in the 1D Case. In Y. D. Sergeyev, & D. E. Kvasov (Eds.), Numerical Computations: Theory and Algorithms - 3rd International Conference, NUMTA 2019, Revised Selected Papers (pp. 394-399). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11974 LNCS). Springer Gabler. https://doi.org/10.1007/978-3-030-40616-5_35

Vancouver

Kel’manov A, Khandeev V. Exact Linear-Time Algorithm for Parameterized K-Means Problem with Optimized Number of Clusters in the 1D Case. In Sergeyev YD, Kvasov DE, editors, Numerical Computations: Theory and Algorithms - 3rd International Conference, NUMTA 2019, Revised Selected Papers. Springer Gabler. 2020. p. 394-399. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-40616-5_35

Author

Kel’manov, Alexander ; Khandeev, Vladimir. / Exact Linear-Time Algorithm for Parameterized K-Means Problem with Optimized Number of Clusters in the 1D Case. Numerical Computations: Theory and Algorithms - 3rd International Conference, NUMTA 2019, Revised Selected Papers. editor / Yaroslav D. Sergeyev ; Dmitri E. Kvasov. Springer Gabler, 2020. pp. 394-399 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{2136e25b2b2c4917a76bf425d67324b9,
title = "Exact Linear-Time Algorithm for Parameterized K-Means Problem with Optimized Number of Clusters in the 1D Case",
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{\textquoteright}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.",
keywords = "K-Means, Linear-time algorithm, One-dimensional case, Parameterized approach",
author = "Alexander Kel{\textquoteright}manov and Vladimir Khandeev",
note = "Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; 3rd Triennial International Conference and Summer School on Numerical Computations: Theory and Algorithms, NUMTA 2019 ; Conference date: 15-06-2019 Through 21-06-2019",
year = "2020",
month = jan,
day = "1",
doi = "10.1007/978-3-030-40616-5_35",
language = "English",
isbn = "9783030406158",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Gabler",
pages = "394--399",
editor = "Sergeyev, {Yaroslav D.} and Kvasov, {Dmitri E.}",
booktitle = "Numerical Computations",
address = "Germany",

}

RIS

TY - GEN

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

AU - Kel’manov, Alexander

AU - Khandeev, Vladimir

N1 - Publisher Copyright: © 2020, Springer Nature Switzerland AG. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020/1/1

Y1 - 2020/1/1

N2 - 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.

AB - 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.

KW - K-Means

KW - Linear-time algorithm

KW - One-dimensional case

KW - Parameterized approach

UR - http://www.scopus.com/inward/record.url?scp=85080871796&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-40616-5_35

DO - 10.1007/978-3-030-40616-5_35

M3 - Conference contribution

AN - SCOPUS:85080871796

SN - 9783030406158

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 394

EP - 399

BT - Numerical Computations

A2 - Sergeyev, Yaroslav D.

A2 - Kvasov, Dmitri E.

PB - Springer Gabler

T2 - 3rd Triennial International Conference and Summer School on Numerical Computations: Theory and Algorithms, NUMTA 2019

Y2 - 15 June 2019 through 21 June 2019

ER -

ID: 23740861