第11卷第1期 智能系统学报 Vol.11 No.1 2016年2月 CAAI Transactions on Intelligent Systems Feh.2016 D01:10.11992.tis.201410021 网络出版地址：http:/www.cnki.net/kcms/detail/23.1538.tp.20150930.1557.028.html 一种改进的自适应快速AF-DBSCAN聚类算法 周治平，王杰锋，朱书伟，孙子文 (江南大学物联网工程学院，江苏无锡214122)》 摘要：基于密度的DBSCAN聚类算法可以识别任意形状簇，但存在全局参数Eps与MiPs的选择需人工干预，采 用的区域查询方式过程复杂且易丢失对象等问题，提出了一种改进的参数自适应以及区域快速查询的密度聚类算 法。根据KNN分布与数学统计分析自适应计算出最优全局参数Es与MinPts,避免聚类过程中的人工干预，实现了 聚类过程的全自动化。通过改进种子代表对象选取方式进行区域查询，无需漏检操作，有效提高了聚类的效率。对 4种典型数据集的密度聚类实验结果表明，本文算法使得聚类精度提高了8.825%，聚类的平均时间减少了0.92s。 关键词：密度聚类：DBSCAN:区域查询：全局参数：KNN分布：数学统计分析 中图分类号：TP181文献标志码：A文章编号：1673-4785(2016)01-0093-06 中文引用格式：周治平，王杰锋，朱书伟，等.一种改进的自适应快速AF-DBSCAN聚类算法[J].智能系统学报，2016,11(1)：93-98. 英文引用格式：ZHOU Zhiping,WANG Jiefeng,ZHU Shuwei,etal.An improved adaptive and fast AF-.DBSCAN clustering algo- rithm[J].CAAI Transactions on Intelligent Systems,2016,11(1):93-98. An improved adaptive and fast AF-DBSCAN clustering algorithm ZHOU Zhiping,WANG Jiefeng,ZHU Shuwei,SUN Ziwen School of Internet of Things Engineering,Jiangnan University,Wuxi 214122,China) Abstract:The density-based DBSCAN clustering algorithm can identify clusters with arbitrary shape,however,the choice of the global parameters Eps and MinPts requires manual intervention,the process of regional query is com- plex and loses objects easily.Therefore,an improved density clustering algorithm with adaptive parameter for fast regional queries is proposed.Using KNN distribution and mathematical statistical analysis,the optimal global pa- rameters Eps and MinPts are adaptively calculated,so as to avoid manual intervention and enable full automation of the clustering process.The regional query is conducted by improving the selection manner of the object,which is represented by a seed and thus avoiding manual intervention,and so the clustering efficiency is effectively in- creased.The experiment results looking at density clustering of four typical data sets show that the proposed method effectively improves clustering accuracy by 8.825%and reduces the average time of clustering by 0.92 s. Keywords:density clustering;DBSCAN;region query;global parameters;KNN distribution;mathematical statis- tics and analysis 数据挖掘是一种从大量数据中发现感兴趣信息 /0消耗也很大：当空间聚类的密度不均匀，聚类间 的技术，聚类算法在数据挖掘应用中日益广泛。其 距离相差很大时，聚类质量较差。针对DBSCAN 中，基于密度的聚类算法可以发现任意形状的簇且 算法在大型数据库与多密度数据集聚类精度低，计 能够较好地处理噪声数据，越来越受到广泛的关注。 算复杂度高，全局参数人工选取等问题，已有很多学 DBSCAN算法能够发现任意形状的簇，并有效识别 者进行了相关研究：S.Mimaroglu等)提出对位向 离群点，但聚类之前需要人工选择Eps和minPts2 量使用裁剪技术，H.Jiang等)提出一种基于划分 个参数。当数据量增大时，要求较大的内存支持， 的DBSCAN算法，B.Borah等I6提出一种改进的基 收稿日期：2014-10-13.网络出版日期：2015-09-30. 于抽样的DBSCAN算法，D.Kellner提出基于格点 基金项目：国家自然科学基金资助项目(61373126)：江苏省产学研联合 创新资金-前瞻性联合研究基金资助项目(BY2013015-33). 的DBSCAN算法，旨在解决DBSCAN算法在内存占 通信作者：王杰锋.E-mail:18352513420@163.com. 用，处理高维数据和密度分布不均数据聚类效果不
第 １１ 卷第 １ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．１ ２０１６ 年 ２ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｆｅｂ． ２０１６ ＤＯＩ：１０．１１９９２．ｔｉｓ．２０１４１００２１ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ｔｐ．２０１５０９３０．１５５７．０２８．ｈｔｍｌ 一种改进的自适应快速 ＡＦ⁃ＤＢＳＣＡＮ 聚类算法 周治平，王杰锋，朱书伟，孙子文 （江南大学 物联网工程学院，江苏 无锡 ２１４１２２） 摘 要：基于密度的 ＤＢＳＣＡＮ 聚类算法可以识别任意形状簇，但存在全局参数 Ｅｐｓ 与 ＭｉｎＰｔｓ 的选择需人工干预，采 用的区域查询方式过程复杂且易丢失对象等问题，提出了一种改进的参数自适应以及区域快速查询的密度聚类算 法。 根据 ＫＮＮ 分布与数学统计分析自适应计算出最优全局参数 Ｅｐｓ 与 ＭｉｎＰｔｓ，避免聚类过程中的人工干预，实现了 聚类过程的全自动化。 通过改进种子代表对象选取方式进行区域查询，无需漏检操作，有效提高了聚类的效率。 对 ４ 种典型数据集的密度聚类实验结果表明，本文算法使得聚类精度提高了 ８．８２５％，聚类的平均时间减少了０．９２ ｓ。 关键词：密度聚类；ＤＢＳＣＡＮ；区域查询；全局参数；ＫＮＮ 分布；数学统计分析 中图分类号：ＴＰ１８１ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１６）０１⁃００９３⁃０６ 中文引用格式：周治平，王杰锋，朱书伟，等．一种改进的自适应快速 ＡＦ⁃ＤＢＳＣＡＮ 聚类算法［Ｊ］． 智能系统学报， ２０１６， １１（１）： ９３⁃９８． 英文引用格式：ＺＨＯＵ Ｚｈｉｐｉｎｇ，ＷＡＮＧ Ｊｉｅｆｅｎｇ，ＺＨＵ Ｓｈｕｗｅｉ，ｅｔ ａｌ． Ａｎ ｉｍｐｒｏｖｅｄ ａｄａｐｔｉｖｅ ａｎｄ ｆａｓｔ ＡＦ⁃ＤＢＳＣＡＮ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏ⁃ ｒｉｔｈｍ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１６，１１（１）：９３⁃９８． Ａｎ ｉｍｐｒｏｖｅｄ ａｄａｐｔｉｖｅ ａｎｄ ｆａｓｔ ＡＦ⁃ＤＢＳＣＡＮ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ＺＨＯＵ Ｚｈｉｐｉｎｇ， ＷＡＮＧ Ｊｉｅｆｅｎｇ， ＺＨＵ Ｓｈｕｗｅｉ， ＳＵＮ Ｚｉｗｅｎ （Ｓｃｈｏｏｌ ｏｆ Ｉｎｔｅｒｎｅｔ ｏｆ Ｔｈｉｎｇｓ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｊｉａｎｇｎａｎ Ｕｎｉｖｅｒｓｉｔｙ， Ｗｕｘｉ ２１４１２２， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｄｅｎｓｉｔｙ⁃ｂａｓｅｄ ＤＢＳＣＡＮ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｃａｎ ｉｄｅｎｔｉｆｙ ｃｌｕｓｔｅｒｓ ｗｉｔｈ ａｒｂｉｔｒａｒｙ ｓｈａｐｅ， ｈｏｗｅｖｅｒ， ｔｈｅ ｃｈｏｉｃｅ ｏｆ ｔｈｅ ｇｌｏｂａｌ ｐａｒａｍｅｔｅｒｓ Ｅｐｓ ａｎｄ ＭｉｎＰｔｓ ｒｅｑｕｉｒｅｓ ｍａｎｕａｌ ｉｎｔｅｒｖｅｎｔｉｏｎ， ｔｈｅ ｐｒｏｃｅｓｓ ｏｆ ｒｅｇｉｏｎａｌ ｑｕｅｒｙ ｉｓ ｃｏｍ⁃ ｐｌｅｘ ａｎｄ ｌｏｓｅｓ ｏｂｊｅｃｔｓ ｅａｓｉｌｙ． Ｔｈｅｒｅｆｏｒｅ， ａｎ ｉｍｐｒｏｖｅｄ ｄｅｎｓｉｔｙ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｗｉｔｈ ａｄａｐｔｉｖｅ ｐａｒａｍｅｔｅｒ ｆｏｒ ｆａｓｔ ｒｅｇｉｏｎａｌ ｑｕｅｒｉｅｓ ｉｓ ｐｒｏｐｏｓｅｄ． Ｕｓｉｎｇ ＫＮＮ ｄｉｓｔｒｉｂｕｔｉｏｎ ａｎｄ ｍａｔｈｅｍａｔｉｃａｌ ｓｔａｔｉｓｔｉｃａｌ ａｎａｌｙｓｉｓ， ｔｈｅ ｏｐｔｉｍａｌ ｇｌｏｂａｌ ｐａ⁃ ｒａｍｅｔｅｒｓ Ｅｐｓ ａｎｄ ＭｉｎＰｔｓ ａｒｅ ａｄａｐｔｉｖｅｌｙ ｃａｌｃｕｌａｔｅｄ， ｓｏ ａｓ ｔｏ ａｖｏｉｄ ｍａｎｕａｌ ｉｎｔｅｒｖｅｎｔｉｏｎ ａｎｄ ｅｎａｂｌｅ ｆｕｌｌ ａｕｔｏｍａｔｉｏｎ ｏｆ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｐｒｏｃｅｓｓ． Ｔｈｅ ｒｅｇｉｏｎａｌ ｑｕｅｒｙ ｉｓ ｃｏｎｄｕｃｔｅｄ ｂｙ ｉｍｐｒｏｖｉｎｇ ｔｈｅ ｓｅｌｅｃｔｉｏｎ ｍａｎｎｅｒ ｏｆ ｔｈｅ ｏｂｊｅｃｔ， ｗｈｉｃｈ ｉｓ ｒｅｐｒｅｓｅｎｔｅｄ ｂｙ ａ ｓｅｅｄ ａｎｄ ｔｈｕｓ ａｖｏｉｄｉｎｇ ｍａｎｕａｌ ｉｎｔｅｒｖｅｎｔｉｏｎ， ａｎｄ ｓｏ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｅｆｆｉｃｉｅｎｃｙ ｉｓ ｅｆｆｅｃｔｉｖｅｌｙ ｉｎ⁃ ｃｒｅａｓｅｄ． Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔ ｒｅｓｕｌｔｓ ｌｏｏｋｉｎｇ ａｔ ｄｅｎｓｉｔｙ ｃｌｕｓｔｅｒｉｎｇ ｏｆ ｆｏｕｒ ｔｙｐｉｃａｌ ｄａｔａ ｓｅｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ｍｅｔｈｏｄ ｅｆｆｅｃｔｉｖｅｌｙ ｉｍｐｒｏｖｅｓ ｃｌｕｓｔｅｒｉｎｇ ａｃｃｕｒａｃｙ ｂｙ ８．８２５％ ａｎｄ ｒｅｄｕｃｅｓ ｔｈｅ ａｖｅｒａｇｅ ｔｉｍｅ ｏｆ ｃｌｕｓｔｅｒｉｎｇ ｂｙ ０．９２ ｓ． Ｋｅｙｗｏｒｄｓ：ｄｅｎｓｉｔｙ ｃｌｕｓｔｅｒｉｎｇ； ＤＢＳＣＡＮ； ｒｅｇｉｏｎ ｑｕｅｒｙ； ｇｌｏｂａｌ ｐａｒａｍｅｔｅｒｓ； ＫＮＮ ｄｉｓｔｒｉｂｕｔｉｏｎ； ｍａｔｈｅｍａｔｉｃａｌ ｓｔａｔｉｓ⁃ ｔｉｃｓ ａｎｄ ａｎａｌｙｓｉｓ 收稿日期：２０１４⁃１０⁃１３． 网络出版日期：２０１５⁃０９⁃３０． 基金项目：国家自然科学基金资助项目（６１３７３１２６）；江苏省产学研联合 创新资金－前瞻性联合研究基金资助项目（ＢＹ２０１３０１５⁃３３）． 通信作者：王杰锋． Ｅ⁃ｍａｉｌ：１８３５２５１３４２０＠ １６３．ｃｏｍ． 数据挖掘是一种从大量数据中发现感兴趣信息 的技术，聚类算法在数据挖掘应用中日益广泛。 其 中，基于密度的聚类算法可以发现任意形状的簇且 能够较好地处理噪声数据，越来越受到广泛的关注。 ＤＢＳＣＡＮ 算法能够发现任意形状的簇，并有效识别 离群点，但聚类之前需要人工选择 Ｅｐｓ 和 ｍｉｎＰｔｓ ２ 个参数。 当数据量增大时，要求较大的内存支持， Ｉ／ Ｏ消耗也很大；当空间聚类的密度不均匀，聚类间 距离相差很大时，聚类质量较差［１⁃３］ 。 针对 ＤＢＳＣＡＮ 算法在大型数据库与多密度数据集聚类精度低，计 算复杂度高，全局参数人工选取等问题，已有很多学 者进行了相关研究：Ｓ． Ｍｉｍａｒｏｇｌｕ 等［４］ 提出对位向 量使用裁剪技术，Ｈ． Ｊｉａｎｇ 等［５］ 提出一种基于划分 的 ＤＢＳＣＡＮ 算法，Ｂ． Ｂｏｒａｈ 等［６］ 提出一种改进的基 于抽样的 ＤＢＳＣＡＮ 算法，Ｄ． Ｋｅｌｌｎｅｒ ［７］提出基于格点 的 ＤＢＳＣＡＮ 算法，旨在解决 ＤＢＳＣＡＮ 算法在内存占 用，处理高维数据和密度分布不均数据聚类效果不
·94. 智能系统学报 第11卷 好等问题；H.F.Zhou、S.H.Yue、Y.Ma、S.JA- 题。实际上，对于密度聚类，在核心对象邻域内相当 HIRABAPKAR和Z.Y.Xiong等s-]基于数据的数 一部分种子对象可以被忽略，选择核心对象边界的 学统计特性，确定全局参数：B.Lim)提出一种基于 部分代表对象进行类的扩展，从而达到减少区域查 密度的快速聚类方法，按照特定维的坐标排序，选择 询频度的目的。 有序的未被标记的在核心对象邻域以外的点作为种 为了自适应确定合适的全局参数MinPts和 子扩展簇。综上所述，基于密度聚类算法的改进点 Eps,减少内存占用量和I/O消耗，提高DBSCAN的 主要集中在全局参数的选择以及提高密度聚类效率 计算效率，基于这些分析，本文提出一种改进的自 等。DBSCAN全局参数选择根据k-dist曲线人工确 适应快速算法(adaptive and fast density-based spatial 定，过程繁琐，实用性不高。其他基于统计分析的方 clustering of applications with noise,AF-DBSCAN), 法，部分以特定数据分布确定全局参数，而数据分布 在以自适应方式确定合理的全局参数MinPts和 存在不确定性，以特定分布规定不能准确反映数据 E即s,以及区域查询时选择部分具有代表性的对象作 的分布特性，使计算出的全局参数不准确：提高密度 为种子对象进行类扩展。改进算法描述如下：1)自 聚类效率主要集中在区域查询中的代表对象的选 适应确定全局参数Eps和MinPts;2)将所有点分类， 择，但是选择的代表对象进行区域查询时存在丢失 分别标记为核心点、边界点和噪声点；3)删除标记 对象现象，对丢失对象进行查漏操作，一定程度上增 处的噪声点：4)连接距离在Eps距离内的所有核心 加了区域查询的复杂度。 点，并归入到同一簇中：5)各个簇中的核心点对应 种子代表对象的选择：6)遍历数据集，根据选择的 DBSCAN算法及改进算法 代表对象进行区域查询，将边界点分入与之对应核 DBSCAN是一种经典的基于密度聚类算法[8]」 心点的簇中。如果数据集中所有点都被处理，算法 可以自动确定簇的数量，并能够发现任意形状的簇。 结束。 Eps近邻表示一个给定对象的Eps半径内的近邻称 2AF-DBSCAN聚类算法 为该对象的Eps近邻，表示为NEps(p): NEps(p)={q∈DI dist(p,q)≤Eps}(1) 2.1参数Eps与参数MinPts的确定 直接密度可达是指对于给定的MinPts和Eps, 由于密度衡量指标单一，本文算法数据集主要 从对象q可以直接密度可达P,需要满足的条件为 针对簇密度差异不明显的数据。根据输入数据集D p∈NEps(q),I NEps(q)I≥MinPts(2) 计算出距离分布矩阵DIST,如式(3)所示： DBSCAN算法的全局参数MinPts和Eps的选 DIST={dist(i,ji)I1≤i≤n,1≤j≤n}(3) 取依赖于人工干预，对密度分布均匀的数据根据k 式中：n为数据集D的对象数目；DIST.xm是一个n dist曲线升序排列后，人为选择曲线变化幅度开始 行和n列的实对称矩阵，其中每个元素表示数据集 陡升的点作为Eps参数，并且确定MinPts参数为固 D中对象i和对象j之间的距离。计算DIST中 定常量4，实施过程繁琐，依赖于人工干预。本文提 的每个元素的值，然后逐行按照升序排列。用 出一种全局参数自适应选择的方法，根据数据距离 DIST:表示DIST中第i列的的值，对DIST:中 空间的统计分布特性，统计出k-dst值的分布情况. 每一列进行升序排列得到KNN分布，如图1所示。 曲线拟合出分布曲线，通过计算拟合曲线拐点处对 3.0f 应的值，自适应确定出Es参数，并根据数据中每个 2.5 点Eps领域内点数的分布情况，计算出参数MinPts.。 DBSCAN以核心对象P来拓展一个簇，通过对 2.0 包含在P邻域内的点进行区域查询扩展簇。包含 1 在P邻域的对象相互交叉，Q是P的邻域内的一个 1.0 对象，如果它的邻域被P中其他对象的邻域所覆 盖，那么Q的区域查询操作就可以省略，Q不需要 0.5 作为种子对象用于类的扩展。因此，用于Q的区域 查询时间和Q作为核心对象的内存占用都可以被 0 20 406080100120140160 省去。而一个核心对象边界的对象更有利于作为候 按k-dist距离升序排列数据点个数 选对象被选为种子，因为内部对象邻域往往会被外 图1KNN分布 部对象的邻域覆盖。因此，抽样种子实际上是选择 Fig.1 KNN distribution 的代表对象能够准确描绘出核心对象邻域形状的问
好等 问 题； Ｈ． Ｆ． Ｚｈｏｕ、 Ｓ． Ｈ． Ｙｕｅ、 Ｙ． Ｍａ、 Ｓ． ＪＡ⁃ ＨＩＲＡＢＡＰＫＡＲ 和 Ｚ． Ｙ． Ｘｉｏｎｇ 等［８⁃１２］ 基于数据的数 学统计特性，确定全局参数；Ｂ． Ｌｉｕ ［１３］提出一种基于 密度的快速聚类方法，按照特定维的坐标排序，选择 有序的未被标记的在核心对象邻域以外的点作为种 子扩展簇。 综上所述，基于密度聚类算法的改进点 主要集中在全局参数的选择以及提高密度聚类效率 等。 ＤＢＳＣＡＮ 全局参数选择根据 ｋ⁃ｄｉｓｔ 曲线人工确 定，过程繁琐，实用性不高。 其他基于统计分析的方 法，部分以特定数据分布确定全局参数，而数据分布 存在不确定性，以特定分布规定不能准确反映数据 的分布特性，使计算出的全局参数不准确；提高密度 聚类效率主要集中在区域查询中的代表对象的选 择，但是选择的代表对象进行区域查询时存在丢失 对象现象，对丢失对象进行查漏操作，一定程度上增 加了区域查询的复杂度。 １ ＤＢＳＣＡＮ 算法及改进算法 ＤＢＳＣＡＮ 是一种经典的基于密度聚类算法［８］ ， 可以自动确定簇的数量，并能够发现任意形状的簇。 Ｅｐｓ 近邻表示一个给定对象的 Ｅｐｓ 半径内的近邻称 为该对象的 Ｅｐｓ 近邻，表示为 ＮＥｐｓ（ｐ）： ＮＥｐｓ（ｐ） ＝ ｛ｑ ∈ Ｄ ｜ ｄｉｓｔ（ｐ，ｑ） ≤ Ｅｐｓ｝ （１） 直接密度可达是指对于给定的 ＭｉｎＰｔｓ 和 Ｅｐｓ， 从对象 ｑ 可以直接密度可达 ｐ，需要满足的条件为 ｐ ∈ ＮＥｐｓ（ｑ）， ｜ ＮＥｐｓ（ｑ） ｜ ≥ ＭｉｎＰｔｓ （２） ＤＢＳＣＡＮ 算法的全局参数 ＭｉｎＰｔｓ 和 Ｅｐｓ 的选 取依赖于人工干预，对密度分布均匀的数据根据 ｋ⁃ ｄｉｓｔ 曲线升序排列后，人为选择曲线变化幅度开始 陡升的点作为 Ｅｐｓ 参数，并且确定 ＭｉｎＰｔｓ 参数为固 定常量 ４，实施过程繁琐，依赖于人工干预。 本文提 出一种全局参数自适应选择的方法，根据数据距离 空间的统计分布特性，统计出 ｋ⁃ｄｉｓｔ 值的分布情况， 曲线拟合出分布曲线，通过计算拟合曲线拐点处对 应的值，自适应确定出 Ｅｐｓ 参数，并根据数据中每个 点 Ｅｐｓ 领域内点数的分布情况，计算出参数 ＭｉｎＰｔｓ。 ＤＢＳＣＡＮ 以核心对象 Ｐ 来拓展一个簇，通过对 包含在 Ｐ 邻域内的点进行区域查询扩展簇。 包含 在 Ｐ 邻域的对象相互交叉，Ｑ 是 Ｐ 的邻域内的一个 对象，如果它的邻域被 Ｐ 中其他对象的邻域所覆 盖，那么 Ｑ 的区域查询操作就可以省略，Ｑ 不需要 作为种子对象用于类的扩展。 因此，用于 Ｑ 的区域 查询时间和 Ｑ 作为核心对象的内存占用都可以被 省去。 而一个核心对象边界的对象更有利于作为候 选对象被选为种子，因为内部对象邻域往往会被外 部对象的邻域覆盖。 因此，抽样种子实际上是选择 的代表对象能够准确描绘出核心对象邻域形状的问 题。 实际上，对于密度聚类，在核心对象邻域内相当 一部分种子对象可以被忽略，选择核心对象边界的 部分代表对象进行类的扩展，从而达到减少区域查 询频度的目的。 为了自适应确定合适的全局参数 ＭｉｎＰｔｓ 和 Ｅｐｓ，减少内存占用量和 Ｉ／ Ｏ 消耗，提高 ＤＢＳＣＡＮ 的 计算效率， 基于这些分析，本文提出一种改进的自 适应快速算法（ａｄａｐｔｉｖｅ ａｎｄ ｆａｓｔ ｄｅｎｓｉｔｙ⁃ｂａｓｅｄ ｓｐａｔｉａｌ ｃｌｕｓｔｅｒｉｎｇ ｏｆ ａｐｐｌｉｃａｔｉｏｎｓ ｗｉｔｈ ｎｏｉｓｅ，ＡＦ⁃ＤＢＳＣＡＮ），旨 在以自适应方式确定合理的全局参数 ＭｉｎＰｔｓ 和 Ｅｐｓ，以及区域查询时选择部分具有代表性的对象作 为种子对象进行类扩展。 改进算法描述如下：１）自 适应确定全局参数 Ｅｐｓ 和 ＭｉｎＰｔｓ；２）将所有点分类， 分别标记为核心点、边界点和噪声点；３） 删除标记 处的噪声点；４）连接距离在 Ｅｐｓ 距离内的所有核心 点，并归入到同一簇中；５） 各个簇中的核心点对应 种子代表对象的选择；６） 遍历数据集，根据选择的 代表对象进行区域查询，将边界点分入与之对应核 心点的簇中。 如果数据集中所有点都被处理，算法 结束。 ２ ＡＦ⁃ＤＢＳＣＡＮ 聚类算法 ２．１ 参数 Ｅｐｓ 与参数 ＭｉｎＰｔｓ 的确定 由于密度衡量指标单一，本文算法数据集主要 针对簇密度差异不明显的数据。 根据输入数据集 Ｄ 计算出距离分布矩阵 ＤＩＳＴｎ × ｎ ，如式（３）所示： ＤＩＳＴｎ×ｎ ＝ ｛ｄｉｓｔ（ｉ，ｊ） ｜ １ ≤ ｉ ≤ ｎ， １ ≤ ｊ ≤ ｎ｝ （３） 式中：ｎ 为数据集 Ｄ 的对象数目；ＤＩＳＴｎ × ｎ是一个 ｎ 行和 ｎ 列的实对称矩阵，其中每个元素表示数据集 Ｄ 中对象 ｉ 和对象 ｊ 之间的距离。 计算 ＤＩＳＴｎ × ｎ中 的每 个 元 素 的 值， 然 后 逐 行 按 照 升 序 排 列。 用 ＤＩＳＴｎ × ｉ表示 ＤＩＳＴｎ × ｎ中第 ｉ 列的的值，对 ＤＩＳＴｎ × ｉ中 每一列进行升序排列得到 ＫＮＮ 分布，如图 １ 所示。 图 １ ＫＮＮ 分布 Ｆｉｇ．１ ＫＮＮ ｄｉｓｔｒｉｂｕｔｉｏｎ ·９４· 智 能 系 统 学 报 第 １１ 卷
第1期 周治平，等：一种改进的自适应快速AF-DBSCAN聚类算法 ·95· 图1中，k=1,2,…,45,根据k-dist分布曲线可 其中，高斯曲线拟合方法的效果最佳，但是由 以看出，k=4的dist,曲线可以反映出其他dist曲线 于概率分布的拟合精度过低，不可用于全局参数 的形状。本文选择k=4的dist(k-最近邻距离)的 Eps的估计。拟合结果为SSE:312.7,R-square: 数据进行统计分析，dist,的概率分布图2所示。 0.6755,调整R-square:0.6514,RMSE:3.403,参数 SSE和RMSE越接近0拟合越准确；R-square和调 0.20 整后的R-square越接近于1越准确；高斯拟合曲线 0.18 0.16 如式(4)所示： 0.14 f(x)=a x exp(-((x-b)/c)2) (4) 0.12 0.10 根据KNN升序排列曲线确定Eps,对dist,曲线 0.08 进行拟合。对于升序排列得到KNN分布数据，采用 0.06 0.04 3种拟合方法进行曲线拟合。实验发现高斯拟合精 0.02 02030405000700 度高，但拟合阶数高，计算复杂度高：傅里叶拟合精 0.1 度不高：而多项式拟合不仅拟合阶数低，而且拟合精 归一化k-dist值 度高，计算复杂度低，拟合结果为SSE:0.04636,R 图2dist,(k=4)概率分布 square:0.9883,调整R-square:0.988,RMSE: Fig.2 Probability distribution of dist (k=4) 从图1可以看出，任何一条曲线都是在平缓变 0.01788,如图4所示。多项式曲线拟合如式(5) 化后急剧上升，dist中大部分值落在一个比较密集 所示。 f(x)=ax bx cx2+dx +e (5) 的区域内，因此可以判断ds,中大部分值应落在一 个比较密集的区域内（曲线平缓段）。如果可以通 1.0 ·isk升序排列数据点· 0.9 一多项式拟合 过数学方法找出dist,中平缓变化到急剧上升处的 0.8 点，或者dist概率分布最为密集的区域，则可确定扫 描半径参数Eps,所以本文选择图1中dist拐点处 的值为Eps。由图2可以得到dist的概率分布情 单0.5 况，假如能够通过数学方法找到分布曲线的峰值，也 04 可以用峰值点所对应的k-最近邻距离值（横坐标刻 0.3 度)作为Eps。 0.2 对于概率分布数据，通过分析数据集的统计特 0.1 50 100 150 性，建立统计模型对数据集进行曲线拟合[4。本文 升序排列数据点个数 通过实验对概率分布使用傅里叶、高斯和多项式3 图4多项式拟合曲线 种典型曲线拟合方法，如图3所示。 Fig.4 Polynomial fitting curves 25 归一化KNN距离分布 根据多项式拟合曲线，求解曲线的拐点，对y 多项式拟合 20 傅里叶拟合 求二次导可得f(x)”=12ax2+6bx+2c,求解二次导方 高斯拟合 15 程得x的解为，=-6±V36-96a 。由于较小的 24a 10 值为靠近边界的点，取x解中较大的值，舍去较小的 值，将其带入式(5)，可以得到Eps=f八xo)。Eps确 定后，需要确定MinPts的值。根据每个点邻域数据 点的统计分布特性，依次计算出每个点的Es邻域 的对象数量：计算数据对象的数学期望，即MinPts, 0.2 0.40.6 0.8 1.0 如式(6)所示： 归一化k-dist值 (6) 图3归一化KNN分布拟合曲线 n i=1 Fig.3 Fitting curves of normalized KNN distribution 式中：P,表示在点i的Eps邻域的点数
图 １ 中，ｋ ＝ １，２，…，４５，根据 ｋ⁃ｄｉｓｔ 分布曲线可 以看出，ｋ ＝ ４ 的 ｄｉｓｔ ４曲线可以反映出其他 ｄｉｓｔ ｋ曲线 的形状。 本文选择 ｋ ＝ ４ 的 ｄｉｓｔ ｋ（ ｋ⁃最近邻距离） 的 数据进行统计分析，ｄｉｓｔ ４ 的概率分布图 ２ 所示。 图 ２ ｄｉｓｔｋ（ｋ＝ ４）概率分布 Ｆｉｇ．２ Ｐｒｏｂａｂｉｌｉｔｙ ｄｉｓｔｒｉｂｕｔｉｏｎ ｏｆ ｄｉｓｔｋ（ｋ＝ ４） 从图 １ 可以看出，任何一条曲线都是在平缓变 化后急剧上升，ｄｉｓｔ ｋ中大部分值落在一个比较密集 的区域内，因此可以判断 ｄｉｓｔ ｋ中大部分值应落在一 个比较密集的区域内（曲线平缓段）。 如果可以通 过数学方法找出 ｄｉｓｔ ｋ中平缓变化到急剧上升处的 点，或者 ｄｉｓｔ ｋ概率分布最为密集的区域，则可确定扫 描半径参数 Ｅｐｓ，所以本文选择图 １ 中 ｄｉｓｔ ｋ拐点处 的值为 Ｅｐｓ。 由图 ２ 可以得到 ｄｉｓｔ ｋ 的概率分布情 况，假如能够通过数学方法找到分布曲线的峰值，也 可以用峰值点所对应的 ｋ⁃最近邻距离值（横坐标刻 度）作为 Ｅｐｓ。 对于概率分布数据，通过分析数据集的统计特 性，建立统计模型对数据集进行曲线拟合［１４］ 。 本文 通过实验对概率分布使用傅里叶、高斯和多项式 ３ 种典型曲线拟合方法，如图 ３ 所示。 图 ３ 归一化 ＫＮＮ 分布拟合曲线 Ｆｉｇ．３ Ｆｉｔｔｉｎｇ ｃｕｒｖｅｓ ｏｆ ｎｏｒｍａｌｉｚｅｄ ＫＮＮ ｄｉｓｔｒｉｂｕｔｉｏｎ 其中，高斯曲线拟合方法的效果最佳，但是由 于概率分布的拟合精度过低，不可用于全局参数 Ｅｐｓ 的 估 计。 拟 合 结 果 为 ＳＳＥ： ３１２． ７， Ｒ⁃ｓｑｕａｒｅ： ０．６７５ ５，调整 Ｒ⁃ｓｑｕａｒｅ：０．６５１ ４，ＲＭＳＥ：３．４０３，参数 ＳＳＥ 和 ＲＭＳＥ 越接近 ０ 拟合越准确；Ｒ⁃ｓｑｕａｒｅ 和调 整后的 Ｒ⁃ｓｑｕａｒｅ 越接近于 １ 越准确；高斯拟合曲线 如式（４）所示： ｆ（ｘ） ＝ ａ × ｅｘｐ（ － （（ｘ － ｂ） ／ ｃ） ２ ） （４） 根据 ＫＮＮ 升序排列曲线确定 Ｅｐｓ，对 ｄｉｓｔ ４ 曲线 进行拟合。 对于升序排列得到 ＫＮＮ 分布数据，采用 ３ 种拟合方法进行曲线拟合。 实验发现高斯拟合精 度高，但拟合阶数高，计算复杂度高；傅里叶拟合精 度不高；而多项式拟合不仅拟合阶数低，而且拟合精 度高，计算复杂度低，拟合结果为 ＳＳＥ：０．０４６ ３６，Ｒ⁃ ｓｑｕａｒｅ： ０．９８８ ３， 调 整 Ｒ⁃ｓｑｕａｒｅ： ０．９８８， ＲＭＳＥ： ０．０１７ ８８，如图 ４ 所示。 多项式曲线拟合如式（ ５） 所示。 ｆ（ｘ） ＝ ａｘ ４ ＋ ｂｘ ３ ＋ ｃｘ ２ ＋ ｄｘ ＋ ｅ （５） 图 ４ 多项式拟合曲线 Ｆｉｇ．４ Ｐｏｌｙｎｏｍｉａｌ ｆｉｔｔｉｎｇ ｃｕｒｖｅｓ 根据多项式拟合曲线，求解曲线的拐点，对 ｙ 求二次导可得 ｆ（ｘ）″＝ １２ａｘ ２＋６ｂｘ＋２ｃ，求解二次导方 程得 ｘ 的解为 ｘ０ ＝ －６ｂ± ３６ｂ ２－９６ａｃ ２４ａ 。 由于较小的 值为靠近边界的点，取 ｘ 解中较大的值，舍去较小的 值，将其带入式（５），可以得到 Ｅｐｓ ＝ ｆ（ ｘ０ ）。 Ｅｐｓ 确 定后，需要确定 ＭｉｎＰｔｓ 的值。 根据每个点邻域数据 点的统计分布特性，依次计算出每个点的 Ｅｐｓ 邻域 的对象数量；计算数据对象的数学期望，即 ＭｉｎＰｔｓ， 如式（６）所示： ＭｉｎＰｔｓ ＝ １ ｎ ∑ ｎ ｉ ＝ １ Ｐｉ （６） 式中：Ｐｉ 表示在点 ｉ 的 Ｅｐｓ 邻域的点数。 第 １ 期 周治平，等：一种改进的自适应快速 ＡＦ⁃ＤＢＳＣＡＮ 聚类算法 ·９５·
·96. 智能系统学报 第11卷 本文将密度聚类算法与基于统计模型相结合， 3实验与分析 基于数理统计理论，假定数据集由统计过程产生，并 通过找出最佳拟合模型来描述数据集，自适应计算 本文算法采用了Java语言，在Windows XP系 出最优全局参数Eps和Minpts。 统和eclipse环境下运行，PC机硬件配置：Pentium 2.2种子代表对象的选择 (R)CPU,3GB内存，300GB硬盘。为了验证本文 本文提出一种改进的基于DBSCAN的快速聚 改进算法的有效性，根据数据集的维度、数据量和密 类算法，在通过选用核心对象附近区域包含的所有 度分布3种标准进行数据库的选择，选取UCI数据 对象的代表对象作为种子对象扩展类，减少了区域 库中的4种典型数据集ris、Wine、Glass和cmc。根 查询的次数，减低了聚类时间和/0开销。 据聚类准确度和时间特性分析2项指标对DB- 对于一个给出Eps和MinPts的核心对象P,为 SCAN、I-DBSCANU8劉和AF-DBSCAN算法性能进行比 了便于阐述，仅考虑二维对象，算法可用于其他大于 较分析，其中聚类准确度采用F-Measure)。DB- 二维的高维对象。代表对象选择过多则难以发挥算 SCAN中根据k-dist曲线，选取dist,曲线图进行参数 法效率，选择过少则容易造成对象丢失，影响算法聚 Eps值的确定，如图5所示。 类质量。FDBSCAN[5]算法在区域查询后，在第1轮 根据图5中平缓变化后急剧上升处对应的k 核心点区域查询时无丢失对象现象，而在以种子对 dist值作为全局参数Eps的值，且Minpts值设为4。 象进行类扩展时，产生丢失对象，因此需要选择足够 得到4种数据集ris、Wine、Glass和cmc的(Minpts, 多的代表对象：而I-DBSCAN[6]在二维数据中采用 Eps)分别为(4,0.436)、(4,27.330)、(4,3.700)和 至多8个代表对象，不存在对象丢失的情况。本文 (4.1.732)。 结合FDBSCAN与I-DBSCAN,第1轮区域查询时采 用4个代表对象进行类扩展，继续扩展类时，选择8 1.0r 个代表对象进行类扩展。本算法在提高查询效率的 0.9 基础上，解决了类扩展时丢失对象的问题。 0.8 0.7 本文提出的代表对象选择方式如下：以核心对 0.6 象p为中心，Eps为半径画圆，以对象p为原点画坐 0.5 标系交圆周于A、C、E和G4点，再画2条分别与x 0.4 轴成45°和135°角的直径交圆周于B、D、F和H4 0.3 点。第1轮选择代表对象时，以核心点边界的A、C、 0.2 0.1 E和G点为参照，在p的Eps区域中分别选择离A、 0 C、E和G点最近的点作为代表对象。当对于不同 20 40 6080100120140160 数据点个数 参照点存在离其距离最近的点为同一点时，此点只 能被选择1次，且属于第1个参考点的代表对象。 (a)is数据集 如果对象是n维数据，则至多可以选择2n个代表 对象。 8 在继续扩展类选择代表对象时，以核心点边界 7 的A、B、C、D、E、F、G和H点为参照点选择代表对 6 象，其原则为p的Es区域中选择离参考点对象最 5 近的点作为代表对象，即使1个代表对象到2个以 4 上的参考点都是最近的，它也只被选1次，且归入第 3 1个参考点的代表对象。因此，在二维空间范围内， 对任一对象的被选代表对象数最多为8个。一般情 况下，对n维空间，由于有3"-1个参考点和2个象 0 限，因此被选种子数最多为3”-1个，按照以上方式 20406080100120140160180200220 实现区域查询，有效提高聚类效率以及解决对象丢 数据点个数 失的问题。 (b)Glass数据集
本文将密度聚类算法与基于统计模型相结合， 基于数理统计理论，假定数据集由统计过程产生，并 通过找出最佳拟合模型来描述数据集，自适应计算 出最优全局参数 Ｅｐｓ 和 Ｍｉｎｐｔｓ。 ２．２ 种子代表对象的选择 本文提出一种改进的基于 ＤＢＳＣＡＮ 的快速聚 类算法，在通过选用核心对象附近区域包含的所有 对象的代表对象作为种子对象扩展类，减少了区域 查询的次数，减低了聚类时间和 Ｉ／ Ｏ 开销。 对于一个给出 Ｅｐｓ 和 ＭｉｎＰｔｓ 的核心对象 Ｐ，为 了便于阐述，仅考虑二维对象，算法可用于其他大于 二维的高维对象。 代表对象选择过多则难以发挥算 法效率，选择过少则容易造成对象丢失，影响算法聚 类质量。 ＦＤＢＳＣＡＮ ［１５］算法在区域查询后，在第 １ 轮 核心点区域查询时无丢失对象现象，而在以种子对 象进行类扩展时，产生丢失对象，因此需要选择足够 多的代表对象；而 Ｉ⁃ＤＢＳＣＡＮ ［６］ 在二维数据中采用 至多 ８ 个代表对象，不存在对象丢失的情况。 本文 结合 ＦＤＢＳＣＡＮ 与 Ｉ⁃ＤＢＳＣＡＮ，第 １ 轮区域查询时采 用 ４ 个代表对象进行类扩展，继续扩展类时，选择 ８ 个代表对象进行类扩展。 本算法在提高查询效率的 基础上，解决了类扩展时丢失对象的问题。 本文提出的代表对象选择方式如下：以核心对 象 ｐ 为中心，Ｅｐｓ 为半径画圆，以对象 ｐ 为原点画坐 标系交圆周于 Ａ、Ｃ、Ｅ 和 Ｇ ４ 点，再画 ２ 条分别与 ｘ 轴成 ４５°和 １３５°角的直径交圆周于 Ｂ、Ｄ、Ｆ 和 Ｈ ４ 点。 第 １ 轮选择代表对象时，以核心点边界的 Ａ、Ｃ、 Ｅ 和 Ｇ 点为参照，在 ｐ 的 Ｅｐｓ 区域中分别选择离 Ａ、 Ｃ、Ｅ 和 Ｇ 点最近的点作为代表对象。 当对于不同 参照点存在离其距离最近的点为同一点时，此点只 能被选择 １ 次，且属于第 １ 个参考点的代表对象。 如果对象是 ｎ 维数据，则至多可以选择 ２ｎ 个代表 对象。 在继续扩展类选择代表对象时，以核心点边界 的 Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇ 和 Ｈ 点为参照点选择代表对 象，其原则为 ｐ 的 Ｅｐｓ 区域中选择离参考点对象最 近的点作为代表对象，即使 １ 个代表对象到 ２ 个以 上的参考点都是最近的，它也只被选 １ 次，且归入第 １ 个参考点的代表对象。 因此，在二维空间范围内， 对任一对象的被选代表对象数最多为 ８ 个。 一般情 况下，对 ｎ 维空间，由于有 ３ ｎ －１ 个参考点和 ２ ｎ个象 限，因此被选种子数最多为 ３ ｎ －１ 个，按照以上方式 实现区域查询，有效提高聚类效率以及解决对象丢 失的问题。 ３ 实验与分析 本文算法采用了 Ｊａｖａ 语言，在 Ｗｉｎｄｏｗｓ ＸＰ 系 统和 ｅｃｌｉｐｓｅ 环境下运行，ＰＣ 机硬件配置：Ｐｅｎｔｉｕｍ （Ｒ） ＣＰＵ，３ ＧＢ 内存， ３００ ＧＢ 硬盘。 为了验证本文 改进算法的有效性，根据数据集的维度、数据量和密 度分布 ３ 种标准进行数据库的选择，选取 ＵＣＩ 数据 库中的 ４ 种典型数据集 Ｉｒｉｓ、Ｗｉｎｅ、Ｇｌａｓｓ 和 ｃｍｃ。 根 据聚类准确度和时间特性分析 ２ 项指标对 ＤＢ⁃ ＳＣＡＮ、Ｉ⁃ＤＢＳＣＡＮ ［８］和 ＡＦ⁃ＤＢＳＣＡＮ 算法性能进行比 较分析，其中聚类准确度采用 Ｆ⁃Ｍｅａｓｕｒｅ ［１３］ 。 ＤＢ⁃ ＳＣＡＮ 中根据 ｋ⁃ｄｉｓｔ 曲线，选取 ｄｉｓｔ ４曲线图进行参数 Ｅｐｓ 值的确定，如图 ５ 所示。 根据图 ５ 中平缓变化后急剧上升处对应的 ｋ⁃ ｄｉｓｔ 值作为全局参数 Ｅｐｓ 的值，且 Ｍｉｎｐｔｓ 值设为 ４。 得到 ４ 种数据集 Ｉｒｉｓ、Ｗｉｎｅ、Ｇｌａｓｓ 和 ｃｍｃ 的（Ｍｉｎｐｔｓ， Ｅｐｓ）分别为（４，０．４３６）、（４，２７．３３０）、（４，３．７００） 和 （４，１．７３２）。 （ａ）Ｉｒｉｓ 数据集 （ｂ）Ｇｌａｓｓ 数据集 ·９６· 智 能 系 统 学 报 第 １１ 卷
第1期 周治平，等：一种改进的自适应快速AF-DBSCAN聚类算法 97 算法快，有效减少了密度聚类的时间。 6 表1实验比较 Table 1 Experiment comparison 数据集 算法 MinPts Eps 时间/s 精度 DBSCAN 0.436 0.342 0.7407 Iris I-DBSCAN 6 0.405 0.335 0.8803 AF-DBSCAN 7 0.389 0.157 0.8662 DBSACN 27.330 0.481 0.5994 Wine I-DBSCAN 6 22.890 0.467 0.5667 ×103 810121416 AF-DBSCAN 6 29.870 0.172 0.6091 数据点个数 DBSCAN 3.700 0.516 0.6561 (c)cmc数据集 Glass I-DBSCAN 4 2.980 0.525 0.6522 AF-DBSCAN 4 2.695 0.188 0.7879 200 DBSCAN 1.732 3.239 0.4491 I-DBSCAN 6 1.691 3.145 0.4491 3983 AF-DBSCAN 5 1.646 1.266 0.4491 4 结束语 60 本文针对DBSCAN算法的参数选取困难，计算 40 效率低以及区域查询中代表对象选择后类扩展易丢 20 失对象点等问题，提出一种改进的自适应快速AF 0 20 40 6080100120140160180 DBSCAN聚类算法，通过分析数据的KNN的数学统 数据点个数 计规律，辅助用户自适应确定全局参数Eps与 (d)Wine数据集 MinPts.。通过改进的区域查询方法，有效提高类扩 图5dist曲线 展的效率，AF-DBSCAN算法解决了DBSCAN算法 Fig.5 Curve of dist 人工干预，给定全局参数导致聚类质量恶化以及大 本文提出的AF-DBSCAN算法的(Minpts,Eps) 数据集计算效率低的问题。 分别为(7,0.389)、(6,29.870)、(4,2.695)和(5， 1.646)。4种数据集聚类结果如表1所示。由表1 参考文献： 可以看出，本文提出的AF-DBSCAN算法自适应计 [1]吉根林，姚瑶。一种分布式隐私保护的密度聚类算法 算出的全局参数减少了人为根据k-dist曲线确定全 [J].智能系统学报，2009,4(2)：137-141. 局参数Eps的误差及工作量，以及设定MinPts为固 JI Genlin,YAO Yao.Density-based privacy preserving dis- 定值4，而使聚类结果达不到全局最优的效果。通 tributed clustering algorithm[J].CAAI transactions on intel- 过比较分析4种数据集的聚类结果，AF-DBSCAN的 ligent systems,2009,4(2):137-141. F-Measure值均优于其他2种典型算法，尤其在Iris [2]SMITI A,ELOUEDI Z.DBSCAN-GM:An improved cluste- 和Glass数据集上，聚类精度比DBSCAN算法分别 ring method based on Gaussian means and DBSCAN tech- niques[C]//2012 IEEE 16th Intemational Conference on 高12.55%和13.18%。而I-DBSCAN算法规定数据 Intelligent Engineering Systems INES).Lisbon,2012: 符合泊松分布，对于不同数据集F-Measure值不稳 573-578 定，不能适应不同统计特性的数据集。由于密度衡 [3]ZHANG Jiashu,KEREKES J.An adaptive density-based 量指标单一，AF-DBSCAN算法适用于簇密度差异不 model for extracting surface returns from photon-counting la- 明显的数据集。经过区域查询改进后的AFDB- ser altimeter data[J].Geoscience and remote sensing let- SCAN算法，运行速度明显比DBSCAN和I-DBSCAN ters,2015,12(4):726-730
（ｃ）ｃｍｃ 数据集 （ｄ）Ｗｉｎｅ 数据集 图 ５ ｄｉｓｔ４ 曲线 Ｆｉｇ．５ Ｃｕｒｖｅ ｏｆ ｄｉｓｔ４ 本文提出的 ＡＦ⁃ＤＢＳＣＡＮ 算法的（Ｍｉｎｐｔｓ，Ｅｐｓ） 分别为（ ７，０． ３８９）、（ ６，２９． ８７０）、（ ４，２． ６９５） 和（ ５， １．６４６）。 ４ 种数据集聚类结果如表 １ 所示。 由表 １ 可以看出，本文提出的 ＡＦ⁃ＤＢＳＣＡＮ 算法自适应计 算出的全局参数减少了人为根据 ｋ⁃ｄｉｓｔ 曲线确定全 局参数 Ｅｐｓ 的误差及工作量，以及设定 ＭｉｎＰｔｓ 为固 定值 ４，而使聚类结果达不到全局最优的效果。 通 过比较分析 ４ 种数据集的聚类结果，ＡＦ⁃ＤＢＳＣＡＮ 的 Ｆ⁃Ｍｅａｓｕｒｅ 值均优于其他 ２ 种典型算法，尤其在 Ｉｒｉｓ 和 Ｇｌａｓｓ 数据集上，聚类精度比 ＤＢＳＣＡＮ 算法分别 高 １２．５５％和 １３．１８％。 而 Ｉ⁃ＤＢＳＣＡＮ 算法规定数据 符合泊松分布，对于不同数据集 Ｆ⁃Ｍｅａｓｕｒｅ 值不稳 定，不能适应不同统计特性的数据集。 由于密度衡 量指标单一，ＡＦ⁃ＤＢＳＣＡＮ 算法适用于簇密度差异不 明显的数据集。 经过区域查询改进后的 ＡＦ⁃ＤＢ⁃ ＳＣＡＮ 算法，运行速度明显比 ＤＢＳＣＡＮ 和 Ｉ⁃ＤＢＳＣＡＮ 算法快，有效减少了密度聚类的时间。 表 １ 实验比较 Ｔａｂｌｅ １ Ｅｘｐｅｒｉｍｅｎｔ ｃｏｍｐａｒｉｓｏｎ 数据集 算法 ＭｉｎＰｔｓ Ｅｐｓ 时间／ ｓ 精度 Ｉｒｉｓ ＤＢＳＣＡＮ ４ ０．４３６ ０．３４２ ０．７４０ ７ Ｉ⁃ＤＢＳＣＡＮ ６ ０．４０５ ０．３３５ ０．８８０３ ＡＦ⁃ＤＢＳＣＡＮ ７ ０．３８９ ０．１５７ ０．８６６ ２ Ｗｉｎｅ ＤＢＳＡＣＮ ４ ２７．３３０ ０．４８１ ０．５９９ ４ Ｉ⁃ＤＢＳＣＡＮ ６ ２２．８９０ ０．４６７ ０．５６６ ７ ＡＦ⁃ＤＢＳＣＡＮ ６ ２９．８７０ ０．１７２ ０．６０９ １ Ｇｌａｓｓ ＤＢＳＣＡＮ ４ ３．７００ ０．５１６ ０．６５６ １ Ｉ⁃ＤＢＳＣＡＮ ４ ２．９８０ ０．５２５ ０．６５２ ２ ＡＦ⁃ＤＢＳＣＡＮ ４ ２．６９５ ０．１８８ ０．７８７ ９ ｃｍｃ ＤＢＳＣＡＮ ４ １．７３２ ３．２３９ ０．４４９ １ Ｉ⁃ＤＢＳＣＡＮ ６ １．６９１ ３．１４５ ０．４４９ １ ＡＦ⁃ＤＢＳＣＡＮ ５ １．６４６ １．２６６ ０．４４９ １ ４ 结束语 本文针对 ＤＢＳＣＡＮ 算法的参数选取困难，计算 效率低以及区域查询中代表对象选择后类扩展易丢 失对象点等问题，提出一种改进的自适应快速 ＡＦ⁃ ＤＢＳＣＡＮ 聚类算法，通过分析数据的 ＫＮＮ 的数学统 计规律， 辅 助 用 户 自 适 应 确 定 全 局 参 数 Ｅｐｓ 与 ＭｉｎＰｔｓ。 通过改进的区域查询方法，有效提高类扩 展的效率，ＡＦ⁃ＤＢＳＣＡＮ 算法解决了 ＤＢＳＣＡＮ 算法 人工干预，给定全局参数导致聚类质量恶化以及大 数据集计算效率低的问题。 参考文献： ［１］吉根林， 姚瑶． 一种分布式隐私保护的密度聚类算法 ［Ｊ］． 智能系统学报， ２００９， ４（２）： １３７⁃１４１． ＪＩ Ｇｅｎｌｉｎ， ＹＡＯ Ｙａｏ． Ｄｅｎｓｉｔｙ⁃ｂａｓｅｄ ｐｒｉｖａｃｙ ｐｒｅｓｅｒｖｉｎｇ ｄｉｓ⁃ ｔｒｉｂｕｔｅｄ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌ⁃ ｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２００９， ４（２）： １３７⁃１４１． ［２］ＳＭＩＴＩ Ａ， ＥＬＯＵＥＤＩ Ｚ． ＤＢＳＣＡＮ⁃ＧＭ： Ａｎ ｉｍｐｒｏｖｅｄ ｃｌｕｓｔｅ⁃ ｒｉｎｇ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ Ｇａｕｓｓｉａｎ ｍｅａｎｓ ａｎｄ ＤＢＳＣＡＮ ｔｅｃｈ⁃ ｎｉｑｕｅｓ［ Ｃ］ ／ ／ ２０１２ ＩＥＥＥ １６ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｅｎｇｉｎｅｅｒｉｎｇ Ｓｙｓｔｅｍｓ （ ＩＮＥＳ ）． Ｌｉｓｂｏｎ， ２０１２： ５７３⁃５７８． ［３］ ＺＨＡＮＧ Ｊｉａｓｈｕ， ＫＥＲＥＫＥＳ Ｊ． Ａｎ ａｄａｐｔｉｖｅ ｄｅｎｓｉｔｙ⁃ｂａｓｅｄ ｍｏｄｅｌ ｆｏｒ ｅｘｔｒａｃｔｉｎｇ ｓｕｒｆａｃｅ ｒｅｔｕｒｎｓ ｆｒｏｍ ｐｈｏｔｏｎ⁃ｃｏｕｎｔｉｎｇ ｌａ⁃ ｓｅｒ ａｌｔｉｍｅｔｅｒ ｄａｔａ［ Ｊ］． Ｇｅｏｓｃｉｅｎｃｅ ａｎｄ ｒｅｍｏｔｅ ｓｅｎｓｉｎｇ ｌｅｔ⁃ ｔｅｒｓ， ２０１５， １２（４）： ７２６⁃７３０． 第 １ 期 周治平，等：一种改进的自适应快速 ＡＦ⁃ＤＢＳＣＡＮ 聚类算法 ·９７·
·98. 智能系统学报 第11卷 [4]MIMAROGLU S,AKSEHIRLI E.Improving DBSCAN's ex- [13]LIU Bing.A fast density-based clustering algorithm for ecution time by using a pruning technique on bit vectors[]. large databases C//2006 International Conference on Pattern Recognition Letters,2011,32(13):1572-1580. Machine Learning and Cybernetics.Dalian,China,2006: [5]JIANG Hua,LI Jing,YI Shenghe,et al.A new hybrid 996-1000. method based on partitioning-based DBSCAN and ant clus. [14]夏鲁宁.SA-DBSCAN:一种自适应基于密度聚类算法 tering[J.Expert systems with applications,2011,38(8): [J].中国科学院研究生院学报，2009,26(4)：530- 9373-9381 538. [6]BORAH B,BHATTACHARYYA D K.An improved sam- XIA Luning.SA-DBSCAN:A self-adaptive density-based pling-based DBSCAN for large spatial databases[C]//Pro- clustering algorithm[J].Journal of the graduate school of ceedings of International Conference on Intelligent Sensing the Chinese academy of sciences,2009,26(4):530-538. and Information Processing (ICISIP).Chennai,India, [15]周水庚，周傲英，曹晶，等.一种基于密度的快速聚类 2004:92-96. 算法[J].计算机研究与发展，2000,37(11)：1287- [7]KELLNER D,KLAPPSTEIN J,DIETMAYER K.Grid- 1292. based DBSCAN for clustering extended objects in radar data ZHOU Shuigeng,ZHOU Aoying,CAO Jing,et al.A fast [C]//2012 IEEE Intelligent Vehicles Symposium.Alcal de density-based clustering algorithmJ.Journal of computer Henares,Madrid,Spain,2012:365-370. research development,2000,37(11):1287-1292. [8]ZHOU Hongfang,Wang Peng,LI Hongyan.Research on a- 作者简介： daptive parameters determination in DBSCAN algorithm[J]. 周治平，男，1962年生，教授，博士， Journal of information computational science,2012,9 主要研究方向为检测技术与自动化装 (7):1967-1973. 置、信息安全等。 [9]YUE Shihong,LI Ping,GUO Jidong,et al.A statistical in- formation-based clustering approach in distance space[J]. Journal of Zhejiang university science,2005,6A(1):71- 78. [10]MA Yu,GAO Yuling,SONG Shaoyun.The algorithm of 王杰锋，男，1989年生，硕士研究 DBSCAN based on probability distribution[C]//5th Inter- 生，主要研究方向为智能信息处理。 national Symposium on IT in Medicine and Education.Xin- ing,China,2014:2785-2792. [11]JAHIRABADKAR S,KULKARNI P.Algorithm to deter- mine s-distance parameter in density based clustering[J]. Expert systems with applications,2014,41(6):2939- 朱书伟，男，1990年生，硕士研究 2946. 生，主要研究方向为数据挖掘与人工 [12]XIONG Zhongyang,CHEN Ruotian,ZHANG Yufang,et 智能。 al.Multi-density DBSCAN algorithm based on density lev- els partitioning[J].Journal of information and computa- tional science,2012,9(10):2739-2749
［４］ＭＩＭＡＲＯＧＬＵ Ｓ， ＡＫＳＥＨＩＲＬＩ Ｅ． Ｉｍｐｒｏｖｉｎｇ ＤＢＳＣＡＮｓ ｅｘ⁃ ｅｃｕｔｉｏｎ ｔｉｍｅ ｂｙ ｕｓｉｎｇ ａ ｐｒｕｎｉｎｇ ｔｅｃｈｎｉｑｕｅ ｏｎ ｂｉｔ ｖｅｃｔｏｒｓ［Ｊ］． Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ Ｌｅｔｔｅｒｓ， ２０１１， ３２（１３）： １５７２⁃１５８０． ［５］ ＪＩＡＮＧ Ｈｕａ， ＬＩ Ｊｉｎｇ， ＹＩ Ｓｈｅｎｇｈｅ， ｅｔ ａｌ． Ａ ｎｅｗ ｈｙｂｒｉｄ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｐａｒｔｉｔｉｏｎｉｎｇ⁃ｂａｓｅｄ ＤＢＳＣＡＮ ａｎｄ ａｎｔ ｃｌｕｓ⁃ ｔｅｒｉｎｇ［Ｊ］． Ｅｘｐｅｒｔ ｓｙｓｔｅｍｓ ｗｉｔｈ ａｐｐｌｉｃａｔｉｏｎｓ， ２０１１， ３８（８）： ９３７３⁃９３８１． ［６］ ＢＯＲＡＨ Ｂ， ＢＨＡＴＴＡＣＨＡＲＹＹＡ Ｄ Ｋ． Ａｎ ｉｍｐｒｏｖｅｄ ｓａｍ⁃ ｐｌｉｎｇ⁃ｂａｓｅｄ ＤＢＳＣＡＮ ｆｏｒ ｌａｒｇｅ ｓｐａｔｉａｌ ｄａｔａｂａｓｅｓ［Ｃ］ ／ ／ Ｐｒｏ⁃ ｃｅｅｄｉｎｇｓ ｏｆ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｅｎｓｉｎｇ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ （ ＩＣＩＳＩＰ ）． Ｃｈｅｎｎａｉ， Ｉｎｄｉａ， ２００４： ９２⁃９６． ［７］ ＫＥＬＬＮＥＲ Ｄ， ＫＬＡＰＰＳＴＥＩＮ Ｊ， ＤＩＥＴＭＡＹＥＲ Ｋ． Ｇｒｉｄ⁃ ｂａｓｅｄ ＤＢＳＣＡＮ ｆｏｒ ｃｌｕｓｔｅｒｉｎｇ ｅｘｔｅｎｄｅｄ ｏｂｊｅｃｔｓ ｉｎ ｒａｄａｒ ｄａｔａ ［Ｃ］ ／ ／ ２０１２ ＩＥＥＥ Ｉｎｔｅｌｌｉｇｅｎｔ Ｖｅｈｉｃｌｅｓ Ｓｙｍｐｏｓｉｕｍ． Ａｌｃａｌ ｄｅ Ｈｅｎａｒｅｓ， Ｍａｄｒｉｄ， Ｓｐａｉｎ， ２０１２： ３６５⁃３７０． ［８］ＺＨＯＵ Ｈｏｎｇｆａｎｇ， Ｗａｎｇ Ｐｅｎｇ， ＬＩ Ｈｏｎｇｙａｎ． Ｒｅｓｅａｒｃｈ ｏｎ ａ⁃ ｄａｐｔｉｖｅ ｐａｒａｍｅｔｅｒｓ ｄｅｔｅｒｍｉｎａｔｉｏｎ ｉｎ ＤＢＳＣＡＮ ａｌｇｏｒｉｔｈｍ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｉｎｆｏｒｍａｔｉｏｎ ＆ ｃｏｍｐｕｔａｔｉｏｎａｌ ｓｃｉｅｎｃｅ， ２０１２， ９ （７）： １９６７⁃１９７３． ［９］ＹＵＥ Ｓｈｉｈｏｎｇ， ＬＩ Ｐｉｎｇ， ＧＵＯ Ｊｉｄｏｎｇ， ｅｔ ａｌ． Ａ ｓｔａｔｉｓｔｉｃａｌ ｉｎ⁃ ｆｏｒｍａｔｉｏｎ⁃ｂａｓｅｄ ｃｌｕｓｔｅｒｉｎｇ ａｐｐｒｏａｃｈ ｉｎ ｄｉｓｔａｎｃｅ ｓｐａｃｅ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｚｈｅｊｉａｎｇ ｕｎｉｖｅｒｓｉｔｙ ｓｃｉｅｎｃｅ， ２００５， ６Ａ（ １）：７１⁃ ７８． ［１０］ＭＡ Ｙｕ， ＧＡＯ Ｙｕｌｉｎｇ， ＳＯＮＧ Ｓｈａｏｙｕｎ． Ｔｈｅ ａｌｇｏｒｉｔｈｍ ｏｆ ＤＢＳＣＡＮ ｂａｓｅｄ ｏｎ ｐｒｏｂａｂｉｌｉｔｙ ｄｉｓｔｒｉｂｕｔｉｏｎ［Ｃ］ ／ ／ ５ｔｈ Ｉｎｔｅｒ⁃ ｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ ＩＴ ｉｎ Ｍｅｄｉｃｉｎｅ ａｎｄ Ｅｄｕｃａｔｉｏｎ． Ｘｉｎ⁃ ｉｎｇ， Ｃｈｉｎａ， ２０１４： ２７８５⁃２７９２． ［１１］ ＪＡＨＩＲＡＢＡＤＫＡＲ Ｓ， ＫＵＬＫＡＲＮＩ Ｐ． Ａｌｇｏｒｉｔｈｍ ｔｏ ｄｅｔｅｒ⁃ ｍｉｎｅ ε⁃ｄｉｓｔａｎｃｅ ｐａｒａｍｅｔｅｒ ｉｎ ｄｅｎｓｉｔｙ ｂａｓｅｄ ｃｌｕｓｔｅｒｉｎｇ［ Ｊ］． Ｅｘｐｅｒｔ ｓｙｓｔｅｍｓ ｗｉｔｈ ａｐｐｌｉｃａｔｉｏｎｓ， ２０１４， ４１ （ ６）： ２９３９⁃ ２９４６． ［１２］ＸＩＯＮＧ Ｚｈｏｎｇｙａｎｇ， ＣＨＥＮ Ｒｕｏｔｉａｎ， ＺＨＡＮＧ Ｙｕｆａｎｇ， ｅｔ ａｌ． Ｍｕｌｔｉ⁃ｄｅｎｓｉｔｙ ＤＢＳＣＡＮ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｄｅｎｓｉｔｙ ｌｅｖ⁃ ｅｌｓ ｐａｒｔｉｔｉｏｎｉｎｇ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ ｃｏｍｐｕｔａ⁃ ｔｉｏｎａｌ ｓｃｉｅｎｃｅ， ２０１２， ９（１０）： ２７３９⁃２７４９． ［ １３］ ＬＩＵ Ｂｉｎｇ． Ａ ｆａｓｔ ｄｅｎｓｉｔｙ⁃ｂａｓｅｄ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｌａｒｇｅ ｄａｔａｂａｓｅｓ ［ Ｃ］ ／ ／ ２００６ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ ａｎｄ Ｃｙｂｅｒｎｅｔｉｃｓ． Ｄａｌｉａｎ， Ｃｈｉｎａ， ２００６： ９９６⁃１０００． ［１４］夏鲁宁． ＳＡ⁃ＤＢＳＣＡＮ：一种自适应基于密度聚类算法 ［Ｊ］． 中国科学院研究生院学报， ２００９， ２６ （ ４）： ５３０⁃ ５３８． ＸＩＡ Ｌｕｎｉｎｇ． ＳＡ⁃ＤＢＳＣＡＮ： Ａ ｓｅｌｆ⁃ａｄａｐｔｉｖｅ ｄｅｎｓｉｔｙ⁃ｂａｓｅｄ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｔｈｅ ｇｒａｄｕａｔｅ ｓｃｈｏｏｌ ｏｆ ｔｈｅ Ｃｈｉｎｅｓｅ ａｃａｄｅｍｙ ｏｆ ｓｃｉｅｎｃｅｓ， ２００９， ２６（４）： ５３０⁃５３８． ［１５］周水庚， 周傲英， 曹晶， 等． 一种基于密度的快速聚类 算法［ Ｊ］． 计算机研究与发展， ２０００， ３７（ １１）： １２８７⁃ １２９２． ＺＨＯＵ Ｓｈｕｉｇｅｎｇ， ＺＨＯＵ Ａｏｙｉｎｇ， ＣＡＯ Ｊｉｎｇ， ｅｔ ａｌ． Ａ ｆａｓｔ ｄｅｎｓｉｔｙ⁃ｂａｓｅｄ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒ ｒｅｓｅａｒｃｈ ＆ ｄｅｖｅｌｏｐｍｅｎｔ， ２０００， ３７（１１）： １２８７⁃１２９２． 作者简介： 周治平，男，１９６２ 年生，教授，博士， 主要研究方向为检测技术与自动化装 置、信息安全等。 王杰锋，男，１９８９ 年生，硕士研究 生，主要研究方向为智能信息处理。 朱书伟，男，１９９０ 年生，硕士研究 生，主要研究方向为数据挖掘与人工 智能。 ·９８· 智 能 系 统 学 报 第 １１ 卷