基于關(guān)系數(shù)據(jù)庫管理系統(tǒng)的K—means聚類算法

金微等

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

關(guān)鍵詞：聚類，K-means；SQL；關(guān)系數(shù)據(jù)庫管理系統(tǒng)

中圖分類號：TP391.41文獻(xiàn)標(biāo)識碼：A文章編號：2095-7394（2015）04-0026-06

0 引言

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

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

1 定義

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

江蘇理工學(xué)院學(xué)報(bào)第21卷

這里yi∈Xj。

2 用SQL執(zhí)行K-means算法

至于如何在關(guān)系數(shù)據(jù)庫管理系統(tǒng)中執(zhí)行K-means，最后自動生成SQL代碼，這是通過選定參數(shù)d的輸入表格Y與參數(shù)k，k為期望的聚類個(gè)數(shù)，這在第二節(jié)中已經(jīng)定義。SQL代碼生成器動態(tài)創(chuàng)建SQL語句，通過不斷地迭代監(jiān)測聚類的好壞直至停止。SQL對于特定的數(shù)據(jù)庫管理系統(tǒng)供應(yīng)商有不同的擴(kuò)展，但是我們使用標(biāo)準(zhǔn)SQL，這樣我們的方案可以用在任何關(guān)系數(shù)據(jù)庫中。

2.1 一般定義

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

2.2 K-means基礎(chǔ)構(gòu)架

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

（1）安裝：創(chuàng)建、索引和填充表格，從Y中隨機(jī)初始化C和k

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

E：計(jì)算每個(gè)數(shù)據(jù)點(diǎn)yi的聚類k，找到該點(diǎn)最近的中心Cj，然后更新充分的數(shù)據(jù)。

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

2.3 K-means的執(zhí)行

在這一節(jié)中主要描述了K-means算法的特性，并且用SQL來實(shí)現(xiàn)此算法。

3.3.1 創(chuàng)建、索引和填充表格

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

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

INSERT INTO YH

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

FROM Y；

Sum函數(shù)對于每個(gè)數(shù)據(jù)點(diǎn)疊加1，最后計(jì)算出累加和。這一函數(shù)是ANSI OLAP標(biāo)準(zhǔn)中的一部分。Over語句是累計(jì)越來越多的窗口行來計(jì)算和。點(diǎn)的標(biāo)識i可以由其他SQL函數(shù)來獲取，并且對于每個(gè)數(shù)據(jù)點(diǎn)這是唯一的一個(gè)標(biāo)識。用隨機(jī)的數(shù)字來獲取標(biāo)識不是一個(gè)好的方法，因?yàn)楹苋菀字貜?fù)，特別是對于大型數(shù)據(jù)庫而言，聚類結(jié)果保存在W、C、R中的。這就促使每一個(gè)矩陣都建立一張表格，分別是W（j，w），C（l，j，val），R（l，j，val），分別有k、dk和dk行。

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

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

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

……

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

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

3.3.2 初始化

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

3 比較SQL與C++

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

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

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

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

4 結(jié)語

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

參考文獻(xiàn)：

[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

責(zé)任編輯 祁秀春