gen2Out: Detecting and Ranking Generalized Anomalies
  In a cloud of m-dimensional data points, how would we spot, as well as rank,
both single-point- as well as group- anomalies? We are the first to generalize
anomaly detection in two dimensions: The first dimension is that we handle both
point-anomalies, as well as group-anomalies, under a unified view -- we shall
refer to them as generalized anomalies. The second dimension is that gen2Out
not only detects, but also ranks, anomalies in suspiciousness order. Detection,
and ranking, of anomalies has numerous applications: For example, in EEG
recordings of an epileptic patient, an anomaly may indicate a seizure; in
computer network traffic data, it may signify a power failure, or a DoS/DDoS
attack. We start by setting some reasonable axioms; surprisingly, none of the
earlier methods pass all the axioms. Our main contribution is the gen2Out
algorithm, that has the following desirable properties: (a) Principled and
Sound anomaly scoring that obeys the axioms for detectors, (b) Doubly-general
in that it detects, as well as ranks generalized anomaly -- both point- and
group-anomalies, (c) Scalable, it is fast and scalable, linear on input size.
(d) Effective, experiments on real-world epileptic recordings (200GB)
demonstrate effectiveness of gen2Out as confirmed by clinicians. Experiments on
27 real-world benchmark datasets show that gen2Out detects ground truth groups,
matches or outperforms point-anomaly baseline algorithms on accuracy, with no
competition for group-anomalies and requires about 2 minutes for 1 million data
points on a stock machine.
