Anomalous window discovery through scan statistics for linear intersecting paths (SSLIP)

ABSTRACT

Anomalous windows are the contiguous groupings of data points. In this paper, we propose an approach for discovering anomalous windows using Scan Statistics for Linear Intersecting Paths (SSLIP). A linear path refers to a path represented by a line with a single dimensional spatial coordinate marking an observation point. Our approach for discovering anomalous windows along linear paths comprises of the following distinct steps: (a) Cross Path Discovery: where we identify a subset of intersecting paths to be considered, (b) Anomalous Window Discovery: where we outline three order invariant algorithms, namely SSLIP, Brute Force-SSLIP and Central Brute Force-SSLIP, for the traversal of the cross paths to identify varying size directional windows along the paths. For identifying an anomalous window we compute an unusualness metric, 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 (c) Monte Carlo Simulations: to ascertain whether this window is truly anomalous and not just a random occurrence we perform hypothesis testing by computing a p-value using Monte Carlo Simulations. We present extensive experimental results in real world accident datasets for various highways with known issues(code and data available from [27], [21]). Our results show that our approach indeed is effective in identifying anomalous traffic accident windows along multiple intersecting highways.

REFERENCES

• 1: 2001 state data for fatalities relating to roadway, pedestrian and large trucks, 2001.
• 2: V. Barnett and T. Lewis. Outliers in Statistical Data. John Wiley and Sons, 3rd edition, 1994.
• 3: J. Besag and J. Newell. The detection of clusters in rare diseases. Jrnl. of the Royal Statistical Society, 154:143---155, 1991.
• 4: L. Duczmal and A. Renato. A simulated annealing strategy for the detection of arbitrarily shaped spatial clusters. Computational Statistics and Data Analysis, 45(2):269--286, 2004.
• 5: M. Ester, H. P. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusters in large spatial databases. In Proc. of the 2nd Intl. Conference on Knowledge Discovery and Data Mining, pages 44--49, U.S.A., 1996. AAAI Press.
• 6: A. Getis. Reflections on spatial autocorrelation. Regional Science and Urban Economics, 37(4):491--496, 2007.
• 7: J. Glaz, J. Naus, and S. Wallenstein. Scan Statistics. Springer Verlag Series in Statistics, New York, 2001.
• 8: D. Griffith. Spatial Autocorrelation: A Primer. Association of American Geographers, 1987.
• 9: R. Haining. Spatial Data Analysis: Theory and Practice. Cambridge University Press, 2003.
• 10: Highway research and technology, the need for greater inverstment, 1999.
• 11: Vijay S. Iyengar, On detecting space-time clusters, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014124]
• 12: Vandana P. Janeja , Vijayalakshmi Atluri, FS³: A Random Walk Based Free-Form Spatial Scan Statistic for Anomalous Window Detection, Proceedings of the Fifth IEEE International Conference on Data Mining, p.661-664, November 27-30, 2005 [doi>10.1109/ICDM.2005.71]
• 13: Vandana Pursnani Janeja , Vijayalakshmi Atluri, LS³: a <u>L</u>inear <u>S</u>emantic <u>S</u>can <u>S</u>tatistic technique for detecting anomalous windows, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico [doi>10.1145/1066677.1066790]
• 14: Vandana P. Janeja , Vijayalakshmi Atluri, Random Walks to Identify Anomalous Free-Form Spatial Scan Windows, IEEE Transactions on Knowledge and Data Engineering, v.20 n.10, p.1378-1392, October 2008 [doi>10.1109/TKDE.2008.96]
• 15: M. Kulldorff. A spatial scan statistic. Communications of Statistics - Theory Meth., 26(6):1481--1496, 1997.
• 16: M. Kulldorff, W. Athas, E. Feuer, B. Miller, and C. Key. Evaluating cluster alarms: A space-time scan statistic and brain cancer in los alamos. American Journal of Public Health, 88(9):1377--1380, 1998.
• 17: H. J. Miller. Tobler's first law and spatial analysis. Annals of the Assoc. of American Geographers, 94(2):284--89, 2004.
• 18: S. Mohammadi, V. Janeja, and A. Gangopadhyay. Discretized spatio-temporal scan window. In The ninth SIAM International conference on Data Mining, 2009.
• 19: J. Naus. The distribution of the size of the maximum cluster of points on the line. Journal of the American Statistical Association 60, pages 532--538, 1965.
• 20: D. Neill, A. Moore, F. Pereira, and T. Mitchell. Detecting significant multidimensional spatial clusters. In Advances in Neural Information Processing Systems 17, pages 969--976. MIT Press, 2005.
• 21: New Jersey accident data for state routes. http://www.state.nj.us/transportation/refdata/accident/, 1999.
• 22: National motor vehicle crash causation survey(dot-hs-811-057), 2008.
• 23: National highway traffic safety administration(nhtsa), traffic safety facts, dot hs 810 809, 2006.
• 24: Nj state routes straight line diagrams, 2009.
• 25: S. Openshaw. A mark 1 geographical analysis machine for the automated analysis of point data sets. Intl. Journal of GIS, 1(4):335--358, 1987.
• 26: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 27: SSLIP : Code
• 28: http://www.umbc.edu/people/leishi1, 2009.
• 29: T. Tango and K. Takahashi. A flexibly shaped spatial scan statistic for detecting clusters. Intl. Journal of Health Geographics, 4(11), 2005.
• 30: W. Tobler. A computer model simulation of urban growth in the detroit region. Eco. Geography, 46(2):234--240, 1970.
• 31: Njdot, top 100 intersection crash locations in nj, 1998-1999, accessed 2004.
• 32: New Jersey Safe Corridor Program http://www.ite.org/meetcon/2007AM/Session_17_Alfred%20Kotchi.pdf, 2007.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Experimentation

Keywords:
anomalous window discovery, intersecting paths, scan statistic, traffic accidents