On path anomaly detection in a large transportation network

The purpose of anomaly (outlier) detection is to find a small group of objects that are numerically distant from the rest of the data set. It is generally applied to identifying anomalies from normal patterns and events in urban traffic flow, trends in air quality change, human activities in urban environments, route quality assurance and control, etc. Traditional research in this field has focused on cases where objects can be represented as points or sequences, and popular methods include clustering, distribution, and distance-based methods. In this paper, we present a new type of outlier detection, path outlier detection, in a large spatial graph typically representing a transportation network. Two types of abnormal paths are presented and their corresponding applications are discussed. To perform path anomaly detection, we propose two fundamental distance metrics, spatial-region-based and perimeter-based, along with path segmentation based metrics to capture local feature differences and to jointly combine similarity and dissimilarity. Search algorithms for three distance metrics and outlier detection algorithms are provided to detect abnormal paths and potentially assist with identifying abnormal events or phenomena which occur during a trip. Experiments were performed on synthetic data sets that correspond to two real-world scenarios, and the results show that the efficient perimeter-based distance metric is very effective when used with path segmentation to capture local features and global features, and to combine similarity and dissimilarity.