Information theoretic clustering of sparse cooccurrence data

Inderjit S. Dhillon, Yuqiang Guan

Abstract

A novel approach to clustering cooccurrence data poses it as an optimization problem in information theory which minimizes the resulting loss in mutual information. A divisive clustering algorithm that monotonically reduces this loss function was recently proposed. We show that sparse high-dimensional data presents special challenges which can result in the algorithm getting stuck at poor local minima. We propose two solutions to this problem: (a) a "prior" to overcome infinite relative entropy values as in the supervised Naive Bayes algorithm, and (b) local search to escape local minima. Finally, we combine these solutions to get a robust algorithm that is computationally efficient. We present experimental results to show that the proposed method is effective in clustering document collections and outperform previous information-theoretic clustering approaches.
BibTeX
@inproceedings{dhillon2003information,
  author = {Inderjit S. Dhillon and Yuqiang Guan},
  title = {{Information theoretic clustering of sparse cooccurrence data}},
  booktitle = {ICDM},
  year = {2003},
  doi = {10.1109/icdm.2003.1250966},
}

Loading related content...

Figure