Anomaly detection

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Anomaly detection, also referred to as outlier detection[1] refers to detecting patterns in a given data set that do not conform to an established normal behavior.[2] The patterns thus detected are called anomalies and often translate to critical and actionable information in several application domains. Anomalies are also referred to as outliers, change, deviation, surprise, aberrant, peculiarity, intrusion, etc.

In particular in the context of abuse and network intrusion detection, the interesting objects are often not rare objects, but unexpected bursts in activity. This pattern does not adhere to the common statistical definition of an outlier as a rare object, and many outlier detection methods (in particular unsupervised methods) will fail on such data, unless it has been aggregated appropriately. Instead, a cluster analysis algorithm may be able to detect the micro clusters formed by these patterns.[3]

Three broad categories of anomaly detection techniques exist. Unsupervised anomaly detection techniques detect anomalies in an unlabeled test data set under the assumption that the majority of the instances in the data set are normal by looking for instances that seem to fit least to the remainder of the data set. Supervised anomaly detection techniques require a data set that has been labeled as "normal" and "abnormal" and involves training a classifier (the key difference to many other statistical classification problems is the inherent unbalanced nature of outlier detection). Semi-supervised anomaly detection techniques construct a model representing normal behavior from a given normal training data set, and then testing the likelihood of a test instance to be generated by the learnt model.[citation needed]

Contents

Applications [edit]

Anomaly detection is applicable in a variety of domains, such as intrusion detection, fraud detection, fault detection, system health monitoring, event detection in sensor networks, and detecting Eco-system disturbances. It is often used in preprocessing to remove anomalous data from the dataset. In supervised learning, removing the anomalous data from the dataset often results in a statistically significant increase in accuracy.[4][5]

Popular techniques [edit]

Several anomaly detection techniques have been proposed in literature. Some of the popular techniques are:

Application to data security [edit]

Anomaly detection was proposed for Intrusion detection systems (IDS) by Dorothy Denning in 1986.[7] Anomaly detection for IDS is normally accomplished with thresholds and statistics, but can also be done with Soft computing, and inductive learning.[8] Types of statistics proposed by 1999 included profiles of users, workstations, networks, remote hosts, groups of users, and programs based on frequencies, means, variances, covariances, and standard deviations.[9] The counterpart of Anomaly detection in Intrusion detection is Misuse Detection.

Time series outlier detection [edit]

Parametric tests to find outliers in time series are implemented in almost all statistical packages: Demetra+, for example, uses the most popular ones. One way to detect anomalies in time series is a simple non parametric method called washer.[10] It uses a non parametric test to find one or more outliers in a group of even very short time series. The group must have a similar behaviour, as explained more fully below. An example is that of municipalities cited in the work of Dahlberg and Johanssen (2000).[11] Swedish municipalities expenditures between 1979 and 1987 represent 256 time series. If you consider three years such as, for example, 1981,1982 and 1983, you have 256 simple polygonal chains made of two lines segments. Every couple of segments can approximate a straight line or a convex downward (or convex upward) simple polygonal chain. The idea is to find outliers among the couples of segments that performs in a too much different way from the other couples. In the washer procedure every couple of segments is represented by an index and a non parametric test (Sprent test [12]) is applied to the unknown distribution of those indices.[13] For implementing washer methodology you can download an open source R (programming language) function with a simple numeric example.[14]

See also [edit]

References [edit]

  1. ^ Hans-Peter Kriegel, Peer Kröger, Arthur Zimek (2009). "Outlier Detection Techniques (Tutorial)". 13th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD 2009) (Bangkok, Thailand). Retrieved 2010-06-05. 
  2. ^ Varun Chandola, Arindam Banerjee, and Vipin Kumar, Anomaly Detection: A Survey, ACM Computing Surveys, Vol. 41(3), Article 15, July 2009
  3. ^ Dokas, Paul; Levent Ertoz, Vipin Kumar, Aleksandar Lazarevic, Jaideep Srivastava, Pang-Ning Tan (2002). "Data mining for network intrusion detection". Proceedings NSF Workshop on Next Generation Data Mining. 
  4. ^ Ivan Tomek (1976). "An Experiment with the Edited Nearest-Neighbor Rule". IEEE Transactions on Systems, Man and Cybernetics. 6. pp. 448-452. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4309523&tag=1.
  5. ^ Michael R Smith and Tony Martinez (2011). "Improving Classification Accuracy by Identifying and Removing Instances that Should Be Misclassified". Proceedings of International Joint Conference on Neural Networks (IJCNN 2011). pp. 2690-2697. http://axon.cs.byu.edu/papers/smith.ijcnn2011.pdf.
  6. ^ Breunig, M. M.; Kriegel, H. -P.; Ng, R. T.; Sander, J. (2000). "LOF: Identifying Density-based Local Outliers". ACM SIGMOD Record 29: 93. doi:10.1145/335191.335388.  edit
  7. ^ Denning, Dorothy, "An Intrusion Detection Model," Proceedings of the Seventh IEEE Symposium on Security and Privacy, May 1986, pages 119-131.
  8. ^ Teng, Henry S., Chen, Kaihu, and Lu, Stephen C-Y, "Adaptive Real-time Anomaly Detection Using Inductively Generated Sequential Patterns," 1990 IEEE Symposium on Security and Privacy
  9. ^ Jones, Anita K., and Sielken, Robert S., "Computer System Intrusion Detection: A Survey," Technical Report, Department of Computer Science, University of Virginia, Charlottesville, VA, 1999
  10. ^ Venturini, Andrea, "Time Series Outlier Detection: A New Non Parametric Methodology (Washer)" - Statistica - Università di Bologna, Dec. 2011, Vol.71, Fasc.3, pages 329-344. http://rivista-statistica.unibo.it/article/viewFile/3617/2968
  11. ^ M. DAHLBERG, E. JOHANSSON, (2000), An examination of the dynamic behaviour of local governments using GMM bootstrapping methods, “Journal of applied econometrics”, vol 5, pp. 401-416.
  12. ^ P. SPRENT (1998) "Data driven statistical methods", Chapman and Hall, London.
  13. ^ https://sites.google.com/site/andreaventurini65/home/outlier-detection
  14. ^ https://sites.google.com/site/andreaventurini65/home/outlier-detection/esempio.R?attredirects=0
Retrieved from "http://en.wikipedia.org/w/index.php?title=Anomaly_detection&oldid=555652510"