论文部分内容阅读
摘 要：基于关系型数据库管理系统（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 Int’l 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
责任编辑 祁秀春
关键词：聚类，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 Int’l 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
责任编辑 祁秀春