0 引言

随着智慧交通概念的提出，城市道路上部署了大量的感知器不间断地采集具有相关时间地点信息的交通数据，这些数据被用来监测城市交通运行状态和进行通行时间预测等。由于采集到的时空交通数据规模与维数越来越大，并且数据采集过程中不可避免地发生数据丢失等情况，实际使用这些原始观测数据时，难免会受到缺失数据的影响，使得数据集的有效性降低。数据丢失的原因可能是由于传感器故障或传输丢包等设备因素，也可能是感知器的覆盖范围有限造成的。因此，数据缺失可分为以下两种情形：一种是连续时间状态下，随机记录点的缺失，即随机缺失情形；另一种是传感器不工作状态下，此区间段的数据丢失，即非随机缺失情形。可见对缺失数据进行合理补全成为交通数据应用前的关键步骤。

过去的工作中，低秩矩阵补全和低秩张量补全在图像领域取得了显著成功^[1-2]。由于现实中大多数交通数据集也具有低秩性，所以可将低秩矩阵/张量补全用于交通数据集。Yu等^[3]基于车辆轨迹数据建立了时空速度矩阵，使用Schatten p-norm实现了缺失数据矩阵的估计，并可以用作全市范围的交通数据估计和流量的动态监测。当采用矩阵结构来建模交通数据时，矩阵结构无法充分利用数据的时空信息，且在数据丢失率较大时，矩阵方法的恢复效果就会下降。鉴于交通数据与时间和空间高度相关，选择张量结构能很好地保留数据的时空特性。Asif和Tan等^[4-5]均提出使用低秩张量补全的方法来解决交通数据的估算。鉴于交通数据集存在强时空相关性(如传感器在不同天的同一时间具有相似的读数，在不同星期观察的趋势也彼此相似)，低秩模型往往能在一定准确度上对此类数据集进行建模并恢复。

在低秩逼近(Low Rank Approximation, LRA)中，核范数是最典型的低秩约束，其定义为给定矩阵的奇异值之和，即给定矩阵，核范数。同时核范数是原始秩最小化问题的最紧凸松弛。对于给定的缺失矩阵Y，核范数最小化的目标是找出一个低秩矩阵X，满足以下目标函数：

(1)

式中，λ为一个平衡参数。在一定条件下，核范数可以完美恢复低秩矩阵^[6]。Liu等^[7]提出了HaLRTC(High accuracy Low Rank Tensor Completion)算法，采用张量展开的核范数和最小化算法进行数据补全。继而有学者提出使用Schatten p-范数作为低秩约束，其定义为奇异值的l_p范数，，0＜p≤1。理论上，Schatten p-范数与标准核范数相比，在弱约束条件的情况下有更准确的数据恢复，当p=1时，Schatten范数即为核范数。且经验结果也表明基于Schatten p-范数的模型表现比一般核范数最小化的效果要好^[8]。在大部分基于Schatten p-范数的模型中，均等地考虑了所有奇异值的重要性，因此这些模型在处理不同秩的要求时不能灵活应对和有效解决实际问题。所以提高低秩逼近表现的一种方法是处理不同秩元素时考虑奇异值的放缩。最近，Chen等在低秩张量补全的框架中引入截断核范数(Truncated Nuclear Norm, TNN)，定义一个参数控制截断程度，目的是最小化N-r个奇异值的和(N是奇异值的个数，r是矩阵的秩)，保证前r个最大奇异值不变，使得主要信息被保留，从而表征出时空交通数据，同时也弥补了低秩模型受噪声影响的缺陷^[9]。然而秩r很难直接估计，且会随着数据变化。基于不同奇异值的先验知识，Xie等^[10]提出了加权的Schatten p-范数，即, w=[w₁, …, w_n], w_i≥0是一个非负向量权重作用于σ_i(X)。与传统的核范数最小化相比，加权Schatten p-范数最小化(Weighted Schatten Norm Minimization, WSNM)能根据不同的奇异值施加不同的权重且具有放缩性，大的奇异值将赋予较小的权重; 反之，较小的奇异值赋予适当大的权重，这种软阈值处理会更加合理。另一方面，Chen等^[11]提出了基于贝叶斯框架的数据插补模型，用Gibbs采样法来获取不同变量的后验分布。基于此，Chen等^[12]随后提出一种新的增广张量因子分解法，其结合了显式模型和潜在因素，在变分贝叶斯框架中，通过推断张量的后验分布概率来更新增广张量分解中的模型参数。此外变分贝叶斯和期望最大化比封闭形式的马尔可夫链蒙特卡洛法更有效^[13-14]。Zhang等^[15]基于模糊神经网络的异构集成，相比于贝叶斯高斯CP分解(Bayesian Gauss CP, BGCP)等方法获得了更好的表现。基于Tucker分解的插补方法可以挖掘交通数据的多维结构^[16]。Goulart等^[17]通过软阈值化作用于Tucker核心来提高模型的简约性。为了更好地捕捉相关性并利用不同日期的全局结构，Tan等^[18]将未来交通作为需要补全的数据，提出了动态张量补全法，从而完成了对交通的短时预测，有效利用了数据中时空信息。Duan等^[19]引入灰色预测模型，使用Tucker分解交替最小二乘GM(1, 1)模型，也实现了短期的交通流量预测。

总体来说，交通数据补全领域多用核范数相关方法，于是本研究提出张量加权Schatten p-范数最小化(Tensor Weighted Schatten p-Norm Minimization, TWSNM)模型，结合交替方向乘子法和贝叶斯优化算法，用于广州城市交通数据的补全估计，并给出TWSNM模型的准确性与有效性。

1 基于低秩张量补全的优化模型 1.1 低秩张量补全

低秩张量补全(Low Rank Tensor Completion, LRTC)是张量补全体系中的一个分支。针对时空交通数据具有低秩结构这一先验假设，本研究将构建1个三阶张量模型。对于缺失张量, LRTC模型可以表示为：

(2)

式中，为恢复完整后的张量；Ω为缺失张量y中已知元素的索引集。rank(·)为指秩函数。P_Ω(·)为投影函数：

(3)

LRTC模型中秩最小化的问题在计算上是非常困难的，因此需要寻找一个合适的凸松弛来逼近秩函数。常用的方法是利用核范数来代替秩函数，即：

(4)

式中，χ_(k)为对应的k阶张量展开矩阵，核范数的定义是对于任何矩阵，σ_i(X)是矩阵X的第i个最大奇异值。

1.2 基于张量的加权Schatten范数数据补全

首先介绍关于矩阵的加权Schatten p-范数的常用定义。

定义1：矩阵的Schatten p-范数^[20]。给定一个矩阵和一个正整数r < min{m, n}，定义矩阵的Schatten p-范数为：

(5)

即：

(6)

式中，σ_i(X), i=1, 2, …, min{m, n}是矩阵X的第i个奇异值。奇异值的排序为σ₁≥σ₂≥…≥σ_r≥…≥σ_{min{m, n}}≥0。

由于矩阵的Schatten p-范数定义并不能直接用于多维张量，并且奇异值的大小会对模型产生影响，于是在张量上定义加权的Schatten p-范数。

定义2：张量加权Schatten p-范数。对于任意d阶张量χ，张量加权Schatten p-范数定义为：

(7)

式中，α₁, α₂, …, α_d分别为施加在张量展开矩阵χ₍₁₎, χ₍₂₎, …, χ_(d)上的权重参数，且。

由定义2，当权重参数α_k适当的设置，每个张量模态展开矩阵χ_(k)将被分配权重。现用张量加权Schatten p-范数替换式(4)中的标准核范数，则LRTC模型变形为：

(8)

事实上，以不同模态展开的张量不能保证变量的稳定性。因此，引入一个辅助张量δ和一组新的约束，将模型改写为：

(9)

式中，引入δ是为了保留观测信息，并将这些信息广播到变量χ_k, k=1, 2, 3，建立辅助变量δ与现有观测量y之间的关系。

1.3 算法设计

为了解决优化式(9)，本研究采用交替方向乘子法(Alternating Direction Method of Multipliers, ADMM)，给出增广拉格朗日函数^{[9, 21-22]}：

(10)

式中 < ·, ·>为内积，τ₁, τ₂, τ₃∈ DMM中对偶更新。则式(10)转化为以下3个子问题：

(11)

(12)

(13)

遵循的更新顺序为χ₁^l+1→…→χ₃^l+1→S^l+1→τ₁^l+1→…→τ₃^l+1。

基于增广拉格朗日函数(10)，得到χ_k^l+1的最优解为：

(14)

考虑到模型的凸性，为使式(14)收敛到期望的全局最优解，基于定理1本研究给出引理1，得到封闭形式的最优解或者次优解。

定理1 (Von-Neumann ^[23])：对于任意m×n矩阵A和B，对应的奇异值分别为σ(A)=[σ₁(A), σ₂(A), …, σ_r(A)]^T，σ(B)=[σ₁(B), σ₂(B), …, σ_r(B)]^T，r=min{m, n}，可得tr(A^TB)≤tr(σ(A)^Tσ(B))，当且仅当同时找到U, V时，取得等号。

(15)

式中Σ_A, Σ_B为有序对角奇异值矩阵。

引理1：对于任意α, ρ>0, , r∈ , r < min{m, n}，问题的最优解由广义奇异值阈值给出，Z的奇异值分解为Z=U∑_ZV^T, ∑_Z=diag(σ₁, σ₂, …, σ_r)，X的奇异值分解为X=U∑_XV^T, ∑_X=diag(δ₁, δ₂, …, δ_r)。

由引理1，最小化目标函数改写如下：

(16)

则χ_k^l+1可以通过式(17)进行更新：

(17)

式中fold_k(·)为一个折叠运算符，将以k阶展开的矩阵再转换为高阶张量，即fold_k(χ_(k))=χ。同理，可以计算出辅助张量S^l+1。

2 算例分析 2.1 数据准备

从CERN数据中心的公开数据集中选取广州城市交通速度数据作为试验数据集，其时间跨度为2016年8月1日—2016年9月30日，共61天。从214个路段收集平均行车速度，时间窗间隔为10 min，则一天可分为144个时间间隔。张量结构为“位置×天×时间窗”，其大小为214×61×144；展开成矩阵结构时为“位置×时间”，其大小为214×8 784, 数据的缺失率为1.29%。

2.2 对比模型

本研究选取以下模型与提出的TWSNM模型进行比较：

(1) HaLRTC：高精度低阶张量补全^[7]。其为低秩补全模型，使用核范数最小化估计缺失数据。

(2) LRTC-TNN：截断核范数张量补全^[9]。其为低秩补全模型，使用截断的核范数来估计缺失数据。

(3) BGCP：贝叶斯高斯CP分解^[11]。其为全贝叶斯高斯张量分解模型，使用马尔可夫链蒙特卡洛方法来学习低秩结构。

2.3 试验设定

为了评估模型表现，将已观察到的数据掩盖为“缺失”数据。采用两种数据缺失模式，即随机缺失(Random Missing, RM)和非随机缺失(Non-random Missing, NM)，对这些“缺失”数据进行逼近估计。选取平均百分比误差(Mean Absolute Percentage Error, MAPE)和均方根误差(Root Mean Square Error, RMSE)作为评价指标：

(18)

(19)

其中非随机缺失情形更具有挑战性，数据会被严重破坏。

许多算法依赖于各种参数选择和设置，如滤波器组的大小，分类器正则化的强度等，这些设置会对系统性能产生巨大影响且这些参数是至关重要的。而调整参数的过程往往依赖于个人经验和直觉，难以量化或者描述。本研究采用的参数搜索方法是TPE (Tree of Parzen Estimators) 优化后的贝叶斯算法^[24]。相较于随机搜索，TPE是用高斯混合模型(GMM)替代随机节点。在每次迭代中，对于每个超参数，TPE将匹配最小损失函数值相关的超参数值集。采用TPE算法目的是用可重复和无偏优化过程取代手工调优，其广泛地探索了一个单一参数化的模型族，产生从偶然到最优表现的分类性能，于是特定的搜索过程通常可以在给定的时间内发现最佳配置。贝叶斯优化，又叫序贯模型优化(Sequential Model-Based Optimization, SMBO)，是有效的函数优化方法之一。与共轭梯度下降法等标准优化策略相比，SMBO具有自适应性且可以利用平滑性而无需计算梯度。TWSNM模型中需要设置参数的搜索空间，其中α₁, α₂, α₃是3个展开张量的权重。在的约束条件下，Liu等的HaLRTC使用了相同的权重，即。通过试验，本研究发现将α₁设置在[0, 0.1]，α₂设置在[0, 0.9]，α₃=1-α₁-α₂的情况下效果会更好。ρ在每次迭代更新时采用ρ=min{μ×ρ, ρ_max}，μ为学习率，应大于1同时也不能过大，设置在[1, 1.4]，ρ的初始值为ρ=10^-5，最大值ρ_max=10⁵。范数中p的取值在[0, 1]。

3 试验结果

在随机缺失(RM)和非随机缺失(NM)两种数值缺失模式下，通过可视化搜索过程研究参数和模型的关系。横坐标为各参数的数值，纵坐标为RMSE值。通过图 1中展示的散点分布，可以看到TWSNM模型寻优过程中的趋势。在非随机缺失模式中，散点的分布要多于随机缺失模式，可以理解为在非随机缺失模式下算法需要进行更多的尝试，这一表现也符合现实逻辑。当点从均匀分布到集中在某一块区域，表明优化算法开始是在整个范围中均匀选择参数值，来学习目标值整体分布，最后找到最优分布区域和最优值。

针对广州城市交通速度数据集，表 1总结了4个模型的数据插补性能，其中BGCP属于张量分解，HaLRTC、LRTC-TNN以及TWSNM模型属于低秩框架下的插补模型。

由图 2，可以看出TWSNM在随机缺失场景下各个缺失率中的指标表现都优于其他插补模型。随着缺失率上升，MAPE和RMSE也在上升。与随机缺失场景相比，非随机缺失场景更具挑战性。结果显示，在60%非随机缺失率之前，TWSNM模型仅次于低秩框架下的LRTC-TNN模型，但两者之间的差异非常小，RMSE相差0.2左右，说明TWSNM模型依然具有竞争性。在60%~80%缺失率的区间，TWSNM模型要优于其他模型，而此时LRTC-TNN模型的波动较大，变得不稳定，从而反映出TWSNM模型具有鲁棒性。在90%缺失率时贝叶斯模型显示出一定优势。

本研究选取4个不同路段，分别在缺失率20%，50%和80%场景下，展示TWSNM模型补全后的时间序列数据与实际时间序列数据的比较，如图 3所示。圆点表示实际时间序列数据，线条表示TWSNM模型补全后的时间序列数据。能看出线条可以基本覆盖圆点数据点，即使在缺失率大的场景下，也能做到趋势吻合。可见TWSNM模型可以进行高质量的数据补全估计。

4 结论

缺失交通数据的补全可以提高数据的利用率。本研究提出了一种基于非凸最小化的低秩张量补全模型——TWSNM模型，结合交替方向乘子法和贝叶斯优化算法来估计广州城市交通数据集中的缺失值。试验表明，TWSNM模型在随机缺失场景中不同缺失率情况下的表现都优于其他插补模型；在非随机缺失场景中低缺失率情形下TWSNM模型的表现与其他模型相比具有竞争性，在高缺失率情形下也有较好的表现并具有鲁棒性。可见TWSNM模型对实际缺失交通数据具有很好的补全效果。