基于密度的K-means算法在轨迹数据聚类中的优化

Optimization of density-based K-means algorithm in trajectory data clustering

针对传统的K-means算法无法预先明确聚类数目,对初始聚类中心选取敏感且易受离群孤点影响导致聚类结果稳定性和准确性欠佳的问题,提出一种改进的基于密度的K-means算法。该算法首先基于轨迹数据分布密度和增加轨迹数据关键点密度权值的方式选取高密度的轨迹数据点作为初始聚类中心进行K-means聚类,然后结合聚类有效函数类内类外划分指标对聚类结果进行评价,最后根据评价确定最佳聚类数目和最优聚类划分。理论研究与实验结果表明,该算法能够更好地提取轨迹关键点,保留关键路径信息,且与传统的K-means算法相比,聚类准确性提高了28个百分点,与具有噪声的基于密度的聚类算法相比,聚类准确性提高了17个百分点。所提算法在轨迹数据聚类中具有更好的稳定性和准确性。

Since the traditional K-means algorithm can hardly predefine the number of clusters, and performs sensitively to the initial clustering centers and outliers, which may result in unstable and inaccurate results, an improved density-based K- means algorithm was proposed. Firstly, high-density trajectory data points were selected as the initial clustering centers to perform K-means clustering by considering the density of the trajectory data distribution and increasing the weight of the density of important points. Secondly, the clustering results were evaluated by the Between-Within Proportion （BWP） index of cluster validity function. Finally, the optimal number of clusters and clustering were determined according to the clustering results evaluation. Theoretical researches and experimental results show that the improved algorithm can be better at extracting the trajectory key points and keeping the key path information. The accuracy of clustering resuhs was 28 percentage points higher than that of the traditional K-means algorithm and 17 percentage points higher than that of the Density-Based Spatial Clustering of Applications with Noise （DBSCAN） algorithm. The proposed algorithm has a better stability and a higher accuracy in trajectory data clustering.