A New Outlier Detection Algorithm Based on Fast Density Peak Clustering Outlier Factor

Introduction

Outlier refers to the data points in the data set that deviate from the normal data distribution; their observations are significantly different from other observations. Outlier detection is the process of finding outliers in a data set and is an important area of data mining research. At present, outlier detection is used in a variety of fields, including industrial wireless sensor networks (Ramotsoela et al., 2018; Safaei et al., 2020), fraud detection (Avdiienko et al., 2017; Ngai et al., 2011), intrusion detection (Denning, 1987), fault detection (Bhatti et al., 2020) and electrocardiogram anomaly detection (Andrysiak, 2020). Research on outlier detection has also proposed many methods, mainly based on statistics (Kafadar et al., 1995; Seheult et al., 1989), distance-based (Knorr et al., 2000; Knorr & Ng, 1997), cluster-based (Ester et al., 1996; Jain et al., 1999; Karypis et al., 1999), density-based (Breunig et al., 2000; Schubert et al., 2014; Wahid & Annavarapu, 2021; Wang et al., 2019; Yang & Liu, 2020; Zhang et al., 2009), and other methods.

Since Breunig et al. (2000) published the local outlier factor method, the density-based outlier identification approach has been one of the most prominent directions in the area of outlier detection. The primary idea behind this categorization approach is to determine the density of each data object using a density estimate algorithm, and then judge outliers based on the region where the data objects are situated. In terms of data objects, there are considerable variances. With the development of clustering approaches in recent years, clustering-based outlier detection algorithms have emerged as an essential component of the outlier detection area. The core idea is to use clustering methods to cluster data sets; outliers are usually in those small-scale clusters that contain very few data objects. The core ideas of the two methods evidences that the two types of methods have certain similarities, and small-scale clusters are often sparse areas. These two types of methods have their advantages and disadvantages. In recent years, many scholars have begun to focus on how to combine the advantages of the two methods to propose a more robust outlier detection algorithm.

Rodriguez and Laio (2014) published an important new clustering algorithm, namely, the density peak clustering (DPC) algorithm. The DPC algorithm is a simple and efficient clustering algorithm. The data set of any dimension is mapped into a two-dimensional decision diagram by estimating the relative distance and density in the nearby area. The decision diagram can clearly reflect the hierarchical relationship of the data set, and then choose the data set with the highest density and the greatest separation from other data sets. The data objects with high density data objects are farther away; these data objects are called density peak points, as the cluster center of the data set. Finally, the remaining data objects are assigned to the cluster center closest to it. Compared with other traditional clustering methods, the DPC algorithm is less affected by outliers and noise. In addition, the DPC algorithm does not require multiple iterations in the clustering process. Therefore, regardless of the detection accuracy or time efficiency, the DPC algorithm is more suitable for combination with the outlier detection algorithm.

Although the DPC algorithm can complete clustering simply and efficiently, there are still some problems. Since the DPC algorithm needs to calculate the density of each data object, a distance matrix will be generated in the process of calculation, which will enhance the temporal complexity while increasing the space complexity. The time complexity of the DPC algorithm is O(n²). For some large-scale data sets, the time efficiency drops severely.