基于關系數據庫管理系統的K—means聚類算法

金微等

摘 要：基于關系型數據庫管理系統（DBMS）的數據挖掘算法對數據庫程序員來說是一個很重要的問題。這里介紹了利用SQL實現的基于關系數據庫管理系統的K-means聚類算法，將簡單的K-means計算轉化為SQL。實驗證明，提出的K-means聚類算法可以對大型數據集進行聚類。將K-means算法分別用SQL和C++實現，比較相關的速度和可伸縮性，并且研究了在DBMS外輸出數據集的時間。實驗表明，SQL對于小型數據集還是很有效的，但對于大型數據集效率較低，而輸出次數對于C++成為了一個瓶頸。

關鍵詞：聚類，K-means；SQL；關系數據庫管理系統

中圖分類號：TP391.41文獻標識碼：A文章編號：2095-7394（2015）04-0026-06

0 引言

基于關系數據庫管理系統（DBMS）的K-means聚類算法是一個重要的和具有挑戰性的問題[1-2]。在本文中，專注于使用SQL執行基于關系數據庫管理系統的K-means聚類算法，SQL是現今在關系型數據庫中的標準語言。聚類算法[3-4]即是將數據集分割成幾個組，使分在同一組得個體盡量接近，不在同一組的個體盡量遠離。對于提高K-means算法的速度和質量有研究[5-7]，但將它集成到關系數據庫中卻沒有得到足夠關注。

使用SQL執行基于關系數據庫管理系統的K-means聚類算法有許多優勢。在任何關系數據庫管理系統SQL都是可用的。SQL使應用程序程序員從DBMS的內部機制中分離出來。許多數據集都是存儲在關系數據庫中的。嘗試數據點和維數的不同子集會變得更靈活，更快，而且一般來說，在DBMS內部使用SQL查詢比在數據庫外部使用其他查詢工具更加容易。沒有DBMS的支持，管理大型數據集會是一個艱巨的任務。在大多數情況下，空間管理、容錯、安全訪問、并發性控制等，是由DBMS自動管理的。雖然在關系數據庫外部，對一個龐大的數據集進行有效的聚類也是可行的，但將其導出到一個工作站所花費的時間會需要很長。在大多數情況下，聚類結果需要聯系其他在數據倉庫的報表才能得出結果，或者這些結果將會作為其他數據挖掘任務的輸入。所以在關系數據庫內部對數據集進行聚類能夠解決這些問題。然而用SQL來執行聚類算法顯現出一個明顯的缺點，SQL語言沒有高級程序語言，像C++那么有效和靈活。SQL沒有提供很多數組和函數，很多計算如果用SQL表達的話會很復雜或者不可能。SQL查詢需要引入更高級的程序語言，比如C來訪問文件系統。許多存儲器和磁盤訪問優化只能被查詢優化器控制，而不是數據庫應用程序員。以上所提出的缺點將會在本文提出的K-means算法中得到解決。

1 定義

K-means的輸入是一個數據集Y，包含d維的n個點，Y={y1，y2，…，yn}，期望的聚類數目是ki，每個點yi都是d*1的列向量，K-means算法就是找到這樣一個包含k個中心點的集合，使每個點到各自中心的距離的平方和最短。輸出為三個矩陣，W，C，R，矩陣C和R都是d*k，W是k*1的。貫穿全文，有三個小標被用到指數矩陣中：i=1，2，….n，j=1，2，…k，l=1，2，…，d。矩陣和下標的具體描述見表1和表2。為了表示C或R中的任一列，我們用j下標（比如Cj，Rj），Cj可以理解為包含在第j個類中的d維向量，每一維有各自的每平方半徑，是由Rj提供的。Cj是以列的形式表示第j個聚類中心，CTj是以行的形式表示第j個聚類中心。X1，X2，…，Xk表示數據集Y的k個數據子集，其中Xj∩Xj′=，j≠j′。K-means使用歐幾里德找到距離每個輸入點最近的中心點。每個輸入點yi到其聚類中心Cj的平均歐幾里德距離可以表示為：

江蘇理工學院學報第21卷

這里yi∈Xj。

2 用SQL執行K-means算法

至于如何在關系數據庫管理系統中執行K-means，最后自動生成SQL代碼，這是通過選定參數d的輸入表格Y與參數k，k為期望的聚類個數，這在第二節中已經定義。SQL代碼生成器動態創建SQL語句，通過不斷地迭代監測聚類的好壞直至停止。SQL對于特定的數據庫管理系統供應商有不同的擴展，但是我們使用標準SQL，這樣我們的方案可以用在任何關系數據庫中。

2.1 一般定義

從執行性能觀點出發，在我們提出的算法背后有很多重要的定義。第一個是連接表時基于散列的機制。兩張表每張都有n行，相同的主鍵，以時間復雜度O（n）進行連接。每行可以基于主鍵以時間復雜度O（l）進行查詢。因此，如果不同的DBMS沒有提供基于散列的索引，連接兩張表的時間要比O（n）長。一般來說，人們認為n越大，d和k就相對較小。

2.2 K-means基礎構架

用SQL來執行K-means算法最基本的方案為：

（1）安裝：創建、索引和填充表格，從Y中隨機初始化C和k

（2）重復E和M步驟，直至K-means算法收斂，當q（l-1）（C）-ql（C）≤∈（3）

E：計算每個數據點yi的聚類k，找到該點最近的中心Cj，然后更新充分的數據。

M：更新W、C、R，更新模板表格沿著K-means算法的進程。

2.3 K-means的執行

在這一節中主要描述了K-means算法的特性，并且用SQL來實現此算法。

3.3.1 創建、索引和填充表格

接下來，討論表格的定義、索引，寫出有效的SQL代碼來執行K-means算法。通常，省略了數據定義語言（DDL）的申明和刪除語句使闡述更加簡潔。這樣，大多數SQL代碼包含了數據操作語言（DML）。表格中主關鍵字這一列是有下劃線的。為了有效的連接訪問，這些表格是以主關鍵字為索引的。在SQL中下標i，j，l（表格2）被定義為整形列，數據集Y中數據點的維數d為數值型，W、C、R的矩陣入口為浮點型。在每個INSERT語句之前，都假設有“DELETE FROM……ALL；”語句，使在執行插入語句之前表格為空。

正如第2節中介紹的，輸入數據集有d維。實際上，輸入的表可能要多于d列。在沒有特殊情況下，我們假設定義為Y（Y1，Y2，…，Yd），i為關鍵字。SQL實現需要構建縮減版本映射所需的維列。這促使生成下面的“橫向”表，有d+1列：YH（i，Y1，Y2，…Yd），i是主鍵。第一列是對每個數據點的下標i，YH是d維的列表。這個表節省了輸入輸出訪問時間，在算法執行過程中會掃描多次。總之，不保證存在i，因為Y的主鍵不止一列，或者可能根本不存在，因為Y是聚類的結果。在算法執行過程中，用程序語言，如C++或者JAVA，點識別是不重要的，因為Y是被順序訪問的，而在關系數據庫中，這就很重要。因此，這就有必要自動生成i，保證對于每個數據點yi都是唯一的標識。以下語句顯示了如何在數據集Y上掃描來獲取i。

INSERT INTO YH

SELECT sum（1）OVER（）ASi，Y1；Y2；……；Yd

FROM Y；

Sum函數對于每個數據點疊加1，最后計算出累加和。這一函數是ANSI OLAP標準中的一部分。Over語句是累計越來越多的窗口行來計算和。點的標識i可以由其他SQL函數來獲取，并且對于每個數據點這是唯一的一個標識。用隨機的數字來獲取標識不是一個好的方法，因為很容易重復，特別是對于大型數據庫而言，聚類結果保存在W、C、R中的。這就促使每一個矩陣都建立一張表格，分別是W（j，w），C（l，j，val），R（l，j，val），分別有k、dk和dk行。

矩陣W、C、R和Y相比規模比較小，而且沒有索引也能連續訪問。既然K-means算法在E步驟中使用C來計算類成員，所以只有表C才需要索引。但為了統一起來，表C和R都被l和j（關鍵字）索引，W僅被下標j索引。

上面介紹的表YH對于使用SQL的sum（）函數計算距離是不太合適的，因此YH轉換成d行表格，每一維表示成一行，即生成表YV（i，l，val），由下面d條語句組成：

INSERT INTO YV SELECT i，1；Y1 FROM YH；

……

INSERT INTO YV SELECT i，d；Yd FROM YH；

最后，定義一個稱之為模板的表格，追蹤K-means算法通過不斷迭代觀察公式（2）的均方差，測試收斂性、迭代次數，以及矩陣規模比如n（避免重復掃描Y），d（維數），k（聚類個數）。在K-means算法每次迭代后都記錄下日期/時間。

3.3.2 初始化

大多數K-means算法變量使用k個隨機從Y中選擇的數據點。因為W和R都是輸出，它們不需要初始化，既然如此，表YH對于建立C的橫向版本是合適的。表CH（j，Y1，Y2，…，Yd）保存了k個從YH中隨機選擇的數據點。隨機的數據點可以從1到n之間的任意整數。一旦CH表被填充，可以用來對C初始化，通過如下的dk條語句（J和L代表SQL代碼發生器中的變量，J=1….K，L=1….d）：

3 比較SQL與C++

將SQL與C++進行比較來了解用SQL的算法執行需要多少開銷，分析了在DBMS外輸出數據集的時間，然后從性能角度來了解什么時候應該在DBMS外對數據進行聚類，什么時候不可以。重點研究K-means算法在具有相似特性計算機上迭代一次的性能。

比較輸出數據集的時間和迭代以此所需的時間。這里強調，對于一個數據集輸出操作只執行一次，而K-means算法可以迭代多次。在數據庫管理系統DBMS和工作站之間的接口是ODBC（開發數據庫互聯），運行提交查詢和輸出表格。使用ODBC3.3輸出數據集作為文本文件。表3顯示了對于SQL和C++執行一次所需的時間，同時也顯示了使用ODBC輸出數據集所需的時間。對于小規模數據集，因為C++要比SQL快很多，所以在DBMS外，考慮到輸出數據集的時間，用C++更經濟些。但隨著n的增加，不管對C++或是SQL，與每次迭代時間相比，輸出時間變得更長。當n=1000k時，輸出時間將會是20倍。結果顯示，對大型數據庫進行聚類，SQL和C++表現類似，都不是很理想。

對于大規模數據集而言，SQL的執行速度比C++要稍微好些，但對于小規模數據集，C++的表現要好很多。但是在典型環境中，DBMS服務器比工作站快很多，而且可以存儲更多數據。因此，為了追求完整性，將工作站性能與一個典型的DBMS服務器進行比較，在接下來的實驗中，DBMS服務器還是上面試驗中用到的（4CPUs，800 MHz，40 AMPs），工作站（1CUP，1.2GHz）。

表4顯示了，數據集（d=8，k=8）n從1M到16M變化，每次迭代所需時間。實驗證明，SQL在每次實驗中單從執行性能考慮，都是最好的選擇，如果考慮輸出時間，選擇SQL也是顯而易見的。對于大規模數據集，在DBMS外部對數據集進行聚類是不合理的，因為輸出時間接近于一天。

4 結語

將SQL和C++在類似的計算機上執行性能進行比較，在大規模數據集上，SQL的效率與C++相類似，但對于小規模數據，就要慢很多。另外，將輸出時間和每次迭代所需時間進行比較，在DBMS外部聚類，輸出大數據集變為瓶頸，這時SQL將會是一個更有效的選擇。在數據挖掘領域，K-means算法適用范圍比較廣。結合本文提出的概念，用戶自定義函數和有效索引，大規模數據可以經過一次掃描進行聚類。 某些計算確保在DBMS內部可以通過定義SQL元素，有更大的適用性。這樣的結構將包括歐幾里德距離計算，旋轉一個表使每一行都得到一個值，另一個找到最近的類。

參考文獻：

[1]Aggarwal C，Yu P.Finding Generalized Projected Clusters in High Dimensional Spaces[J]. Proc.ACM SIGMOD Conf，2000，2（10）：70-81.

[2]Sarawagi S，Thomas S，Agrawal R.Integrating Mining with Relational Databases：Alternatives and Implications[J]. Proc.ACM SIGMOD Conf.，1998，28（2）：343-354.

[3]Fayyad U，Piatetsky-Shapiro G，Smyth P.The KDD Process for Extracting Useful Knowledge from Volumes of Data[J].Comm.ACM，1996，39（11）：27-34.

[4]Duda R，Hart P.Pattern Classification and Scene Analysis[M].[S.1.]：John Wiley and Sons，1973.

[5]Zhang T，Ramakrishnan R，Livny M.BIRCH：An Efficient Data Clustering Method for Very Large Databases[J].Proc.ACM SIGMOD Conf.，1996，39（11）：103-114.

[6]Pelleg D，Moore A.Accelerating Exact K-Means Algorithms with Geometric Reasoning[J].Proc.ACM Intl Conf.Knowledge Discovery and Data Mining，1999，1（4）：277-281.

[7]Fritzke B.The LBG-U Method for Vector Quantization—An Improvement over LBG Inspired from Neural Networks[J].Neural Processing Letters，1997，5（1）：35-45.

K-means Clustering Algorithm with a Relational DBMS

JIN Wei，LV Ping，ZHU Cui-qing，WANG Ke-feng

（School of Computer Engineering，Jiangsu University of Technology，Changzhou 213001，China）

Abstract：Data mining algorithms with a relational DBMS is an important problem for database programmers.We introduce SQL implementations of K-means clustering algorithm to integrate it with a relational DBMS，translate K-means computations into SQL.We experimentally show the proposed K-means can cluster large data sets.We compare K-means implementations in SQL and C++ with respect to speed and scalability and we also study the time to export data sets outside of the DBMS.Experiments show that SQL overhead is significant for small data sets，but relatively low for large data sets，whereas export times become a bottleneck for C++.

Key words：clustering；K-means；SQL；relational DBMS

責任編輯 祁秀春