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

Arindam Banerjee, Joydeep Ghosh

Research output: Contribution to journalArticlepeer-review

73 Scopus citations

Abstract

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
Volume15
Issue number3
DOIs
StatePublished - May 1 2004

Keywords

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

Fingerprint 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