留言板

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

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

利用GPS轨迹二次聚类方法进行道路拥堵精细化识别

付子圣 李秋萍 柳林 周素红

付子圣, 李秋萍, 柳林, 周素红. 利用GPS轨迹二次聚类方法进行道路拥堵精细化识别[J]. 武汉大学学报 ● 信息科学版, 2017, 42(9): 1264-1270. doi: 10.13203/j.whugis20150036
引用本文: 付子圣, 李秋萍, 柳林, 周素红. 利用GPS轨迹二次聚类方法进行道路拥堵精细化识别[J]. 武汉大学学报 ● 信息科学版, 2017, 42(9): 1264-1270. doi: 10.13203/j.whugis20150036
FU Zisheng, LI Qiuping, LIU Lin, ZHOU Suhong. Identification of Urban Network Congested Segments Using GPS Trajectories Double-Clustering Method[J]. Geomatics and Information Science of Wuhan University, 2017, 42(9): 1264-1270. doi: 10.13203/j.whugis20150036
Citation: FU Zisheng, LI Qiuping, LIU Lin, ZHOU Suhong. Identification of Urban Network Congested Segments Using GPS Trajectories Double-Clustering Method[J]. Geomatics and Information Science of Wuhan University, 2017, 42(9): 1264-1270. doi: 10.13203/j.whugis20150036

利用GPS轨迹二次聚类方法进行道路拥堵精细化识别

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

国家自然科学基金 41531178

国家自然科学基金 41501424

国家自然科学基金优秀青-基金 41522104

广东省自然科学基金 2014A030312010

详细信息

Identification of Urban Network Congested Segments Using GPS Trajectories Double-Clustering Method

Funds: 

The National Natural Science Foundation of China 41531178

The National Natural Science Foundation of China 41501424

the National Natural Science Foundation for Outstanding Youth 41522104

the Natural Science Foundation of Guangdong Province 2014A030312010

More Information
  • 摘要: 针对当前在精细识别道路拥堵时空范围方面研究的不足,提出一种利用GPS轨迹的二次聚类方法,通过快速识别大批量在时间、空间上差异较小且速度相近的轨迹段,反映出道路交通状态及时空变化趋势,并根据速度阈值确定拥堵状态及精细时空范围。首先将轨迹按采样间隔划分成若干条子轨迹,针对子轨迹段提出相似队列的概念,并设计了基于密度的空间聚类的相似队列提取方法,通过初次聚类合并相似子轨迹段,再利用改进的欧氏空间相似度度量函数计算相似队列间的时空距离,最后以相似队列为基本单元,基于模糊C均值聚类的方法进行二次聚类,根据聚类的结果进行交通流状态的识别和划分。以广州市主干路真实出租车GPS轨迹数据为例,对该方法进行验证。实验结果表明,该二次聚类方法能够较为精细地反映城市道路的拥堵时空范围,便于管理者精准疏散城市道路拥堵,相比直接聚类方法可以有效提升大批量轨迹数据的计算效率。
  • 图  1  GPS轨迹表达

    Figure  1.  Representation of GPS Trajectory

    图  2  相似队列中的轨迹

    Figure  2.  Trajectories of Similar Queues

    图  3  E邻域在时空域上的定义

    Figure  3.  E-Neighbourhood in Spatio-temporal Domains

    图  4  相似队列间相似度度量

    Figure  4.  Similarity Measure of Similar Queues

    图  5  实验路段

    Figure  5.  Experimental Road Segment

    图  6  不同聚类个数对应的DB指标值

    Figure  6.  DB Index for Different Cluster Numbers

    图  7  聚类结果(聚类个数为7)

    Figure  7.  Cluster Result (Cluster Number is 7)

    图  8  类5拥堵状态时空变化过程

    Figure  8.  Spatio-Temporal Congestion Process of Class 5

    图  9  直接子轨迹聚类和相似队列聚类DB指标

    Figure  9.  DB Index of Two Clustering Methods

    表  1  相似队列与子轨迹参数对比

    Table  1.   Comparison of Parameters Between Similar Queues and Sub-trajectories

    聚类基本单元单元/个数全天平均速度/(km·h-1)全天速度标准偏差/(km·h-1)基本单元内的速度平均偏差/(km·h-1)
    子轨迹9 74526.635.80基本单元只含一条轨迹
    相似队列1 34027.555.891.63
    下载: 导出CSV

    表  2  每个类的时空范围及速度属性

    Table  2.   Spatio-Temporal Range and Speed Properties of Each Class

    起始时间终止时间起始位置/m终止位置/m平均速度/(km·h-1)速度偏差/(km·h-1)
    类100:00:0004:15:0001 72633.4113.52
    类204:15:00
    07:15:00
    07:15:00
    09:00:00
    001 7261 02037.0011.86
    类307:15:00
    08:20:00
    08:20:00
    11:45:00
    1 02001 7261 72618.2111.71
    类411:58:00
    16:22:00
    16:22:00
    17:39:00
    01 1301 7261 72616.1012.22
    类5(严重拥堵状态)16:22:0017:56:0001 106
    17:56:0019:17:0001 0106.847.00
    19:17:0020:08:000492
    类620:15:0023:59:00098418.5213.61
    类716:56:00
    18:02:00
    18:02:00
    23:59:00
    1 106
    1 020
    1 726
    1 726
    10.088.59
    下载: 导出CSV

    表  3  直接轨迹聚类与二次聚类方法耗时对比

    Table  3.   Computation Time of Two Clustering Methods

    聚类数直接轨迹聚类/s二次聚类
    Step1:相似队列提取/sStep2:基于相似队列的模糊聚类/s总耗时/s
    45.855.380.485.86
    56.335.380.545.92
    64.535.381.366.74
    711.505.381.647.02
    834.405.381.717.09
    912.915.384.7910.17
    1030.325.385.1910.57
    1132.825.387.7413.12
    1231.375.388.8314.21
    1376.775.389.5114.89
    下载: 导出CSV
  • [1] 李清泉, 胡波, 乐阳.一种基于约束的最短路径低频浮动车数据地图匹配算法[J].武汉大学学报·信息科学版, 2013, 38(7):805-808 http://ch.whu.edu.cn/CN/abstract/abstract2697.shtml

    Li Qingquan, Hu Bo, Yue Yang. Flowing Car Data Map-Matching Based on Constrained Shortest Path Algorithm[J]. Geomatics and Information Science of Wuhan University, 2013, 38(7):805-808 http://ch.whu.edu.cn/CN/abstract/abstract2697.shtml
    [2] Wang Handong, Yue Yang, Li Qingquan. How Many Probe Vehicles Are Enough for Identifying Traffic Congestion? -A Study from a Streaming Data Perspective[J]. Frontiers of Earth Science, 2013, 7(1):34-42 doi:  10.1007/s11707-012-0343-x
    [3] 孙健, 刘琼, 彭仲仁.城市交通拥挤成因及时空演化规律分析——以深圳市为例[J].交通运输系统工程与信息. 2011, 11(5):86-93 http://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201105014.htm

    Sun Jian, Liu Qiong, Peng Zhongren. Research and Analysis on Causality and Spatial-Temporal Evolution of Urban Traffic Congestions-A Case Study on Shenzhen of China[J]. Journal of Transportation Systems Engineering and Information Technology, 2011, 11(5):86-93 http://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201105014.htm
    [4] Wang Jingyuan, Mao Yu, Li Jing, et al. Predictability of Road Traffic and Congestion in Urban Areas[J]. Plos One, 2015, 10(4):e01218254 https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4388623/figure/pone.0121825.g002/
    [5] Xia Ying, Zhang Xu, Wang Guoyin. Cluster-based Congestion Outlier Detection Method on Trajectory Data[C]. The 6th International Conference on Fuzzy Systems and Knowledge Discovery, Tianjin, China, 2009
    [6] Chengkun L, Kun Q, Chaogui K. Exploring Time-dependent Traffic Congestion Patterns from Taxi Trajectory Data[C]. IEEE International Conference on Spatial Data Mining and Geographical Knowledge Services, Fuzhou, China, 2015
    [7] Wang Y, Han Q, Pan H. A Clustering Scheme for Trajectories in Road Networks[M].Berlin Heidelberg, Germany:Springer, 2012
    [8] Song S, Kwak D, Kwak Y, et al. Segmentation Based Trajectory Clustering in Road Network with Location Sensing Technology[J].Sensor Letters, 2013, 11(9):1779-1782 doi:  10.1166/sl.2013.3009
    [9] Zhao Hongbin, Han Qilong, Pan Haiwei. Spatio-Temporal Similarity Measure for Trajectories on Road Networks[J]. Computer Engineering and Applications, 2010, 46(29):9-12
    [10] 马林兵, 李鹏.基于子空间聚类算法的时空轨迹聚类[J].地理与地理信息科学. 2014, 30(4):7-11 http://www.cnki.com.cn/Article/CJFDTOTAL-DLGT201404002.htm

    Ma Linbing, Li Peng. Spatio-Temporal Trajectory Clustering Based on Automatic Subspace Clustering Algorithm[J]. Geography and Geo-Information Science, 2014, 30(4):7-11 http://www.cnki.com.cn/Article/CJFDTOTAL-DLGT201404002.htm
    [11] Ester M, Kriegel H P, Sander J, et al. A Density-based Algorithm for Discovering Clusters in Large Spatial Databases with Noise[C]. International Conference Knowledge Discovery and Data Mining, Portland, USA, 1996
    [12] CJ J37-90. 城市道路设计规范[S]. 北京: 中华人民共和国建设部, 1991

    CJ J37-90. Specification for Design of Urban Road Subgrades[S]. Beijing, China:Ministry of Housing and Urban-Rural Development of the People's Republic of China, 1991
    [13] Elnekave S, Last M, Maimon O. Incremental Clustering of Mobile Objects:Data Engineering Workshop[C].International Conference on Data Engineering Workshop, Istanbul, Turkey, 2007
  • [1] 郭宁, 熊伟, 欧阳雪, 杨岸然, 吴烨, 陈荦, 景宁.  时空轨迹多层级相似子段匹配方法 . 武汉大学学报 ● 信息科学版, 2022, 47(9): 1390-1397. doi: 10.13203/j.whugis20200170
    [2] 张萍, 李必军, 郑玲, 王建培.  一种基于改进LCSS的相似轨迹提取方法 . 武汉大学学报 ● 信息科学版, 2020, 45(4): 550-556. doi: 10.13203/j.whugis20180406
    [3] 赵云鹏, 孙群, 刘新贵, 程绵绵, 俞童, 李元復.  面向地理实体的语义相似性度量方法及其在道路匹配中的应用 . 武汉大学学报 ● 信息科学版, 2020, 45(5): 728-735. doi: 10.13203/j.whugis20190039
    [4] 李兆兴, 翟京生, 武芳.  线要素综合的形状相似性评价方法 . 武汉大学学报 ● 信息科学版, 2019, 44(12): 1859-1864. doi: 10.13203/j.whugis20180164
    [5] 徐丰, 牛继强, 林昊, 陈时雨, 张兵兵, 陈飞燕.  利用等距同构建立多尺度空间实体相似性度量模型 . 武汉大学学报 ● 信息科学版, 2019, 44(9): 1399-1406. doi: 10.13203/j.whugis20170344
    [6] 程绵绵, 孙群, 李少梅, 徐立.  多尺度点群广义Hausdorff距离及在相似性度量中的应用 . 武汉大学学报 ● 信息科学版, 2019, 44(6): 885-891. doi: 10.13203/j.whugis20170305
    [7] 信睿, 艾廷华, 晏雄锋, 杨敏.  相似性度量支持下的隐喻地图轮廓设计 . 武汉大学学报 ● 信息科学版, 2019, 44(4): 625-632. doi: 10.13203/j.whugis20170153
    [8] 陈占龙, 吴亮, 谢忠, 张丁文.  利用约束满足问题进行多洞面实体相似性度量 . 武汉大学学报 ● 信息科学版, 2018, 43(5): 745-751, 785. doi: 10.13203/j.whugis20160191
    [9] 陈占龙, 吕梦楼, 吴亮, 徐永洋.  基于特征矩阵和关联图的空间场景相似性度量方法 . 武汉大学学报 ● 信息科学版, 2017, 42(7): 956-962. doi: 10.13203/j.whugis20140450
    [10] 朱进, 胡斌, 邵华.  基于多重运动特征的轨迹相似性度量模型 . 武汉大学学报 ● 信息科学版, 2017, 42(12): 1703-1710. doi: 10.13203/j.whugis20150594
    [11] 贾小斌, 艾廷华, 彭子凤, 王光霞.  地理信息语义的LOD表达与相似性度量 . 武汉大学学报 ● 信息科学版, 2016, 41(10): 1299-1306. doi: 10.13203/j.whugis20140711
    [12] 安晓亚, 刘平芝, 杨 云, 侯溯源.  一种线状要素几何相似性度量方法及其应用 . 武汉大学学报 ● 信息科学版, 2015, 40(9): 1225-1229. doi: 10.13203/j .whu g is20130495
    [13] 操震洲.  网络多分辨率传输中曲线集的相似性度量模型研究 . 武汉大学学报 ● 信息科学版, 2014, 39(10): 1257-1260.
    [14] 孟妮娜, 艾廷华, 周校东.  建筑群邻近关系相似性计算 . 武汉大学学报 ● 信息科学版, 2012, 37(7): 775-779.
    [15] 安晓亚, 孙群, 尉伯虎.  利用相似性度量的不同比例尺地图数据网状要素匹配算法 . 武汉大学学报 ● 信息科学版, 2012, 37(2): 224-228.
    [16] 谢明霞, 王家耀, 郭建忠, 陈科.  不等距划分的高维相似性度量方法研究 . 武汉大学学报 ● 信息科学版, 2012, 37(7): 780-783.
    [17] 马国锐, 眭海刚, 李平湘, 秦前清.  基于核函数度量相似性的遥感影像变化检测 . 武汉大学学报 ● 信息科学版, 2009, 34(1): 19-23.
    [18] 杨春成, 何列松, 谢鹏, 周校东.  顾及距离与形状相似性的面状地理实体聚类 . 武汉大学学报 ● 信息科学版, 2009, 34(3): 335-338.
    [19] 唐炉亮, 杨必胜, 徐开明.  基于线状图形相似性的道路数据变化检测 . 武汉大学学报 ● 信息科学版, 2008, 33(4): 367-370.
    [20] 杜培军, 唐宏, 方涛.  高光谱遥感光谱相似性度量算法与若干新方法研究 . 武汉大学学报 ● 信息科学版, 2006, 31(2): 112-115.
  • 加载中
图(9) / 表(3)
计量
  • 文章访问数:  2396
  • HTML全文浏览量:  141
  • PDF下载量:  718
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-09-30
  • 刊出日期:  2017-09-05

利用GPS轨迹二次聚类方法进行道路拥堵精细化识别

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

    国家自然科学基金 41531178

    国家自然科学基金 41501424

    国家自然科学基金优秀青-基金 41522104

    广东省自然科学基金 2014A030312010

    作者简介:

    付子圣, 硕士, 主要从事时空数据分析与建模研究。fzs1992@163.com

    通讯作者: 柳林, 博士, 教授。liulin2@mail.sysu.edu.cn
  • 中图分类号: P228;P208

摘要: 针对当前在精细识别道路拥堵时空范围方面研究的不足,提出一种利用GPS轨迹的二次聚类方法,通过快速识别大批量在时间、空间上差异较小且速度相近的轨迹段,反映出道路交通状态及时空变化趋势,并根据速度阈值确定拥堵状态及精细时空范围。首先将轨迹按采样间隔划分成若干条子轨迹,针对子轨迹段提出相似队列的概念,并设计了基于密度的空间聚类的相似队列提取方法,通过初次聚类合并相似子轨迹段,再利用改进的欧氏空间相似度度量函数计算相似队列间的时空距离,最后以相似队列为基本单元,基于模糊C均值聚类的方法进行二次聚类,根据聚类的结果进行交通流状态的识别和划分。以广州市主干路真实出租车GPS轨迹数据为例,对该方法进行验证。实验结果表明,该二次聚类方法能够较为精细地反映城市道路的拥堵时空范围,便于管理者精准疏散城市道路拥堵,相比直接聚类方法可以有效提升大批量轨迹数据的计算效率。

English Abstract

付子圣, 李秋萍, 柳林, 周素红. 利用GPS轨迹二次聚类方法进行道路拥堵精细化识别[J]. 武汉大学学报 ● 信息科学版, 2017, 42(9): 1264-1270. doi: 10.13203/j.whugis20150036
引用本文: 付子圣, 李秋萍, 柳林, 周素红. 利用GPS轨迹二次聚类方法进行道路拥堵精细化识别[J]. 武汉大学学报 ● 信息科学版, 2017, 42(9): 1264-1270. doi: 10.13203/j.whugis20150036
FU Zisheng, LI Qiuping, LIU Lin, ZHOU Suhong. Identification of Urban Network Congested Segments Using GPS Trajectories Double-Clustering Method[J]. Geomatics and Information Science of Wuhan University, 2017, 42(9): 1264-1270. doi: 10.13203/j.whugis20150036
Citation: FU Zisheng, LI Qiuping, LIU Lin, ZHOU Suhong. Identification of Urban Network Congested Segments Using GPS Trajectories Double-Clustering Method[J]. Geomatics and Information Science of Wuhan University, 2017, 42(9): 1264-1270. doi: 10.13203/j.whugis20150036
  • 交通拥堵已经成为我国大中城市面临的共同问题。精细化识别城市道路的拥堵状态, 准确定位拥堵发生的时空范围,能够针对性地缓解交通拥堵,提高城市道路运行效率。浮动车GPS数据因其较广的路网覆盖率和较高的采样频率,已成为识别道路拥堵的重要数据源[1]。已有研究主要利用GPS数据提取路段速度信息,通过对速度值进行统计、聚类或分级来识别拥堵路段[2]。例如以整条路段为基本单位[3]或者将路段进行等间隔拆分[4],通过计算该统计单元的平均速度,并设定阈值判定道路是否拥堵。这类方法的识别结果受限于路段的实际长度或子路段的划分方式。

    还有研究通过对GPS轨迹段聚类来识别道路拥堵[5-6]。这类方法利用基于线数据的聚类方法,聚类不同的道路交通状态,以此进行拥堵的识别。然而,目前针对城市路网中时空轨迹聚类的研究,大部分是将移动对象轨迹整体作为聚类单元[7-9],以轨迹形态相似为度量标准,没有全面考虑时空数据的多维信息,在识别轨迹的局部特征方面有所不足[10],也无法用于精细化的道路拥堵识别。

    本文提出一种基于出租车GPS轨迹二次聚类的道路拥堵精细时空范围识别方法。该方法将同一辆车每一对前后采样点之间的轨迹作为子轨迹,先通过基于密度的空间聚类(density-based spatial clustering of applications with noise,DBSCAN)方法将时间、空间位置差异较小且速度相近的一系列子轨迹聚合为一组相似队列,再通过改进的包围盒距离度量方法对聚合得到的相似队列进行相似性度量,然后采用模糊C均值聚类对相似队列进行二次聚类分析,最后根据速度阈值精细化识别道路的拥堵时空范围。本文方法的优势在于充分利用了多条时空相近轨迹的速度相似性,用轨迹特征反映道路的局部精细粒度拥堵时空范围。

    • 在路网环境下,车辆运动轨迹易受到路段及车辆行驶方向约束。为反映路段精细的拥堵状态,本文将路段R上一条包含连续多个采样点的轨迹P表示为一组子轨迹集合P={RID, [(d1, d2, t1, t2), ..., (dn, dn+1, tn, tn+1)]},如图 1所示,每个四元组表示一段子轨迹,RID为所在路段编号,dndn+1分别表示第n条子轨迹的起点和终点到路段起点的距离,tntn+1为子轨迹起点和终点的采样时刻。当子轨迹跨路段时,需要在路段交叉处打断。该子轨迹划分方法可保证拥堵识别的最小时间与空间粒度,为下文进行路段拥堵时空范围精细化识别奠定基础。

      图  1  GPS轨迹表达

      Figure 1.  Representation of GPS Trajectory

    • 本文将形态相似且时空位置相近的若干子轨迹归并形成的轨迹簇定义为一个相似队列。时空位置相近指轨迹位于目标轨迹的E邻域内,E邻域的构建方法见§2.2.1;形态相似指速度差异小,速度差异阈值设为±10 km/h。图 2展示了3个互相独立的相似队列L1L2L3,其中,纵坐标t表示时间;横坐标d为路段上任意一点距路段起点的偏移;相似队列L1即为方框表示的时空范围内一组大致平行的时空轨迹(虚线)。同样,时空范围内的实线表示的子轨迹不能被归并到L1中,因为该轨迹速度与L1中子轨迹差异较大。

      图  2  相似队列中的轨迹

      Figure 2.  Trajectories of Similar Queues

    • 为了尽可能消除噪声数据,提高初次聚类的速率和准确性,引入DBSCAN密度聚类方法[11],并将经典DBSCAN算法中的E邻域扩展到时空维,重新定义算法中的直接密度可达、核心对象等。

    • E邻域在时空维上的扩展如图 3所示,纵坐标t表示时间,横坐标d为路段上任意一点距路段起点的偏移。以轨迹p1为例,粗实线为其本身的时空域;细实线的覆盖范围即为p1对应的E邻域,其在空间维上的扩展长度为Dex (p1),对应图中AB长度;在时间维上的扩展长度为Tex (p1),对应图中BE长度。任意子轨迹段piE邻域扩展长度计算方法为:

      图  3  E邻域在时空域上的定义

      Figure 3.  E-Neighbourhood in Spatio-temporal Domains

      $$\left\{ \matrix{ {D_{ex}}({p_i}) = \alpha \times \overline {v{\rm{ }}({p_i})} {\rm{ }} \hfill \cr {T_{ex}}({p_i}) = {t_k}({p_i}) - {t_{k - 1}}({p_i}) \hfill \cr} \right.$$ (1)

      式中,k为采样点序号。空间拓展的长度需要一定的约束,长度过小可能无法找到相似的轨迹,过大则会影响提取的相似队列的质量。为保证时空域内轨迹间合适的空间距离差,取安全距离作为空间扩展距离。结合我国道路交通安全法,安全距离与行驶速度的关系为dsafe=ε×v。由于ε=1,v的单位是km/h,故式(1) 中α的值取1。

    • 若待判断轨迹pj与轨迹piE邻域边界相交或被E邻域包含,且其速度与pi相近,则认为轨迹pi直接密度可达。对于速度相近的界定,本文结合城市主干道及快速路的设计时速标准[12],将速度分为5个层级(km·h-1),如式(2)。0、1两级表示道路拥堵,2级属于缓慢行驶,3级及以上表示正常行驶。

      $${\rm{Rank}}\left( v \right) = \left\{ \matrix{ 0,{\rm{ }}v \in \left[ {0,{\rm{ }}10} \right) \hfill \cr {\rm{ }}1,{\rm{ }}v \in [10,{\rm{ }}20){\rm{ }} \hfill \cr 2,{\rm{ }}v \in [20,{\rm{ }}40){\rm{ }} \hfill \cr 3,{\rm{ }}v \in [40,{\rm{ }}60){\rm{ }} \hfill \cr 4,{\rm{ }}v \in [60,{\rm{ }} + \infty ) \hfill \cr} \right.$$ (2)
    • 时空核心对象为在自身E邻域内直接密度可达的轨迹数超过1的对象。实际含义表示相近时间空间内至少有一个行驶状态相似的车辆。通过对直接密度可达及时空核心对象的定义,基于DBSCAN密度聚类方法在时间维度上的扩展进行时空轨迹聚类,得到相似队列。

    • 利用最小包围矩阵(minimal bounding rectangle, MBR)进行时空距离度量,对一组相似队列中的所有子轨迹取其时间维度上的极大极小值作为该最小包围矩阵的tmintmax,同理取空间维度上的极大极小值作为该最小包围矩阵的dmindmax,所有子轨迹的平均速度即为该队列的速度。Elnekave[13]曾基于MBR提出一种度量方法,但该方法只能度量有重叠部分的两个MBR的相似度,对没有重叠部分的判定其相似性为0。本文对其进行改进,使得无论两个MBR重叠与否都可以度量其相似度:

      $$\left\{ \matrix{ {S_d} = 1 + {{\max ({d_{i,{\rm{ }}1}} - {d_{j,{\rm{ }}2}},{\rm{ }}{d_{j,{\rm{ }}1}} - {d_{i,{\rm{ }}2}})} \over {\max ({d_{i,{\rm{ }}2}} - {d_{i,{\rm{ }}1}},{\rm{ }}{d_{j,{\rm{ }}2}} - {d_{j,{\rm{ }}1}})}} \hfill \cr {\rm{ }}{S_t} = 1 + {{\max ({t_{i,{\rm{ }}1}} - {t_{j,{\rm{ }}2}},{\rm{ }}{t_{j,{\rm{ }}1}} - {t_{i,{\rm{ }}2}})} \over {\max ({t_{i,{\rm{ }}2}} - {t_{i,{\rm{ }}1}},{\rm{ }}{t_{j,{\rm{ }}2}} - {t_{j,{\rm{ }}1}})}}{\rm{ }} \hfill \cr {S_v} = {L_i}\left( v \right) - {L_j}\left( v \right)| \hfill \cr} \right.$$ (3)

      式中,SdStSv分别表示空间、时间、速度上的相似度;di, k-1di, k分别为队列Li在空间属性上的起止位置;ti, 1ti, 2分别为队列Li在时间属性上的起止时刻;v (Li)为队列Li的整体平均速度;对速度属性的相似度度量取两个队列的整体速度差;队列Lj参数表达同上。由式(3) 可知,在实际度量相似度时会出现4种情况,即空间相交、时间相交、时空相交以及时空都不相交(图 4)。

      图  4  相似队列间相似度度量

      Figure 4.  Similarity Measure of Similar Queues

      求得三个相似度后,将时间相似度、空间相似度和速度相似度加权累积求平方根,即得总体队列间的相似度:

      $$S = \sqrt {{\beta _1} \times {S_d} \times {S_d} + {\beta _2} \times {S_t} \times {S_t} + {\beta _3} \times {S_v} \times {S_v}} $$ (4)

      式中,β1β2β3为加权系数,用来平衡时空维度、速度维度和速度的差异性。

    • 以提取出的相似队列为基本单元,利用模糊C均值算法(FCM)聚类。模糊矩阵Uc×n的元素ui, j表示第j (j=1, 2, …, n)个相似队列对第i (i=1, 2, …, C)类待分交通状态类别的隶属度,每个相似队列对于各个状态类别的隶属度之和为1,其自身值介于0~1,该方法本质是在此约束下求解式(5) 的极值问题。

      $${J_m}\left( {\mathit{\boldsymbol{U}},{\rm{ }}\mathit{\boldsymbol{V}}} \right) = \max \left( {\sum\limits_{j = 1}^n {} \sum\limits_{i = 1}^c {} u_{i,{\rm{ }}j}^md_{i,{\rm{ }}j}^2} \right)$$ (5)

      式中,Jm(U, V)为每个相似队列到聚类中心的加权距离平方和;m为模糊指数,数值越大则分类的模糊程度越高;di, j为队列ij之间的距离,通过迭代使得目标函数最大。

      本文利用Davies-Bouldin记为DB指标对聚类效果进行评价。DB指标是对数据集结构未知的模糊聚类结果进行内部度量的最常用指标。DB值越小,类内距离越小,类间的相似度越低,聚类结果越佳。每个聚类对应一个连续稳定的交通流状态。

    • 以广州市番禺区迎宾路一条长1 726 m的路段作为实验路段,如图 5所示,该路段位于主干道上,包含较为全面的交通流状态。

      图  5  实验路段

      Figure 5.  Experimental Road Segment

    • 根据GPS采样点的位置和流向筛选出2014年6月23日0时至24时全天所有经过迎宾路车辆的轨迹点,由这些轨迹点提取出9 745条子轨迹。以此为基础进行基于DBSCAN聚类的相似子轨迹队列提取,得到1 340组相似队列,平均每个相似队列中包含7.3条子轨迹,大大缩小了二次聚类时的计算规模。表 1对比了初次聚类前后相似队列与子轨迹的相关参数。

      表 1  相似队列与子轨迹参数对比

      Table 1.  Comparison of Parameters Between Similar Queues and Sub-trajectories

      聚类基本单元单元/个数全天平均速度/(km·h-1)全天速度标准偏差/(km·h-1)基本单元内的速度平均偏差/(km·h-1)
      子轨迹9 74526.635.80基本单元只含一条轨迹
      相似队列1 34027.555.891.63

      表 1可知,两个数据集的全天速度平均值和标准偏差差别不大,说明初次聚类后的相似队列较好地保持了原始数据的速度分布。此外,在相似队列的提取过程中也消除了部分速度过低的噪声数据,因此全天平均速度较子轨迹略有上升。相似队列的速度平均偏差较小(1.63 km/h),表明相似队列的内部速度属性一致性较好。

      提取相似队列后利用模糊C均值聚类对相似队列进行聚类,经试验,计算相似度时对3个加权系数β1β2β3取1:2.5:1,可较好地反映时空及速度关系。对不同的聚类个数分别计算DB指标值,如图 6所示,该路段的最佳划分应为7类,相应DB值为0.335 1。

      图  6  不同聚类个数对应的DB指标值

      Figure 6.  DB Index for Different Cluster Numbers

      按最佳聚类结果将迎宾路全天24 h的行驶轨迹分类见表 2,划分的7个类速度偏差稳定在8.5 km/h~13.6 km/h,偏差较大的类平均速度也相对较高,而速度较低的类3、类7,其标准偏差相对较低。说明本文所划分的类内部状态相对稳定。

      表 2  每个类的时空范围及速度属性

      Table 2.  Spatio-Temporal Range and Speed Properties of Each Class

      起始时间终止时间起始位置/m终止位置/m平均速度/(km·h-1)速度偏差/(km·h-1)
      类100:00:0004:15:0001 72633.4113.52
      类204:15:00
      07:15:00
      07:15:00
      09:00:00
      001 7261 02037.0011.86
      类307:15:00
      08:20:00
      08:20:00
      11:45:00
      1 02001 7261 72618.2111.71
      类411:58:00
      16:22:00
      16:22:00
      17:39:00
      01 1301 7261 72616.1012.22
      类5(严重拥堵状态)16:22:0017:56:0001 106
      17:56:0019:17:0001 0106.847.00
      19:17:0020:08:000492
      类620:15:0023:59:00098418.5213.61
      类716:56:00
      18:02:00
      18:02:00
      23:59:00
      1 106
      1 020
      1 726
      1 726
      10.088.59

      实验路段划分的7个类的可视化轨迹如图 7所示,类5行驶平均速度仅为6.84 km/h,属于严重拥堵。以类5为例,其拥堵的精细时空范围如表 2中所示,拥堵时间范围从16:22:00起至20:08:00。拥堵从匝道处开始产生,迅速漫延至路段起点,大约在19:17:00拥堵长度消散至492 m,大致在20:08:00恢复正常通行。其对应的交通状态时空变化过程如图 8所示,图中纵坐标为时间,横坐标为长度/m。

      图  7  聚类结果(聚类个数为7)

      Figure 7.  Cluster Result (Cluster Number is 7)

      图  8  类5拥堵状态时空变化过程

      Figure 8.  Spatio-Temporal Congestion Process of Class 5

    • 本文二次聚类方法与子轨迹直接聚类相比,在聚类效果及计算开销上都有显著进步。利用DB值比较本文方法与直接轨迹聚类方法的效果,如图 9所示,直接对子轨迹聚类的最佳聚类数为6,DB值为0.648 1,划分效果较差。总体上看,当聚类数为4~13时,直接利用子轨迹聚类的效果低于相似队列方法,其原因在于直接利用子轨迹聚类无法有效剔去脏数据,在一定的时空域内存在较多的干扰轨迹,对聚类结果有较大影响。在相同的计算平台Intel (R) CPU E3-1230 v3(主频3.30 GHz、内存8.00 GB)上采用两种方法分别计算,时间对比如表 3所示,在聚类个数为4、5、6时,两种算法效率相当,但聚类个数大于6时,本文方法具有明显的效率优势。

      图  9  直接子轨迹聚类和相似队列聚类DB指标

      Figure 9.  DB Index of Two Clustering Methods

      表 3  直接轨迹聚类与二次聚类方法耗时对比

      Table 3.  Computation Time of Two Clustering Methods

      聚类数直接轨迹聚类/s二次聚类
      Step1:相似队列提取/sStep2:基于相似队列的模糊聚类/s总耗时/s
      45.855.380.485.86
      56.335.380.545.92
      64.535.381.366.74
      711.505.381.647.02
      834.405.381.717.09
      912.915.384.7910.17
      1030.325.385.1910.57
      1132.825.387.7413.12
      1231.375.388.8314.21
      1376.775.389.5114.89
    • 本文提出一种针对城市路网的GPS时空轨迹二次聚类方法,综合考虑了轨迹的时间、空间和速度属性,在时空维度上能够精细地识别道路拥堵时空范围。后续的研究将主要改进相似度度量方法,使其更加适应城市路网环境,从而更加有效地区分出不同类别的轨迹或轨迹簇,提高交通状态识别和划分的精度。

参考文献 (13)

目录

    /

    返回文章
    返回