基于密度的并行聚类算法

1、 8基于密度的并行聚类算法陈 敏 1,高学东 1,栾绍峻 1,郗玉平 2(1. 北京科技大学经济管理学院,北京 100083; 2. 北京信息职业技术学院汽车工程系,北京 100015摘 要:为满足大规模空间数据库的聚类需求,面向计算机集群,提出一种基于密度的并行聚类算法。该算法根据数据库分布特征进行数 据分区, 在每一个节点上对数据块并行聚类, 在主节点上合并聚类结果。 实验结果表明, 该算法的计算速度随着节点数的增多呈线性增加, 具有较好的延展性。关键词:并行聚类;计算机集群;数据库;延展性Parallel Clustering Algorithm Based on DensityCHEN

2、 Min1, GAO Xue-dong1, LUAN Shao-jun1, XI Yu-ping2(1. School of Economics and Management, University of Science and Technology Beijing, Beijing 100083; 2. Department of Automotive Engineering, Beijing Information Technology College, Beijing 100015【 Abstract 】 In order to meet the demands for large sc

3、ale databases clustering, this paper proposes a parallel clustering algorithm based on density for computer colony. This algorithm goes on data partition according to database distribution feature, processes data block parallel clustering on every node, merges clustering result on main node. Experim

4、ental result shows that computing speed of this algorithm is linear increment with number of node increasing, and it has better extensibility.【 Key words】 parallel clustering; computer colony; database; extensibility计 算 机 工 程 Computer Engineering第 36卷 第 11期Vol.36 No.11 2010年 6月June 2010·博士论文

5、83;文章编号:1000 3428(201011 0008 03文献标识码:A中图分类号:TP301.61 概述聚类分析是数据挖掘的主要任务之一,在很多领域有着广泛应用,如模式识别、图像处理和数据压缩等。随着信息 技术的高速发展,出现了越来越多如地理信息、卫星图像等 大规模空间数据库,对聚类算法提出更高要求:尽可能减少 先决知识或输入参数要求,发现任意形状的类,适用于大规 模数据库聚类等。文献 1提出一种面向空间数据库,基于密度的聚类算 法,其主要思想为:如果一个对象在半径为 Eps 的领域内包 含至少 MinPts 个对象,那么该区域是密集的。该算法基本满 足上述对于聚类算法的要求,理论上能

6、够处理大规模空间数 据库的聚类。为进一步提高计算速度及当空间数据库规模增大时算法 的延展性,本文提出一种基于密度的并行聚类算法。在计算 机集群中实现该算法,其原因是计算机集群理论上具有无限 扩容的能力,当面临巨型数据库时,可以通过将集群中的计 算节点增加到几百个甚至上千个来满足计算要求。本文算法 能合理划分数据库,由集群中的计算节点并行聚类,最后合 并聚类结果。2 基于密度的聚类算法给出文献 1算法的几个基本概念, 其中, DB 为数据库;Eps 和 MinPts 为给定阈值。定义 1(Eps 邻域 对于空间任意一个点 p ,其 Eps 领域 记作 ( , (, Eps N p q DB di

7、st p q Eps = 。定 义 2(核 心 点 如 果 一 个 点 的 Eps 邻 域 内 至 少 包 含MinPts 个点,则称其为核心点。定义 3(直接密度可达 若 q 是核心点, 且 p 在 q 的 Eps 邻 域内,则 p 从 q 直接密度可达。定义 4(密度可达 点 p 从点 q 密度可达,若存在 12, , , p p "n p ,其中, 1p q =; n p p =,且 1i p +从 i p 直接密度可达。定义 5(密度相连 若点 p 和点 q 是密度连接的,则存在 对象 o ,使 p 和 q 都从 o 密度可达。定义 6(类 数据库 DB 的非空集合 C 是一

8、个类,当且仅 当 C 满足以下条件:(1任意点 p , q ,若 p C ,且 q 从 p 密度可达,则 q C (最大性 ;(2任意点 p , q C ,则 p , q 密度连接 (连通性 。 定义 7(噪声 数据库 D 中不属于任何类的点为噪声。 文献 1算法思路如下:对数据库中任何一个点 p ,对其 进行区域查询, 判断是否是核心点, 如是, 则建立新类 C , p 及其邻域内的点均属于该类。 考察 C 中尚未被考察过的点 q , 若 q 是核心点,则将其领域内未属于任何一类的点追加到类C 。不断重复此过程,直到没有新的点可以追加为止。以同样程序寻找其他的类,不属于任何类的点为噪声。文献

9、 1算法 的复杂度为 2( O n ,其中, n 是对象的总数。为了提高聚类效 率,该算法采用空间数据库索引 R*-tree2实现区域搜索,使基金项目:国家自然科学基金资助项目“高维稀疏数据聚类研究” (70771007作者简介:陈 敏 (1976- , 女, 博士研究生, 主研方向:数据挖掘; 高学东,教授;栾绍峻,博士研究生;郗玉平,硕士 收稿日期:2010-01-10 E-mail :lynn.chenmin 9计算复杂度降为 (log O n n 。 3 基于密度的并行聚类算法3.1 算法思路问题描述:给定 d 维空间点集 12, , , n DB q q q =" 及计算机

10、集群 12, , , M PC P P P =" , 其中, , 1,2, , i P i M =" 为集群中的 计算节点,计算节点之间用网络相连。寻找数据库 DB 中基 于合适参数 Eps 和 MinPts 的类。本文算法思路如下:(1读 入 数 据 库 DB , 根 据 k -dist 图 确 定 参 数 Eps 和MinPts 。(2将数据库 DB 划分为 N 块, 12, , , N s s s " , i j s s =,i j , 1N i i DB s =,将数据块 i s , 1,2, , i N =" 分配到集群中的 M 个计算节点,其

11、中, N M ,当每个计算节点均有 2个 CPU 时,理想划分为 2N M =。注意:要根据数据库规模来 确定合适的集群规模,当数据库较小时,集群中的节点不宜 过多。(3计算机集群中的计算节点 12, , , M P P P " 对于自己分到 的数据块,利用文献 1算法聚类。(4合并各计算节点 i P 的计算结果,得到对整个数据库DB 的聚类结果,本文采用文献 3中的合并策略。3.2 参数确定在读入数据库后,需要确定参数 Eps 和 MinPts ,即领域 大小及领域内最小点数阈值。文献 1算法提到的邻域概念虽 然是任意形状的,不过通常都采用“圆”形邻域。事实上, 支持领域搜索的 R

12、*-tree的每个节点都对应一个外接矩形, 搜 索其实是针对这些矩形进行的。如果采用圆形的邻域,则需 要先在 R*-tree的矩形邻域内搜索, 再根据矩形与圆形的包含 关系来确定在圆形领域内的对象数目。这样的转换影响了搜 索的效率,所以,在本文算法中采用矩形搜索邻域,导致参 数的确定发生变化。在文献 1算法中, 可以将 MinPts 固定为 4,再确定 Eps 的大小。然而经过反复试验证明,在采用矩形 搜索邻域时,如果将 MinPts 固定为 4,在某些噪音干扰的情 况下,无法得出正确的聚类结果。如果将 MinPts 设定为 7, 再根据 k -dist 图来确定 Eps ,聚类结果会较好。实

13、验结果表 明,搜索速度与 MinPts 的值无关,而是由搜索的邻域范围, 即 Eps 确定。所以,将 MinPts 设定为 7不会降低搜索效率。 3.3 数据库划分在确定了参数后,需要划分数据库,划分的优劣对于计 算机集群环境中的并行计算来说是至关重要的,不仅影响到 并行算法的效率与延展性,而且对整个并行系统的负载平衡 也有着重要意义。 本文根据数据空间分布特征来划分数据库, 具体方法如下:首先扫描数据库,将数据库在每一个坐标轴 上进行投影,据此找到数据库在每一维上的分布特征,从而 对数据库进行合理划分,这是人机交互的过程。分割原数据库需要遵循 2个原则:(1依据空间分布特征进行数据块划分。寻

14、找能显示数 据分布特征的点,本文称为断点,之后从断点处进行区域 划分。(2划分数据块的多少要根据数据库大小及计算环境来 共同决定。当数据库较小或计算节点数目较少,均不宜将其 划分成过多的数据块,其原因是将消耗过多的合并成本。该数据库划分方法适应于任何维数的数据空间,为演示方便,以图 1所示的带有噪音的二维原数据库进行说明。 图 1 原数据库将图 1所示数据库投影至 X 轴、 Y 轴,投影结果见图 2。 图 2 数据库在 X 轴、 Y 轴上的投影结果假如实验环境仅有 2个计算节点 (4个 CPU ,那么根据 对数据库划分的 2个原则, 可在 X 轴上根据 A 点, 在 Y 轴上 根据 B 点将数

15、据库划分成 4块。若实验环境存在更多计算节 点,则可适当选取多个断点将数据库划分成更多块。 3.4 算法复杂度在完成数据库划分之后,每个计算节点将对自己分到的 数据块 i s , 1,2, , i N =" 采用文献 1算法分别聚类,在采用空 间索引 R*-tree的情况下, 如果忽略合并成本, 则对每一个数 据块聚类的时间复杂度为 (log i i O s s , 其中, i s 为数据块 i s 的点数, 即数据量。 本文算法总体的时间复杂度为 11(log O s s +22log log N N s s s s +" ,在数据库规模很大时,远小于文献 1算法的复杂度

16、 (log O n n ,而且 n 越大,差距越明显。4 实验实验所用设备为 3台笔记本电脑,其中主节点为一台采 用 Windows 操作系统、 Intel 1.73 GHz(双核 、 2.87 GB内存 的笔记本。另外, 2个计算节点为均为采用 Windows 操作系统、 Intel 2.0 GHz(双核 、 3 GB内存的笔记本;电脑之间由带宽为 100 Mb/s的局域网络连接;编程工具和运行环境为 JDK 1.5。 与建立 k -dist 图确定参数这个过程类似,数据分区是人机交 互的过程,作为预处理部分,没有纳入执行时间。4.1 加速性实验采用图 1所示数据库来进行测试,该数据库文件包

17、含 45 727个点,参数 Eps 和 MinPts 分别设定为 4, 7,本文算法 聚类结果如图 3所示。 10 图 3 本文算法聚类结果实验结果证明,本文算法的聚类结果是正确的,并且随 着计算节点的增多,几乎可以线性加速,如表 1所示。表 1 本文算法与文献 1算法计算效率比较算法 节点数执行时间 /s执行时间比 /(%聚类结果 /类文献 1算法 1 46.375 100 10 本文算法 2 22.953 49 10 本文算法3 16.93837104.2 关于数据库规模的延展性实验为测试本文算法的延展性,采用含有 5×104个点、 1×105个点、 1.5×

18、105个点、 2×105个点的 4个数据库进行实验。这 4个数据库点的分布形状基本相似,差别在于对象数目。在针对 4个数据库的实验中,参数 Eps 和 MinPts 均分别设定为3, 7,实验结果如图 4所示。 图 4 本文算法的延展性从图 4可以看出,随着数据库规模的增加, 3条线之间 的距离越远,本文算法的优势越明显。相对于文献 1算法, 本文算法在 3台机器上实现的计算时间增势很平缓。实验结 果表明,当数据库规模增大时,本文算法可通过适当增加计 算节点来达到高效聚类,具有良好的延展性。4.3 文献 1算法中参数对计算效率的影响文献 1提到当 MinPts 的值增加时, 执行时间

19、剧增, 然而 本文实验发现,在预先确定的 2个参数 Eps 和 MinPts 中,对计算速度有明显影响的是 Eps 而非 MinPts 。在图 1中, Eps 的测试值为 2, 3, 4; MinPts 的测试值为 4, 7, 10。当参数不正确时,显然无法得到正确的聚类结果, 这里的执行时间定义为文献 1算法执行完毕的时间,实验结 果如图 5所示。 图 5 文献 1算法的参数对计算效率影响从图 5可以看出,当 Eps =2, Eps =3, Eps =4时,虽然MinPts 值会变化,执行时间近似为 3条平行直线;当 Eps 固定时,执行时间几乎没有随 MinPts 值而变化。与此相反,当M

20、inPts 值固定时,采用不同的 Eps 值,可以看到计算时间分别为 3条平行线,有明显差距。因此,本文主要影响计算时间的参数为 Eps , MinPts 对计算时间影响很小。5 结束语本文提出一种面向计算机集群系统的基于密度的并行聚 类算法。实验结果表明,本文算法通过适当增加计算节点, 能加速计算速度,适用于大规模数据库的聚类分析;并且得 到影响文献 1算法效率的参数为 Eps ,而非 MinPts 。下一步 研究方向为:拟采用更先进方式划分数据库,以规避人机交 互的过程,使算法的可操作性、可使用性更强。参考文献1 Easter M, Kriegek H P, Sander J, et al. A Density-based Algorithmfor Discovering Clusters in Large DatabasesC/Proc. of the 2nd International Conference on Knowledge Discovery