A Survey of Outlier Detection Methodologies <s> Statistical Models <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> Statistical Models <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> Statistical Models <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> Statistical Models <s> In a precedent-bused domain one appeals to previous cases to support a solution, decision, explanation, or an argument. Experts typically use care in choosing cases in precedent-based domains, and apply such criteria as case relevance, prototypicality, and importance. In domains where both cases and rules are used, experts use an additional case selection criterion: the generalizations that a particular group of cases support. Domain experts use their knowledge of cases to forge the rules learned from those cases. ::: ::: In this paper, we explore inductive learning in a "mixed paradigm" setting, where both rule-based and case-based reasoning methods are used. In particular, we consider how the techniques of casebased reasoning in an adversarial, precedent-based domain can be used to aid a decision-tree based classification algorithm for (1) training set selection, (2) branching feature choice, and (3) induction policy preference and deliberate exploitation of inductive bias. We focus on how precedentbased argumentation may inform the selection of training examples used to build classification trees. The resulting decision trees may then be reexpressed as rules and incorporated into the mixed paradigm system. We discuss the heuristic control problems involved in incorporating an inductive learner into CABARET, a mixed paradigm reasoner. Finally, we present an empirical study in a legal domain of the classification trees generated by various training sets constructed by a case-based reasoning module. <s> BIB004 </s> A Survey of Outlier Detection Methodologies <s> Statistical Models <s> With the goal of reducing computational costs without sacrificing accuracy, we describe two algorithms to find sets of prototypes for nearest neighbor classification. Here, the term “prototypes” refers to the reference instances used in a nearest neighbor computation — the instances with respect to which similarity is assessed in order to assign a class to a new data item. Both algorithms rely on stochastic techniques to search the space of sets of prototypes and are simple to implement. The first is a Monte Carlo sampling algorithm; the second applies random mutation hill climbing. On four datasets we show that only three or four prototypes sufficed to give predictive accuracy equal or superior to a basic nearest neighbor algorithm whose run-time storage costs were approximately 10 to 200 times greater. We briefly investigate how random mutation hill climbing may be applied to select features and prototypes simultaneously. Finally, we explain the performance of the sampling algorithm on these datasets in terms of a statistical measure of the extent of clustering displayed by the target classes. <s> BIB005 </s> A Survey of Outlier Detection Methodologies <s> Statistical Models <s> Accurate weather prediction is crucial for many activities, including Naval operations. Researchers within the meteorological division of the Naval Research Laboratory have developed and fielded several expert systems for problems such as fog and turbulence forecasting, and tropical storm movement. They are currently developing an automated system for satellite image interpretation, part of which involves cloud classification. Their cloud classification database contains 204 high-level features, but contains only a few thousand instances. The predictive accuracy of classifiers can be improved on this task by employing a feature selection algorithm. We explain why non-parametric case-based classifiers are excellent choices for use in feature selection algorithms. We then describe a set of such algorithms that use case-based classifiers, empirically compare them, and introduce novel extensions of backward sequential selection that allows it to scale to this task. Several of the approaches we tested located feature subsets that attain significantly higher accuracies than those found in previously published research, and some did so with fewer features. <s> BIB006 </s> A Survey of Outlier Detection Methodologies <s> Statistical Models <s> Abstract We describe a new representation for learning concepts that differs from the traditional decision tree and rule approach. This representation, called prototypical concept descriptions, can represent several prototypes for a concept. We also describe PL, our algorithm for learning these prototypes, and demonstrate that prototypical concept descriptions can, in some situations, classify more accurately than standard Machine Learning algorithms. More importantly, we show that they yield more stable descriptions when applied in noisy and dynamic situations. <s> BIB007 </s> A Survey of Outlier Detection Methodologies <s> Statistical Models <s> According to Barlow (1989), feature extraction can be understood as finding a statistically independent representation of the probability distribution underlying the measured signals. The search for a statistically independent representation can be formulated by the criterion of minimal mutual information, which reduces to decorrelation in the case of gaussian distributions. If nongaussian distributions are to be considered, minimal mutual information is the appropriate generalization of decorrelation as used in linear Principal Component Analyses (PCA). We also generalize to nonlinear transformations by only demanding perfect transmission of information. This leads to a general class of nonlinear transformations, namely symplectic maps. Conservation of information allows us to consider only the statistics of single coordinates. The resulting factorial representation of the joint probability distribution gives a density estimation. We apply this concept to the real world problem of electrical motor fault detection treated as a novelty detection task. <s> BIB008 </s> A Survey of Outlier Detection Methodologies <s> Statistical Models <s> Informal box plot identification of outliers in realworld medical data was studied. Box plots were used to detect univariate outliers directly whereas the box plotted Mahalanobis distances identified multivariate outliers. Vertigo and female urinary incontinence data were used in the tests. The removal of outliers increased the descriptive classification accuracy of discriminant analysis functions and nearest neighbour method, while the predictive ability of these methods reduced somewhat. Outliers were also evaluated subjectively by expert physicians, who found most of the multivariate outliers to truly be outliers in their area. The experts sometimes disagreed with the method on univariate outliers. This happened, for example, in heterogeneous diagnostic groups where also extreme values are natural. The informal method may be used for straightforward identification of suspicious data or as a tool to collect abnormal cases for an in-depth analysis. <s> BIB009 </s> A Survey of Outlier Detection Methodologies <s> Statistical Models <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> BIB010
Statistical approaches were the earliest algorithms used for outlier detection. Some of the earliest are applicable only for single dimensional data sets. In fact, many of the techniques described in both BIB002 and BIB003 are single dimensional or at best univariate. One such single dimensional method is Grubbs' method (extreme studentized deviate) BIB001 which calculates a Z value as the difference between the mean value for the attribute and the query value divided by the standard deviation for the attribute where the mean and standard deviation are calculated from all attribute values including the query value. The Z value for the query is compared with a 1% or 5% significance level. The technique requires no user parameters as all parameters are derived directly from data. However, the technique is susceptible to the number of exemplars in the data set. The higher the number of records the more statistically representative the sample is likely to be. Statistical models are generally suited to quantitative real-valued data sets or at the very least quantitative ordinal data distributions where the ordinal data can be transformed to suitable numerical values for statistical (numerical) processing. This limits their applicability and increases the processing time if complex data transformations are necessary before processing. Probably one of the simplest statistical outlier detection techniques described here, BIB009 use informal box plots to pinpoint outliers in both univariate and multivariate data sets. This produces a graphical representation (see Figure 1 for an example box plot) and allows a human auditor to visually pinpoint the outlying points. It is analogous to a visual inspection of Figure 2 . Their approach can handle real-valued, ordinal and categorical (no order) attributes. Box plots plot the lower extreme, lower quartile, median, upper quartile and upper extreme points. For univariate data, this is a simple 5-point plot, as in Figure 1  . the authors note that there are no unambiguous total orderings but recommend using the reduced sub-ordering based on the generalised distance metric using the Mahalanobis distance measure (see equation (2)). The Mahalanobis distance measure includes the inter-attribute dependencies so the system can compare attribute combinations. The authors found the approach most accurate for multivariate data where a panel of experts agreed with the outliers detected by the system. For univariate data, outliers are more subjective and may be naturally occurring, for example the heights of adult humans, so there was generally more disagreement. Box plots make no assumptions about the data distribution model but are reliant on a human to note the extreme points plotted on the box plot. Statistical models use different approaches to overcome the problem of increasing dimensionality which both increases the processing time and distorts the data distribution by spreading the convex hull. Some methods preselect key exemplars to reduce the processing time BIB005 BIB007 . As the dimensionality increases, the data points are spread through a larger volume and become less dense. This makes the convex hull harder to discern and is known as the 'Curse of Dimensionality'. The most efficient statistical techniques automatically focus on the salient attributes and are able to process the higher number of dimensions in tractable time. However, many techniques such as k-NN, neural networks, minimum volume ellipsoid or convex peeling described in this survey are susceptible to the Curse of Dimensionality. These approaches may utilise a preprocessing algorithm to preselect the salient attributes BIB004 BIB006 BIB005 . These feature selection techniques essentially remove noise from the data distribution and focus the main cluster of normal data points while isolating the outliers as with Figure 2 . Only a few attributes usually contribute to the deviation of an outlier case from a normal case. An alternative technique is to use an algorithm to project the data onto a lower dimensional subspace to compact the convex hull BIB010 or use principal component analysis BIB008  .