留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种基于核距离的车辆轨迹点聚类方法

陆川伟 孙群 季晓林 徐立 温伯威 程绵绵

陆川伟, 孙群, 季晓林, 徐立, 温伯威, 程绵绵. 一种基于核距离的车辆轨迹点聚类方法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(7): 1082-1088. doi: 10.13203/j.whugis20180361
引用本文: 陆川伟, 孙群, 季晓林, 徐立, 温伯威, 程绵绵. 一种基于核距离的车辆轨迹点聚类方法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(7): 1082-1088. doi: 10.13203/j.whugis20180361
LU Chuanwei, SUN Qun, JI Xiaolin, XU Li, WEN Bowei, CHENG Mianmian. A Method of Vehicle Trajectory Points Clustering Based on Kernel Distance[J]. Geomatics and Information Science of Wuhan University, 2020, 45(7): 1082-1088. doi: 10.13203/j.whugis20180361
Citation: LU Chuanwei, SUN Qun, JI Xiaolin, XU Li, WEN Bowei, CHENG Mianmian. A Method of Vehicle Trajectory Points Clustering Based on Kernel Distance[J]. Geomatics and Information Science of Wuhan University, 2020, 45(7): 1082-1088. doi: 10.13203/j.whugis20180361

一种基于核距离的车辆轨迹点聚类方法

doi: 10.13203/j.whugis20180361
基金项目: 

国家自然科学基金 41571399

详细信息

A Method of Vehicle Trajectory Points Clustering Based on Kernel Distance

Funds: 

The National Natural Science Foundation of China 41571399

More Information
    Author Bio:

    LU Chuanwei, PhD candidate, specializes in trajectory data mining and map updating. E-mail: 19wei.90chuan@163.com

    Corresponding author: SUN Qun, PhD, professor. E-mail: 13503712102@163.com
  • 摘要: 基于聚类算法进行车辆轨迹点信息提取与挖掘,在高精度车道信息提取与更新、道路拥堵时空分析与治理、用户出行线路规划与推荐等应用中具有重要意义。针对现有聚类算法的不足,提出基于核距离的车辆轨迹点聚类方法。首先给出车辆轨迹点的定义,分析车辆轨迹的几何特征和轨迹聚类的要求,然后基于核函数的概念,推导核距离的计算过程,提出核距离密度聚类算法,重定义密度聚类算法中核邻域、核心对象等概念,最后以郑州市出租车轨迹数据进行验证。实验表明,聚类算法在减少参数数量、结果沿道路中心线对称分布、降低计算时间、提取长类簇等方面具有显著优势,可以有效地实现有向轨迹点的聚类。
  • 图  1  轨迹密度分布差异性问题

    Figure  1.  Problems of Difference in Trajectory Density Distribution

    图  2  轨迹朝向分布差异

    Figure  2.  Difference of Trajectory Orientation Distribution

    图  3  聚类结果局部对比图

    Figure  3.  Comparison of Clustering Results

    图  4  3种算法道路段提取结果局部对比图

    Figure  4.  Local Comparison of Road Sections Extraction of Three Algorithms

    表  1  实验区域轨迹点数量统计

    Table  1.   Statistics of Trajectory Points Number in Experimental Areas

    实验区域 轨迹点数量
    区域1(惠济区) 31 413
    区域2(管城区) 138 262
    区域3(金水区) 299 367
    下载: 导出CSV

    表  2  算法参数对比

    Table  2.   Comparison of Algorithmic Parameters

    算法 参数 说明
    K-DBSCAN ε = 0.02
    O-DBSCAN-1 ε=15 文献[11]中采用的参数
    α = 1
    O-DBSCAN-2 ε=50 本实验区域表现更优的参数
    α = 5
    下载: 导出CSV

    表  3  聚类结果的主要批标对比表

    Table  3.   Comparison of Main Indicators of Clustering Results

    K-DBSCAN O-DBSCAN-1 O-DBSCAN-2
    类别 区域1 区域2 区域3 域1区 区域2 区域3 域1区 区域2 区域3
    聚类点数 31 413 138 262 299 367 31 413 138 262 299 367 31 413 138 262 299 367
    离群点数 2 876 7 770 11 168 11 131 36 342 20 459 4 482 12 874 20 459
    离群点率/% 9.20 5.60 3.70 35.4 26.3 6.8 14.3 9.3 6.8
    CH指数 53 139.2 252.0 8.0 16.6 252.9 44.6 111.4 116.7
    下载: 导出CSV

    表  4  不同算法效率对比表

    Table  4.   Efficiency Comparison of Three Algorithms

    算法 区域1 区域2 区域3
    时间/s 空间/MB 时间/s 空间/MB 时间/s 空间/MB
    K-DBSCAN 181 224 898 887 2 646 2 537
    O-DBSCAN-1 246 156 1 292 306 3 695 2 536
    O-DBSCAN-2 276 233 1 624 869 4 873 2 588
    下载: 导出CSV

    表  5  3种算法提取的路段对比表

    Table  5.   Comparison of Road Sections of Three Algorithms

    算法 K-DBSCAN O-DBSCAN-1 O-DBSCAN-2
    区域1 区域2 区域3 区域1 区域2 区域3 区域1 区域2 区域3
    路段数 290 1 050 1 680 293 1 542 3 397 353 1 209 2 481
    < 100 m 32 214 1 578 243 1 227 2 729 181 685 2 432
    [100, 200]m 88 380 70 35 230 459 111 306 34
    > 200 m 170 456 32 15 85 209 61 218 15
    路段总长度/km 100.3 328.3 566.7 22.7 125.1 296.6 53.7 203.3 426.7
    下载: 导出CSV
  • [1] Edelkamp S, Schrödl S. Route Planning and Map Inference with Global Positioning Traces[M]. Berlin, Heidelberg:Springer, 2003:128-151
    [2] Schroedl S, Wagstaff K, Rogers S, et al. Mining GPS Traces for Map Refinement[J]. Data Mining & Knowledge Discovery, 2004, 9(1):59-87 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=5f872aa3ffffd2e24322cd0bea2c84bf
    [3] Worrall S, Nebot E. Automated Process for Generating Digitised Maps Through GPS Data Compression [C]. Australasian Conference on Robotics and Automation, Brisbane, Australian, 2007
    [4] Jang S, Kim T, Lee E. Map Generation System with Lightweight GPS Trace Data[C]. International Conference on Advanced Communication Technology, Gangwon-do, South Korea, 2010
    [5] Cao L, Krumm J. From GPS Traces to a Routable Road Map[C]. 17th ACM Sigspatial International Symposium on Advances in Geographic Information Systems, Seattle, Washington, US, 2009
    [6] Niehöfer B, Burda R, Wietfeld C, et al. GPS Community Map Generation for Enhanced Routing Methods Based on Trace-Collection by Mobile Phones[C]. 1st International Conference on Advances in Satellite and Space Communications, Colmar, France, 2009
    [7] Davies J J, Beresford A R, Hopper A. Scalable, Distributed, Real-Time Map Generation[J]. IEEE Pervasive Computing, 2006, 5(4):47-54 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=053c6bb6e767581aa4714f5efd09b2e2
    [8] Wu J W, Zhu Y, Tao K, et al. Detecting Road Intersections from Coarse-gained GPS Traces Based on Clustering[J]. Journal of Computers, 2013, 8(11):2 959-2 965 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=a058ed49728b7062baa440525d14be32
    [9] 马超, 孙群, 陈换新, 等.利用路段分类识别复杂道路交叉口[J].武汉大学学报·信息科学版, 2016, 41(9): 1 232-1 237 doi:  10.13203/j.whugis20160073

    Ma Chao, Sun Qun, Chen Huanxin, et al. Recognition of Road Junctions Based on Road Classification Method[J]. Geomatics and Information Science of Wuhan University, 2016, 41(9):1 232-1 237 doi:  10.13203/j.whugis20160073
    [10] 杨伟, 艾廷华.众源车辆轨迹加油停留行为探测与加油站点提取[J].测绘学报, 2017, 46(7):918-927 http://d.old.wanfangdata.com.cn/Periodical/chxb201707015

    Yang Wei, Ai Tinghua. Refueling Stop Activity Detection and Gas Station Extraction Using Crowdsourcing Vehicle Trajectory Data[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(7):918-927 http://d.old.wanfangdata.com.cn/Periodical/chxb201707015
    [11] Qiu J, Wang R, Wang X. Inferring Road Maps from Sparsely-Sampled GPS Traces[J]. Journal of Location Based Services, 2014, 10(2):111-124 http://d.old.wanfangdata.com.cn/NSTLHY/NSTL_HYCC0214236601/
    [12] Liu X, Zhu Y, Wang Y, et al. Road Recognition Using Coarse-grained Vehicular Traces[R]. Technical Report HPL-2012-26, CA, USA, 2012
    [13] 杨伟, 艾廷华.基于众源轨迹数据的道路中心线提取[J].地理与地理信息科学, 2016, 32(3):1-7 doi:  10.3969/j.issn.1672-0504.2016.03.001

    Yang Wei, Ai Tinghua. Road Centerline Extraction from Crowdsourcing Trajectory Data[J]. Geography and Geo-Information Science, 2016, 32(3):1-7 doi:  10.3969/j.issn.1672-0504.2016.03.001
    [14] 李军, 秦其明, 游林, 等.利用浮动车数据提取停车场位置[J].武汉大学学报·信息科学版, 2013, 38(5):599-603 http://ch.whu.edu.cn/article/id/2637

    Li Jun, Qin Qiming, You Lin, et al. Parking Lot Extraction Method Based on Floating Car[J]. Geomatics and Information Science of Wuhan University, 2013, 38(5):599-603 http://ch.whu.edu.cn/article/id/2637
    [15] 唐炉亮, 段倩, 阚子涵, 等.出租车交接班行为识别与时空分布研究[J].地球信息科学学报, 2017, 19(2):167-175 http://d.old.wanfangdata.com.cn/Periodical/dqxxkx201702004

    Tang Luliang, Duan Qian, Kan Zihan, et al. Study on Identification and Space-time Distribution Analysis of Taxi Shift Behavior[J]. Journal of Geoinformation Science, 2017, 19(2):167-175 http://d.old.wanfangdata.com.cn/Periodical/dqxxkx201702004
    [16] 张宪超.数据聚类[M].北京:科学出版社, 2017

    Zhang Xianchao. Data Clustering[M]. Beijing:Science Press, 2017:
    [17] Scholkopf B, Smola A J. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond[M]. MA, USA:MIT press, 2001
    [18] Phillips J M, Suresh V. A Gentle Introduction to the Kernel Distance[OL]. https://arxiv.org/abs/1103.1625,2011
    [19] Chen D, Phillips J M. Relative Error Embeddings for the Gaussian Kernel Distance[C]. 28th International Conference on Algorithmic Learning Theory, Kyoto, Japan, 2017
    [20] Caliński T, Harabasz J. A Dendrite Method for Cluster Analysis[J]. Communications in Statistics, 1974, 3(1):1-27 doi:  10.1080-03610927408827101/
  • [1] 曹布阳, 冯华森, 梁峻浩, 李响.  利用Hilbert曲线与Cassandra技术实现时空大数据存储与索引 . 武汉大学学报 ● 信息科学版, 2021, 46(5): 620-629. doi: 10.13203/j.whugis20200367
    [2] 李健, 曹垚, 王宗敏, 王广印.  融合k-means聚类和Hausdorff距离的散乱点云精简算法 . 武汉大学学报 ● 信息科学版, 2020, 45(2): 250-257. doi: 10.13203/j.whugis20180204
    [3] 程绵绵, 孙群, 李少梅, 徐立.  顾及密度对比的多层次聚类点群选取方法 . 武汉大学学报 ● 信息科学版, 2019, 44(8): 1131-1137. doi: 10.13203/j.whugis20180043
    [4] 崔晓杰, 王家耀, 巩现勇, 赵耀.  利用模糊密度聚类和双向缓冲区自动识别热点区 . 武汉大学学报 ● 信息科学版, 2019, 44(1): 84-91. doi: 10.13203/j.whugis20180358
    [5] 李延, 王大魁, 耿晶, 王树良.  数据质量聚类算法 . 武汉大学学报 ● 信息科学版, 2019, 44(1): 153-158. doi: 10.13203/j.whugis20150760
    [6] 职露, 余旭初, 李光强.  滚圆法用于空间点聚类的研究 . 武汉大学学报 ● 信息科学版, 2018, 43(8): 1193-1198. doi: 10.13203/j.whugis20160287
    [7] 李佳怡, 张锦, 张静文, 王琪, 彭冬平.  城市公交乘客下车站点推算方法和有效性评价 . 武汉大学学报 ● 信息科学版, 2018, 43(8): 1172-1177. doi: 10.13203/j.whugis20160235
    [8] 付子圣, 李秋萍, 柳林, 周素红.  利用GPS轨迹二次聚类方法进行道路拥堵精细化识别 . 武汉大学学报 ● 信息科学版, 2017, 42(9): 1264-1270. doi: 10.13203/j.whugis20150036
    [9] 廖力, 周雪芹, 李清清, 陈璐, 周建中.  基于双重迭代聚类的模糊投影寻踪聚类算法 . 武汉大学学报 ● 信息科学版, 2016, 41(7): 932-938. doi: 10.13203/j.whugis20140152
    [10] 丁玉琦, 邵振峰, 胡石元.  一种云模型和期望最大聚类的遥感影像分割算法 . 武汉大学学报 ● 信息科学版, 2015, 40(6): 721-726. doi: 10.13203/j.whugis20130483
    [11] 黄少滨, 杨欣欣.  基于最小平方和残差的高阶模糊联合聚类算法 . 武汉大学学报 ● 信息科学版, 2015, 40(2): 238-242.
    [12] 袁汉宁, 周彤, 韩言妮, 陈媛媛.  基于MI聚类的协同推荐算法 . 武汉大学学报 ● 信息科学版, 2015, 40(2): 253-257.
    [13] 利用3DVoronoi图的兔子点云聚类分割 . 武汉大学学报 ● 信息科学版, 2013, 38(3): 358-.
    [14] 赵凤, 刘汉强, 范九伦, 潘晓英.  应用于遥感图像分割的原型提取谱聚类集成算法 . 武汉大学学报 ● 信息科学版, 2012, 37(12): 1472-1476.
    [15] 石岩, 刘启亮, 邓敏, 林雪梅.  融合图论与密度思想的混合空间聚类方法 . 武汉大学学报 ● 信息科学版, 2012, 37(11): 1276-1280.
    [16] 邓敏, 彭东亮, 刘启亮, 石岩.  一种基于场论的层次空间聚类算法 . 武汉大学学报 ● 信息科学版, 2011, 36(7): 847-852.
    [17] 刘启亮, 李光强, 邓敏.  一种基于局部分布的空间聚类算法 . 武汉大学学报 ● 信息科学版, 2010, 35(3): 373-377.
    [18] 邓敏, 刘启亮, 李光强, 肖奇.  一种基于似最小生成树的空间聚类算法 . 武汉大学学报 ● 信息科学版, 2010, 35(11): 1360-1364.
    [19] 杨春成, 何列松, 谢鹏, 周校东.  顾及距离与形状相似性的面状地理实体聚类 . 武汉大学学报 ● 信息科学版, 2009, 34(3): 335-338.
    [20] 唐亮, 黄培之, 谢维信.  顾及数据空间分布特性的模糊C-均值聚类算法研究 . 武汉大学学报 ● 信息科学版, 2003, 28(4): 476-479.
  • 加载中
图(4) / 表(5)
计量
  • 文章访问数:  810
  • HTML全文浏览量:  280
  • PDF下载量:  98
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-04-04
  • 刊出日期:  2020-07-30

一种基于核距离的车辆轨迹点聚类方法

doi: 10.13203/j.whugis20180361
    基金项目:

    国家自然科学基金 41571399

    作者简介:

    陆川伟, 博士生, 主要从事轨迹数据挖掘与地图更新研究。19wei.90chuan@163.com

    通讯作者: 孙群, 博士, 教授。13503712102@163.com
  • 中图分类号: P208

摘要: 基于聚类算法进行车辆轨迹点信息提取与挖掘,在高精度车道信息提取与更新、道路拥堵时空分析与治理、用户出行线路规划与推荐等应用中具有重要意义。针对现有聚类算法的不足,提出基于核距离的车辆轨迹点聚类方法。首先给出车辆轨迹点的定义,分析车辆轨迹的几何特征和轨迹聚类的要求,然后基于核函数的概念,推导核距离的计算过程,提出核距离密度聚类算法,重定义密度聚类算法中核邻域、核心对象等概念,最后以郑州市出租车轨迹数据进行验证。实验表明,聚类算法在减少参数数量、结果沿道路中心线对称分布、降低计算时间、提取长类簇等方面具有显著优势,可以有效地实现有向轨迹点的聚类。

English Abstract

陆川伟, 孙群, 季晓林, 徐立, 温伯威, 程绵绵. 一种基于核距离的车辆轨迹点聚类方法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(7): 1082-1088. doi: 10.13203/j.whugis20180361
引用本文: 陆川伟, 孙群, 季晓林, 徐立, 温伯威, 程绵绵. 一种基于核距离的车辆轨迹点聚类方法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(7): 1082-1088. doi: 10.13203/j.whugis20180361
LU Chuanwei, SUN Qun, JI Xiaolin, XU Li, WEN Bowei, CHENG Mianmian. A Method of Vehicle Trajectory Points Clustering Based on Kernel Distance[J]. Geomatics and Information Science of Wuhan University, 2020, 45(7): 1082-1088. doi: 10.13203/j.whugis20180361
Citation: LU Chuanwei, SUN Qun, JI Xiaolin, XU Li, WEN Bowei, CHENG Mianmian. A Method of Vehicle Trajectory Points Clustering Based on Kernel Distance[J]. Geomatics and Information Science of Wuhan University, 2020, 45(7): 1082-1088. doi: 10.13203/j.whugis20180361
  • 随着全球导航卫星系统(global navigation satellite system,GNSS)移动通信等技术的发展,车辆定位导航设备逐步普及,大量的车辆轨迹数据被获得。车辆轨迹数据记录了移动车辆在道路上的运行踪迹,其蕴含了海量、精确、实时的道路几何、拓扑与属性信息。基于车辆轨迹数据的道路信息提取与更新方法研究已经成为近年来科学研究与商业应用的一个热点。当前基于车辆轨迹数据的道路信息提取与更新方法主要包括3类:基于轨迹点聚类的方法[1-4]、基于轨迹线融合的方法[5-6]和基于核密度估计(kernel density estimation,KDE)的方法[7]

    基于轨迹点聚类的方法是根据车辆轨迹点空间分布的稀疏稠密,采用点聚类算法对车辆轨迹点进行空间聚类,识别轨迹点的空间聚集模式,提取关键道路信息,实现道路信息融合更新,如道路交叉口识别、道路附属设施识别以及道路中心线识别等。如文献[8-9]提出首先提取车辆转向轨迹点,然后基于改进的聚类算法(如X-means、分层聚类等)对转向点聚类,进而识别出道路交叉口的位置。文献[10]通过分析车辆加油行为中的轨迹运动特征,将车辆轨迹位置序列转换为速度序列,基于线性聚类算法识别车辆加油轨迹,进一步将群体加油轨迹进行层次聚类识别出加油站位置。上述方法对轨迹源数据精度要求很高,轨迹点采样时间间隔达到秒级。传统聚类方法的距离度量一般采用欧氏距离,难以同时顾及车辆轨迹的位置、朝向等信息。文献[11]针对此问题对DBSCAN(density-based spatial clustering of applications with noise)算法进行了改进,根据车辆轨迹点基于朝向的不同,分别集中分布于道路两侧区域的特点,提出方向约束的DBSCAN方法(O-DBSCAN)。该方法一方面采用基于密度的聚类方法,较好地降低了轨迹定位精度对结果的影响;另一方面同时考虑轨迹点之间的距离和夹角等因素对聚类结果的影响,聚类结果可以有效地区分出道路中心线两侧异向的轨迹点,但算法需要同时设置多个相互影响的参数(距离阈值、角度阈值),参数设置对聚类结果影响较大。由此可见,轨迹数据聚类算法面临着对源数据的精度要求高、算法参数多,以及距离度量难以顾及多个影响因子等问题。本文针对多影响因子的轨迹点空间聚类问题,基于核函数的概念,将低维空间的轨迹数据的位置和方位等信息映射到高维Hilbert空间,提出核距离的概念,实现轨迹数据低维空间距离度量(如欧氏距离、角度余弦距离等)向高维空间核距离度量的转换,然后采用核距离取代传统DBSCAN算法中的欧氏距离进行度量,达到减少算法参数数量和降低源数据精度要求的目的。

    • 本文对车辆轨迹点和车辆轨迹作如下定义。定义1车辆轨迹点(tp)是指记录车辆当前地理空间位置的点,除经度(lon)和纬度(lat)位置信息(pos)外,还包括定位时间(t)、车辆朝向(o)、车辆速度(s)等其他车辆语义信息(attr)。采用二元组表示即:

      tp = < pos, attr >

      其中,pos = < lon,lat > ;attr = < tos > 。

      定义2  车辆轨迹(T)由记录车辆行驶路径的轨迹点序列构成。即:

      $$ T = \left( {t{p_0}, t{p_1}, t{p_2} \cdots t{p_i} \cdots } \right) $$

      其中,tpi.t < tpi+1.t

    • 基于车辆轨迹数据的道路信息提取与更新研究主要基于车辆轨迹数据的空间特征、统计特征、潜在语义特征等,挖掘地图空间中道路区域与非道路区域的特征差异性,提取道路的空间、拓扑、语义等信息。车辆轨迹数据在地图空间中道路区域与非道路区域的特征差异性主要体现在以下几个方面:

      1)轨迹密度分布差异。车辆行驶于道路之上,车辆轨迹密集分布于承载车辆的道路区域。轨迹密度分布差异特征是实现基于车辆轨迹数据道路信息提取的根本。基于轨迹点聚类的方法、基于轨迹线融合的方法以及基于KDE的方法等都是基于轨迹密度分布差异性,实现道路区域与非道路区域的分离。但基于车辆轨迹密度差异特征进行道路信息提取存在两大难题:噪声问题(图 1a所示)和不同等级道路轨迹密度差异问题(图 1bc所示,低等级道路轨迹数据很少)。这两个问题会导致道路信息提取错误(图 1d所示,道路无中生有)和道路信息提取不完整(图 1ef所示,路网不完整)。如何避免这两种情况对道路信息提取的影响是当前研究的一个难点。

      图  1  轨迹密度分布差异性问题

      Figure 1.  Problems of Difference in Trajectory Density Distribution

      2)轨迹朝向分布差异。车辆必须按照一定的交通规则行驶,如中国规定车辆必须沿道路中心线右侧车道行驶。车辆轨迹数据很好地体现出了这些道路规则,如双向车道道路中心线一侧的车辆朝向基本一致,且与另一侧朝向相反。目前的研究主要集中在道路中心线提取方面[12-13]。在现有研究的基础上,基于轨迹朝向分布差异特征,提取不同朝向的道路中心线,精细化道路信息,对高精地图生产、车辆导航等生产应用具有重要意义。图 2为两条不同朝向道路的轨迹点朝向分布统计信息。可以看出,每条道路的朝向会形成两个明显的朝向峰值(图 2bc所示),朝向峰值之外的轨迹点数量相对非常少,体现出轨迹点朝向的集中性。但在朝向峰值之外存在异常峰值(图 2a所示),根据这些异常峰值所属轨迹点在道路上的空间分布,可推断异常朝向峰值所属轨迹点的形成原因是道路交叉口区域相交道路上的车辆轨迹点,这类轨迹点朝向一般与当前道路朝向呈一定夹角。分析轨迹朝向分布特征和异常峰值形成的原因是实现车道级(不同朝向车道)道路提取的关键。

      图  2  轨迹朝向分布差异

      Figure 2.  Difference of Trajectory Orientation Distribution

      3)轨迹速度分布差异。由于堵车、红绿灯信号、上下客、加油等原因,车辆轨迹会呈现出不同的速度分布差异,如在堵车路段、红绿灯路口、停车场[14]、加油站[10]、出租车交接班[15]等区域轨迹速度会明显减低或停止。

    • 数据聚类就是在一个对象集合中,根据某种相似性度量发现其自然的分组,使得组内相似度高,组间相似度低[16]。根据车辆轨迹数据空间分布特征和城市道路空间结构特点,针对考虑多影响因子的轨迹点空间聚类问题,考虑改进一种基于密度的聚类算法,将不同朝向的车辆轨迹进行聚类,使得簇中的轨迹点构成一段具有某个朝向的道路段。该聚类算法应满足以下要求:

      1)方向约束。根据车辆轨迹点朝向分布差异特征,聚类过程对轨迹点的朝向进行约束,聚类结果同一簇内的轨迹点朝向基本一致。

      2)形状拓展。道路区域一般为具有一定宽度的线形或弧形区域,因此聚类结果的形状需要具有可拓展性,能够根据实际轨迹数据的空间分布形状而延展。

      3)密度可达。由于轨迹点采样间隔、道路等级、驾驶员习惯等原因,不同等级道路之间、同一道路不同位置之间的轨迹点分布密度不均匀,因此聚类算法应能够在不同密度区域聚类。

      DBSCAN是一类基于密度的聚类算法,根据邻域大小和密度阈值进行聚类,可以发现任意形状和大小的类簇。Qiu等[11]同时考虑角度邻域和距离邻域,改进了方向约束的DBSCAN算法,首先计算当前轨迹点与邻近点之间的方向夹角diffAngle(pq),并设定夹角阈值α,然后对满足角度邻域diffAngle(pq) < α的车辆轨迹点进行距离邻域约束聚类计算。本文提出基于高斯核函数将低维距离空间(欧氏距离和余弦距离)映射到高维Hilbert空间,实现欧氏距离和余弦距离向核距离的转换,解决轨迹点聚类算法中同时考虑多个影响因子的距离度量问题。

    • 核函数是样本数据从输入空间到特征空间的一种映射关系的内积。通过构造核函数,将低维线性不可分的数据映射到高维空间实现线性可分,常用于支持向量机、主成分分析等机器学习分类算法中。其数学定义为[17]:设χ是输入空间(欧式空间Rn的子集或离散几何),Η为特征空间(Hilbert空间),如果存在一个从χΗ的映射:

      $$ \mathit{\Phi }\left( \chi \right):\chi \to H $$ (1)

      使得对所有xyχ,函数K (xy)满足条件

      $$ K\left( {x, y} \right) = \mathit{\Phi }\left( x \right) \cdot \mathit{\Phi }\left( y \right) $$ (2)

      则称K (xy)为核函数。常用的核函数包括多项式核函数、高斯核函数等。核函数的本质是数据在高维空间中的一种距离度量手段,车辆轨迹点聚类是根据轨迹点之间的角度、距离等因子的相似程度进行聚合和区分的过程,因此提出基于核距离来度量轨迹点之间在高空间中的距离(相似度)。

    • 已知两点X = < x0x1x2xn > 和Y = < y0y1y2yn > ,n为点XY的维度,则点XY的欧氏距离为:

      $$ d\left( {X, Y} \right) = \sqrt {{{\left( {X - Y} \right)}^2}} = \sqrt {{{\left( {{x_0} - {y_0}} \right)}^2} + {{\left( {{x_1} - {y_1}} \right)}^2} + \cdots + {{\left( {{x_n} - {y_n}} \right)}^2}} $$ (3)

      设核函数K,下面给出点XY在Hilbert空间的核距离[18-19]的推导过程:

      1)将点XY映射到Hilbert空间,分别表示为:

      $$ \left\{ {\begin{array}{*{20}{c}} {X \to \mathit{\Phi }\left( X \right)}\\ {Y \to \mathit{\Phi }\left( Y \right)} \end{array}} \right. $$ (4)

      2)将Φ(X)、Φ(Y)代入式(3),则两点间的距离为:

      $$ {D_k}\left( {X, Y} \right) = \sqrt {{{\left( {\mathit{\Phi }\left( X \right) - \mathit{\Phi }\left( Y \right)} \right)}^2}} $$ (5)

      3)将式(5)分解得:

      $$ {D_k}\left( {X, Y} \right) = \sqrt {\mathit{\Phi }{{\left( X \right)}^2} + \mathit{\Phi }{{\left( Y \right)}^2} - 2\mathit{\Phi }\left( X \right)\mathit{\Phi }\left( Y \right)} $$ (6)

      4)根据式(2)得:

      $$ {D_k}\left( {X, Y} \right) = \sqrt {K\left( {X, X} \right) + K\left( {Y, Y} \right) - 2K\left( {X, Y} \right)} $$ (7)

      则式(7)即为所求的核距离公式。

      本文采用高斯核函数进行度量,即:

      $$ {K_{{\rm{rbf}}}}\left( {X, Y} \right) = \exp \left( { - \frac{{{{\left\| {X - Y} \right\|}^2}}}{{{\delta ^2}}}} \right) $$ (8)

      其中,Krbf (XX)= 1,故高斯核距离为:

      $$ {D_{{\rm{rbf}}}}\left( {X, Y} \right) = \sqrt {2 - 2K\left( {X, Y} \right)} = \sqrt {2\left( {1 - {K_{{\rm{rbf}}}}\left( {X, Y} \right)} \right)} $$ (9)
    • 本文引入核距离的概念,使用核距离改进传统DBSCAN算法中的欧氏距离邻域,提出核DBSCAN算法(K-DBSCAN算法)。其定义为:给定数据集D = {x1x2xn},核距离半径ε,点数阈值minPts,则有如下定义。

      定义3  核ε-邻:对∀xpD,若xp的核ε-邻域表示为N (xp),则N (xp)= {xiD|Dk (xixp)≤ ε}。即轨迹集D中满足到点xp的核距离小于ε的任意样本点xi的集合。

      定义4  核心对象:对∀xpD,若xp的核ε-邻域内的轨迹点的个数大于m,即| N (xp) | ≥ m,则xp为一个核心对象。

      此外,算法中的直接密度可达、密度可达、密度相连等定义与DBSCAN通用算法相同,算法流程亦相同,本文不再重复[11]

      采用高斯核距离作为距离度量方法,因此核ε-邻域的限定条件可变换为:

      $$ {N_{k\varepsilon }}\left( {{x_p}} \right) = \left\{ {{x_i} \in D|{K_{{\rm{rbf}}}}\left( {{x_i}, {x_p}} \right) \ge \gamma } \right\} $$ (10)

      其中,$\gamma = 1 - \frac{{{\varepsilon ^2}}}{2}, \gamma \in \left[ {0, 1} \right]$。

    • 改进的K-DBSCAN算法涉及用户设定的参数包括核ε-邻域值ε、高斯核函数参数δ和点数阈值m

      1)参数ε控制核心对象的邻域范围,ε取值过小会导致满足条件的轨迹点数量过少,有效类减少;ε取值过大又会出现聚类过度的问题。以轨迹点之间欧氏距离小于50 m、夹角小于5°为聚类约束条件,多次实验得出,在本实验范围内,ε= 0.02时满足约束条件的轨迹点数量最大。

      2)参数δ控制高斯核函数的作用带宽,δ越小,作用带宽越窄,核函数值变化得越快。轨迹点坐标值归一化为[0, 1]后,相邻轨迹点之间归一化坐标值差异非常小,因此需要作用带宽越窄、函数值变化速度快的核函数。多次实验得出,在本实验范围内,δ = 0.5时,可以有效地区分出相邻轨迹点核函数值的差异。

      3)参数m控制轨迹点成为核心对象的邻域内最少轨迹点数量。考虑到轨迹点密度分布的不均匀性和道路的连续性,m取值为2。

    • 车辆轨迹数据为郑州市2016年11月15日1 h内的出租车轨迹,轨迹数据包括车辆ID、车辆位置、定位时间、车辆朝向等信息。为验证改进算法的效率及有效性,根据轨迹点数量不同,划分出3个实验区域,各实验区域内轨迹点数量统计如表 1所示。

      表 1  实验区域轨迹点数量统计

      Table 1.  Statistics of Trajectory Points Number in Experimental Areas

      实验区域 轨迹点数量
      区域1(惠济区) 31 413
      区域2(管城区) 138 262
      区域3(金水区) 299 367

      实验在Win7/64位/64 GB内存环境下进行,基于ArcGIS 10平台、MySQL数据库、Python编程语言进行算法实现与验证,同时为提升运算速度和降低算法内存空间,在实验区域建立100 m× 100 m格网索引。

    • 首先进行轨迹数据预处理,剔除重复轨迹点数据;然后将轨迹数据中的位置和朝向信息构建为〈xyo〉,进行数据归一化处理;建立格网索引,计算相邻格网内轨迹点的高斯核距离,构造核距离稀疏矩阵;设定算法参数,使用K-DBSCAN算法进行聚类。

      为了对比评价算法性能,将本文改进的K-DBSCAN算法与文献[11]中提出的O-DBSCAN算法进行对比,算法参数如表 2所示。

      表 2  算法参数对比

      Table 2.  Comparison of Algorithmic Parameters

      算法 参数 说明
      K-DBSCAN ε = 0.02
      O-DBSCAN-1 ε=15 文献[11]中采用的参数
      α = 1
      O-DBSCAN-2 ε=50 本实验区域表现更优的参数
      α = 5

      下面分别从聚类效果、算法效率、道路段提取效果3个方面对K-DBSCAN轨迹聚类算法进行分析与讨论。

      1)聚类效果对比

      为评价非监督聚类效果,引入Calinski-Harabasz指数[20](CH)分别对不同聚类结果进行对比。CH指数定义为:该指数通过衡量聚类结果数据的协方差比值评价聚类效果,类别内部数据的协方差越小,类别之间的协方差越大,则聚类效果越好。其计算公式为:

      $$ {\rm{CH}} = \frac{{{\rm{tr}}\left( {{\mathit{\boldsymbol{B}}_k}} \right)n - k}}{{{\rm{tr}}\left( {{\mathit{\boldsymbol{W}}_k}} \right)k - 1}} $$ (11)

      式中,n为样本数量;k为聚类结果类别数;Bk为不同类簇之间样本的协方差矩阵;Wk为同一类簇中样本的协方差矩阵;tr为矩阵的迹。CH指数值越高,则说明聚类结果效果越好。

      图 3为3个算法在实验区域某一路口附近的聚类结果放大图,其中不同颜色的框代表不同的类簇。由图 3可见,K-DBSCAN算法聚类结果(见图 3(a))的主要类簇沿道路中心线两侧对称分布,沿道路方向有较长的延伸,且连续性较好,便于后续道路提取融合;O-DBSCAN-1算法聚类结果(见图 3(b))的类簇比较零散,每个类簇包含的轨迹点数量较少;O-DBSCAN-2算法聚类结果(见图 3(c))的类簇虽能形成一些沿道路分布的长类簇,但是数量较少且长度较短。表 3为聚类结果各项指标的对比。由表 3中可见,在3种轨迹点数据量的情况下,K-DBSCAN算法聚类结果的离群点率和CH指数普遍优于O-DBSCAN算法。

      图  3  聚类结果局部对比图

      Figure 3.  Comparison of Clustering Results

      表 3  聚类结果的主要批标对比表

      Table 3.  Comparison of Main Indicators of Clustering Results

      K-DBSCAN O-DBSCAN-1 O-DBSCAN-2
      类别 区域1 区域2 区域3 域1区 区域2 区域3 域1区 区域2 区域3
      聚类点数 31 413 138 262 299 367 31 413 138 262 299 367 31 413 138 262 299 367
      离群点数 2 876 7 770 11 168 11 131 36 342 20 459 4 482 12 874 20 459
      离群点率/% 9.20 5.60 3.70 35.4 26.3 6.8 14.3 9.3 6.8
      CH指数 53 139.2 252.0 8.0 16.6 252.9 44.6 111.4 116.7

      2)算法效率对比

      表 4统计了不同轨迹点数据量的情况下,不同算法的运算时间与内存空间存储峰值的变化情况。由表 4可见,在时间效率上,K-DBSCAN算法将多个影响因子转换到高维空间后仅需要度量一个参数,因此K-DBSCAN算法在3个实验区域的算法运算时间都最少。在算法消耗的内存空间存储峰值方面,O-DBSCAN-1算法在区域1和区域2耗费内存空间存储峰值最低,因为其算法参数为ε = 15,α = 1,满足该邻域的轨迹点数量较少,距离稀疏矩阵存储值较少;随着轨迹点数量的增加,3种算法在区域3耗费的内存空间存储峰值基本一致。可见,在满足K-DBSCAN算法较大存储空间需求的情况下,可以有效地减少聚类的运算时间。

      表 4  不同算法效率对比表

      Table 4.  Efficiency Comparison of Three Algorithms

      算法 区域1 区域2 区域3
      时间/s 空间/MB 时间/s 空间/MB 时间/s 空间/MB
      K-DBSCAN 181 224 898 887 2 646 2 537
      O-DBSCAN-1 246 156 1 292 306 3 695 2 536
      O-DBSCAN-2 276 233 1 624 869 4 873 2 588

      3)道路段提取效果对比

      采用最小二乘法二次函数曲线拟合分别对3种算法中有效聚类结果(n>10)进行道路段提取,表 5统计了3种算法提取路段的长度分布情况。图 4为3种算法路段提取结果与实际道路影像的对比。

      表 5  3种算法提取的路段对比表

      Table 5.  Comparison of Road Sections of Three Algorithms

      算法 K-DBSCAN O-DBSCAN-1 O-DBSCAN-2
      区域1 区域2 区域3 区域1 区域2 区域3 区域1 区域2 区域3
      路段数 290 1 050 1 680 293 1 542 3 397 353 1 209 2 481
      < 100 m 32 214 1 578 243 1 227 2 729 181 685 2 432
      [100, 200]m 88 380 70 35 230 459 111 306 34
      > 200 m 170 456 32 15 85 209 61 218 15
      路段总长度/km 100.3 328.3 566.7 22.7 125.1 296.6 53.7 203.3 426.7

      图  4  3种算法道路段提取结果局部对比图

      Figure 4.  Local Comparison of Road Sections Extraction of Three Algorithms

    • 针对传统轨迹点聚类算法采用的相似性度量方法难以同时考虑方向、位置等多维影响因子,本文提出基于核距离的方法,从低维空间转换到高维Hilbert空间进行距离度量,即基于核距离的车辆轨迹点聚类。针对轨迹数据的几何特征和轨迹聚类的要求,对DBSCAN算法进行了改进,提出了基于核距离的K-DBSCAN算法,减少了算法的参数数量。实验对比结果表明,K-DBSCAN算法聚类结果较好地保持了车辆轨迹的对称分布特征,具有较好的空间延展性;聚类结果的离群点率、CH指数均优于对比算法;在大数据量情况下,算法的运算时间显著优于对比算法;提取路段的长路段数量和路段总长度也优于对比算法。

参考文献 (20)

目录

    /

    返回文章
    返回