Clustering on the Unit Hypersphere using von Mises-Fisher Distributions

摘要

Several large scale data mining applications, such as textcategorization and gene expression analysis, involve high-dimensionaldata that is also inherently directional in nature. Often such datais L₂ normalized so that it lies on the surface of aunit hypersphere. Popular models such as (mixtures of) multi-variateGaussians are inadequate for characterizing such data. This paperproposes a generative mixture-model approach to clustering directionaldata based on the von Mises-Fisher (vMF) distribution, which arisesnaturally for data distributed on the unit hypersphere. Inparticular, we derive and analyze two variants of the ExpectationMaximization (EM) framework for estimating the mean and concentrationparameters of this mixture. Numerical estimation of the concentrationparameters is non-trivial in high dimensions since it involvesfunctional inversion of ratios of Bessel functions. We also formulatetwo clustering algorithms corresponding to the variants of EM that wederive. Our approach provides a theoretical basis for the use ofcosine similarity that has been widely employed by the informationretrieval 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 andgene-expression data based on a mixture of vMF distributions show thatthe ability to estimate the concentration parameter for each vMFcomponent, which is not present in existing approaches, yieldssuperior results, especially for difficult clustering tasks inhigh-dimensional spaces. color="gray">