A fast MST-inspired kNN-based outlier detection method

• A new k-nearest neighbors (kNN) based outlier detection scheme is proposed.
• It is built upon two new MST-inspired outlier scores, a global one and a local one.
• A set of state-of-the-art outlier detectors are applied to some high dimensional data.
• A fast approximate kNN search algorithm is used to accelerate the mining process.
• The proposed method can provide competing performances with existing solutions.

Today׳s real-world databases typically contain millions of items with many thousands of fields. As a result, traditional distribution-based outlier detection techniques have more and more restricted capabilities and novel k-nearest neighbors based approaches have become more and more popular. However, the problems with these k-nearest neighbors based methods are that they are very sensitive to the value of k, may have different rankings for top n outliers, are very computationally expensive for large datasets, and doubts exist in general whether they would work well for high dimensional datasets. To partially circumvent these problems, we propose in this paper a new global outlier factor and a new local outlier factor and an efficient outlier detection algorithm developed upon them that is easy to implement and can provide competing performances with existing solutions. Experiments performed on both synthetic and real data sets demonstrate the efficacy of our method.