Efficient online sphercal K-means clustering
Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005.Published 5 January 2006
Shi Zhong
Citations213
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is demonstrated that the online spherical k-means algorithm can achieve significantly better clustering results than the batch version, especially when an annealing-type learning rate schedule is used.
Abstract
The spherical k-means algorithm, i.e., the k-means algorithm with cosine similarity, is a popular method for clustering high-dimensional text data. In this algorithm, each document as well as each cluster mean is represented as a high-dimensional unit-length vector. However, it has been mainly used in hatch mode. Thus is, each cluster mean vector is updated, only after all document vectors being assigned, as the (normalized) average of all the document vectors assigned to that cluster. This paper investigates an online version of the spherical k-means algorithm based on the well-known winner-take-all competitive learning. In this online algorithm, each cluster centroid is incrementally updated given a document. We demonstrate that the online spherical k-means algorithm can achieve significantly better clustering results than the batch version, especially when an annealing-type learning rate schedule is used. We also present heuristics to improve the speed, yet almost without loss of clustering quality.
Keywords
Computer SciencePhysics and Astronomy
ScienceOptimization by Simulated Annealing
44,600 Citations1983Scott Kirkpatrick, C. D. Gelatt +1 more
A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems.
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)Some methods for classification and analysis of multivariate observations
22,787 Citations1967James B. MacQueen
SIAM Journal on Scientific ComputingA Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
5,588 Citations1998George Karypis, Vipin Kumar
This work presents a new coarsening heuristic (called heavy-edge heuristic) for which the size of the partition of the coarse graph is within a small factor of theSize of the final partition obtained after multilevel refinement, and presents a much faster variation of the Kernighan--Lin (KL) algorithm for refining during uncoarsening.
IEEE Transactions on Neural Networks'Neural-gas' network for vector quantization and its application to time-series prediction
1,436 Citations1993Thomas Martinetz, S.G. Berkovich +1 more
It is shown that the dynamics of the reference (weight) vectors during the input-driven adaptation procedure are determined by the gradient of an energy function whose shape can be modulated through a neighborhood determining parameter and resemble the dynamicsof Brownian particles moving in a potential determined by a data point density.
Machine LearningConcept Decompositions for Large Sparse Text Data Using Clustering
1,297 Citations2001Inderjit S. Dhillon, Dharmendra S. Modha
The concept vectors produced by the spherical k-means algorithm constitute a powerful sparse and localized “basis” for text data sets and are localized in the word space, are sparse, and tend towards orthonormality.
Proceedings of the IEEEDeterministic annealing for clustering, compression, classification, regression, and related optimization problems
869 Citations1998Kenneth Rose
The deterministic annealing approach to clustering and its extensions has demonstrated substantial performance improvement over standard supervised and unsupervised learning methods in a variety of important applications including compression, estimation, pattern recognition and classification, and statistical regression.
Neural NetworksCompetitive learning algorithms for vector quantization
670 Citations1990Stanley C. Ahalt, Ashok Krishnamurthy +2 more
A new competitive-learning algorithm based on the “conscience” learning method is introduced that is shown to be efficient and yields near-optimal results in vector quantization for data compression.
Impact of Similarity Measures on Web-page Clustering
662 Citations2000Alexander L. Strehl, Joydeep Ghosh +1 more
Comparing four popular similarity measures in conjunction with several clustering techniques, cosine and extended Jaccard similarities emerge as the best measures to capture human categorization behavior, while Euclidean performs poorest.
University of Minnesota Digital Conservancy (University of Minnesota)Criterion Functions for Document Clustering: Experiments and Analysis
592 Citations2001Ying Zhao, George Karypis
CLUTO - A Clustering Toolkit
551 Citations2002George Karypis
Clustering algorithms divide data into meaningful or useful groups, called clusters, such that the intra-cluster similarity is maximized and the inter-clusters similarity is minimized.
Cluster ensembles: a knowledge reuse framework for combining partitionings
323 Citations2002Alexander L. Strehl, Joydeep Ghosh
This contribution is to formally define the cluster ensemble problem as an optimization problem and to propose three effective and efficient combiners for solving it based on a hypergraph model.
Knowledge and Information SystemsGenerative model-based document clustering: a comparative study
247 Citations2005Shi Zhong, Joydeep Ghosh
This paper presents a detailed empirical study of 12 generative approaches to text clustering, obtained by applying four types of document-to-cluster assignment strategies to each of three base models, namely mixtures of multivariate Bernoulli, multinomial, and von Mises-Fisher distributions.
Massive computingEfficient Clustering of Very Large Document Collections
236 Citations2001Inderjit S. Dhillon, James Fan +1 more
This paper presents a time and memory efficient technique for the entire clustering process, including the creation of the vector space model, and demonstrates how this efficiency is obtained by a memory-efficient multi-threaded preprocessing scheme and a fast clustering algorithm that fully exploits the sparsity of the data set.
Iterative clustering of high dimensional text data augmented by local search
128 Citations2003Inderjit S. Dhillon, Yuqiang Guan +1 more
A local search procedure that refines a given clustering by incrementally moving data points between clusters, thus achieving a higher objective function value and a powerful "ping-pong" strategy that often qualitatively improves k-means clustering and is computationally efficient.
IEEE Transactions on Neural NetworksFrequency-Sensitive Competitive Learning for Scalable Balanced Clustering on High-Dimensional Hyperspheres
112 Citations2004Arindam Banerjee, Joydeep Ghosh
This paper shows that the spkmeans algorithm can be derived from a certain maximum likelihood formulation using a mixture of von Mises-Fisher distributions as the generative model, and in fact, it can be considered as a batch-mode version of (normalized) competitive learning.
IEEE Transactions on Neural NetworksDiffusion approximation of frequency sensitive competitive learning
24 Citations1997A.S. Galanopoulos, Randolph L. Moses +1 more
This paper approximate the final phase of FSCL learning by a diffusion process described by the Fokker-Plank equation and shows that the convergence conditions involve only the learning rate and that they are the same as the conditions for weak convergence described previously.
Fast Fuzzy Clustering of Web Page Collections
19 Citations2004Christian Borgelt, Andreas Nürnberger
An extension of learning vector quantization that draws on ideas from fuzzy clustering is studied, enabling us to find fuzzy clusters of ellipsoidal shape with a competitive learning scheme.