Anomaly based Incident Detection in Large Scale Smart
Transportation Systems
Md. Jaminur Islam∗Jose Paolo Talusan∗

Shameek Bhattacharjee‡

Western Michigan University
Kalamazoo, MI, USA
mohammadjaminur.islam@wmich.edu

Nara Institute of Sc. and Tech.
Nara, Japantalusan.jose_paolo.tg3@is.naist.jp

Western Michigan University
Kalamazoo, MI, USA
shameek.bhattacharjee@wmich.edu

Francis Tiausas

Sayyed Mohsen Vazirizade

Abhishek Dubey

Nara Institute of Sc. and Tech.
Nara, Japantiausas.francis_jerome.ta5@is.naist.jp

Vanderbilt University
Nashville, TN, USA
s.m.vazirizade@vanderbilt.edu

Vanderbilt University
Nashville, TN, USA
abhishek.dubey@vanderbilt.edu

Keiichi Yasumoto

Sajal K. Das

Nara Institute of Sc. and Tech.
Nara, Japan
yasumoto@is.naist.jp

Missouri University of Science andTechnology
Rolla, MO, USA
sdas@mst.edu

ABSTRACT
Modern smart cities are focusing on smart transportation solutions to detect and mitigate the effects of various traffic incidents
in the city. To materialize this, roadside units and ambient transportation sensors are being deployed to collect vehicular data thatprovides real-time traffic monitoring. In this paper, we first proposea real-time data-driven anomaly-based traffic incident detection
framework for a city-scale smart transportation system. Specifically,
we propose an incremental region growing approximation algorithm for optimal Spatio-temporal clustering of road segments andtheir data; such that road segments are strategically divided into
highly correlated clusters. The highly correlated clusters enable
identifying a Pythagorean Mean-based invariant as an anomaly
detection metric that is highly stable under no incidents but showsa deviation in the presence of incidents. We learn the bounds ofthe invariants in a robust manner such that anomaly detection can
generalize to unseen events, even when learning from real noisy
data. We perform extensive experimental validation using mobility
data collected from the City of Nashville, Tennessee, and prove thatthe method can detect incidents within each cluster in real-time.

KEYWORDS
Unsupervised Learning, Anomaly Detection, Smart Transportation,
Graph Algorithms, Cluster Analysis, Regression,Incident Detection

1

INTRODUCTION

Rapid urbanization has proliferated the number of vehicles in cities
leading to increasing congestion and a higher number of traffic accidents. For any traffic accident, delayed detection and response fromfirst responders or emergency management agencies can worsen
into heavy city-wide congestion and even in the loss of life. This
∗ Both authors contributed equally to this research.
‡ Corresponding Author

delay is one of the most important challenges faced by communities
across the globe [11].
To monitor the transportation infrastructure, three approaches
have emerged to increase the visibility of real-time road conditions:(i) vehicular crowdsourcing, (ii) video-based anomaly detection;and (iii) sensor-based data collection.
Vehicular crowdsourcing involves cities leveraging commercial
crowdsourcing platforms (such as Waze), to gather content reported
by citizen users on these platforms to get real-time observations
on traffic events. However, traffic incident detection is often unreliable and strong verification of the human reported data cannot be
guaranteed in real-time.
Video anomaly detection[4] leverages cameras and sensors deployed by the city to detect traffic emergencies. This approachrequires expensive edge devices, longer model training times, andcontinuous maintenance. Many environmental and connectivity
constraints also negatively influence video quality and real-time
availability. The computational resources needed to monitor andidentify traffic incidents are high and not community scalable.
To avoid the above problems in these two paradigms, smart cities
are deploying traffic sensors and Road Side Units (RSU) along roads
and highways that collect traffic data from speed sensors or smart
cars [8]. The RSU infrastructure is a typical IoT network that isdecentralized, low-powered, and resource-constrained in nature.
However, given the ubiquity and number of devices, the RSU
infrastructure can be utilized to work together in a distributed capacity, to design intelligent lightweight anomaly-based traffic incident
detection in real-time that would otherwise be too computationallyintensive, geographically impossible, or costly.
Challenges: We view traffic incidents as anomalies that occur
between otherwise normal traffic patterns. However, characterizing a normal traffic pattern that works at a large city scale is notstraightforward due to (i) day-to-day variability of traffic, (ii) local
neighborhood dependencies, (iii) a large number of speed sensors

ICCPS ’22, May 4–6, 2022, Milan, Italy

and road segments. Hence, the nature of the problem falls undersmart living CPS, which, unlike industrial CPS, are not just boundby tightly defined laws of physics. Therefore, the anomaly detection
problem is much more challenging and requires novel advances
compared to existing theories of anomaly detection in CPS.
Furthermore, some previous works on smart metering [1] haveattempted to solve the anomaly detection challenge in smart living
CPS. However, such efforts used data collected from small experimental testbeds. Thus, the scale of the problem was smaller, andtraining data was free from noise. In contrast, our transportation
CPS setting includes data collected from the wild, across a wholecity. This needs to be accounted for in the design. Specifically,
geospatial factors need to be blended with causal factors of the underlying structure of the data that characterizes benign situations.
While many prior works exist in this area, the effort in thispaper takes the challenge for the whole city with a dataset analyzed
over one year to account for all seasonal and human behavioral
effects. The validation and the performance metrics reported arevery robust compared to existing works in [7, 13, 14].
Paper Contributions: We propose an unsupervised time series
based anomaly detection framework for large-scale smart transportation networks that detects traffic incidents in real-time while
maintaining a low false alarm rate. The framework automatically
pinpoints the area of incident occurrence.
Specifically, we first show theoretical parallelism between thetransportation problem and an existing anomaly detection metric(Harmonic to Arithmetic Mean ratios) previously developed foranomaly detection in smart energy systems. Second, we propose
a region-growing approximation algorithm that allows to strategically partition the smart transportation CPS into clusters where
the data is highly positively correlated. The strategic partitioning
guarantees 1) high invariance of the anomaly detection metric andallows 2) decentralized cluster-wise implementation of our detection framework which enables the framework to pinpoint the areaof the incident. Third, we propose a data cleaning and augmentation
technique to enable learning the underlying structure of benign conditions from the data collected from the wild to reduce false alarms.
Fourth, we give a technique to learn the bounds of the anomaly detection metric in each of the strategic partitions under normal traffic
conditions to establish the anomaly detection criterion. Finally, we
validate our approach through extensive large-scale experimentson real mobility datasets (6928 road segments over 1 year) acquired
from the City of Nashville, Tennessee. Results show that our model
is able to detect traffic incidents in real-time. The performance ismeasured by comparing our framework’s decisions with a separate
ground truth dataset containing actual incidents recorded by the
Nashville Fire and Safety Department.
The rest of the paper is organized as follows: Section 2 discusses
the related work. Section 3 introduces the transportation systemmodel. Section 4 discusses the proposed framework. Experimental
results are discussed in Section 5 followed by conclusions.

2

PREVIOUS WORK

Existing research on automatic incident detection for cyber-physicaltransportation systems broadly falls into two classes. They can

Md. J. Islam and J.P. Talusan, et al.

be classified into model-based and data-driven approaches. Modelbased approaches [6, 10] include probabilistic models [17], fuzzy Cmeans clustering [16], and state-based methods which used Kalman
Filtering [9] to describe the state of monitored traffic so that usual
traffic behaviors can be learned and unusual incidents can be detected. However, these methods require realistic assumptions for thetarget area and assume that their forecasting models are representative of true uncertainty in the data. Thus, they require extensive
time-series validation.
Data-driven approaches, on the other hand, include classification
methods which typically include nearest neighbors [12], neuralnetworks, and support vector machines. These methods requirelabeled data to train and introduce new challenges regarding user
data privacy. Techniques such as convolutional-LSTM models andneural networks [18], consume a lot of time comparing real-timedata with historical data and have high computational costs limiting
their effectiveness in decentralized deployments.

3

SYSTEM MODEL DESCRIPTION

The smart transportation CPS monitors the physical world of roadconditions via TMC sensors that are deployed in each road segment.
In our setting, there is one TMC sensor per road segment, so thenumber of TMC sensors equals the number of road segments. The
data collected from TMC is used for various operational decisions
that can control the appropriate volume of traffic to reduce thedisturbance in mobility and travel times.
The TMC sensors are small computational units with minimal
memory. Hence, each captured information is sent to a Road Side
unit [15] (RSU). Each RSU receives data from multiple TMCs andhas a larger computational power and memory. The RSUs usually
have a wired backhaul link to an edge or cloud server, where datafrom all TMCs of an area of interest is accumulated. Dependingon implementation variations, the RSU itself could also serve as adecentralized edge server for edge analytics. However, the systemlevel implementation is out of the scope of our paper. We provide aframework that can run on the edge or fog, based on the computational and networking capabilities available to the smart city.
For this paper, a traffic incident is an anomalous event suchas vehicular accidents, crime, or man-made disaster affecting traffic
flow, fire, non-recurring high duration congestion to which the police,
emergency, and fire safety required a response. The ground truth
information on incidents was collected from Nashville Fire and
Safety Department. This ground truth information contains thelocation, time stamp, and date of each incident responded by theCity of Nashville in the year 2019.
Our goal in this paper is to develop a framework and learn theparameters that automatically detect congestion in real-time in
the test/deployment stage. The ground truth information during
the testing set is used to measure the incident detection accuracyof our anomaly detection framework. The ground truth information during the training phase is used to cross-reference for data
augmentation and cleaning that enables efficient learning of theunderlying structure of data corresponding to benign conditionsin the transportation CPS. Each TMC at the end of a time window 𝑡 sends the following information to the RSU: timestamp, roadsegment ID, mean speed over the 𝑡-th time window). The TMC
sensor is located at the center of each road segment. Therefore, theAnomaly based Incident Detection in Large Scale Smart Transportation Systems

distance between two road segments is the distance between the
midpoint of any two road segments. The TMCs capture ambient
speeds as vehicles pass by over a particular road segment.

4

PROPOSED FRAMEWORKFirst, we provide a high-level overview of the framework followed
by a summary of the notations used in this paper in Table 1. There
are five logical modules in which the contribution is divided:
Theoretical Intuition: We discuss the choice of harmonic mean
to arithmetic mean ratio metric [1] as an anomaly detection metric,
its relevance to the problem, and its advantages and modifications
necessary to fit the transportation application.
Region Growing Approximation: For the metric to achieve
invariance, we need spatial and temporal partitions of the highdimensional data at which the positive correlation within eachpartition is maximized, which is achieved through a region growing
approximation algorithm.
Invariant Design: Involves metric derivation after the region
growing approximation.
Pre-processing and Augmentation: Due to the characteristics
of real-world traffic data, the invariant contains the effects of accidents. This poses a practical problem for unsupervised learning
problems such as anomaly detection. Therefore, our framework
invokes a data cleaning and sanitization technique to augment
synthetic benign samples of the invariant.
Learning normal operating range of invariant: Once thecleaning has been done, we obtain a low dimensional invariant
that is a suitable candidate for pattern recognition of this invariant
that remains stable when there are no incidents.
Anomaly Detection Criterion: We identify the best hyperparameter inputs to the training algorithm that gives the best output.
Table 1: List of symbols.
Symbol
𝐶
𝑐𝑘
𝑆
𝑛
𝑆𝑐 𝑘
𝑠𝑐𝑙
𝑘

𝑝𝑐𝑢𝑡
𝑡
𝑚
𝑑𝑠𝑙 (𝑡 )Speed correlation
Correlation thresholdCut off correlation value
Time slot, based on temporal granularity
Number of time slots
Mean speed 𝑑 at segment 𝑙 within 𝑆𝑐𝑘 at time 𝑡

𝐻 𝑀𝑐𝑘 (𝑡 )𝐴𝑀𝑐𝑘 (𝑡 )𝑄𝑐𝑘 (𝑡 )Harmonic Mean of cluster 𝑐𝑘 at time window 𝑡
Arithmetic Mean of cluster 𝑐𝑘 at time window 𝑡
Q-ratio metric of cluster 𝑐𝑘 at time window 𝑡𝑝𝑝 (𝑚𝑖𝑛)𝑐𝑘

Γ𝑐𝑘

Description
Total clusters in the target area
𝑘 𝑡ℎ cluster within the set of clusters 𝐶
Set of segments in the target area
Number of segments
Set of segments located in cluster 𝑐𝑘
𝑙 𝑡ℎ segment in the 𝑘 𝑡ℎ clusterℎ𝑖𝑔ℎ(𝑡 ), Γ𝑐𝑙𝑜𝑤
(𝑡 )
𝑘

𝜏𝑐𝑚𝑎𝑥
(ℎ), 𝜏𝑐𝑚𝑖𝑛(ℎ)
𝑘𝑘∇𝑐𝑘 (𝑡 )𝜅𝑆𝐹

Upper and lower Safe margins for the ratio of cluster 𝑐𝑘 attime 𝑡 , exceeding these results in non-zero residuals
Upper and lower standard limits of cluster 𝑐𝑘 over historical
data ℎResiduals for the ratios of cluster 𝑐𝑘 , a non-zero residual
indicates a possible anomaly
Scalar Factor Hyperparameter
Sliding Frame Size Hyperparameter

ICCPS ’22, May 4–6, 2022, Milan, Italy

4.1

Theoretical Intuition

For a large scale CPS application such as smart transportation, theanomaly detection metric should have the following properties:(1) Invariance Under Benign Conditions: Under no incidents, themetric should show minimal change across time and across history.
This is important to reduce false alarms given the low base rate ofincident occurrence.
(2) Deviation Under Incidents: Under incidents, the metric shouldhave properties that cause quick and discernible deviation in themetric. This is important to increase detection accuracy.
As a starting point, we leverage a recent result from [1] thatshowed that a collection of positively correlated random variables
sampled repeatedly over time can be represented as a time seriesof ratio between the harmonic to the arithmetic mean of the aggregate data; and can be used as an anomaly detection metric. This isbecause this the metric is stationary in its time series as long as apositive co-variance structure can be preserved. Any unforeseen
data falsification attack that disturbs the space-time covariancestructure will cause deviations in the otherwise stationary timeseries of Harmonic Means to Arithmetic Means. In the following,
we explain the theoretical explanation of why the HM to AM ratio
is a good starting point for our problem and examine what novel
theoretical and applied contributions are necessary to make it work
for incident detection for a transportation CPS.
4.1.1 Invariance Under Benign Conditions. Here we explain
why the harmonic to the arithmetic mean ratio is a candidate for an
anomaly detection metric that is invariant under benign conditions.
The basic premise is that humans react with some shared driving
behavior based on the time of the day, traffic level on the road,road type (highway or city lanes), and road width, etc. Such shared
driving behavior in the absence of incidents causes driving speeds
to increase or decrease together, or remain similar that in turn manifests itself as having high positive correlation among data points.
One of the achievements of [1] is that it proved that the upperbound on the absolute difference between the arithmetic mean andharmonic mean of the data collected from a positively correlated
system depends on two things: (1) minimum possible value of thedata (denoted by 𝑑𝑚𝑖𝑛 ) and (2) the average difference in data observed between any two arbitrary sensing end-points averaged
over an appropriate time granularity (say, 𝑇 ), (denoted by 𝜉 (𝑇 )).
As long as it can be guaranteed that 𝑑𝑚𝑖𝑛 and 𝜉 (𝑇 ) do not changewith time, the invariance in the harmonic to the arithmetic mean
ratio is guaranteed. We identified, however, that 𝜉 (𝑇 ) does notchange only under strategic spatial and temporal partitions which is
nontrivial to achieve for a transportation CPS.
Note that, the studies [1, 2] worked with a small experimental
micro-grid. Furthermore, weather in a city affects all areas equallywhich implicitly preserves similar city-wide power consumption
patterns. For the above reasons, a positive correlation was implicitly
guaranteed in the advanced metering infrastructure (AMI) application. However, this is not the case with transportation applications.
In a transportation CPS, data is collected from the wild, andcities are a complex mix of narrower lanes and highways. The
data is also affected by the uniqueness of the neighborhoods (e.g.
downtown vs uptown) and thus a positive co-variance structure is

ICCPS ’22, May 4–6, 2022, Milan, Italy

Md. J. Islam and J.P. Talusan, et al.

not implicitly guaranteed. Therefore, a computationally tractableclustering method is required to achieve invariance.

to the exact solution. This is done by first converting the clustering
problem into a graph problem.

4.1.2 Deviation Under Incidents. Another key achievementof [1] and [2] is that it proved that any short-lived disturbanceon the covariance structure will lead to deviation in any metric thatcombines Harmonic and Arithmetic Mean calculated from a highly
positively correlated set of random variables. This is attributed toan asymmetry in Schur Concavity properties. The Harmonic Meanis strictly Schur Concave while Arithmetic Mean is Schur Convex.
This imbalance causes deviations in the HM to AM ratio metricwhenever any event triggers a decrease in the correlation.
4.1.3 Domain-Specific Challenges: We need to realize the following domain-specific adaptations:First, in [1], the strength of the positive correlation was implicit
in smart metering CPS. However, in transportation CPS, several
localized factors affect traffic data patterns in sub-areas of the city.
This requires intelligent clustering that preserves a high space-timecovariance structure strategically. Second, [1] was designed for
power consumption data from smart meters for a small experimental micro-grid. In such applications, geospatial factors play littlerole, which is not the case with city-wide smart transportation
CPS. This requires bounding the clustering region size. Third, AMI
application had only one observation per hour and the framework
proposed was suitable for attack detection and not incident detection. The time for detection of attacks was in the order of hours.
In our CPS use case, incident detection needs to happen withinminutes. This requires too many detection rounds, increases thefalse alarm reduction challenge. Fourth, in [1] the data was freefrom anomalies due to a controlled environment of an experimental
micro-grid. Instead, this application contains data from the wildfrom a real city and therefore framework adaptions are necessary
to learn the underlying structure of the benign pattern of the CPS.

4.2

Region Growing Clustering Algorithm

This is the main theoretical core of the contribution which mainly
addresses the first two challenges. We need to strategically groupthe road segments into spatial clusters such that the speed data has
maximum positive correlation which leads to the highest invariance. At the same time, the clustering needs to be geographicallyproximate for disturbances in the co-variance structure to have acausal link to the traffic incidents.
All the road segments exhibiting correlations above a threshold may be grouped together to form a cluster. Thereafter, if 𝐶 ={𝑐 1, ...𝑐𝑘 , ...𝑐 𝐾 } is a candidate cluster set and 𝑠𝑖 and 𝑠 𝑗 are any tworoad segments where 𝑖 ≠ 𝑗, 1 ≤ 𝑖, 𝑗 ≤ 𝑛 such that 𝑠𝑖 and 𝑠 𝑗 are in
the same cluster 𝑐𝑘 , we can formalize the problem as the following:
max

Õ

Õ

𝑐 ∈𝐶

{𝑠𝑖 ,𝑠 𝑗 } ∈𝑐s.t. 𝐶𝑜𝑟 (𝑠𝑖 , 𝑠 𝑗 ) > 𝑝

𝐶𝑜𝑟 (𝑠𝑖 , 𝑠 𝑗 )
(1)
(𝑚𝑖𝑛)

In the above optimization 𝐶𝑜𝑟 (𝑠𝑖 , 𝑠 𝑗 ) represents the correlation
between two road segments and 𝑝 (𝑚𝑖𝑛) is a threshold. The above
optimization problem is 𝑁 𝑃 hard since with |𝑆 | number of roadsegments, there is an exponential number of possible solutions
which is computationally intractable. We need an approximation

Figure 1: Problem Reformulation to Graph Problem
Reformulation into a Graph Problem We convert our optimal clustering problem into a graph problem, where we visualize
each road segment as a vertex on the graph 𝐺 ′ and the road segment connections as an edge. The weight of an edge is equal tothe correlation between the road segments (vertices) it connects.
Fig. 1 shows the remapped graph abstraction from the original road
network to our reformulated graph mapping.
Theoretically, a correlation may exist between any pair of roadsegments. Therefore the initial graph 𝐺 ′ is a complete graph. However, since all road segments are not necessarily positively correlated (e.g. geographically distant, city roads to highways in thesame geographical area), there will be edges with negative or zeroweights and relatively low weights. Let there be a bound on theminimum correlation value 𝑝𝑐𝑢𝑡 > 0 necessary to be considered afeasible edge of the graph. All edges whose weights are less than𝑝𝑐𝑢𝑡 are pruned from the complete graph. A low 𝑝𝑐𝑢𝑡 affects thelevel of invariance in the ratio invariant which is key to a low false
alarm and improved detection performance.
Formally, this reduced graph is denoted as 𝐺 = (𝑉 , 𝐸), where 𝑉
is the set of vertices and 𝐸 is the set of edges. The set of vertices
and edges are indexed by 𝑣 ∈ 𝑉 and 𝑒 ∈ 𝐸. Each edge 𝑒 is assigned
a weight 𝑝𝑒 that is equal to the correlation between its two vertices,𝑣𝑖 and 𝑣 𝑗≠𝑖 , where 𝑣𝑖 , 𝑣 𝑗 ∈ 𝑉 .
Edge Preference Hyper-parameter (𝑝𝑐𝑢𝑡 ): From the feasible set, we
introduce a notion of desirability to form the strongest groupingof clusters. Note, only using Euclidean distance is not appropriate
for causal link because a narrow lane may have a highway roadsegment running over it. Geographically they are close, but even
if one incident is affecting a ramp connecting the two, the correlation will not be as strong due to inherent differences in their
physical characteristics. Also, some roads are long and can see anincident’s effect quickly propagate, and segments not geographically very close still become affected by that same incident when
not geographically close. Hence, we bring in a notion of edge preference hyper-parameter 𝑝𝑐𝑢𝑡 < 𝑝 (𝑚𝑖𝑛) < 1. Using 𝑝 (𝑚𝑖𝑛) separates′
all edges 𝐸 into two subsets. We let the set 𝐸𝑠 include all edges(𝑚𝑖𝑛)𝑠whose 𝑝𝑒 < 𝑝while the set 𝐸 include those edges whose𝑝𝑒 ≥ 𝑝 (𝑚𝑖𝑛) . This separation improves causal linkage.
Distance Weight Variable (𝑥𝑒 ): As explained earlier, geographicallycloser road segments will be affected by the same incident. Hence,the distance should be factored in the clustering too. Each edge 𝑒 ∈ 𝐸

Anomaly based Incident Detection in Large Scale Smart Transportation Systems

can be visualized as associated with a weight variable, 𝑥𝑒 ∈ (0, 1].
The weight 𝑥𝑒 equals the normalized distance between two vertices(road segments) such that 𝑥𝑒 = 𝑑𝑑𝑑𝑑𝑒 , where 𝑑𝑑𝑒 is the distances𝑚𝑎𝑥
between two vertices of edge 𝑒 and 𝑑𝑑𝑚𝑎𝑥 is the maximum distanceamong all distances between any pair of vertices.
Many optimization problems are formulated as error minimization problems where error is an unfavorable outcome that needs tobe minimized. In our setting, two kinds of errors happen for any
candidate solution (cluster). First, the two end vertices {𝑣𝑖 , 𝑣 𝑗 } ofan edge 𝑒 has correlation value 𝑝𝑒 > 𝑝 (𝑚𝑖𝑛) but they are in two
different candidate clusters (positive error). Second, the two end
vertices {𝑣𝑖 , 𝑣 𝑗 } of an edge 𝑒 has correlation value 𝑝𝑒 < 𝑝𝑚𝑖𝑛 but
they are in the same cluster negative error. By minimizing these
two errors, the optimal clustering can be achieved, maximizing thecorrelations in a cluster.
Transformed Optimization Problem: In the graph-theoretic mapping of the original network, the original optimization can then be
re-written as the following:h ÕiÕ
arg min𝑝𝑒 𝑥𝑒 +𝑝𝑒 (1 − 𝑥𝑒 )
𝐶
′
(2)
𝑒 ∈𝐸𝑠
𝑒 ∈𝐸𝑠
s.t. 𝑥𝑒 ∈ (0, 1]
In the above optimization, the first term includes all positive
errors for a given candidate solution 𝐶, when 𝑒 ∈ 𝐸𝑠 (they have𝑝𝑒 ≥ 𝑝 (𝑚𝑖𝑛) ) and {𝑣𝑖 , 𝑣 𝑗 } are not in the same candidate cluster 𝐶.
Similarly, the second term includes all negative errors for the same′candidate solution 𝐶, when 𝑒 ∈ 𝐸𝑠 (they have 𝑝𝑒 < 𝑝 (𝑚𝑖𝑛) ) and{𝑣𝑖 , 𝑣 𝑗 } are in the same candidate solution 𝐶. We need to find thesolution 𝐶 which jointly minimizes both errors.
In [3], a clustering problem for a weighted graph which has thesame form as Eqn. 2, was solved. Their study revealed that therelaxed form of the integer problem has an Ω(log 𝑛) integrality gap.
Hence, the best-known factor of the approximation can be 𝑂 (log 𝑛).
Hence, it ensures theoretical guarantees to our approach.
Approximation Algorithm: To understand the core idea of theapproximation algorithm, which is based on growing a region withradius 𝑟 from some random starting point, we first need to definesome key elements.
Region: A 𝑅𝑒𝑔𝑖𝑜𝑛(𝑣𝑖𝑛𝑖𝑡 , 𝑟 ) is the set of road segments 𝑣 ∈ 𝑉 thatare within the area with radius 𝑟 from an initial vertex 𝑣𝑖𝑛𝑖𝑡 .
Cut: A 𝑐𝑢𝑡 (𝑐), where 𝑐 ∈ 𝐶, is the sum of the weights of the edges𝑒 ∈ 𝐸𝑠 with 𝑝𝑒 > 𝑝 (𝑚𝑖𝑛) where each edge 𝑒 has one vertex 𝑣𝑖 ,within 𝑐 and the other 𝑣 𝑗 , is outside.
Õ
𝑝𝑒(3)𝑐𝑢𝑡 (𝑐) ={𝑣𝑖 ,𝑣 𝑗 }∩𝑐=1
𝑒 ∈𝐸𝑠

Volume: 𝑣𝑜𝑙 (𝑐) is also the total sum of the weights of the edges𝑒 ∈ 𝐸𝑠 , with 𝑝𝑒 > 𝑝 (𝑚𝑖𝑛) , where at least one vertex 𝑣𝑖 or 𝑣 𝑗 is inside
the cluster.
Õ𝑣𝑜𝑙 (𝑐) =𝑝𝑒 𝑥𝑒(4){𝑣𝑖 ,𝑣 𝑗 } ∈𝑐𝑒 ∈𝐸𝑠The algorithm 1 returns the set of different clusters. The formation of one cluster happens via the region growing process. The coreof the region growing approximation corresponds to the lines 3-7

ICCPS ’22, May 4–6, 2022, Milan, Italy

Algorithm 1: Approximation Algorithm
Input: 𝐺 = (𝑉 , 𝐸)
Output: 𝐶 = 𝑐 1 , ..., 𝑐 𝐾
Initialize: 𝑘 = 1, 𝐶 = { }1 begin2
while 𝐺 𝑖𝑠 𝑛𝑜𝑡 ∅ do3
𝑠𝑒𝑙𝑒𝑐𝑡 𝑟𝑎𝑛𝑑𝑜𝑚 𝑣𝑖𝑛𝑖𝑡 ∈ 𝑉
4𝑟 → 𝑟𝑖𝑛𝑖𝑡
5
while 𝑐𝑢𝑡 (𝑅𝑒𝑔𝑖𝑜𝑛 (𝑣𝑖𝑛𝑖𝑡 , 𝑟 )) ≥ 𝑣𝑜𝑙 (𝑅𝑒𝑔𝑖𝑜𝑛 (𝑣𝑖𝑛𝑖𝑡 , 𝑟 )) do
6𝑟 → 𝑟 + min(𝑑 𝑣𝑖𝑛𝑖𝑡 ,𝑣 − 𝑟 )𝑣∈𝑉𝑣∉𝑅𝑒𝑔𝑖𝑜𝑛 (𝑣𝑖𝑛𝑖𝑡 ,𝑟 )

7
8
9
10
11

𝑐𝑘 = 𝑅𝑒𝑔𝑖𝑜𝑛 (𝑣𝑖𝑛𝑖𝑡 , 𝑟 )𝑖𝑛𝑠𝑒𝑟𝑡 (𝑐𝑘 , 𝐶)𝑟𝑒𝑚𝑜𝑣𝑒 (𝑐𝑘 , 𝐺)
𝑘 →𝑘 +1
return 𝐶 = 𝑐 1 , 𝑐 2 , ...𝑐 𝐾

in Algorithm 1 which decides what is included in one cluster, while
the rest of the algorithm repeats the process of finding clusters forthe whole graph. It starts at a random vertex 𝑣𝑖𝑛𝑖𝑡 with an initial radius 𝑟 1 = 𝑟𝑖𝑛𝑖𝑡 > 0, that forms an initial region 𝑅𝑒𝑔𝑖𝑜𝑛(𝑣𝑖𝑛𝑖𝑡 , 𝑟 1 ). To
illustrate, Fig. 2a represents an initial region centered on a random
vertex (shaded in red) with radius 𝑟 1 .
Next it finds nearest vertex 𝑣, in the neighborhood of the initialregion. To find the nearest vertex, it lists all other vertices 𝑣𝑛𝑒𝑎𝑟
such that each vertex in set 𝑣𝑛𝑒𝑎𝑟 includes only vertices that are
directly connected to the region 𝑅𝑒𝑔𝑖𝑜𝑛(𝑣𝑖𝑛𝑖𝑡 , 𝑟 1 ). The term “directly
connected to the region” implies that an edge exists between avertex in 𝑣𝑛𝑒𝑎𝑟 and any vertex inside 𝑅𝑒𝑔𝑖𝑜𝑛(𝑣𝑖𝑛𝑖𝑡 , 𝑟 1 ) (any vertex
shaded red). For illustration, in Fig. 2a, 𝑣 1 and 𝑣 2 are the only vertices
directly connected to the 𝑅𝑒𝑔𝑖𝑜𝑛(𝑣𝑖𝑛𝑖𝑡 , 𝑟 1 ).
It then calculates the euclidean distance from 𝑣𝑖𝑛𝑖𝑡 to each vertex
in 𝑣𝑛𝑒𝑎𝑟 and selects the vertex 𝑣 that is nearest 𝑣𝑖𝑛𝑖𝑡 . Let this smallest
distance (from 𝑣𝑖𝑛𝑖𝑡 ) be denoted as 𝑑 (𝑣𝑖𝑛𝑖𝑡 ,𝑣) . This distance is used as
the radius of the new region such that 𝑟 2 = 𝑑 (𝑣𝑖𝑛𝑖𝑡 ,𝑣) . Since 𝑟 2 > 𝑟 1 ,the region grows from the initial region, hence the term region
growing approximation. This is illustrated in Fig. 2b, where 𝑟 2 isformed by the distance between the nearest vertex 𝑣 1 and 𝑣𝑖𝑛𝑖𝑡 .
Note, that with the new region, the set 𝑣𝑛𝑒𝑎𝑟 now includes 𝑣 2and 𝑣 3 . For simplicity, let’s drop the suffix of the radius parameter such that the radius at any iteration of region growth is denoted simply by 𝑟 . The region then continuously grows until the𝑣𝑜𝑙 (𝑅𝑒𝑔𝑖𝑜𝑛(𝑣𝑖𝑛𝑖𝑡 , 𝑟 )) is greater than 𝑐𝑢𝑡 (𝑅𝑒𝑔𝑖𝑜𝑛(𝑣𝑖𝑛𝑖𝑡 , 𝑟 )) (See line
5 in Algorithm 1). When this stopping condition is met, the region
stops growing and we achieve our first cluster 𝑐𝑘 = 𝑐 1 where 𝑘 = 1.
We insert this first cluster into our final cluster set denoted by 𝐶
(See line 8 in Algorithm 1).
All the vertices in cluster 𝑐 1 are then removed from the graph
𝐺 to avoid duplication while generating other clusters (line 9 in
Algorithm 1). Finally, 𝑘 is increased by 1 for the next iteration. The
process starts again with a new initial region centered around a new
random vertex 𝑣𝑖𝑛𝑖𝑡 . It generates the cluster 𝑐𝑘 = 𝑐 2 by executing
the lines 3 − 7 which is added to the cluster set 𝐶 before removing
the vertices in cluster 𝑐 2 from graph 𝐺. Algorithm 1 continues until
there are no vertices left to cluster (see line 2 in Algorithm 1). Oncethe graph 𝐺 is empty, the set of clusters 𝐶 is returned.

ICCPS ’22, May 4–6, 2022, Milan, Italy

Md. J. Islam and J.P. Talusan, et al.

(a)

(b)

(c)

Figure 2: (a) A region around the initial node. (b) Increased radius for the region based on the nearest segment whose one
connecting end is inside the previous region. (c) A region where the volume is greater than cut.

4.3

Ratio Invariant per Cluster

The clustering process ensures clusters that maximize the correlation strategically. Let any cluster 𝑐𝑘 have |𝑆𝑐𝑘 | number of roadsegments. Then, we calculate a ratio metric 𝑄𝑐𝑘 (𝑡) for every cluster
𝑐𝑘 at each time window 𝑡, which is the invariant. The ratio metric isdefined as the ratio of the harmonic mean 𝐻𝑀𝑐𝑘 (𝑡) and arithmetic
mean 𝐴𝑀𝑐𝑘 (𝑡) of data collected from all TMC road segments within
Í |𝑆𝑐𝑘 |a cluster such that:
𝑑𝑆 𝑙
𝑆𝑐 𝑘
𝑙=0
𝑐𝑘
𝐻 𝑀𝑐𝑘 (𝑡) = Í
𝐴𝑀𝑐𝑘 (𝑡) =(5)|𝑆𝑐𝑘 | 1
𝑆𝑐 𝑘
𝑙=0

𝑑𝑆 𝑙

𝑐𝑘

where 𝑑𝑆 𝑙 is the aggregate speed reported by the 𝑙-th TMC for a

1.1

1.0

1.0

0.9

0.9

0.8

0.8

Qratioincident

Q-ratio

1.1

Q-ratio

Complexity Analysis: The approximation algorithm takes polynomial time to cluster all the segments. To prove that, we canassume that no two vertices are at the same distance level fromthe initial random vertex 𝑣𝑖𝑛𝑖𝑡 . Therefore, it will be safe to assume
that at each iteration of the inner loop a single node will be addedin 𝑟𝑒𝑔𝑖𝑜𝑛(𝑣𝑖𝑛𝑖𝑡 , 𝑟 ). If there are 𝑚 1 number of vertices for the firstcluster, then there will 𝑛 −𝑚 1 number of vertices available to clusterin the next iteration. If this same process runs 𝑘 𝑡ℎ number of times
until there will be no vertex left to cluster, it can be shown that𝑛 −𝑚 1 −𝑚 2 − ... −𝑚𝑘 = 0 where 𝑚 2, 𝑚 3, .., 𝑚𝑘 are the number of vertices in successive clusters. This implies that 𝑛 = 𝑚 1 + 𝑚 2 + ... + 𝑚𝑘
which is the total number of segments. Therefore, for 𝑛 number ofsegments, the algorithm performs clustering at most 𝑛 number oftimes. Hence, the complexity of the algorithm is bounded by 𝑂 (𝑛).

0.7

0.7

0.6

0.6

0.5

0.5

Qratio0.4

0.4incident

0.3
00:00 03:00 06:00 09:00 12:00 15:00 18:00 21:00
01-Aug0.3
00:00 03:00 06:00 09:00 12:00 15:00 18:00 21:00
01-Aug

(a)

(b)

Time

Time

Figure 3: Effect of cluster level correlation on invariance. (a)high correlation (0.87). (b) low data correlation (0.35)
An important thing to note is that every incident is unique inits manifestation and the method has to generalize for various
clusters. Hence, we need to learn the underlying general structureof the ratio time series. However, the training data collected fromthe wild have incidents, and the data collected from connectedtransportation is very noisy due to human behavioral randomness.
This is unlike traditional industrial CPS where the data patterns
are only governed by tightly modeled laws of physics. Hence, wecannot simply learn the ratio samples themselves.

4.4

Data Pre-processing and Augmentation

Real-world mobility data collected from the wild (not from theexperimental testbed), pose a practical problem for unsupervised
learning problems such as anomaly detection, due to the presence ofvarious incidents in the training phase. This prevents the learningof the underlying structure of benign data patterns. We need amechanism to bypass this problem which we discuss here.

𝑐𝑘

0.8

0.008

0.6

0.006

0.4

0.004
0.002
0.000

incident training
replacement

Ground Truth Incident

Q-ratio

𝐻𝑀𝑐𝑘 (𝑡)𝑄𝑐𝑘 (𝑡) =(6)
𝐴𝑀𝑐𝑘 (𝑡)To illustrate the importance of the approximation algorithm
for clustering to maximize positive correlation strategically, we
compare the plots of time series of the ratio samples for the sametime frame of the same day in Fig. 3 for the same area. Fig. 3a is acluster with high data correlation (0.87) and Fig. 3b is a cluster withlow data correlation (0.37). Observe that the time series of ratio
samples in Fig. 3a is highly stable under benign traffic conditions(stationarity and low variance) and shows a sharp deviation on theincident that happened at 13:00 hrs. In contrast, Fig. 3b that did not
maximize correlation has poor stability and does not show clear
deviation in its time series when the incident happens.

1.0

0.010
Probability

time window 𝑡. Consequently, the ratio sample of the cluster 𝑐𝑘 at
any time window 𝑡 is calculate by the following:

Region A

Region B

19:00

20:00

0.2

−100

−50

0

50

Duration from GT(t)
(a)

100

0.0

Time

21:00

22:00

(b)

Figure 4: (a) Distribution of Temporal Neighborhood of Disturbances across all incidents (b) Data Augmentation
The intuition is to use the time and location stamp of the groundtruth incidents and superimpose them on the ratio time series of
the cluster which falls under the location of a particular incident.
Then we identify the neighborhood of the time series of 𝑄𝑐𝑘 (𝑡)Anomaly based Incident Detection in Large Scale Smart Transportation Systems

ICCPS ’22, May 4–6, 2022, Milan, Italyaround all incidents to learn the portions of the time series thatwere disturbed. Unless these disturbances are cleaned out, it will
prevent learning the structure of the benign behavior.
Note, ground truth incident recording itself is noisy due tohuman-in-the-loop issues. We observed in many cases, they arerecorded much after the physical world has been affected by theincident. In other cases, the incident is reported and recorded instantly but it takes some time for the physical world to get reallyaffected (e.g. in sparse traffic scenarios).
Temporal Disturbance Period Selection: We know that prominent incidents in the city cause large congestion that gets captured
in the congestion factor metric available with the dataset. Additionally, the moving average of the invariant decreases near incidents.
We utilize the decrease to differentiate between benign and noisy
ratios (invariant) which are then used to select a neighborhood
around the incident ground truth timestamp 𝐺𝑇 (𝑡). This can bevisualized through Fig. 4b where region 𝐵 is such a neighborhood.
From the time stamp where the incident was recorded (minutes=0), we check how many incidents showed a low moving average of ratio samples for a window before and after (minutes=0).
One can find 𝑎𝑟 % of the incidents create a decrease in the ratio
time series for less than Minutes =±𝑦 minutes. Hence, the temporal neighborhood of ratio time series sample around the 𝐺 (𝑡)timestamp that needs to be cleaned and discarded is on averagey minutes before and after the 𝐺𝑇 (𝑡) shown in Fig. 4a. In Fig. 4b,
this region is marked as region B. In Fig. 4b, we showed region
markings assuming, 𝑎𝑟 = 60%, the 𝑦 is around 30 minutes before
and after any corresponding ground truth time stamps. Similarly,
any confidence interval can be used for cleaning.
Ratio Sample Cleaning and Augmentation: To clean the incident neighborhood, we discard the ratios of region B from thetraining examples of ratio samples and replace them with the cumulative moving average (CMA) of an equal length of time just before
the start of region B (temporal disturbance window of a cluster).
As an illustration, the cumulative sliding moving average of theratio samples from region A are copied into the discarded ratio
samples from region B, as demonstrated by Fig. 4b. The CMA for
any cluster 𝑐𝑘 at time 𝑡, is calculated by the following:𝑄𝑐𝑀𝐴(𝑡 ) =
𝑘(𝑡 − 1)𝑄𝑐𝑀𝐴(𝑡 − 1) + 𝑄𝑐𝑘 (𝑡 )𝑘denoted as Γ𝑐𝑘 (𝑡) and the lower boundary is denoted as Γ𝑐𝑙𝑜𝑤(𝑡).
𝑘
The boundaries are termed as safe margins which can be calculatedusing the following equations:
ℎ𝑖𝑔ℎ

Γ𝑐𝑘

ℎ𝑖𝑔ℎ

After cleaning effects of ground truth recorded incidents, there
are other behavioral randomness and noise that make lowering
false alarms challenging without sacrificing the detection accuracy.
Therefore, a two-tier approach (NIST recommended [5]) to learning
the thresholds and an appropriate anomaly detection criterion isessential. The two-tier principal mandates short-term and longterm errors of any underlying detection metric. We adapt this idea
in our context in the following manner:

(8)

Γ𝑐𝑙𝑜𝑤
(𝑡 ) = 𝑄𝑐𝑀𝑒𝑎𝑛(𝑡 ) − 𝜅𝜎 𝑐𝑘
𝑘
𝑘

(9)


ℎ𝑖𝑔ℎ


 = 𝑄𝑐𝑘 (𝑡 ) − Γ𝑐𝑘 (𝑡 ),𝑙𝑜𝑤∇𝑐𝑘 (𝑡 ) := 𝑄𝑐𝑘 (𝑡 ) − Γ𝑐𝑘 (𝑡 ), = 0,
ℎ𝑖𝑔ℎif 𝑄𝑐𝑘 (𝑡 ) > Γ𝑐𝑘 (𝑇 ); 



𝑙𝑜𝑤
if 𝑄𝑐𝑘 (𝑡 ) < Γ𝑐𝑘 (𝑡 );otherwise;

(10)

Residual Under Curve A non-zero residual indicates the possible
presence of an anomaly. However, to confirm, a sum of residuals is
calculated over a fix optimal time window size which can be called
as sliding frame size. The summation is termed as the residuals
under curve. It is calculated using the equation below.

(7)

Detection Framework Design(𝑡 ) = 𝑄𝑐𝑀𝑒𝑎𝑛(𝑡 ) + 𝜅𝜎 𝑐𝑘
𝑘4.5.2 Second Tier Stateful Residuals. The second tier consists of
two thresholds. These thresholds are termed as standard limits in[1]. The upper side standard limit is 𝜏𝑐𝑚𝑖𝑛
(ℎ) and the lower side𝑘standard limit is 𝜏𝑐𝑚𝑎𝑥
(ℎ).
Setting
up
these
two
thresholds is not as𝑘straightforward as tier 1. To calculate the thresholds, the first stepis to get the residuals ∇𝑐𝑘 (𝑡) of each time window using the safe
margin. This residual will be used to again calculate the residual
under curve 𝑅𝑈𝐶𝑐𝑘 (𝑡) over a sliding frame of size 𝑆𝐹 for each time
window and the sub-region. Finally the 𝑅𝑈𝐶𝑐𝑘 (𝑡)’s are used tolearn the standard limits by the given algorithm 2
Residual is defined as the difference between the safe marginℎ𝑖𝑔ℎand the ratio. If a ratio is higher than Γ𝑐𝑘 (𝑡), the residual will
be positive and if a ratio is less than Γ𝑐𝑙𝑜𝑤(𝑡), the residual will be𝑘negative. The following equation calculates the residual:

𝑅𝑈 𝐶𝑐𝑘 (𝑡 ) =𝑡This process is executed for all ratio sample neighborhoods ofground truth incidents found in all clusters during the training
phase. The CMA of region A is then used to replace the signaturein region B. Figure 4b shows the incident signature being replacedby the cleaned data. This allows the model to learn the underlying
structure of the data without incidents.

4.5

4.5.1 First Tier Stateless Residuals. The first tier uses the timeseries distribution of the ratios 𝑄𝑐𝑘 to set up a varying thresholdthat follows the ratio distribution for each cluster 𝑐𝑘 where 𝑘 ∈{1, · · · , 𝐾 }. A particular ratio 𝑄𝑐𝑘 (𝑡) can be greater than or lessthan the mean ratio 𝑄𝑐𝑀𝑒𝑎𝑛(𝑡). The acceptable margin creates the𝑘upper and lower side boundary using the mean ratio of a cluster
𝑄𝑐𝑀𝑒𝑎𝑛(𝑡) and the standard deviation 𝜎 𝑐𝑘 . The upper boundary is𝑘𝑡Õ∇𝑐𝑘 (𝑘)(11)

𝑗 =𝑡 −𝐹 𝑆

Algorithm 2: Calculate 𝜏𝑐𝑚𝑎𝑥
(ℎ)
𝑘
1
2

for 𝑐𝑘 , 𝑡, 𝜏 do
if (𝑅𝑈𝐶𝑐𝑘 (𝑡) < 𝜏 then
|𝜏−𝑅𝑈 𝐶𝑐 (𝑡 ) |34𝑘𝑐𝑐𝑚𝑎𝑥 :
2
CC ← 𝑐𝑐𝑚𝑎𝑥

else
𝑝𝑝𝑚𝑎𝑥 = |𝑅𝑈𝐶𝑐𝑘 (𝑡) − 𝜏 |2
7
PP ← 𝑝𝑝𝑚𝑎𝑥Í𝑚𝑎𝑥 (ℎ) = 1 argmin Í
8 𝜏𝑐
𝜏
𝜂+
𝑘
CC 𝑐𝑐𝑚𝑎𝑥 − PP 𝑝𝑝𝑚𝑎𝑥
5

6

Learning Standard Limit The computed 𝑅𝑈𝐶𝑐𝑘 is later used
to learn the standard limit using Algo. 2. The algorithm treats theinterior and exterior RUC in a different manner by multiplying

ICCPS ’22, May 4–6, 2022, Milan, Italy

Md. J. Islam and J.P. Talusan, et al.

two different weights. An interior-point contributes less to theoverall loss and an exterior point contributes more. The algorithm
minimizes the difference between the loss of interior and exterior
points to learn the optimal standard limit both for the higher andlower sides. Eventually, both of the learned thresholds use the samealgorithm, here we have shown only for the 𝜏𝑐𝑚𝑎𝑥
(ℎ). For 𝜏𝑐𝑚𝑖𝑛
(ℎ)
𝑘𝑘
only the negative 𝑅𝑈𝐶𝑐𝑘 (−) are used whereas for 𝜏𝑐𝑚𝑎𝑥
only the𝑘positive 𝑅𝑈 𝐶𝑐𝑘 (+) are used.
4.5.3 Anomaly Detection Criterion. Similarly, the RUC can becalculated at every time window in the test set. Let 𝑅𝑈𝐶𝑐𝑘 (𝑇 𝑐 ) is
the RUC value for the cluster 𝑐𝑘 in the test set at the current time
window 𝑇 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 . Then, the incident detection criterion is given∈ [𝜏𝑐𝑚𝑖𝑛(ℎ), 𝜏𝑐𝑚𝑎𝑥
(ℎ)] No Incident;𝑘𝑘
𝑅𝑈 𝐶𝑐𝑘 (𝑇 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 ) :𝑚𝑖𝑛∉ [𝜏𝑐𝑘 (ℎ), 𝜏𝑐𝑚𝑎𝑥
(ℎ)],
Incident Inferred;
𝑘
(12)
0.10

0.00

−0.05

−0.15

τmax
τmin

08:00

0.102
0.100

0.6

Ground Truth Incidents

06:00

0.104

Missed Detection Rate
False Positive Rate

0.8

ResidualHyperparameter Learning

10:00

12:00

14:00

Time

16:00

18:00

0.098

Percent

−0.10

4.6

There are four different types of hyperparameters. First set of hyperparameters is 𝑝𝑐𝑢𝑡 and 𝑝 (𝑚𝑖𝑛) which affect the clustering process
and the distribution of ratios. Second parameter set includes 𝜅 and𝑆𝐹 values which affect the standard limits. For every combination of𝜅 and 𝑆𝐹 the same ratio distribution will produce different standard
limits. Here, we will discuss how the hyperparameters are learnt.
To learn the 𝑝𝑐𝑢𝑡 , we measure the deviation in invariance (ratios)
𝑄 𝑀𝐴𝐷 for different margin of 𝑝𝑐𝑢𝑡 . The 𝑄 𝑀𝐴𝐷 is used to selectthe 𝑝𝑐𝑢𝑡 value since it directly affects the level of invariance in theratiometric. Since the lowest median absolute deviation in the series
imply the most stability, it implies that the smallest 𝑝𝑐𝑢𝑡 for which
the minimum value of 𝑄 𝑀𝐴𝐷 stops decreasing across consecutive
values of candidate 𝑝𝑐𝑢𝑡 is desirable. The smallest value is useful of
𝑝𝑐𝑢𝑡 is recommended since too much positive correlation reduces
the sensitivity to smaller incidents. It is shown in Fig. 7b.

MAD Value

RUC

0.05

values within the identified clusters over time 𝜉 (𝑇 ) are not varying
too much, which is required for ratio stability.

20:00

0.4

0.096
0.094

0.2

Average difference between speeds (mph)Figure 5: Detection Illustration: RUC of 𝑖 𝑡ℎ cluster.
Fig. 5 illustrates the incident detection where the vertical lines
are the ground truth incidents and the horizontal lines represent
the standard limits. we can see that RUC(T) metric goes beyond thelearned standard limit near the growth truth time stamps.

10

(a)

i th cluster

8
6
4
2
0
06:00

08:00

10:00

12:00

14:00

Time

16:00

18:00

20:00

(b)

Figure 6: (a) Propagation of Initial Incident. (b) Average Difference in Speeds.
Why ratios and RUC deviate? As and when an accident occurs within a subarea of a city, the immediate neighborhood of thelocation where the accident happened, experiences a decrease in vehicle speeds instantly. However, this reduction in speed takes timeto propagate beyond this immediate neighborhood until it affects
the whole cluster. In Fig. 6a an accident occurred at time 𝑡 inside acluster 𝑐, the reduction in speed in the immediate neighborhood(red circle) takes time (𝑡 + 𝑛) to propagate outwards. The shaded
region has decreasing speeds compared to the unshaded region
that does not decrease creating a drop in correlation. This delay
in propagation causes the deviation in the signature and can bedetected by the metric as an anomaly. Fig. 6b, is an illustration thatshows that the average difference between any two pair of TMC

0.0

0.092
0.090

0.25

0.5

0.75

1.0 1.25
Kappa

1.5

1.75

2.0

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

(a)

pcut

(b)

Figure 7: (a) Effect of varying 𝜅 on the detection performanceof a given cluster. (b) MAD over 𝑝𝑐𝑢𝑡 for 𝑘 𝑡ℎ cluster.
As we increase 𝑝𝑐𝑢𝑡 from 0.0 to 0.99, the mean absolute deviationof the ratios in a cluster decreases. This trend continues until acertain point where the deviation stabilizes. Accounting this, wesettle on 𝑝𝑐𝑢𝑡 = 0.7 as a lower bound. The hyper-parameter 𝑝 (𝑚𝑖𝑛)controls the area coverage and the performance of the cluster-wise
incident detection. We learn it by the following:arg max (𝐶𝑜𝑣𝑅 + 𝑇 𝑃𝑅 − 𝐹 𝑃𝑅)
𝑝 (𝑚𝑖𝑛)(13)

where 𝐶𝑜𝑣𝑅 is the coverage rate of road segments while clustering,
𝑇 𝑃𝑅 true positive rate of detection, 𝐹 𝑃𝑅 are the false positive rate,
for incident detection. The above equation ensures the maximization of performance by reducing the false positives at the same timeand increasing the coverage percentage. The approximate solution
cover a majority of the area which had a total of 6,928 road segments. As we increase the correlation threshold, 𝑝 (𝑚𝑖𝑛) , the radius
becomes smaller with fewer segments being included in each cluster. However, as a result, there are now more clusters generated,
resulting a larger coverage of the target area. The performance fordifferent values for 𝑝 (𝑚𝑖𝑛) are given in Table 2.
For the incident detection model we learn the optimal value forthe hyper parameters 𝜅 and 𝑆𝐹 . The parameter 𝜅 is a value in (0, 3)
and 𝑆𝐹 is a sliding frame size which varies among the integer values
in the set {3, 5, 7, 9} . The optimal values of 𝜅 and 𝑆𝐹 are learnt byarg min
𝜅,𝑆𝐹(𝑀𝐷𝑅 + 𝐹 𝑃𝑅)(14)

Anomaly based Incident Detection in Large Scale Smart Transportation Systems

Cluster Info

0.75

0.85

0.95

count
mean
min
max
ave. data correlation
ave. radius (m)area coverage

317
16.06
4
161
0.863
611.11
73%

354
14.54
4
132
0.862
610.07
74%

472
11.81
4
112
0.867
490.0380%

True Positive Rate
False Positive Rate

0.916092
0.010727

0.924653
0.032051

0.926340
0.030957

where 𝑀𝐷𝑅 is the missed detection rate and 𝐹 𝑃𝑅 is the false positive
rate. The 𝜅 and 𝑆𝐹 from the above equation are selected as the
optimal hyperparameters for the considered cluster.Each cluster 𝑐𝑘
has its own optimal selection of 𝜅 and 𝑆𝐹 . Figure 7a shows the effectof the hyperparameter 𝜅 on the detection performance of the 𝑘 𝑡ℎcluster. A detection model with large 𝜅 reduces the total number offalse alarms however, it increases the number of missed incidents
detected. The equation above ensures an acceptable performance.

5

EXPERIMENTAL EVALUATIONIn this section, we introduce the dataset and the performance of ourframework in terms of metrics such as incident detection rate, false
alarm rate, time to detection of incidents, the impact of undetected
incidents on the CPS application.

5.1

Details of Dataset

To evaluate our framework, we use one year (2019) long traffic datacollected from the city of Nashville, Tennessee by road side sensors
at five-minute intervals. This dataset is bigger in duration and interms of coverage area compared to validation used in existing
works [7, 14]. For ground truth incidents, we use another dataset
collected from Nashville’s Fire and Emergency Response Department during the same year. In all phases of the experiment, we only
consider weekdays of 2019, focusing on the period between 6:00
AM to 9:00 PM since during night hours and weekend hours the
traffic has discrete patterns. Details are shown in Table 3.
Table 3: Detail of datasets

are clustered following the clustering process discussed in Sect. 4.2.
To cluster, the road segments from the transformed graph problem
where correlation 𝑝𝑒 is assigned as the weights for each edges 𝑒in the graph. We consider a cutoff correlation value 𝑝𝑐𝑢𝑡 and aminimum level of correlation 𝑝𝑚𝑖𝑛 which leads to more invariance.
The clustering generated 354 clusters. However, we found thatmost incidents in the ground truth dataset were restricted to fewer
clusters that correspond to the busiest parts of the city. Hence,
we selected 25 clusters with the most reported incidents from theground truth dataset and used it to evaluate the performance ofincident detection. For the temporal disturbance due to the groundtruth incidents, the 𝑎𝑟 = 60% was used from the distribution ofduration from 𝐺𝑇 (𝑡) variable. This corresponds to 𝑦 = ±30 minutes
around the neighborhood from all 𝐺𝑇 (𝑡). Since 𝑡 is slotted every 5
minutes, it boils down to 12 ratio samples augmented per incident.
5.1.2 Details of Testing dataset. In this section, we evaluate ourdecentralized implementation of a lightweight anomaly detection
framework. We used two months (Nov. and Dec.) from the dataset
for testing. In these two months, there were a total of 851 incidents
recorded in 580 active segments. We present how our techniquegives us the ability to detect these incidents which can lead towards
valuable actionable information.

5.2

Performance Results

In this section, we show sensitivity analysis of our performance
to changing hyperparameters instead of learnt hyperparameters.
Then, we report performance of the optimal learnt model withhyperparameters using the fitness function described in Section 4.6.
5.2.1 Sensitivity Analysis of Performance. Here we give the sensitivity analysis of performance where the 𝑘𝑎𝑝𝑝𝑎 is not learned
but varied as a free parameter to check its effect on the changing
performance. The performance metrics include time to detection,true positive rate, false-positive rate, expected time between false
alarms, and impact of undetected incidents.
0.9
0.8
0.7

Data Sources

Properties

ValuesRoad network# intersections# streets

6928
19493

Traffic incidents
Sensors# instances# count

8116
6928

Data collection period

01/01/2019 - 12/31/2019

Experimental Setup: The twelve months of data is divided
across training, cross-validation, and testing sets. The training
phase learns the model for a combination of hyperparameters The
cross-validation set is used to find the best hyperparameters thatgive the best outcome. The best hyperparameters are fitted to themodel to find the final learned model that is used for testing.
The first eight months (Jan. to Aug.) are used for training. The
next two months, (Sept. and Oct.), used for cross-validation. The
final two months (Nov. and Dec.) are used to test the model itself.
5.1.1 Training Dataset Details. For training, we focus on the geographic coverage area Southwest(−87.050630, 35.989510) and Northeast (−86.527560, 36.416830). Then, the segments inside the area

0.6
0.5
0.4

ROC

0.3
0.005 0.010 0.015 0.020 0.025 0.030

False Positive Rate(a)Time between false alarms (minutes)

𝑝 (𝑚𝑖𝑛)True Positive Rate

Table 2: Cluster Information

ICCPS ’22, May 4–6, 2022, Milan, Italy

500
400
300
200
100
0

0.25

0.5

0.75

1.0

1.25

Kappa

1.5

1.75

2.0

(b)

Figure 8: (a) Average ROC curve for 25 clusters (b) Mean time
between false positives based on different 𝜅 for 𝑐𝑘 .
Detection Rate and False Alarms Fig. 8a shows the average ROC
curve across the 25 clusters, underscoring the performance of ourframework. One can see that at 90% true positive detection rate, thefalse alarm/false positive rate (FPR) is only 0.030. The low FPR is asignificant achievement because: (1) anomaly detection methods areprone to false alarms (2) due to lower rates of emergency/incidents,
the cost of FPR is usually high for any CPS. Each cluster has 16,560
detection attempts and the false positives are few. Fig. 8b shows
the rarity of these false positives even when using 𝜅 = 0.25 which
has the best overall detection rate. Specifically, Fig. 8b gives an ideaon the expected time between two false alarms for various 𝜅.

ICCPS ’22, May 4–6, 2022, Milan, Italy

Md. J. Islam and J.P. Talusan, et al.

Mean Time to Detection A key performance indicator of usability in a CPS application is time to detection. Fig. 9a shows that 78%
incidents were detected in the first 5 minutes and 90% incidents
were detected within 30 minutes. Quick time to detection is essential to warn commuters earlier and control the flow of traffic toprevent congestion spread.
1.0

CDF

Minutes saved per year

REFERENCES

4000

CDF

0.6

3000

0.4

2000

0.2

1000

10

20

30

40

50

60

Time to Detection of Incidents (minutes)

0
0.25

0.5

(a)

0.75

1.0

1.25

Kappa (κ)

1.5

1.75

2.0

(b)

Figure 9: (a) Time to Detection of Incidents (b) Impact onroute travel times under different 𝜅
Impacts of Undetected Incidents By successfully detecting an incident, a traffic congestion will be prevented or mitigated and thecommuters will be diverted to different routes, avoiding travel delays. We generated 200 routes that pass through segments withincidents and computed the travel time of each route with incidents.
Using the true positive rates, we calculated what percentage of incidents will be detected. Detected incidents allow the system tonotify commuters early and thus will experience less delay in theirtravel times. The time saved per vehicle is given by the following:△ 𝑡 = 𝑅𝐷 (

1
1
−
)
𝐼𝑆 𝐹𝑆

(15)

where 𝑅𝐷 is the total distance in a given route, 𝐼𝑆 is the speed due
to incidents and 𝐹𝑆 is the free-flow speed which is experienced
when affected areas are avoided. Assuming on average that 10,000
vehicles pass by any segment per year, we can identify the impact of
our anomaly detector on the travel time saved over a year. Figure 9b
show the amount of travel time saved on a macro level dependingon the hyperparameter and granularity used respectively.
5.2.2 Overall Performance with Learnt Hyperparameter. We applied the learnt values of 𝜅, 𝑆𝐹 , 𝑝𝑐𝑢𝑡 and 𝑝𝑚𝑖𝑛 for each of the 25
clusters. The final performance is an average from all 25 clusters for
all traffic incidents over the full 2 months. Doing this, we found theaverage true positive detection rate 𝑇 𝑃𝑅 = 0.90 and 𝐹 𝑃𝑅 = 0.03.

6

Acknowledgements This research was supported by National
Science Foundation, USA grants, SATC-2030611, CNS-1818942,CNS1818901, SATC-2030624, OAC-2017289. We thank the Tennessee
department of transportation and Nashville fire department forhelp in obtaining the relevant data for this research.

5000

0.8

0.0

to be deployed in a decentralized manner while maintaining highperformance anomaly detection in a real-time manner.

CONCLUSION

We proposed an unsupervised time series-based anomaly detection framework for city-scale smart transportation CPS. We discuss
how an existing anomaly detection metric (Harmonic to Arithmetic
Mean ratios) can be applied to a transportation problem, by using astrategic partitioning of city area into positively correlated clusters
that guarantee high invariance in detection metric. We utilize a data
augmentation technique to enable unsupervised learning of theanomaly detection technique and learn the bounds of the techniqueunder the sanitized, normal traffic conditions to establish anomaly
detection criteria. Results show that our proposed unsupervised
anomaly detection framework allows strategic partitions to independently generate, sanitize, learn and detect anomalies with highaccuracy and low false-positive rates. This enables our approach[1] Shameek Bhattacharjee and Sajal K. Das. 2021. Detection and Forensics against
Stealthy Data Falsification in Smart Metering Infrastructure. IEEE Transactions
on Dependable and Secure Computing 18, 1 (2021), 356–371. https://doi.org/10.
1109/TDSC.2018.2889729[2] Shameek Bhattacharjee, Venkata Praveen Kumar Madhavarapu, Simone Silvestri,and Sajal K. Das. 2021. Attack Context Embedded Data Driven Trust Diagnostics
in Smart Metering Infrastructure. ACM Trans. Priv. Secur. 24, 2, Article 9 (Jan.
2021), 36 pages. https://doi.org/10.1145/3426739[3] Erik D. Demaine, Dotan Emanuel, Amos Fiat, and Nicole Immorlica. 2006. Correlation clustering in general weighted graphs. Theoretical Computer Science 361, 2(2006), 172–187. https://doi.org/10.1016/j.tcs.2006.05.008 Approximation and
Online Algorithms.
[4] Keval Doshi and Yasin Yilmaz. 2021. An Efficient Approach for Anomaly Detection in Traffic Videos. arXiv preprint arXiv:2104.09758 (2021).
[5] David I. Urbina Jairo Giraldo Alvaro A. Cardenas Junia Valente Mustafa Faisal.
2016. Survey and New Directions for Physics-Based Attack Detection in Control
Systems. NIST NIST GCR 16-010 (2016).
[6] Yaser E. Hawas. 2007. A fuzzy-based system for incident detection in urban street
networks. Transportation Research Part C: Emerging Technologies 15, 2 (2007),
69–95. https://doi.org/10.1016/j.trc.2007.02.001[7] Yue Hu and Daniel B. Work. 2021. Robust Tensor Recovery with Fiber Outliers
for Traffic Events. ACM Trans. Knowl. Discov. Data 15, 1, Article 6 (Dec. 2021),
27 pages. https://doi.org/10.1145/3417337[8] Zafar Iqbal and Majid Iqbal Khan. 2018. Automatic incident detection in smart
city using multiple traffic flow parameters via V2X communication. International
Journal of Distributed Sensor Networks 14, 11 (2018), 1550147718815845. https://doi.org/10.1177/1550147718815845[9] S.J. Julier and J.K. Uhlmann. 2004. Unscented filtering and nonlinear estimation.
Proc. IEEE 92, 3 (2004), 401–422. https://doi.org/10.1109/JPROC.2003.823141[10] Akira Kinoshita, Atsuhiro Takasu, and Jun Adachi. 2015. Real-time traffic incident
detection using a probabilistic topic model. Information Systems 54 (2015), 169–
188. https://doi.org/10.1016/j.is.2015.07.002[11] Ayan Mukhopadhyay, Geoffrey Pettet, Sayyed Mohsen Vazirizade, Di Lu, Alejandro Jaimes, Said El Said, Hiba Baroud, Yevgeniy Vorobeychik, Mykel Kochenderfer,
and Abhishek Dubey. 2022. A Review of Incident Prediction, Resource Allocation,
and Dispatch Models for Emergency Management. Accident Analysis & Prevention
165 (2022), 106501. https://doi.org/10.1016/j.aap.2021.106501[12] Murat Ozbayoglu, Gokhan Kucukayan, and Erdogan Dogdu. 2016. A real-time
autonomous highway accident detection model based on big data processing andcomputational intelligence. In 2016 IEEE International Conference on Big Data
(Big Data). 1807–1813. https://doi.org/10.1109/BigData.2016.7840798[13] Yasas Senarath, Ayan Mukhopadhyay, Sayyed Vazirizade, hemant Purohit,
Saideep Nannapaneni, and Abhishek Dubey. 2021. Practitioner-Centric Approach for Early Incident Detection Using Crowdsourced Data for Emergency
Services. In 21st IEEE International Conference on Data Mining (ICDM 2021).
[14] Yasas Senarath, Saideep Nannapaneni, Hemant Purohit, and Abhishek Dubey.
2020. Emergency Incident Detection from Crowdsourced Waze Data using
Bayesian Information Fusion. In 2020 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT). 187–194.
https://doi.org/10.1109/WIIAT50758.2020.00029[15] Siemens. 2018.
Connected Vehicle Roadside Unit (RSU).
Brochure.
https://www.mobotrex.com/download/download-datasheet-for-siemensconnected-vehicle-roadside-unit-rsu/[16] Hong Yang, Zhenyu Wang, Kun Xie, and Dong Dai. 2017. Use of ubiquitousprobe vehicle data for identifying secondary crashes. Transportation ResearchPart C: Emerging Technologies 82 (2017), 138–160. https://doi.org/10.1016/j.trc.
2017.06.016[17] Kun Zhang and Michael A.P. Taylor. 2006. Effective arterial road incident detection: A Bayesian network based algorithm. Transportation Research Part C: Emerging Technologies 14, 6 (2006), 403–417. https://doi.org/10.1016/j.trc.2006.11.001[18] Lin Zhu, Rajesh Krishnan, Aruna Sivakumar, Fangce Guo, and John W. Polak. 2019.
Traffic Monitoring and Anomaly Detection based on Simulation of Luxembourg
Road Network. In 2019 IEEE Intelligent Transportation Systems Conference (ITSC).
382–387. https://doi.org/10.1109/ITSC.2019.8917015