第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.（ｃ）ｃｍｃ 数据集 （ｄ）Ｗｉｎｅ 数据集 图 ５ ｄｉｓｔ４ 曲线 Ｆｉｇ．５ Ｃｕｒｖｅ ｏｆ ｄｉｓｔ４ 本文提出的 ＡＦ⁃ＤＢＳＣＡＮ 算法的（Ｍｉｎｐｔｓ，Ｅｐｓ） 分别为（ ７，０． ３８９）、（ ６，２９． ８７０）、（ ４，２． ６９５） 和（ ５， １．６４６）。 ４ 种数据集聚类结果如表 １ 所示。 由表 １ 可以看出，本文提出的 ＡＦ⁃ＤＢＳＣＡＮ 算法自适应计 算出的全局参数减少了人为根据 ｋ⁃ｄｉｓｔ 曲线确定全 局参数 Ｅｐｓ 的误差及工作量，以及设定 ＭｉｎＰｔｓ 为固 定值 ４，而使聚类结果达不到全局最优的效果。 通 过比较分析 ４ 种数据集的聚类结果，ＡＦ⁃ＤＢＳＣＡＮ 的 Ｆ⁃Ｍｅａｓｕｒｅ 值均优于其他 ２ 种典型算法，尤其在 Ｉｒｉｓ 和 Ｇｌａｓｓ 数据集上，聚类精度比 ＤＢＳＣＡＮ 算法分别 高 １２．５５％和 １３．１８％。 而 Ｉ⁃ＤＢＳＣＡＮ 算法规定数据 符合泊松分布，对于不同数据集 Ｆ⁃Ｍｅａｓｕｒｅ 值不稳 定，不能适应不同统计特性的数据集。 由于密度衡 量指标单一，ＡＦ⁃ＤＢＳＣＡＮ 算法适用于簇密度差异不 明显的数据集。 经过区域查询改进后的 ＡＦ⁃ＤＢ⁃ ＳＣＡＮ 算法，运行速度明显比 ＤＢＳＣＡＮ 和 Ｉ⁃ＤＢＳＣＡＮ 算法快，有效减少了密度聚类的时间。 表 １ 实验比较 Ｔａｂｌｅ １ Ｅｘｐｅｒｉｍｅｎｔ ｃｏｍｐａｒｉｓｏｎ 数据集 算法 ＭｉｎＰｔｓ Ｅｐｓ 时间／ ｓ 精度 Ｉｒｉｓ ＤＢＳＣＡＮ ４ ０．４３６ ０．３４２ ０．７４０ ７ Ｉ⁃ＤＢＳＣＡＮ ６ ０．４０５ ０．３３５ ０．８８０３ ＡＦ⁃ＤＢＳＣＡＮ ７ ０．３８９ ０．１５７ ０．８６６ ２ Ｗｉｎｅ ＤＢＳＡＣＮ ４ ２７．３３０ ０．４８１ ０．５９９ ４ Ｉ⁃ＤＢＳＣＡＮ ６ ２２．８９０ ０．４６７ ０．５６６ ７ ＡＦ⁃ＤＢＳＣＡＮ ６ ２９．８７０ ０．１７２ ０．６０９ １ Ｇｌａｓｓ ＤＢＳＣＡＮ ４ ３．７００ ０．５１６ ０．６５６ １ Ｉ⁃ＤＢＳＣＡＮ ４ ２．９８０ ０．５２５ ０．６５２ ２ ＡＦ⁃ＤＢＳＣＡＮ ４ ２．６９５ ０．１８８ ０．７８７ ９ ｃｍｃ ＤＢＳＣＡＮ ４ １．７３２ ３．２３９ ０．４４９ １ Ｉ⁃ＤＢＳＣＡＮ ６ １．６９１ ３．１４５ ０．４４９ １ ＡＦ⁃ＤＢＳＣＡＮ ５ １．６４６ １．２６６ ０．４４９ １ ４ 结束语 本文针对 ＤＢＳＣＡＮ 算法的参数选取困难，计算 效率低以及区域查询中代表对象选择后类扩展易丢 失对象点等问题，提出一种改进的自适应快速 ＡＦ⁃ ＤＢＳＣＡＮ 聚类算法，通过分析数据的 ＫＮＮ 的数学统 计规律， 辅 助 用 户 自 适 应 确 定 全 局 参 数 Ｅｐｓ 与 ＭｉｎＰｔｓ。 通过改进的区域查询方法，有效提高类扩 展的效率，ＡＦ⁃ＤＢＳＣＡＮ 算法解决了 ＤＢＳＣＡＮ 算法 人工干预，给定全局参数导致聚类质量恶化以及大 数据集计算效率低的问题。 参考文献： ［１］吉根林， 姚瑶． 一种分布式隐私保护的密度聚类算法 ［Ｊ］． 智能系统学报， ２００９， ４（２）： １３７⁃１４１． ＪＩ Ｇｅｎｌｉｎ， ＹＡＯ Ｙａｏ． Ｄｅｎｓｉｔｙ⁃ｂａｓｅｄ ｐｒｉｖａｃｙ ｐｒｅｓｅｒｖｉｎｇ ｄｉｓ⁃ ｔｒｉｂｕｔｅｄ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌ⁃ ｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２００９， ４（２）： １３７⁃１４１． ［２］ＳＭＩＴＩ Ａ， ＥＬＯＵＥＤＩ Ｚ． ＤＢＳＣＡＮ⁃ＧＭ： Ａｎ ｉｍｐｒｏｖｅｄ ｃｌｕｓｔｅ⁃ ｒｉｎｇ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ Ｇａｕｓｓｉａｎ ｍｅａｎｓ ａｎｄ ＤＢＳＣＡＮ ｔｅｃｈ⁃ ｎｉｑｕｅｓ［ Ｃ］ ／ ／ ２０１２ ＩＥＥＥ １６ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｅｎｇｉｎｅｅｒｉｎｇ Ｓｙｓｔｅｍｓ （ ＩＮＥＳ ）． Ｌｉｓｂｏｎ， ２０１２： ５７３⁃５７８． ［３］ ＺＨＡＮＧ Ｊｉａｓｈｕ， ＫＥＲＥＫＥＳ Ｊ． Ａｎ ａｄａｐｔｉｖｅ ｄｅｎｓｉｔｙ⁃ｂａｓｅｄ ｍｏｄｅｌ ｆｏｒ ｅｘｔｒａｃｔｉｎｇ ｓｕｒｆａｃｅ ｒｅｔｕｒｎｓ ｆｒｏｍ ｐｈｏｔｏｎ⁃ｃｏｕｎｔｉｎｇ ｌａ⁃ ｓｅｒ ａｌｔｉｍｅｔｅｒ ｄａｔａ［ Ｊ］． Ｇｅｏｓｃｉｅｎｃｅ ａｎｄ ｒｅｍｏｔｅ ｓｅｎｓｉｎｇ ｌｅｔ⁃ ｔｅｒｓ， ２０１５， １２（４）： ７２６⁃７３０． 第 １ 期 周治平，等：一种改进的自适应快速 ＡＦ⁃ＤＢＳＣＡＮ 聚类算法 ·９７·