Geodesic
Interpretation and optimization of the $k$-means algorithm
Applications of Mathematics, Tome 59 (2014) no. 4, pp. 391-406

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

The paper gives a new interpretation and a possible optimization of the well-known $k$-means algorithm for searching for a locally optimal partition of the set $\mathcal {A}= \{a_i\in \mathbb {R}^n\colon i=1,\dots ,m\}$ which consists of $k$ disjoint nonempty subsets $\pi _1,\dots ,\pi _k$, $1\leq k\leq m$. For this purpose, a new divided $k$-means algorithm was constructed as a limit case of the known smoothed $k$-means algorithm. It is shown that the algorithm constructed in this way coincides with the $k$-means algorithm if during the iterative procedure no data points appear in the Voronoi diagram. If in the partition obtained by applying the divided $k$-means algorithm there are data points lying in the Voronoi diagram, it is shown that the obtained result can be improved further.
DOI : 10.1007/s10492-014-0063-5
Classification : 62H30, 68T10, 90C26, 91C20
Keywords: clustering; data mining; $k$-means; Voronoi diagram 
@article{10_1007_s10492_014_0063_5,
     author = {Sabo, Kristian and Scitovski, Rudolf},
     title = {Interpretation and optimization of the $k$-means algorithm},
     journal = {Applications of Mathematics},
     pages = {391--406},
     publisher = {mathdoc},
     volume = {59},
     number = {4},
     year = {2014},
     doi = {10.1007/s10492-014-0063-5},
     mrnumber = {3233551},
     zbl = {06362235},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10492-014-0063-5/}
}
TY  - JOUR
AU  - Sabo, Kristian
AU  - Scitovski, Rudolf
TI  - Interpretation and optimization of the $k$-means algorithm
JO  - Applications of Mathematics
PY  - 2014
SP  - 391
EP  - 406
VL  - 59
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10492-014-0063-5/
DO  - 10.1007/s10492-014-0063-5
LA  - en
ID  - 10_1007_s10492_014_0063_5
ER  - 
%0 Journal Article
%A Sabo, Kristian
%A Scitovski, Rudolf
%T Interpretation and optimization of the $k$-means algorithm
%J Applications of Mathematics
%D 2014
%P 391-406
%V 59
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1007/s10492-014-0063-5/
%R 10.1007/s10492-014-0063-5
%G en
%F 10_1007_s10492_014_0063_5
Sabo, Kristian; Scitovski, Rudolf. Interpretation and optimization of the $k$-means algorithm. Applications of Mathematics, Tome 59 (2014) no. 4, pp. 391-406. doi: 10.1007/s10492-014-0063-5

Cité par Sources :