Correlating sparse sensing for large-scale traffic speed estimation A Laplacian-enhanced low-rank tensor kriging approach Tong Niea Guoyang Qina Yunpeng Wangb Jian Suna

2025-05-06 0 0 7.01MB 29 页 10玖币
侵权投诉
Correlating sparse sensing for large-scale traffic speed estimation: A
Laplacian-enhanced low-rank tensor kriging approach
Tong Niea, Guoyang Qina, Yunpeng Wangb, Jian Suna,∗
a
Department of Traffic Engineering & Key Laboratory of Road and Traffic Engineering, Ministry of Education, Tongji University, Shanghai 201804, China
b
Beijing Key Laboratory for Cooperative Vehicle Infrastructure Systems and Safety Control, School of Transportation Science and Engineering, Beihang
University, Beijing 100191, China
Abstract
Traffic speed is central to characterizing the fluidity of the road network. Many transportation applications rely
on it, such as real-time navigation, dynamic route planning, and congestion management. Rapid advances in
sensing and communication techniques make traffic speed detection easier than ever. However, due to sparse
deployment of static sensors or low penetration of mobile sensors, speeds detected are incomplete and far from
network-wide use. In addition, sensors are prone to error or missing data due to various kinds of reasons, speeds
from these sensors can become highly noisy. These drawbacks call for effective techniques to recover credible
estimates from the incomplete data. In this work, we first identify the issue as a spatiotemporal kriging problem
and propose a Laplacian enhanced low-rank tensor completion (LETC) framework featuring both low-rankness
and multi-dimensional correlations for large-scale traffic speed kriging under limited observations. To be specific,
three types of speed correlation including temporal continuity, temporal periodicity, and spatial proximity are
carefully chosen and simultaneously modeled by three different forms of graph Laplacian, named temporal
graph Fourier transform, generalized temporal consistency regularization, and diffusion graph regularization.
We then design an efficient solution algorithm via several effective numeric techniques to scale up the proposed
model to network-wide kriging. By performing experiments on two public million-level traffic speed datasets,
we finally draw the conclusion and find our proposed LETC achieves the state-of-the-art kriging performance
even under low observation rates, while at the same time saving more than half computing time compared with
baseline methods. Some insights into spatiotemporal traffic data modeling and kriging at the network level are
provided as well.
Keywords: Network-wide traffic speed estimation, spatiotemporal correlation, kriging, graph Laplacian,
large-scale traffic data, low-rank tensor completion
1. Introduction
Traffic speed is the central macroscopic quantity used to characterize the fluidity of the road network. Many
applications in the transportation domain rely on the knowledge of traffic speed over the road network to support
various dimensions of decision-making, such as real-time navigation, dynamic route planning, congestion
management, pollution evaluation, and infrastructure optimization (Boriboonsomsin et al.,2012;Liebig et al.,
2017;Liu et al.,2019;Han et al.,2020). With rapid advances in sensing and communication techniques, collecting
traffic speed measurements becomes easier than ever: static sensors such as loop detectors are continuously
logging vehicular speeds past a cross-section, while mobile sensors such as floating cars are chronicling speeds of
their background traffic flow. In fluid mechanics’ terminology, static sensors generate Eulerian measurements
at fixed locations, while mobile sensors produce Lagrangian measurements following the flow as they move.
To obtain a full picture of the network-wide traffic speed, either Eulerian measurements with dense sensor
deployments or Lagrangian measurements with high vehicular penetration rates is desired, whereas in fact the
reality is far from desirable.
One may see in reality that the static sensors often have a sparse coverage subject to high installation budget
and maintenance costs and leave many road links undetected, thereby rendering low spatial resolution data
that is hard to extend to the entire network. In the meanwhile, mobile sensors, which are mostly installed on
commercial vehicle fleets like taxis, often result in a low penetration rate, which may render dubious speed
estimation due to its biased representation of the population. In addition, sensors are prone to error or missing
data due to various kinds of reasons such as equipment failure, communication outage, and out-of-service,
speeds detected from these sensors can become highly noisy (Asif et al.,2016). These drawbacks combined imply
that the sensing data is by no means ideal, and call for effective techniques to recover credible estimates from the
∗Corresponding author. Address: Cao’an Road 4800, Shanghai 201804, China
Email address: sunjian@tongji.edu.cn (Jian Sun)
Preprint submitted to Transportation Research Part C: Emerging Technologies May 30, 2023
arXiv:2210.11780v3 [stat.ML] 28 May 2023
incomplete data. Fortunately, traffic speeds bounded in the road network are highly correlated in both space and
time, and therefore pose a rich degree of redundancy (or low-rankness in a matrix or tensor theory’s term (Tan
et al.,2013)) that undetected or erroneous speeds of some road links are recoverable by virtue of the correlation.
In other words, sparse sensors are able to achieve a "collaborative perception" of traffic speeds of the undetected
road links, when their intrinsic multi-dimensional correlations are effectively exploited (see Fig. 1).
Recent years have witnessed a vast array of studies investigating the problem of estimating traffic state on
undetected road links (Meng et al.,2017;Zhang et al.,2020;Wu et al.,2021a;Lei et al.,2022). This problem is often
cast into spatiotemporal traffic kriging (Wu et al.,2021a) in the literature. Unlike the traffic forecasting problem
that aims at predicting future state of a road link given its historical state, spatiotemporal traffic kriging attempts
to estimate the traffic state of an undetected road link without any historical state of that link; it instead needs
to utilize measurements of other detected road links to complete the "spatial prediction." Kriging is therefore
regarded as a special missing data imputation problem. How to effectively utilize the correlation between undetected
road links and other sparsely detected roads is the core research question of this paper. Upon close inspection, we
identify three-fold specific challenges:
First, correlation between speeds of the detected road links and speeds of the undetected ones can be arbitrary
unless reasonable prior assumptions are made. Low-rankness is a widely-adopted general prior in literature to
reflect linear correlation of traffic data over space and time (Tan et al.,2013;Asif et al.,2016;Chen et al.,2021a).
However, low-rankness is not directly applicable to our kriging problem in which data are fully missing in some
locations, as in this case, we can fill different sets of values to the missing data without changing the rank and the
missing values therefore remain undetermined under the low-rankness assumption. Conceptually, low-rankness
is not sufficient when imputing a space-time matrix with entire row or column missing. Additional regularization
terms should be carefully considered to complement the low-rankness assumption (Bahadori et al.,2014;Yokota
et al.,2018;Yamamoto et al.,2022).
Second, in addition to general correlation assumptions, exploiting the semantic spatiotemporal correlation of
speeds is an necessary add-on. Since speed manifests microscopic traffic that is time-varying, dynamic, periodic,
and spatially interdependent, in the meanwhile, spatial correlation is bounded on a graph instead of on a 2D
plane, spatial correlation should consider the graph features (e.g., network topology) as well as traffic flow loaded
on that graph (e.g., moving directions of traffic flow) (Li et al.,2017), exploiting spatio-temporal correlations is
by no means trivial. Moreover, as a graph signal, traffic data features inherent time series characteristics such
as continuity, periodicity, and stationary, providing another prior for ones to achieve time-varying recovery.
Tailoring an effective kriging model to capture the multi-modal correlations of spatiotemporal traffic data is still
an open question yet to be resolved.
Third, scalability of the kriging approach onto the network level is desired as it allows exploiting correlation
of a wider scope of speeds over space with added accuracy. Moreover, when new measurements are collected,
a kriging model with fast parametric update is preferable for an online estimation.To this end, computational
efficiency is the key. However, classical Gaussian process (GP) based kriging doesn’t show scalability due to
its computational complexity, while existing scalable tensor based imputation methods (Lu et al.,2019b;Chen
et al.,2021a) are mainly designed for general data imputation problem, and are not applicable to the kriging
task. Although Bayesian Gaussian kriging methods achieve flexible hyper-parameter tuning for spatiotemporal
kriging (Lei et al.,2022;Chen et al.,2022b), its high consumption of time and memory in parametric learning of
the Gaussian kernel inhibits itself from being scaled to the network level. Custom scalable solution algorithms
need to be designed to maximize the kriging performance.
To tackle the challenges and realize a network-wide kriging of missing speed data for the undetected road
links, we propose a Laplacian enhanced tensor completion (LETC) based kriging model to exploit multi-modal
spatiotemporal correlations of traffic speeds, where three kinds of carefully chosen speed correlation – temporal
continuity,temporal periodicity and spatial proximity – are simultaneously captured by assigning three forms of
graph Laplacian. By integrating graph Laplacian into tensor completion model either explicitly or implicitly,
LETC can leverage both global low-rankness property and local dependency informed by physical constraints at
the same time. The framework contributes to the current literature in four aspects as follows:
1.
We customize a new temporal graph Fourier transform (TGFT) based on temporal periodic graph Laplacian
to encode the temporal periodicity of speeds. The TGFT complements the low-rankness assumption and
enables parallelization of the tensor completion by a series of daily matrix in graph spectral domain.
2.
We propose a novel diffusion graph regularization (DGR) to exploit spatial dependency on directed graphs.
By modeling as random walkers on graphs, DGR considers the directed nature of traffic flows and closely
connects with the graph diffusion process. Moreover, DGR features explicit physical explanations and
encourages a low-pass propagation which is beneficial for reconstructing spatiotemporal traffic data.
3.
We develop a general formulation of temporal consistency regularization (GTCR) to impose smoothness
constraints on time slots within a kernel size. GTCR considers the causality of time series in a model-free
manner and can directly convert into some previously developed temporal regularization terms.
4.
To scale up the kriging on large-scale network, we speed up our model by randomized tensor singular
value decomposition and conjugate gradient method. Experiments on million-level traffic datasets not only
2
reveal the superiority of LETC on both accuracy and computational efficiency, but also provide insights
into handling large-scale kriging problem.
The rest of this article is organized as follows. Section 2reviews related works about spatiotemporal kriging.
Section 3introduces basic concepts about tensor operations in this work and defines the tensor-based kriging
problem. In Section 4, we propose the graph tensor-based kriging model and a scalable solution algorithm.
In Section 5, we perform numerical experiments of the proposed approach on two public data sets, which is
followed by model comparison, ablation studies, and sensitivity analysis. Section 6concludes this work and
provides future directions.
Speed values
Sensor Missing values
Recorded speed time series
Link 1
Link 2
Link 3
Link 3
Link 1
Link 2
Sensor network with low coverage and incomplete speed records
③
Spatial proximity
!
①
Temporal periodicity
! !
②
Temporal continuity
! !
Higher similarity Lower similarity
Exploiting spatial and temporal correlations
Graph tensor learning
Time
Location
SpeedSpeed
Time
Location
Link 1 2 3
Day
Day
…
…
Estimating Network-wide speeds
Spatial proximity
Temporal
periodicity
Temporal continuity
Figure 1: Illustration of spatiotemporal kriging problem. Take link 1, 2 and 3 as an example: link 1 and 2 record incomplete traffic speeds
with missing time intervals, and link 3 are not equipped with a sensor so there is no historical record at all. The aim of spatiotemporal kriging
is using the multi-dimensional spatial and temporal correlations (temporal continuity, temporal periodicity and spatial proximity) to infer the
unmeasured locations (link 3) from the measured locations (link 1 and 2). In this figure, link 2 is physically closer to link 3 than link 1, so it is
rational to assume link 2 and link 3 have stronger similarity.
2. Related work
Kriging is typically a regression problem for spatial modeling and interpolation of random fields based on
covariance functions, which is a ubiquitous topic in geostatistics and usually associated with GP regression.
Recently, kriging tasks have aroused great interests from different disciplines in machine learning community and
many of these works can be viewed as special variants of kriging. In this section, we discuss kriging problems
and summarize related solutions from a general perspective: spatial prediction with no historic data.
2.1. Graph regularized low-rank matrix and tensor completion based methods
In recommendation system community, graph regularized matrix completion/factorization models are
commonly used for collaborative filtering tasks (Kalofolias et al.,2014;Rao et al.,2015;Strahl et al.,2020). The
main purpose is to predict the unknown node values using side information about edges, which resembles the
motivation of kriging. Kalofolias et al. (2014) first proposed a matrix completion model with graph Laplacian
regularization. Rao et al. (2015) solved this problem in a scalable manner called graph regularized alternating
least squares method, where conjugate gradient method was applied to update parameters. In the study of
transportation, graph regularization is introduced either in space-time domain (Bahadori et al.,2014;Wang
et al.,2018;Zhang et al.,2020;Yang et al.,2021), or graph spectral domain (Deng et al.,2021) to model spatial
dependency. Among these works, Bahadori et al. (2014) proposed a tensor learning model for spatiotemporal
co-kriging. The optimization problem was solved by greedy algorithm with orthogonal projections. Most of
these works are developed for other data source and can not be directly transferred to our problem, as the unique
characteristics of traffic speed should be taken into consideration.
2.2. Bayesian/probabilistic matrix factorization based method
Since kriging is a basic problem in GP modeling, some works combine GP priors with matrix factorization
in a whole probabilistic framework to inference unknown data (Luttinen and Ilin,2009;Zhou et al.,2012;Yang
et al.,2018;Strahl et al.,2020). When graph Laplacian is specified as the kernel (covariance) function, this kind of
model is equivalent to the graph regularized matrix factorization model. Most recently, Lei et al. (2022) proposed
a Bayesian kernelized matrix factorization model for spatiotemporal traffic data imputation and kriging. Using
a fully Bayesian treatment, this method can learn the hyper-parameters of graph kernels through resampling.
One downside can not be overlooked is that the hyper-parameter sampling procedure is quite time-consuming.
Therefore, there seems to be a trade-off between model scalability and flexibility.
3
2.3. Graph neural network based method
Graph convolution neural networks (GCN) has shown great potential for inductive modeling and achieved
promising performances on kriging tasks (Appleby et al.,2020;Wu et al.,2021a,b;Liang et al.,2022). Appleby
et al. (2020) first developed a kriging convolutional networks using K-nearest neighbor to reconstruct all the node
values on a defined graph. Wu et al. (2021a) proposed an inductive GCN to model the spatial dependency and a
random mask sample generation method was used for model training. However, both of these methods consider
the sample over a specific observation time as individual or additional features, thus ignoring the temporal
consistency. Liang et al. (2022) further improved the kriging performance of GCN by integrating an external
attention mechanism and a temporal convolution network. Despite high accuracy has been achieved, training
these elaborate GCN models is computationally very expensive and may require GPU hardware acceleration,
which is prohibitive for large-scale problems.
2.4. Multi-way delay embedding (Hankelization) based methods
In the field of computer vision, kriging can be regarded as recovery of missing pixels along entire rows or
columns of RGB images, i.e., a special image inpainting task (Yokota et al.,2018). Hankel matrix that bases on
shift-invariant features of image is supposed to be a powerful tool for this issue. Yokota et al. (2018) proposed
a Tucker tensor decomposition in multi-way delay-embedded (MDT) space method (aka., Hankelization) and
extend the Hankel matrix to tensor. Yamamoto et al. (2022) further improved the scalability of Hankel tensor
completion by using circulant MDT approximation. Although these pioneering works do not aim to solve
spatiotemporal traffic kriging, the MDT based method has been applied to various transportation problems,
such as traffic speed estimation from trajectories (Wang et al.,2021b), traffic data anomaly detection using RPCA
(Wang et al.,2021a), and short-term traffic forecasting (Shi et al.,2020). In the context of spatiotemporal traffic
data, there exists shift-invariant patterns in the time dimension, while this phenomenon is not distinctive in the
space dimension. Without external spatial information, the MDT may produce erroneous kriging results.
3. Preliminaries and problem definitions
In this section, we first introduce some basic notation and preliminaries about tensor algebra. After that, we
describe the spatiotemporal traffic speed kriging problem in the perspective of graph tensor learning framework.
3.1. Notation and basic concepts
Throughout this paper, we use the same notations as in (Kolda and Bader,2009). Specifically, we adopt
boldface capital letters to denote matrices, e.g.,
M∈RM×N
, boldface lowercase letters, e.g.,
a∈RM
to denote
vectors, and scalars are denoted by lowercase letters, e.g.,
a
. For a matrix
M
, the
i
-th row and
j
-th column are
abbreviated as
Mi
,
Mj
. A third-order tensor is denoted by calligraphic letter, e.g.,
X ∈ Rn1×n2×n3
, whose
(i, j, k)
-
th entry is
xijk
, and we use the MATLAB notation
X(i, :,:)
,
X(:, i, :)
and
X(:,:, i)
to denote the
i
-th horizontal,
lateral and frontal slice, respectively. Specially, the frontal slice
X(:,:, i)
is denoted compactly as
X(i)
. A tubal
fiber (mode-3 fiber)
X(i, j, :)
is obtained by fixing the first two indices and varying the third index. The inner
product of two matrix is given by
⟨A,B⟩= Tr(ATB)
, where
Tr(·)
signifies the matrix trace. The inner product of
two third-order tensors is defined by
⟨A,B⟩ =Pi,j,k ai,j,kbi,j,k
, and the corresponding tensor Frobenius norm is
∥A∥F=p⟨A,A⟩.
For matrices, we introduce the reshaping and vectorization operation for efficient matrix-vector product.
If
X∈RM×N
, then the vectorization of
X
denoted by
vec(X)
is an
NM
-by-
1
vector obtained by stacking the
columns of X:
vec(X) =
X(:,1)
.
.
.
X(:, N)
.(1)
Let A∈Rm×nand m1n1=mn, then the outcome of reshaping A:
B= reshape(A, m1, n1)(2)
is a m1-by-n1matrix defined by vec(B) = vec(A).
Graph Laplacian serves as a regularization term and has ubiquitous applications in geometric matrix
factorization models (Kalofolias et al.,2014;Rao et al.,2015). Given an undirected and possibly weighted
graph
G= (N,E,W)
with nodes
N
and edges
E⊆N×N
weighted with a non-negative weight matrix
(adjacent matrix) W, the graph Laplacian is calculated from the weight matrix:
Lap =D−W,D= Diag(X
i′
wii′).(3)
4
Invertible linear transform, is proved to be a flexible tool for different real data formatted as tensors (Lu et al.,
2019b). Given an invertible linear transform, one can establish a transform induced tensor product (t-product)
and tensor singular value decomposition (t-SVD) accordingly. Let
L∈Cn3×n3
be an arbitrary invertible transform
matrix (e.g., discrete Fourier transform (DFT), discrete cosine/sine transform (DCT/DST), unitary transform
(UT) and graph Fourier transform (GFT)) that satisfies:
LLH=LHL=lIn3,(4)
where
l > 0
is a constant and
H
is the conjugate transposition, then given a third-order tensor
X ∈ Rn1×n2×n3
,
the transform matrix is applied on each tube fiber X(i, j, :) along the third-dimension of X, i.e.,
¯
X(i, j, :) = LX(i, j, :),(5)
which is equivalent to: ¯
X=L(X) = X ×3L,(6)
where we use
L(·)
to denote the linear transform operator,
¯
X
is the transformed tensor, and
×3
denotes the
mode-3 product (Kolda and Bader,2009). Similarly, the inverse transform is given by:
X=L−1(¯
X) = ¯
X ×3LH.(7)
To give an intuitive example, when we adopt the DFT, the transformed tensor can be obtained by performing
DFT of Xalong the third-dimension, i.e., ¯
X= fft(X,[ ],3) by using the MATLAB command fft.
The mechanism of transformed tensor completion is that by imposing transform along certain dimension,
the whole tensor completion problem can be divided into solving a series of small-scale matrix completion
problems for each frontal slice
¯
X(i)
, and their solutions are then concatenated through inverse transform. This
treatment reduces the computational cost of tensor completion and enable us to perform it on large-scale data set
by computing in parallel.
Like the product of two matrices, the product of two tensors induced by linear transform can be defined
analogously.
Definition 1. (t-product (Lu et al.,2019b;Song et al.,2020)) Given any invertible transform
L
, and
A ∈ Rn1×n2×n3
and
B ∈ Rn1×n2×n3
, then the transform based t-product denoted as
C=A∗LB
, is defined such that
¯
C(i)=¯
A(i)¯
B(i)
, for
i= 1, . . . , n3.
Note that
¯
C(i)=¯
A(i)¯
B(i)
can be denoted compactly using the block diagonal matrix. Def. 1implies that
the transform induced t-product can be performed by the matrix-matrix product in the transform domain. In
the following sections, we will adopt this t-product to achieve some important tensor operations in the graph
spectral domain.
3.2. Graph-regularized low-rank tensor learning for traffic speed kriging
Spatiotemporal traffic speed kriging can be treated as a special data imputation problem on a pre-specified
graph so that we can model it through a tensor completion/learning method. Specifically, given an observation
speed matrix
Z∈R(IK)×J
whose rows correspond to
IK
uniformly distributed time points with
I
time intervals
per day within
K
days, and columns correspond to sensors at
J
locations, the objective of spatiotemporal kriging
in this paper can be described as learning the graph signals (node values) at unmeasured locations (entire
columns) and missing time intervals (entire rows), given the observations and graph structure. This can be
formulated as maximum of a posterior probability (MAP):
ˆ
Z= arg max
ZP(Z|ZΩ,Gr,Gc),(8)
where
P(·|·)
is the conditional probability function,
Ω
is the index where rows and columns are measured.
Gr
and
Gc
are prior information about rows and columns, i.e., temporal and spatial correlations in our case. From
the perspective of tensor completion model, MAP is equivalent to the following form:
min
X∥X∥norm +Rs(X) + Rt(X),
s.t. P⊙Z=P⊙T,
X=T(Z),
(9)
where
∥X∥norm
is the tensor norm of
X
to approximate the tensor rank,
Rs(·),Rt(·)
are spatial and temporal
consistency regularization, respectively.
P
is an indicating matrix whose entry is 1 when this data point
is observed and 0 otherwise.
T
is the partially observed matrix,
⊙
is the Hadamard product. Note that
T(·) : R(IK)×J→RI×J×K
denotes a forward tensorization operator that converts the spatiotemporal matrix
5
摘要：

Correlatingsparsesensingforlarge-scaletrafficspeedestimation:ALaplacian-enhancedlow-ranktensorkrigingapproachTongNiea,GuoyangQina,YunpengWangb,JianSuna,∗aDepartmentofTrafficEngineering&KeyLaboratoryofRoadandTrafficEngineering,MinistryofEducation,TongjiUniversity,Shanghai201804,ChinabBeijingKeyLabora...

展开>> 收起<<
Correlating sparse sensing for large-scale traffic speed estimation A Laplacian-enhanced low-rank tensor kriging approach Tong Niea Guoyang Qina Yunpeng Wangb Jian Suna.pdf

共29页,预览5页

还剩页未读， 继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

相关推荐

更多
立即下载
分类：图书资源 价格：10玖币 属性：29 页 大小：7.01MB 格式：PDF 时间：2025-05-06

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 配电装置 动力学连接体 力的合成 高考理综 全宋诗作者索引 公务员考试
/ 29
评分 收藏
分享
立即下载
客服
关注