A Minimum Spanning Tree Clustering-Inspired Outlier Detection Technique

Due to its important applications in data mining, many techniques have been developed for outlier detection. In contrast to k-nearest neighbor-based outlier detection techniques such as distance-based and density-based algorithms whose results have a relatively strong sensitiveness to the setting of the parameters, clustering-based outlier detection algorithms regard data items in the small groups as outliers and often obtain them as a by-product. Unlike K-means clustering algorithms, minimum spanning tree-based clustering algorithms can find clusters of arbitrary shapes, different sizes, and different densities. However, minimum spanning tree clustering-based outlier detection approaches may incur high computational costs. To partially circumvent these problems, in this chapter, an efficient outlier detection technique is proposed which is inspired by minimum spanning tree-based clustering. Extensive performance evaluations on synthetic as well as real datasets are conducted to show that the proposed approach works well for identifying global as well as local outliers with respect to the state-of-the-art outlier detection methods.