Programming the K-means clustering algorithm in SQL

ABSTRACT

Using SQL has not been considered an efficient and feasible way to implement data mining algorithms. Although this is true for many data mining, machine learning and statistical algorithms, this work shows it is feasible to get an efficient SQL implementation of the well-known K-means clustering algorithm that can work on top of a relational DBMS. The article emphasizes both correctness and performance. From a correctness point of view the article explains how to compute Euclidean distance, nearest-cluster queries and updating clustering results in SQL. From a performance point of view it is explained how to cluster large data sets defining and indexing tables to store and retrieve intermediate and final results, optimizing and avoiding joins, optimizing and simplifying clustering aggregations, and taking advantage of sufficient statistics. Experiments evaluate scalability with synthetic data sets varying size and dimensionality. The proposed K-means implementation can cluster large data sets and exhibits linear scalability.

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: P. Bradley, U. Fayyad, and C. Reina. Scaling clustering algorithms to large databases. In ACM KDD Conference, pages 9--15, 1998.
• 3: John Clear , Debbie Dunn , Brad Harvey , Michael Heytens , Peter Lohman , Abhay Mehta , Mark Melton , Lars Rohrberg , Ashok Savasere , Robert Wehrmeister , Melody Xu, NonStop SQL/MX primitives for knowledge discovery, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.425-429, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312309]
• 4: G. Graefe, U. Fayyad, and S. Chaudhuri. On the efficient gathering of sufficient statistics for classification from large SQL databases. In ACM KDD Conference, pages 204--208, 1998.
• 5: Hasan M. Jamil, Ad Hoc Association Rule Mining as SQL3 Queries, Proceedings of the 2001 IEEE International Conference on Data Mining, p.609-612, November 29-December 02, 2001
• 6: J.B. MacQueen. Some methods for classification and analysis of multivariate observations. In Proc. of the 5th Berkeley Symposium on Mathematical Statistics and Probability, 1967.
• 7: Carlos Ordonez, Clustering binary data streams with K-means, Proceedings of the 8th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery, June 13-13, 2003, San Diego, California [doi>10.1145/882082.882087]
• 8: 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
• 9: Carlos Ordonez , Edward Omiecinski, FREM: fast and robust EM clustering for large data sets, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584889]
• 10: Carlos Ordonez , Edward Omiecinski, Efficient Disk-Based K-Means Clustering for Relational Databases, IEEE Transactions on Knowledge and Data Engineering, v.16 n.8, p.909-921, August 2004 [doi>10.1109/TKDE.2004.25]
• 11: Dimitris Papadopoulos , Carlotta Domeniconi , Dimitrios Gunopulos , Sheng Ma, Clustering gene expression data in SQL using locally adaptive metrics, Proceedings of the 8th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery, June 13-13, 2003, San Diego, California [doi>10.1145/882082.882091]
• 12: Sunita Sarawagi , Shiby Thomas , Rakesh Agrawal, Integrating association rule mining with relational database systems: alternatives and implications, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.343-354, June 01-04, 1998, Seattle, Washington, United States
• 13: Kai-Uwe Sattler , Oliver Dunemann, SQL database primitives for decision tree classifiers, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502650]
• 14: 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:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Languages

Keywords:
K-means, SQL, clustering