大规模数据集下基于DBSCAN算法的增量并行化快速聚类

摘要

Spatial temporal trajectory data mining is an important way to discover the behavior patterns of mobile objects.Aimed at the demand of massive trajectory data processing,an incremental parallelization fast clustering algorithm was proposed.Based on the number of data points,the algorithm divided the space grid by dichotomy,and combined the greedy algorithm to restructure the partition rationally to reasonably divide the data.It dealt with local clustering to obtain the merged candidate cluster sets.The candidate clusters of R *-tree indexes were merged to be judged and processed.An undirected acyclic graph model of the merged clusters was established and the data was globally re-labeled.The experimental results show that thealgorithm effectively reduces the elastic partition processing noise data and improves the quality of local clustering.The merging strategy adopting R *-tree index structure effectively improves the time efficiency of clustering,and has good clustering effect and realized the online processing of large-scale data.%时空轨迹数据挖掘是发现移动对象行为模式的重要方式.针对海量轨迹数据处理的需求,提出一种增量并行化快速聚类算法.算法基于数据点的数量采用二分法对空间网格分区,结合贪心算法弹性重组分区,合理进行数据划分;进行本地局部聚类,获得合并簇候选集;采用R*-tree索引候选簇进行合并判断并处理;建立合并簇的无向无环图模型,并进行数据的全局重标签.实验结果表明:算法的弹性分区处理能有效地减少噪点数据,提高局部聚类的质量,采用R *-tree索引结构的合并策略有效提高了聚类的时间效率,聚类效果好,能实现大规模数据的在线处理.