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 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. Proposes variational Wasserstein barycenters for geometric clustering.
problem Geometric clustering problems, especially K-means and co-clustering.
method Solves for Monge maps using variational principle, explores connections to K-means and co-clustering.
result Demonstrates feasibility and use of variational Wasserstein barycenters in clustering.
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.
A new framework improves fairness in clustering and Wasserstein Barycenter problems.
problem Fair clustering in datasets with multiple groups.
method Relax and Merge framework for (1+4ρ+O(ε))-approximate solutions. result Improved approximation guarantees for fairness constraints.
K-means clustering improved for robustness to outliers and distribution shifts.
problem K-means is brittle to outliers, distribution shifts, and limited samples.
method Developed a distributionally robust variant using Wasserstein-2 ball around the empirical distribution.
result Substantial gains in outlier detection and robustness to noise demonstrated.
Paper proposes a new algorithm for clustering financial market regimes.
problem Rapid and automated detection of distinct market regimes.
method Wasserstein k-means algorithm for clustering financial time-series.
result Wasserstein k-means algorithm outperforms traditional clustering methods.
We propose a novel framework for graph mean computation.
problem Defining a mean for graph data is difficult.
method Embeddings in the space of smooth graph signal distributions, using the Wasserstein metric.
result Existence and uniqueness of the graph mean established, and an iterative algorithm provided.
New theory for clustering in geometric and adaptive settings.
problem Clustering in non-Euclidean spaces and adaptive parameters.
method Asymptotic theory for k-means and related methods. result Strong consistency and asymptotic limit theorems for various clustering procedures.
FWC creates fair synthetic samples for machine learning tasks.
problem Addressing biases in machine learning models for fair decision-making.
method FWC uses an efficient majority minimization algorithm to minimize Wasserstein distance while enforcing demographic parity.
result FWC achieves a competitive fairness-utility tradeoff and reduces biases in predictions from large language models.
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$\$.
This study improves graph coarsening methods by preserving graph spectrum and distances.
problem Solving large-scale graph problems by working on a smaller graph.
method Developed a geometric approach using Gromov--Wasserstein distance to minimize the difference between graph distances and their coarsened versions.
result Minimizing the difference between graph distances and their coarsened versions can be achieved using the weighted kernel K-means method. 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 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.
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 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,…
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…