SyMP: an efficient clustering approach to identify clusters of arbitrary shapes in large data sets

ABSTRACT

We propose a new clustering algorithm, called SyMP, which is based on synchronization of pulse-coupled oscillators. SyMP represents each data point by an Integrate-and-Fire oscillator and uses the relative similarity between the points to model the interaction between the oscillators. SyMP is robust to noise and outliers, determines the number of clusters in an unsupervised manner, identifies clusters of arbitrary shapes, and can handle very large data sets. The robustness of SyMP is an intrinsic property of the synchronization mechanism. To determine the optimum number of clusters, SyMP uses a dynamic resolution parameter. To identify clusters of various shapes, SyMP models each cluster by multiple Gaussian components. The number of components is automatically determined using a dynamic intra-cluster resolution parameter. Clusters with simple shapes would be modeled by few components while clusters with more complex shapes would require a larger number of components. The scalable version of SyMP uses an efficient incremental approach that requires a simple pass through the data set. The proposed clustering approach is empirically evaluated with several synthetic and real data sets, and its performance is compared with CURE.

REFERENCES

• 1: 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
• 2: P. Bradley, U. Fayyad, and C. Reina. Scaling clustering algorithms to large databases. In Proc. of the ACM SIGKDD, 1998.
• 3: P. Bradley, U. Fayyad, and C. Reina. Scaling EM clustering to large databases. Technical Report MSR-TR-98-35, Microsoft Research, 1998.
• 4: A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society Series B, 39(1):1--38, 1977.
• 5: M. Ester, H. P. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proc. of the ACM SIGKDD, 1996.
• 6: 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]
• 7: Hichem Frigui , Mohamed Ben Hadj Rhouma, A Synchronization Based Algorithm for Discovering Ellipsoidal Clusters in Large Datasets, Proceedings of the 2001 IEEE International Conference on Data Mining, p.139-146, November 29-December 02, 2001
• 8: 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
• 9: Daniel A. Keim , Alexander Hinneburg, Clustering techniques for large data sets—from the past to the future, Tutorial notes of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.141-181, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312179.312189]
• 10: A. Hinneburg and D. Keim. An efficient approach to clustering in large multimedia databases with noise. In Proc. of the ACM SIGKDD, 1998.
• 11: L. Kaufman and P. Rousseeuw. Finding Groups in Data. John Wiley and Sons, 1989.
• 12: L. Kaufman and P. J. Rousseeuw. Finding Groups in Data: An Introduction to Cluster Analysis. Addison Wesley, NEW York, 1990.
• 13: R. Krishnapuram, H. Frigui, and O. Nasraoui. Fuzzy and possibilistic shell clustering algorithms and their application to boundary detection and surface approximation I. IEEE Trans. FS, 3(1):29--43, 1995.
• 14: 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
• 15: Mohamed Ben Hadj Rhouma , Hichem Frigui, Self-Organization of Pulse-Coupled Oscillators with Application to Clustering, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.2, p.180-195, February 2001 [doi>10.1109/34.908968 ]
• 16: Jorma Rissanen, Stochastic Complexity in Statistical Inquiry Theory, World Scientific Publishing Co., Inc., River Edge, NJ, 1989
• 17: R.O.Duda and P. E. Hart. Pattern Classification and Scene Analysis. John Wiley and Sons, 1973.
• 18: Gholamhosein Sheikholeslami , Surojit Chatterjee , Aidong Zhang, WaveCluster: A Multi-Resolution Clustering Approach for Very Large Spatial Databases, Proceedings of the 24rd International Conference on Very Large Data Bases, p.428-439, August 24-27, 1998
• 19: Wei Wang , Jiong Yang , Richard R. Muntz, STING: A Statistical Information Grid Approach to Spatial Data Mining, Proceedings of the 23rd International Conference on Very Large Data Bases, p.186-195, August 25-29, 1997
• 20: Xiaowei Xu , Martin Ester , Hans-Peter Kriegel , Jörg Sander, A Distribution-Based Clustering Algorithm for Mining in Large Spatial Databases, Proceedings of the Fourteenth International Conference on Data Engineering, p.324-331, February 23-27, 1998
• 21: 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:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Algorithms

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Multimedia databases
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

General Terms:
Algorithms, Measurement, Performance

Keywords:
Gaussian mixture models, clustering, large datasets