Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (10): 2946-2951.DOI: 10.11772/j.issn.1001-9081.2017.10.2946

Previous Articles     Next Articles

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

HAO Meiwei, DAI Hualin, HAO Kun   

  1. College of Computer and Information Engineering, Tianjin Chengjian University, Tianjin 300384, China
  • Received:2017-04-14 Revised:2017-06-21 Online:2017-10-10 Published:2017-10-16
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61571318).

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

郝美薇, 戴华林, 郝琨   

  1. 天津城建大学 计算机与信息工程学院, 天津 300384
  • 通讯作者: 郝美薇(1993-),女,新疆乌鲁木齐人,硕士研究生,主要研究方向:虚拟现实、大数据,E-mail:angelsamle@126.com
  • 作者简介:郝美薇(1993-),女,新疆乌鲁木齐人,硕士研究生,主要研究方向:虚拟现实、大数据;戴华林(1974-),男,湖南武冈人,教授,博士,主要研究方向:虚拟现实、数字图像处理;郝琨(1979-),女,河北临西人,副教授,博士,主要研究方向:网络性能优化、无线传感网络、大数据分析.
  • 基金资助:
    国家自然科学基金资助项目(61571318)。

Abstract: 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 results 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.

Key words: K-means algorithm, density-based, characteristics of vehicle activity, weight of density, initial clustering center, Between-Within Proportion (BWP) index

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

关键词: K-means算法, 基于密度, 车辆活动特征, 密度权值, 初始聚类中心, 类内类外划分指标

CLC Number: