Abstract
Knowledge discovery in databases (KDD) is a nontrivial process of detecting valid, novel, potentially useful and ultimately understandable patterns in data (Fayyad, Piatetsky-Shapiro, Smyth & Uthurusamy, 1996). In general KDD tasks can be classified into four categories i) Dependency detection, ii) Class identification, iii) Class description and iv) Outlier detection. The first three categories of tasks correspond to patterns that apply to many objects while the task (iv) focuses on a small fraction of data objects often called outliers (Han & Kamber, 2006). Typically, outliers are data points which deviate more than user expectation from the majority of points in a dataset. There are two types of outliers: i) data points/objects with abnormally large errors and ii) data points/objects with normal errors but at far distance from its neighboring points (Maimon & Rokach, 2005). The former type may be the outcome of malfunctioning of data generator or due to errors while recording data, whereas latter is due to genuine data variation reflecting an unexpected trend in data. Outliers may be present in real life datasets because of several reasons including errors in capturing, storage and communication of data. Since outliers often interfere and obstruct the data mining process, they are considered to be nuisance. In several commercial and scientific applications, a small set of objects representing some rare or unexpected events is often more interesting than the larger ones. Example applications in commercial domain include credit-card fraud detection, criminal activities in e-commerce, pharmaceutical research etc.. In scientific domain, unknown astronomical objects, unexpected values of vital parameters in patient analysis etc. manifest as exceptions in observed data. Outliers are required to be reported immediately to take appropriate action in applications like network intrusion, weather prediction etc., whereas in other applications like astronomy, further investigation of outliers may lead to discovery of new celestial objects. Thus exception/ outlier handling is an important task in KDD and often leads to a more meaningful discovery (Breunig, Kriegel, Raymond & Sander, 2000). In this article different approaches for outlier detection in static datasets are presented.
TopBackground
Outliers are data points which deviate much from the majority of points in a dataset. Figure 1 shows two outliers (O1 and O2) in Employee dataset with two attributes age and salary. Points O1 and O2 represent employees drawing high salary with age 18 and 90 respectively. These points are considered outliers because i) there is no other point in their neighborhood and ii) they are substantially different from the rest of points. Further exploration of such points may reveal some interesting facts.
Figure 1. Distinction between normal data and outliers
Although exact definition of an outlier is application and context dependent, two commonly used general definitions for outliers are as follows. The classical definition is given by Hawkins (Hawkins, 1980) according to which, an outlier is an observation that deviates so much from other observations so as to arouse suspicion that it was generated by a different mechanism. A more recent definition, given by Johnson (Johnson, 1992), defines outlier as an observation which appears to be inconsistent with the remainder of the dataset.