Generative model-based clustering of directional data

ABSTRACT

High dimensional directional data is becoming increasingly important in contemporary applications such as analysis of text and gene-expression data. A natural model for multi-variate directional data is provided by the von Mises-Fisher (vMF) distribution on the unit hypersphere that is analogous to the multi-variate Gaussian distribution in R^d. In this paper, we propose modeling complex directional data as a mixture of vMF distributions. We derive and analyze two variants of the Expectation Maximization (EM) framework for estimating the parameters of this mixture. We also propose two clustering algorithms corresponding to these variants. An interesting aspect of our methodology is that the spherical kmeans algorithm (kmeans with cosine similarity) can be shown to be a special case of both our algorithms. Thus, modeling text data by vMF distributions lends theoretical validity to the use of cosine similarity which has been widely used by the information retrieval community. As part of experimental validation, we present results on modeling high-dimensional text and gene-expression data as a mixture of vMF distributions. The results indicate that our approach yields superior clusterings especially for difficult clustering tasks in high-dimensional spaces.

REFERENCES

• 1: Charu C. Aggarwal, Re-designing distance functions and distance-based applications for high dimensional data, ACM SIGMOD Record, v.30 n.1, p.13-18, March 2001 [doi>10.1145/373626.373638]
• 2: A. Banerjee, I. S. Dhillon, J. Ghosh, and S. Sra. Clustering on hyperspheres using Expectation Maximization. Technical Report TR-03-07, Department of Computer Sciences, University of Texas, February 2003.
• 3: A. Banerjee and J. Ghosh. Frequency sensitive competitive learning for clustering on high-dimensional hyperspheres. In Proceedings International Joint Conference on Neural Networks, pages 1590--1595, May 2002.
• 4: P. S. Bradley, K. P. Bennett, and A. Demiriz. Constrained k-means clustering. Technical report, Microsoft Research, May 2000.
• 5: M. Collins. The EM algorithm. In fulfillment of Written Preliminary Exam II requirement, September 1997.
• 6: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 7: Sanjoy Dasgupta, Learning Mixtures of Gaussians, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.634, October 17-18, 1999
• 8: A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society, Series B, 39:1--38, 1977.
• 9: I. Dhillon and J. Kogan, editors. Proc. Workshop on Clustering High Dimensional Data and its Applications. SIAM, 2002.
• 10: Inderjit S. Dhillon , Yuqiang Guan , J. Kogan, Iterative Clustering of High Dimensional Text Data Augmented by Local Search, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.131, December 09-12, 2002
• 11: Inderjit S. Dhillon , Dharmendra S. Modha, Concept Decompositions for Large Sparse Text Data Using Clustering, Machine Learning, v.42 n.1-2, p.143-175, January-February 2001 [doi>10.1023/A:1007612920971]
• 12: I. S. Dhillon and S. Sra. Modeling data using directional distributions. Technical Report TR-06-03, University of Texas, Dept. of Coputer Sciences, February 2003.
• 13: M. B. Eisen, P. T. Spellman, P. O. Brown, and D. Botstein. Cluster analysis and display of genome-wide expression patterns. Proc. Natl. Acad. Sci., 95:14863--14868, 1998.
• 14: T. R. H. et. al Functional discovery via a compendium of expression profiles. Cell, 102:109--126, 2000.
• 15: J. Ghosh. Scalable clustering methods for data mining. In N. Ye, editor, Handbook of Data Mining, pages 247--277. Lawrence Erlbaum, 2003.
• 16: G. K. Gupta and J. Ghosh. Detecting seasonal and divergent trends and visualization for very high dimensional transactional data. In Proc. 1st SIAM Intl. Conf. on Data Mining, April 2001.
• 17: Piotr Indyk, A Sublinear Time Approximation Scheme for Clustering in Metric Spaces, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.154, October 17-18, 1999
• 18: Tommi S. Jaakkola , David Haussler, Exploiting generative models in discriminative classifiers, Proceedings of the 1998 conference on Advances in neural information processing systems II, p.487-493, July 1999
• 19: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 20: M. Kearns, Y. Mansour, and A. Ng. An information-theoretic analysis of hard and soft assignment methods for clustering. In 13th Annual Conf. on Uncertainty in Artificial Intelligence (UA197), 1997.
• 21: K. V. Mardia. Statistical Distributions in Scienctific Work, volume 3, chapter Characteristics of directional distributions, pages 365--385. Reidel, Dordrecht, 1975.
• 22: K. V. Mardia and P. Jupp. Directional Statistics. John Wiley and Sons Ltd., 2nd edition, 2000.
• 23: Radford M. Neal , Geoffrey E. Hinton, A view of the EM algorithm that justifies incremental, sparse, and other variants, Learning in graphical models, MIT Press, Cambridge, MA, 1999
• 24: Kamal Nigam , Andrew Kachites McCallum , Sebastian Thrun , Tom Mitchell, Text Classification from Labeled and Unlabeled Documents using EM, Machine Learning, v.39 n.2-3, p.103-134, May-June 2000 [doi>10.1023/A:1007692713085]
• 25: C. R. Rao. Linear Statistical Inference and its Applications. Wiley, New York, 2nd edition, 1973.
• 26: Badrul Sarwar , George Karypis , Joseph Konstan , John Reidl, Item-based collaborative filtering recommendation algorithms, Proceedings of the 10th international conference on World Wide Web, p.285-295, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372071]
• 27: B. Schölkopf and A. Smola. Learning with Kernels. MIT Press, 2001.
• 28: Janne Sinkkonen , Samuel Kaski, Clustering based on conditional distributions in an auxiliary space, Neural Computation, v.14 n.1, p.217-239, January 2002 [doi>10.1162/089976602753284509]
• 29: P. Smyth. Clustering sequences with hidden Markov models. In M. C. Mozer, M. I. Jordan, and T. Petsche, editors, Advances in Neural Information Processing, volume 9, pages 648--654. MIT Press, 1997.
• 30: A. Strehl, J. Ghosh, and R. Mooney. Impact of similarity measures on web-page clustering. In Proc 7th Natl Conf on Artificial Intelligence: Workshop of AI for Web Search (AAAI 2000), pages 58--64. AAAI, July 2000.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering

Keywords:
EM, clustering, directional data, mixtures, von Mises-Fisher