C-AllOut: Catching & Calling Outliers by Type
  Given an unlabeled dataset, wherein we have access only to pairwise
similarities (or distances), how can we effectively (1) detect outliers, and
(2) annotate/tag the outliers by type? Outlier detection has a large
literature, yet we find a key gap in the field: to our knowledge, no existing
work addresses the outlier annotation problem. Outliers are broadly classified
into 3 types, representing distinct patterns that could be valuable to
analysts: (a) global outliers are severe yet isolate cases that do not repeat,
e.g., a data collection error; (b) local outliers diverge from their peers
within a context, e.g., a particularly short basketball player; and (c)
collective outliers are isolated micro-clusters that may indicate coalition or
repetitions, e.g., frauds that exploit the same loophole. This paper presents
C-AllOut: a novel and effective outlier detector that annotates outliers by
type. It is parameter-free and scalable, besides working only with pairwise
similarities (or distances) when it is needed. We show that C-AllOut achieves
on par or significantly better performance than state-of-the-art detectors when
spotting outliers regardless of their type. It is also highly effective in
annotating outliers of particular types, a task that none of the baselines can
perform.
