Faster Balanced Clusterings in High Dimension

2018-09-04 · Hu Ding

The problem of constrained clustering has attracted significant attention in the past decades. In this paper, we study the balanced $k$-center, $k$-median, and $k$-means clustering problems where the size of each cluster is constrained by the given lower and upper bounds. The problems are motivated by the applications in processing large-scale data in high dimension. Existing methods often need to compute complicated matchings (or min cost flows) to satisfy the balance constraint, and thus suffer from high complexities especially in high dimension. We develop an effective framework for the three balanced clustering problems to address this issue, and our method is based on a novel spatial partition idea in geometry. For the balanced $k$-center clustering, we provide a $4$-approximation algorithm that improves the existing approximation factors; for the balanced $k$-median and $k$-means clusterings, our algorithms yield constant and $(1+\epsilon)$-approximation factors with any $\epsilon>0$. More importantly, our algorithms achieve linear or nearly linear running times when $k$ is a constant, and significantly improve the existing ones. Our results can be easily extended to metric balanced clusterings and the running times are sub-linear in terms of the complexity of $n$-point metric.

📄 PDF Abstract BibTeX arXiv:1809.00932

Code (0)

등록된 구현이 없습니다.

Tasks

ClusteringConstrained ClusteringVocal Bursts Intensity Prediction

Fast kNN mode seeking clustering applied to active learning

2017-12-20 · Robert P. W. Duin, Sergey Verzakov

A significantly faster algorithm is presented for the original kNN mode seeking procedure. It has the advantages over the well-known mean shift algorithm that it is feasible in high-dimensional vector spaces and results …

Active Learning Clustering General Classification

Learning Deep Representations By Distributed Random Samplings

2013-12-16 · Xiao-Lei Zhang

In this paper, we propose an extremely simple deep model for the unsupervised nonlinear dimensionality reduction -- deep distributed random samplings, which performs like a stack of unsupervised bootstrap aggregating. Fi…

Clustering Dimensionality Reduction

k2-means for fast and accurate large scale clustering

2016-05-30 · Eirikur Agustsson, Radu Timofte, Luc van Gool

We propose k^2-means, a new clustering method which efficiently copes with large numbers of clusters and achieves low energy solutions. k^2-means builds upon the standard k-means (Lloyd's algorithm) and combines a new st…

Clustering

Multidimensional Hopfield Networks for clustering

2023-10-11 · Gergely Stomfai, Łukasz Sienkiewicz, Barbara Rychalska

We present the Multidimensional Hopfield Network (DHN), a natural generalisation of the Hopfield Network. In our theoretical investigations we focus on DHNs with a certain activation function and provide energy functions…

Clustering Graph Embedding

Clustering Ensemble Meets Low-rank Tensor Approximation

2020-12-16 · Yuheng Jia, Hui Liu, Junhui Hou, Qingfu Zhang

This paper explores the problem of clustering ensemble, which aims to combine multiple base clusterings to produce better performance than that of the individual one. The existing clustering ensemble methods generally co…

Clustering Clustering Ensemble