Accelerating EM Clustering to Find High Quality Solutions

Clustering is one of the most important techniques used in Data Mining. This article focuses on the EM clustering algorithm. Two fundamental aspects are studied: achieving faster convergence and nding higher quality clustering solutions. This work introduces several improvements to the EM clustering algorithm, being periodic M steps during initial iterations, reseeding of low weight clusters and splitting of high weight clusters the most important. These improvements lead to two important parameters. The rst parameter is the number of M steps per iteration and the second one, a weight threshold to reseed low-weight clusters. Experiments show how frequently the M step must be executed and what weight threshold values make EM reach higher quality solutions. In general, the improved EM clustering algorithm nds higher quality solutions than the Classical EM algorithm and converges in less iterations.