A Survey of Outlier Detection Methodologies <s> Proximity-based techniques <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> BIB001 </s> A Survey of Outlier Detection Methodologies <s> Proximity-based techniques <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> BIB002 </s> A Survey of Outlier Detection Methodologies <s> Proximity-based techniques <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> BIB003 </s> A Survey of Outlier Detection Methodologies <s> Proximity-based techniques <s> Clustering algorithms are attractive for the task of class identification in spatial databases. However, the application to large spatial databases rises the following requirements for clustering algorithms: minimal requirements of domain knowledge to determine the input parameters, discovery of clusters with arbitrary shape and good efficiency on large databases. The well-known clustering algorithms offer no solution to the combination of these requirements. In this paper, we present the new clustering algorithm DBSCAN relying on a density-based notion of clusters which is designed to discover clusters of arbitrary shape. DBSCAN requires only one input parameter and supports the user in determining an appropriate value for it. We performed an experimental evaluation of the effectiveness and efficiency of DBSCAN using synthetic data and real data of the SEQUOIA 2000 benchmark. The results of our experiments demonstrate that (1) DBSCAN is significantly more effective in discovering clusters of arbitrary shape than the well-known algorithm CLAR-ANS, and that (2) DBSCAN outperforms CLARANS by a factor of more than 100 in terms of efficiency. <s> BIB004 </s> A Survey of Outlier Detection Methodologies <s> Proximity-based techniques <s> This paper deals with finding outliers (exceptions) in large, multidimensional datasets. The identification of outliers can lead to the discovery of truly unexpected knowledge in areas such as electronic commerce, credit card fraud, and even the analysis of performance statistics of professional athletes. Existing methods that we have seen for finding outliers in large datasets can only deal efficiently with two dimensions/attributes of a dataset. Here, we study the notion of DB- (DistanceBased) outliers. While we provide formal and empirical evidence showing the usefulness of DB-outliers, we focus on the development of algorithms for computing such outliers. First, we present two simple algorithms, both having a complexity of O(k N’), k being the dimensionality and N being the number of objects in the dataset. These algorithms readily support datasets with many more than two attributes. Second, we present an optimized cell-based algorithm that has a complexity that is linear wrt N, but exponential wrt k. Third, for datasets that are mainly disk-resident, we present another version of the cell-based algorithm that guarantees at most 3 passes over a dataset. We provide <s> BIB005 </s> A Survey of Outlier Detection Methodologies <s> Proximity-based techniques <s> Abstract We consider the problem of detecting features in spatial point processes in the presence of substantial clutter. One example is the detection of minefields using reconnaissance aircraft images that identify many objects that are not mines. Our solution uses Kth nearest neighbor distances of points in the process to classify them as clutter or otherwise. The observed Kth nearest neighbor distances are modeled as a mixture distribution, the parameters of which are estimated by a simple EM algorithm. This method allows for detection of generally shaped features that need not be path connected. In the minefield example this method yields high detection and low false-positive rates. Another application, to outlining seismic faults, is considered with some success. The method works well in high dimensions. The method can also be used to produce very high-breakdown-point–robust estimators of a covariance matrix. <s> BIB006 </s> A Survey of Outlier Detection Methodologies <s> Proximity-based techniques <s> Topic Detection and Tracking (TDT) is a DARPA-sponsored initiative to investigate the state of the art in finding and following new events in a stream of broadcast news stories. The TDT problem consists of three major tasks: (1) segmenting a stream of data, especially recognized speech, into distinct stories; (2) identifying those news stories that are the first to discuss a new event occurring in the news; and (3) given a small number of sample news stories about an event, finding all following stories in the stream. <s> BIB007 </s> A Survey of Outlier Detection Methodologies <s> Proximity-based techniques <s> This article is intended to serve as an overview of a rapidly emerging research and applications area. In addition to providing a general overview, motivating the importance of data mining problems within the area of knowledge discovery in databases, our aim is to list some of the pressing research challenges, and outline opportunities for contributions by the optimization research communities. Towards these goals, we include formulations of the basic categories of data mining methods as optimization problems. We also provide examples of successful mathematical programming approaches to some data mining problems. <s> BIB008 </s> A Survey of Outlier Detection Methodologies <s> Proximity-based techniques <s> In this paper, we propose a novel formulation for distance-based outliers that is based on the distance of a point from its kth nearest neighbor. We rank each point on the basis of its distance to its kth nearest neighbor and declare the top n points in this ranking to be outliers. In addition to developing relatively straightforward solutions to finding such outliers based on the classical nested-loop join and index join algorithms, we develop a highly efficient partition-based algorithm for mining outliers. This algorithm first partitions the input data set into disjoint subsets, and then prunes entire partitions as soon as it is determined that they cannot contain outliers. This results in substantial savings in computation. We present the results of an extensive experimental study on real-life and synthetic data sets. The results from a real-life NBA database highlight and reveal several expected and unexpected aspects of the database. The results from a study on synthetic data sets demonstrate that the partition-based algorithm scales well with respect to both data set size and data set dimensionality. <s> BIB009 </s> A Survey of Outlier Detection Methodologies <s> Proximity-based techniques <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
Proximity-based techniques are simple to implement and make no prior assumptions about the data distribution model. They are suitable for both type 1 and type 2 outlier detection. However, they suffer exponential computational growth as they are founded on the calculation of the distances between all records. The computational complexity is directly proportional to both the dimensionality of the data m and the number of records n. Hence, methods such as k-nearest neighbour (also known as instance-based learning and described next) with Oðn 2 mÞ runtime are not feasible for high dimensionality data sets unless the running time can be improved. There are various flavours of k-nearest neighbour (k-NN) algorithm for outlier detection but all calculate the nearest neighbours of a record using a suitable distance calculation metric such as Euclidean distance or Mahalanobis distance. Euclidean distance is given by equation (1): and is simply the vector distance whereas the Mahalanobis distance given by equation (2): calculates the distance from a point to the centroid (l) defined by correlated attributes given by the Covariance matrix (C). Mahalanobis distance is computationally expensive to calculate for large high dimensional data sets compared to the Euclidean distance as it requires a pass through the entire data set to identify the attribute correlations. BIB009 introduce an optimised k-NN to produce a ranked list of potential outliers. A point p is an outlier if no more than n À 1 other points in the data set have a higher D m (distance to mth neighbour) where m is a user-specified parameter. In Figure 3 , V is most isolated followed by X, W, Y then Z so the outlier rank would be V, X, W, Y, Z. This approach is susceptible to the computational growth as the entire distance matrix must be calculated for all points (ALL k-NN) so Ramaswamy et al. include techniques for speeding the k-NN algorithm such as partitioning the data into cells. If any cell and its directly adjacent neighbours contains more than k points, then the points in the cell are deemed to lie in a dense area of the distribution so the points contained are unlikely to be outliers. If the number of points lying in cells more than a pre-specified distance apart is less than k then all points in the cell are labelled as outliers. Hence, only a small number of cells not previously labelled need to be processed and only a relatively small number of distances need to be calculated for outlier detection. Authors have also improved the running speed of k-NN by creating an efficient index using a computationally efficient indexing structure BIB004 with linear running time. BIB005 introduce an efficient type 1 k-NN approach. If m of the k nearest neighbours (where m < k) lie within a specific distance threshold d then the exemplar is deemed to lie in a sufficiently dense region of the data distribution to be classified as normal. However, if there are less than m neighbours inside the distance threshold then the exemplar is an outlier. A very similar type 1 approach for identifying land mines from satellite ground images BIB006 is to take the mth neighbour and find the distance D m . If this distance is less than a threshold d then the exemplar lies in a sufficiently dense region of the data distribution and is classified as normal. However, if the distance is more than the threshold value then the exemplar must lie in a locally sparse area and is an outlier. This has reduced the number of data-specific parameters from BIB005 approach by one as we now have d and m but no k value. In Figure 3 , points V, W, X, Y and Z are relatively distant from their neighbours and will have fewer than m neighbours within d and a high D m so both Knorr and Ng and Byers and Raftery classify them as outliers. This is less susceptible to the computational growth than the ALL k-NN approach as only the k nearest neighbours need to be calculated for a new exemplar rather than the entire distance matrix for all points. A type 2 classification k-NN method such as the majority voting approach  ) requires a labelled data set with both normal and abnormal vectors classified. The k-nearest neighbours for Figure 3 . Shows a data distribution classified by type 1 -outlier clustering. The data is adapted from the Wine data set  . the new exemplar are calculated and it is classified according to the majority classification of the nearest neighbours  ). An extension incorporates the distance where the voting power of each nearest neighbour is attenuated according to its distance from the new item  with the voting power systematically decreasing as the distance increases.  introduce an type 1 outlier diagnostic which unifies weighted k-NN with a connectivitybased approach and calculates a weighted distance score rather than a weighted classification. It calculates the average chaining distance (path length) between a point p and its k neighbours. The early distances are assigned higher weights so if a point lies in a sparse region as points V, W, X, Y and Z in Figure 4 its nearest neighbours in the path will be relatively distant and the average chaining distance will be high. In contrast, Wettschereck requires a data set with good coverage for both normal and abnormal points. The distribution in Figure 4 would cause problems for voted k-NN as there are relatively few examples of outliers and their nearest neighbours, although distant, will in fact be normal points so they are classified as normal. Tang's underlying principle is to assimilate both density and isolation. A point can lie in a relatively sparse region of a distribution without being an outlier but a point in isolation is an outlier. However, the technique is computationally complex with a similar expected run-time to a full k-NN matrix calculation as it relies on calculating paths between all points and their k neighbours. Wettschereck's approach is less susceptible as only the k nearest neighbours are calculated relative to the single new item. . Shows a data distribution classified by type 2 -outlier classification. The data is adapted from the Wine data set  . Another technique for optimising k-NN is reducing the number of features. These feature subset selectors are applicable for most systems described in this survey, not just the k-NN techniques. BIB001 describe a forward sequential selection feature selector which iteratively evaluates feature subsets adding one extra dimension per iteration until the extra dimension entails no improvement in performance. The feature selector demonstrates high accuracy when coupled with an instance-based classifier (nearest neighbour) but is computationally expensive due to the combinatorial problem of subset selection. BIB010 employ lower dimensional projections of the data set and focus on key attributes. The method assumes that outliers are abnormally sparse in certain lower dimensional projections where the combination of attributes in the projection correlates to the attributes that are deviant. Aggarwal and Yu use an evolutionary search algorithm to determine the projections which has a faster running time than the conventional approach employed by Aha and Bankert. Proximity based methods are also computationally susceptible to the number of instances in the data set as they necessitate the calculation of all vector distances. BIB003 use a diagnostic prototype selection to reduce the storage requirements to a few seminal vectors. BIB002 employs both feature selection and prototype selection where a large data set can be stored as a few lower dimensional prototype vectors. Noise and outliers will not be stored as prototypes so the method is robust. Limiting the number of prototypes prevents over-fitting just as pruning a decision tree can prevent overfitting by limiting the number of leaves (prototypes) stored. However, prototyping must be applied carefully and selectively as it will increase the sparsity of the distribution and the density of the nearest neighbours. A majority voting k-NN technique such as  will be less affected but an approach relying on the distances to the nth neighbour BIB006 or counting the number of neighbours within specific distances BIB005 will be strongly affected. Prototyping is in many ways similar to the k-means and k-medoids described next but with prototyping a new instance is compared to the prototypes using conventional k-nearest neighbour whereas k-means and k-medoids prototypes have a kernel with a locally defined radius and the new instance is compared with the kernel boundaries. A prototype approach is also applicable for reducing the data set for neural networks and decision trees. This is particularly germane for node-based neural networks which require multiple passes through the data set to train so a reduced data set will entail less training steps. Dragon Research BIB007 and Nairac  ) (discussed in section 5) use k-means for novelty detection. Dragon perform on-line event detection to identify news stories concerning new events. Each of the k clusters provides a local model of the data. The algorithm represents each of the k clusters by a prototype vector with attribute values equivalent to the mean value across all points in that cluster. In Figure 4 , if k is 3 then the algorithm would effectively circumscribe each class (1, 2 and 3) with a hyper-sphere and these three hyperspheres effectively represent and classify normality. k-Means requires the user to specify the value of k in advance. Determining the optimum number of clusters is a hard problem and necessitates running the k-means algorithm a number of times with different k values and selecting the best results for the particular data set. However, the k value is usually small compared with the number of records in the data set. Thus, the computational complexity for classification of new instances and the storage overhead are vastly reduced as new vectors need only be compared to k prototype vectors and only k prototype vectors need be stored unlike k-NN where all vectors need be stored and compared to each other. k-Means initially chooses random cluster prototypes according to a user-defined selection process, the input data is applied iteratively and the algorithm identifies the best matching cluster and updates the cluster centre to reflect the new exemplar and minimise the sum-of-squares clustering function given by equation (3): where l is the mean of the points (x n ) in cluster S j . Dragon use an adapted similarity metric that incorporates the word count from the news story, the distance to the clusters and the effect the insertion has on the prototype vector for the cluster. After training, each cluster has a radius which is the distance between the prototype and the most distant point lying in the cluster. This radius defines the bounds of normality and is local to each cluster rather than the global distance settings used in many approaches such as BIB006 BIB005 BIB009 k-NN approaches. A new exemplar is compared with the k-cluster model. If the point lies outside all clusters then it is an outlier. A very similar partitional algorithm is the k-medoids algorithm or partition around medoids (PAM) which represents each cluster using an actual point and a radius rather than a prototype (average) point and a radius.  use a k-medoids type approach they call peer group analysis for fraud detection. k-Medoids is robust to outliers as it does not use optimisation to solve the vector placement problem but rather uses actual data points to represent cluster centres. k-Medoids is less susceptible to local minima than standard k-means during training where k-means often converges to poor quality clusters. It is also data-order independent unlike standard k-means where the order of the input data affects the positioning of the cluster centres and BIB008 shows that k-medoids provides better class separation than k-means and hence is better suited to a novelty recognition task due to the improved separation capabilities. However, k-means outperforms k-medoids and can handle larger data sets more efficiently as k-medoids can require O(n 2 ) running time per iteration whereas k-means is O(n). Both approaches can generalise from a relatively small data set. Conversely, the classification accuracy of k-NN, least squares regression or Grubbs' method is susceptible to the number of exemplars in the data set like the kernel-based Parzen windows and the node-based supervised neural networks described later as they all model and analyse the density of the input distribution. The data mining partitional algorithm CLARANS  , is an optimised derivative of the k-medoids algorithm and can handle outlier detection which is achieved as a by-product of the clustering process. It applies a random but bounded heuristic search to find an optimal clustering by only searching a random selection of cluster updates. It requires two user-specified parameters, the value of k and the number of cluster updates to randomly select. Rather than searching the entire data set for the optimal medoid it tests a pre-specified number of potential medoids and selects the first medoid it tests which improves the cluster quality. However, it still has Oðn 2 kÞ running time so is only really applicable for small to medium size data sets. Another proximity-based variant is the graph connectivity method.  introduce an approach to traffic monitoring which examines the neighbourhoods of points but from a topologically connected rather than distance-based perspective. Shekhar detects traffic monitoring stations producing sensor readings which are inconsistent with stations in the immediately connected neighbourhood. A station is an outlier if the difference between its sensor value and the average sensor value of its topological neighbours differs by more than a threshold percentage from the mean difference between all nodes and their topological neighbours. This is analogous to calculating the average distance between each point i and its k neighbours avg D k i and VICTORIA J. HODGE AND JIM AUSTIN then finding any points whose average distance avg D k differs by more than a specified percentage. The technique only considers topologically connected neighbours so there is no prerequisite for specifying k and the number can vary locally depending on the number of connections. However, it is best suited to domains where a connected graph of nodes is available such as analysing traffic flow networks where the individual monitoring stations represent nodes in the connected network.