dbscan文献

第３７卷　

Ｖ＿０１．３７　第１２期　

ＮＯ．１２　计算机工程　

Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　２０１１年６月　

Ｊｕｎｅ　２０ｌｌ　

・软件技术与数据库・　文章编号：１０ｏ　＿３４２８（２０１１）１２—＿００５０—＿０３　文献标识码：Ａ　中图分类号．ＴＰ３９３　

基于改进ＤＢＳＣＡＮ算法的文本聚类　

蔡岳，袁津生　

（北京林业大学信息学院，北京１　０００８３）　

摘要：目前多数聚类算法不能很好地适应文本聚类的快速自适应需求。为此，论述ＤＢＳＣＡＮ算法的基本原理和实现过程，提出一种基　

于改进ＤＢＳＣＡＮ算法的文本聚类算法，利用最小二乘法降低文本向量的维度，并创建一种应用于ＤＢＳＣＡＮ算法的簇关系树结构。实验结　

果表明，该算法能自适应地进行文本聚类，且与ＤＢＳＣＡＮ相比，准确率较高。　关崩司：ＤＢＳＣＡＮ算法；文本聚类；最小二乘法；簇关系树　

Ｔｅｘｔ　Ｃｌｕｓｔｅｒｉｎｇ　Ｂａｓｅｄ　０ｎ　Ｉｍｐｒｏｖｅｄ　ＤＢＳＣＡＮ　Ａｌｇｏｒｉｔｈｍ　

ＣＡＩ　Ｙｕｅ．ＹＵＡＮ　Ｊｉｎ－ｓｈｅｎｇ　

（Ｓｃｈｏｏｌ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ，Ｂｅｉｊｉｎｇ　Ｆｏｒｅｓｔｒｙ　Ｕｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ　１０００８３，Ｃｈｉｎａ）　

［Ａｂｓｔｒａｃｔ｜Ｍｏｓｔ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍｓ　ｃａｎ　ｎｏｔ　ｍｅｅｔ　ｔｈｅ　ｄｅｍａｎｄ　ｏｆ　ｓｐｅｅｄ　ａｎｄ　ｓｅｌｆ－ａｄａｐｔｉｎｇ　ａｂｏｕｔ　ｔｅｘｔ　ｃｌｕｓｔｅｒｉｎｇ．Ｉｎ　ｔｈｉｓ　ｐａｐｅｒ，ａｆｔｅｒ　ｆｕｎｄａｍｅｎｔａｌ　

ｔｈｅｏｒｙ　ａｎｄ　ｉｍｐｌｅｍｅｎｔ　ａｒｅ　ｅｘｐｏｕｎｄｅｄ，ｔｈｅ　ｉｄｅａ　ｏｆ　ｃｒｅａｔｉｎｇ　ａｎ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｉｍｐｒｏｖｅｄ　ＤＢＳＣＡＮ　ｉｓ　ｐｒｏｐｏｓｅｄ．Ｔｈｅ　ｌｅａｓｔ　ｓｑｕａｒｅ　ｍｅｔｈｏｄ　ｉｓ　ｕｓｅｄ　ｆｏｒ　ｄｅｃｒｅａｓｉｎｇ　ｄｉｖｉｓｉｏｎｓ　ａｎｄ　ｔｈｅ　ｃｌｕｓｔｅｒ－ｔｒｅｅ　ｉｓ　ｃｒｅａｔｅｄ　ｔｏ　ｇａｉｎ　ａ　ｓｔｒｏｎｇ　ｓｅｌｆ－ａｄａｐｔｉｎｇ　ｏｆ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ．Ａｃｃｏｒｄｉｎｇ　ｔｏ　ｔｈｅ　ｄａｔａ　ｆｒｏｍ　ａｎ　ｅｘｐｅｒｉｍｅｎｔ　

并行DBSCAN聚类算法

[摘 要] 本文针对DBSCAN算法在计算速度方面的瓶颈,提出了一种新的基于内存的并行DBSCAN算法:合理划分数据库,各个处理器并行聚类,之后合并聚类结果,可以达到很好的聚类结果效果和计算效率。通过对一台双核计算机的实验,发现实验速度可以提高50%左右。

[关键词] 聚类;DBSCAN算法;并行DBSCAN算法

聚类分析是根据相似性对数据库中的对象进行分组, 使得不同类中的数据尽可能相异而同一类中的数据尽可能相同,从而发现数据空间的分布特征,是数据挖掘的主要任务之一。目前已经有了很多经典的聚类算法,总体来说可以分为基于密度、分区、分层、网格几类。

随着信息技术的高速发展,出现了越来越多诸如地理信息、卫星图像等大规模空间数据库。大规模空间数据库对于聚类算法的要求更高,要求算法能够发现任何形状的类并能高效聚类。DBSCAN是面向空间数据库的基于密度的聚类算法,其主要思想为:如果一个对象在半径为ε的领域内包含至少MinPts个对象,那么该区域是密集的。其优点是能够发现任意形状的类,并且不受异常值(噪声)的影响,然而当数据库规模增大时,该算法要求较大的内存支持,I/O消耗大,采用串行算法,无论是运算速度还是内存,都无法满足对大规模数据库聚类的需求。

针对该算法的计算效率问题,本文提出一种基于内存的并行DBSCAN算法。首先基于投影进行数据分区,之后在每一处理器上分别聚类,最后合并聚类结果。实验证明该算法较DBSCAN算法速度有很大提高,并且聚类的准确程度亦有所改善。

1DBSCAN算法介绍[1]

首先给出DBSCAN算法的几个基本概念,其中D为数据库, Eps和MinPts为给定阈值。

定义1.1(Eps-邻域) 对于空间任意一个点P,其Eps领域记作NEps(p)={q∈D

dist(p,q)≤Eps｝。

定义1.2(核心点) 对于一个点,如果在其Eps-邻域内至少包含MinPts个对象,则称该对象为核心对象。

ＩＳＳＮ　１ＯＯ９－３０４４　ＣｏｍｐｕｔｅｒＫｎｏｗｌｅｄｇｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ电脑知识与技术　

Ｖｏ１．８，Ｎｏ．７，Ｍａｒｃｈ　２０１２．　Ｅ－ｍａｉｈ　ｊｓｈ＠ｅｃｃｃ．ｎｅｔ．ｃｎ　ｈｔｔｐ：／／ｗｗｗ．ｄｎｚｓ．ｎｅｔ．ｃｒｌ　

Ｔｅｌ：＋８６—５５　ｌ一５６９０９６３　５６９０９６４　

基于ＸＭＬ分布式数据库的ＤＢＳＣＡＮ分片方法研究　

方明，雷杨　

（西安石油大学计算机学院，陕西西安７１００６５）　

摘要：ＸＭＬ分布式数据库可以解决不同数据源的异构问题，各个数据库的数据之间传输问题。在实际应用中，由于数据量大，Ａｄ／］　

提出了数据分片来减少系统响应时间。然而在查询过程中，不变化的分片方法无法适不断变化和增加的谓词。并且按照现有的分　

割方法，大型数据库会有大量的谓词或属性，那么分割的片数也将成指数式增长。该文采用一种ＤＢＳＣＡＮ分割方法来解决这些问　

题。　

关键词：ＤＢＳＣＡＮ；分布式数据库　

中图分类号：ＴＰ３１１　文献标识码：Ａ　文章编号：１００９—３０４４（２０１２）０７—１４６５—０２　

Ｓｔｕｄｙ　ｏｆ　ＤＢＳＣＡＮ　Ｆｒａｇｍｅｎｔａｔｉｏｎ　Ｍｅｔｈｏｄ　Ｂａｓｅｄ　ｏｎ　ＸＭＬ－Ｂａｓｅｄ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ｄａｔａｂａｓｅ　

ＦＡＮＧ　Ｍｉｎｇ，ＬＥＩ　Ｙａｎｇ　

（Ｓｃｈｏｏｌ　ｏｆＣｏｍｐｕｔｅｒ，Ｘｉ　ａｎ　Ｓｈｉｙｏｕ　Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉ　ａｎ　７１　００６５，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：ＸＭＬ—ｂａｓｅｄ　ｄｉｓｔｒｉｂｕｔｅｄ　ｄａｔａｂａｓｅ　ｃａｎ　ｓｏｌｖｅ　ｐｒｏｂｌｅｍｓ　ｃａｕｓｅｄ　ｂｙ　ａｎｄ　ａｒｃｈｉｔｅｃｔｕｒｅ　ａｎｄ　ｔｒａｎｓｍｉｓｓｉｏｎ　ｂｅｔｗｅｅｎ　ｄｉｆｅｒｅｎｔ　ｄａｔａ　ｓｏｕｒｃｅｓ．　Ｉｎ　ｐｒａｃｔｉｃｅ，ｓｏｍｅ　ｏｆｆｅｒ　ｆｒａｇｍｅｎｔａｔｉｏｎ　ｔＯ　ｒｅｄｕｃｅ　ｒｅｓｐｏｎｓｅ　ｔｉｍｅ．Ｈｏｗｅｖｅｒ，Ｉｎ　ｑｕｅｒｙｉｎｇ　ｐｒｏｃｅｓｓ，ｕｎｃｈａｎｇｅａｂｌｅ　ｆｒａｇｍｅｎｔ　ｍｅｔｈｏｄ　ｃａｎ’ｔ　ａｄａｐｔ　

第ｌ６卷第２期　２００６年４月　华北航天工业学院学报　Ｊｏｕｒｎａｌ　ｏｆ　Ｎｏｒｔｈ　Ｃｈｉｎａ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ａｓｔｒｏｎａｕｔｉｃ　Ｅｎ　Ｖｏ１．１６　Ｎｏ．２　ＡＤｒ．２００６　

增量聚类综述及增量ＤＢＳＣＡＮ聚类算法研究　

徐新华　谢永红　（北京科技大学，北京１０００２４）　摘要：本文首先介绍了增量聚类算法的分类以及研究现状，提出了增量聚类算法等价性概念；然后介绍了增　量ＤＢＳＣＡＮ聚类算法；最后针对用于批量更新的增量ＤＢＳＣＡＮ聚类算法，提出了本文的改进方法。其中，用插　入更新数据集生成的子模式调整原聚类模式的方法，还可有效地应用于分布式聚类。　关键词：聚类；增量聚类；增量ＤＢＳＣＡＮ　中图分类号：ＴＰ３０１　文献标识码：Ａ　文章编号：１００９—２１４５（２００６）０２—００１５—０３　

而言，往往是多种聚类思想融合的结果，并不能简单　上　策矢　地将其归人上述某一类算法。每种聚类算法都有其　图１增量数据模型　优点，同时也都存在着一定的不足。　引起数据集变化的更新操作通常包括：插入、删　聚类分析的数据源——数据库中的数据通常是　除和修改。由于修改操作可以由删除和插入操作来　不断变化的，使得原聚类分析得到的聚类可能与新　实现（先删除、后插入），所以更新操作可以只考虑插　的数据不匹配。获得新的聚类的方法通常有两　人和删除两种。对于因插入、删除操作产生的增量　种　］：一是重新聚类；二是增量聚类。　数据集△　和△一，常用的处理方式有两种：（１）单个　聚类分析所面对的一般都是大数据集。所以重　方式——１次处理１个数据；（２）批量方式——１次　新聚类，一方面是代价太大；另一方面，因未利用前　处理１批数据。这两种增量处理方式适应不同的应　一次聚类的有关信息，而导致计算资源的浪费。因　用需求，批量方式适用于批量更新的数据挖掘系统，　此，如何设计增量聚类算法以提高聚类效率，成为当　而单个方式更适用于实时数据挖掘系统。　前聚类分析的一个重要挑战。　聚类分析中，判断聚类对象之间的相似性，是通　１　增量聚类算法综述　过计算对象之间的差异度来实现的。在各聚类算法　在设计增量聚类算法时，增量数据模型通常考　中，作为差异度的度量主要有距离和密度两种，其中　虑两种　：一是迄今为止的所有数据，本文称之为全　以距离作为度量的居多。　局数据模型ＦＤＭ（Ｆｕｌｌ　Ｄａｔａ　Ｍ０ｄｅ１）；二是部分数据，　如前所述，目前已经提出了许多聚类算法，但在　如时问窗口内的数据，本文称之为局部数据模型　增量聚类算法方面所做的研究较少，其中比较全面　ＰＤＭ（Ｐａ　ｔ　Ｄａｔａ　Ｍ０ｄｅ１）。这两种增量数据模型对应　和系统的、着眼于增量聚类算法本身的文献就更少。　于不同的应用需求。本文采用图１所示的增量数据　本文引用的文献［６］和文献［７］，根据前述的增量数　——　据处理方式和差异度度量分类，都是基于密度度量，　收稿日期：２００６—０１—０７　但文献［６］为单个方式，文献［７］是批量方式。　作者简介：徐新华（１９６５一），男，副教授，湖南资兴人，从事数据　对于增量聚类算法而言，有一个很重要的基本　挖掘系统的研究与开发。　问题——算法等价性，即增量聚类算法的结果，与重　一１　５—