A new K-means method HT K-means uses ℓ0 penalty for sparsity.
problem Cluster center regularization for improved clustering performance.
method HT K-means with ℓ0 penalty for sparsity. result HT K-means outperforms other regularized K-means methods in simulations and real data. Paper finds methods to accurately determine the number of clusters in data.
problem Finding the correct number of clusters in a dataset.
method Penalized k-means algorithms with ideal clusters and multiplicative penalties.
result K-means with multiplicative penalties provides a clearer indication of the correct number of clusters.
We propose the Lasso Weighted k-means (LW-k-means) algorithm as a simple yet efficient sparse clustering procedure for high-dimensional data where the number of features (p) can be much larger compared to the number of observations (n). In the LW-k-means algorithm, we introduce a lasso-based penalty term,…
Proposes ARSK for robust and sparse clustering.
problem Outliers and high-dimensional noisy variables in K-means clustering.
method Introduces redundant error component and group sparse penalty for robustness, and weights and sparsity control penalty for noisy variables.
result Superior performance in identifying clusters without outliers and informative variables.
A framework estimates multiple precision matrices with shared structures.
problem Estimating multiple precision matrices with shared structures.
method Penalized likelihood framework with iterative algorithm alternating between convex and clustering problems.
result The method outperforms competitors and performs similarly to methods using prior information.
The classical mixture of Gaussians model is related to K-means via small-variance asymptotics: as the covariances of the Gaussians tend to zero, the negative log-likelihood of the mixture of Gaussians model approaches the K-means objective, and the EM algorithm approaches the K-means algorithm. Kulis & Jordan (2012) us…
The non-negative matrix factorization (NMF) model with an additional orthogonality constraint on one of the factor matrices, called the orthogonal NMF (ONMF), has been found a promising clustering model and can outperform the classical K-means. However, solving the ONMF model is a challenging optimization problem becau…
Breathing k-means outperforms greedy k-means++ in clustering.
problem Improving k-means clustering solutions.
method Dynamic adjustment of centroids through breathing technique.
result Breathing k-means outperforms other k-means techniques, especially greedy k-means++.
Improved K-Means++ and K-Means∥ with faster run-time.
problem Efficiently selecting initial seeds for K-means clustering.
method Triangle inequality pruning and dynamic priority queue.
result Up to 17x speedup for K-Means++ and 551x for K-Means$\$.
Paper identifies sparse structures and communities in heterogeneous graphical models.
problem Detecting community structures in graphical models.
method Novel decomposition into sparse and low-rank parts, three-stage estimation procedure.
result Consistent model selection for adaptive ℓ1 penalized estimator. Modified K-means ensures local optimality with same complexity.
problem Lack of rigorous analysis on local optimality guarantees of K-means.
method Proposed modifications to K-means ensuring local optimality.
result Proposed methods provide improved locally optimal solutions.
k-means algorithm is one of the most classical clustering methods, which has been widely and successfully used in signal processing. However, due to the thin-tailed property of the Gaussian distribution, k-means algorithm suffers from relatively poor performance on the dataset containing heavy-tailed data or outlie…
Clustering is a separation of data into groups of similar objects. Every group called cluster consists of objects that are similar to one another and dissimilar to objects of other groups. In this paper, the K-Means algorithm is implemented by three distance functions and to identify the optimal distance function for c…
Paper improves clustering risk bounds for kernel k-means.
problem Improving clustering risk bounds for kernel k-means.
method Analyzes kernel k-means and Nyström approximation.
result Achieves nearly optimal excess clustering risk bound.
Ball k-means reduces point-centroid distance computations for faster k-means clustering.
problem Efficiently finding k-means clusters in large datasets.
method Uses a ball to describe clusters, dividing them into stable and active areas, and adjusting points within annulus areas.
result Significantly reduces point-centroid distance computations, making k-means faster and more efficient.
New method speeds up k-means clustering using sketch-and-solve.
problem Efficiently solving k-means clustering for large datasets.
method Sketch-and-solve approach with Peng-Wei semidefinite relaxation.
result Provides high-confidence lower bounds on k-means optimal value.
A new k-means variant minimizes pairwise distances within clusters.
problem The need for improved clustering methods.
method A stochastic optimization procedure that minimizes the k-sums target function.
result The new k-sums method outperforms k-means and its variants.
TS-K-means improves financial data clustering with dynamic time warping.
problem Inadequate handling of temporal dependencies in financial time series data.
method Integrates Dynamic Time Warping into Time Series K-means for financial data.
result TS-K-means outperforms traditional K-means in financial data analysis.
Paper proposes a novel unsupervised feature selection method using K-means and ADMM.
problem Finding a subset of features for high-dimensional unsupervised learning problems.
method Developed K-means Derived Unsupervised Feature Selection (K-means UFS) using ADMM to solve NP-hard optimization.
result K-means UFS outperforms baselines in feature selection for clustering.
A faster Wasserstein k-means algorithm for histogram data reduces computation and maintains clustering quality.
problem Efficiently clustering histogram data with reduced computation time.
method Sparse simplex projection to reduce data samples, centroids, and ground cost matrix, dynamically removing lower-valued samples.
result Significant reduction in computational complexity without compromising clustering quality.
A new k-means method improves clustering accuracy and robustness.
problem Insufficient asymptotic properties in existing k-means methods. method Introducing clustering consistency and proposing a new k-means method. result The new k-means method has lower clustering error rates and is more robust. We show that k-means (Lloyd's algorithm) is obtained as a special case when truncated variational EM approximations are applied to Gaussian Mixture Models (GMM) with isotropic Gaussians. In contrast to the standard way to relate k-means and GMMs, the provided derivation shows that it is not required to consider Gau…
Two algorithms improve K-means clustering speed without sacrificing quality.
problem Improving clustering quality of K-means while speeding up the process.
method Divisive K-means and Parallel Two-Phase K-means.
result Achieved empirically global optimum clustering results with lower complexity.
We address the problem of simultaneously learning a k-means clustering and deep feature representation from unlabelled data, which is of interest due to the potential of deep k-means to outperform traditional two-step feature extraction and shallow-clustering strategies. We achieve this by developing a gradient-estimat…
The study investigates the consistency of k-means clustering under finite expectation assumptions.
problem Consistency of k-means clustering under finite expectation assumptions. method Investigates the conditions under which k-means clustering is consistent, considering finite expectation instead of finite variance. result Inconsistency can arise due to extreme cluster imbalance, leading to some clusters having few points.
The paper assesses conditions for the uniqueness of k-means clustering.
problem Conditions for the uniqueness of k-means clustering.
method Analyzes the choice of k and provides necessary and sufficient conditions for uniqueness.
result Determines the asymptotic distribution of the within cluster sum of squares (WCSS) and provides a bootstrap test for uniqueness.
Finding the optimal k-means clustering is NP-hard in general and many heuristics have been designed for minimizing monotonically the k-means objective. We first show how to extend Lloyd's batched relocation heuristic and Hartigan's single-point relocation heuristic to take into account empty-cluster and single-poin…
Data-target association is an important step in multi-target localization for the intelligent operation of un- manned systems in numerous applications such as search and rescue, traffic management and surveillance. The objective of this paper is to present an innovative data association learning approach named multi-la…
K-Means and RBF networks are shown to be equivalent under certain conditions.
problem Discrete clustering vs. continuous optimization in machine learning.
method Established variational and gradient-based equivalence between K-Means and RBF networks.
result Gradient-based updates of RBF centers recover K-Means centroid update rule.
Study reduces dimensions for k-means clustering for better accuracy.
problem Improving accuracy of k-means clustering with high-dimensional data. method Four randomized algorithms: two feature selection and two feature extraction.
result Provably accurate approximations of k-means clustering are obtained. Efficient algorithms for k-means clustering frequently converge to suboptimal partitions, and given a partition, it is difficult to detect k-means optimality. In this paper, we develop an a posteriori certifier of approximate optimality for k-means clustering. The certifier is a sub-linear Monte Carlo algorithm b…
Transform learning improves K-means clustering for document analysis.
problem Improving K-means clustering for document analysis.
method Embedding K-means clustering loss into transform learning framework and solving jointly using ADMM.
result Improves over state-of-the-art in document clustering.
Fair k-means algorithm ensures equitable costs for different groups.
problem K-means clustering can result in biased outcomes for subgroups of data.
method Presented a fair k-means objective and algorithm (Fair-Lloyd) to choose cluster centers that provide equitable costs for different groups.
result Fair-Lloyd algorithm ensures all groups have equal costs in the output k-clustering, with negligible increase in running time.
One of the applications of center-based clustering algorithms such as K-Means is partitioning data points into K clusters. In some examples, the feature space relates to the underlying problem we are trying to solve, and sometimes we can obtain a suitable feature space. Nevertheless, while K-Means is one of the most ef…
The paper improves marine buoy placement to detect ships robustly against disruptions.
problem Detecting fishing vessels in the presence of natural and man-made disruptions.
method Formulated as a clustering problem, used dropout k-means and k-median to improve buoy placement robustness.
result Improved ship detection probability with dropout k-means compared to classic methods.
A new Wasserstein K-means method for clustering probability distributions.
problem Clustering probability distributions using the Wasserstein metric.
method Distance-based K-means with SDP relaxation for Wasserstein barycenters. result Distance-based K-means outperforms centroid-based K-means for clustering probability distributions. K-means fails in high dimensions with noise and few samples.
problem Clustering in high-dimensional data with noise and limited samples.
method Simple Gaussian Mixture Model (GMM) analysis.
result Almost every partition becomes a fixed point of k-means in high dimensions.
Entropy regularization improves power k-means for high-dimensional data.
problem Power k-means' tendency to get stuck in local minima and performance in high dimensions.
method Entropy regularization to learn feature relevance, combined with majorization-minimization algorithm.
result Consistent learning and scalable algorithm with closed-form updates and convergence guarantees.
K-means fails catastrophically in high dimensions, Hartigan's avoids it.
problem K-means algorithm's failure in high-dimensional data.
method Proof of k-means failure and Hartigan's algorithm success.
result Hartigan's algorithm avoids the catastrophic failure of k-means in high dimensions.
We present *K-means clustering algorithm and source code by expanding statistical clustering methods applied in https://ssrn.com/abstract=2802753 to quantitative finance. *K-means is statistically deterministic without specifying initial centers, etc. We apply *K-means to extracting cancer signatures from genome data w…
Two new scalable K-means initialization methods proposed for large-scale clustering.
problem Efficient initialization for large-scale clustering problems.
method Divide-and-conquer approach and random projection method for multiple lower-dimensional subspaces.
result The proposed methods outperform state-of-the-art in large-scale clustering tasks.
Identifying a set of homogeneous clusters in a heterogeneous dataset is one of the most important classes of problems in statistical modeling. In the realm of unsupervised partitional clustering, k-means is a very important algorithm for this. In this technical report, we develop a new k-means variant called Augmented …
Proposes PKM for soft K-means clustering.
problem Soft K-means (m=1) unsolved since 1981.
method Probabilistic K-Means (PKM) via nonlinear programming.
result Proposed methods solve PKM efficiently.
We study the problem of estimating a manifold from random samples. In particular, we consider piecewise constant and piecewise linear estimators induced by k-means and k-flats, and analyze their performance. We extend previous results for k-means in two separate directions. First, we provide new results for k-means rec…
This paper proposes the use of an optimization algorithm, namely PSO to decide the initial centroids in K-means, to eventually get better accuracy. The vectorized notation of the optimal centroids can be thought of as entities in an optimization space, where the accuracy of K-means over a random subset of the data coul…
Traditionally, practitioners initialize the {\tt k-means} algorithm with centers chosen uniformly at random. Randomized initialization with uneven weights ({\tt k-means++}) has recently been used to improve the performance over this strategy in cost and run-time. We consider the k-means problem with semi-supervised inf…
Adapts manifold structure for better clustering performance.
problem Lack of consideration for local manifold structure in existing multiple kernel k-means methods.
method Adopts manifold adaptive kernel to integrate local manifold structure of kernels.
result Proposed method outperforms state-of-the-art methods.
Study explores K-means clustering of variables and its relation to PCA.
problem Exploring the relationship between K-means clustering of variables and PCA.
method Apply PCA to original data and K-means to transposed data, quantify variable contributions to principal components.
result Identifies how variable clusters contribute to principal components identified by PCA.