第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. 用，处理高维数据和密度分布不均数据聚类效果不第 １１ 卷第 １ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．１ ２０１６ 年 ２ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｆｅｂ． ２０１６ ＤＯＩ：１０．１１９９２．ｔｉｓ．２０１４１００２１ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ｔｐ．２０１５０９３０．１５５７．０２８．ｈｔｍｌ 一种改进的自适应快速 ＡＦ⁃ＤＢＳＣＡＮ 聚类算法 周治平，王杰锋，朱书伟，孙子文 （江南大学 物联网工程学院，江苏 无锡 ２１４１２２） 摘 要：基于密度的 ＤＢＳＣＡＮ 聚类算法可以识别任意形状簇，但存在全局参数 Ｅｐｓ 与 ＭｉｎＰｔｓ 的选择需人工干预，采 用的区域查询方式过程复杂且易丢失对象等问题，提出了一种改进的参数自适应以及区域快速查询的密度聚类算 法。 根据 ＫＮＮ 分布与数学统计分析自适应计算出最优全局参数 Ｅｐｓ 与 ＭｉｎＰｔｓ，避免聚类过程中的人工干预，实现了 聚类过程的全自动化。 通过改进种子代表对象选取方式进行区域查询，无需漏检操作，有效提高了聚类的效率。 对 ４ 种典型数据集的密度聚类实验结果表明，本文算法使得聚类精度提高了 ８．８２５％，聚类的平均时间减少了０．９２ ｓ。 关键词：密度聚类；ＤＢＳＣＡＮ；区域查询；全局参数；ＫＮＮ 分布；数学统计分析 中图分类号：ＴＰ１８１ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１６）０１⁃００９３⁃０６ 中文引用格式：周治平，王杰锋，朱书伟，等．一种改进的自适应快速 ＡＦ⁃ＤＢＳＣＡＮ 聚类算法［Ｊ］． 智能系统学报， ２０１６， １１（１）： ９３⁃９８． 英文引用格式：ＺＨＯＵ Ｚｈｉｐｉｎｇ，ＷＡＮＧ Ｊｉｅｆｅｎｇ，ＺＨＵ Ｓｈｕｗｅｉ，ｅｔ ａｌ． Ａｎ ｉｍｐｒｏｖｅｄ ａｄａｐｔｉｖｅ ａｎｄ ｆａｓｔ ＡＦ⁃ＤＢＳＣＡＮ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏ⁃ ｒｉｔｈｍ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１６，１１（１）：９３⁃９８． Ａｎ ｉｍｐｒｏｖｅｄ ａｄａｐｔｉｖｅ ａｎｄ ｆａｓｔ ＡＦ⁃ＤＢＳＣＡＮ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ＺＨＯＵ Ｚｈｉｐｉｎｇ， ＷＡＮＧ Ｊｉｅｆｅｎｇ， ＺＨＵ Ｓｈｕｗｅｉ， ＳＵＮ Ｚｉｗｅｎ （Ｓｃｈｏｏｌ ｏｆ Ｉｎｔｅｒｎｅｔ ｏｆ Ｔｈｉｎｇｓ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｊｉａｎｇｎａｎ Ｕｎｉｖｅｒｓｉｔｙ， Ｗｕｘｉ ２１４１２２， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｄｅｎｓｉｔｙ⁃ｂａｓｅｄ ＤＢＳＣＡＮ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｃａｎ ｉｄｅｎｔｉｆｙ ｃｌｕｓｔｅｒｓ ｗｉｔｈ ａｒｂｉｔｒａｒｙ ｓｈａｐｅ， ｈｏｗｅｖｅｒ， ｔｈｅ ｃｈｏｉｃｅ ｏｆ ｔｈｅ ｇｌｏｂａｌ ｐａｒａｍｅｔｅｒｓ Ｅｐｓ ａｎｄ ＭｉｎＰｔｓ ｒｅｑｕｉｒｅｓ ｍａｎｕａｌ ｉｎｔｅｒｖｅｎｔｉｏｎ， ｔｈｅ ｐｒｏｃｅｓｓ ｏｆ ｒｅｇｉｏｎａｌ ｑｕｅｒｙ ｉｓ ｃｏｍ⁃ ｐｌｅｘ ａｎｄ ｌｏｓｅｓ ｏｂｊｅｃｔｓ ｅａｓｉｌｙ． Ｔｈｅｒｅｆｏｒｅ， ａｎ ｉｍｐｒｏｖｅｄ ｄｅｎｓｉｔｙ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｗｉｔｈ ａｄａｐｔｉｖｅ ｐａｒａｍｅｔｅｒ ｆｏｒ ｆａｓｔ ｒｅｇｉｏｎａｌ ｑｕｅｒｉｅｓ ｉｓ ｐｒｏｐｏｓｅｄ． Ｕｓｉｎｇ ＫＮＮ ｄｉｓｔｒｉｂｕｔｉｏｎ ａｎｄ ｍａｔｈｅｍａｔｉｃａｌ ｓｔａｔｉｓｔｉｃａｌ ａｎａｌｙｓｉｓ， ｔｈｅ ｏｐｔｉｍａｌ ｇｌｏｂａｌ ｐａ⁃ ｒａｍｅｔｅｒｓ Ｅｐｓ ａｎｄ ＭｉｎＰｔｓ ａｒｅ ａｄａｐｔｉｖｅｌｙ ｃａｌｃｕｌａｔｅｄ， ｓｏ ａｓ ｔｏ ａｖｏｉｄ ｍａｎｕａｌ ｉｎｔｅｒｖｅｎｔｉｏｎ ａｎｄ ｅｎａｂｌｅ ｆｕｌｌ ａｕｔｏｍａｔｉｏｎ ｏｆ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｐｒｏｃｅｓｓ． Ｔｈｅ ｒｅｇｉｏｎａｌ ｑｕｅｒｙ ｉｓ ｃｏｎｄｕｃｔｅｄ ｂｙ ｉｍｐｒｏｖｉｎｇ ｔｈｅ ｓｅｌｅｃｔｉｏｎ ｍａｎｎｅｒ ｏｆ ｔｈｅ ｏｂｊｅｃｔ， ｗｈｉｃｈ ｉｓ ｒｅｐｒｅｓｅｎｔｅｄ ｂｙ ａ ｓｅｅｄ ａｎｄ ｔｈｕｓ ａｖｏｉｄｉｎｇ ｍａｎｕａｌ ｉｎｔｅｒｖｅｎｔｉｏｎ， ａｎｄ ｓｏ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｅｆｆｉｃｉｅｎｃｙ ｉｓ ｅｆｆｅｃｔｉｖｅｌｙ ｉｎ⁃ ｃｒｅａｓｅｄ． Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔ ｒｅｓｕｌｔｓ ｌｏｏｋｉｎｇ ａｔ ｄｅｎｓｉｔｙ ｃｌｕｓｔｅｒｉｎｇ ｏｆ ｆｏｕｒ ｔｙｐｉｃａｌ ｄａｔａ ｓｅｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ｍｅｔｈｏｄ ｅｆｆｅｃｔｉｖｅｌｙ ｉｍｐｒｏｖｅｓ ｃｌｕｓｔｅｒｉｎｇ ａｃｃｕｒａｃｙ ｂｙ ８．８２５％ ａｎｄ ｒｅｄｕｃｅｓ ｔｈｅ ａｖｅｒａｇｅ ｔｉｍｅ ｏｆ ｃｌｕｓｔｅｒｉｎｇ ｂｙ ０．９２ ｓ． Ｋｅｙｗｏｒｄｓ：ｄｅｎｓｉｔｙ ｃｌｕｓｔｅｒｉｎｇ； ＤＢＳＣＡＮ； ｒｅｇｉｏｎ ｑｕｅｒｙ； ｇｌｏｂａｌ ｐａｒａｍｅｔｅｒｓ； ＫＮＮ ｄｉｓｔｒｉｂｕｔｉｏｎ； ｍａｔｈｅｍａｔｉｃａｌ ｓｔａｔｉｓ⁃ ｔｉｃｓ ａｎｄ ａｎａｌｙｓｉｓ 收稿日期：２０１４⁃１０⁃１３． 网络出版日期：２０１５⁃０９⁃３０． 基金项目：国家自然科学基金资助项目（６１３７３１２６）；江苏省产学研联合 创新资金－前瞻性联合研究基金资助项目（ＢＹ２０１３０１５⁃３３）． 通信作者：王杰锋． Ｅ⁃ｍａｉｌ：１８３５２５１３４２０＠ １６３．ｃｏｍ． 数据挖掘是一种从大量数据中发现感兴趣信息 的技术，聚类算法在数据挖掘应用中日益广泛。 其 中，基于密度的聚类算法可以发现任意形状的簇且 能够较好地处理噪声数据，越来越受到广泛的关注。 ＤＢＳＣＡＮ 算法能够发现任意形状的簇，并有效识别 离群点，但聚类之前需要人工选择 Ｅｐｓ 和 ｍｉｎＰｔｓ ２ 个参数。 当数据量增大时，要求较大的内存支持， Ｉ／ Ｏ消耗也很大；当空间聚类的密度不均匀，聚类间 距离相差很大时，聚类质量较差［１⁃３］ 。 针对 ＤＢＳＣＡＮ 算法在大型数据库与多密度数据集聚类精度低，计 算复杂度高，全局参数人工选取等问题，已有很多学 者进行了相关研究：Ｓ． Ｍｉｍａｒｏｇｌｕ 等［４］ 提出对位向 量使用裁剪技术，Ｈ． Ｊｉａｎｇ 等［５］ 提出一种基于划分 的 ＤＢＳＣＡＮ 算法，Ｂ． Ｂｏｒａｈ 等［６］ 提出一种改进的基 于抽样的 ＤＢＳＣＡＮ 算法，Ｄ． Ｋｅｌｌｎｅｒ ［７］提出基于格点 的 ＤＢＳＣＡＮ 算法，旨在解决 ＤＢＳＣＡＮ 算法在内存占 用，处理高维数据和密度分布不均数据聚类效果不