Traffic Incident Detection Using Probabilistic Topic Model. Akira Kinoshita 1 , Atsuhiro Takasu 2 , and Jun Adachi 2 < firstname.lastname@example.org > 1 The University of Tokyo 2 National Institute of Informatics, Japan International Workshop on Mining Urban Data Athens, Greece, March 28, 2014. - PowerPoint PPT Presentation
Traffic Incident DetectionUsingProbabilistic Topic ModelAkira Kinoshita1, Atsuhiro Takasu2, and Jun Adachi2
1The University of Tokyo2National Institute of Informatics, Japan
International Workshop on Mining Urban DataAthens, Greece, March 28, 2014Thank you. Good morning everyone.Im a masters student at the University of Tokyo, and Im glad to tell you about some of our recent work in this workshop.AbstractDetect traffic incidents by comparing current traffic with usual traffic with less knowledge of traffic engineering.Show the method works well on the Shuto Expressway in Tokyo, using real probe-car dataPossible by-product: characteristic analysis of road2014-03-282Kinoshita, A. Takasu, and J. Adachi.Traffic Incident Detection Using Probabilistic Topic ModelIn this presentation, I will introduce our method to detect traffic incidents by comparing between usual and current traffic with less knowledge on traffic engineering.I will show the method discriminates anomalous cars better than an existing method on the Shuto Expressway in Tokyo, Japan, using real probe-car data.In addition, I will discuss a possible by-product of our method at the end of this presentation.
Now, let me talk about the background.Background2014-03-283Kinoshita, A. Takasu, and J. Adachi.Traffic Incident Detection Using Probabilistic Topic Model
Causes of congestionin Japan [E-NEXCO]http://www.e-nexco.co.jp/english/business_activities/expressway_management/eliminating.htmlProbe-car data(position+timestamp)CongestionIncident
Today, some cars in road traffic are working as probe cars, which send their position information with timestamps.This picture shows a car running through the Shuto Expressway in Tokyo from Higashi-Ikebukuro toward the central Tokyo.Color of marker indicates speed of the car. Blue is almost stop.
We can see that this car suddenly slowed down at Gokokuji interchange.We can guess that the car was involved in a traffic congestion.Congestion is easily detected if we have enough probe-car data, and this information is very useful for drivers.
Also, traffic incident detection is a crucial technology in intelligent transport systems.Incidents, such as accident and fallen objects, cause congestion, and therefore incidents should be detected in real time to be solved immediately.However, it is not always true that congestion is caused by an incident.
Actually, there was NOT any incidents in this picture.
This pie chart shows the ratio of causes of congestion in Japan.You can see that the most of congestion is caused by traffic concentration.
Incidents cause congestion, but congestion is not always caused by incidents.
Related Work2014-03-284Kinoshita, A. Takasu, and J. Adachi.Traffic Incident Detection Using Probabilistic Topic Model[Zhu, et al. 2009]TimeLinkslowdown@incidentDateslowslowfastFeature vectorbased on the speed change
Distance-basedoutlier detectionafter filterling+
However, existing work exploit the characteristic of traffic flow at the point of incident.This picture illustrates Zhus method, which is based on spatio-temporal analysis of traffic flow.For temporal analysis, once an incident occurs, vehicular speed decreases there.For spatial analysis, cars travel slowly on links upstream of the incident, while they run fast downstream.Zhus feature vector is consisted of four speed values, and
filtered out if it is obviously not an anomaly.Then distance-based outlier detection is conducted. Outlier means an occurrence of an incident.However, this behavior can be seen at bottlenecks, junctions for example, and this method may misdetect spontaneous congestion which is caused by traffic concentration.Research Problem& Solution StrategyProblemCongestion is not always caused by traffic incidents speed reduction often occurs without any incidentsReal-time data stream processing
Solution strategyRegard incident as sudden event different from usualEstimate traffic state using probe-car data (or else)Compare current traffic with usual traffic current traffic should be much different from usual2014-03-285Kinoshita, A. Takasu, and J. Adachi.Traffic Incident Detection Using Probabilistic Topic ModelAlthough congestion can be easily detected, it is difficult to distinguish anomalous congestion from spontaneous congestion.Especially, in Japan or on local streets, speed reduction often occurs without any incidents.In addition, real-time data stream processing is quite important issue in the field of data engineering.To solve the problem, we take an data-engineering approach instead of traffic-engineering approach.In this work, incident is considered as sudden event different from usual.To detect incidents, we estimate traffic state using traffic data such as probe-car data, and then compare the current traffic with the usual traffic.If the current state is much different from usual, our method will give an alert of incident occurrence.OutlineBackgroundAutomatic incident detectionRelated work & research problemMethodologyTraffic state model based on topic modelEstimate usual/current traffic states and then compare themExperimentUsing probe-car data on three routes of the Shuto Expressway in Tokyo during 2011DiscussionResults of the experimentPossible analysis using traffic state model2014-03-286Kinoshita, A. Takasu, and J. Adachi.Traffic Incident Detection Using Probabilistic Topic ModelNow, I will instruct our method to detect traffic incidents.I will first introduce traffic state model, and I will explain how to learn it using traffic data such as probe-car data.Then, using the model, usual and current traffic states are estimated and compared to detect incidents.Traffic State Model (TSM) Similar to LDA [Blei 2003]Distribution of is mixture distribution2014-03-287Kinoshita, A. Takasu, and J. Adachi.Traffic Incident Detection Using Probabilistic Topic ModelInbound expressway,midnightInbound artery,weekday morning
Here is the concept of our traffic state model.First, we introduce K traffic states, such as good and congested, that influence cars in the traffic.If a traffic is in congested state now, cars behavior should be stop-and-go, and thereby an observation value x is generated by a probe-car.For example, when cars observe their vehicular speed, x tends to be large in good state, and be small in congested state, so x follows a state-specific distribution each of which has its own parameter k.In addition, because traffic changes according to the time and the place, I also introduce segment s as a spatio-temporal unit of observation, I mean, a certain road section in a certain time period.Every segment is dominated by traffic states in its own mixture ratio s, which indicates the state tendency there.Now, the distribution of x is mixture distribution like ..
This model is similar to LDA, Latent Dirichlet Allocation, which is the simplest probabilistic topic models.Traffic states and their parameter k are shared over all the segments, but they are mixed with different coefficient s for each segment.We should learn and using observed probe-car data archives, and ...()Parameter EstimationMost-likelihood estimation2014-03-288Kinoshita, A. Takasu, and J. Adachi.Traffic Incident Detection Using Probabilistic Topic Model
it is known that the parameters can be estimated by EM algorithm like this using an archive of observation data.
E step calculates posterior distribution of the state k given data x, and M step updates the model parameters by maximizing the Q function.Most-likelihood estimation of the parameters will be obtained by iterating E and M steps until the likelihood converges.
Incident Detection Method2014-03-289Kinoshita, A. Takasu, and J. Adachi.Traffic Incident Detection Using Probabilistic Topic Model
GMCSGCMCSGGMCSGGGGGGUsualTraffic StateCurrentTraffic StateObservedValue
SegmentG: GoodC: CongestedM: ModerateS: StopIncidentDivergence sum of divs
Divergence betweenusual - current states measure by KL divergenceNow, a route is partitioned into some segments, and we have a learned traffic state model, that can be considered to reflect the traffic over whole observation period.
Therefore, we can estimate usual traffic state as the most probable state for each segment.Usual state may be good in many segments, but if a segment has toll gate or speed trap by police, the usual state can be congested for example.On the other hand, when a car travels along the route and generates data for each segment,
current traffic state is estimated by calculating the most probable state given the value in the segment, using posterior distribution of the model.Then, the current state is compared to the usual state.
The divergence between them is measured by Kullback-Leibler divergence, which is common scale to measure the difference of the model distribution from the true distribution.
Then, the divergences will be summed up throughout N segments, which we call divergence of trajectory,
and if it is more than a predefined threshold, it is discriminated as an incident.OutlineBackgroundAutomatic incident detectionRelated work & research problemMethodologyTraffic state model based on topic modelEstimate usual/current traffic states and then compare themExperimentUsing probe-car data on three routes of the Shuto Expressway in Tokyo during 2011DiscussionResults of the experimentPossible analysis using traffic state model2014-03-2810Kinoshita, A. Takasu, and J. Adachi.Traffic Incident Detection Using Probabilistic Topic ModelSo, lets look the experiment and the result.
ExperimentPurposeTo show the proposed method works more efficiently than an existing method.Data SourcesProbe-car data in the Shuto Expressway (Shutoko) in Tokyo during 2011.Timestamp, position (longitude, latitude),vehicular speed (non-negative integer)Traffic log by the road administrator as the ground truth of incidents.Incident includes the five events:accident, broken-down car, fallen object, construction, looking-aside driving2014-03-2811Kinoshita, A. Takasu, and J. Adachi.Traffic Incident Detection Using Probabilistic Topic ModelI will show that our method works more efficiently than an existing method.In this experiment, we used probe-car data in the Shuto Expressway, which we call Shutoko, in Tokyo during 2011, which included timestamp and cars position.We used vehicular speed as the observation value of traffic.It was represented by non-negative integers.For evaluation, we also used traffic log data which was made available by the road administrator, as the ground truth of incidents.In this data, incident includes these five events.Dataset & Preprocessing2014-03-2812Kinoshita, A. Takasu, and J. Adachi.Traffic Incident Detection Using Probabilistic Topic ModelPreprocessing1. Map matching2. Trajectory identification3. Interpolation4. LabelingParameter assumptionsK = 8N = 10Poisson distribution
Area Map[Shuto Expwy.](5)Ikebukuro(4)Shinjuku(3)ShibuyaCentralTokyoShuto Expwy.Routes(3)Shibuya(4)Shinjuku(5)IkebukuroInboundOut-In-Out-In-Out-Period1 Jan 2011 31 Dec 2011 (365 days)# of carsTotal100,58195,38695,29388,345128,789114,942Anomaly4,2592,4754,3653,8916,0895,603Segment= 50-m length sectionThe experiment was conducted in three routes of Shutoko.Inbound is the direction toward the central Tokyo, and outbound is the opposite.In our dataset, the number of total probe cars per route is about one hundred thousand for one year.The number of anomaly is the number of probe cars which passed by a point of incident, so it is not the unique number of incident.We defined road segments by partitioning each route every 50 meters for estimation at a finer level of granularity.To apply our model to probe-car data, four-phase preprocessing was done.And then, we estimated our traffic state model using this dataset on the assumption that the number of states is eight, and that every non-negative integer observation value is generated by Poisson distribution.Parameter Estimation2014-03-2813Kinoshita, A. Takasu, and J. Adachi.Traffic Incident Detection Using Probabilistic Topic Model
Poisson mixture at a certain segment in the inbound Shibuya routeEstimated Poisson mixture fits the original histogramComponent Poisson multiplied by coefficientThis figure shows the actual histogram of observed speed values in a segment and the estimated Poisson mixture there.
We can see the model distribution was learned to fit the original histogram.This eight dashed lines are component Poisson distributions which are multiplied by its own mixing coefficient.
Incident DetectionResult ROC curveoutbound (best)outbound (worst)2014-03-2814Kinoshita, A. Takasu, and J. Adachi.Traffic Incident Detection Using Probabilistic Topic Model
Baseline: [Zhu, et al. 2009]betterArea Under the CurveProposed: 0.812Baseline: 0.794Next, we will see the result of incident detection experiment.We evaluated the performance of our detector using familiar ROC curve.True positive rate and false positive rate change according to the threshold value of detection.When the threshold is too high, the detector detects nothing, so the both rates are zero.Both rates increase as the threshold decreases, and finally, the detector gives an alert for every input, so the both rates are one.Ideal detector detects all anomalies without any false positives at a certain threshold, so the true positive rate is one, but false positive rate is zero.ROC curve illustrates the performance of the detector, and the nearer to the upper left corner, the better the detectors performance is.Therefore, area under the curve is used for quantitative evaluation, and the larger the area is, the better the performance is.We implemented Zhus method, that I mentioned a while ago, as the baseline method,
and our method gave better performance than the baseline for all the routes of our dataset.The left figure is the best case, and the right one is the worst case.
The Most Anomalous Trajectory2014-03-2815Kinoshita, A. Takasu, and J. Adachi.Traffic Incident Detection Using Probabilistic Topic ModelAccident
Our method calculates divergence for each trajectory, so the divergence can be considered as the degree of anomaly.This figure shows the most anomalous trajectory, I mean the trajectory of the largest divergence, in the outbound Shibuya route in time-space diagram.Detected trajectory is this....The car ran very slowly in this section, and the traffic log said there was actually an accident here at that time.OutlineBackgroundAutomatic incident detectionRelated work & research problemMethodologyTraffic state model based on topic modelEstimate usual/current traffic states and then compare themExperimentUsing probe-car data on three routes of the Shuto Expressway in Tokyo during 2011Discus...