Clustering on the Unit Hypersphere using von Mises-Fisher Distributions Export

@article{citeulike:3666407, abstract = {Several large scale data mining applications, such as text categorization and gene expression analysis, involve high-dimensional data that is also inherently directional in nature. Often such data is L 2 normalized so that it lies on the surface of a unit hypersphere. Popular models such as (mixtures of) multi-variate Gaussians are inadequate for characterizing such data. This paper proposes a generative mixture-model approach to clustering directional data based on the von Mises-Fisher (vMF) distribution, which arises naturally for data distributed on the unit hypersphere. In particular, we derive and analyze two variants of the Expectation Maximization (EM) framework for estimating the mean and concentration parameters of this mixture. Numerical estimation of the concentration parameters is non-trivial in high dimensions since it involves functional inversion of ratios of Bessel functions. We also formulate two clustering algorithms corresponding to the variants of EM that we derive. Our approach provides a theoretical basis for the use of cosine similarity that has been widely employed by the information retrieval community, and obtains the spherical kmeans algorithm (kmeans with cosine similarity) as a special case of both variants. Empirical results on clustering of high-dimensional text and gene-expression data based on a mixture of vMF distributions show that the ability to estimate the concentration parameter for each vMF component, which is not present in existing approaches, yields superior results, especially for difficult clustering tasks in high-dimensional spaces.}, address = {Cambridge, MA, USA}, author = {Banerjee, Arindam and Dhillon, Inderjit S. and Ghosh, Joydeep and Sra, Suvrit}, citeulike-article-id = {3666407}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1046920.1088718}, issn = {1533-7928}, journal = {Journal of Machine Learning Research}, keywords = {clustering, directional\_statistics, mises-fisher, text\_modeling, topic\_modeling}, pages = {1345--1382}, posted-at = {2008-11-23 17:00:13}, priority = {0}, publisher = {MIT Press}, title = {{Clustering on the Unit Hypersphere using von Mises-Fisher Distributions}}, url = {http://portal.acm.org/citation.cfm?id=1046920.1088718}, volume = {6}, year = {2005} }

TY - JOUR ID - citeulike:3666407 L3 - citeulike-article-id:3666407 N2 - Several large scale data mining applications, such as text categorization and gene expression analysis, involve high-dimensional data that is also inherently directional in nature. Often such data is L 2 normalized so that it lies on the surface of a unit hypersphere. Popular models such as (mixtures of) multi-variate Gaussians are inadequate for characterizing such data. This paper proposes a generative mixture-model approach to clustering directional data based on the von Mises-Fisher (vMF) distribution, which arises naturally for data distributed on the unit hypersphere. In particular, we derive and analyze two variants of the Expectation Maximization (EM) framework for estimating the mean and concentration parameters of this mixture. Numerical estimation of the concentration parameters is non-trivial in high dimensions since it involves functional inversion of ratios of Bessel functions. We also formulate two clustering algorithms corresponding to the variants of EM that we derive. Our approach provides a theoretical basis for the use of cosine similarity that has been widely employed by the information retrieval community, and obtains the spherical kmeans algorithm (kmeans with cosine similarity) as a special case of both variants. Empirical results on clustering of high-dimensional text and gene-expression data based on a mixture of vMF distributions show that the ability to estimate the concentration parameter for each vMF component, which is not present in existing approaches, yields superior results, especially for difficult clustering tasks in high-dimensional spaces. JF - Journal of Machine Learning Research SN - 1533-7928 AD - Cambridge, MA, USA EP - 1382 TI - {Clustering on the Unit Hypersphere using von Mises-Fisher Distributions} PB - MIT Press VL - 6 SP - 1345 KW - clustering KW - directional_statistics KW - mises-fisher KW - text_modeling KW - topic_modeling AU - Banerjee, Arindam AU - Dhillon, Inderjit AU - Ghosh, Joydeep AU - Sra, Suvrit PY - 2005/// UR - http://portal.acm.org/citation.cfm?id=1046920.1088718 ER -