Frequency-sensitive competitive learning for scalable balanced clustering on high-dimensional hyperspheres

Arindam Banerjee, Joydeep Ghosh

Research output: Contribution to journalArticlepeer-review

97 Scopus citations


Competitive learning mechanisms for clustering, in general, suffer from poor performance for very high-dimensional (>1000) data because of "curse of dimensionality" effects. In applications such as document clustering, it is customary to normalize the high-dimensional input vectors to unit length, and it is sometimes also desirable to obtain balanced clusters, i.e., clusters of comparable sizes. The spherical kmeans (sDkmeans) algorithm, which normalizes the cluster centers as well as the inputs, has been successfully used to cluster normalized text documents in 2000+ dimensional space. Unfortunately, like regular kmeans and its soft expectation-maximization-based version, sDkmeans tends to generate extremely imbalanced clusters in high-dimensional spaces when the desired number of clusters is large (tens or more). This paper first shows that the sDkmeans 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. The proposed generative model is then adapted in a principled way to yield three frequency-sensitive competitive learning variants that are applicable to static data and produced high-quality and well-balanced clusters for high-dimensional data. Like kmeans, each iteration is linear in the number of data points and in the number of clusters for all the three algorithms. A frequency-sensitive algorithm to cluster streaming data is also proposed. Experimental results on clustering of high-dimensional text data sets are provided to show the effectiveness and applicability of the proposed techniques.

Original languageEnglish (US)
Pages (from-to)702-718
Number of pages17
JournalIEEE Transactions on Neural Networks
Issue number3
StatePublished - May 2004

Bibliographical note

Funding Information:
Manuscript recieved October 4, 2002. This work was supported in part by the National Science Foundation (NSF) under Grant ECS-9900353 and in part by the Intel Corporation under Research Grant 8032. The authors are with the Department of Electrical and Computer Engineering, University of Texas at Austin, Austin, TX 78712 USA (e-mail:; Digital Object Identifier 10.1109/TNN.2004.824416


  • Balanced clustering
  • Expectation maximization (EM)
  • Frequency-sensitive competitive learning (FSCL)
  • High-dimensional clustering
  • Kmeans
  • Normalized data
  • Scalable clustering
  • Streaming data
  • Text clustering


Dive into the research topics of 'Frequency-sensitive competitive learning for scalable balanced clustering on high-dimensional hyperspheres'. Together they form a unique fingerprint.

Cite this