A Survey of Outlier Detection Methodologies <s> Machine Learning <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> BIB001 </s> A Survey of Outlier Detection Methodologies <s> Machine Learning <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> BIB002 </s> A Survey of Outlier Detection Methodologies <s> Machine Learning <s> We describe the problem of finding deviations in large data bases. Normally, explicit information outside the data, like integrity constraints or predefined patterns, is used for deviation detection. In contrast, we approach the problem from the inside of the data, using the implicit redundancy of the data. ::: ::: We give a formal description of the problem and present a linear algorithm for detecting deviations. Our solution simulates a mechanism familiar to human beings: after seeing a series of similar data, an element disturbing the series is considered an exception. We also present experimental results from the application of this algorithm on real-life datasets showing its effectiveness. <s> BIB003 </s> A Survey of Outlier Detection Methodologies <s> Machine Learning <s> Finding useful patterns in large datasets has attracted considerable interest recently, and one of the most widely studied problems in this area is the identification of clusters, or densely populated regions, in a multi-dimensional dataset. Prior work does not adequately address the problem of large datasets and minimization of I/O costs.This paper presents a data clustering method named BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies), and demonstrates that it is especially suitable for very large databases. BIRCH incrementally and dynamically clusters incoming multi-dimensional metric data points to try to produce the best quality clustering with the available resources (i.e., available memory and time constraints). BIRCH can typically find a good clustering with a single scan of the data, and improve the quality further with a few additional scans. BIRCH is also the first clustering algorithm proposed in the database area to handle "noise" (data points that are not part of the underlying pattern) effectively.We evaluate BIRCH's time/space efficiency, data input order sensitivity, and clustering quality through several experiments. We also present a performance comparisons of BIRCH versus CLARANS, a clustering method proposed recently for large datasets, and show that BIRCH is consistently superior. <s> BIB004 </s> A Survey of Outlier Detection Methodologies <s> Machine Learning <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> BIB005
Much outlier detection has only focused on continuous real-valued data attributes there has been little focus on categorical data. Most statistical and neural approaches require cardinal or at the least ordinal data to allow vector distances to be calculated and have no mechanism for processing categorical data with no implicit ordering. BIB002 and BIB001 use a C4.5 decision tree to detect outliers in categorical data and thus identify errors and unexpected entries in databases. Decision trees do not require any prior knowledge of the data unlike many statistical methods or neural methods that require parameters or distribution models derived from the data set. Conversely, decision trees have simple class boundaries compared with the complex class boundaries yielded by neural or SVM approaches. Decision trees are robust, do not suffer the curse of dimensionality as they focus on the salient attributes, and work well on noisy data. C4.5 is scalable and can accommodate large data sets and high dimensional data with acceptable running times as they only require a single training phase. C4.5 is suited to type 2 classifier systems but not to novelty recognisers which require algorithms such as k-means which can define a boundary of normality and recognise whether new data lies inside or outside the boundary. However, decision trees are dependent on the coverage of the training data as with many classifiers. They are also susceptible to over fitting where they do not generalise well to completely novel instances which is also a problem for many neural network methods. There are two solutions to over-fitting: pre-selection of records or pruning. BIB001 pre-select cases using the taxonomy from a case-based retrieval algorithm to pinpoint the 'most-on-point-cases' and exclude outliers. They then train a decision tree with this preselected subset of normal cases. Many authors recommend pruning superfluous nodes to improve the generalisation capabilities and prevent over-fitting. BIB002 exploits this tactic and uses repeated pruning and retraining of the decision tree to derive the optimal tree representation until no further pruning is possible. The pruned nodes represent the outliers in the database and are systematically removed until only the majority of normal points are left. BIB003 also uses pruning but in a set-based machinelearning approach. It processes categorical data and can identify outliers where there are errors in any combination of variables. Arning identifies the subset of the data to discard that produces the greatest reduction in complexity relative to the amount of data discarded. He examines the data as a sequence and uses a set-based dissimilarity function to determine how dissimilar the new exemplar is compared to the set of exemplars already examined. A large dissimilarity indicates a potential outlier. The algorithm can run in linear time though this relies on prior knowledge of the data but even without prior knowledge, it is still feasible to process large data mining data sets with the approach. However, even the authors note that it is not possible to have a universally applicable dissimilarity function as the function accuracy is data dependent. This pruning is analogous to the statistical techniques (see section 2.2) of convex peeling or Torr and Murray's approach of shedding points and re-fitting the regression line to the remaining data. Another machine learning technique exploited for outlier detection is rule-based systems which are very similar to decision trees as they both test a series of conditions (antecedents) before producing a conclusion (class). In fact rules may be generated directly from the paths in the decision tree. Rule-based systems are more flexible and incremental than decision trees as new rules may be added or rules amended without disturbing the existing rules. A decision tree may require the generation of a complete new tree.  describe their DC-1 activity monitoring system for detecting fraudulent activity or news story monitoring. The rule-based module may be either a classifier learning classification rules from both normal and abnormal training data or a recogniser trained on normal data only and learning rules to pinpoint changes that identify fraudulent activity. The learned rules create profiling monitors for each rule modelling the behaviour of a single entity, such as a phone account. When the activity of the entity deviates from the expected, the output from the profiling monitor reflects this. All profiling monitors relating to a single entity feed into a detector which combines the inputs and generates an alarm if the deviation exceeds a threshold. This approach detects deviations in sequences compared to Nairac's time-series approach which uses one-step ahead prediction to compare the expected next value in a sequence with the actual value measured. There is no prediction in activity monitoring all comparisons use actual measured values. Lane and Brodley (1997a, b) introduced a similar approach for activity monitoring using similarity-based matching. The system stores and records the activities of users on a computer system as sequences. The system uses similarity-based matching to compare command sequences issued by users against the stored sequences. Due to the asynchronous nature of human-computer interaction, a new fraudulent command sequence is unlikely to exactly match a previously stored sequence. The matching metric must allow for the interpolation of gaps and non-matching sub-sequences reflecting, for example, the user collecting an incoming e-mail. Lane and Brodley take their cue from Michalski's (Dietterich and Michalski, 1985) sequential data modelling techniques and generate a validity analysis for each step in the command sequence entered. They incorporate adjacency into their similarity metric. If the similarity value is between a lower and upper bound threshold then the current sequence up to and including the current command is not anomalous. Data mining algorithms such as BIRCH BIB004 and DBSCAN BIB005 are robust and as such tolerant to outliers but were specifically optimised for clustering large data sets. They are based around tree structured indices and cluster hierarchies. Both techniques are capable of identifying outliers but cannot provide a degree of novelty score. BIRCH BIB004 uses local clustering and data compression and has O(n) running time. BIRCH can operate incrementally, clustering data as and when it becomes available. However, it is limited to numerical data and is dependent on the order of presentation of the data set. It uses a specialised balanced tree structure called a CF-tree which is designed for large, high dimensional data sets and induces a good quality clustering from only a single pass through the data set which can optionally be improved by further passes. It can only store a limited number of records in each tree node and this can lead to an artificial cluster topology. DBSCAN BIB005 is density-based with Oðn log nÞ running time and generates an R*-tree to cluster the data and identify the k nearest neighbours. It can identify clusters of arbitrary shape like the Gaussian mixture model described earlier. DBSCAN has two userspecified parameters which determine the density of the data in the tree but it autonomously determines the number of clusters unlike for example the k-means algorithm. One parameter, the number of neighbours is generally set to 4 but the other parameter (the neighbourhood distance) requires Oðn log nÞ time to calculate. The pre-initialisation step for DBSCAN calculates the distance between a point and its fourth nearest neighbours, plots the distance graph and then requires the user to find a valley in the distance plot. The user must identify where the valley begins from the graph profile and set the parameter accordingly.