DBSCAN聚类算法的研究与改进.pdf

第3 7 卷第1 期 中国矿业大学学报V 0 1 ．3 7N o ．1 2 0 0 8 年1 月 J o u r n a lo fC h i n aU n i v e r s i t yo fM i n i n g T e c h n o l o g yJ a n ．2 0 0 8 D B S C A N 聚类算法的研究与改进 冯少荣h2 ，肖文俊1 1 ．华南理工大学计算机科学与工程学院，广东广州 5 1 0 6 4 1 2 ．厦门大学信息科学与技术学院，福建厦f 13 6 1 0 0 5 摘要针对“基于密度的带有噪声的空间聚类” D B S C A N 算法存在的不足，提出“分而治之”和 高效的并行方法对D B S C A N 算法进行改进．通过对数据进行划分，利用“分而治之”思想减少全 局变量E p s 值的影响；利用并行处理方法和降维技术提高聚类效率，降低D B S C A N 算法对内存 的较高要求；采用增量式处理方式解决数据对象的增加和删除对聚类的影响．结果表明新方法 有效地解决了D B S C A N 算法存在的问题，其聚类效率和聚类效果明显优于传统D B S C A N 聚类 算法． 关键词聚类；D B S C A N ；划分；并行 中图分类号T P3 1 1 文献标识码A文章编号1 0 0 0 1 9 6 4 2 0 0 8 0 1 0 1 0 5 0 7 A nI m p r o v e dD B S C A NC l u s t e r i n gA l g o r i t h m F E N GS h a o r o n 9 1 ”，X I A OW e n ju n l 1 ．S c h o o lo fC o m p u t e rS c i e n c ea n dE n g i n e e r i n g S o u t hC h i n aU n i v e r s i t yo fT e c h n o l o g y ，G u a n g z h o u ， G u a n g d o n g5 1 0 6 4 1 ，C h i n a ； 2 ．C o l l e g eo fI n f o r m a t i o nS c i e n c ea n dT e c h n o l o g y ，X i a m e nU n i v e r s i t y ，X i a m e n ，F u j i a n g3 6 1 0 0 5 ，C h i n a A b s t r a c t A ni m p r o v e dd e n s i t yb a s e ds p a t i a lc l u s t e r i n go fa p p l i c a t i o n sw i t hn o i s e D B S C A N a l g o r i t h m ，w h i c hc a nc o n s i d e r a b l yi m p r o v ec l u s t e rq u a l i t y ，i sp r o p o s e d ．T h ea l g o r i t h mi sb a s e d o nt w oi d e a s d i v i d i n ga n dr u l i n g ，a n d ；h i g hp e r f o r m a n c ep a r a l l e lm e t h o d s ．T h ei d e ao fd i v i d i n ga n dr u l i n gw a su s e dt or e d u c et h ee f f e c to ft h eg l o b a lv a r i a b l eE p sb yd a t ap a r t i t i o n ．P a r a l l e lp r o c e s s i n gm e t h o d sa n dt h et e c h n i q u eo fr e d u c i n gd i m e n s i o n a l i t yw e r eu s e dt oi m p r o v et h e e f f i c i e n c yo fc l u s t e r i n ga n dt or e d u c et h el a r g em e m o r ys p a c er e q u i r e m e n t so ft h eD B S C A Na l g o r i t h m ．F i n a l l y ，a ni n c r e m e n t a lp r o c e s s i n gm e t h o dw a sa p p l i e dt od e t e r m i n et h ei n f l u e n c eo n c l u s t e r i n go fi n s e r t i n go rd e l e t i n gd a t ao b j e c t s ．T h er e s u l t ss h o wt h a ta ni m p l e m e n t a t i o no ft h e n e wm e t h o ds o l v e se x i s t i n gp r o b l e m st r e a t e db yt h eD B S C A Na l g o r i t h m B o t ht h ee f f i c i e n c y a n dt h ec l u s t e rq u a l i t ya r eb e t t e rt h a nf o rt h eo r i g i n a lD B S C A Na l g o r i t h m ．K e yw o r d s c l u s t e r i n g ；D B S C A N ；p a r t i t i o n ；p a r a l l e l K e yw o r d s c l u s t e r i n g ；D B S C A N ；p a r t i t i o n ；p a r a l l e l 数据挖掘技术目前已成为数据库技术的一个 研究热点，在许多领域得到广泛应用阻3 。．D B S C A N E 4 3 算法是聚类分析中基于密度的聚类算 法‘子6 | ，其基本思想是对于簇中的每一个点在其给 定的半径范围内都至少包含给定数目的点．该算法 将具有足够高密度的区域划分为一类，并可以在带 有“噪声” o u t l i e r s 的空间数据库中发现任意形状 的聚类，而且聚类速度快，可以作为增量聚类算 法吲的基础．但是，由于它直接对整个数据库进行 操作，聚类时使用了一个全局性的表征密度的参 收稿日期2 0 0 7 0 1 2 2 基金项目福建省自然科学基金项目 A 0 3 1 0 0 0 8 ；福建省高新技术研究开放计划重点项目 2 0 0 3 H 0 4 3 作者简介冯少荣 1 9 6 4 一 ，男，河北省南宫市人，副教授，博士研究生，从事并行分布数据库、数据仓库、数据挖掘等方面的研究 E - m a i l s h a o r o n g x m u ．e d u ．c n T e l 0 5 9 2 2 1 8 6 8 2 5 万方数据 1 0 6中国矿业大学学报 第3 7 卷 数，因此，具有两个比较明显的弱点1 当数据量 增大时，要求较大的内存支持，I ／0 消耗也很大；2 当空间聚类的密度不均匀，聚类间距离相差很大 时，聚类的质量较差．针对D B S C A N 算法存在的不 足，本文提出利用“分而治之”和高效的并行算法思 想对其进行改进，采用降维技术和增量处理方式提 高聚类的效率．通过在标准数据集上与原D B s C A N 算法进行实验比较，结果表明，新算法高效 可行． ， 1 D B S C A N 算法存在的问题 1 在聚类过程中，D B S C A N 一旦找到一个核 心对象，即以该核心对象为中心向外扩展．此过程 中核心对象将不断增多，未处理的对象被保留在内 存中．若数据库中存在庞大的聚类，将需要很大的 内存来存储核心对象信息，其需求难以预料． 2 输入参数敏感．确定参数E p s ，M i n P t s 困 难，若选取不当，将造成聚类质量下降． 3 由于在D B S C A N 算法中，变量E p s ， M i n P t s 是全局惟一的，当数据分布不均匀时聚类 质量较差． 针对D B S C A N 算法存在的问题，虽然已有一 些改进方法r 8 ] ，但它们或多或少都存在一些不足， 并没有很好解决存在问题． 2D B S C A N 算法的改进 2 ．1 输入参数的处理 针对D B S C A N 算法对输入参数 聚类半径 E p s ，聚类点数M i n P t s 敏感问题，作如下处理． 由于参数的设置通常是依赖经验，当数据密度 相差较大和类间距离分布不均匀时，很难选取一个 合适的E p s 值来进行聚类且得到比较准确的结 果．因此，事先确定算法的参数值大小是不可取的， 应在聚类过程中根据聚类结果的好坏对参数进行 适当的调整．比如选择适当的评价函数作为评价聚 类结果的尺度．反复调整算法的参数，重新聚类，直 到聚类结果满足要求． 尽管D B S C A N 算法提供了利用绘制降序k 一 距离图的可视化方法来选择E p s ，选定的E p s 值已 经比较接近“理想”值；但常有微小差距，最终造成 聚类结果的相差很大．可以考虑采用如下方法来加 以改善 1 可以对所有聚类对象按照从一个簇到另一 个簇，按簇边缘一簇核心一簇边缘的顺序排序．这 样，该对象序列就可以反映出数据空间基于密度的 簇结构信息．基于这些信息可以容易地确定合适的 E p s 值，并随之发现各个簇． 2 不对原始数据集进行聚类，而是通过从数 据集合中抽取高密度点生成新的数据集合，并修改 密度参数，反复进行这一过程，直到生成的数据集 合可以很容易地被聚类为止，然后以此结果为基 础，再将其它点逐层地吸附到各个类中．这样，就避 免了D B S C A N 算法中输人参数对聚类结果的影 响． 3 采用核聚类的思想对样本集进行非线性变 换，使样本集的分布尽可能地均匀，经过核函数的 映射使原来没有显现的特征突现出来，然后再用全 局参量；E p s ，从而能够更好地聚类，得到较好的结 果． 4 在绝大多数聚类结果不理想的情况下，是 E p s 值选择过小，导致本应为一个簇的对象集合被 分析成了多个子簇．被分开的子簇共享一些对象， 可以认为子簇通过这些共享的对象相互连接．而 D B S C A N 算法将子簇的连接信息简单地丢掉．因 此，可以通过记录下所有的簇连接信息，由用户根 据实际的聚类结果和簇连接信息，将被错误分开 的子簇合并．这样可以提高聚类的效果，而输入参 数E p s 的变化对聚类结果的影响，就被最后的合 并过程屏蔽掉． 可以考虑以下两种方式进行改进 1 并行化凹] ．从D B S C A N 算法可以看出，全 局变量E p s 值影响了聚类质量，尤其是数据分布 不均匀时．因此，考虑对数据进行划分，每一个划分 中的数据分布相对较均匀，根据每个划分中数据的 分布密集程度来选取E p s 值．这样一方面降低了 全局变量E p s 值的影响，另一方面由于具有多个 划分，因此考虑并行处理，从而提高聚类效率，也降 低了D B S C A N 算法对内存的较高要求． 2 增量式处理．当数据增加或者删除时，只考 虑其增加或删除的数据所影响到的那些类．这种方 法在处理大数据集时非常有效，不需要重新对数据 库中的数据进行聚类，只需要对类进行渐进性地更 新，修正和加强已发现的类．另外，由于高维数据的 复杂性，使聚类分析的效率和实用性都很差．通过 确定聚类空问中和聚类主题相关性较强的数据维， 来降低聚类空间的维度．利用数据降维可以降低数 据结构上的复杂性．目前，有多种降维技术[ 10 。1 1 ] ，均 可用于特征空间的削减．在方法的选择上应根据降 维后，信息丢失率在可接收范围内，来选择一种合 适的降维方法． 万方数据 第1 期冯少荣等D B S C A N 聚类算法的研究与改进 2 ．2 数据划分网格的产生 数据经过降维处理，实现从多维到二维的多维 变换后，就可以实现数据的划分． 2 ．2 ．1 数据划分过程 在数据的分区中，可以利用在关系数据库系统 提供了5 种内部聚集函数c o u n t ，S U m ，a v g ， m a x ，m i n 来进行数据分布特性的统计． 定义所谓“步长密度”是指在一个度量长度 内的点数除以整个样本数据中的点数． 在划分中使用直方图来确定数据分布的密度 情况．直方图由一组矩形组成，这些矩形反映了落 在给定区间内的点数占总的样本数据的多少．在画 直方图之前，首先要确定分组数和数据样本点中的 最大值和最小值．最大值和最小值可以使用内部聚 集函数求出，而组数的值不宜过大或过小，如果组 数取得过大，则有的区间内没有样本观测值，过小 则无法看出数据点的分布情况．组数 m 和数据 点 以 之间一般应该满足 m ≈1 ．8 7 理一1 寺． 组数确定之后，可求出每一个区间内的点数， 从而求出该区问内的点的密度情况，如图1 所示． 釉 图1 数据在X 轴的分布密度 F i g ．1 D i s t r i b u t i o nd e n s i t yo fd a t ao nXa x i s 通过每个矩形上边的中点顺次连接成一条曲 线，该瞌线反映出数据点的大概密度分布情况．为 了避免把一个类分裂成多个类，在两个相邻波峰 之间的波谷位置选择划分点，即数据分布最稀疏的 位置确定划分点．在划分中，给定一阀值A ，用来决 定是否需要在相邻的两个波峰之问确定一个划分 点，用向量 L 。，s 。，L 来存储相邻的两个最大值 点L 。 波峰 和L 波峰 以及相邻两个波峰之间 的波谷S 。，当lL 。一L 。l A 时，在S 。所对应的坐 标轴上的点处进行划分，所有这些坐标轴上的点构 成集合S ，S 中存储了所有的划分点．从图1 中的曲 线可以看出，X ，，X 为相邻的两个波峰值，而且这 两个波峰值相差较大，因此，可以在波谷位置确定 划分点为X 。．分别对X ，y 轴作划分步骤，确定划 分点．从图1 中可以看出，并不是所有的情况都需 要进行数据的划分，当发现数据的分布密度相差不 大时，就不需要进行划分 连续分布时 ． 当出现下面3 种情况时1 数据分布密度为 一条直线；2 数据分布密度呈现递增的情况；3 数据分布密度呈现递减的情况．说明相邻区域内的 数据分布密度较一致，不存在数据分布较稀疏的区 域 边界区域除外 ，这时需要把两个维上的数据划 分结合起来考虑，并根据处理机数目进行数据划 分．假设处理机数目为N 个，在某一维上划分了 K i i X 或i Y 个区域，另一维上平均划分成 N ／K 。个区域． 若不是上述3 种情况，就需要用上述阀值进行 确定．但当出现互相包含的环状类和互相缠绕的螺 旋状类时，用这种简单的投影到X ，y 轴的方法并 不见效． 2 ．2 ．27 ’。数据划分算法P a r t i t i o n 算法P a r t i t i o n 算法 输入二维的样本数据文件F ，处理机数目N ． 输出每维上的划分点S S ≥1 ． 1 根据样本点数确定组数m 和样本数据中的 最大值m a x 和最小值m i n ． 2 计算步长d 一m a x - - m l n ． 3 对m 个组的每一个执行 a ．计算步长密度B 一莓薹甬觜； b ．存储m 个向量 步长起点，步长终点，B ． 4 对优个组的每一个执行／／判断n 值的变 化情况． i f P i 没有变化o rP i 呈单调递增o r 』D i 呈单调递 减 t h e n 平均进行分配N ／K 。；确定S 个 S N ／K 。一1 划分点． e l s e 依次判断相邻的两个波峰值之间的差的 绝对值是否大于阀值A ，如果大于，记下波谷S 。对 应的坐标值S ； S SUS 。． 5 输出所有的划分点S ． 对X 轴和y 轴分别采用这种数据划分方法确 定划分点，在某一维上可以定义一个划分向量V ， i X 或Y P 。P ⋯，P 。 ，设第i 维的第k 区间记为工。 [ z 。，h 。] ，这样每一个长方形为2 个 不同维区问的笛卡儿乘积[ z ，。。，h ，。。] [ z 艟， h 抛] ，该长方形称之为网格，每个网格可以用表达 式 z 。。。≤z ≤h 。。。八z 。。≤Y ≤h ；2 表示，这个网 格可以使用坐标定义为 K ，，K 。 ．这就可实现把 万方数据 1 0 8 中国矿业大学学报第3 7 卷 分布较均匀的数据划分到一个长方形的网格中，从 而把各个网格分配给多个处理机进行单独的 D B S C A N 聚类．这样处理之后，数据分布较均匀， 各个区域之问不会由于E p s 值的选择而受到影响， 提高了聚类质量．另一方面，由于多个处理机对数 据进行聚类，从而提高了聚类效率． 2 ．3 网格分配算法 网格分配算法实现在处理机问分配由P a r t i t i o n 算法产生的网格．在该算法中使用了一个坐标 和求模函数C M D K 1 ，K 2 一 K 1 K 2 m o d N ，实现处理机之问分配网格的，即坐标 K 。，K 。 的网格被分配给处理机C M D K 。，K ． 算法D a l l o c a t i o n 算法． 输入存储在处理机0 上的数据文件F ，以及 划分向量 P 。P n ，⋯，P 。 ，i X 或y ． 输出由P a r t i t i o n 算法产生的网格 1 对数据文件F 的每个网格T 执行 a ．由F 的划分向量 P 。P n ，⋯，P 。 计算网 格了、所属网格的坐标定义 K ，，K ； b ．矗一C M D K l ，K 2 ； C ．把网格 z ，。，≤z ≤h ㈨ z 。。。≤Y ≤h 。 发 送到处理机k ． 2 对N 个处理机的每一个执行 处理机i 接受并存储处理机0 发送来的网格 T ，第一个F O R 循环B E G I N 和E N D 之问的语句 均在处理机。上执行． 2 ．4 基于数据划分的并行D B S C A N 算法 一旦数据划分完成，把各个网格分配给处理机 之后，就可以并行地对各个处理机使用D B S C A N 算法，每一个数据区域可以选取本机的E p s 值．各 个处理机也建立了一个R 。树，便于区域查询．具 体过程为1 构建本处理机数据的R 树；2 选取 适合本机的E p s 值；3 根据本机的E p s 值进行聚 类． 为了提高局部聚类的合并效率，需要在局部聚 类过程中记录下噪声点、类的边界点以及划分的边 界信息．因它们可能是全局中某个聚类的边界点或 某一被分割的小聚类中的点．由于划分可能使得本 属于同一个类的数据点被划分到相邻的两个区域 中，最后需要对两个类进行合并．为了提高聚类效 率，在局部聚类过程中已经将可能有用的信息保存 了下来，如噪声点，边界点信息．类的合并涉及到3 种情况 1 两个类A ，B 合并，当且仅当 a ．A ，B 分别处于相邻的两个网格P A ，P e 中i b ．没E p s A ，E p s B 分别是网格 ，P 。的 E p s 值，E p s P A ，P B 一m i n { E p s A ，E p s B } ， 两个类中的边界点之问的距离小于等于E p s P 。， P B ． 2 对噪声点的归并 处在网格边界的噪声点N 可能是全局中某个 类C 的边界点，此时需要把噪声点N 归到该类C 中．当噪声点N 满足以下条件时就进行归并 a ．类C 和噪声点N 分别处在两个相邻的网格 中； b ．设E c 是类C 中的边界点，如果边界点和噪 声点N 之间的距离小于等于E p s P 。 ． 3 多个噪声点产生新类 在数据划分时，一些较小的类被分到不同的网 格中，由于在同一个网格中的数据量较小，因此这 些点被认为是噪声点．首先随机选取一个噪声点 E ，如果噪声点E 和其它噪声点E ，之间的距离小 于等于E p s 值，则把E 看成一个新类的核心对象 点，然后剩下的噪声点按照第二种方法进行归并． 2 ．5 D B S C A N 算法中的增量聚类分析 数据库中的数据不是一成不变的，有的数据库 需要定期进行更新操作．这样就会增加一些数据， 或者删除一些数据．这些数据的增加或者删除都会 影响系统中已经存在的类．可能会出现1 有的 类元素减小；2 新增加一些类；3 出现一些新的 噪声点；4 使原来的多个类合并成一个类；5 使 原来的类分裂成多个类．对数据库中的数据进行增 加或者删除都是一项非常频繁的操作，尤其是在 W w w 日志数据库中． 因此，若对更新后的数据重新聚类是一个非常 耗时的工作．因为增加或删除的数据只会影响到与 这个数据相邻的小部分数据类别，而其它大部分数 据类别是不会受到增加或删除数据的影响．另一方 面，如果数据一更新，就重新聚类，这一点在时问效 率上也不允许，因为数据的更新会经常发生，而且 在大型数据库中这样做也不现实． 所以，基于D B S C A N 算法，在此讨论增加或者 删除数据元素对已有类的影响．不论是增加还是删 除数据都可能会改变邻域内对象的属性，即原来是 核心对象的可能会成为非核心对象，原来是非核心 对象而成为核心对象．当增加了数据对象P ，则P 的邻域内原来是边界点或者噪声点的那些点可能 变成核心对象，相应会建立新的密度相连的链，当 删除P ，原来P 的E p s 邻域内的核心对象可能会 成为非核心对象，原来的一些密度相连的链就会被 万方数据 第1 期冯少荣等D B S C A N 聚类算法的研究与改进 删除． 2 ．5 ．1 数据元素的增加 增加数据可能对已有类的影响∞。3 ] 1 增加的数据点可能本身就是一个噪声点， 这种情况下，该噪声点不会影响其它的类． 2 原来的一些噪声点和新增加对象P 建立一 个新的类别． 3 新增的对象P 成为原来某类中的一个对 象． 4 原来的两类由于新增对象P 的插入而进行 合并． 2 ．5 ．2 数据对象的删除 数据对象的删除也可能会影响删除对象邻域 内的对象的核心对象属性，使原来的核心对象成为 非核心对象，所以，原来密度相连的一些链的序列 就被删除，引起一些类的分裂；也可能会使原来的 一些核心对象变成噪声点，从而使类中的数据对 象减少．也可能使原来的一些数据对象比较少的类 被删除，类中原来的数据对象成为噪声点． 因此，如果能够很好地利用原始数据的聚类结 果来对现在更新了的数据进行聚类分析，就可以在 很大程度上解决对大数据量进行聚类的效率问题． 2 ．6 算法复杂性讨论 D B S C A N 时间复杂度为O n 2 ，其中咒为数 据对象数目．当九很大时，D B S C A N 算法耗时T D 为 行2 t ．改进的算法耗时主要在局部聚类及聚类合并 时交叠区点集聚类信息传输上，而数据传输并行 执．设k 为数据分区数，9 为交叠比，因为数据近似 均匀划分，每个节点上对象数目为[ 咒 1 9 ] ／走， 又设传输一个整数 对象聚集结果用整数表示 的 时间为T ，则数据传输所花时间为n P T ／k ，不考虑 聚类合并耗时，改进的D B S C A N 耗时丁改进D 为 E n 1 c p ／k ] 2 t n 9 T ／k ，加速比为 口一善L ；』L ． 1 口2 了；■一2 萧． L lJ 定』改进D 咒2 1 p 2 咒妒足』一 ’t 若采用空间索引，D B S C A N 算法的时间复杂 度为O n l g7 2 ，改进的D B S C A N 加速比为 a 一业卫 ． 2 n k 1 9 [ 1 9 ，2 l g 1 9 一l o g 足] 咒9 _ 1 对于同一个系统，T ／t 值是确定的，从式 1 可看出控制交叠比并选择合适的数据分区数是，可 以得到一个好的加速比． 对于高维情况，可以像二维空间那样进行数据 划分，只是划分更加复杂而已．虽然改进后的D B S C A N 算法其时间复杂度由3 部分 数据划分及网 格分配、并行聚类、合并 决定，但把数据划分及网 格分配作为预处理部分，其耗时没有计入到算法消 耗的总时间中，如同D B S C A N 算法没有将构建 R * 一树所花时间 尽管很花时间 计入算法总时间 内一样．若不考虑类的合并耗时，在时间复杂性方 面，改进后的D B S C A N 算法时问复杂度与D B S C A N 算法时间复杂度 O n l g 门 比较相似．可 粗略地表示为O n 。l g 胛． 挖2 l g 艘2 ⋯ 船 l g 理 ， 卵； i 一1 ，2 ，⋯，k 为各个数据分区的数据对象总 量． 3 实验结果 使用改进后的D B S C A N 算法对图2 中的数据 对象进行聚类分析．根据数据密集程度，把数据分 成3 个区域 如图3 所示 ．区域1 2 ．0 5 ≤z ≤ 4 ．3 3 八3 ≤Y ≤4 ．6 6 ；区域2 4 ．3 3 ≤z ≤7 ．6 6 0 ．6 6 ≤Y ≤3 ；区域3 0 ．2 ≤z ≤3 ．1 八0 ．6 6 ≤Y ≤3 ． C ， c 懑嚆G 图2 分布不均匀的数据对象 F i g ．2 N o nu n i f o r m l yd i s t r i b u t e dd a t ao b je c t s 0l23456 78 Ⅳ 图3根据密度划分的区域 F i g ．3 A r e ab a s e do nd e n s i t yp a r t i t i o n 对3 个区域按E p s 一0 ．1 6 ，0 ．2 0 ，0 ．2 3 分别进 行聚类，聚类结果如表1 ．若使用统一的E p s ，则结 果为表2 ． 表1不同E p s 的聚类结果 T a b l e1 C l u s t e r i n gr e s u l to fd i f f e r e n tE p s ．G 警。遵≤是一， 鬈。。，． 0 ≮q } ■～ 万方数据 中国矿业大学学报第3 7 卷 表2统一的E p s 的聚类结果 T a b l e2 C l u s t e r i n gr e s u l to fu n i f i e dE p s E p s 值聚类结果 6 个类，C ，，C 2 ，C 3 合并成一个类 7 个类，C 7 分裂成两个类 结果表明，D B S C A N 无论取什么E p s 值，都无 法得到完全正确的聚类结果；而使用改进后的D B S C A N ，由于对3 个数据分区分别取不同的E p s 值，对3 个数据分区并行进行聚类，获得的聚类结 果与实际情况一致．同时，使用分区之后的聚类更 加合理，质量更高． 使用分区后的执行效率也得到了一定的提高， 如图4 所示．各个分区的执行时问明显小于没分区 所需要的总的时间．而且分区后总的时间小于没分 区时总的时间，因此分区对效率也有一定的提高． 鼍鼍} --I●_5 [ --I- _ o123无无 分区 图4 各分区的执行时I 司 F i g ．4 E a c hp a r t i t i o ne x e c u t i o nt i m e 如果同时使用模拟数据和真实数据进行测试， 模拟测试数据集来自D B S C A N 算法中的d a t a b a s e ，测试的真实数据用的是S E Q U O I A 2 0 0 0 数据 库．数据量从2 万到1 5 万个点．测试的硬件环境 是P 4 2 ．4G H Z 的C P U ，主存为5 1 2M ，硬盘为8 0 G ，72 0 0r ／m i n ．软件环境是操作系统为M i c r o s o f tW i n d o w s2 0 0 0S e r v e r ，算法实现的语言为 标准C ．表3 给出了一组测试结果，从中可以 看到，改进后D B S C A N 算法的运行时间快于原始 D B S C A N 算法的运行时问，且随着数据量的加大， 差距更加明显．可见新算法是一种效率非常高的聚 类算法．且当数据量增大时，改进后的D B S C A N 算 法所需时问的增幅比原始D B S C A N 算法小． 表3S E Q U O I A 2 0 0 0 数据库的一组测试结果 T a b l e3 A g r o u po ft e s t i n gr e s u l t so f S E Q U O I A 2 0 0 0d a t a b a s e 4 结论 本文对D B S C A N 算法的优缺点进行了详细分 析和研究，分析了聚类质量对输入参数E p s 的依 赖．根据D B S C A N 存在的问题，使用了“分而治之” 和高效的并行算法思想，把数据划分成分布均匀的 网格，对每个网格单独处理，分配网格到多个处理 机共同聚类．这样一方面克服了全局变量E p s 的 影响，提高了聚类质量；另一方面，提高了聚类效 率，也降低了D B S C A N 对主存的较高要求．最后分 析了聚类过程中数据对象的增加和删除对聚类的 影响；对改进的聚类算法给出了实验结果．实验结 果中表明改进的聚类算法无论是在聚类质量还是 在聚类效率上都得到了比较满意的结果． 参考文献 [ 1 ] I 。I UZ h e n h u a ，J I A N GZ h e n - q u a n ，Z U OR u s o n g ． S t u d yo ff u s s yc l u s t e r i n g o fe n g i n e e r i n gg e o l o g i c a l e n v i r o n m e n tw i t hG I S [ J ] ．J o u r n a lo fC h i n aU n i v e r s i t yo fM i n i n g T e c h n o l o g y ，2 0 0 3 ，1 3 2 1 9 6 2 0 0 ． E 2 ] 沈斌，姚敏，温长洋．一种基于混合模型的时间 序列数据挖掘系统E J ] ．中国矿业大学学报，2 0 0 3 3 2 3 2 8 4 2 8 8 ． S H E NB i n ，Y A OM i n ，W E NC h a n g y a n g ．As y s t e m o ft i m es e r i e sd a t am i n i n gb a s e do nh y b r i dm o d e l [ J ] ． J o u r n a lo fC h i n aU n i v e r s i t yo fM i n i n g8 LT e c h n o l o g Y ，2 0 0 3 3 2 3 2 8 4 2 8 8 ． E 3 2 刘高军，朱燃．基于数据挖掘技术的建筑企业信 用评价E J ] ．中国矿业大学学报，2 0 0 5 ，3 4 4 4 9 4 4 9 9 ． L I UG a o j u n ，Z H UY a n ．C r e d i te v a l u a t i o no fo n s t r u c t i o nc o m p a n i e sb a s e do nd a t am i n i n g [ J ] ．J o u r n a l o fC h i n aU n i v e r s i t yo fM i n i n g T e c h n o l o g y ．2 0 0 5 。 3 4 4 4 9 4 4 9 9 ． [ 4 1E S T E RM ，K R I E G E LH ，S A N D E RJ ，e ta 1 ．Ad e n s i t y b a s e da l g o r i t h mf o rd i s c o v e r i n gc l u s t e r si nl a r g e s p a t i a ld a t a b a s e sw i t hn o i s e [ c ] ／／P r o co ft h e1 9 9 6 2 n dI n t ’1C o n fo nK n o w l e d g eD i s c o v e r ya n dD a t a M i n i n g ．P o r t l a n d A A A IP r e s s ，1 9 9 6 2 2 6 2 3 1 ． [ 5 ]Q I A NW e i n i n g ，G O N GX u e q i n g ，A oY i n g z h o u ． C l u s t e r i n gi nv e r yl a r g ed a t a b a s e sb a s e do nd i s t a n c e a n dd e n s i t y [ J ] ．J o u r n a lo fC o m p u t e rS c i e n c ea n d T e c h n o l o g y ，2 0 0 3 ，1 8 1 6 7 7 0 ． [ 6 ] 周水庚，周傲英，曹晶，等．一种基于密度的快速 聚类算法[ J ] ．计算机研究与发展，2 0 0 0 ，3 7 1 1 1 2 8 7 1 2 9 2 ． Z H O US h u i g e n g ，Z H O U A o y i n g ，C A OJ i n g ，e t 万方数据 第1 期冯少荣等D B S C A N 聚类算法的研究与改进1 1 1 [ 7 ] [ 8 ] [ 9 ] a LAf a s td e n s i t y b a s e dc l u s t e r i n ga l g o r i t h m [ J ] ． J o u r n a lo fC o m p u t e rR e s e a r c ha n dD e v e l o p m e n t ， 2 0 0 0 ，3 7 1 1 1 2 8 7 1 2 9 2 ． E S T E RM ，K R I E G E LHP ，S A N D E RJ ，e ta 1 ．I n c r e m e n t a lc l u s t e r i n gf o rm