Interpretation and optimization of the k-means algorithm.

DOI10.1007/S10492-014-0063-5MaRDI QIDQ464720zbMATH OpenOpenAlexFDO

Authors Rudolf Scitovski, Kristian Sabo

Publication date 29 October 2014

Published in Applications of Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10492-014-0063-5

zbMATH Keywords

\(k\)-meansclusteringVoronoi diagram

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Pattern recognition, speech recognition (68T10)

Review text

The paper proposes a new algorithm called the divided \(k\)-means (DKM), which is developed as a limit case of another recently proposed alternative to \(k\)-means, i.e. smoothed \(k\)-means algorithm (SMOKA). Many illustrative examples are provided along with the theoretical explanations. Experiments demonstrate the higher efficiency of the DKM as opposed to the classical algorithm in the determined locally optimal partitions and its better CPU time than the SMOKA competitor. DKM contrasts to the original \(k\)-means approach only when data points appear in the Voronoi diagram during the iterative progression and results can still be improved.

Recommendations

• \(k\)-means algorithm
• An efficient enhanced \(k\)-means clustering algorithm
• Modified global \(k\)-means algorithm for minimum sum-of-squares clustering problems
• -Means: A new generalized k-means clustering algorithm
• A survey on algorithms for k-means problem and its variants

Cites work

• A generalized Weiszfeld method for the multi-facility location problem
• A modification of the \texttt{DIRECT} method for Lipschitz global optimization for a symmetric function
• A review of recent advances in global optimization
• A toolbox for \(K\)-centroids cluster analysis
• Building initial partitions through sampling techniques
• Data Clustering: Theory, Algorithms, and Applications
• Fast modified global \(k\)-means algorithm for incremental cluster construction
• Firefly Algorithms for Multimodal Optimization
• Global optimization in action. Continuous and Lipschitz optimization: algorithms, implementations and applications
• scientific article; zbMATH DE number 5957421 (Why is no real title available?)
• scientific article; zbMATH DE number 3852234 (Why is no real title available?)
• scientific article; zbMATH DE number 852532 (Why is no real title available?)
• scientific article; zbMATH DE number 1424293 (Why is no real title available?)
• Introduction to clustering large and high-dimensional data.
• Lipschitzian optimization without the Lipschitz constant
• Modified global \(k\)-means algorithm for minimum sum-of-squares clustering problems
• On fuzzy cluster validity indices
• One-dimensional center-based l 1-clustering method

Cited in

(8)

• A combination of \(k\)-means and \texttt{DBSCAN} algorithm for solving the multiple generalized circle detection problem
• The adaptation of the \(k\)-means algorithm to solving the multiple ellipses detection problem by using an initial approximation obtained by the DIRECT global optimization algorithm.
• Two-level \(k\)-means clustering algorithm for \(k\)-\(\tau \) relationship establishment and linear-time classification
• Improved \(k'\)-means algorithms and applications in image segmentation
• \(k\)-means algorithm
• scientific article; zbMATH DE number 7071628 (Why is no real title available?)
• A method for searching for a globally optimal \(k\)-partition of higher-dimensional datasets
• Optimising \(k\)-means clustering results with standard software packages

Describes a project that uses

Uses Software

• DIRECT
• LGO
• flexclust
• SymDIRECT

This page was built for publication: Interpretation and optimization of the \(k\)-means algorithm.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q464720)