FREM: fast and robust EM clustering for large data sets

ABSTRACT

Clustering is a fundamental Data Mining technique. This article presents an improved EM algorithm to cluster large data sets having high dimensionality, noise and zero variance problems. The algorithm incorporates improvements to increase the quality of solutions and speed. In general the algorithm can find a good clustering solution in 3 scans over the data set. Alternatively, it can be run until it converges. The algorithm has a few parameters that are easy to set and have defaults for most cases. The proposed algorithm is compared against the standard EM algorithm and the On-Line EM algorithm.

REFERENCES

• 1: Charu C. Aggarwal , Philip S. Yu, Finding generalized projected clusters in high dimensional spaces, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.70-81, May 15-18, 2000, Dallas, Texas, United States
• 2: Charu C. Aggarwal , Philip S. Yu, Outlier detection for high dimensional data, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.37-46, May 21-24, 2001, Santa Barbara, California, United States
• 3: Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan, Automatic subspace clustering of high dimensional data for data mining applications, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.94-105, June 01-04, 1998, Seattle, Washington, United States
• 4: Kevin S. Beyer , Jonathan Goldstein , Raghu Ramakrishnan , Uri Shaft, When Is ''Nearest Neighbor'' Meaningful?, Proceeding of the 7th International Conference on Database Theory, p.217-235, January 10-12, 1999
• 5: P. Bradley, U. Fayyad, and C. Reina. Scaling clustering algorithms to large databases. In ACM KDD Conference, 1998.
• 6: P. Bradley, U. Fayyad, and C. Reina. Scaling EM clustering to large databases. Technical report, Microsoft Research, 1999.
• 7: Markus M. Breunig , Hans-Peter Kriegel , Peer Kröger , Jörg Sander, Data bubbles: quality preserving performance boosting for hierarchical clustering, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.79-90, May 21-24, 2001, Santa Barbara, California, United States
• 8: A.P. Dempster, N.M. Laird, and D. Rubin. Maximum likelihood estimation from incomplete data via the EM algorithm. Journal of The Royal Statistical Society, 39(1):1--38, 1977.
• 9: R. Dubes and A.K. Jain. Clustering Methodologies in Exploratory Data Analysis, pages 10--35. Academic Press, New York, 1980.
• 10: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 11: Fredrik Farnstrom , James Lewis , Charles Elkan, Scalability for clustering algorithms revisited, ACM SIGKDD Explorations Newsletter, v.2 n.1, p.51-57, June, 2000 [doi>10.1145/360402.360419]
• 12: Usama Fayyad , Gregory Piatetsky-Shapiro , Padhraic Smyth, The KDD process for extracting useful knowledge from volumes of data, Communications of the ACM, v.39 n.11, p.27-34, Nov. 1996 [doi>10.1145/240455.240464]
• 13: Venkatesh Ganti , Johannes Gehrke , Raghu Ramakrishnan, CACTUS—clustering categorical data using summaries, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.73-83, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312201]
• 14: Sudipto Guha , Rajeev Rastogi , Kyuseok Shim, CURE: an efficient clustering algorithm for large databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.73-84, June 01-04, 1998, Seattle, Washington, United States
• 15: S. Guha, R. Rastogi, and K. Shim. Rock: A robust clustering algorithm for categorical attributes. In ICDE Conference, 1999.
• 16: Zhexue Huang, Extensions to the k-Means Algorithm for Clustering Large Data Sets with Categorical Values, Data Mining and Knowledge Discovery, v.2 n.3, p.283-304, September 1998 [doi>10.1023/A:1009769707641]
• 17: Alexander Hinneburg , Daniel A. Keim, Optimal Grid-Clustering: Towards Breaking the Curse of Dimensionality in High-Dimensional Clustering, Proceedings of the 25th International Conference on Very Large Data Bases, p.506-517, September 07-10, 1999
• 18: Michael I. Jordan , Robert A. Jacobs, Hierarchical mixtures of experts and the EM algorithm, Neural Computation, v.6 n.2, p.181-214, March 1994 [doi>10.1162/neco.1994.6.2.181]
• 19: Edwin M. Knorr , Raymond T. Ng, Finding Intensional Knowledge of Distance-Based Outliers, Proceedings of the 25th International Conference on Very Large Data Bases, p.211-222, September 07-10, 1999
• 20: G.J. MacLachlan and T. Krishnan. The EM Algorithm and Extensions, pages 120--211. Wiley, New York, 1997.
• 21: Alexandros Nanopoulos , Yannis Theodoridis , Yannis Manolopoulos, C2P: Clustering based on Closest Pairs, Proceedings of the 27th International Conference on Very Large Data Bases, p.331-340, September 11-14, 2001
• 22: R. Neal and G. Hinton. A view of the EM algorithm that justifies incremental, sparse and other variants. Technical report, Dept. of Statistics, University of Toronto, 1993.
• 23: Raymond T. Ng , Jiawei Han, Efficient and Effective Clustering Methods for Spatial Data Mining, Proceedings of the 20th International Conference on Very Large Data Bases, p.144-155, September 12-15, 1994
• 24: Carlos Ordonez , Edward Omiecinski, Mining complex databases using the EM algorithm, 2000
• 25: Carlos Ordonez , Paul Cereghini, SQLEM: fast clustering in SQL using the EM algorithm, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.559-570, May 15-18, 2000, Dallas, Texas, United States
• 26: Carlos Ordonez , Edward Omiecinski , Levien de Braal , Cesar A. Santana , Norberto Ezquerra , Jose A. Taboada , David Cooke , Elizabeth Krawczynska , Ernest V. Garcia, Mining Constrained Association Rules to Predict Heart Disease, Proceedings of the 2001 IEEE International Conference on Data Mining, p.433-440, November 29-December 02, 2001
• 27: Carlos Ordonez , Edward Omiecinski , Norberto Ezquerra, A Fast Algorithm to Cluster High Dimensional Basket Data, Proceedings of the 2001 IEEE International Conference on Data Mining, p.633-636, November 29-December 02, 2001
• 28: Dan Pelleg , Andrew Moore, Accelerating exact k-means algorithms with geometric reasoning, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.277-281, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312248]
• 29: R.A. Redner and H.F. Walker. Mixure densities, maximum likelihood, and the EM algorithm. SIAM Review, 26:195--239, 1984.
• 30: Sam Roweis , Zoubin Ghahramani, A unifying review of linear Gaussian models, Neural Computation, v.11 n.2, p.305-345, Feb. 15, 1999 [doi>10.1162/089976699300016674]
• 31: Masa-Aki Sato , Shin Ishii, On-line EM Algorithm for the Normalized Gaussian Network, Neural Computation, v.12 n.2, p.407-432, February 2000 [doi>10.1162/089976600300015853]
• 32: D. Scott. Multivariate Density Estimation, pages 10--130. J. Wiley and Sons, New York, 1992.
• 33: Naonori Ueda , Ryohei Nakano , Zoubin Ghahramani , Geoffrey E. Hinton, SMEM algorithm for mixture models, Proceedings of the 1998 conference on Advances in neural information processing systems II, p.599-605, July 1999
• 34: Lei Xu , Michael I. Jordan, On convergence properties of the EM algorithm for Gaussian mixtures, Neural Computation, v.8 n.1, p.129-151, Jan. 1996
• 35: Alan L. Yuille , Paul Stolorz , Joachim Utans, Statistical physics, mixtures of distributions, and the EM algorithm, Neural Computation, v.6 n.2, p.334-340, March 1994 [doi>10.1162/neco.1994.6.2.334]
• 36: Tian Zhang , Raghu Ramakrishnan , Miron Livny, BIRCH: an efficient data clustering method for very large databases, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.103-114, June 04-06, 1996, Montreal, Quebec, Canada

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

Additional Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering

General Terms:
Algorithms, Theory

Keywords:
EM, clustering, data mining