一种改进的自适应快速AFDBSCAN聚类算法.PDF

第 １１卷第 １期　 　 　 　 　 　 　 　 　 　 　 　 　 　 智　 能　 系　 统　 学　 报　 　 　 　 　 　 　 　 　 　 　 　 　 　 Ｖｏｌ．１１№．１ ２０１６年２月　 　 　 　 　 　 　 　 　 　 　 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ　 　 　 　 　 　 　 　 　 　 　 　 Ｆｅｂ． ２０１６ ＤＯＩ：１０．１１９９２．ｔｉｓ．２０１４１００２１ 网络出版地址：ｈｔｔｐ：／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ／ ｋｃｍｓ／ ｄｅｔａｉｌ／ ２３．１５３８．ｔｐ１５５７．０２８．ｈｔｍｌ 一种改进的自适应快速ＡＦ⁃ＤＢＳＣＡＮ聚类算法 周治平，王杰锋，朱书伟，孙子文 （江南大学物联网工程学院，江苏无锡 ２１４１２２） 摘　 要：基于密度的ＤＢＳＣＡＮ聚类算法可以识别任意形状簇，但存在全局参数Ｅｐｓ与ＭｉｎＰｔｓ 的选择需人工干预，采 用的区域查询方式过程复杂且易丢失对象等问题，提出了一种改进的参数自适应以及区域快速查询的密度聚类算 法。 根据ＫＮＮ分布与数学统计分析自适应计算出最优全局参数Ｅｐｓ与ＭｉｎＰｔｓ，避免聚类过程中的人工干预，实现了 聚类过程的全自动化。 通过改进种子代表对象选取方式进行区域查询，无需漏检操作，有效提高了聚类的效率。 对 ４种典型数据集的密度聚类实验结果表明，本文算法使得聚类精度提高了８．８２５％，聚类的平均时间减少了０．９２ ｓ。 关键词：密度聚类；ＤＢＳＣＡＮ；区域查询；全局参数；ＫＮＮ分布；数学统计分析 中图分类号：ＴＰ１８１　 文献标志码：Ａ　 文章编号：１６７３⁃４７８５（２０１６）０１⁃００９３⁃０６ 中文引用格式：周治平，王杰锋，朱书伟，等．一种改进的自适应快速ＡＦ⁃ＤＢＳＣＡＮ聚类算法［Ｊ］． 智能系统学报，２０１６，１１（１）：９３⁃９８． 英文引用格式：ＺＨＯＵ Ｚｈｉｐｉｎｇ，ＷＡＮＧ Ｊｉｅｆｅｎｇ，ＺＨＵ Ｓｈｕｗｅｉ，ｅｔ ａｌ． Ａｎ ｉｍｐｒｏｖｅｄ ａｄａｐｔｉｖｅ ａｎｄ ｆａｓｔ ＡＦ⁃ＤＢＳＣＡＮ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏ⁃ ｒｉｔｈｍ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ，２０１６，１１（１）：９３⁃９８． Ａｎ ｉｍｐｒｏｖｅｄ ａｄａｐｔｉｖｅ ａｎｄ ｆａｓｔ ＡＦ⁃ＤＢＳＣＡＮ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ＺＨＯＵ Ｚｈｉｐｉｎｇ，ＷＡＮＧＪｉｅｆｅｎｇ，ＺＨＵ Ｓｈｕｗｅｉ，ＳＵＮ Ｚｉｗｅｎ （Ｓｃｈｏｏｌ ｏｆ Ｉｎｔｅｒｎｅｔ ｏｆ Ｔｈｉｎｇｓ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｊｉａｎｇｎａｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｗｕｘｉ ２１４１２２，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｄｅｎｓｉｔｙ⁃ｂａｓｅｄ ＤＢＳＣＡＮ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｃａｎ ｉｄｅｎｔｉｆｙ ｃｌｕｓｔｅｒｓｗｉｔｈ ａｒｂｉｔｒａｒｙ ｓｈａｐｅ，ｈｏｗｅｖｅｒ，ｔｈｅ ｃｈｏｉｃｅ ｏｆ ｔｈｅ ｇｌｏｂａｌ ｐａｒａｍｅｔｅｒｓＥｐｓａｎｄ ＭｉｎＰｔｓｒｅｑｕｉｒｅｓｍａｎｕａｌ ｉｎｔｅｒｖｅｎｔｉｏｎ，ｔｈｅｐｒｏｃｅｓｓｏｆ ｒｅｇｉｏｎａｌ ｑｕｅｒｙ ｉｓｃｏｍ⁃ ｐｌｅｘ ａｎｄ ｌｏｓｅｓ ｏｂｊｅｃｔｓ ｅａｓｉｌｙ． Ｔｈｅｒｅｆｏｒｅ，ａｎ ｉｍｐｒｏｖｅｄ ｄｅｎｓｉｔｙ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｗｉｔｈ ａｄａｐｔｉｖｅ ｐａｒａｍｅｔｅｒ ｆｏｒ ｆａｓｔ ｒｅｇｉｏｎａｌ ｑｕｅｒｉｅｓ ｉｓ ｐｒｏｐｏｓｅｄ． Ｕｓｉｎｇ ＫＮＮ ｄｉｓｔｒｉｂｕｔｉｏｎ ａｎｄ ｍａｔｈｅｍａｔｉｃａｌ ｓｔａｔｉｓｔｉｃａｌ ａｎａｌｙｓｉｓ，ｔｈｅ ｏｐｔｉｍａｌ ｇｌｏｂａｌ ｐａ⁃ ｒａｍｅｔｅｒｓ ＥｐｓａｎｄＭｉｎＰｔｓａｒｅａｄａｐｔｉｖｅｌｙ ｃａｌｃｕｌａｔｅｄ，ｓｏａｓｔｏａｖｏｉｄｍａｎｕａｌｉｎｔｅｒｖｅｎｔｉｏｎａｎｄｅｎａｂｌｅｆｕｌｌａｕｔｏｍａｔｉｏｎｏｆ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｐｒｏｃｅｓｓ． Ｔｈｅ ｒｅｇｉｏｎａｌ ｑｕｅｒｙ ｉｓ ｃｏｎｄｕｃｔｅｄ ｂｙ ｉｍｐｒｏｖｉｎｇ ｔｈｅ ｓｅｌｅｃｔｉｏｎ ｍａｎｎｅｒ ｏｆ ｔｈｅ ｏｂｊｅ