基于图正则化和Schatten-p范数最小化的交通数据恢复

2022-12-16陈小波梁书荣

西南交通大学学报 2022年6期

陈小波，梁书荣，柯佳，陈玲，胡煜

（1.江苏大学汽车工程研究院，江苏镇江 212013；2.江苏大学管理学院，江苏镇江 212013）

准确、完整的交通数据是实现交通大数据分析与挖掘的基础.然而，实际交通环境中，由于检测器故障、恶劣天气、通信中断等原因，采集的交通数据通常存在缺失值.例如，北京交通流数据检测设备采集的数据中每天约有10%的数据缺失[1].传统的机器学习算法，如支持向量机、神经网络等无法处理不完整数据，严重地影响交通预测与分析智能算法的性能.因此，数据缺失问题已成为交通大数据分析的关键挑战之一.

近年来，如何对交通数据中的缺失值进行准确恢复受到国内外学者的广泛关注.由于路网的拓扑结构、人们出行行为的规律性和周期性等，同一路网中不同位置的检测器在不同检测时间所记录的数据具有较强的时空相关性，因此，充分挖掘交通数据内在的时空相关性是实现缺失数据准确恢复的关键.目前，交通数据缺失值恢复的主要方法可分为三类：基于预测的方法、基于插值的方法和基于统计学习的方法.基于预测的方法是利用历史数据的特性将缺失值作为预测的目标进行恢复；例如，Henrickson等[2]针对交通数据中的连续缺失现象，提出一种预测均值匹配多重恢复方法，即使是全天数据缺失，也能取得良好的效果；但这类方法基于历史数据建模，忽略了缺失值之后的数据所提供的信息，导致对信息利用不充分，同时，当数据变化波动较大时，恢复数据的准确性将显著降低.基于插值的方法是利用缺失值前后邻近的数据或者缺失值所在的邻近检测器数据取加权平均作为缺失值的恢复值；孙玲等[3]通过研究缺失值与观测值的相关性，对不同相关性的数据给予不同的权重，通过加权平均作为插补值；基于插值的方法计算简单，但要求缺失数据前后的相似性较高，并且当缺失值周围数据也存在缺失时，这类方法将会出现较大误差.基于统计学习的方法通过引入机器学习理论与算法[4-5]建模交通数据的时空关系，实现缺失值恢复；李林超等[6]提出一种基于多源数据融合的异质交通流数据修复方法，通过自编码器提取高维多源交通流数据的时空特征，并采用随机森林估计数据中的缺失值；这类方法主要是建立符合数据分布的模型，并不断调整模型参数，使之实现对数据的最优拟合，进而实现缺失值的恢复.

低秩矩阵补全（low-rank matrix completion，LRMC）、低秩张量补全（low-rank tensor completion，LRTC）算法被成功应用于交通数据缺失值恢复[7].由于交通数据的时空相关性，交通数据矩阵具有低秩结构，通过矩阵秩最小化实现对缺失数据矩阵的恢复.Chen等[8]将交通量数据表示为张量形式，并利用贝叶斯张量分解理论交替优化缺失值和概率模型参数.Li等[7]对4种LRTC和4种预测模型进行了研究，表明提高缺失值恢复精度可以改善交通预测模型的性能.基于LRMC的缺失值恢复方法取得了较好的效果，然而，最小化秩函数是一个NP （nondeterministic polynomial）难的非凸优化问题，难以在多项式时间内求解.一些方法将秩函数凸松弛为矩阵核范数进行求解，最小化核范数是一个凸优化问题，具有全局最优解.然而，凸松弛问题的最优解可能会偏离原问题的最优解.同时，大多数基于LRMC的恢复方法只利用了数据矩阵的全局时空相关性，而没有充分利用数据的局部结构特性.

基于上述分析，本文提出一种基于图正则化和Schatten-p范数（Schatten-pnorm and graph regularization，SPGR）的交通数据缺失值恢复方法.首先，应用已有的数据缺失值恢复方法对缺失值进行初步估计，基于此，建立刻画交通数据局部近邻结构的图模型以反映不同样本之间的相似度；依据交通数据的低秩结构这一全局先验信息，应用Schatten-p范数逼近矩阵的秩函数，提出融合图正则化和Schattenp范数最小化的缺失值恢复模型.然后，基于交替方向乘子法（alternating direction method of multipliers，ADMM）框架设计优化算法，实现对模型的有效求解.最后，通过在真实路网交通流量与速度数据上的实验对比分析验证该方法的有效性.

1 问题描述

将交通数据（如交通流量、速度）表示为变量矩阵X=(X1,X2,···,Xi,···,XN)∈RM×N.N为样本总数；M为检测器一天采集的交通数据个数，即一个样本中的数据量；Xi=(xi(1),xi(2),···,xi(q),···,xi(Q))T，xi(q)为第i个样本中第q个时刻的交通数据.设 Ω表示X中已知元素的下标集合，即XΩ为观测值集合，表示X中缺失元素的下标集合，因此，交通数据恢复问题就是根据观测值集合XΩ准确估计缺失值集合.

2 基于SPGR的交通数据缺失值恢复算法

2.1 算法框架

本文提出的基于图正则化和Schatten-p范数最小化的交通数据缺失值恢复算法，算法流程如图1所示，具体包括以下步骤：

图1 交通数据恢复算法框架Fig.1 Diagram of traffic data imputation algorithm

步骤1应用已有的数据缺失值恢复方法（如LRMC）得到缺失值的初始估计，其中，当xi(q)已知时，(q)=xi(q).

步骤2根据初始估计的结果，计算任意两个样本之间的距离，表示为矩阵D=(dij)∈RN×N，其中，dij为第i个样本与第j个样本间的距离，j=1,2,···,N，通过加权欧几里得公式[9]计算，如式（1）所示.

式中：θq为两样本在第q个时刻的差值权重；θ˜q为 θq的归一化值；α为相对小的正数，本文取0.1.

步骤3对样本Xi，根据距离矩阵D选出与之最接近的K个样本，表示为集合Ne(i).然后构造邻接矩阵（权矩阵）S=(sij)∈RN×N.

步骤4基于X与S，建立SPGR模型并求解，得到最终恢复值Y=(Y1,Y2,···,YN).

2.2 SPGR模型

如前所述，交通数据具有较强的时空相关性，因此，交通数据矩阵具有低秩结构[1]，可将缺失值恢复问题转化为矩阵秩最小化问题，如式（5）所示.

式中：A∈RM×N为观测值矩阵；PΩ(•)为 Ω 的投影运算，如式（6）所示.

然而，由于秩函数是非凸且不连续，所以式（5）是一个NP难问题，难以求解.为解决这一问题，用矩阵的Schatten-p（0

式中：∥X∥sp为X的Schatten-p范数；σt为X的第t个奇异值.

当p= 1 时，Schatten-1范数即为核范数.当p越趋近于0时，X的Schatten-p范数越接近秩函数.当p= 0 时，式（7）就是X的秩函数.总的来说，与核范数相比，Schatten-p范数对秩函数的逼近能力更强，可以更精确刻画数据的低秩结构.因此，本文构建基于Schatten-p范数最小化的缺失值恢复模型，如式（8）所示.

式中：∥•∥F为矩阵的F范数.

同时，邻近的数据样本具有相似的特征，为更好利用这种信息，在进行恢复时，将所有邻域样本之间的距离限制在适当的范围内，以防止被恢复样本与邻域样本的差异过大.基于上述分析，提出图正则化来刻画这种局部邻近结构：

式中：L=E−S，为图的拉普拉斯矩阵；E为对角元素是的对角矩阵.

结合式（8）、（9），SPGR的目标函数为

式中：λ>0为控制图正则化项的权重常数.

2.3 基于ADMM的优化算法

本文采用交替方向乘子法（ADMM）框架寻求式（10）的最优解[10].首先，引入辅助变量W和Z，将式（10）转化为式（11）所示等价问题.

构造式（11）的增广拉格朗日函数为

式中：U、V为拉格朗日乘子；µ1>0，µ2>0，为惩罚系数.

增广拉格朗日函数融合了罚函数法与拉格朗日乘子法的优点，依据ADMM框架对优化变量进行迭代求解.一个变量进行优化时，固定其他变量，通过变量交替近似求解，实现算法结果的优化.

1）固定变量Z和X，

式中：l为ADMM算法中的迭代次数；Wl、Zl、Xl、Ul、Vl分别为W、Z、X、U、V迭代l次后对应的数值.

式（13）的最优解通过迭代算法[11]求出.

2）固定变量W和X，

式（14）中对Z求导，并将导数设为0，得到

3）固定变量W和Z，

式（16）中对X求导，并将导数设为0，得到

式（17）为Sylvester方程，对于方程AX+XB=C，其解表示为X=s(A,B,C)

[12]，s(•)为Sylvester方程的求解运算.因此，

4）更新乘子Ul+ 1和Vl+ 1，

变量W、Z和X按照上述规则迭代更新，直到算法收敛，收敛条件 ε为

式中：r为很小的正数，本文取 1×10−5.

当 ε

综上，求解式（11）的优化算法流程如图2所示.

图2 ADMM流程Fig.2 Flow chart of ADMM

3 实验验证

3.1 交通数据与实验方案

为了评估SPGR方法的数据恢复性能，在真实的交通流量和交通速度数据上进行实验分析.交通流量数据来自美国俄勒冈州波特兰市交通信息中心，从I205和I84州际公路构成的路网中选择40个只有极少缺失数据的检测站采集数据.由于工作日的交通流量数据与周末和节假日的数据存在较大差异，因此，选取2015年中连续30个工作日的交通流数据进行研究.传感器采样间隔为15 min，最终获取30 × 40 = 1200个样本，构造为96 × 1200的数据矩阵.此外，交通速度数据集为中国广州两个月（2016年8月1日至2016年9月30日共61 d）内以10 min为间隔的7个路段（主要包括城市快速路和干线）的速度信息.因此，得到7 × 61 = 421个样本，构造为144 × 421数据矩阵.图3展示了8个传感器在同一天的交通数据变化情况.

图3 同一天中不同传感器交通流和交通速度的变化情况Fig.3 Changes in traffic flow and speed from different sensors over the same day

反映交通数据缺失值的复杂分布，模拟3种常见的数据缺失模式：1）完全随机缺失（missing completely at random，MCAR），缺失值独立于其他缺失数据或已知数据，表现为一组随机分布的孤立点；2）随机缺失（missing at random，MAR），交通数据表现为连续缺失的现象，即缺失值的恢复依赖于相邻的缺失值；3）混合缺失（mixture of MCAR and MAR，MIXED），MAR与MCAR的混合比例各为0.5.图4为不同缺失模式的示例，图中每行表示一个流量样本，每列表示一个变量，黑色表示缺失值.

图4 数据缺失模式模拟示例Fig.4 Simulation examples of data missing modes

为综合比较不同数据恢复方法的有效性，将提出的SPGR模型、去除图正则化的SP模型（Schattenp范数最小化，λ=0）与3种缺失值恢复方法：LRMC、概率主成分分析（probabilistic principal component analysis，PPCA）、局部最小二乘（local least squares，LLS）进行比较[1,13-14].这3种对比方法涵盖了数据缺失值恢复的主流技术，包括低秩矩阵补全、概率模型和回归模型.

实验中，按照缺失模式和缺失比例模拟缺失值.其中，缺失率 δ 定义为缺失数据数量与总数据量之比，以0.1为步长将 δ 从0.1增加到0.5，研究不同缺失率对恢复性能的影响.为衡量不同算法的恢复性能，采用缺失项的恢复值与真实值之间的均方根误差（RMSE，eRMSE）和平均绝对百分比误差（MAPE，eMAPE）表示，分别为

式中：C为缺失值的总数目；和分别为真实值和恢复值.

RMSE和MAPE越小，算法的恢复性能越好.为准确评估5种缺失值恢复方法在两种交通数据上的性能，减少随机性对实验结果的影响，每种实验均重复5次，取实验结果的误差平均值作为评价缺失值恢复方法性能的依据.

3.2 实验结果分析

表1～ 3分别列出了不同算法在MCAR、MAR和MIXED模式下的恢复误差，根据实验结果，可以得到以下结论：1）MCAR缺失模式下，各种算法的恢复误差最小；而在MAR缺失模式下，因缺失大量相关信息，导致数据恢复误差较大；此外，每种方法的恢复误差随着缺失率的增加而增加.2）在恢复性能方面，LRMC和PPCA方法不能很好地处理内部结构复杂的数据集，导致总体性能比其他方法差；当缺失率较低时，PPCA的性能较好，而当缺失率增加时，LRMC的性能优于PPCA；LLS在低缺失率下恢复性能较好，然而，当缺失率增加时，其恢复性能会迅速退化.3）本文提出的SPGR算法获得了更好的恢复性能；与LLS、PPCA、LRMC方法相比，在MCAR缺失模式下，RMSE降低了3.02% ～ 22.31%，在MAR缺失模式下，RMSE降低了3.23% ～ 28.49%，在MIXED缺失模式下，RMSE降低了3.05% ～ 21.56%；特别是当缺失率大于30%时，恢复误差降低率越大，相对于LLS算法误差降低率高达28.49%，表明该方法可以有效挖掘观测数据的内在关联，实现准确的缺失值恢复.

表1 MCAR模式下不同算法的恢复误差Tab.1 Imputation error of different algorithms in MCAR mode

表2 MAR模式下不同算法的恢复误差Tab.2 Imputation error of different algorithms in MAR mode

3.3 算法参数的影响

本文提出的SPGR模型涉及3个参数：Schattenp范数的p值、K近邻（K-nearest neighbor, KNN）方法中的K值、图正则化的权重常数 λ.p值决定了对矩阵秩函数的近似程度，K值决定了用于重建每个样本的近邻数量，λ控制基于局部邻近的图正则化的影响.为得到模型参数的最优值，调整其中一个参数，固定另外两个参数，每次参数改变时记录实验结果.以交通流量数据为例，图5给出了不同参数下，缺失值恢复误差RMSE的变化.由图可知：不同缺失率下，p具有不同的最优值，由于Schatten-p范数比核范数（p=1）更能逼近秩函数，从而获得更好的恢复结果；如果K值过大或过小，都会导致恢复精度较差.这是因为K值太小，选择代表目标样本的相邻样本过少，导致用于缺失值恢复的可用信息不充分，K值过大，远离目标的样本将参与重建，也将降低恢复精度.对于 λ的影响，也可以得出与K值类似的结论.

表3 MIXED模式下不同算法的恢复误差Tab.3 Imputation error of different algorithms in MIXED mode

图5 SPGR模型在交通流量数据上的RMSE随参数 p、K、λ的变化Fig.5 RMSEs of SPGR model on traffic flow data varied with the parameters ofp、K、λ

3.4 初始化影响

根据SPGR算法的第一步，为建立表征样本间相邻关系的图矩阵，需要选择一种已有的恢复方法对交通数据的缺失值进行初始估计.本节将采用3种不同的初始化方法，即KNN、LLS、LRMC，进行缺失值的初始估计，进而研究其对SPGR算法性能的影响，实现敏感性分析.以交通流数据为例，δ=0.3下的实验结果如表4所示.可以看出，不同的初始化方法对SPGR的恢复性能影响较小，在其他缺失率下也可以观察到类似现象.这验证了SPGR对初始值具有较好的鲁棒性.