T a b l e 1E x p l a n a t i o n o f w o r d s u s e d i n p a p e r名称含义
x,x,X,D(常数,向量,矩阵,张量
T(^,n)张量n-M ode展开函数
X n
张量与矩阵的n阶模乘
a数据集合
mod取余操作
A评价指标,如RM SE,R-square,ER等
ti n)第n个缺失数据
4”)第n个缺失数据估计值
3.1张置理论基础
矩阵乘积:给定矩阵A e R m和矩阵B e R,我们称C
和B的乘积,用A B表示,其第(i,k)项如公式 (1)所示.当A的列数与B的行数相同时,矩阵乘积才有意 义.
心=⑴n-M o d e展开:对于张量R h+ 4,从指定的第n阶 上进行切割得到若干数据切片,其中1矣n矣r.将得到的切片 以1…为行,按顺序展开合并成矩阵,我们将这一过程称为张 量的n-M o d e展开.本文用
r(«,n)表示张量在第n阶的展开 矩阵,如公式(2)所示:
X= r(£V,n)g R ln,<n k=i.k»<n lk(2) n阶模乘:给定张量W_'_4和矩阵先
将张量》在第n阶上进行n-Mode展开,然后将M与展开得 到的矩阵相乘得到矩阵乘积,最后将得到的矩阵在第n阶上 重建张量,表达式如公式(3)所示:
C<X…M e R…1r(3)
图1T u c k e r分解
F i g. 1T u c k e r d e c o m p o s i t i o n
T u c k e r:以三阶张量久e R W l3为例,如图1所示,将久 分解为一个核张量今和3个因子矩阵U,e R ||><、1;2£111^4,1]3曰》131<、核张量乡包含了不同阶之间 的潜在相关性,因子矩阵U,,U2,U3可以理解为张量模型在 各个阶的主成分,他们通常是两两正交的,三阶张量的T u c k e
r
胡雪等:张量表达下的多模态交通缺失数据补全算法107
视规
-^19191
非结构化数据
交通蓝授
数据、G P s g j g ^l 结构化数据
图2多模态交通数据
Fig . 2 Multimodal traffic data
数据融合技术已在多传感器环境中广泛应用,目的是通 过使用多源数据来获得较高的可靠性.但由于各种传感器的 特点以及数据类型的差异,以更小的代价获取更髙质量的信 息并不是一件简单的事情.在过去的十几年中,学者们对数据 融合做了较多的研究,主要包括信息融合的方法、结构、层次 以及信息的表示和转换.但对于多模态交通数据的融合目前 的研究本不是很多.本文针对非结构化(道路监控视频)和结 构化(车流量)两大类交通数据,进行张量建模,并对其所包 含的缺失数据进行补全.
3.3问题定义
结合上文提出的多模态交通数据张量模型,我们分别用 R 表示完整数据和缺失权重张量.便于分析,我们将分成实验数据和检验数据两部分实验数据(即缺失 数据)用于验证缺失值估计的误差,用%,,B.a =〇表示.已知 数据用用T V e 』=1表示,所有已知数据的集合用f t 表示,如
公式(5)所示:
f 1,史il,i 2,a e 〇 !•〇,少il.i2,i3 隹 Q
我们可以根据得到包含缺失的实验数据集表达
如公式(6)所示:
(5)
1期
分解表达式如公式(4)所示:
x 2U 2 x 3U 3
或3E L :!::•, E ::,久
(4)
3.2多模态交通数据
生活中,交通数据的完整性对于进一步数据分析、智能交
通的优化等具有十分重要的作用,如图2所示.随着技术的发 展,我们收集交通数据的方法也越来越多,
道路监控数据、流 量检测、GPS 定位等设备都收集了成千上万的数据.这些数据 由于来源的不同,导致了他们的编码方式、语义的差异,构成 了信息孤岛.但来自于不同平台的异构数据,往往存在着相关 性.例如对于同一路口的监控录像和车流量对于该路段的实 时车况有着很髙的价值,同时经过该路段的GPS 数据对于我 们交通规划也有很大的帮助.因此,将不同类型的交通数据通 过特定的方法,本文采用张量进行融合后,将原本无法交互的 信息进行统一映射,便于后续进一步挖掘交通信息的相关性, 提高交通数据的利用率,这一过程对于智能交通规划、拥塞避 免、智慧城市有着很大的意义.
交|驚据@通网络规@ (拥!苎免)
(智慧城市)
^11,12,0 = ^1,12,13^1,12,13
(6)
多模态交通数据张量化后,估计缺失数据可以视为一个
张量补全问题,其目标是通过张量分解对缺失值进行估计,并 且使估计值尽可能地接近真实值.用久表示填充后的数据 集,那么,我们可以用公式(7)来表示目标函数:
min | <P-<x\,s. t. €P a =3fn (7)
4 T C M D -I A
4.1多模态交通数据的表达
结合交通数据,本文针对两种不同类型的数据进行缺失 值估计:1)非结构化数据,主要包含道路监控视频;2)结构 化数据,主要针对车流量检测数据.交通监控视频主要包括视 频帧、分辨率、彩空间等特征.其中分辨率由像素宽和高组 成,彩空间可用RGB 表示.又可利用灰度值将三维RGB 转 化为一维灰度值.转化公式如公式(8)所示:
Gray = 0.299Red + 0. 587Green +0.114Blue (8)
因此,视频数据可用三阶张量表示,其中 Iw ,表示水平像素点,IH ,表示垂直像素点,Ire 表示视频帧数,对 应的数据为该像素点的灰度值.
车流量检测数据通过道路检测设备采集,每间隔一段时 间收集通过车辆数目,可根据不同时间间隔分成不同的时间
片数据.根据文献[14]中提出车流量信息以天和周为时间切 割单位时具有一定的循环性和相关性,因此本文构造R
来表达车流量数据,其中I x ]表示一天中测试车流量 次数,ID A 表示按天为单位划分,IW E 表示按周为单位划分,对
应的每个单元数据为车流量.
得到上述两种不同类型的交通数据张量模型后,我们观 察可知,视频数据的水平和垂直像素维数是固定的,帧数可随 着监控时长增加.同时,车流量数据划分之后,每天的测试次 数与每周的天数是固定的,测试的周数是可增加的.即a ,7 第一、二阶上的维度是不变的,第三阶的维度会随着时间的增 加而变大.基于此,我们将上述两种不同类型数据映射到同一 张量P 中,在第一阶上取口,7维度之和,对其进行叠加映射. 在第二阶上取对应维度的较大值,较小张量的对应缺失 数据置空第三阶的维数取决于时间长短.得到融合了结构化 与非结构化数据统一表达张量A
4.2基于T u c k e r -C r o s s o v e i •的多模态数据补全算法
上节我们已经将两种不同类型的交通数据统一映射到张 量空间中,本节我们将重点介绍Tucker-Crossover 模型,并将 其应用到多模态张量表达下的交通数据补全上,并提出基于 Tucker-Crossover 的多模态交通数据补全算法(TCMD-IA ). 该方法利用了最小二乘法Tucker 分解,计算三阶张量模型的 核张量和各阶的因子矩阵.并提取核矩阵与另一阶的因子矩 阵进行交叉相乘,将各阶的潜在相关性融合到因子矩阵中,使 其更具有特征性,增加了缺失数据补全的准确性.
结合前文定义的P 和构造包含缺失的多模态交通数 据集M e R h 4xl 3,通过最小二乘法的Tucker 选取合适的初始 核张量将张量进行n -Mode 展开后与初始因子 矩阵相乘,计算该次迭代的特征值与特征向量,排序后选取前 n 个特征值所对应特征向量作为因子矩阵组成.迭代至收敛, 可以得到最终的核张量S 和因子矩阵U ,,即算法1中的F ,.
脏数据处理
108小型微型计算机系统2021 年
Ft e R''xL',where t = 1,2,3(9)核张量s表达了各阶上数据之间的潜在相关性,因子矩
阵则代表着各阶的主要特征.针对不同的数据,核张量不同.为了进一步利用各阶之间的潜在相关性,本文定义了核张量 在第t阶的特征矩阵为核矩阵C,.
C, e R L'xL', where / = 1,2,3 (10)为了更好地利用各阶之间的潜在相关性,我们将因子矩 阵F,与下一阶的核矩阵C,进行交叉相乘,得到特征矩阵R,,最后结合T u c k e r进行张量的重建,得到的:V为补全缺失值后 的完整数据集.该操作再次利用不同阶之间的潜在相关性,将 阶之间的特征融合到特征矩阵中,从而提高了算法对于数据 补全的准确性.
R,= F,Ck,w h e r e k= (t+ 1)mod3 (11)
D( = s x,R,x2R2x3R3(12) TCMD-IA的伪代码如算法1所示.算法第1行通过缺失 权重张量w构造了包含缺失的实验数据集如公式(6)所 示第2.12行为最小二乘法的T u ck er分解,通过迭代将实验 数据集分解成核张量S和因子矩阵F,两部分.第13-18行构 造了核矩阵C,,将因子矩阵与下一阶的核矩阵进行信息融合,计算特征矩阵R,.第19行重建完整张量可视为补全后的数据集.第20-22行,通过不同的评价指标对缺失值补全效 果进行估计.
算法1.基于T u c k e r-C r o s s o v e r的多模态交通数据补全算法
输入:包含完整数据和缺失权重张量史,R卩*〜和最大迭代次数m a x l t e r a t e
输出:补全评价指标A
1.^h—(!P,nv);
#通过最小二乘法Tucker分解构建核张量与因子矩阵
2. Initial U;
3. For iterate i in 1: maxlterate do
4. For order n in 1 :3 do
5. <u = ttm(〇?,U,-n);
6. U| n| = nvecsC'W.n);
7. End For
8. c = ttm(T^,U,n);
9. End For
10. Ttensor = ttensor( <J,U);
11. N = ndims(〇;#计算核张量各阶维数
12. B = Ttensor. C\
13. For order t in 1:3 do
14. Ft= A Ttensor. U t#因子矩阵
15. Ct=Ft(l:N U|核矩阵
16. k = (t + 1) mod 3 ;
17. R,=F,C k;#特征矩阵
18. End For
19. a = B x丨R丨x2R2x3R3;#重构张量
20. For missing i tem in ^do
21. A =Eval(iP,£X,);
22.End for
5实验分析
5.1数据来源
实验道路监控视频与车流量数据采集于上海市杨浦区某 路段.车流量数据选取的时间节点为2019年9月1日-2019 年9月30日,每天的13点-21点,以1分钟为单位采集通过 车辆数,共14,400条数据.道路监控视频像素656 * 656,共 650 帧.
5.2评价指标
实验采用均方根误差(R o o t Mean S q u a r e d E r r o r,RMSE)作为数据补全误差准则,如公式(13)所示.其中,N为缺失数 据的数量,表示第n个缺失数据表示第n个缺失数 据的估计值.从公式可知,当R M S E的值越小,说明估计的数 据与真实值之间的误差越小,数据补全效果越好.
RMSE =
N
(13)
确定系数(R-s q u a r e)通过数据变化来评估拟合的好坏,其取值范围为[0,1],越接近1表示拟合效果越好.其中,&为已知数据的平均值.表达式如公式(14)所示:
R-square =
I I,
S:=,(^-o2
(14)
错误率(E r r o r R a t i o,ER)用来度量估计后张量项的恢复 误差,其表达式如公式(15)所示,值域为[0,1],值越接近0 表示数据补全的效果越接近真实值.
/I:,W))2
(15) 5.3实验结果与分析
实验1.核张量大小对实验结果影响
实验通过设置核张量在各个阶上维数的不同,探究了核张 量大小对缺失数据估计的影响.本节根据核张量各阶维数的比 例,选取了[50 ~ 300,50 ~ 200,50 - 70]的取值范围,通过随机 组合共设置了 12组不同大小的核张量来探究核张量对缺失数 据估计效果的影响,如表2所示.图3给出不同核张量大小对
表2核张量表
Table 2Core tensor table
标号核张量
C1[50,50,50]
C2[100,50,50]
C3[200,50,50]
C4[300,50,50]
C5[100,100,50]
C6[100,200,40]
C7[200,100,30]
C8[100,200,60]
C9[300,200,60]
C10[200,200,50]
C11[200,200,60]
C12[200,200,70]
缺失数据的补全效果R M S E折线对比图.从图中可以看出,C1-C4的R M S E较大,保持在112.3左右.随着第二阶维数的
胡雪等:张量表达下的多模态交通缺失数据补全算法109 1期
增加,C5-C8的R M S E下降至110附近.C9-C12四组的R MS E相对较小,且C10所包含的数据最少.因此,在后续实 验中,我们选取C10所对应的核张量大小,g卩[200,200,50].
113「
—<(N m rf«0'〇r^-00〇N〇—C S
核张量
图3核张量对补全效果影响
F i g.3 E f f e c t s o f c o r e t e n s o r o n c o m p l e t i o n
实验2.与其他缺失值填充方法的比较
在实验1的基础上,我们确定了核张量的大小,本节实验 目的在于验证T CM D-IA算法对于多模态交通数据的补全. 在RMSE.R-s q u a r e和E R的评价标准下,对比了平均值方法、最大期望法[l5]、_、HaLRTC、多源数据修正模型w和T-CURE[n)6种不同的数据补全方法.其中,前4种方法为传统 缺失值补全方法,多源数据修正模型,本文记为M j,为多源 数据关联补全方法,T-C U R E为基于张量的补全方法.根据 本文所设定的多模态交通数据补全场景,我们对上述部分补 全方法进行了重新定义.其中,平均值方法将缺失数据在第三 阶的前后各K个维度数据的平均值作为估计值.假设当前缺
失数据为M,.b.。,则其估计值为&,本节实验中K取10.最大期望法根据文献[15]设置第1、2阶的数据 来回归缺值变量._是以缺失数据为中心,周围K3-l个数 据的平均值作为该数据的估计值.针对方法,本文设置 60%的数据为训练集,40%的数据为检验集.
图4不同补全方法效果对比图
F i g.4 C o m p a r i s o n o f d i f f e r e n t c o m p l e t i o n m e t h o d s
实验设定少,90:100 ]为缺失数据,其余数据为已知 数据,结果如图4所示.R M S E子图中,最大期望法的误差最 小,TCMD-IA仅次于最大期望法,且与前者差距较小,平均值 法的误差最大.R-s q u a r e子图中,TCMD-IA的得分最大,拟合 效果最好,最大期望值得分最小.E R子图中,TCMD-1A的错 误率最小,平均值法最大.综合3种评价指标,我们可知T-C UR E与TCMD-IA两种基于张量的方法,相比于传
统方法对 于缺失值处理的整体效果更佳,进一步验证了前文给出的张 量在数据处理领域的表现.TCMD-IA通过T u c k e r分解所得 的各阶特征矩阵和不同阶之间的相关性,更好地利用了已知 数据,从而提高了数据补全的准确性,整体效果均优于T-CURE.
实验3.不同缺失率下的数据补全效果
实验通过选取了不同的缺失率(M i s s i n g R a t i o,M R)来进 一步衡量TCMD-IA对于多模态交通数据的补全效果.缺失率从10% -80%,每增加10%计算数据估计的R M S E、R-s q u a r e和E R值,实验结果如表3所示.从表中可知,随着缺失 率不断增加,TCMD-IA的补全效果在3种评价指标下均表现 优秀,其R M S E稳定在23左右,R-s q u a r e维持在0. 7 ,E R恒定
表3不同缺失率下的数据补全实验结果
T a b l e3 E x p e r i m e n t a l r e s u l t s o f d a t a
c o m p l e t i o n u n
d
e r d i
f f e r e n t m i s s r a t e s
MR(% )RMSE R-square ER
1023.32410.74560.3156
2023.23390.72640.3321
3023.14370.78000.3098
4022.34280.78230.2989
5022.90350.77230.3421
6022.90720.79020.3002
7023.01210.77240.3156
8022.32910.79240.2956
在0.3,具有较高的鲁棒性.这表明T CM D-IA在对数据补全 的过程中,通过采用Tu cker分解,对已知
数据的比例要求并不是十分严格,仅需要少量已知数据即可进行高质量数据估 计,因此更适合于缺失率较大的情况.
6结论
多模态交通数据的表达有利于数据的统一处理,同时,交 通数据的补全可以帮助我们更好地挖掘数据的相关性和潜在 价值,进一步为智能交通网络规划、避免拥堵等应用提供可靠 数据.本文所提的模型将结构化与非结构化数据通过张量方 法进行融合表达,并在此基础上提出了基于T u c k e r-C r o s s o v e r 的多模态数据补全算法(T CM D-IA).该方法通过T u c k e i■分解,将因子矩阵与另一阶分解所得核矩阵交叉相乘,更好地融 合了阶与阶的特征,进一步利用了不同阶的潜在相关性,从而 提高算法的补全效果.在真实数据集上实验表明,文本所提算 法具有更好地补全效果和鲁棒性.下一步工作将继续考虑更 多不同类型的数据进行融合,提髙缺失数据统一补全的效果.
References:
[1] Zhang J,W ang F Y,W ang K,et al. Data-driven intelligent transpor
tation systems:a survey [ J ]. IEEE Transactions on Intelligent Transportation System s,2011,12(4) : 1624-1639.
[2] Ni D,Leonard J D,Guin A,et al. Multiple imputation scheme for o-
vercoming the missing values and variability issues in ITS data[ J].
Journal of Transportation Engineering,2005,131 (12) :931-938. [3] Qu L,Zhang Y,H u J,et al. A BPCA based missing value imputing
method for traffic flow volume data[ C]//IE E E Intelligent Vehicles Symposium,正E E,2008:985 -990.
[4] Qu L,L i L,Zhang Y,et al. PPCA-based missing data imputation for
traffic flow volume:a systematical approach[ J]. IEEE Transactions on Intelligent Transportation System s,2009,10(3) :512-522.
[5] Acar E,Dunlavy D M,Kolda T G,et al. Scalable tensor factoriza
tions for incomplete data[ J]. Chemometrics and Intelligent Laboratory System s,2011,106( 1) :
41-56.