作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2021, Vol. 47 ›› Issue (2): 133-138. doi: 10.19678/j.issn.1000-3428.0057015

• 先进计算与数据处理 • 上一篇    下一篇

基于密度核心的出租车载客轨迹聚类算法

田智慧1,2, 马占宇1, 魏海涛2   

  1. 1. 郑州大学 信息工程学院, 郑州 450001;
    2. 郑州大学 地球科学与技术学院, 郑州 450052
  • 收稿日期:2019-12-25 修回日期:2020-02-15 出版日期:2021-02-15 发布日期:2020-02-20
  • 作者简介:田智慧(1965-),男,教授、博士,主研方向为数据挖掘、深度学习;马占宇,硕士研究生;魏海涛(通信作者),讲师、博士。
  • 基金资助:
    河南省重点研发与推广专项(科技攻关)(192102210124)。

Taxi Passenger Trajectory Clustering Algorithm Based on Density Core

TIAN Zhihui1,2, MA Zhanyu1, WEI Haitao2   

  1. 1. College of Information Engineering, Zhengzhou University, Zhengzhou 450001, China;
    2. College of Earth Science and Technology, Zhengzhou University, Zhengzhou 450052, China
  • Received:2019-12-25 Revised:2020-02-15 Online:2021-02-15 Published:2020-02-20

摘要: 目前常见的轨迹聚类大多基于OPTICS、DBSCAN和K-means等算法,但这些聚类方法的时间复杂度随着轨迹数量的增加会大幅上升。针对该问题,提出一种基于密度核心的轨迹聚类算法。通过引入密度核心的概念,设计轨迹密度计算函数以获取聚类簇的致密核心轨迹,同时利用出租车载客轨迹自身的方向和速度等属性提取轨迹特征点,减少轨迹数据量。在此基础上,根据聚类簇中致密核心轨迹与参与聚类轨迹的相似度距离判断轨迹的匹配程度,进而聚合相似轨迹,并将聚类结果储存在聚类节点中。实验结果表明,与TRACLUS和OPTICS聚类算法相比,该算法能够得到更准确的聚类效果,并且时间效率更高。

关键词: DBSCAN算法, 特征点, 密度核心, 相似度距离, 轨迹聚类

Abstract: The existing trajectory clustering methods are mostly based on OPTICS,DBSCAN,and K-means clustering algorithms,etc.,but their time complexity soars with the increase of the number of trajectories.To address the problem,this paper proposes a trajectory clustering algorithm based on density core.By introducing the concept of density core,a trajectory density calculation function is designed to obtain the dense core trajectory of the cluster.At the same time,the attributes of the taxi passenger trajectory,including the direction and speed,are used to extract the trajectory feature points to reduce the amount of trajectory data.Then based on the similarity distance between the dense core trajectories in the cluster and the participating clustering trajectories,the matching degree of the trajectories is judged,and then similar trajectories are aggregated.The clustering results are stored in the cluster nodes.Experimental results show that the proposed algorithm is more accurate and efficient than TRACLUS,OPTICS and other clustering algorithms.

Key words: DBSCAN algorithm, feature point, density core, similarity distance, trajectory clustering

中图分类号: