Source-linked AI summary
Real-time Traffic Accident Risk Prediction based on Frequent Pattern Tree
Lei Lin, Qian Wang, Adel W. Sadek
TL;DR
Real-time accident-risk prediction requires selecting useful variables from noisy, incomplete, heterogeneous traffic data. The paper proposes FP-tree-based selection using ROPR, compares it with random forest selection in k-NN and Bayesian network models, and finds better performance for FP-tree-selected variables. The best Bayesian network achieved 61.11% sensitivity with a 38.16% false alarm rate.
Problem
The paper addresses how to select important variables to improve real-time traffic accident risk prediction from noisy, incomplete, heterogeneous data.
Method
The method discovers frequent patterns with an FP tree, computes ROPR for each pattern, and adds ROPR to the importance scores of differentiating variables before evaluating k-NN and Bayesian network models.
Results
61.11% sensitivity and a 38.16% false alarm rate were achieved by the best Bayesian network using variables selected by the FP tree; FP-tree-selected variables outperformed random-forest-selected variables across the evaluated model types.
Takeaways & Limitations
FP-tree variable selection yielded better accident-risk prediction models than random forest selection in the evaluated k-NN and Bayesian network settings.
Takeaways & Limitations
Because many values were missing, the study extracted pre-crash and normal data from only one accident-reporting detector.
Abstract
from arXiv · showhide
Traffic accident data are usually noisy, contain missing values, and heterogeneous. How to select the most important variables to improve real-time traffic accident risk prediction has become a concern of many recent studies. This paper proposes a novel variable selection method based on the Frequent Pattern tree (FP tree) algorithm. First, all the frequent patterns in the traffic accident dataset are discovered. Then for each frequent pattern, a new criterion, called the Relative Object Purity Ratio (ROPR) which we proposed, is calculated. This ROPR is added to the importance score of the variables that differentiate one frequent pattern from the others. To test the proposed method, a dataset was compiled from the traffic accidents records detected by only one detector on interstate highway I-64 in Virginia in 2005. This dataset was then linked to other variables such as real-time traffic information and weather conditions. Both the proposed method based on the FP tree algorithm, as well as the widely utilized, random forest method, were then used to identify the important variables or the Virginia dataset. The results indicate that there are some differences between the variables deemed important by the FP tree and those selected by the random forest method. Following this, two baseline models (i.e. a nearest neighbor (k-NN) method and a Bayesian network) were developed to predict accident risk based on the variables identified by both the FP tree method and the random forest method. The results show that the models based on the variable selection using the FP tree performed better than those based on the random forest method for several versions of the k-NN and Bayesian network models.The best results were derived from a Bayesian network model using variables from FP tree. That model could predict 61.11% of accidents accurately while having a false alarm rate of 38.16%.
1 INTRODUCTION
The paper addresses real-time traffic accident risk prediction by proposing FP-tree-based variable selection and comparing it with random forest selection in k-NN and Bayesian network models.
- Traffic accident risk models aim to estimate accident-occurrence probabilities from real-time traffic and weather data.
- The paper proposes an FP-tree method that identifies important variables and calculates their importance scores for accident-risk prediction.
- The study compares FP-tree and random forest variable rankings using k-NN and Bayesian network models trained on an I-64 Virginia detector dataset.
- The paper evaluates variable-selection results through accident-risk prediction models and reports that FP-tree-selected variables produced the best-performing models.
2 MODEL METHODOLOGY
The methodology uses frequent patterns in transaction data to assign variable importance through the Relative Object Purity Ratio and aggregate item-level scores into variable-level scores.
- 2.1 Frequent-Pattern Tree: The FP-tree algorithm compactly represents relevant frequency information and identifies frequent patterns whose support meets a user-defined minimum threshold.
- 2.2 Variable Importance Calculation: For each frequent pattern, ROPR is the absolute difference between its object-value proportion and the whole-dataset object-value proportion.
- 2.2 Variable Importance Calculation: The method adds a pattern’s ROPR to the importance scores of items located in exclusive nodes that distinguish that pattern from others.
- 2.2 Variable Importance Calculation: A variable’s importance score sums the scores of its corresponding discrete items, with continuous variables discretized using fuzzy c-means clustering.
3 MODELING DATASET
The study constructs accident and normal-traffic classification data from one I-64 Virginia detector, using defined time windows and traffic, weather, and visibility variables.
- The pre-crash condition is a 10-minute period beginning five minutes before an accident, while normal conditions use matching weekday periods from nearby weeks.
- Due to many missing values, the study uses data from only the detector that reported each accident; accident occurrence is coded 1 for pre-crash and 0 for normal traffic.
- The dataset contains 174 pre-crash and 569 normal records, split randomly into 80% training and 20% testing sets.
4 MODEL DEVELOPMENT AND RESULTS
The study compares FP-tree- and random-forest-based variable selection for k-NN and Bayesian-network accident-risk prediction. Across both model families, FP-tree-selected variables generally performed better, with the strongest Bayesian-network result reaching 61.11% sensitivity and a 38.16% false alarm rate.
- Variable Importance Calculation: The FP-tree and random-forest methods produced different variable-importance rankings.The FP-tree identified mean speed and occupancy standard deviation as least important, whereas random forest identified mean weather and mean visibility.
- k Nearest Neighbor (k-NN): All k-NN models using FP-tree variables outperformed models using all variables or random-forest-selected variables.For k=2, success rates remained below 46% across scenarios, while false alarm rates reached 49.12%.
- k Nearest Neighbor (k-NN): Increasing k from 2 to 3 improved k-NN sensitivity but also increased false alarm rates.The comparison indicates a trade-off between detecting accidents and generating false alarms as more neighbors are considered.
- Bayesian Network: The Bayesian-network experiments varied discretization width and variable-selection scenario using NED values of 3 and 4.Continuous variables were discretized with normalized equal distances, and the network treated accident occurrence as the response node.
- Bayesian Network: 61.11% sensitivity and a 38.16% false alarm rate were achieved by the best Bayesian network using NED equal to 4 and FP-tree-selected variables.Changing NED from 3 to 4 generally improved sensitivity while leaving the false alarm rate nearly unchanged.
5 CONCLUSIONS
The study found that FP-tree-based variable selection supported stronger real-time accident-risk prediction than random-forest selection across the tested models. Its best-performing model was a Bayesian network using FP-tree-selected variables.
- 61.11% sensitivity and a 38.16% false alarm rate were achieved by the best Bayesian network using FP-tree-selected variables and NED number equal to 4.The study notes that this model used data from only one detector.
- k-NN performance was significantly affected by the selected number of neighbors, k.
- Bayesian network performance was obviously affected by variable discretization.
- FP-tree-selected variables produced better-performing models than random-forest-selected variables for both k-NN and Bayesian network models.