A fast and recursive algorithm for clustering large datasets with k-medians

DOI10.1016/J.CSDA.2011.11.019zbMATH Open1243.62087arXiv1101.4179OpenAlexW2003188728MaRDI QIDQ434902FDOQ434902

Jean-Marie Monnez, Peggy Cénac, Hervé Cardot

Publication date: 16 July 2012

Published in: Computational Statistics and Data Analysis (Search for Journal in Brave)

Abstract: Clustering with fast algorithms large samples of high dimensional data is an important challenge in computational statistics. Borrowing ideas from MacQueen (1967) who introduced a sequential version of the $k$-means algorithm, a new class of recursive stochastic gradient algorithms designed for the $k$-medians loss criterion is proposed. By their recursive nature, these algorithms are very fast and are well adapted to deal with large samples of data that are allowed to arrive sequentially. It is proved that the stochastic gradient algorithm converges almost surely to the set of stationary points of the underlying loss criterion. A particular attention is paid to the averaged versions, which are known to have better performances, and a data-driven procedure that allows automatic selection of the value of the descent step is proposed. The performance of the averaged sequential estimator is compared on a simulation study, both in terms of computation speed and accuracy of the estimations, with more classical partitioning techniques such as $k$-means, trimmed $k$-means and PAM (partitioning around medoids). Finally, this new online clustering technique is illustrated on determining television audience profiles with a sample of more than 5000 individual television audiences measured every minute over a period of 24 hours.

Full work available at URL: https://arxiv.org/abs/1101.4179

Recommendations

• Near-optimal large-scale k-medoids clustering
• scientific article; zbMATH DE number 2090269
• Learning Theory
• Fast recursive and efficient algorithms for estimating the functional median and robust clustering in large dimension
• On coresets for k-means and k-median clustering
• A fast clustering algorithm for large-scale and high dimensional data
• Algorithms for \(k\)-median clustering over distributed streams
• A framework for statistical clustering with constant time approximation algorithms for \(K\)-median and \(K\)-means clustering
• scientific article; zbMATH DE number 7760187

zbMATH Keywords

stochastic gradienthigh dimensional datastochastic approximationaveraging\(k\)-medoidsonline clusteringpartitioning around medoidsrecursive estimatorsRobbins-Monro

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Sequential estimation (62L12) Stochastic approximation (62L20)

Cites Work

• Finding Groups in Data
• A general trimming approach to robust cluster analysis
• On a Geometric Notion of Quantiles for Multivariate Data
• Stochastic Approximation for Multivariate and Functional Median
• Acceleration of Stochastic Approximation by Averaging
• Printer graphics for clustering
• Title not available (Why is that?)
• Asymptotic Almost Sure Efficiency of Averaged Stochastic Algorithms
• Title not available (Why is that?)
• Asymptotic behaviour of classification maximum likelihood estimates
• Hybrid hierarchical clustering with applications to microarray data
• A review of robust clustering methods
• Robustness Properties of k Means and Trimmed k Means
• Almost sure convergence of stochastic gradient processes with matrix step sizes
• Data Clustering: Theory, Algorithms, and Applications
• Large-Scale Machine Learning with Stochastic Gradient Descent
• Online wavelet-based density estimation for non-stationary streaming data
• Editorial: Machine learning and robust data mining
• \(L_1\)-quantization and clustering in Banach spaces

Cited In (15)

• Recursive estimators of integrated squared density derivatives
• Widening the scope of an eigenvector stochastic approximation process and application to streaming PCA and related methods
• Metric \(k\)-median clustering in insertion-only streams
• Online estimation of hazard rate under random censoring
• Clustering transformed compositional data usingK-means, with applications in gene expression and bicycle sharing system data
• Multiobjective semisupervised learning with a right‐censored endpoint adapted to the multiple imputation framework
• Online estimation of integrated squared density derivatives
• A compact law of the iterated logarithm for online estimator of hazard rate under random censoring
• Bayesian Quadrature, Energy Minimization, and Space-Filling Design
• Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm
• Fast estimation of the median covariation matrix with application to online robust principal components analysis
• Estimating the geometric median in Hilbert spaces with stochastic gradient algorithms: \(L^p\) and almost sure rates of convergence
• Online stochastic Newton methods for estimating the geometric median and applications
• Streaming constrained binary logistic regression with online standardized data
• A quasi-Bayesian perspective to online clustering

Uses Software

• clusfind

This page was built for publication: A fast and recursive algorithm for clustering large datasets with \(k\)-medians

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q434902)