Anomalous Window Discovery for Linear Intersecting Paths

作者：Shi Lei^*; Janeja Vandana P

来源：IEEE Transactions on Knowledge and Data Engineering, 2011, 23(12): 1857-1871.

DOI：10.1109/TKDE.2010.212

• Spatial scan statistics
• spatial scan window
• linear scan statistic
• anomaly detection

The focus of this paper is to discover anomalous windows in linear intersecting paths. Anomalous windows are the contiguous groupings of data points. A linear path refers to a path represented by a line with a single dimensional spatial coordinate marking an observation point. In this paper, we propose an approach for discovering anomalous windows using a class of algorithms based on scan statistics, specifically 1) an Order invariant algorithm using Scan Statistics for Linear Intersecting Paths (SSLIP), 2) Brute force-SSLIP (BF-SSLIP), and 3) Central Brute Force-SSLIP (CBF-SSLIP). We further present two efficient variants of SSLIP: SSLIP* which employs a upper bound on the scan window size, and SSLIP-Acc, which adopts an accelerator function to speed up the scan process. The proposed approach for discovering anomalous windows along linear paths comprises the following distinct steps: 1) Cross Path Discovery: where we identify a subset of intersecting paths to be considered, 2) Anomalous Window Discovery: where we outline the various algorithms for the traversal of the cross paths to identify varying size directional windows along the paths. For identifying an anomalous window, an unusualness metric is computed, in the form of a likelihood ratio to indicate the degree of unusualness of this window with respect to the rest of the data. We identify the window with the highest likelihood ratio as our anomalous window, and 3) Monte Carlo Simulations: to ascertain whether this window is truly anomalous and not merely random occurrence, we perform hypothesis testing by computing a p-value using Monte Carlo Simulations. We present extensive experimental results in real world accident data sets for various highways with known issues (code and data available from [32], [27]). Additionally, we also perform comparisons with current approaches [18], [34] to show the efficacy of our approach. Our results show that our approach indeed is effective in identifying anomalous traffic accident windows along multiple intersecting highways.

• 出版日期2011-12