基于占空比的聚类算法评价指标研究

doi:10.3778/j.issn.1002-8331.2007-0298

摘要/Abstract

摘要： 基于密度的聚类算法（DBSCAN）是最有效的轨迹数据挖掘方法之一，但基于密度的聚类算法往往受到输入参数选择的限制。在轨迹数据挖掘中，聚类结果不仅受到类内距离和类间距离的影响，还受到聚类中坐标点个数的影响。因此，提出了一种新的基于内外占空比的集群有效性指标来平衡这三个因素，该指标可以自动选择密度聚类的输入参数，并在不同的数据集上形成有效的聚类，优化后的聚类方法可应用于出行者行为轨迹的深度分析和挖掘。实验结果证明，与传统的有效性指标相比，提出的基于占空比的评价指标能够优化输入参数，获得较好的出行者位置信息聚类结果。

关键词: DBSCAN算法, 有效性指数, 密度聚类, 轨迹聚类

Abstract: Density-based clustering （DBSCAN） is one of the most effective methods for trajectory data mining, but density-based clustering algorithms are often limited by the choice of input parameters. In the trajectory data mining, clustering results are not only affected by the within-class distance and between-class distance, but also by the number of coordinate points in the cluster. Therefore, this paper proposes a novel cluster validity index based on the internal and external duty cycle to balance the three parameters. In this way, the parameters of density clustering can be automatically selected, and effective clustering can be formed on different datasets. Then the clustering method is applied to the depth analysis and mining of travelers’ behavior trajectories. The experiments prove that compared with the traditional validity index, the evaluation function proposed can optimize input parameters and get better clustering results of user location information.

Key words: DBSCAN algorithm, validity index, density-based clustering, trajectory clustering

张欣环, 刘宏杰, 吴金洪, 施俊庆, 毛程远, 孟国连. 基于占空比的聚类算法评价指标研究[J]. 计算机工程与应用, 2022, 58(1): 175-181.

ZHANG Xinhuan, LIU Hongjie, WU Jinhong, SHI Junqing, MAO Chengyuan, MENG Guolian. Research on Evaluation Function of Clustering Algorithm Based on Duty Cycle#br#[J]. Computer Engineering and Applications, 2022, 58(1): 175-181.

参考文献

[1] ZHENG Y.Trajectory data mining：An overview[J].ACM Transactions on Intelligent Systems and Technology，2015，6（3）：1-41.
[2] CHENG D D，ZHU Q S，HUANG J L.A novel cluster validity index based on local cores[J].IEEE Transactions on Neural Networks & Learning Systems，2019，30（4）：985-999.
[3] WANG Z.Research on moving objects trajectories collection based on data mining[C]//Proceedings of 2017 International Conference on Smart Grid and Electrical Automation，2017：538-541.
[4] CHOONG M Y，CHIN R K Y，YEO K B，et al.Trajectory clustering for behavioral pattern learning in transportation surveillance[C]//Proceedings of 4th International Conference on Artificial Intelligence with Applications in Engineering and Technology，2014：199-203.
[5] SHARMA A.KNN-DBSCAN：Using K-nearest neighbor information for parameter-free density based clustering[C]//Proceedings of International Conference on Intelligent Computing，Instrumentation and Control Technologies （ICICICT’17），2017：787-792.
[6] HOU J，GAO H J，LI X.Dsets-DBSCAN：A parameter-free clustering algorithm[J].IEEE Transactions on Image Processing，2016，25（7）：3182-3193.
[7] DUNN J C.A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters[J].Journal of Cybernetics，1973，3（3）：32-57.
[8] DAVIES D L，BOULDIN D W.A cluster separation measure[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1979，1（2）：224-227.
[9] ROUSSEEUW P J.Silhouettes：A graphical aid to the interpretation and validation of cluster analysis[J].Journal of Computational & Applied Mathematics，1999，20：53-65.
[10] ZHOU S B，XU Z Y，LIU F.Method for determining the optimal number of clusters based on agglomerative hierarchical clustering[J].IEEE Transactions on Neural Networks & Learning Systems，2017，28（12）：3007-3017.
[11] KARO I M K，ADHINUGRAHA K M，HUDA A F.A cluster validity for spatial clustering based on Davies-Bouldin index and Polygon Dissimilarity function[C]//Proceedings of the 2nd International Conference on Informatics and Computing，2017：1-6.
[12] ACHARYA S，SAHA S，BANDYOPADHYAY S.Development of some line symmetry based cluster validity indices[C]//Proceedings of the International Conference on Soft Computing & Machine Intelligence，2014：24-27.
[13] THOMAS J C R，PE?AS M S，MORA M.New version of Davies-Bouldin index for clustering validation based on cylindrical distance[C]//Proceedings of the 32nd International Conference of the Chilean Computer Science Society，2013：49-53.
[14] 江玉玲，熊振南，唐基宏.基于轨迹段DBSCAN的船舶轨迹聚类算法[J].中国航海，2019，42（3）：1-5.
JIANG Y L，XIONG Z N，TANG J H.Ship trajectory clustering algorithm based on DBSCAN[J].Navigation of China，2019，42（3）：1-5.
[15] 周培培，丁庆海，罗海波，等.基于DBSCAN聚类算法的异常轨迹检测[J].红外与激光工程，2017，46（5）：230-237.
ZHOU P P，DING Q H，LUO H B，et al.Trajectory outlier detection based on DBSCAN clustering algorithm[J].Infrared and Laser Engineering，2017，46（5）：230-237.