Fast Expectation Maximization Clustering Algorithm
Durgesh Kumar, J. V. R. Murthy, N. B. VENKATESWARLU · International Journal of Computational Intelligence Research · 2012
Expectation Maximization (EM) is an efficient and widely employed mixturemodel based data clustering algorithm. EM algorithm iterates two prominent computationally demanding steps to name: expectation and maximization steps. Many researchers reported that compared to contemporary clustering algorithms EM algorithm to be giving exceptionally good clustering results, but demands huge computational efforts. In the present paper, methods are proposed to reduce the computational time required for computing probability density function (pdf) which involves computation of a quadratic term and whose computational complexity is O(d 2 ) , where d is number of dimensions. Winograd's approach is employed to reduce computational effort required for Expectation step. Experiments are carried out with popular data mining data sets from UCI ML repository and simulated data sets. The algoritm is observed to be giving about 5 to 6 speed-up compared to standard implementations such as Cluster package of Purdue University.