Extracting dynamic mobility patterns by Hankel dynamic modes
decomposition
Xudong Wang, Lijun Sun∗
Department of Civil Engineering, McGill University, Montreal, Canada
xudong.wang2@mail.mcgill.ca, lijun.sun@mcgill.ca∗ Corresponding author
Extended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

April 11, 2022
Keywords: Mobility pattern, dynamic mode decomposition, smart card data, anomaly detection

1INTRODUCTION

The metro system is becoming an essential component of metropolises, with 182 cities in 56
countries operating metros, carrying an average a total of 168 million passengers per day in 2017
(UITP, 2018). The corresponding high-dimensional spatiotemporal mobility data allow us tounderstand and solve crucial topics in traffic operation and management, such as mobility patterndiscovery, boarding/alighting passenger flow prediction, anomaly detection, to mention but a few.
However, it is challenging to capture the critical features and model the high-dimensional data
due to the complex dependence and interaction among space and time.
As the spatiotemporal mobility data can be naturally summarized into a multidimensional
array, i.e., matrix/tensor, many existing studies apply dimension reduction techniques, suchas principal component analysis (PCA) and matrix/tensor decomposition, to reveal the mobility patterns (Sun & Axhausen, 2016). The principle of these methods is projecting the highdimensional data into a low-dimensional space. They use observations instead of the dynamics ofthe traffic system to analyze the latent patterns, which cannot capture the evolution of the mobility pattern. To fill the gap, we introduce an analytical framework to study the high-dimensional
human mobility data from a dynamic perspective. We apply the dynamic mode decomposition(DMD) with Hankel structure on metro boarding passenger flow to uncover the dynamics ofmobility patterns and detect abnormal passenger flow by predicting future passenger flow.
The DMD is a data-driven technique that can simultaneously extract dynamically spatial structures called dynamic modes with corresponding temporal evolution from observations(Schmid, 2010). Though the DMD is applied in many domains, e.g., fluid mechanics, video
processing, and epidemiology, only a few studies have been published in the transportation area
nowadays (Avila & Mezić, 2020, Lehmberg et al., 2021). The DMD fails to formula the dynamics of the traffic system because the spatial dimension is usually much less than the temporaldimension, which cannot fully capture the system dynamics over the whole period. Therefore,
we use delay embedding (Hankelization) to enlarge the spatial dimension of the traffic data andobtain meaningful dynamic modes. We apply hierarchical clustering to group the dynamic modes
at different timestamps to demonstrate the dynamics of mobility patterns. We also conduct along-term prediction experiment using extracted dynamic modes to evaluate the effectiveness ofthe dynamic modes.
TRISTAN XI Symposium

Revised abstract submittal

X.Wang and L.Sun

22METHODOLOGY

We denote the traffic variable (e.g., metro passenger flow) collected from N locations/stations
at timestamp t as xt ∈ RN , t = 1, · · · , T and the whole data set as X = [x1 , · · · , xT ] ∈ RN ×T .
We assume the traffic system is a locally linear dynamical system so that xt+1 ≈ Axt , whereA ∈ RN ×N is a dynamic matrix. The DMD aims to compute the leading eigendecompositionof the best-fit linear operator A for all the traffic data X. However, the traffic data have rank
mismatch problem due to N ≪ T in practice; therefore, we construct a Hankel matrix H ∈RN K×(N −K+1) to enlarge the data dimension. The Hankelization is a useful data augmentation
technique that recursively augment the data by repeating portions of them (Wang et al., 2021).
Given the delay embedding length K, we can obtain H from X by Hankelization operation H:H(X) := H (k−1)N +1:kN, : = X :, t:N −K+t ,for k = 1, . . . , K, t = 1, . . . , T.

(1)

Similarly, we can obtain ht+1 ≈ AH ht , where ht ∈ RN K is the t column of H and AH ∈RN K×N K is the dynamic matrix for H (Brunton et al., 2016). So the problem turns to be findthe leading eigenvectors and eigenvalues of AH relating the data H 2 ≈ AH H 1 (Tu et al., 2013):
AH = H 2 H +1,(2)where H 1 := [h1 , · · · , hN −K ] ∈ RN K×(N −K) and H 2 := [h2 , · · · , hN −K+1 ] ∈ RN K×(N −K) andH+
1 is the Moore–Penrose inverse of H 1 .
The eigenvectors named dynamic modes reflect the spatially coherent, and the corresponding
eigenvalues determine the time dynamics, e.g., oscillation frequency and decay/growth rate, ofthese modes. This is the backbone of the DMD. However, it is intractable to analyze AH directlyfrom Eq. (2) when the dimension is high. Instead, DMD discover the leading eigenvalues andeigenvectors of AH from a rank-reduced matrix ÃH ∈ Rr×r by taking truncated SVD of H 1 sothat H 1 ≈ U r Σr V Tr (Tu et al., 2013):
ÃH = U Tr AH U r = U Tr H 2 V r Σ−1r ,(3)where U ∈ RN K×r , Σ ∈ Rr×r , V ∈ R(N −K)×r , and r denotes the rank of ÃH . We use cumulativePmin(N K,N −K)
Pλi to determine the rank r: theeigenvalue percentage (CEP) defined as ri=1 λi / i=1first r eigenvalues are selected when the CEP reaches the threshold δ. It has been proved thatAH and ÃH have the same nonzero leading eigenvalues, so we can obtain the eigenvectors
ΦH ∈ CN K×r and eigenvalues λ ∈ Cr of AH by computing the eigenvalue decomposition of ÃH :ÃH W = W diag(λ),ΦH = H 2 V r Σ−1r W,(4)

where columns of W are eigenvectors of ÃH (Kutz et al., 2016). We reshape the dynamic modesΦ to a tensor of size N × r × K and apply hierarchical clustering on frontal slices to discover themobility pattern under different timestamp k.
Given a time period length Tξ , we can reconstruct the Hankel traffic matrix H and predict
the future values by the dynamic modes and eigenvalues:
H DMD = Φdiag(b)Ψ,(5)where b is the mode amplitudes computed as b = Φ+ h1 and Ψ is a Vandermonde matrix ofeigenvalues denoted dynamic evolution, i.e., Ψi,t = λt−1
i , i = 1, . . . , r, t = 1, . . . , Tξ . It has tobe noted that the most eigenvalues will decay to zero due to |λi | < 1, which fails to predict
long-term future values. To address the problem, we set the norm of some eigenvalues to be 1
when |λi | ≈ 1. To the end, we use inverse Hankelization operator H−1 (Wang et al., 2021) totransform the Hankel matrix H DMD back to X DMD .
TRISTAN XI Symposium

Revised abstract submittal

X.Wang and L.Sun

33RESULTS

We apply Guangzhou metro boarding passenger flow collected by a fare collection system (passengers tap in/tap out at fare gantries) to evaluate our model. The data set includes 159 stations
and 3 weeks with 15-min resolution from 6:00 to 0:00, i.e., X ∈ R159×(72×21) . We use the firsttwo weeks’ data as training data to discover the mobility patterns and the third week to evaluate
the prediction performance. We set the Hankel delay embedding length K as 504 (one week)
and the rank threshold δ as 0.9 to determine the number of dynamic modes.
As the dynamic modes describe the spatial coherent, we identify the mobility patterns byhierarchical clustering. Figure 1a and 1b shows the pattern clustering results at 8:00 and 18:00
on Monday, respectively. We can observe from the figure: (1) most stations exhibit spatial
correlation regardless of time, such as neighbor stations are clustered as a group (brown cluster
and gray cluster); (2) some stations are clustered by area function, e.g., all the stations in theblue cluster are transport hubs; (3) some stations have dynamic spatial correlation; for example,
stations in pink group are near the residential area in the morning, carrying passengers to workin the morning, which merges to brown group in the afternoon.

(a) Mobility pattern clustering at 8:00.

(b) Mobility pattern clustering at 18:00.

Figure 1 – Spatial mobility pattern clustering result under two peak hours. Each dot represents astation and the same color denotes same group.

The comparison between boarding flow predictions and observations (ground-truth) is shownin Figure 2a. Each dot in (a) represents one pair of observation and its corresponding predictionin every 15 minutes at all the stations. The size of dots represents the station as a single station(S) or transfer station (T), the color of dots denotes the absolute error. It can be seen thatmost data pairs are predicted accurately (red color) except for several points (blue color). It
demonstrates that the extracted dynamic modes can reproduce the passenger flow. To figureout the reason for inaccurate prediction, we select two points with significant prediction errors(Point A and Point B) from 2a. Point A occurs at 21:45 Saturday at Station 15, and Point B at
22:15 Wednesday at Station 29. We plot the predictions (gray background) of these two stationsin Figure 2b. The same days of the week in the training data (white background) are shown in
the figure as the passenger flow exhibits strong periodicity. It can be seen that unexpected large
boarding flow causes the prediction error in both scenarios. In other words, Point A and Point
B can be regarded as anomalies detected by the model.
TRISTAN XI Symposium

Revised abstract submittal

X.Wang and L.Sun

4(a) Observations and predictions for the third week (b) The prediction of Point A and Point B denoting
using the extracted leading dynamic modes.
in (a).

Figure 2 – The prediction and anomaly detection results.

4CONCLUSION

In this paper, we apply the dynamic mode decomposition with Hankel structure on metro boarding passenger flow to reveal the dynamics of mobility patterns. The Hankelization of mobility
data guarantees that the DMD successfully works on the metro system by enlarging the spatial
dimension and obtaining the dynamic modes simultaneously. Unlike other dimension reduction
methods, the DMD uncovers the dynamical characteristics of the system; therefore, we can exploit the underlying mobility pattern by separately grouping the dynamic modes of stations at
any timestamp. The dynamic correlation between stations can be used as prior information tomodel the spatiotemporal data in future research. Another aspect where the framework shines isthat it can achieve long-term prediction and anomaly detection and deal with data heterogeneity.

References
Avila, AM, & Mezić, I. 2020. Data-driven analysis and forecasting of highway traffic dynamics. Naturecommunications, 11(1), 1–16.
Brunton, Bingni W, Johnson, Lise A, Ojemann, Jeffrey G, & Kutz, J Nathan. 2016. Extracting spatial–temporal coherent patterns in large-scale neural recordings using dynamic mode decomposition. Journalof neuroscience methods, 258, 1–15.
Kutz, J Nathan, Brunton, Steven L, Brunton, Bingni W, & Proctor, Joshua L. 2016. Dynamic mode
decomposition: data-driven modeling of complex systems. SIAM.
Lehmberg, Daniel, Dietrich, Felix, & Köster, Gerta. 2021. Modeling Melburnians—Using the Koopman
operator to gain insight into crowd dynamics. Transportation Research Part C: Emerging Technologies,
133, 103437.
Schmid, Peter J. 2010. Dynamic mode decomposition of numerical and experimental data. Journal offluid mechanics, 656, 5–28.
Sun, Lijun, & Axhausen, Kay W. 2016. Understanding urban mobility patterns with a probabilistic
tensor factorization framework. Transportation Research Part B: Methodological, 91, 511–524.
Tu, Jonathan H, Rowley, Clarence W, Luchtenburg, Dirk M, Brunton, Steven L, & Kutz, J Nathan. 2013.
On dynamic mode decomposition: Theory and applications. arXiv preprint arXiv:1312.0041.
UITP. 2018. World metro figures 2018–statistic brief. https://cms.uitp.org/wp/wp-content/
uploads/2020/06/Statistics-Brief-World-metro-figures-2018V3_WEB.pdf.
Wang, Xudong, Wu, Yuankai, Zhuang, Dingyi, & Sun, Lijun. 2021. Low-Rank Hankel Tensor Completion
for Traffic Speed Estimation. arXiv preprint arXiv:2105.11335.

TRISTAN XI Symposium

Revised abstract submittal