BEGIN:VCALENDAR
VERSION:2.0
PRODID:ECMLPKDD-MB
BEGIN:VEVENT
DTSTAMP;TZID=Europe/Dublin:20180826T200000
UID:_ecmlpkdd_34
DTSTART;TZID="Europe/Dublin":20180911T162000
DTEND;TZID="Europe/Dublin":20180911T164000
LOCATION:Hogan Mezz 1
TRANSP:TRANSPARENT
SEQUENCE:1
DESCRIPTION:Angle-based outlier detection (ABOD) has been recently emerged as an effective method to detect outliers in high dimensions. Instead of examining neighborhoods as proximity-based concepts, ABOD assesses the broadness of angle spectrum of a point as an outlier factor. Despite being a \emph{parameter-free} and robust measure in high-dimensional space, the exact solution of ABOD suffers from the cubic cost $O(n^3)$ regarding the data size $n$, hence cannot be used on large-scale data sets. In this work we present a \emph{conceptual} relationship between the ABOD intuition and the L1-depth concept in statistics, one of the earliest methods used for detecting outliers. Deriving from this relationship, we propose to use L1-depth as a variant of angle-based outlier factors, since it only requires a quadratic computational time as proximity-based outlier factors. Empirically, L1-depth is competitive (often superior) to proximity-based and other proposed angle-based outlier factors on detecting high-dimensional outliers regarding both efficiency and accuracy. In order to avoid the quadratic computational time, we introduce a simple but efficient sampling method named \emph{SamDepth} for estimating L1-depth measure. We also present theoretical analysis to guarantee the reliability of SamDepth. The empirical experiments on many real-world high-dimensional data sets demonstrate that SamDepth with $\sqrt{n}$ samples often achieves very competitive accuracy and runs several orders of magnitude faster than other proximity-based and ABOD competitors.
SUMMARY:L1-Depth Revisited: A Robust Angle-based Outlier Factor in High-dimensional Space
CLASS:PUBLIC
END:VEVENT
END:VCALENDAR