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.
Kernel k-Means algorithm improves clustering of non-linear data.
problem Non-convexity of kernel k-Means objective function leads to local minima.
method Generalizes MM approach to solve non-convex problem in kernel and multi-kernel settings.
result Establishes strong consistency guarantees for Kernel Power k-Means.
Kernel-based K-means clustering has gained popularity due to its simplicity and the power of its implicit non-linear representation of the data. A dominant concern is the memory requirement since memory scales as the square of the number of data points. We provide a new analysis of a class of approximate kernel methods…
A fast algorithm for K-means clustering using subsampled SDP.
problem Efficiently solving large-scale K-means clustering problems. method Sketch-and-Lift (SL) approach for approximating SDP relaxed K-means. result SL method achieves similar exact recovery threshold as full SDP on full dataset.
New k-means method handles random data better than traditional techniques.
problem Limitations of traditional clustering methods in random data.
method Probabilistic metric space with random normed k-means (RNKM).
result RNKM outperforms traditional methods in complex clustering scenarios.
sWk-means clusters multidimensional financial time series into distinct market regimes.
problem Classifying distinct market regimes in multidimensional financial time series.
method Approximated multidimensional Wasserstein distance as sliced Wasserstein distance for clustering.
result sWk-means successfully identifies distinct market regimes in real financial data.
Paper studies kernel hyperparameters for clustering, proposing an efficient search method.
problem Challenges in tuning kernel parameters for clustering, especially for RBF kernels.
method Derives a lower bound for RBF kernel parameters, proposes an efficient hyperparameter search algorithm.
result Proposes an efficient algorithm for hyperparameter search in kernel clustering, improving upon grid search.
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++.
Estimates statistical power for cluster analysis in biomedical research.
problem Lack of established methods to compute a priori statistical power for cluster analysis.
method Simulation studies varying subgroup size, number, separation, and covariance structure.
result Sufficient statistical power achieved with small samples (N=20-30) for large effect sizes.
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$\$.
New clustering method for exponential family data.
problem Improving clustering for non-Gaussian data.
method Bregman Power k-Means algorithm.
result Outperforms existing methods in non-Gaussian data settings.
It has always been a great challenge for clustering algorithms to automatically determine the cluster numbers according to the distribution of datasets. Several approaches have been proposed to address this issue, including the recent promising work which incorporate Bayesian Nonparametrics into the k-means clusterin…
In addition to finding meaningful clusters, centroid-based clustering algorithms such as K-means or mean-shift should ideally find centroids that are valid patterns in the input space, representative of data in their cluster. This is challenging with data having a nonconvex or manifold structure, as with images or text…
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. 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.
UNTIE learns representations of coupled categorical data.
problem Challenges in learning from unlabeled categorical data with complex couplings.
method UNTIE approach for unsupervised representation learning of heterogeneous couplings.
result UNTIE significantly improves categorical data representations on 25 diverse datasets.
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…
We consider K-means clustering in networked environments (e.g., internet of things (IoT) and sensor networks) where data is inherently distributed across nodes and processing power at each node may be limited. We consider a clustering algorithm referred to as networked K-means, or NK-means, which relies only on l…
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.