Traffic Incident Detection Using Probabilistic Topic Model

  • Published on
    06-Feb-2016

  • View
    43

  • Download
    0

DESCRIPTION

Traffic Incident Detection Using Probabilistic Topic Model. Akira Kinoshita 1 , Atsuhiro Takasu 2 , and Jun Adachi 2 < kinoshita@nii.ac.jp > 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

Transcript

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

Higashi-IkebukuroGokokujiWasedaLocal slowdownIncident

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

TrafficStatesSegmentObservedValue

TopicWorddocument

CongestedStopModerateGood

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.

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

Toll gate

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

speed [km/h]

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 2011DiscussionResults of the experimentPossible analysis using traffic state model2014-03-2816Kinoshita, A. Takasu, and J. Adachi.Traffic Incident Detection Using Probabilistic Topic ModelNow, I will discuss the proposed method and the results of the experiment.DiscussionFalse PositivesOur definition of incident also matches abnormally fast carsDeeper analysis on alarmed trajectories is neededProposed method can detect anomalies in real timeLearn traffic state model and compute divergence matrix in advanceUse sliding window for each probe carOur approach performed better than an existing method based on physical traffic modelCongestion often occurs without any incidents on Shutoko; there are many bottlenecksFinding difference between current and usual traffic states has an effect on traffic incident detection2014-03-2817Kinoshita, A. Takasu, and J. Adachi.Traffic Incident Detection Using Probabilistic Topic ModelFirst, we regarded incidents as sudden events different from usual, so false positives include unusually fast cars which wasnt involved in any incident.It is surely a kind of outlier, so deeper analysis on alarmed trajectories is needed.

Second, although our method requires a learned traffic state model which can be prepared by batch processing, our detection process can be executed in real time.Divergence calculation will also be done in advance, so using sliding window, the proposed method simply finds the divergence, hold it in a sliding window for every input.

Third, to detect incidents, our method compares the difference between current and usual trafficinstead of building a physical model of traffic flow in case of incidents.Shutoko, or local streets, have many bottlenecks, so speed reduction often occurs without any incidents.Our approach should be one solution to avoid this problem.

Road Characteristic Analysis Based on TSM2014-03-2818Kinoshita, A. Takasu, and J. Adachi.Traffic Incident Detection Using Probabilistic Topic Model

Fastest stateSlowest stateUsually slow sectionNext, I will demonstrate another analysis based on the estimated traffic state model.In this experiment, we used the speed of the probe car, and the traffic state was represented by the Poisson distribution, which was characterized by a single parameter.The parameter is equal to both mean and variance.This stacked area chart shows the estimated mixing coefficients along the outbound Route 3.The top is the ratio of the fastest state, and the bottom is that of the slowest.We can see faster states dominate this section.However, just after passing this junction, slower states begin to dominate.

This result indicates that cars usually run slowly in this bottleneck section.This sort of analysis appears to be utilized for improving roads and traffic systems.ConclusionsTraffic state modelMixing shared states in different ratio for each segmentDetection methodCompare current/usual traffic states find irregular eventsExperimental resultBetter detection performance than existing method using real probe-car data in ShutokoPossible applications of traffic state modelTraffic characteristic analysis2014-03-2819Kinoshita, A. Takasu, and J. Adachi.Traffic Incident Detection Using Probabilistic Topic Model

GMCSGCMCSGGMCSGGGGGGUsualCur.

Now, let me summarize my presentation.Real-time incident detection is a crucial technology because incidents have bad influence such as congestion, but congestion is not always caused by incidents.Our detection approach is to compare between the current traffic and the usual traffic.I first introduced a traffic state model based on probabilistic topic model, and learn it using existing data.Then I proposed an incident detection method which compare the current and usual traffic states.This method can find irregular events in traffic, and we confirmed this method discriminates probe-car data in case of incidents from that in usual behavior using real data in Shuto Expressway in Tokyo.Moreover, there is another possible application of the traffic state model.Mixture coefficient of a segment characterizes the performance of the segment.Some of Future Work(Working Now)(Automatic) Parameter tuningK: the number of traffic statesN: the length of sliding windowProper divergence function selectionMore deep analysis on anomalous trajectories2014-03-2820Kinoshita, A. Takasu, and J. Adachi.Traffic Incident Detection Using Probabilistic Topic ModelThere are a lot of future work, and here is a part of them.First, there is a problem of parameter tuning.Our traffic state model has parameter K, the number of traffic states.N, the length to watch a cars trajectory, is also a parameter required for detection.These values should be set properly.

Second, we should select proper one of divergence functions.

Moreover, more deep analysis on trajectories which is judged as anomaly by our methodis necessary to improve the performance of incident detection.Thank you for listeningTraffic state modelMixing shared states in different ratio for each segmentDetection methodCompare current/usual traffic states find irregular eventsExperimental resultBetter detection performance than existing method using real probe-car data in ShutokoPossible applications of traffic state modelTraffic characteristic analysis2014-03-2821Kinoshita, A. Takasu, and J. Adachi.Traffic Incident Detection Using Probabilistic Topic Model

GMCSGCMCSGGMCSGGGGGGUsualCur.

Thank you for your attention.Divergence DefinitionIn the proceedings (equations (13) and (14))

Another way (reversed)

Notes 2014-03-2822Kinoshita, A. Takasu, and J. Adachi.Traffic Incident Detection Using Probabilistic Topic ModelKL divergence of q from p

Divergence Of usual From currentDivergence Of current From usual

We measure the difference between the usual and current traffic states by KL divergence, which is not symmetric scale.We wrote this equations in our paper, but these equations calculate divergence of the usual state from the current state, which is not natural way.So, in this presentation, I will report the experimental results using the reversed divergence.

Incident DetectionResult ROC curveinbound (best)outbound (worst)2014-03-2823Kinoshita, A. Takasu, and J. Adachi.Traffic Incident Detection Using Probabilistic Topic Model

Baseline: [Zhu, et al. 2009]

betterbetterNext, 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.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 six routes of our dataset.This slide shows the two of six.The Most Anomalous Trajectory2014-03-2824Kinoshita, A. Takasu, and J. Adachi.Traffic Incident Detection Using Probabilistic Topic Model

Accident

speed [km/h]

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 in stop-and-go manner from Ohashi junction to here, and the traffic log said there was actually an accident here at that time.KL Divergence between Poisson DistributionsNot symmetryKL vs. Reversed KLIf , then

From faster state to slower state LARGE divergenceFrom slower state to faster state SMALL divergence2014-03-2825Kinoshita, A. Takasu, and J. Adachi.Traffic Incident Detection Using Probabilistic Topic Model

Although our method requires a learned traffic state model which can be prepared by batch processing, our detection process can be executed in real time.Divergence calculation will also be done in advance, so using sliding window, the proposed method simply finds the divergence, hold it in a sliding window for every input.

Second, to detect incidents, our method compares the difference between current and usual trafficinstead of building a physical model of traffic flow in case of incidents.Shutoko, or local streets, have many bottlenecks, so speed reduction often occurs without any incidents.Our approach should be one solution to avoid this problem.

Resampling2014-03-2826Kinoshita, A. Takasu, and J. Adachi.Traffic Incident Detection Using Probabilistic Topic Model

Parameter Tuning : K

2014-03-28A. Kinoshita, A. Takasu, and J. Adachi.Traffic Incident Detection Using Probabilistic Topic Model27Parameter Tuning: N2014-03-28A. Kinoshita, A. Takasu, and J. Adachi.Traffic Incident Detection Using Probabilistic Topic Model28

Recommended

View more >