A new k k k -means method improves clustering accuracy and robustness.
problem Insufficient asymptotic properties in existing k k k -means methods. method Introducing clustering consistency and proposing a new k k k -means method. result The new k k k -means method has lower clustering error rates and is more robust. 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.
Deep k-means learns clustering and features from unlabeled data.
problem Clustering and feature learning from unlabeled data.
method Gradient-estimator for non-differentiable k-means objective via Gumbel-Softmax reparameterisation.
result Concrete k-means model optimised for canonical k-means objective, end-to-end trainable.
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.
New *K-means method finds cancer signatures without NMF.
problem Identifying cancer signatures from genome data.
method Applying *K-means clustering to 1,389 cancer samples.
result 3 cancers lack cluster-like structures, 2 have high correlations.
The study investigates the consistency of k k k -means clustering under finite expectation assumptions.
problem Consistency of k k k -means clustering under finite expectation assumptions. method Investigates the conditions under which k k 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.
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.
Augmented k-means improves clustering accuracy and efficiency.
problem Identifying homogeneous clusters in heterogeneous datasets.
method Hybrid of k-means and logistic regression, using cluster probabilities to refine cluster means.
result Augmented k-means outperforms standard k-means in accuracy and convergence speed.
DISCERN estimates K for K-Means clustering efficiently.
problem Estimating the number of clusters in data.
method A deterministic initialization method for K-Means++.
result Improves both K estimation and clustering performance.
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.
Improved kernel k-means clustering for large datasets with reduced computational cost.
problem High computational cost of kernel k-means clustering for large datasets.
method Applying linear k-means clustering to a subset of features constructed using rank-restricted Nyström approximation.
result Achieves a 1+ε approximation ratio for kernel k-means cost function.
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.
initKmix generates better initial partitions for k-means clustering of mixed datasets.
problem Random initial partitions lead to inconsistent clustering results.
method initKmix runs k-means multiple times, using different attributes to create initial clusters, then combines results.
result initKmix produces more accurate and consistent clustering results.
A new Wasserstein K K K -means method for clustering probability distributions.
problem Clustering probability distributions using the Wasserstein metric.
method Distance-based K K K -means with SDP relaxation for Wasserstein barycenters. result Distance-based K K K -means outperforms centroid-based K K K -means for clustering probability distributions. 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.
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.
A new clustering method for non-linear data on manifolds using diffusion distances.
problem Clustering non-linear data on manifolds with non-Euclidean geometry.
method Diffusion K K K -means clustering on manifolds with polynomial-time convex relaxations via SDP. result Exact recovery of SDPs for diffusion K K K -means under suitable geometric conditions. Study reduces dimensions for k k k -means clustering for better accuracy.
problem Improving accuracy of k k k -means clustering with high-dimensional data. method Four randomized algorithms: two feature selection and two feature extraction.
result Provably accurate approximations of k k k -means clustering are obtained. 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++.
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…
Proposes Lasso Weighted k-means for sparse clustering of high-dimensional data.
problem Sparse clustering of high-dimensional data with variable feature weights.
method Introduces a lasso-based penalty term on feature weights for sparse clustering without distributional assumptions.
result Establishes strong consistency of the algorithm and competitive performance on real and synthetic datasets.
Selective inference controls Type I error in k-means clustering tests.
problem Inflated Type I error in classical hypothesis tests for k-means clusters.
method Selective inference approach to control Type I error.
result Proposes a computable finite-sample p-value for selective inference.
Hybrid clustering merges K K K -means and hierarchical methods for diverse group shapes.
problem Clustering homogeneous spherical groups in large datasets.
method First, K K K -means partitions the dataset into spherical groups. Then, hierarchical clustering merges these groups with a data-driven distance measure. result Hybrid approach reveals general-shaped groups in datasets.
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.
A novel clustering method using a subset of data for better performance.
problem Improving clustering efficiency with limited data.
method Proposes a sampling subset approach for variance-based k-clustering.
result The method achieves competitive results with only 7% of the dataset, outperforming existing methods in 80% of tasks.
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.
Finding the optimal k k k -means clustering is NP-hard in general and many heuristics have been designed for minimizing monotonically the k k 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…
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.
A novel k-means method for MNAR data improves clustering accuracy.
problem Improving k-means clustering for data missing not at random.
method A magnitude-decaying MNAR scenario-based k-means method with size constraints.
result The method reduces bias in estimated cluster centers and improves clustering accuracy.
Paper certifies k-means clustering optimality efficiently.
problem Detecting k k k -means optimality in suboptimal partitions. method Sub-linear Monte Carlo algorithm based on semidefinite relaxation.
result 3-approximation certificate with 99% confidence for mixtures of Gaussians.
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.
New K-indicators model outperforms K-means for large K in big data.
problem Scalability bottleneck of K-means with large number of clusters.
method Developed K-indicators model and an efficient algorithm.
result New algorithm significantly outperforms K-means with large K.
A new t t t - k k k -means algorithm improves clustering stability and robustness.
problem Poor performance and instability of standard k k k -means on heavy-tailed data. method Proposes t t t - k k k -means, a robust and stable variant of k k k -means. result Demonstrates improved stability and robustness on datasets with outliers.
New method jointly clusters and learns representations for better performance.
problem Jointly clustering and learning representations for improved clustering performance.
method Continuous reparametrization of k k k -Means objective function. result Jointly clustering and learning representations leads to better performance.
New insights into spurious local minima in k-means clustering.
problem Understanding and mitigating spurious local minima in k-means clustering.
method Investigating spurious local minima under a probabilistic generative model.
result Proven structures of spurious local minima for k-means clustering.
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.
The paper analyzes k k k -means clustering for missing data, proving statistical guarantees under MCAR.
problem Statistical guarantees for k k k -means clustering with missing data, especially under Missing Completely at Random (MCAR). method Established n \sqrt{n} n -excess risk bound and consistency of cluster centers under general missing mechanisms; derived n \sqrt{n} n -convergence rate and asymptotic normality for MCAR. result Achieving n \sqrt{n} n -rate and converging to true cluster centers requires distinct true cluster centers in every dimension under MCAR. 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.
Proposes a method to select diverse kernels for improved clustering performance.
problem Redundancy in selected kernels degrades clustering performance and efficiency.
method Selects diverse subset of kernels as representative kernels, optimizes combination coefficients using alternating minimization.
result Improves clustering performance and efficiency compared to existing methods.
Robust Trimmed k-means improves clustering with outliers and mixed data.
problem Real-world data often contains outliers and mixed membership clusters, complicating traditional clustering methods.
method Proposes Robust Trimmed k-means (RTKM) that robustifies k-means for both single- and multi-membership data.
result RTKM outperforms other methods on multi-membership data with outliers and single membership data with outliers.
Many clustering algorithms exist that estimate a cluster centroid, such as K-means, K-medoids or mean-shift, but no algorithm seems to exist that clusters data by returning exactly K meaningful modes. We propose a natural definition of a K-modes objective function by combining the notions of density and cluster assignm…
New k k k -means method clusters radar image sequences using SPD matrices.
problem Clustering radar image sequences efficiently.
method Developed k k k -means on SPD matrices for non-Euclidean data. result Effective clustering of radar image sequences via SPD matrices.
K-Means clustering improved with sophisticated initialisation techniques.
problem K-Means algorithm's sensitivity to initial centroid positions and local minima.
method Comparison of deterministic and stochastic initialisation techniques for K-Means variations.
result Deterministic methods outperform stochastic methods in clustering quality.
A new k-means algorithm using cover trees accelerates clustering.
problem Efficiently clustering large datasets with k-means.
method Combining cover trees with upper and lower bounds.
result Significantly reduces distance computations and improves clustering performance.
PNN-smoothing improves k k k -means clustering by merging subsets' clusterings.
problem Improving k k k -means clustering initialization efficiency and effectiveness. method Split dataset into subsets, cluster each subset, merge with PNN method.
result PNN-smoothing enhances k k k -means++ seeding, reducing costs. Kernel clustering algorithm improved for large datasets using incomplete Cholesky factorization.
problem Large memory usage in kernel-based clustering for large-scale datasets.
method Approximate the kernel matrix using incomplete Cholesky factorization and apply linear k k k -means clustering. result The proposed method achieves similar performance to kernel k k k -means clustering but handles large-scale datasets efficiently. Solves K-Means clustering's need for known cluster count.
problem Determining the number of clusters for K-Means without prior knowledge.
method Uses hypersphere density to estimate clusters, visualizing density vs. number of clusters.
result Identifies the optimal number of clusters in datasets.
Paper presents a novel k-means clustering method using two distance measures for Gaussian data.
problem Improving clustering accuracy and robustness for Gaussian data.
method Integrates within cluster distance (WCD) and inter cluster distance (ICD) into k-means clustering.
result The algorithm provides more accurate clustering and better handles outliers.