基于时空相似系数的环形交叉口车辆轨迹聚类

任柏寒, 丁雪梅, 孙士龙

(1. 吉林建筑科技学院 交通工程学院, 长春 130114； 2. 白山市互联网信息中心 舆情科, 吉林 白山 134300)

0 引 言

随着社会生活水平的发展, 汽车保有量不断攀升, 造成道路资源服务增长与车辆增长之间严重失衡, 从而使交通拥堵等交通问题变得越来越严重。而随着信息化的发展, 使实时记录车辆的轨迹信息变为可能, 为解决交通问题提供了新的契机。例如可以利用手机基站位置、 公交数据形成的交通轨迹数据, 分析城市职住关系和通勤出行[1-2]、 个体活动规律[3]和城市空间结构[4]等。

聚类是一种将数据归类划分的技术方法[5], 可以广泛应用于交通数据处理等方面。陈继东等[6]将道路网络的边和结点信息作为特征数据对象进行聚类。袁冠等[7]根据转角分割得到轨迹段, 然后计算轨迹段结构相似系数, 完成轨迹聚类。王金凤等[8]基于道路网络的移动对象聚类算法 MOBORN(Moving Objects Based on Road Network), 考虑了不同时刻对象的移动速度、 方向和位置参数, 在此基础上计算网络距离和不同时刻的空间相似度, 确定时空相似系数, 当移动对象间的时空相似系数达到给定阈值时, 将其分到同一类。Won等[9]提出一种计算运动物体之间轨迹相似性的方法, 将运动物体轨迹间的相似性定义为两个轨迹间非重叠部分长度与两个轨迹的总长度之比。该计算方法仅考虑了轨迹间的空间相似性, 并未考虑两轨迹之间的时间相似性。Chen等[10]基于Hausdorff距离思想, 根据路网中路段距离计算两轨迹之间的距离, 虽在计算轨迹间空间方面上更有效, 但该方法未考虑轨迹间的时间信息。Hwang等[11]首先通过过滤阶段在道路路网中发现路网距离, 然后根据时间距离细化前一阶段对数据进行预处理, 然后进行轨迹聚类从而发现相似的轨迹。Chang等[12]利用道路网中移动物体轨迹之间的时间相似性和空间相似性的均值和乘积度量轨迹间的时空相似性。Abraham等[13]找出并根据轨迹中的兴趣位置点和时间点, 计算出移动对象轨迹间的时空相似性。

基于以往的研究可得知轨迹相似性不仅依赖于形状, 而且还依赖于时间。为实现区域车辆轨迹聚类, 笔者通过分析交叉口车辆轨迹时空信息并计算时空相似系数, 由于文中的车辆数据有较多的空值, 部分信息丢失或不完全, 这属于稀疏数据, 所以采用谱聚类将相似的数据聚集在一个类簇中, 继而可视化展示车辆轨迹在环形交叉口区域一段时间内的轨迹聚类情况。根据聚类情况继而发现车辆轨迹之间共同特征, 从而为实现车辆管控、 轨迹异常检测、 交通拥堵的发现等应用奠定基础。

1 时空相似系数

轨迹相似系数是聚类的基础, 通过相似系数确定轨迹之间的关系, 再利用轨迹相似系数对轨迹进行聚类。因此, 笔者从时间维度和空间维度两方面入手, 利用杰卡德相似系数(Jaccard Similarity Coefficient)计算两条轨迹上的时间相似系数； 以两条轨迹上的车辆在任意相同时间点上的平均距离为标准获取两条轨迹的距离, 继而用高斯过程求出距离相似系数。然后用时间相似系数乘以距离相似系数求得两条轨迹间的时空相似系数, 以实现轨迹聚类。

1.1 时间相似系数

结合在环形交叉口区域经纬度范围, 定义任意在区域内的车辆k的轨迹如下

(1)

(2)

根据式(2)可得到环形交叉口区域任意两车辆轨迹之间的时间相似系数

(3)

1.2 距离相似系数

根据环形交叉口区域两车辆轨迹所处的时间交集段, 以采样时间间隔Δt划分轨迹子段, 计算各个划分轨迹子段的距离。然后求得时间交集段各个划分轨迹子段的距离的平均值, 作为计算的轨迹距离, 再采用高斯过程转化得到环形交叉口区域两车辆轨迹的距离相似系数。

1.2.1 轨迹子段距离

通过假设环形交叉口区域两车辆轨迹在采样时间间隔Δt内, 两车辆的速度稳定, 不发生突变, 即认为两车辆在采样时间间隔Δt内匀速运行。采样时间间隔Δt内两车辆的轨迹子段分别记为L1:p(1)→p(1)′, L2:p(2)→p(2)′, 相对运动轨迹记为ΔL: Δp→Δp′, 其中Δp=p(2)-p(1); Δp′=p(2)′-p(1)′。令d=Δp+α(Δp′-Δp), 其中d为相对运动轨迹ΔL上的位置点,α的范围是： 0≤α≤1。综上, 轨迹子段L1,L2的距离如下

(4)

令α=(Δp′-Δp)T(Δp′-Δp),b=2ΔpT(Δp′-Δp),c=ΔpTΔp, 可得到dist(L1,L2)如下所示

(5)

1.2.2 轨迹距离

截取轨迹L(k1),L(k2)时间交集段的两车辆的轨迹L′(k1),L′(k2)如下

(6)

(7)

通过式(7)可计算出任意时间交集段的两车辆的轨迹距离如下

(8)

1.2.3 距离相似系数

利用高斯过程计算出两轨迹距离的相似系数

(9)

其中σ为高斯过程标准参数。

1.3 时空相似度系数

将时间相似系数矩阵与距离相似系数矩阵进行Hadamard乘积运算, 表示对应位置元素相乘。求得轨迹相似系数矩阵

S=T⊙G

(10)

2 基于谱聚类的轨迹聚类

谱聚类算法在聚类过程中只需要数据之间的相似度矩阵, 因此可以有效处理稀疏数据聚类的情况。同时谱聚类算法使用了降维处理, 对高维数据进行聚类时, 其复杂程度优于传统聚类算法。故选取了谱聚类算法进行轨迹聚类。聚类算法步骤如下：

1) 计算时空相似系数矩阵S的每行元素值之和构成对角度矩阵D;

2) 计算拉普拉斯矩阵

S′=D-S

(11)

3) 采用

Lsym=D-1/2S′D-1/2

(12)

得到对称标准化拉普拉斯矩阵Lsym;

4) 计算矩阵Lsym的前k个最大特征值, 并从大到小组成向量g∈Rk×1, 相应的特征向量排成矩阵U∈Rm×k, 其中U的第i列为第i大特征值对应的特征向量；

5) 根据K-means聚类算法将矩阵U的行向量聚成k类, 所聚类结果即为谱聚类结果。

3 实例验证

3.1 数据预处理

由于观测数据中包含系统噪声和干扰, 故采用卡尔曼滤波(Kalman Filtering)方法对数据进行降噪处理。该方法通过输入输出观测数据, 在不确定性变化中寻求一种平衡, 对系统状态进行最优估计。卡尔曼滤波方法的处理过程可分为预测模块和更新模块。

3.1.1 预测模块

预测模块主要通过当前时刻与上一时刻的关系, 实现对状态的预测并且构建状态预测误差的协方差矩阵。

1) 根据状态转移矩阵、 控制矩阵及上一时刻的状态矩阵si对当前时刻状态矩阵si+1的预测估计, 得到当前时刻状态矩阵的估计值

(13)

(14)

其中Q为预测模型本身带来的噪声。

3.1.2 更新模块

1) 根据预测状态协方差矩阵P和观测量的协方差矩阵W确定卡尔曼增益矩阵

(15)

式(15)中,λ为测量结果不信任指数, 该值越高表示对相应时刻的测量结果越不可信。根据车辆在短时间内速度不会突变。确定不信任指数λ的计算如下

(16)

(17)

其中Zi∈R2×1为GPS实际观测的车辆轨迹状态矩阵。

(18)

图1 在交叉口坐标平面中车辆轨迹数据预处理结果展示

3.1.3 数据预处理结果展示

以采集到的一条车辆轨迹的交叉口坐标数据为例, 进行了数据预处理, 处理结果如图1所示。

3.2 相似度计算结果

为了避免杂乱的轨迹影响绘图效果, 从数据库中选取8条轨迹展示聚类效果。为检验聚类效果, 在环形交叉口中每个进口的轨迹数据中选取了不同数量的车辆轨迹, 其轨迹的方向如表1所示。

表1 车辆轨迹编号及其图示

计算得到的时间相似系数矩阵

(19)

计算得到的距离相似系数矩阵

(20)

得到的时间相似系数矩阵imagesc如图2所示。距离相似系数矩阵imagesc如图3所示。根据式(11)得到标准化的拉普拉斯矩阵

(21)

可以得出如图4所示的标准化的拉普拉斯矩阵imagesc图。

图2 时间相似系数矩阵imagesc图 图3 距离相似系数矩阵imagesc图 图4 标准化的拉普拉斯矩阵imagesc图

图5 聚类结果

4 聚类结果及结论

通过轨迹聚类得到的聚类效果如图5所示。

Mou等[14]指出轨迹聚类的有效性评价需要更加深入研究, 故笔者只对聚类得到的可视化图进行阐述。由图5可以直观看出, 可以将交叉口进口道的车辆轨迹聚类一起, 以区分不同交叉口进口道的轨迹。笔者所提出的基于GPS数据的车辆轨迹聚类算法具有一定的可行性, 为交通数据挖掘提供了一定的基础。

5 结 语

笔者考虑环形交叉口车辆运行轨迹时间上和空间上的相似性, 构建了时空相似系数, 以此作为主要指标提出了车辆轨迹的谱聚类方法。通过法国克雷泰伊一环形交叉口GPS数据验证, 笔者提出的方法能有效确定车辆进出交叉口路线、 环岛交织段, 为避免车辆冲突科学渠化设计环形交叉口提供了重要依据。