Page 179 - 《软件学报》2024年第4期

赵文竹 等: 多视角融合的时空动态 GCN 城市交通流量预测 1757

点之间的空间位置关系. 节点 i 和 j 的距离矩阵 A ij S ∈ NN× 具体定义如下:
  d  ij 2  d  ij 2

A =  exp −    s 2    , for i ≠ j and exp −    s 2    ≥ e (2)
S
ij

 0, otherwise
2
S
其中, d ij 代表节点 i 和节点 j 之间的距离, s 为控制矩阵 A 分布的阈值, e为控制邻接矩阵稀疏性的阈值.
(2) 动态关联图
动态关联图是基于节点之间的时间序列相似性, 通过考虑节点之间相似的功能特性以及交通模式的动态
影响所构建的交互图. 例如: 类似的商业区附近存在相似的交通模式, 在空间中可能不存在连接关系的节点,
但由于其功能特性相似, 在动态关联图上就会存在交互. 为了捕获节点之间的相似性, 使用 DTW 算法 [37] 计算
两个时间序列相似度. DTW 算法是通过一对多以及多对一匹配的方式使得两个时间序列之间总距离最小化的
最优匹配方法, 且由于其对形状相似性而非点状相似性的敏感性, 令该算法优于其他相似度计算方法. 具体
而言, 给定两个时间序列 X=(x 1 ,x 2 ,…,x m )和 Y=(y 1 ,y 2 ,…,y n ), 序列之间的距离定义为
D(i,j)=dist(x i ,y i )+min[D(i−1,j),D(i,j−1),D(i−1,j−1)] (3)
其中, D(i,j)表示两个时间序列 X=(x 1 ,x 2 ,…,x i )和 Y=(y 1 ,y 2 ,…,y j )之间的最短距离; dist(x i ,y i )为任意经典距离度量,
例如绝对距离. 算法核心是求解扭曲曲线, 因此, DTW(X,Y)=D(i,j)被设定为时间序列 X 和 Y 之间的最终距离,
与欧氏距离相比, 它更能反映两个时间序列的相似性.
然而, 使用 DTW 算法计算序列相似度需获得 D(i−1,j), D(i,j−1), D(i−1,j−1)等计算项, 即计算 D(i,j)需要得
2
到整个 D 矩阵以确保找到最优答案, 算法的时间复杂度为 O(N ), 当时间序列较长时, DTW 算法效率过低. 因
此, 本文使用了 Fast-DTW 算法 [38] , 该算法基于 DTW 算法, 可以处理大规模时间序列, 通过使用多级方法避
免了标准 DTW 算法中的暴力动态规划方法来确定两个时间序列的相似性和对应区域. Fast-DTW 算法结合了
限制和数据抽象两种方法来加速 DTW 的计算, 具体分为以下 3 个步骤(如图 4 所示).
• 粗化: 将原始的时间序列进行粗化, 即对原始的时间序列进行数据抽象, 形成一个新的、更粗糙的时
间序列, 以更少的数据点尽可能准确地表示同一曲线;
• 投影: 在较粗粒度上使用 DTW 算法, 即在较低维度下计算最小距离扭曲路径, 并将获得的扭曲路径
投影至较高维度时间序列, 为较高维度序列构建一个扭曲带;
• 细化: 通过局部调整以优化扭曲路径, 即在先前构建的扭曲带中再次计算扭曲路径.
Fast-DTW 算法重复投影和细化步骤, 直到获得最终序列的扭曲路径并计算出最佳扭曲路径的实际 DTW
距离. 由于该算法成本矩阵仅填充较低维度投影路径的附近, 扭曲路径的长度随时间序列的长度线性增长,
2
将算法的时间复杂度由 O(N )降为 O(N), 使得其在大规模空间时间数据集上的应用成为可能.
长度=8 长度=4 长度=2
|Y|
时间序列Y
Time

1
1 |X|
时间序列X
Time

(a) 粗化 (b) 投影 (c) 细化
()投影
()粗化
图 4 Fast-DTW 算法流程
通过 Fast-DTW 算法构造节点 i 和 j 之间的动态关联矩阵 A ij D ∈ NN× , 定义 A 为
D
ij
,
 1, FastDTW (XX ) e<
A ij D =  i j (4)
 0, other isew
其中, X i 和 X j 分别表示节点 i 和节点 j 的时间序列, e为控制邻接矩阵稀疏性的阈值.