A fast MST-inspired kNN-based outlier detection method. (March 2015)

• Record Type: Journal Article
• Authors: Wang, Xiaochun; Wang, Xia Li; Ma, Yongqiang; Wilkes, D. Mitchell
• Is Part Of: Information systems. Volume 48(2015)
• Page Start: 89
• Page End: 112
• Publication Date: 2015-03
• Subjects: Distance-based outlier detection -- Density-based outlier detection -- Clustering-based outlier detection -- Minimum spanning tree-based clustering -- Approximate k-nearest neighbors' search; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2014.09.002
• Languages: English
• ISSNs: 0306-4379

Abstract

Abstract: 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. Highlights: A new k -nearest neighbors ( k NN) 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 k NN search algorithm is used to accelerate the mining process. The proposed method can provide competing performances with existing solutions.