Rapid Distance-Based Outlier Detection via Sampling
Distance-based approaches to outlier detection are popular in data mining, as they do not require to model the underlying probability distribution, which is particularly challenging for high-dimensional data. We present an empirical comparison of various approaches to distance-based outlier detection across a large number of datasets. We report the surprising observation that a simple, sampling-based scheme outperforms state-of-the-art techniques in terms of both efficiency and effectiveness. To better understand this phenomenon, we provide a theoretical analysis why the sampling-based approach outperforms alternative methods based on k-nearest neighbor search.
Summary: This paper proposes a modification of 
      the method of Wu and Jermanine [21] for distance-based outlier 
      detection. The empirical results show that the proposed method 
      outperforms [21] and in fact is generally the best (and fastest) out 
      of the 7 methods tested. To this reader it is (at least at first) 
      surprising that so few samples can be used while retaining good 
      performance. Quality: The modification over [21] is to 
      only draw one sample from the dataset, rather than repeated samples. 
      This would seem to be an effective strategy in terms of variance 
      reduction. What is notable from Fig 1 is that so few samples can be 
      drawn in order to obtain good performance (indeed it seems preferable 
      to use a small number over n). Table 2 shows that this is the 
      fastest method, while table 3 shows that method is only beaten on 4/20 
      datasets by [21]. In sec 4, please state what parameters (e.g. k) 
      are being used here for each method, and also why these are sensible 
      choices. Section 6 provides some analysis of why e.g. small sample 
      sizes might be desirable. I don't find this very compelling, e.g at 
      line 394 they talk about beta being small, but if there are several 
      clusters it seems that beta (defined ie eq 2) will be close to 1. To 
      really make this convincing I would like to see these analysis 
      assumptions tested against values obtained for real data. 
      Clarity: I found the writing clear Originality: this could 
      be seen as a simple "tweak" on [21], although a tweak that appears to 
      have a significant effect. Significance: it appears that the 
      proposed method advances the s-o-a in distance-based outlier 
      detection. Although this topic is more "data mining" than the usual 
      NIPS focus, it could be of practical value. Overall: 
      This paper proposes a simple modification of the method of Wu and 
      Jermanine [21] for distance-based outlier detection. The empirical 
      results presented show that the proposed method outperforms [21] and 
      in fact is generally the best (and fastest) out of the 7 methods 
      tested. To this reader it is (at least at first) surprising that so 
      few sample can be used while retaining good performance. The 
      significance to the NIPS community might be limited due to a 
      relatively low profile for outlier detection.