金微等

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

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

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

0 引言

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

使用SQL執(zhí)行基于關(guān)系數(shù)據(jù)庫(kù)管理系統(tǒng)的K-means聚類算法有許多優(yōu)勢(shì)。在任何關(guān)系數(shù)據(jù)庫(kù)管理系統(tǒng)SQL都是可用的。SQL使應(yīng)用程序程序員從DBMS的內(nèi)部機(jī)制中分離出來(lái)。許多數(shù)據(jù)集都是存儲(chǔ)在關(guān)系數(shù)據(jù)庫(kù)中的。嘗試數(shù)據(jù)點(diǎn)和維數(shù)的不同子集會(huì)變得更靈活，更快，而且一般來(lái)說(shuō)，在DBMS內(nèi)部使用SQL查詢比在數(shù)據(jù)庫(kù)外部使用其他查詢工具更加容易。沒(méi)有DBMS的支持，管理大型數(shù)據(jù)集會(huì)是一個(gè)艱巨的任務(wù)。在大多數(shù)情況下，空間管理、容錯(cuò)、安全訪問(wèn)、并發(fā)性控制等，是由DBMS自動(dòng)管理的。雖然在關(guān)系數(shù)據(jù)庫(kù)外部，對(duì)一個(gè)龐大的數(shù)據(jù)集進(jìn)行有效的聚類也是可行的，但將其導(dǎo)出到一個(gè)工作站所花費(fèi)的時(shí)間會(huì)需要很長(zhǎng)。在大多數(shù)情況下，聚類結(jié)果需要聯(lián)系其他在數(shù)據(jù)倉(cāng)庫(kù)的報(bào)表才能得出結(jié)果，或者這些結(jié)果將會(huì)作為其他數(shù)據(jù)挖掘任務(wù)的輸入。所以在關(guān)系數(shù)據(jù)庫(kù)內(nèi)部對(duì)數(shù)據(jù)集進(jìn)行聚類能夠解決這些問(wèn)題。然而用SQL來(lái)執(zhí)行聚類算法顯現(xiàn)出一個(gè)明顯的缺點(diǎn)，SQL語(yǔ)言沒(méi)有高級(jí)程序語(yǔ)言，像C++那么有效和靈活。SQL沒(méi)有提供很多數(shù)組和函數(shù)，很多計(jì)算如果用SQL表達(dá)的話會(huì)很復(fù)雜或者不可能。SQL查詢需要引入更高級(jí)的程序語(yǔ)言，比如C來(lái)訪問(wèn)文件系統(tǒng)。許多存儲(chǔ)器和磁盤(pán)訪問(wèn)優(yōu)化只能被查詢優(yōu)化器控制，而不是數(shù)據(jù)庫(kù)應(yīng)用程序員。以上所提出的缺點(diǎn)將會(huì)在本文提出的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)的具體描述見(jiàn)表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ù)庫(kù)管理系統(tǒng)中執(zhí)行K-means，最后自動(dòng)生成SQL代碼，這是通過(guò)選定參數(shù)d的輸入表格Y與參數(shù)k，k為期望的聚類個(gè)數(shù)，這在第二節(jié)中已經(jīng)定義。SQL代碼生成器動(dòng)態(tài)創(chuàng)建SQL語(yǔ)句，通過(guò)不斷地迭代監(jiān)測(cè)聚類的好壞直至停止。SQL對(duì)于特定的數(shù)據(jù)庫(kù)管理系統(tǒng)供應(yīng)商有不同的擴(kuò)展，但是我們使用標(biāo)準(zhǔn)SQL，這樣我們的方案可以用在任何關(guān)系數(shù)據(jù)庫(kù)中。

2.1 一般定義

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

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

用SQL來(lái)執(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來(lái)實(shí)現(xiàn)此算法。

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

接下來(lái)，討論表格的定義、索引，寫(xiě)出有效的SQL代碼來(lái)執(zhí)行K-means算法。通常，省略了數(shù)據(jù)定義語(yǔ)言（DDL）的申明和刪除語(yǔ)句使闡述更加簡(jiǎn)潔。這樣，大多數(shù)SQL代碼包含了數(shù)據(jù)操作語(yǔ)言（DML）。表格中主關(guān)鍵字這一列是有下劃線的。為了有效的連接訪問(wè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語(yǔ)句之前，都假設(shè)有“DELETE FROM……ALL；”語(yǔ)句，使在執(zhí)行插入語(yǔ)句之前表格為空。

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

INSERT INTO YH

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

FROM Y；

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

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

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

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

……

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

最后，定義一個(gè)稱之為模板的表格，追蹤K-means算法通過(guò)不斷迭代觀察公式（2）的均方差，測(cè)試收斂性、迭代次數(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對(duì)于建立C的橫向版本是合適的。表CH（j，Y1，Y2，…，Yd）保存了k個(gè)從YH中隨機(jī)選擇的數(shù)據(jù)點(diǎn)。隨機(jī)的數(shù)據(jù)點(diǎn)可以從1到n之間的任意整數(shù)。一旦CH表被填充，可以用來(lái)對(duì)C初始化，通過(guò)如下的dk條語(yǔ)句（J和L代表SQL代碼發(fā)生器中的變量，J=1….K，L=1….d）：

3 比較SQL與C++

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

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

對(duì)于大規(guī)模數(shù)據(jù)集而言，SQL的執(zhí)行速度比C++要稍微好些，但對(duì)于小規(guī)模數(shù)據(jù)集，C++的表現(xiàn)要好很多。但是在典型環(huán)境中，DBMS服務(wù)器比工作站快很多，而且可以存儲(chǔ)更多數(shù)據(jù)。因此，為了追求完整性，將工作站性能與一個(gè)典型的DBMS服務(wù)器進(jìn)行比較，在接下來(lái)的實(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也是顯而易見(jiàn)的。對(duì)于大規(guī)模數(shù)據(jù)集，在DBMS外部對(duì)數(shù)據(jù)集進(jìn)行聚類是不合理的，因?yàn)檩敵鰰r(shí)間接近于一天。

4 結(jié)語(yǔ)

將SQL和C++在類似的計(jì)算機(jī)上執(zhí)行性能進(jìn)行比較，在大規(guī)模數(shù)據(jù)集上，SQL的效率與C++相類似，但對(duì)于小規(guī)模數(shù)據(jù)，就要慢很多。另外，將輸出時(shí)間和每次迭代所需時(shí)間進(jìn)行比較，在DBMS外部聚類，輸出大數(shù)據(jù)集變?yōu)槠款i，這時(shí)SQL將會(huì)是一個(gè)更有效的選擇。在數(shù)據(jù)挖掘領(lǐng)域，K-means算法適用范圍比較廣。結(jié)合本文提出的概念，用戶自定義函數(shù)和有效索引，大規(guī)模數(shù)據(jù)可以經(jīng)過(guò)一次掃描進(jìn)行聚類。 某些計(jì)算確保在DBMS內(nèi)部可以通過(guò)定義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é)任編輯 祁秀春