Streaming k-means approximation

2009-12-01 · NeurIPS 2009 12 · Nir Ailon, Ragesh Jaiswal, Claire Monteleoni

We provide a clustering algorithm that approximately optimizes the k-means objective, in the one-pass streaming setting. We make no assumptions about the data, and our algorithm is very light-weight in terms of memory, and computation. This setting is applicable to unsupervised learning on massive data sets, or resource-constrained devices. The two main ingredients of our theoretical work are: a derivation of an extremely simple pseudo-approximation batch algorithm for k-means, in which the algorithm is allowed to output more than k centers (based on the recent k-means++"), and a streaming clustering algorithm in which batch clustering algorithms are performed on small inputs (fitting in memory) and combined in a hierarchical manner. Empirical evaluations on real and simulated data reveal the practical utility of our method."

📄 PDF Abstract BibTeX

Code (0)

등록된 구현이 없습니다.

Tasks

Clustering

On Coreset Constructions for the Fuzzy $K$-Means Problem

2016-12-22 · Johannes Blömer, Sascha Brauer, Kathrin Bujna

The fuzzy $K$-means problem is a popular generalization of the well-known $K$-means problem to soft clusterings. We present the first coresets for fuzzy $K$-means with size linear in the dimension, polynomial in the numb…

K-means for Evolving Data Streams

2020-12-07 · Arkaitz Bidaurrazaga, Aritz Pérez, Marco Capó

Currently the amount of data produced worldwide is increasing beyond measure, thus a high volume of unsupervised data must be processed continuously. One of the main unsupervised data analysis is clustering. In streaming…

Clustering Drift Detection

Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming

2023-10-29 · NeurIPS 2023 11

Sketching algorithms have recently proven to be a powerful approach both for designing low-space streaming algorithms as well as fast polynomial time approximation schemes (PTAS). In this work, we develop new techniques …

Clustering Dictionary Learning

Differentially Private Clustering in Data Streams

2023-07-14 · Alessandro Epasto, Tamalika Mukherjee, Peilin Zhong

The streaming model is an abstraction of computing over massive data streams, which is a popular way of dealing with large-scale modern data analysis. In this model, there is a stream of data points, one after the other.…

Clustering

Dimensionality Reduction for k-Means Clustering and Low Rank Approximation

2014-10-24 · Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco 외

We show how to approximate a data matrix $\mathbf{A}$ with a much smaller sketch $\mathbf{\tilde A}$ that can be used to solve a general class of constrained k-rank approximation problems to within $(1+\epsilon)$ error. …

Clustering Dimensionality Reduction