PQR*TDBSCAN改进算法

摘要:DBSCAN是基于密度的聚类算法的一个典型代表。但是DBSCAN算法在处理大规模数据库时,存在很大欠缺。PQR*TDBSCAN是针对DBSCAN算法内存使用过大、I/O消耗过多等方面提出的,但是在实际应用中发现存在异常挂死的可能。本文针对PQR*TDBSCAN的缺陷进行了改进。测试表明,本算法在处理海量数据过程中降低了DBSCAN对时间和空间的需求。

关键词:DBSCAN;数据分区;QR*树;并行计算

中图分类号:TP311文献标识码:A 文章编号:1009-3044(2010)05-1035-03

AN Improve Algorithm based PQR*TDBSCAN

WANG Hong, XU Fan, CUI Hong-jing, XU Hui

(Computer College.,Shandong Xiehe Vocational and Technical College, Jinan 250107, China)

Abstract: DBSCAN algorithm is an outstanding representative of density based on clustering algorithms. However, there are some defects when dealing with large-scale database. Aiming at requiring large volume of memory support and needing a lot of I/O costs, a PQR*TDBSCAN algorithm is presented. But actually there is the possibility of making the algorithm goes to the abnormal status. In this paper, a PQR*TDBSCAN improve algorithm is presented. Experimental results show that the new algorithm is superior to the original DBSCAN in efficiency.

Key words: DBSCAN; data-partitioning; QR*-tree; parallel computing

随着信息技术的高速发展,数据库应用的规模、范围和深度的不断扩大,导致积累了大量的数据,而这些激增的数据后面隐藏着许多重要的信息,因此人们希望能够对其进行更高层次的分析,以便更好地利用这些数据。日前的数据库系统可以高效、方便地实现数据的录入、查询、统计等功能,但是在发现数据中存在的各种关系和规则方面还是比较薄弱。聚类(clustering)是数据挖掘领域中的一个重要课题。它将数据库中的数据划分成具有一定意义的子类,使得不同子类中的数据尽可能相异而同一子类中的数据尽可能相同。迄今为止,人们提出了许多数据聚类的算法,像CLARANS,BIRCH,DBSCAN,CURE,STING,CLIQUE和Wavecluster等等。所有这些算法都试图解决大规模数据库的数据聚类问题。

基于数据分区、QR*-树的并行DBSCAN算法PQR*TDBSCAN,即根据数据的空间分布特性,将整个数据空间划分为多个较小的分区,然后对这些局部分区使用QR*-树建立空间索引,再进行聚类,最后将各局部聚类进行合并。但是该算法在实际应用过程中针对某一类数据库无法寻找找到分类方法时会进入到异常挂死的状态,本文针对PQR*TDBSCAN算法的这个问题提出了PQR*TDBSCAN改进算法。经过实际应用在遇到异常挂死的情况下程序在进行了m次比较后就会停止,防止程序挂死,同时在使用不同分区时使用不同的Eps,可以达到更好的聚类效果,但是该程序的效率与PQR*TDBSCAN基本相同。

1 DBSCAN 及 PQR*TDBSCAN算法模型

Ester Martin 等人提出的 DBSCAN 算法是一种基于密度的空间数据聚类方法, DBSCAN算法采用了一种查找密度可达对象的方法进行聚类分析。DBSCAN算法的正确性由下述事实保证:一个簇与由簇中任意核心对象密度可达的所有对象构成的集合O是等价的。DBSCAN算法采用迭代查找的方法。通过迭代查找所有直接密度可达的对象。找到各个簇所包含的所有密度可达的对象。

PQR*TDBSCAN算法思想是:根据数据库在某一维的分布特性,将整个数据库划分为若干个交集为空的局部区域;然后将每个局部数据库分别送入一个处理单元中,以每个处理单元为基础建立QR*-树,用基于QR*-树的DBSCAN算法进行聚类(种子点的选取过程中把与核心点的距离在0.6Eps到Eps范围内的点作为种子点);最后将所得到的聚类结果按照合并规则进行合并。PQR*TDBSCAN的算法具体描述是:

对于一个给定数据库D和MinPts、参数Eps(由k-dist 图得到),D中任意元素E有m维(E1,E2,…,Em),把D分成n个数据量大致相同的分区,步骤如下:

1) 取任意整数i(1≤i≤m),把数据库D投影到第i维上,即任意E∈D,EEi,则数据库D映射为一个一维数据集Di,即Di={Ei|E(E1,E2,…Em)∈D};

2) 令A,B分别为数据集Di的下限和上限,则数据集分布在区间[A,B]内;

3) 找到数列a0,a1,…,an,满足: A=a0

4) 如果分区结果满足步骤(3),则转到步骤(6);

5) 如果分区结果不满足步骤(3),则转到步骤(1);

6) 把分区结果进行简单的冗余处理, 即把步骤(3)的分区区间修改为:[a0,a1+Eps],[a1-Eps,a2+Eps],…,[ai-Eps,ai+1+Eps],…,[an-1-Eps,an],(i=1,2,…,n-2)。 为了阐述方便,将修改后的分区定名为C1,C2,…,Cn ;

7) 把Ci发送到第i个处理机内存中,(i=1,2,…,n);

8) 每一个处理机节点用基于QR*-树DBSCAN算法对本地数据进行聚类(以第i个分区为例):

①对于给定的分区Ci构建QR*-树;

②)初始化每个点为没有处理过的、初始化种子点队列(seeds)为空、初始化结果集(results)为空;

③定义第一个簇的类标签(ID)为1;

④取得分区Ci第一个点进行聚类;

⑤对在步骤I中建立好的QR*-树,进行点的区域查询,并且返回区域查询的结果点数;

⑥根据MinPts判断这个点是否是核心点,如果不是核心点就先记为噪声点(Noise);如果是核心点则将所有的点标记上当前的ID,然后从与核心点的距离在0.6Eps到Eps范围内的点集(Fseeds)中找出下一个点再进行步骤V,将已经处理过的点从Fseeds中删除,直到Fseeds为空;

⑦取得分区Ci的下一个点进行聚类,并将类标签(ID)增加1,直到取道Ci分区的所有点;

⑧基于QR*-树DBSCAN算法结束。

9) 聚类合并,对于处理机i(1≤i≤n-1):把Ci内数据的聚类信息发送到第i+1个处理机,与Ci+1内数据的聚类信息进行比较,如果某点z分别属于类1和类2,若z至少有一次为核心对象,则类1和类2合并为一个类;如果某点z在类1、2中都是边界点,则z可以属于类1或类2,但类1和类2不能合并;如果z有一次属于类1,而另一次是噪声点,则z属于类1;如果z点两次都为噪声点,z在全局聚类中就是噪音点;

10) 算法结束。

2 PQR*TDBSCAN改进算法

2.1 算法思想

PQR*TDBSCAN改进算法思想是:根据数据库在某一维的分布特性,将整个数据库划分为若干个交集为空的局部区域,如果在进行m次的寻找划分方法的过程中仍然没有找到,程序停止运行;然后将每个局部数据库分别送入一个处理单元中,以每个处理单元为基础建立QR*-树,用基于QR*-树的DBSCAN算法进行聚类,同时每个聚类使用自己的Eps(种子点的选取过程中把与核心点的距离在0.6Eps到Eps范围内的点作为种子点);最后将所得到的聚类结果按照合并规则进行合并。

2.2 算法描述

对于一个给定数据库D和MinPts、参数Eps(由k-dist 图得到),D中任意元素E有m维(E1,E2,…,Em),把D分成n个数据量大致相同的分区,步骤如下:

1) 取任意整数i(1≤i≤m),把数据库D投影到第i维上,即任意E∈D,EEi,则数据库D映射为一个一维数据集Di,即Di={Ei|E(E1,E2,…,Em)∈D};在投影过程中应用数据集的分区算法Partition算法进行数据集的划分;取一变量tmp,赋初始值为m;

2)令A,B分别为数据集Di的下限和上限,则数据集Di分布在区间[A,B]内;

3)找到数列a0,a1,…,an,满足:

A=a0

4)如果分区结果满足步骤3),则转到步骤6);

5)如果分区结果不满足步骤3)且tmp>1,则tmp=tmp-1,转到步骤1);如果分区结果不满足步骤3)且tmp≤1,则转到步骤10);

6)把分区结果进行简单的冗余处理,即把步骤(3)的分区区间修改为:[a0,a1+Eps],[a1-Eps,a2+Eps],…,[ai-Eps,ai+1+Eps],…,[an-1-Eps,an],(i=2,3,…,n-2)。为了阐述方便,将修改后的分区分别定名为C1,C2,…,C i+1,…,Cn;

7)把Ci发送到第i个处理机内存中,(i=1,2,…,n);

8)每一个处理机结点用基于QR*树DBSCAN算法对本地数据进行聚类(以第i个分区为例):

①对于给定的分区Ci构建QR*树;

②对于给定的分区Ci计算k-dist图,得到Epsi;

③初始化每个点为没有处理过的、初始化种子点队列(seeds)为空、初始化结果集(results)为空;

④定义第一个簇的类标签(ID)为1;

⑤取得分区Ci第一个点进行聚类;

⑥对在步骤I中建立好的QR*树,进行点的区域查询,并且返回区域查询的结果点数;

⑦根据MinPts判断这个点是否是核心点,如果不是核心点就先记为噪声点(Noise);如果是核心点则将所有的点标记上当前的ID,然后从与核心点的距离在0.6Epsi到Epsi范围内的点集(Fseeds)中找出下一个点再进行步骤(5),将已经处理过的点从Fseeds中删除,直到Fseeds为空;

⑧取得分区Ci的下一个点进行聚类,并将类标签(ID)增加1,直到取到Ci分区的所有点;

⑨基于QR*树DBSCAN算法结束。

9)聚类合并,对于处理机i(1≤i≤n-1):把Ci内数据的聚类信息发送到第i+1个处理机,与Ci+1内数据的聚类信息进行比较,如果某点z分别属于类Ci和类Ci+1,且在Ci、Ci+1中均为核心点,则类Ci和类Ci+1合并为一个类;某点z分别属于类Ci和类Ci+1,且一次为核心点,而另一次为边界点,则类Ci和类Ci+1合并为一个类;如果某点z在类Ci、Ci+1中都是边界点,则z可以属于类Ci或类Ci+1,但是类Ci和类Ci+1不能合并;如果z有一次属于类Ci,而另一次是噪声点,则z属于类Ci;如果z点两次都为噪声点,z在全局聚类中就是噪声点;

10)算法结束。

3性能评估

测试系统用JAVA语言开发。实验的硬件环境是50台 Pentium4 3.0G CPU,1024M内存、160G硬盘,软件环境是windows XP Sp2操作系统、Jbuilder8集成开发环境。同时,系统使用SQL Server 2000作为数据库,使用“SQL Server 2000 Driver for JDBC”作为数据库驱动程序。

首先要验证的是PQR*TDBSCAN改进算法在改进聚类质量上的优势。本文在评估聚类质量方面与周水庚的PDBSCAN相比较,测试例子如图1,比较结果如表1。从表1中可以看出PQR*TDBSCAN改进算法在聚类质量上要优于DBSCAN算法,聚类的质量与PDBSCAN相同,即在聚类质量上PQR*TDBSCAN改进算法与PDBSCAN等价。

接下来要对PQR*TDBSCAN改进算法的时间性能进行评估。图2为DBSCAN、PDBSCAN、PQR*TDBSCAN和PQR*TDBSCAN改进算法的一组测试结果。由图2可以看出PQR*TDBSCAN改进算法的时间效率比较高,并且当数据量增加的时候他的增幅比较小,可以得出PQR*TDBSCAN改进算法要优于PDBSCAN算法和DBSCAN算法。

5 结束语

本算法与前述提到的DBSCAN的改进算法相比较,可以看出本算法的优势在于以下几个方面:

1) 缓解了串行DBSCAN算法因数据规模过大内存需求紧张局面;

2) 通过使用多处理器、多个Eps、QR*-树作为空间索引结构,最大化提高了算法的运算速度并改善了聚类质量;

3) 通过使用环形区域种子点的查找,使要接受查询的种子点减少,在不改变聚类质量的情况下,提高了算法的运算速度。

但是本算法存在的主要缺点是对于增量式算法的支持力度不够,对于这方面的改进将是接下来研究的主要方向。

参考文献:

[1] 张健沛,许慧,杨静,崔洪晶.基于数据分区、QR~*-树的并行DBSCAN算法[A].2006北京地区高校研究生学术交流会――通信与信息技术会议论文集(下),2006.

[2] Ester M, et al. A density-based algorithm for discovering clusters in large spatial databases with noise. In: Proc of 2nd Int'l Conf on Knowledge Discovering in Databases and Data Mining (KDD-96). Portland: AAAI Press, 1996

[3] ZHOU Shui-Geng, ZHOU Ao-Ying, and CAO Jin. A Data-Partitioning-Based DBSCAN Algorithm [J]. Journal of Computer Research&Development, 2000, (10):1153-1159.

[4] 邱建华,唐学兵,黄华国.一种基于四叉树和R*-树的索引结构--QR*-树[J].计算机应用,2003,Vol.23, No.8: 124-126,152.

[5] LUAN Li-hua, JI Gen-lin. Fast clustering algorithm based on Quad-tree [J]. Computer Applications,2005,Vol.25,No.5:1001-1003.

[6] QIAN WN, ZHOU AY. Analyzing Popular Clustering Algorithms from Different Viewpoints [J].Journal of Software, 2002,13(8):1382-1394.