Modified K-means Algorithm with Local Optimality Guarantees
The K-means algorithm is one of the most widely studied clustering algorithms in machine learning. While extensive research has focused on its ability to achieve a globally optimal solution, there still lacks a rigorous analysis of its local optimality guarantees. In this paper, we first present conditions under which the K-means algorithm converges to a locally optimal solution. Based on this, we propose simple modifications to the K-means algorithm which ensure local optimality in both the continuous and discrete sense, with the same computational complexity as the original K-means algorithm. As the dissimilarity measure, we consider a general Bregman divergence, which is an extension of the squared Euclidean distance often used in the K-means algorithm. Numerical experiments confirm that the K-means algorithm does not always find a locally optimal solution in practice, while our proposed methods provide improved locally optimal solutions with reduced clustering loss. Our code is available at https://github.com/lmingyi/LO-K-means.
Code (1)
Tasks
ClusteringSimilar Papers 제목 키워드 기반
Statistically Optimal K-means Clustering via Nonnegative Low-rank Semidefinite Programming
$K$-means clustering is a widely used machine learning method for identifying patterns in large datasets. Recently, semidefinite programming (SDP) relaxations have been proposed for solving the $K$-means optimization pro…
ClusteringScalable Second-order Riemannian Optimization for $K$-means Clustering
Clustering is a hard discrete optimization problem. Nonconvex approaches such as low-rank semidefinite programming (SDP) have recently demonstrated promising statistical and local algorithmic guarantees for cluster recov…
Distribution free optimality intervals for clustering
We address the problem of validating the ouput of clustering algorithms. Given data $\mathcal{D}$ and a partition $\mathcal{C}$ of these data into $K$ clusters, when can we say that the clusters obtained are correct or m…
ClusteringOn the optimality of kernels for high-dimensional clustering
This paper studies the optimality of kernel methods in high-dimensional data clustering. Recent works have studied the large sample performance of kernel clustering in the high-dimensional regime, where Euclidean distanc…
ClusteringVocal Bursts Intensity PredictionMultiscale Hybrid Non-local Means Filtering Using Modified Similarity Measure
A new multiscale implementation of non-local means filtering for image denoising is proposed. The proposed algorithm also introduces a modification of similarity measure for patch comparison. The standard Euclidean norm …
DenoisingImage Denoising