Data Mining_ Concepts and Techniques - Jiawei Han [348]
To find cubes of significantly small sparsity coefficient values, a brute-force approach is to search every cube in every possible subspace. The cost of this, however, is immediately exponential. An evolutionary search can be conducted, which improves efficiency at the expense of accuracy. For details, please refer to the bibliographic notes (Section 12.11). The objects contained by cubes of very small sparsity coefficient values are output as outliers.
In summary, searching for outliers in subspaces is advantageous in that the outliers found tend to be better understood, owing to the context provided by the subspaces. Challenges include making the search efficient and scalable.
12.8.3. Modeling High-Dimensional Outliers
An alternative approach for outlier detection methods in high-dimensional data tries to develop new models for high-dimensional outliers directly. Such models typically avoid proximity measures and instead adopt new heuristics to detect outliers, which do not deteriorate in high-dimensional data.
Let's examine angle-based outlier detection (ABOD) as an example.
Angle-based outliers
Figure 12.15 contains a set of points forming a cluster, with the exception of c, which is an outlier. For each point o, we examine the angle for every pair of points x, y such that x ≠ o, y ≠ o. The figure shows angle as an example.
Figure 12.15 Angle-based outliers.
Note that for a point in the center of a cluster (e.g., a), the angles formed as such differ widely. For a point that is at the border of a cluster (e.g., b), the angle variation is smaller. For a point that is an outlier (e.g., c), the angle variable is substantially smaller. This observation suggests that we can use the variance of angles for a point to determine whether a point is an outlier.
We can combine angles and distance to model outliers. Mathematically, for each point o, we use the distance-weighted angle variance as the outlier score. That is, given a set of points, D, for a point, o , we define the angle-based outlier factor (ABOF) as
(12.23)
where 〈,〉 is the scalar product operator, and is a norm distance.
Clearly, the farther away a point is from clusters and the smaller the variance of the angles of a point, the smaller the ABOF. The ABOD computes the ABOF for each point, and outputs a list of the points in the data set in ABOF-ascending order.
Computing the exact ABOF for every point in a database is costly, requiring a time complexity of O(n3), where n is the number of points in the database. Obviously, this exact algorithm does not scale up for large data sets. Approximation methods have been developed to speed up the computation. The angle-based outlier detection idea has been generalized to handle arbitrary data types. For additional details, see the bibliographic notes (Section 12.11).
Developing native models for high-dimensional outliers can lead to effective methods. However, finding good heuristics for detecting high-dimensional outliers is difficult. Efficiency and scalability on large and high-dimensional data sets are major challenges.
12.9. Summary
■ Assume that a given statistical process is used to generate a set of data objects. An outlier is a data object that deviates significantly from the rest of the objects, as if it were generated by a different mechanism.
■ Types of outliers include global outliers, contextual outliers, and collective outliers. An object may be more than one type of outlier.
■ Global outliers are the simplest form of outlier and the easiest to detect. A contextual outlier deviates significantly with respect to a specific context of the object (e.g., a Toronto temperature value of 28° C is an outlier if it occurs in the context of winter). A subset of data objects forms a collective outlier if the objects as a whole deviate significantly from the entire data set, even though the individual data objects may not be outliers. Collective outlier