  The task of outlier detection is to find small groups of data objects that
are exceptional when compared with rest large amount of data. Detection of such
outliers is important for many applications such as fraud detection and
customer migration. Most such applications are high dimensional domains in
which the data may contain hundreds of dimensions. However, the outlier
detection problem itself is not well defined and none of the existing
definitions are widely accepted, especially in high dimensional space. In this
paper, our first contribution is to propose a unified framework for outlier
detection in high dimensional spaces from an ensemble-learning viewpoint. In
our new framework, the outlying-ness of each data object is measured by fusing
outlier factors in different subspaces using a combination function.
Accordingly, we show that all existing researches on outlier detection can be
regarded as special cases in the unified framework with respect to the set of
subspaces considered and the type of combination function used. In addition, to
demonstrate the usefulness of the ensemble-learning based outlier detection
framework, we developed a very simple and fast algorithm, namely SOE1 (Subspace
Outlier Ensemble using 1-dimensional Subspaces) in which only subspaces with
one dimension is used for mining outliers from large categorical datasets. The
SOE1 algorithm needs only two scans over the dataset and hence is very
appealing in real data mining applications. Experimental results on real
datasets and large synthetic datasets show that: (1) SOE1 has comparable
performance with respect to those state-of-art outlier detection algorithms on
identifying true outliers and (2) SOE1 can be an order of magnitude faster than
one of the fastest outlier detection algorithms known so far.
