A Survey of Outlier Detection Methodologies <s> Parametric methods <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> BIB001 </s> A Survey of Outlier Detection Methodologies <s> Parametric methods <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> BIB002 </s> A Survey of Outlier Detection Methodologies <s> Parametric methods <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> BIB003 </s> A Survey of Outlier Detection Methodologies <s> Parametric methods <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> BIB004
Many of the methods we have just described do not scale well unless modifications and optimisations are made to the standard algorithm. Parametric methods allow the model to be evaluated very rapidly for new instances and are suitable for large data sets; the model grows only with model complexity not data size. However, they limit their applicability by enforcing a pre-selected distribution model to fit the data. If the user knows their data fits such a distribution model then these approaches are highly accurate but many data sets do not fit one particular model. One such approach is minimum volume ellipsoid estimation (MVE) BIB002 which fits the smallest permissible ellipsoid volume around the majority of the data distribution model (generally covering 50% of the data points). This represents the densely populated normal region shown in Figure 2 (with outliers shown) and Figure 5 (with outliers removed). Figure 5 . Shows a data distribution classified by type 3 -outlier recognition. The data is adapted from the Wine data set  . A similar approach, convex peeling peels away the records on the boundaries of the data distribution's convex hull BIB002 and thus peels away the outliers. In contrast MVE maintains all points and defines a boundary around the majority of points. In convex peeling, each point is assigned a depth. The outliers will have the lowest depth thus placing them on the boundary of the convex hull and are shed from the distribution model. For example in Figure 2 , V, W, X, Y and Z would each be assigned the lowest depth and shed during the first iteration. Peeling repeats the convex hull generation and peeling process on the remaining records until it has removed a pre-specified number of records. The technique is a type 1, unsupervised clustering outlier detector. Unfortunately, it is susceptible to peeling away p þ 1 points from the data distribution on each iteration and eroding the stock of normal points too rapidly BIB002 . Both MVE and convex peeling are robust classifiers that fit boundaries around specific percentages of the data irrespective of the sparseness of the outlying regions and hence outlying data points do not skew the boundary. Both however, rely on a good spread of the data. Figure 2 has few outliers so an ellipsoid circumscribing 50% of the data would omit many normal points from the boundary of normality. Both MVE and convex peeling are only applicable for lower dimensional data sets BIB001 ) (usually three dimensional or less for convex peeling) as they suffer the curse of dimensionality where the convex hull is stretched as more dimensions are added and the surface becomes too difficult to discern. BIB003 also peel away outlying points by iteratively pruning and re-fitting. They measure the effect of deleting points on the placement of the least squares standard regression line for a diagnostic outlier detector. The LS line is placed to minimise equation (4): whereŷ i is the estimated value. Torr and Murray repeatedly delete the single point with maximal influence (the point that causes the greatest deviation in the placement of the regression line) thus allowing the fitted model to stay away from the outliers. They refit the regression to the remaining data until there are no more outliers, i.e., the next point with maximal influence lies below a threshold value. Least squares regression is not robust as the outliers affect the placement of the regression line so it is best suited to outlier diagnostics where the outliers are removed from the next iteration. Figure 6 shows a least squares regression line fitted to a data distribution with the outliers A and B present and then again after point A and B have been removed. Although there are only two outliers, they have a considerable affect on the line placement. BIB003 extend the technique for image segmentation. They use a computationally cheap non-robust least median of squares (LMS) regression if the number of outliers is small which minimises equation (5): or a computationally expensive robust random sampling algorithm if the number of outliers is high. LMS is able to accommodate more outliers than LS as it uses the median values. However, random sampling can accommodate larger numbers of outliers which eventually distort LMS. LMS has also been improved to produce the least trimmed squares approach BIB002 which has faster convergence and minimises equation (6): where ðy i Àŷ i Þ 2 Þ 1:n Á Á Á ðy i Àŷ i Þ 2 Þ n:n are the ordered square residuals. The summation function accommodates outliers in the distribution by fitting the regression to only the majority of the data rather than all of the data as in LMS. This region thus depicts normality and LTS highlights outliers as the points with large deviations from the majority. MVE and convex peeling aim to compact the convex hull and circumscribe the data with a decision boundary but are only applicable for low dimensional data. Principal component analysis (PCA) BIB004  in contrast, is suitable for higher dimensional data. It identifies correlated attributes in the data distribution and projects the data onto this lower dimensional subspace. PCA is an unsupervised classifier but is linear and incapable of outperforming the complex non-linear class boundaries identified by the support vector machine (see section 2.4) or neural methods described in section 3. PCA assumes that the subspaces determined by the principal components are compact and this limits its applicability particularly for sparse distributions. However, it is an ideal pre-processor to select a subset of attributes for methods which suffer the curse of dimensionality such as the multi-layer perceptron in section 3, proximity-based techniques or symplectic transformations described next. PCA identifies the principal component of greatest variance as each component has an associated eigenvalue whose magnitude corresponds to the variance of the points from the component vector. PCA retains the k principal components with greatest variance and discards all others to preserve maximum information and retain minimal redundancy.  recommend retaining sufficient components so the sum of the eigenvalues of all retained components is at least 85% of the sum of all eigenvalues. They use the principal components to predict attribute values in records by finding the intersection between the given values for the record (i.e., excluding the omitted attribute) and the principal components. If the actual value for an attribute and the predicted value differ then the record is flagged as an outlier. BIB004 have developed a type-3 motor fault detector system which applies PCA to the data and then applies a symplectic transformation to the first few principal components. The symplectic transformation may be used with non-linear data distributions. It maps the input data onto a Gaussian distribution, conserving the volume and separating the training data (normal data) from the outliers. This double transformation preserves information while removing redundancy, generates a density estimation of the data set and thus allows a circular contour of the density to act as the decision boundary.  employ one of the hierarchical approaches detailed in this survey. The other hierarchical approaches are the decision tree and cluster trees detailed in the machine learning section. Baker uses a parametric model-based approach for novelty detection in a news story monitor. A hierarchy allows the domain knowledge to be represented at various levels of abstraction so points can be compared for novelty at a fine-grained or less specific level. The hierarchical statistical algorithm induces a topic hierarchy from the word distributions of news stories using expectation maximisation (EM) to estimate the parameter settings followed by deterministic annealing (DA). DA constructs the hierarchy via maximum likelihood and information theory using a divisive clustering approach to split nodes into sub-nodes, starting from a single cluster, and build the hierarchy top-down. DA stochastically determines the node to split. The system detects novelty when new nodes are added to the hierarchy that represent documents that do not belong to any of the existing event clusters so new events are effectively described by their position in the hierarchy. When EM is used in conjunction with DA it avoids some of the initialisation dependence of EM but at the cost of computational efficiency. DA can avoid local minima which EM is susceptible to but it may produce sub-optimal results.