A Survey of Outlier Detection Methodologies <s> Introduction <s> Procedures are given for determining statistically whether the highest observation, the lowest observation, the highest and lowest observations, the two highest observations, the two lowest observations, or more of the observations in the sample are statistical outliers. Both the statistical formulae and the application of the procedures to examples are given, thus representing a rather complete treatment of tests for outliers in single samples. This paper has been prepared primarily as an expository and tutorial article on the problem of detecting outlying observations in much experimental work. We cover only tests of significance in thii paper. <s> BIB001 </s> A Survey of Outlier Detection Methodologies <s> Introduction <s> Partial table of contents. BASIC PRINCIPLES. Why Do Outlying Observations Arise and What Should One Do About Them? The Accommodation Approach: Robust Estimation and Testing. UNIVARIATE DATA. Accommodation Procedures for Univariate Samples. Specific Discordancy Tests for Outliers in Univariate Samples. MULTIVARIATE AND STRUCTURED DATA. Outliers in Multivariate Data. The Outlier Problem for Structured Data: Regression, the Linear Model and Designed Experiments. SPECIAL TOPICS. Bayesian Approaches to Outliers. Outliers in Time Series: An Important Area of Outlier Study. Outliers in Directional Data. Appendix. References and Bibliography. Index. <s> BIB002 </s> A Survey of Outlier Detection Methodologies <s> Introduction <s> 1. Introduction. 2. Simple Regression. 3. Multiple Regression. 4. The Special Case of One-Dimensional Location. 5. Algorithms. 6. Outlier Diagnostics. 7. Related Statistical Techniques. References. Table of Data Sets. Index. <s> BIB003 </s> A Survey of Outlier Detection Methodologies <s> Introduction <s> We present a new method for solving the problem of motion segmentation, identifying the objects within an image moving independently of the background. We utilize the fact that two views of a static 3D point set are linked by a 3 X 3 Fundamental Matrix (F). The Fundamental Matrix contains all the information on structure and motion from a given set of point correspondences and is derived by a least squares method under the assumption that the majority of the image is undergoing a rigid motion. Least squares is the most commonly used method of parameter estimation in computer vision algorithms. However the estimated parameters from a least squares fit can be corrupted beyond recognition in the presence of gross errors or outliers which plague any data from real imagery. Features with a motion independent of the background are those statistically inconsistent from the calculated value of (F). Well founded methods for detecting these outlying points are described. <s> BIB004 </s> A Survey of Outlier Detection Methodologies <s> Introduction <s> Finding and removing outliers is an important problem in data mining. Errors in large databases can be extremely common, so an important property of a data mining algorithm is robustness with respect to errors in the database. Most sophisticated methods in machine learning address this problem to some extent, but not fully, and can be improved by addressing the problem more directly. In this paper we examine C4.5, a decision tree algorithm that is already quite robust - few algorithms have been shown to consistently achieve higher accuracy. C4.5 incorporates a pruning scheme that partially addresses the outlier removal problem. In our ROBUST-C4.5 algorithm we extend the pruning method to fully remove the effect of outliers, and this results in improvement on many databases. <s> BIB005 </s> A Survey of Outlier Detection Methodologies <s> Introduction <s> Novelty Detection techniques are concept-learning methods that proceed by recognizing positive instances of a concept rather than differentiating between its positive and negative instances. Novelty Detection approaches consequently require very few, if any, negative training instances. This paper presents a particular Novelty Detection approach to classification that uses a Redundancy Compression and Non-Redundancy Differentiation technique based on the [Gluck & Myers, 1993] model of the hippocampus, a part of the brain critically involved in learning and memory. In particular, this approach consists of training an autoencoder to reconstruct positive input instances at the output layer and then using this autoencoder to recognize novel instances. Classification is possible, after training, because positive instances are expected to be reconstructed accurately while negative instances are not. The purpose of this paper is to compare HIPPO, the system that implements this technique, to C4.5 and feedforward neural network classification on several applications. <s> BIB006 </s> A Survey of Outlier Detection Methodologies <s> Introduction <s> The outlier detection problem has important applications in the field of fraud detection, network robustness analysis, and intrusion detection. Most such applications are high dimensional domains in which the data can contain hundreds of dimensions. Many recent algorithms use concepts of proximity in order to find outliers based on their relationship to the rest of the data. However, in high dimensional space, the data is sparse and the notion of proximity fails to retain its meaningfulness. In fact, the sparsity of high dimensional data implies that every point is an almost equally good outlier from the perspective of proximity-based definitions. Consequently, for high dimensional data, the notion of finding meaningful outliers becomes substantially more complex and non-obvious. In this paper, we discuss new techniques for outlier detection which find the outliers by studying the behavior of projections from the data set. <s> BIB007
Outlier detection encompasses aspects of a broad spectrum of techniques. Many techniques employed for detecting outliers are fundamentally identical but with different names chosen by the authors. For example, authors describe their various approaches as outlier detection, novelty detection, anomaly detection, noise detection, deviation detection or exception mining. In this paper, we have chosen to call the technique outlier detection although we also use novelty detection where we feel appropriate but we incorporate approaches from all five categories named above. Additionally, authors have proposed many definitions for an outlier with seemingly no universally accepted definition. We will take the definition of BIB001 and quoted in BIB002 . An outlying observation, or outlier, is one that appears to deviate markedly from other members of the sample in which it occurs. A further outlier definition from BIB002 is: An observation (or subset of observations) which appears to be inconsistent with the remainder of that set of data. In Figure 2 , there are five outlier points labelled V, W, X, Y and Z which are clearly isolated and inconsistent with the main cluster of points. The data in the figures in this survey paper is adapted from the Wine data set  . BIB005 states that an outlier may also be 'surprising veridical data', a point belonging to class A but actually situated inside class B so the true (veridical) classification of the point is surprising to the observer. BIB007 note that outliers may be considered as noise points lying outside a set of defined clusters or alternatively outliers may be defined as the points that lie outside of the set of clusters but are also separated from the noise. These outliers behave differently from the norm. In this paper, we focus on the two definitions quoted from BIB002 above and do not consider the dual class-membership problem or separating noise and outliers. Outlier detection is a critical task in many safety critical environments as the outlier indicates abnormal running conditions from which significant performance degradation may well result, such as an aircraft engine rotation defect or a flow problem in a pipeline. An outlier can denote an anomalous object in an image such as a land mine. An outlier may pinpoint an intruder inside a system with malicious intentions so rapid detection is essential. Outlier detection can detect a fault on a factory production line by constantly monitoring specific features of the products and comparing the real-time data with either the features of normal products or those for faults. It is imperative in tasks such as credit card usage monitoring or mobile phone monitoring to detect a sudden change in the usage pattern which may indicate fraudulent usage such as stolen card or stolen phone airtime. Outlier detection accomplishes this by analysing and comparing the time series of usage statistics. For application processing, such as loan application processing or social security benefit payments, an outlier detection system can detect any anomalies in the application before approval or payment. Outlier detection can additionally monitor the circumstances of a benefit claimant over time to ensure the payment has not slipped into fraud. Equity or commodity traders can use outlier detection methods to monitor individual shares or markets and detect novel trends which may indicate buying or selling opportunities. A news delivery system can detect changing news stories and ensure the supplier is first with the breaking news. In a database, outliers may indicate fraudulent cases or they may just denote an error by the entry clerk or a misinterpretation of a missing value code, either way detection of the anomaly is vital for data base consistency and integrity. A more exhaustive list of applications that utilise outlier detection is: -Fraud detection -detecting fraudulent applications for credit cards, state benefits or detecting fraudulent usage of credit cards or mobile phones. -Loan application processing -to detect fraudulent applications or potentially problematical customers. -Intrusion detection -detecting unauthorised access in computer networks. -Activity monitoring -detecting mobile phone fraud by monitoring phone activity or suspicious trades in the equity markets. -Network performance -monitoring the performance of computer networks, for example to detect network bottlenecks. -Fault diagnosis -monitoring processes to detect faults in motors, generators, pipelines or space instruments on space shuttles for example. -Structural defect detection -monitoring manufacturing lines to detect faulty production runs for example cracked beams. -Satellite image analysis -identifying novel features or misclassified features. -Detecting novelties in images -for robot neotaxis or surveillance systems. -Motion segmentation -detecting image features moving independently of the background. -Time-series monitoring -monitoring safety critical applications such as drilling or high-speed milling. -Medical condition monitoring -such as heart-rate monitors. -Pharmaceutical research -identifying novel molecular structures. -Detecting novelty in text -to detect the onset of news stories, for topic detection and tracking or for traders to pinpoint equity, commodities, FX trading stories, outperforming or under performing commodities. -Detecting unexpected entries in databases -for data mining to detect errors, frauds or valid but unexpected entries. -Detecting mislabelled data in a training data set. Outliers arise because of human error, instrument error, natural deviations in populations, fraudulent behaviour, changes in behaviour of systems or faults in systems. How the outlier detection system deals with the outlier depends on the application area. If the outlier indicates a typographical error by an entry clerk then the entry clerk can be notified and simply correct the error so the outlier will be restored to a normal record. An outlier resulting from an instrument reading error can simply be expunged. A survey of human population features may include anomalies such as a handful of very tall people. Here the anomaly is purely natural, although the reading may be worth flagging for verification to ensure no errors, it should be included in the classification once it is verified. A system should use a classification algorithm that is robust to outliers to model data with naturally occurring outlier points. An outlier in a safety critical environment, a fraud detection system, an image analysis system or an intrusion monitoring system must be detected immediately (in real-time) and a suitable alarm sounded to alert the system administrator to the problem. Once the situation has been handled, this anomalous reading may be stored separately for comparison with any new fraud cases but would probably not be stored with the main system data as these techniques tend to model normality and use this to detect anomalies. There are three fundamental approaches to the problem of outlier detection: 1. Type 1 -Determine the outliers with no prior knowledge of the data. This is essentially a learning approach analogous to unsupervised clustering. The approach processes the data as a static distribution, pinpoints the most remote points, and flags them as potential outliers. Type 1 assumes that errors or faults are separated from the 'normal' data and will thus appear as outliers. In Figure 3 , points V, W, X, Y and Z are the remote points separated from the main cluster and would be flagged as possible outliers. We note that the main cluster may be subdivided if necessary into more than one cluster to allow both classification and outlier detection as with Figure 4 . The approach is predominantly retrospective and is analogous to a batchprocessing system. It requires that all data be available before processing and that the data is static. However, once the system possesses a sufficiently large database with good coverage, then it can compare new items with the existing data. There are two sub-techniques commonly employed, diagnosis and accommodation BIB003 . An outlier diagnostic approach highlights the potential outlying points. Once detected, the system may remove these outlier points from future processing of the data distribution. Many diagnostic approaches iteratively prune the outliers and fit their system model to the remaining data until no more outliers are detected. An alternative methodology is accommodation that incorporates the outliers into the distribution model generated and employs a robust classification method. These robust approaches can withstand outliers in the data and generally induce a boundary of normality around the majority of the data which thus represents normal behaviour. In contrast, non-robust classifier methods produce representations which are skewed when outliers are left in. Non-robust methods are best suited when there are only a few outliers in the data set (as in Figure 3 ) as they are computationally cheaper than the robust methods but a robust method must be used if there are a large number of outliers to prevent this distortion. BIB004 use a cheap Least Squares algorithm if there are only a few outliers but switch to a more expensive but robust algorithm for higher frequencies of outliers. 2. Type 2 -Model both normality and abnormality. This approach is analogous to supervised classification and requires pre-labelled data, tagged as normal or abnormal. In Figure 4 , there are three classes of normal data with pre-labelled outliers in isolated areas. The entire area outside the normal class represents the outlier class. The normal points could be classified as a single class or subdivided into the three distinct classes according to the requirements of the system to provide a simple normal/abnormal classification or to provide an abnormal and 3-classes of normally classifier. Classifiers are best suited to static data as the classification needs to be rebuilt from first principles if the data distribution shifts unless the system uses an incremental classifier such as an evolutionary neural network. We describe one such approach later which uses a grow when required  ) network. A type 2 approach can be used for on-line classification, where the classifier learns the classification model and then classifies new exemplars as and when required against the learned model. If the new exemplar lies in a region of normality it is classified as normal, otherwise it is flagged as an outlier. Classification algorithms require a good spread of both normal and abnormal data, i.e., the data should cover the entire distribution to allow generalisation by the classifier. New exemplars may then be classified correctly as classification is limited to a 'known' distribution and a new exemplar derived from a previously unseen region of the distribution may not be classified correctly unless the generalisation capabilities of the underlying classification algorithm are good. 3. Type 3 -Model only normality or in a very few cases model abnormality BIB006  . Authors generally name this technique novelty detection or novelty recognition. It is analogous to a semi-supervised recognition or detection task and can be considered semi-supervised as the normal class is taught but the algorithm learns to recognise abnormality. The approach needs pre-classified data but only learns data marked normal. It is suitable for static or dynamic data as it only learns one class which provides the model of normality. It can learn the model incrementally as new data arrives, tuning the model to improve the fit as each new exemplar becomes available. It aims to define a boundary of normality. A type 3 system recognises a new exemplar as normal if it lies within the boundary and recognises the new exemplar as novel otherwise. In Figure 5 , the novelty recogniser has learned the same data as shown in Figure 2 but only the normal class is learned and a boundary of normality induced. If points V, W, X, Y and Z from Figure 2 are compared to the novelty recogniser they will be labelled as abnormal as they lie outside the induced boundary. This boundary may be hard where a point lies wholly within or wholly outside the boundary or soft where the boundary is graduated depending on the underlying detection algorithm. A soft bounded algorithm can estimate the degree of 'outlierness'. It requires the full gamut of normality to be available for training to permit generalisation. However, it requires no abnormal data for training unlike type 2. Abnormal data is often difficult to obtain or expensive in many fault detection domains such as aircraft engine monitoring. It would be extremely costly to sabotage an aircraft engine just to obtain some abnormal running data. Another problem with type 2 is it cannot always handle outliers from unexpected regions, for example, in fraud detection a new method of fraud never previously encountered or previously unseen fault in a machine may not be handled correctly by the classifier unless generalisation is very good. In this method, as long as the new fraud lies outside the boundary of normality then the system will be correctly detect the fraud. If normality shifts then the normal class modelled by the system may be shifted by re-learning the data model or shifting the model if the underlying modelling technique permits such as evolutionary neural networks. The outlier approaches described in this survey paper generally map data onto vectors. The vectors comprise numeric and symbolic attributes to represent continuous-valued, discrete (ordinal), categorical (unordered numeric), ordered symbolic or unordered symbolic data. The vectors may be monotype or multi-type. The statistical and neural network approaches typically require numeric monotype attributes and need to map symbolic data onto suitable numeric values 1 but the machine learning techniques described are able to accommodate multi-type vectors and symbolic attributes. The outliers are determined from the 'closeness' of vectors using some suitable distance metric. Different approaches work better for different types of data, for different numbers of vectors, for different numbers of attributes, according to the speed required and according to the accuracy required. The two fundamental considerations when selecting an appropriate methodology for an outlier detection system are: -Selecting an algorithm which can accurately model the data distribution and accurately highlight outlying points for a clustering, classification or recognition type technique. The algorithm should also be scalable to the data sets to be processed. -Selecting a suitable neighbourhood of interest for an outlier. The selection of the neighbourhood of interest is non-trivial. Many algorithms define boundaries around normality during processing and autonomously induce a threshold. However, these approaches are often parametric enforcing a specific distribution model or require user-specified parameters such as the number of clusters. Other techniques discussed below require user-defined parameters to define the size or density of neighbourhoods for outlier thresholding. The choice of neighbourhood whether user-defined or autonomously induced needs to be applicable for all density distributions likely to be encountered and can potentially include those with sharp density variations. In the remainder of this paper, we categorise and analyse broad range of outlier detection methodologies. We pinpoint how each handles outliers and make recommendations for when each methodology is appropriate for clustering, classification and/or recognition. BIB002 and BIB003 describe and analyse a broad range of statistical outlier techniques and  analyses a wide range of neural methods. We have observed that outlier detection methods are derived from three fields of computing: statistics (proximity-based, parametric, non-parametric and semi-parametric), neural networks (supervised and unsupervised) and machine learning. In the next four sections, we describe and analyse techniques from all three fields and a collection of hybrid techniques that utilise algorithms from multiple fields. The approaches described here encompass distance-based, set-based, density-based, depth-based, model-based and graph-based algorithms.