Institute for Program Structures and Data Organization (IPD), Chair Prof. Böhm

Flexible and Adaptive Subspace Search for Outlier Analysis

  • Author:

    Fabian Keller, Emmanuel Müller, Andreas Wixler, and Klemens Böhm

  • Source: Proceedings of the 22nd ACM International Conference on Information and Knowledge Management (CIKM 2013), San Francisco, USA [full paper acceptance rate 16.9%]
  • There exists a variety of traditional outlier models, which measure the deviation of outliers with respect to the full attribute space. However, these techniques fail to detect outliers that deviate only w.r.t. an attribute subset. To address this problem, recent techniques focus on a selection of subspaces that allow: (1) A clear distinction between clustered objects and outliers; (2) a description of outlier reasons by the selected subspaces. However, depending on the outlier model used, different objects in different subspaces have the highest deviation. It is an open research issue to make subspace selection adaptive to the outlier score of each object and flexible w.r.t. the use of different outlier models.

    In this work we propose such a flexible and adaptive subspace selection scheme. Our generic processing allows instantiations with different outlier models. We utilize the differences of outlier scores in random subspaces to perform a combinatorial refinement of relevant subspaces. Our refinement allows an individual selection of subspaces for each outlier, which is tailored to the underlying outlier model. In the experiments we show the flexibility of our subspace search w.r.t. various outlier models such as distance-based, angle-based, and local-density-based outlier detection.

    Download PDF