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…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,932 papers · 148 categories
Trend · papers per month
48 results for “k-means objective”
Finding the optimal -means clustering is NP-hard in general and many heuristics have been designed for minimizing monotonically the -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…
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.
An Objective for Hierarchical Clustering in Euclidean Space and its Connection to Bisecting K-meanscs.LG
Paper develops a new objective for hierarchical clustering in Euclidean space.
problem Hierarchical clustering in Euclidean space with dissimilarity scores.
method Develops a new global objective and connects it to bisecting k-means.
result Optimal 2-means solution approximates the new objective, proving bisecting k-means optimizes a natural global objective.
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.
Lloyd's K-means is shown to be a Frank-Wolfe algorithm variant.
problem Optimizing the sum of squared errors in clustering.
method Established a connection between Lloyd's K-means and Frank-Wolfe algorithm, derived convergence rates, and developed FW variants for empty clusters.
result Lloyd's K-means is a special case of the Frank-Wolfe algorithm with a non-asymptotic convergence rate of O(1/t).
New locally private algorithm for k-means clustering reduces additive error significantly.
problem Designing a locally private algorithm for k-means clustering with reduced additive error.
method Local differential privacy approach, reducing additive error to nearly .
result Achieves multiplicative error and additive error, nearly optimal.
We study in this paper the problem of jointly clustering and learning representations. As several previous studies have shown, learning representations that are both faithful to the data to be clustered and adapted to the clustering algorithm can lead to better clustering performance, all the more so that the two tasks…
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.
We show that the objective function of conventional k-means clustering can be expressed as the Frobenius norm of the difference of a data matrix and a low rank approximation of that data matrix. In short, we show that k-means clustering is a matrix factorization problem. These notes are meant as a reference and intende…
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…
A new algorithm balances fairness in clustering to avoid discrimination.
problem Clustering data can unfairly discriminate against different demographic groups.
method Designing a stochastic alternating balance fair k-means algorithm (SAfairKM) that alternates between k-means updates and group swap updates.
result The algorithm efficiently constructs well-spread and high-quality Pareto fronts on synthetic and real datasets.
Efficient algorithms for -means clustering frequently converge to suboptimal partitions, and given a partition, it is difficult to detect -means optimality. In this paper, we develop an a posteriori certifier of approximate optimality for -means clustering. The certifier is a sub-linear Monte Carlo algorithm b…
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.
We show that -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 -means and GMMs, the provided derivation shows that it is not required to consider Gau…
Following widely used in visual recognition concept of relative attributes, the article establishes definition of the relative PCA attributes for a class of objects defined by vectors of their parameters. A new rating model (RELARM) is built using relative PCA attribute ranking functions for rating object description a…
Fuzzy clustering with similarity queries improves efficiency and accuracy.
problem Clustering uncertain or vague datasets.
method Semi-supervised active clustering framework with oracle similarity queries.
result Polynomial-time approximation algorithm for fuzzy clustering with few similarity queries.
Generative Adversarial Networks (GANs) have achieved great success in generating realistic images. Most of these are conditional models, although acquisition of class labels is expensive and time-consuming in practice. To reduce the dependence on labeled data, we propose an un-conditional generative adversarial model, …
A new Wasserstein -means method for clustering probability distributions.
problem Clustering probability distributions using the Wasserstein metric.
method Distance-based -means with SDP relaxation for Wasserstein barycenters.
result Distance-based -means outperforms centroid-based -means for clustering probability distributions.
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…
Robust Trimmed k-meansstat.ML
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.
Ant colony optimization for clustering with improved K-means.
problem Clustering a set of objects to minimize intra-variance.
method Constructive approach using ant-like solutions with visibility and pheromone trails, improved with K-means.
result Encouraging results in nearly all benchmark real-data sets.
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.
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…
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.
New clustering method using point-set kernel measures similarity.
problem Measuring similarity between objects for clustering.
method Point-set kernel for similarity computation; clustering procedure uses this measure.
result Proposed method is more effective and faster than existing algorithms.
In the context of recent deep clustering studies, discriminative models dominate the literature and report the most competitive performances. These models learn a deep discriminative neural network classifier in which the labels are latent. Typically, they use multinomial logistic regression posteriors and parameter re…
Bayesian models offer great flexibility for clustering applications---Bayesian nonparametrics can be used for modeling infinite mixtures, and hierarchical Bayesian models can be utilized for sharing clusters across multiple data sets. For the most part, such flexibility is lacking in classical clustering methods such a…
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.
Can clustering scale sublinearly with its clusters? A variational EM acceleration of GMMs and -meansstat.ML
One iteration of standard -means (i.e., Lloyd's algorithm) or standard EM for Gaussian mixture models (GMMs) scales linearly with the number of clusters , data points , and data dimensionality . In this study, we explore whether one iteration of -means or EM for GMMs can scale sublinearly with at run…
A new clustering algorithm REFCMFS improves K-Means efficiency and robustness.
problem Efficiently clustering data with outliers and -norm constraints.
method REFCMFS uses -norm robust loss and -norm constraint on membership matrix.
result REFCMFS achieves more promising performance and efficient optimization.
This paper describes a method for clustering data that are spread out over large regions and which dimensions are on different scales of measurement. Such an algorithm was developed to implement a robotics application consisting in sorting and storing objects in an unsupervised way. The toy dataset used to validate suc…
To cluster data that are not linearly separable in the original feature space, -means clustering was extended to the kernel version. However, the performance of kernel -means clustering largely depends on the choice of kernel function. To mitigate this problem, multiple kernel learning has been introduced into th…
Online clustering algorithm with regret bound.
problem Online -means clustering with squared distance objective.
method Multiplicative Weights Update Algorithm (MWUA) with discretized grid and online-to-offline reduction.
result Achieves a regret bound of in expectation.
EKM addresses imbalanced data clustering by repelling centroids in large clusters.
problem Imbalanced data leads to biased clustering of large clusters.
method EKM introduces a novel centroid repulsion mechanism based on the Boltzmann operator.
result EKM outperforms benchmark algorithms on imbalanced data.
In many physical, statistical, biological and other investigations it is desirable to approximate a system of points by objects of lower dimension and/or complexity. For this purpose, Karl Pearson invented principal component analysis in 1901 and found 'lines and planes of closest fit to system of points'. The famous k…
In this paper, we propose an implicit gradient descent algorithm for the classic -means problem. The implicit gradient step or backward Euler is solved via stochastic fixed-point iteration, in which we randomly sample a mini-batch gradient in every iteration. It is the average of the fixed-point trajectory that is c…
Overlapping clustering problem is an important learning issue in which clusters are not mutually exclusive and each object may belongs simultaneously to several clusters. This paper presents a kernel based method that produces overlapping clusters on a high feature space using mercer kernel techniques to improve separa…
Proportional centroid clustering aims to fairly group points without prior protected subsets.
problem Fairly group points without prior protected subsets.
method Define fairness as proportionality, present algorithms for efficient computation and optimization.
result Proportional solutions trade off with the k-means objective.
Paper accelerates K-means clustering for large sparse document data.
problem Efficiently clustering large-scale sparse document data.
method Designs an AFM algorithm leveraging UCs and inverted-index structure.
result Significantly improves clustering speed for large-scale documents.
We introduce an evolutionary algorithm called recombinator--means for optimizing the highly non-convex kmeans problem. Its defining feature is that its crossover step involves all the members of the current generation, stochastically recombining them with a repurposed variant of the -means++ seeding algorithm. Th…
This work refines grid size selection for non-interactive private -means clustering.
problem Choosing the optimal number of grids for privatized -means clustering.
method Proposes a refined grid-size selection rule to minimize expected deviation in the K-means objective function.
result The proposed strategy results in more accurate clustering compared to prior work, even under tight privacy budgets.
A new fuzzy k-means algorithm for high-dimensional data with variable feature weights.
problem Clustering high-dimensional data with varying feature significance.
method Proposes a modified fuzzy k-means algorithm using two entropy terms to weight features.
result Improved clustering performance on various datasets compared to state-of-the-art methods.
SIVF k-means algorithm speeds up sparse data clustering.
problem Efficiently clustering large-scale high-dimensional sparse data.
method Inverted-file structure for centroids, filter-based similarity reduction.
result SIVF achieves higher speed and lower memory consumption.
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++.
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.
This paper provides new algorithms for distributed clustering for two popular center-based objectives, k-median and k-means. These algorithms have provable guarantees and improve communication complexity over existing approaches. Following a classic approach in clustering by \cite{har2004coresets}, we reduce the proble…
We consider -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 -means, or -means, which relies only on l…