A Survey of Outlier Detection Methodologies <s> Hybrid Systems <s> Pattern recognition methods and hidden Markov models can be effective tools for online health monitoring of communications systems. Previous work has assumed that the states in the system model are exhaustive. This can be a significant drawback in real-world fault monitoring applications where it is difficult if not impossible to model all the possible fault states of the system in advance. In this paper a method is described for extending the Markov monitoring approach to allow for unknown or novel states which cannot be accounted for when the model is being designed. The method is described and evaluated on data from one of the Jet Propulsion Laboratory's Deep Space Network antennas. The experimental results indicate that the method is both practical and effective, allowing both discrimination between known states and detection of previously unknown fault conditions. > <s> BIB001 </s> A Survey of Outlier Detection Methodologies <s> Hybrid Systems <s> From the Publisher: ::: Classifier systems play a major role in machine learning and knowledge-based systems, and Ross Quinlan's work on ID3 and C4.5 is widely acknowledged to have made some of the most significant contributions to their development. This book is a complete guide to the C4.5 system as implemented in C for the UNIX environment. It contains a comprehensive guide to the system's use , the source code (about 8,800 lines), and implementation notes. The source code and sample datasets are also available on a 3.5-inch floppy diskette for a Sun workstation. ::: ::: C4.5 starts with large sets of cases belonging to known classes. The cases, described by any mixture of nominal and numeric properties, are scrutinized for patterns that allow the classes to be reliably discriminated. These patterns are then expressed as models, in the form of decision trees or sets of if-then rules, that can be used to classify new cases, with emphasis on making the models understandable as well as accurate. The system has been applied successfully to tasks involving tens of thousands of cases described by hundreds of properties. The book starts from simple core learning methods and shows how they can be elaborated and extended to deal with typical problems such as missing data and over hitting. Advantages and disadvantages of the C4.5 approach are discussed and illustrated with several case studies. ::: ::: This book and software should be of interest to developers of classification-based intelligent systems and to students in machine learning and expert systems courses. <s> BIB002 </s> A Survey of Outlier Detection Methodologies <s> Hybrid Systems <s> Abstract Many existing rule learning systems are computationally expensive on large noisy datasets. In this paper we evaluate the recently-proposed rule learning algorithm IREP on a large and diverse collection of benchmark problems. We show that while IREP is extremely efficient, it frequently gives error rates higher than those of C4.5 and C4.5rules. We then propose a number of modifications resulting in an algorithm RIPPERk that is very competitive with C4.5rules with respect to error rates, but much more efficient on large samples. RIPPERk obtains error rates lower than or equivalent to C4.5rules on 22 of 37 benchmark problems, scales nearly linearly with the number of training examples, and can efficiently process noisy datasets containing hundreds of thousands of examples. <s> BIB003 </s> A Survey of Outlier Detection Methodologies <s> Hybrid Systems <s> This paper presents a new approach to identifying and eliminating mislabeled training instances. The goal of this technique is to improve classification accuracies produced by learning algorithms by improving the quality of the training data. The approach employs an ensemble of classifiers that serve as a filter for the training data. Using an n-fold cross validation, the training data is passed through the filter. Only instances that the filter classifies correctly are passed to the final learning algorithm. We present an empirical evaluation of the approach for the task of automated land cover mapping from remotely sensed data. Labeling error arises in these data from a multitude of sources including lack of consistency in the vegetation classification used, variable measurement techniques, and variation in the spatial sampling resolution. Our evaluation shows that for noise levels of less than 40%, filtering results in higher predictive accuracy than not filtering, and for levels of class noise less than or equal to 20% filtering allows the base-line accuracy to be retained. Our empirical results suggest that the ensemble filter approach is an effective method for identifying labeling errors, and further, that the approach will significantly benefit ongoing research to develop accurate and robust remote sensing-based methods to map land cover at global scales. <s> BIB004 </s> A Survey of Outlier Detection Methodologies <s> Hybrid Systems <s> In this paper, we describe the JAM system, a distributed, scalable and portable agent-based data mining system that employs a general approach to scaling data mining applications that we call meta-learning. JAM provides a set of learning programs, implemented either as JAVA applets or applications, that compute models over data stored locally at a site. JAM also provides a set of meta-learning agents for combining multiple models that were learned (perhaps) at different sites. It employs a special distribution mechanism which allows the migration of the derived models or classifier agents to other remote sites. We describe the overall architecture of the JAM system and the specific implementation currently under development at Columbia University. One of JAM's target applications is fraud and intrusion detection in financial information systems. A brief description of this learning task and JAM's applicability are also described. Interested users may download JAM from http://www.cs.columbia.edu/~sal/JAM/PROJECT. <s> BIB005 </s> A Survey of Outlier Detection Methodologies <s> Hybrid Systems <s> Fraud causes substantial losses to telecommunication carriers. Detection systems which automatically detect illegal use of the network can be used to alleviate the problem. Previous approaches worked on features derived from the call patterns of individual users. In this paper we present a call-based detection system based on a hierarchical regime-switching model. The detection problem is formulated as an inference problem on the regime probabilities. Inference is implemented by applying the junction tree algorithm to the underlying graphical model. The dynamics are learned from data using the EM algorithm and subsequent discriminative training. The methods are assessed using fraud data from a real mobile communication network. <s> BIB006 </s> A Survey of Outlier Detection Methodologies <s> Hybrid Systems <s> Distributed data mining systems aim to discover (and combine) usefull information that is distributed across multiple databases. The JAM system, for example, applies machine learning algorithms to compute models over distributed data sets and employs meta-learning techniques to combine the multiple models. Occasionally, however, these models (or classifiers) are induced from databases that have (moderately) different schemas and hence are incompatible. In this paper, we investigate the problem of combining multiple models computed over distributed data sets with different schemas. Through experiments performed on actual credit card data provided by two different financial institutions, we evaluate the effectiveness of the proposed approaches and demonstrate their potential utility. <s> BIB007 </s> A Survey of Outlier Detection Methodologies <s> Hybrid Systems <s> The structural health of airframes is often monitored by analysis of the frequency of occurrence matrix (FOOM) produced after each flight. Each cell in the matrix records a stress event of a particular severity. These matrices are used to determine how much of the aircraft's life has been used up in each flight. Unfortunately the sensors that produce this data are subject to degradation themselves, resulting in corruption of FOOMs. The paper reports a method of automating detection of sensor faults. It is the only known method that is capable of detecting such faults. The method is in essence a dimensionality reduction algorithm coupled to a novelty detection algorithm that produces measures of unusual counts of stress elements at the level of the individual cell and unusual distributions of counts over the entire FOOM. Cell-level error is detected using a probability threshold and a sum of standard deviations. FOOM-level error is detected using a novel application of the eigenface algorithm. Novelty is measured using a mixture of Gaussian model of the data, fitted using the expectation-maximisation algorithm. <s> BIB008 </s> A Survey of Outlier Detection Methodologies <s> Hybrid Systems <s> The technology for building knowledge-based systems by inductive inference from examples has been demonstrated successfully in several practical applications. This paper summarizes an approach to synthesizing decision trees that has been used in a variety of systems, and it describes one such system, ID3, in detail. Results from recent studies show ways in which the methodology can be modified to deal with information that is noisy and/or incomplete. A reported shortcoming of the basic algorithm is discussed and two means of overcoming it are compared. The paper concludes with illustrations of current research directions. <s> BIB009
The most recent development in outlier detection technology is hybrid systems. The hybrid systems discussed in this section incorporate algorithms from at least two of the preceding sections (statistical, neural or machine learning methods). Hybridisation is used variously to overcome deficiencies with one particular classification algorithm, to exploit the advantages of multiple approaches while overcoming their weaknesses or using a meta-classifier to reconcile the outputs from multiple classifiers to handle all situations. We describe approaches where an additional algorithm is incorporated to overcome weaknesses with the primary algorithm next. The MLP described in section 3 interpolates well but cannot extrapolate to unseen instances. Therefore,  augments his MLP with a Parzen window novelty recogniser. The MLP classifies new items similar to those already seen with high confidence. The Parzen window provides an estimate of the probability density to induce a confidence estimate. Any completely novel instances will lie in a low density and the MLP prediction confidence will be low. Parzen windows are kernel-based algorithms which use various kernel functions to represent the data. Bishop uses one Gaussian kernel (as defined by equation (8)) per input vector with the kernel centred on the attribute values of the vector. The Parzen window method can provide a hard boundary for outlier detection by classifying new exemplar as normal if they belong to a kernel and an outlier otherwise. It can also provide a soft boundary by calculating the probability that the new exemplar belongs to a Gaussian kernel.  similarly incorporate a k-means module with the MLP module in an aircraft engine fault diagnosis system. The k-means module partitions the data and models graph shape normality. It can detect anomalies in the overall vibration shape of new signatures and the MLP detects transitions within the vibration graphs through one-step ahead prediction described in section 3. BIB001 stabilises the output from an MLP to monitor space probe data for fault detection using a hidden Markov model (HMM) as the MLP is susceptible to rapid prediction changes many of which are extraneous. The approach uses time-series data, a snapshot of the space probe transmitted periodically with equal intervals between transmissions. The feed-forward MLP trained using back propagation aims to model the probe and predicts the next state of the probe. However, the MLP has a tendency to switch between states at an artificially high rate so Smyth uses a HMM to correlate the state estimations and smooth the outputs producing a predictor with high accuracy. BIB006 incorporate hierarchical HMMs with EM which helps determine the parameters for time series analysis in the task of cell-phone fraud detection. The authors use the HMM to predict one-step ahead values for a fraud variable in the time series given the current and previous states of a user's account and the EM algorithm is used to provide optimal parameter settings for the HMM to enable accurate one-step ahead prediction. BIB008 introduced a strain gauge fault detection system to detect gauges which are not reading correctly. The system assimilates Gaussian basis function networks (GBFN) and principal components. The technique produces a frequency of occurrence matrix (FOOM) from data taken from aircraft strain gauges operating under normal conditions. The FOOM represents the normal conditions expected during a flight with readings weighted according to their likelihood of occurrence. The approach extracts two unlikeliness features and two principal components from the FOOM and feeds them into a series of GBFN, each trained with different parameter settings. The system selects the GBFN with highest classification accuracy for the data and uses this to classify new FOOMs by thresholding for novelty. A high novelty reading indicates a strain gauge error.  have incorporated a further component into the strain gauge system to detect another form of strain gauge error not covered by the previous approach. They incorporate auxiliary data comprising a vector of accelerations encountered during a flight. Hollier and Austin find the maximally correlated components between the FOOM and the mean and first principal component of the auxiliary data. By establishing a relationship between the auxiliary data and normal FOOMs, they can detect corrupted FOOMs when the relationship breaks down. Authors are beginning to examine the possibilities of ensemble classifiers where a number of different classification algorithms are used and the results from each classifier amalgamated using a suitable metric. From the preceding discussion, it is apparent that all classifiers have differing strengths and weaknesses so a combined approach can exploit the strengths of each classifier while mitigating their weaknesses. The JAM system (Java agents for meta-learning) being developed at Columbia University BIB005 incorporates five machinelearning techniques into a single modular architecture. JAM uses metalearning to assimilate the results from the various modules and produce a single system output. JAM modules are based on the ID3 decision tree BIB009 , its successors CART  and C4.5 BIB002 , Ripper (a rule based learner; BIB003 and a naive Bayes classifier. In experiments, BIB007 demonstrated that these classifiers were complimentary, each performing well on some data sets and comparatively poorly on other data sets. By identifying which approaches excel on which data sets and under which conditions the meta-learner can assess the degree of accuracy and confidence for the outputs from the various classifiers and select the appropriate technique for the data. Ensemble classifiers also permit sub-division of the training data with individual classifier modules trained on subsets of the data. By using multiple data models, JAM mitigates for any loss of accuracy in any one model due to data subdivision. It allows parallel training and classification with each module classifying a new instance in parallel and the meta-learner metric assimilating the results. BIB004 also use an ensemble approach for identifying misclassified instances in a training set of pixels from satellite images of land where each pixel needs to be classified as for example, grassland, woodland, etc. They use three classifiers: a decision tree, a nearest neighbour and a linear machine. The system combines the outputs from the three classifiers using consensus voting. Consensus voting is a more conservative approach than the widely used majority voting. In consensus voting, the system only eliminates an instance from the data set if all three classifiers identify it as an outlier whereas a majority voting system eliminates an instance if the majority of classifiers identify it as an outlier. Consensus voting favours false negatives over false positives with respect to identifying outliers. The three classifiers each use a different distribution model so if all three agree that a point is an outlier then the user can be confident about the decision. Combining multiple classifiers must be done judiciously. An ensemble should obey Occam's Razor, it should be as simple as possible with minimal redundancy, as superfluous modules waste resources, increase complexity and slow processing. Paradoxically, identifying the best combination of classifiers is a combinatorial problem.