# Density Peaks Clustering Based on Feature Reduction and Quasi-Monte Carlo

Authors: Zhihui Hu; Xiaoran Wei; Xiaoxu Han; Guang Kou; Haoyu Zhang; Xueyi Liu; Yefei Bai
Journal: Scientific Programming
 (2022)

---

## Abstract

Density peaks clustering (DPC) is a well-known density-based clustering algorithm that can deal with nonspherical clusters well. However, DPC has high computational complexity and space complexity in calculating local densityρ and distance δ, which makes it suitable only for small-scale data sets. In addition, for clustering high-dimensional data, the performance of DPC still needs to be improved. High-dimensional data not only make the data distribution more complex but also lead to more computational overheads. To address the above issues, we propose an improved density peaks clustering algorithm, which combines feature reduction and data sampling strategy. Specifically, features of the high-dimensional data are automatically extracted by principal component analysis (PCA), auto-encoder (AE), and t-distributed stochastic neighbor embedding (t-SNE). Next, in order to reduce the computational overhead, we propose a novel data sampling method for the low-dimensional feature data. Firstly, the data distribution in the low-dimensional feature space is estimated by the Quasi-Monte Carlo (QMC) sequence with low-discrepancy characteristics. Then, the representative QMC points are selected according to their cell densities. Next, the selected QMC points are used to calculate ρ and δ instead of the original data points. In general, the number of the selected QMC points is much smaller than that of the initial data set. Finally, a two-stage classification strategy based on the QMC points clustering results is proposed to classify the original data set. Compared with current works, our proposed algorithm can reduce the computational complexity from On2 to ONn, where N denotes the number of selected QMC points and n is the size of original data set, typically N≪n. Experimental results demonstrate that the proposed algorithm can effectively reduce the computational overhead and improve the model performance.


---

## Body

## 1. Introduction

With the advent of the era of big data, the importance of data mining is increasingly prominent [1]. As an unsupervised learning method, clustering is widely used in many different fields including image processing, medicine, and archaeology. There are various classical clustering algorithms, such as K-means [2], DBSCAN [3], and AP [4]. According to different standards, clustering algorithms are classified into different categories. Generally speaking, clustering algorithms are divided into partition-based methods, hierarchy-based methods, density-based methods, and grid-based methods.In recent years, a new density peaks clustering (DPC) algorithm has been proposed [5]. It is a typical density-based clustering algorithm with excellent advantages. One advantage is that the DPC relies on the decision graph to select the clustering center. Specifically, DPC draws the decision graph of the data set by defining local density ρ and distance δ. Then, DPC determines the cluster centers based on the decision graph. The obtained cluster centers have two characteristics: (1) The local density of the cluster centers is large and the density of its neighborhood is not greater than itself. (2) The distance between the cluster centers and other data points with a higher density is relatively large. Hence, the cluster centers are data points with high local density and high distance, which are called density peaks. Another advantage is that DPC can not only deal with clusters of arbitrary shape but also does not need to determine the number of categories in advance.Although DPC has achieved good performance in many situations, it still has some drawbacks. Firstly, DPC needs to calculate the local density and distance of each data point, which makes the computational complexityOn2. The expensive computational overhead limits the application of DPC in large-scale data sets. To address this issue, the study in [6] proposed a distributed density peaks clustering algorithm (EDDPC). EDDPC aggregates large-scale data sets into MapReduce and integrates local results to approximate the final results. However, EDDPC is a distributed algorithm and is not suitable for single CPU scenarios. The study in [7] proposed a density-based and grid-based clustering algorithm (DGB). Instead of calculating distances between all data, only a smaller number of grid points are calculated. However, DGB is only suitable for dealing with high-dimensional data set. In general, the data distribution in high-dimensional space may be more complex and contain more noise. Although [8, 9] are proposed to filter the noise, additional operations increase the computational overhead.To address the above problems, an improved density peaks clustering algorithm combining feature reduction and data sampling strategy is proposed in this paper. Firstly, the original data feature space is compressed by some classical feature reduction methods. Then, the low-dimensional feature data are sampled by super-uniformly Quasi-Monte Carlo sequence, and the selected high-density Quasi-Monte Carlo points are used to replace the original data points for clustering. Finally, we perform a two-stage strategy to determine the category for the original data. The proposed method has the following advantages:(1)
The proposed algorithm reduces the computational complexity fromOn2 to ONn, where N and n represent the number of selected QMC points and the size of original data set, respectively. In general, there is N≪n(2)
Through feature reduction, the proposed algorithm reduces the noise form the original data and decreases the complexity of high-dimensional feature space(3)
Extensive experiments have demonstrated the effectiveness of our proposed algorithm in terms of computational overhead and model performance


## 2. Related Work

### 2.1. Feature Reduction

Feature reduction indicates mapping the data from the high-dimensional feature space to a low-dimensional space. The features of the high-dimensional data will be extracted by linear or nonlinear transformation. Hence, efficient low-dimensional features of the original data set can be obtained by various feature reduction methods. An ideal low-dimensional feature should retain the classification information as much as possible and filter the noise.Generally speaking, feature reduction can be divided into linear and nonlinear feature reduction methods. Principal component analysis (PCA) is a classical linear feature reduction method [10]. PCA transforms a group of variables that may correlate with linearly uncorrelated variables by orthogonal transformation. Auto-encoder (AE) and t-distributed stochastic neighbor embedding (t-SNE) are nonlinear feature reduction methods. AE can be regarded as a self-supervised manner that consists of the encoder and the decoder [11]. The input data will be mapped to the hidden layer by the encoder, while the decoder transforms the hidden layer features back to the input. Its goal is to combine some high-order features to reconstruct itself. The t-SNE is a machine learning method basing stochastic neighbor embedding (SNE) for feature reduction [12]. t-SNE maps high-dimensional data to two or more dimensions and alleviates the congestion problem in the process of feature reduction. All the above methods have been applied in many fields [13–15].


### 2.2. Density Peaks Clustering

Density peaks clustering (DPC) is proposed in [5], and it can efficiently deal with arbitrary shape data sets without specifying the cluster number k in advance. The cluster center selected by DPC has two characteristics: (1) the local density of the cluster center should be larger than the local density of its neighbors; (2) Data points with low local density should be far away from other data points with high local density. To describe these characteristics, DPC defines two concepts for each data point xi: the local density ρi and the minimum distance δi. The local density ρi is formulated as(1)ρi=∑jXdij−dc,Xx=1x<00x≥0,where dij represents the distance between xi and xj. dc is the intercept, which is the only artificially defined parameter in DPC. In the code provided by [5], dc is formulated as(2)dc=dNd×2%,where dNd is the size of the distance matrix, which defines the distance between any data point pairs. When the data set is small, the Gaussian kernel function is used to calculate ρi. ρi is formulated as(3)ρi=∑jexp−dij2dc2,In addition,δi is formulated as(4)δi=minj:pj>pidij∃js.t.pj>pimaxj:dijotherwise.DPC draws the decision graph based onρi and δi. Then, DPC selects the data points with both ρi and δi as the cluster centers and assigns the remaining data points to the nearest class. DPC is a simple and efficient algorithm, and a series of works have been carried out [16–22]. However, DPC requires a huge computational overhead. The computational complexity of the DPC is On2, which makes it unsuitable for large-scale data set. To address this problem, a feasible strategy is to sample the data set [23]. Our work is based on the sampling strategy to reduce the computational overhead.


### 2.3. Quasi-Monte Carlo

As a statistical test method, the Monte Carlo method has been widely used in machine learning. The Quasi-Monte Carlo method is similar to the Monte Carlo method, but there are theoretical differences between them. The superiority of the Quasi-Monte Carlo method is to generate the deterministic super-uniformly distributed sequence (called low-discrepancy sequence in mathematics) instead of the pseudo-random sequence generated by the Monte Carlo method. The Quasi-Monte Carlo method has been widely used in the field of machine learning [24, 25]. Specifically, the study in [24] utilizes the Quasi-Monte Carlo method to reduce the computational overhead that occurs in the parameter optimization process of neural networks. The study in [25] generates the Quasi-Monte Carlo sequence to perform the feature map and obtains the low-rank features. Similarity, we generate Quasi-Monte Carlo sequence for data sampling. Next, we briefly describe the Quasi-Monte Carlo sequence.The Quasi-Monte Carlo Random sequence is a deterministic super-uniformly distributed sequence with low deviation. It has the property that any long subsequences are uniformly distributed in the feature space. Recently, the most widely used Quasi-Monte Carlo Random sequence mainly includes Halton sequence [26], Faure sequence [27], and Niederreiter’s t,s sequence [28]. In our work, the Halton sequence is selected to perform the sampling strategy.The Halton sequence is one of the standard low-discrepancy sequences, which is used to generate super-uniformly distributed random numbers. Compared with pseudo-random numbers generated by the Monte Carlo method, it is mathematically proved that the volatility of the Halton sequence is smaller. Specifically, the approximate error of the Halton sequence is determined by the degree of difference of the sequencex1,…,xN. The approximate error is formulated as the following equation:(5)1N∑k=1Nfxk−∫Isfxdx≤VfDN,where 1/N∑k=1Nfxk−∫Isfxdx is the error term, Vf is the Hardy-Krause variation of the function f, and DN is the deviation of x1⋯xN.Because the order ofDN is OlogNs−1/N, the approximate error order of the Quasi-Monte Carlo method is O1/N. Similarly, the error order of the pseudo-random sequence is O1/N. Compared with the above error orders, the error order of the Quasi-Monte Carlo method is smaller than that of the Monte Carlo method. Note that the above discussion only gives the upper limit of approximate error. In fact, the convergence rate of the Halton sequence is much faster than the rate obtained by the upper limit. Generally speaking, the Quasi-Monte Carlo method greatly speeds up the convergence compared with the Monte Carlo method, and the random numbers generated by the Quasi-Monte Carlo method are more uniform.The Monte Carlo method generates the pseudo-random numbers, and the Quasi-Monte Carlo method generates the quasi-random numbers. Figure1 shows the comparison between the quasi-random numbers and the pseudo-random numbers on a two-dimensional plane. As shown in Figure 1, the pseudo-random numbers are not uniformly distributed in some places. However, the Halton sequence is highly uniformly distributed in the whole space. Intuitively, the Quasi-Monte Carlo method may be more comprehensive, while the Monte Carlo method has more blank areas. Hence, this paper adopts the Halton sequence to sample the original data and further proposes a new density peaks clustering algorithm.Figure 1
500 random points of pseudo-random numbers and the quasi-random numbers. (a) Quasi-random numbers (Halton sequence). (b) Pseudo-random numbers.
(a)(b)


## 2.1. Feature Reduction

Feature reduction indicates mapping the data from the high-dimensional feature space to a low-dimensional space. The features of the high-dimensional data will be extracted by linear or nonlinear transformation. Hence, efficient low-dimensional features of the original data set can be obtained by various feature reduction methods. An ideal low-dimensional feature should retain the classification information as much as possible and filter the noise.Generally speaking, feature reduction can be divided into linear and nonlinear feature reduction methods. Principal component analysis (PCA) is a classical linear feature reduction method [10]. PCA transforms a group of variables that may correlate with linearly uncorrelated variables by orthogonal transformation. Auto-encoder (AE) and t-distributed stochastic neighbor embedding (t-SNE) are nonlinear feature reduction methods. AE can be regarded as a self-supervised manner that consists of the encoder and the decoder [11]. The input data will be mapped to the hidden layer by the encoder, while the decoder transforms the hidden layer features back to the input. Its goal is to combine some high-order features to reconstruct itself. The t-SNE is a machine learning method basing stochastic neighbor embedding (SNE) for feature reduction [12]. t-SNE maps high-dimensional data to two or more dimensions and alleviates the congestion problem in the process of feature reduction. All the above methods have been applied in many fields [13–15].


## 2.2. Density Peaks Clustering

Density peaks clustering (DPC) is proposed in [5], and it can efficiently deal with arbitrary shape data sets without specifying the cluster number k in advance. The cluster center selected by DPC has two characteristics: (1) the local density of the cluster center should be larger than the local density of its neighbors; (2) Data points with low local density should be far away from other data points with high local density. To describe these characteristics, DPC defines two concepts for each data point xi: the local density ρi and the minimum distance δi. The local density ρi is formulated as(1)ρi=∑jXdij−dc,Xx=1x<00x≥0,where dij represents the distance between xi and xj. dc is the intercept, which is the only artificially defined parameter in DPC. In the code provided by [5], dc is formulated as(2)dc=dNd×2%,where dNd is the size of the distance matrix, which defines the distance between any data point pairs. When the data set is small, the Gaussian kernel function is used to calculate ρi. ρi is formulated as(3)ρi=∑jexp−dij2dc2,In addition,δi is formulated as(4)δi=minj:pj>pidij∃js.t.pj>pimaxj:dijotherwise.DPC draws the decision graph based onρi and δi. Then, DPC selects the data points with both ρi and δi as the cluster centers and assigns the remaining data points to the nearest class. DPC is a simple and efficient algorithm, and a series of works have been carried out [16–22]. However, DPC requires a huge computational overhead. The computational complexity of the DPC is On2, which makes it unsuitable for large-scale data set. To address this problem, a feasible strategy is to sample the data set [23]. Our work is based on the sampling strategy to reduce the computational overhead.


## 2.3. Quasi-Monte Carlo

As a statistical test method, the Monte Carlo method has been widely used in machine learning. The Quasi-Monte Carlo method is similar to the Monte Carlo method, but there are theoretical differences between them. The superiority of the Quasi-Monte Carlo method is to generate the deterministic super-uniformly distributed sequence (called low-discrepancy sequence in mathematics) instead of the pseudo-random sequence generated by the Monte Carlo method. The Quasi-Monte Carlo method has been widely used in the field of machine learning [24, 25]. Specifically, the study in [24] utilizes the Quasi-Monte Carlo method to reduce the computational overhead that occurs in the parameter optimization process of neural networks. The study in [25] generates the Quasi-Monte Carlo sequence to perform the feature map and obtains the low-rank features. Similarity, we generate Quasi-Monte Carlo sequence for data sampling. Next, we briefly describe the Quasi-Monte Carlo sequence.The Quasi-Monte Carlo Random sequence is a deterministic super-uniformly distributed sequence with low deviation. It has the property that any long subsequences are uniformly distributed in the feature space. Recently, the most widely used Quasi-Monte Carlo Random sequence mainly includes Halton sequence [26], Faure sequence [27], and Niederreiter’s t,s sequence [28]. In our work, the Halton sequence is selected to perform the sampling strategy.The Halton sequence is one of the standard low-discrepancy sequences, which is used to generate super-uniformly distributed random numbers. Compared with pseudo-random numbers generated by the Monte Carlo method, it is mathematically proved that the volatility of the Halton sequence is smaller. Specifically, the approximate error of the Halton sequence is determined by the degree of difference of the sequencex1,…,xN. The approximate error is formulated as the following equation:(5)1N∑k=1Nfxk−∫Isfxdx≤VfDN,where 1/N∑k=1Nfxk−∫Isfxdx is the error term, Vf is the Hardy-Krause variation of the function f, and DN is the deviation of x1⋯xN.Because the order ofDN is OlogNs−1/N, the approximate error order of the Quasi-Monte Carlo method is O1/N. Similarly, the error order of the pseudo-random sequence is O1/N. Compared with the above error orders, the error order of the Quasi-Monte Carlo method is smaller than that of the Monte Carlo method. Note that the above discussion only gives the upper limit of approximate error. In fact, the convergence rate of the Halton sequence is much faster than the rate obtained by the upper limit. Generally speaking, the Quasi-Monte Carlo method greatly speeds up the convergence compared with the Monte Carlo method, and the random numbers generated by the Quasi-Monte Carlo method are more uniform.The Monte Carlo method generates the pseudo-random numbers, and the Quasi-Monte Carlo method generates the quasi-random numbers. Figure1 shows the comparison between the quasi-random numbers and the pseudo-random numbers on a two-dimensional plane. As shown in Figure 1, the pseudo-random numbers are not uniformly distributed in some places. However, the Halton sequence is highly uniformly distributed in the whole space. Intuitively, the Quasi-Monte Carlo method may be more comprehensive, while the Monte Carlo method has more blank areas. Hence, this paper adopts the Halton sequence to sample the original data and further proposes a new density peaks clustering algorithm.Figure 1
500 random points of pseudo-random numbers and the quasi-random numbers. (a) Quasi-random numbers (Halton sequence). (b) Pseudo-random numbers.
(a)(b)


## 3. Description of the Algorithm

In this section, a novel improved density peaks clustering algorithm based on the Quasi-Monte Carlo method (QMC-DPC) is proposed to improve the performance of DPC. Specifically, the proposed method includes two components: the feature reduction module and the data sampling module.


### 3.1. The Feature Reduction Module

In this module, we aim to reduce the feature dimension of data sets. The original data setX∈Rn×m will be transformed to X′∈Rn×d by various feature reduction methods, where d≤m. Our goal is to retain the original information as much as possible while reducing the dimension of the data.In practice, we utilize linear and nonlinear feature reduction methods, including PCA, AE, and t-SNE, respectively. Firstly, we perform the zero-mean normalization forX. For x1,x2,…,xn∈X, we calculate the mean x¯=1/n∑i=1nxi and the standard deviation s=1/n−1∑i=1nxi−x¯2. Hence, we can obtain the normalized numbers xi˜=xi−x¯/s,i∈1,…,n. Then, PCA, AE, and t-SNE are implemented on the normalized data set X˜. For PCA, we choose the number of principal components that are smaller than the original dimension of the data set (except for the two-dimension data set). We keep the original dimension for the two-dimension data set. For AE, we set the AE with three layers, including an encoder, a decoder, and a hidden layer. The dimension of encoder and decoder is equivalent to d and the number of hidden layer units is equivalent to d. For the input data X, we select the hidden layer features as the X′. For t-SNE, the similarity between data points is measured by probability instead of Euclidean distance. Specifically, the similarity of data points in the original feature space is calculated by Gaussian joint probability, while the heavy-tailed student t-distribution is used in the low-dimension to measure the similarity. Then, we minimize the KL divergence to obtain the reduced features X′. Figure 2 shows the obtained two-dimensional features of PCA, AE, and t-SNE on Waveform and Landsat. The original dimensions of Waveform and Landsat are more than 20. From Figure 2, it can be seen that the low-dimensional features that map from higher-dimensional data are distinguishable. In Section 4, we will discuss how to select the feature reduction method by experimental analysis.Figure 2
The obtained two-dimensional features of PCA, AE, and t-SNE. (a) The two-dimensional features of waveform. (b) The two-dimensional features of Landsat.
(a)(b)


### 3.2. The Data Sampling Module

Although we compress the feature dimension of data sets through the feature reduction module, the computational complexity of the DPC is stillOn2. In this module, we aim to reduce the time overhead of DPC. Hence, an improved Density Peaks Clustering algorithm based on super-uniformly Quasi-Monte Carlo sequence (QMC-DPC) is proposed. In summary, we utilize the super-uniformly Quasi-Monte Carlo sequence to sample the low-dimensional feature space of the data set. Then, the representative Quasi-Monte Carlo points are used to calculate δi and ρi instead of the original data. Generally speaking, the number of selected Quasi-Monte Carlo points is much smaller than the size of original data set n. The detailed description of QMC-DPC is given in the following.Specifically, we first define two basic concepts as follows:(1)
Circular data unitC: the circle with the Quasi-Monte Carlo points as the center and radius r(2)
Unit densityCud: the number of data points contained in circular data unit cAssume thatX′=x1′,x2′,…,xn′,X′εRn×d is the low-dimensional feature data set obtained by the feature reduction module. We randomly generate N0 Quasi-Monte Carlo points in the feature space. With the Quasi-Monte Carlo points as the centers, the corresponding C are determined under the appropriate r (When d is small, the parameter r=d/2N0 after experiments). Then, according to whether C contains data points or not, the circular data units are divided into two categories: nonempty unit set and empty unit set, where a nonempty unit set Cne=C|Cud>0 and empty unit set Ce=C|Cud=0. Next, since the empty unit set indicates that it does not contain any data, empty unit set and corresponding Quasi-Monte Carlo points are eliminated. The effect is shown in Figure 3.Figure 3
Sample points and circular data units. (a) Sample points and circular data units. (b) Sample points and nonempty circular units.
(a)(b)As shown in Figure3, the remaining nonempty Quasi-Monte Carlo points are distributed around the sample points, while the removed empty Quasi-Monte Carlo points are far from the sample points. Hence, the distribution of the original data set can be sampled by nonempty Quasi-Monte Carlo points. Furthermore, the local density of the original data set can be estimated by the unit density Cud. Therefore, it is reasonable to utilize the nonempty Quasi-Monte Carlo points to calculate local density ρ and minimum distance δ instead of the original data points. Next, for all the nonempty Quasi-Monte Carlo points (assuming that the number of the nonempty Quasi-Monte Carlo points are N, there is generally N≪N0), the distance of the nonempty Quasi-Monte Carlo point pairs is calculated to obtain the distance matrix A:(6)A=d11⋯d1N⋮⋱⋮dN1⋯dNN=0⋯d1N⋮⋱⋮dN1⋯0,where AεRN×N is a symmetric matrix with diagonal elements that are zero. dN is the ascending order of all elements in A. When N is too small, the dc=dN×2% may be zero which indicates that the function of intercept dc is eliminated. Hence, we remove the zero elements in A and take the first 2% distance from the remaining N2−N elements as the dc. Then, we use equations (3) and (4) to calculate ρi and δi of each nonempty Quasi-Monte Carlo point and draw the decision graph. Figure 4 shows the decision graph of QMC-DPC and DPC on Waveform.Figure 4
The decision graph on waveform. (a) QMC-DPC (PCA). (b) QMC-DPC (AE). (c) QMC-DPC (t-SNE). (d) DPC.
(a)(b)(c)(d)As shown in Figure4, the density peaks obtained by QMC-DPC are easier to distinguish than that of DPC, especially on the low-dimensional features generated by AE and t-SNE. Meanwhile, the number of data points in the decision graph of QMC-DPC is smaller than DPC. Specifically, QMC-DPC (PCA), QMC-DPC (AE), and QMC-DPC (t-SNE), respectively, calculate 2742, 2499, and 2989 data points in the decision graph, while DPC calculates 5000 data points in the decision graph. The above discussion further proves the effectiveness of the Quasi-Monte Carlo sampling method. Specifically, it can be summarized as the following three aspects: (1) Combined with the super uniformity of the Quasi-Monte Carlo sequence, the data sampling is more comprehensive, so as to reduce the bias. This conclusion is described by Figure 1. (2) The number of selected nonempty Quasi-Monte Carlo points is small, which greatly reduces the time and space overhead. This conclusion is described in Figure 3. (3) Based on δ and ρ, data points located in dense areas are difficult to distinguish, because their δ and ρ are similar. On the contrary, Quasi-Monte Carlo points essentially sample the local density, and the distinction between selected nonempty Quasi-Monte Carlo points is enlarged. Finally, according to the nearest distance principle, we propose a two-stage classification strategy:(i)
The density peaks are selected as the class centers, and the remaining nonempty Quasi-Monte Carlo points are assigned to the nearest density peak. The first step obtains the clustering results of all nonempty Quasi-Monte Carlo points.(ii)
The data points ofX′ are assigned to the nearest nonempty Quasi-Monte Carlo point. As the feature mapping is unique, the classification result of X is equivalent to the classification result of X′. The second step obtains the final clustering results of all data points of X.After the above discussion, QMC-DPC is depicted in Algorithm1 and the whole process is shown in Figure 5.Figure 5
The work flow of the overall QMC-DPC.Algorithm 1: QMC-DPC.
Input:The Data set:X=x1,x2,…,xnOutput:Clustering resultsYSteps:(1)
Perform feature reduction onX to obtain low-dimensional feature data X′;(2)
GenerateN0 Quasi-Monte Carlo points and determine circular data unit C on X′;(3)
Count the density for each circular data unitC and generate Cne and Ce;(4)
Calculate the matrixA based on Cne and remove the zero elements in A. Sort the remaining elements and determine the intercept dc;(5)
Calculate theδi and ρi for each nonempty Quasi-Monte Carlo points by equations (3) and (4);(6)
Draw the decision graph to select cluster centers and determine the number ofk;(7)
According to the principle of nearest distance, assign the remaining nonempty Quasi-Monte Carlo Points;(8)
Assign the data points to the class of the nearest nonempty Quasi-Monte Carlo Points;(9)
Return the clustering resultsY.


### 3.3. Algorithm Complexity Analysis

The key of DPC is to draw the decision graph based onρi and δi. Our work retains the idea of choosing cluster centers, but QMC-DPC only calculates ρi and δi for N nonempty Quasi-Monte Carlo points after the screening, making the computational complexity far less than DPC.For the data setX′, the DPC takes the space complexity of On2 to store the distance matrix. The space complexity of QMC-DPC mainly includes: ON0 is required to generate Quasi-Monte Carlo points, ON is required to retain nonempty Quasi-Monte Carlo points, and ON2 is required to store the distance matrix of nonempty Quasi-Monte Carlo point pairs. Therefore, the spatial complexity of QMC-DPC is ON0+N+N2. When n is large, there is ON0+N+N2<On2 in general. However, when n is relatively small, the space complexity of QMC-DPC becomes larger due to generating N0 Quasi-Monte Carlo points.When calculatingρi and δi, DPC needs to calculate the distance matrix with the time complexity of On2. After selecting the cluster centers, the time complexity of classifying data points is also n×k. Therefore, the time complexity of DPC algorithm is On2+nk. The time complexity of QMC-DPC mainly includes On×N0 to calculate the unit density of Quasi-Monte Carlo points, ON2 is required to calculate the ρi and δi of nonempty Quasi-Monte Carlo points, and ON×k is required to classify the nonempty Quasi-Monte Carlo points and On×N when classifying data points. Therefore, the time complexity of QMC-DPC algorithm is On×N+N2. In general, there are always N≪N0 and N0≪n, making the time complexity of the QMC-DPC less than that of the DPC. However, when n is relatively small, the time cost of QMC-DPC is more than that of DPC. In the experiment, we will further prove that even with the addition of the feature reduction module, the proposed algorithm still has time superiority.


## 3.1. The Feature Reduction Module

In this module, we aim to reduce the feature dimension of data sets. The original data setX∈Rn×m will be transformed to X′∈Rn×d by various feature reduction methods, where d≤m. Our goal is to retain the original information as much as possible while reducing the dimension of the data.In practice, we utilize linear and nonlinear feature reduction methods, including PCA, AE, and t-SNE, respectively. Firstly, we perform the zero-mean normalization forX. For x1,x2,…,xn∈X, we calculate the mean x¯=1/n∑i=1nxi and the standard deviation s=1/n−1∑i=1nxi−x¯2. Hence, we can obtain the normalized numbers xi˜=xi−x¯/s,i∈1,…,n. Then, PCA, AE, and t-SNE are implemented on the normalized data set X˜. For PCA, we choose the number of principal components that are smaller than the original dimension of the data set (except for the two-dimension data set). We keep the original dimension for the two-dimension data set. For AE, we set the AE with three layers, including an encoder, a decoder, and a hidden layer. The dimension of encoder and decoder is equivalent to d and the number of hidden layer units is equivalent to d. For the input data X, we select the hidden layer features as the X′. For t-SNE, the similarity between data points is measured by probability instead of Euclidean distance. Specifically, the similarity of data points in the original feature space is calculated by Gaussian joint probability, while the heavy-tailed student t-distribution is used in the low-dimension to measure the similarity. Then, we minimize the KL divergence to obtain the reduced features X′. Figure 2 shows the obtained two-dimensional features of PCA, AE, and t-SNE on Waveform and Landsat. The original dimensions of Waveform and Landsat are more than 20. From Figure 2, it can be seen that the low-dimensional features that map from higher-dimensional data are distinguishable. In Section 4, we will discuss how to select the feature reduction method by experimental analysis.Figure 2
The obtained two-dimensional features of PCA, AE, and t-SNE. (a) The two-dimensional features of waveform. (b) The two-dimensional features of Landsat.
(a)(b)


## 3.2. The Data Sampling Module

Although we compress the feature dimension of data sets through the feature reduction module, the computational complexity of the DPC is stillOn2. In this module, we aim to reduce the time overhead of DPC. Hence, an improved Density Peaks Clustering algorithm based on super-uniformly Quasi-Monte Carlo sequence (QMC-DPC) is proposed. In summary, we utilize the super-uniformly Quasi-Monte Carlo sequence to sample the low-dimensional feature space of the data set. Then, the representative Quasi-Monte Carlo points are used to calculate δi and ρi instead of the original data. Generally speaking, the number of selected Quasi-Monte Carlo points is much smaller than the size of original data set n. The detailed description of QMC-DPC is given in the following.Specifically, we first define two basic concepts as follows:(1)
Circular data unitC: the circle with the Quasi-Monte Carlo points as the center and radius r(2)
Unit densityCud: the number of data points contained in circular data unit cAssume thatX′=x1′,x2′,…,xn′,X′εRn×d is the low-dimensional feature data set obtained by the feature reduction module. We randomly generate N0 Quasi-Monte Carlo points in the feature space. With the Quasi-Monte Carlo points as the centers, the corresponding C are determined under the appropriate r (When d is small, the parameter r=d/2N0 after experiments). Then, according to whether C contains data points or not, the circular data units are divided into two categories: nonempty unit set and empty unit set, where a nonempty unit set Cne=C|Cud>0 and empty unit set Ce=C|Cud=0. Next, since the empty unit set indicates that it does not contain any data, empty unit set and corresponding Quasi-Monte Carlo points are eliminated. The effect is shown in Figure 3.Figure 3
Sample points and circular data units. (a) Sample points and circular data units. (b) Sample points and nonempty circular units.
(a)(b)As shown in Figure3, the remaining nonempty Quasi-Monte Carlo points are distributed around the sample points, while the removed empty Quasi-Monte Carlo points are far from the sample points. Hence, the distribution of the original data set can be sampled by nonempty Quasi-Monte Carlo points. Furthermore, the local density of the original data set can be estimated by the unit density Cud. Therefore, it is reasonable to utilize the nonempty Quasi-Monte Carlo points to calculate local density ρ and minimum distance δ instead of the original data points. Next, for all the nonempty Quasi-Monte Carlo points (assuming that the number of the nonempty Quasi-Monte Carlo points are N, there is generally N≪N0), the distance of the nonempty Quasi-Monte Carlo point pairs is calculated to obtain the distance matrix A:(6)A=d11⋯d1N⋮⋱⋮dN1⋯dNN=0⋯d1N⋮⋱⋮dN1⋯0,where AεRN×N is a symmetric matrix with diagonal elements that are zero. dN is the ascending order of all elements in A. When N is too small, the dc=dN×2% may be zero which indicates that the function of intercept dc is eliminated. Hence, we remove the zero elements in A and take the first 2% distance from the remaining N2−N elements as the dc. Then, we use equations (3) and (4) to calculate ρi and δi of each nonempty Quasi-Monte Carlo point and draw the decision graph. Figure 4 shows the decision graph of QMC-DPC and DPC on Waveform.Figure 4
The decision graph on waveform. (a) QMC-DPC (PCA). (b) QMC-DPC (AE). (c) QMC-DPC (t-SNE). (d) DPC.
(a)(b)(c)(d)As shown in Figure4, the density peaks obtained by QMC-DPC are easier to distinguish than that of DPC, especially on the low-dimensional features generated by AE and t-SNE. Meanwhile, the number of data points in the decision graph of QMC-DPC is smaller than DPC. Specifically, QMC-DPC (PCA), QMC-DPC (AE), and QMC-DPC (t-SNE), respectively, calculate 2742, 2499, and 2989 data points in the decision graph, while DPC calculates 5000 data points in the decision graph. The above discussion further proves the effectiveness of the Quasi-Monte Carlo sampling method. Specifically, it can be summarized as the following three aspects: (1) Combined with the super uniformity of the Quasi-Monte Carlo sequence, the data sampling is more comprehensive, so as to reduce the bias. This conclusion is described by Figure 1. (2) The number of selected nonempty Quasi-Monte Carlo points is small, which greatly reduces the time and space overhead. This conclusion is described in Figure 3. (3) Based on δ and ρ, data points located in dense areas are difficult to distinguish, because their δ and ρ are similar. On the contrary, Quasi-Monte Carlo points essentially sample the local density, and the distinction between selected nonempty Quasi-Monte Carlo points is enlarged. Finally, according to the nearest distance principle, we propose a two-stage classification strategy:(i)
The density peaks are selected as the class centers, and the remaining nonempty Quasi-Monte Carlo points are assigned to the nearest density peak. The first step obtains the clustering results of all nonempty Quasi-Monte Carlo points.(ii)
The data points ofX′ are assigned to the nearest nonempty Quasi-Monte Carlo point. As the feature mapping is unique, the classification result of X is equivalent to the classification result of X′. The second step obtains the final clustering results of all data points of X.After the above discussion, QMC-DPC is depicted in Algorithm1 and the whole process is shown in Figure 5.Figure 5
The work flow of the overall QMC-DPC.Algorithm 1: QMC-DPC.
Input:The Data set:X=x1,x2,…,xnOutput:Clustering resultsYSteps:(1)
Perform feature reduction onX to obtain low-dimensional feature data X′;(2)
GenerateN0 Quasi-Monte Carlo points and determine circular data unit C on X′;(3)
Count the density for each circular data unitC and generate Cne and Ce;(4)
Calculate the matrixA based on Cne and remove the zero elements in A. Sort the remaining elements and determine the intercept dc;(5)
Calculate theδi and ρi for each nonempty Quasi-Monte Carlo points by equations (3) and (4);(6)
Draw the decision graph to select cluster centers and determine the number ofk;(7)
According to the principle of nearest distance, assign the remaining nonempty Quasi-Monte Carlo Points;(8)
Assign the data points to the class of the nearest nonempty Quasi-Monte Carlo Points;(9)
Return the clustering resultsY.


## 3.3. Algorithm Complexity Analysis

The key of DPC is to draw the decision graph based onρi and δi. Our work retains the idea of choosing cluster centers, but QMC-DPC only calculates ρi and δi for N nonempty Quasi-Monte Carlo points after the screening, making the computational complexity far less than DPC.For the data setX′, the DPC takes the space complexity of On2 to store the distance matrix. The space complexity of QMC-DPC mainly includes: ON0 is required to generate Quasi-Monte Carlo points, ON is required to retain nonempty Quasi-Monte Carlo points, and ON2 is required to store the distance matrix of nonempty Quasi-Monte Carlo point pairs. Therefore, the spatial complexity of QMC-DPC is ON0+N+N2. When n is large, there is ON0+N+N2<On2 in general. However, when n is relatively small, the space complexity of QMC-DPC becomes larger due to generating N0 Quasi-Monte Carlo points.When calculatingρi and δi, DPC needs to calculate the distance matrix with the time complexity of On2. After selecting the cluster centers, the time complexity of classifying data points is also n×k. Therefore, the time complexity of DPC algorithm is On2+nk. The time complexity of QMC-DPC mainly includes On×N0 to calculate the unit density of Quasi-Monte Carlo points, ON2 is required to calculate the ρi and δi of nonempty Quasi-Monte Carlo points, and ON×k is required to classify the nonempty Quasi-Monte Carlo points and On×N when classifying data points. Therefore, the time complexity of QMC-DPC algorithm is On×N+N2. In general, there are always N≪N0 and N0≪n, making the time complexity of the QMC-DPC less than that of the DPC. However, when n is relatively small, the time cost of QMC-DPC is more than that of DPC. In the experiment, we will further prove that even with the addition of the feature reduction module, the proposed algorithm still has time superiority.


## 4. Experiment and Analysis

### 4.1. Experimental Setup

To verify the performance of QMC-DPC, the proposed method is compared with related clustering algorithms, including DPC-KNN-PCA [17], SNN-DPC [18], DLORE-DP [16], DPC [5], AP [4], DBSCAN [3], and K-means [2]. The nearest neighbor number is set to 4 in SNN-DPC. The ratio of low-density points in DLORE-DP is set to 0.2. For DBSCAN, the parameter Min Pts is set to 3 and ε is empty. K-means needs to specify the number of classes in advance. The data sets adopted in this section include two major categories: unlabeled data sets and labeled data sets. The details of these data sets are listed in Table 1. In labeled data sets, all data sets are UCI data sets. In unlabeled data sets, Flame, Aggregation, and S2 are Synthetic data sets. KDD is a biological data set, which is used to verify the superiority of our proposed algorithm on large-scale and high-dimensional feature data sets.Table 1
The unlabeled data sets and labeled data sets.
Data setSamplesAttributesCategoriesSourceUnlabeled data setsFlame24023[29]Aggregation78827[31]S25000215[32]KDD145 751742000[33]Labeled data setsIris15043[30]Wine178133[30]Segment2310187[30]Waveform5000213[30]Wpbc198332[30]Breast27792[30]Landsat2000369[30]Pima76882[30]Zoo101167[30]Four evaluation criteria are adopted to evaluate the model performance on labeled data sets, i.e, the Accuracy (Acc) and F-measure (F), Normalized mutual information (NMI), and Adjusted rand index (ARI). These evaluation criteria are described as follows: Assume thatX=x1,x2,…,xn is the data set. Y=y1,y2,…,yn and Y˜=y˜1,y˜2,…,y˜n represent the real labels and the predicted labels, respectively. Acc is denoted as(7)Acc=∑i=1nδyi,mapy˜in,where map. is a permutation mapping function, which uses Hungarian algorithm to match the predicted labels with the real labels.The F-measure is a harmonic mean of precisionprec and recall rec. Prec is the ratio between the number of correct positive results and the number of all positive results returned by the classifier. Rec is the ratio between the number of correct positive results and the number of all data that should have been identified as positive. Ui is the set of the number of all data that should have been classified as positive. Vj is the set of the number of all positive results identified by the classifier. Prec, Rec, and F-measure are defined by the following equations:(8)precUi,Vj=Ui∩VjVj,recUi,Vj=Ui∩VjUj,(9)FUi,Vj=β2+1prec⋅recβ2prec+rec,where β is a nonnegative real number that is set to 1. For the Ui divided by each real label, the nearest one in Vj is selected as its F value:(10)FUi=max1≤j≤CFUi,Vj.Then, we use the weighted average ofFUi to get the final F value:(11)F=∑i=1Rωi⋅FUi,ωi=Uin.The Normalized Mutual Information (NMI) measures the information that the predicted labelsY˜ share with the ground truth Y. NMI is defined as the following equation:(12)NMI=IY˜,YHY˜HY,where IY˜,Y is the mutual information between clustering result and ground truth. HY˜ and HY denote the entropy of clustering result and ground truth, respectively.The Adjusted Rand Index (ARI) is the extension of Rand Index (RI). ARI is defined as the following equation:(13)ARI=RI−ERImaxRI−ERI,where RI=uv+uv¯/uv+uv¯+u¯v+uv¯, uv denotes the data pairs which are in the same class in U and in the same class in V, uv¯ denotes the data pairs which are in different classes in U and in different classes in V. u¯v denotes the data pairs which are in different classes in U and in the same class in V. uv¯ denotes the data pairs which are in the same class in U and in different classes in V. The value of ARI is in the range [− 1, 1]. The upper bound of these evaluation criterions is 1. The larger these criterions are, the better the clustering results are.In the feature reduction module, some parameters are set in advance. For t-SNE, the learning rate is 500, the number of perplexity is 30, and the number of epochs is 800. For AE, the learning rate is 0.01, optimizer is Adam, and the number of epochs is 300.


### 4.2. Experimental Results on Labeled Data Sets

In this section, 9 UCI data sets in Table1 are used to verify the performance of QMC-DPC. All data are normalized to between [0, 1]. To avoid extreme cases, each algorithm runs 10 times and records the average results. The values of evaluation criteria are shown in Table 2 and the best values are highlighted in bold. The relevant parameters of the QMC-DPC are recorded in Table 3.Table 2
The comparison of all algorithms in terms of Acc, F, NMI, and ARI on UCI data sets.
AlgorithmAccFNMIARIAccFNMIARIAccFNMIARIIrisWineSegmentQMC-DPC (PCA)0.8600.7600.6770.7420.5280.6480.5230.3450.6810.6110.7510.539QMC-DPC (AE)0.8830.7850.7870.7710.5160.6110.5880.4060.6160.5780.6120.562QMC-DPC (t-SNE)0.9060.7950.7300.7620.5880.6610.5170.6710.6100.5250.5290.439DPC-KNN-PCA0.0460.6260.6200.4670.4180.5620.4790.2340.6430.3770.4820.539DLORE-DP0.7900.7980.7770.7440.5370.5860.5780.1780.6310.4750.5490.540SNN-DPC0.6000.7400.6890.5570.4420.5680.526−0.0050.6170.3740.0160.429DPC0.8860.7850.7830.7190.4650.6100.4860.3530.6170.5340.7010.539DBSCAN0.6800.7750.7330.5680.3310.5770.009−0.0020.4420.3770.4310.227AP0.8070.7690.6180.3760.4280.4600.5260.2680.6700.3280.5860.502K-means0.6670.6990.5930.5140.3610.5890.4780.3840.6430.5720.6250.493WpbcWaveformBreastQMC-DPC (PCA)0.7150.6990.0360.0420.5220.4980.2070.1550.4720.6440.0730.017QMC-DPC (AE)0.7790.5730.0530.0220.4950.5130.3680.2630.5050.6390.0620.017QMC-DPC (t-SNE)0.6810.6720.0270.0220.4720.6300.4310.4370.5230.6540.0680.014DPC-KNN-PCA0.7620.7970.0150.0120.5060.5610.2600.2470.2850.7640.0270.020DLORE-DP0.6730.6500.020−0.0610.5950.5870.3820.3330.3030.7410.0520.004SNN-DPC0.7520.7860.019−0.0130.3750.5300.0680.0160.2130.6850.0710.016DPC0.6420.6910.015−0.0070.2220.5460.2170.2160.5160.5410.0000.004DBSCAN0.7520.7860.009−0.0130.3310.5770.0000.0250.3530.4380.0590.015AP0.4150.2210.0250.0050.2130.1050.2310.0160.0860.1780.0590.012K-means0.5500.5670.0290.0030.3140.5080.3740.2590.4910.5380.0410.003LandsatPimaZooQMC-DPC (PCA)0.6300.5510.4920.4210.6900.7350.0610.1240.6930.7920.8110.808QMC-DPC (AE)0.6180.5030.5390.3820.6340.7580.0040.0220.6840.7890.7960.796QMC-DPC (t-SNE)0.6120.5170.4580.3700.3900.6870.0070.0270.7120.8130.8220.803DPC-KNN-PCA0.6170.4560.3810.1410.3470.7380.0040.0020.5890.7860.6890.731DLORE-DP0.6350.5460.5400.3580.3520.7090.0020.0110.0290.7390.6900.644SNN-DPC0.5170.4630.2670.0890.6510.7360.0000.0010.0490.8560.8310.713DPC0.6360.5730.5470.4110.3470.7380.0040.0020.3760.3520.3480.076DBSCAN0.5060.4300.0000.0000.3430.7330.0020.0050.6930.7920.7610.691AP0.1040.3270.5040.1870.0100.1590.0790.0170.2670.7580.7920.573K-means0.5650.6470.5480.4690.6220.5590.0280.0540.6740.7120.7430.633The bold values mean the best results.Table 3
Parameter settings on all data sets.
Data setsIrisWineSegmentWpbcWaveformBreastLandsatPimaZooKDDFlameAggregationS2Feature dimension2222424223222r0.350.550.450.350.450.250.400.200.450.350.400.400.35N020020020001500250070020001700180500040010002500As shown in Table2, our proposed algorithm is superior to other algorithms on the whole. Acc indicates the ratio of the number of correct predicted samples to the number of total samples. In terms of Acc, QMC-DPC achieves the highest performance on all data sets except Waveform and Landsat. In particular, QMC-DPC is 33.6% and 34.3% higher than DPC on Zoo and Pima, respectively. F-measure indicates the matching degree between the predicted labels and the true labels of the data set, which is the weighted harmonic mean of precision and recall. In terms of F-measure, QMC-DPC achieves the highest performance on nearly half the data set. NMI quantifies the similarity between the predicted labels and the true labels, which measures the robustness of the algorithm. In terms of NMI, QMC-DPC achieves the highest performance on all data sets except Landsat, Pima, and Zoo. In particular, QMC-DPC is 21.4% higher than DPC on Waveform. ARI is used to measure the degree of coincidence of the two data distributions. In terms of ARI, QMC-DPC achieves the highest performance on all data sets except Breast and Landsat. The ARI value of QMC-DPC is 73.2% higher than DPC on Zoo. In addition, the evaluation criterion values of QMC-DPC (PCA), QMC-DPC (AE), and QMC-DPC (t-SNE) are similar, and the model performance is better than that of DPC on the whole. The above results indicate that the combination of the feature reduction module and the feature sampling module can improve the model performance.


### 4.3. Experimental Results of Unlabeled Data Sets

Since there are no real labels for the unlabeled data sets, the evaluation criteria Acc, F-measure, NMI, and ARI cannot be applied to the unlabeled data sets. To compare the performance on the unlabeled data sets, the evaluation criteria Silhouette Coefficient (SC) and Calinski-Harabasz (CH) are defined. For SC, we first calculate the silhouette coefficient for each data pointi:(14)si=bi−aimaxai,bi,where ai is average dissimilarity between data point i and other data points in the same class, bi is the minimum value of the average dissimilarity between data point i and other categories. Next, we obtain the silhouette coefficient for data set based on si:(15)SC=1n∑i=1nsi,where n is the number of all data points. The value of SC is in the range [−1, 1]. The larger the SC value is, the better the clustering result is.CH is defined as follows:(16)CH=traceB/k−1traceW/k−n,where traceB=∑i=1nniui−u2, ni is the number of data points in class i, ui is the average of data points in class i, and u is the average of all data points. traceW=∑j=1k∑i=1nxi−uj2, k is the cluster numbers. The larger the CH value is, the better the clustering result is.In this section, three synthetic data sets and KDD are selected to verify the performance of QMC-DPC. Flame, Aggregation, and S2 are the classical synthetic data sets. KDD is a large-scale data set with high-dimensional features. Table4 shows the SC and CH of all algorithms on unlabeled data sets. The best values are highlighted in bold. The relevant parameters of the QMC-DPC are recorded in Table 3.Table 4
The comparison of all algorithms in terms of SC and CH on unlabeled data sets.
AlgorithmFlameAggregationS2KDDSCCHSCCHSCCHSCCHQMC-DPC (PCA)0.379153.6720.4611032.8760.45215 011.7490.941 537 569.031 7QMC-DPC (AE)0.303129.0280.4931202.9340.71019 744.3530.944 945 484.132 6QMC-DPC (t-SNE)0.409190.9380.4931202.9340.70419 149.117——DPC-KNN-PCA0.403178.2170.281329.0730.71019 744.353——DLORE-DP0.323108.2440.463883.7130.61117 689.904——SNN-DPC0.13237.0090.363851.9530.0021124.993——DPC0.347133.6150.4931202.9340.71019 744.353——DBSCAN0.2956.8940.318606.2850.5293178.6350.22918 701.700AP0.334247.0170.421660.4220.49617 747.519——K-means0.24580.4060.425967.3940.5397293.5330.69413 042.686The bold values mean the best results.As shown in Table4, our proposed method obtains the best clustering results on the whole, especially QMC-DPC (AE). The “—” in Table 4 indicates that the algorithm cannot execute because it exceeds the virtual memory. For the SC, QMC-DPC (t-SNE) is higher than DPC on Flame. And, DPC obtains the same results as our proposed method on Aggregation and S2. DPC-KNN-PCA also obtains the same results as our proposed method on S2. In general, QMC-DPC (AE) and QMC-DPC (t-SNE) achieve the better performance than QMC-DPC (PCA) except KDD. Limited by the t-SNE method, QMC-DPC (t-SNE) fails to perform clustering on KDD. In Section 4.6, we will make further comprehensive analysis. In addition, we visualized the classification results on synthetic data sets. Figure 6 shows the classification results on Aggregation ans S2.Figure 6
The visualization of classification results on aggregation (a) and S2 (b).


### 4.4. Experimental Results of Running Time

In this subsection, we further verify that our proposed method can effectively reduce the computational overhead. We select data sets with more than 2000 data points and record the running time in Table5.Table 5
The comparison of running time on Segment, Waveform, Landsat, and S2 (unit: seconds).
AlgorithmData setsSegmentWaveformLandsatS2KDDQMC-DPC (PCA)17.737 475.160 128.773 881.083 1341.018 2QMC-DPC (AE)17.563 482.874 130.359 880.144 5368.837 1QMC-DPC (t-SNE)26.369 4115.627 143.406 8124.259 4—DPC40.241 1302.698 358.336 1252.817 5—SNN-DPC279.264 71305.837 4208.851 81208.926 8—AP261.218 3903.003 6144.370 3819.570 3—The bold values mean the best results.As shown in Table5, compared with DPC, SNN-DPC, and AP, QMC-DPC achieves the best performance in terms of running time. QMC-DPC is at least 34.47%, 61.80%, 25.59%, and 50.85% lower than DPC on Segment, Waveform, Landsat, and s2, respectively. Generally speaking, the larger the data size, the more the time saved. For KDD, QMC-DPC (PCA) and QMC-DPC (AE) obtain the results, while QMC-DPC (t-SNE) will exceed memory. This is limited by the t-SNE method. In addition, DPC, SNN-DPC, and AP also exceed memory. This further confirms the effectiveness of our method. How to select QMC-DPC (PCA), QMC-DPC (AE), and QMC-DPC (t-SNE) will be discussed in Section 4.6. In addition, it can be seen that the running time of the QMC-DPC (PCA) and QMC-DPC (AE) is close. However, the computational overhead of QMC-DPC (t-SNE) is higher than that of QMC-DPC (PCA) and QMC-DPC (AE). The reason is that t-SNE requires a huge computational overhead, while auto-encoder only has a shallow structure and does not contain a large number of training parameters. Furthermore, we compare the time complexity of our proposed method with that of the baselines methods. The results are recorded in Table 6. In this part, we set the number of data points to n, the number of cluster categories to k, the number of neighbors to m, the number of iteration to t, and the number of selected Quasi-Monte Carlo points to N. Although the time complexity of QMC-DPC is square, N is much smaller than n in practice. Hence, the time overhead of QMC-DPC will be significantly reduced and the conclusion can also be proved in Table 5.Table 6
The comparison of time complexity.
AlgorithmTime complexityQMC-DPCOn×N+N2DPC-KNN-PCAOn2DLORE-DPOnlognSNN-DPCOm+kn2DPCOn2DBSCANOnlogn∼On2APOn3K-meansOnkt


### 4.5. Experimental Results of Sensitivity Analysis

In this section, we conduct parameter sensitivity analysis from multiple aspects, such as how feature dimensions affect model performance and running time. Specifically, we first calculate Acc, F, NMI, and ARI on UCI data sets where the feature dimension is in the range [16, 24]. The final results are recorded in Tables 7–10, respectively.Table 7
The comparison of Acc on UCI data sets.
Data setsDimensionAlgorithmQMC-DPC (PCA)QMC-DPC (AE)QMC-DPC (t-SNE)Iris20.8600.8830.90630.8600.8130.91340.8430.8390.829Wine20.5280.5160.58830.5620.5560.58940.5620.5560.519Segment20.6810.6160.61030.5440.6020.51940.6140.6150.631Wpbc20.7150.7790.68130.6840.5150.54140.7230.5300.589Waveform20.5650.5610.47930.3860.3330.38040.5220.4950.472Breast20.4720.5050.52330.5230.4690.61040.5270.5680.419Landsat20.6130.6960.60130.5800.6240.58240.6300.6180.612Pima20.6900.6340.39030.6530.5540.65240.6350.6770.638Zoo20.6930.6840.71230.7010.6530.70440.6870.6210.695Table 8
The comparison of F on UCI data sets.
Data setsDimensionAlgorithmQMC-DPC (PCA)QMC-DPC (AE)QMC-DPC (t-SNE)Iris20.7600.7850.89530.7830.7090.94740.7560.7420.595Wine20.6480.6110.66130.6140.6100.50040.5870.6450.578Segment20.6110.5780.52530.4230.3010.41240.3470.3230.356Wpbc20.6990.5730.67230.6320.5640.57640.7330.5620.569Waveform20.5950.5340.47930.5150.5040.52340.4980.5130.630Breast20.6440.6390.65430.5400.5460.63940.5390.5780.598Landsat20.5290.6110.54330.4750.5910.55340.5510.5030.517Pima20.7350.7580.68730.7120.7110.62640.5870.7130.599Zoo20.7920.7890.81330.8010.7740.76340.7650.7520.698Table 9
The comparison of NMI on UCI data sets.
Data setsDimensionAlgorithmQMC-DPC (PCA)QMC-DPC (AE)QMC-DPC (t-SNE)Iris20.6770.7870.77130.7830.7090.94740.7090.7030.362Wine20.5230.5580.51730.4370.4350.24840.3770.4700.384Segment20.7510.6120.52930.3210.2960.46840.0130.3240.343Wpbc20.0360.0530.02730.0180.0120.02340.7330.5620.569Waveform20.4260.3960.32330.5150.5040.52340.2070.3680.431Breast20.0730.0620.06830.0490.0180.05840.0210.0180.039Landsat20.5310.5900.55530.4300.5980.60540.4920.5390.458Pima20.0610.0040.00730.0020.0010.00240.0350.0400.005Zoo20.8110.7960.82230.7840.7350.78640.7620.7130.722Table 10
The comparison of ARI on UCI data sets.
Data setsDimensionAlgorithmQMC-DPC (PCA)QMC-DPC (AE)QMC-DPC (t-SNE)Iris20.7420.7710.76230.6700.5290.92240.5600.5630.266Wine20.3450.4060.67130.3180.2920.14940.2880.3800.353Segment20.5390.5620.43930.1030.1290.29540.0020.1290.197Wpbc20.0420.0220.0223−0.040−0.0080.02840.030−0.000−0.018Waveform20.3000.3010.33630.2670.2550.27340.1550.2630.437Breast20.0730.0620.0683−0.001−0.004−0.0034−0.000−0.001−0.022Landsat20.4280.5280.45130.2850.4880.46140.4210.3820.370Pima20.1240.0220.02730.0100.0080.06440.0760.0590.024Zoo20.8080.7960.80330.7740.7220.78540.7650.6840.752From Tables7 to 10, it can be seen that the performance of the model will decrease slightly with the increase of dimension on the whole. This is limited by the loss of information caused by the sampling strategy as the dimension increases. As the dimensions increase, data distribution will become more complex. To address this issue, there are two methods to reduce the information loss caused by sampling: (1) increase the number of Quasi-Monte Carlo points and (2) appropriately increase the radius r of the circular data unit. If we adopt the first method, the time complexity of QMC-DPC in generating and storing Quasi-Monte Carlo points is ON0, which increases the time and space overhead i as the number of Quasi-Monte Carlo points increases. If the second method is adopted, the selection of radius r is very important. When r is too large and contains the entire data set, the QMC-DPC does not perform sampling operation. Since the main purpose of this paper is to reduce the time overhead of DPC, we give priority to the second method.In addition, we further study the impact of feature dimension on model performance and running time, where the feature dimension is extended to [2, 9]. In this part, KDD is selected and the results are shown in Figure 7. As shown in Figure 7, QMC-DPC (AE) and QMC-DPC (PCA) achieve high performance in terms of SC. On the contrary, QMC-DPC (AE) and QMC-DPC (PCA) have a poor value in terms of CH when the feature dimension is 7. However, the value of CH increases heavily when the feature dimension is 9. The reason is that when we generate more Quasi-Monte Carlo points to execute sampling strategy, the corresponding running time also increases to a great extent. The relevant parameters on KDD are recorded in Table 11.Figure 7
Clustering results of KDD under different feature dimensions. (a) The value of SC on KDD. (b) The value of CH on KDD. (c) The value of time on KDD.
(a)(b)(c)Table 11
Parameter settings on KDD.
Feature dimension23456789r0.350.550.550.650.550.550.650.65N030003000500060008800900012 00025 000


### 4.6. Algorithm Summary

Based on the above experiments, we have a comprehensive discussion on QMC-DPC. Specifically, as shown in Tables2 and 4, it can be found that QMC-DPC achieves the best performance on the whole. On the UCI data sets, QMC-DPC (PCA), QMC-DPC (AE), and QMC-DPC (t-SNE) obtain the highest values of 8, 7, and 9 times, respectively. On the unlabeled data sets, QMC-DPC (PCA), QMC-DPC (AE), and QMC-DPC (t-SNE) obtain the highest values of 0, 6, and 3 times, respectively. Obviously, QMC-DPC combined with nonlinear feature reduction methods achieves better performance, on the whole. In terms of running time, it is obvious that our proposed method has superior performance. Especially when dealing with a large-scale data set, such as KDD, QMC-DPC achieves good performance, while most other baselines cannot be executed due to being out of memory. This further verifies the effectiveness of our method. From Section 4.5, we can find that the feature dimension has an impact on the model performance and various evaluation criteria are affected differently. In general, the model performance will decrease as the feature dimension increases. This is due to the loss of information caused by sampling. In Section 4.5, we propose two methods to overcome this problem, including generating more Quasi-Monte Carlo points and increasing the radius r. The purpose of both methods is to expand the sampling area. For our proposed method, we make a trade-off between running time and model performance, which generates fewer Quasi-Monte Carlo points and sets fewer iterations for t-SNE and AE. The above operations will reduce the running time while reducing the model performance. In particular, we also increase the radius r to reduce the information loss.We summarize the following views on QMC-DPC:(i)
In general, we choose QMC-DPC combined with nonlinear feature reduction methods, such as QMC-DPC (AE) and QMC-DPC (t-SNE). When dealing with a large-scale data set, we prefer QMC-DPC (AE).(ii)
To reduce information loss, we give priority to expanding the radiusr. Secondly, we consider adding Quasi-Monte Carlo points.In addition, there are still exploration directions for our proposed algorithm in the future, which are summarized as follows:(i)
How to select feature dimensions is a heuristic work. In future work, we hope to build a multi-layer auto-encoder and construct the loss function based on hidden layer features. We aim to design the automatic encoder as a multi-tasks neural network.(ii)
We hope to propose a more comprehensive sampling method to reduce the loss of information. We can take the sample point itself as the center for sampling, and then filter out the data samples in the sparse area. Finally, we need to have a strategy for the classification of outliers.(iii)
We hope to propose a more comprehensive sampling method to reduce the loss of information. We can take the sample point itself as the center for sampling, and then filter out the data samples in the sparse area. Finally, we need to have a strategy for the classification of outliers.


## 4.1. Experimental Setup

To verify the performance of QMC-DPC, the proposed method is compared with related clustering algorithms, including DPC-KNN-PCA [17], SNN-DPC [18], DLORE-DP [16], DPC [5], AP [4], DBSCAN [3], and K-means [2]. The nearest neighbor number is set to 4 in SNN-DPC. The ratio of low-density points in DLORE-DP is set to 0.2. For DBSCAN, the parameter Min Pts is set to 3 and ε is empty. K-means needs to specify the number of classes in advance. The data sets adopted in this section include two major categories: unlabeled data sets and labeled data sets. The details of these data sets are listed in Table 1. In labeled data sets, all data sets are UCI data sets. In unlabeled data sets, Flame, Aggregation, and S2 are Synthetic data sets. KDD is a biological data set, which is used to verify the superiority of our proposed algorithm on large-scale and high-dimensional feature data sets.Table 1
The unlabeled data sets and labeled data sets.
Data setSamplesAttributesCategoriesSourceUnlabeled data setsFlame24023[29]Aggregation78827[31]S25000215[32]KDD145 751742000[33]Labeled data setsIris15043[30]Wine178133[30]Segment2310187[30]Waveform5000213[30]Wpbc198332[30]Breast27792[30]Landsat2000369[30]Pima76882[30]Zoo101167[30]Four evaluation criteria are adopted to evaluate the model performance on labeled data sets, i.e, the Accuracy (Acc) and F-measure (F), Normalized mutual information (NMI), and Adjusted rand index (ARI). These evaluation criteria are described as follows: Assume thatX=x1,x2,…,xn is the data set. Y=y1,y2,…,yn and Y˜=y˜1,y˜2,…,y˜n represent the real labels and the predicted labels, respectively. Acc is denoted as(7)Acc=∑i=1nδyi,mapy˜in,where map. is a permutation mapping function, which uses Hungarian algorithm to match the predicted labels with the real labels.The F-measure is a harmonic mean of precisionprec and recall rec. Prec is the ratio between the number of correct positive results and the number of all positive results returned by the classifier. Rec is the ratio between the number of correct positive results and the number of all data that should have been identified as positive. Ui is the set of the number of all data that should have been classified as positive. Vj is the set of the number of all positive results identified by the classifier. Prec, Rec, and F-measure are defined by the following equations:(8)precUi,Vj=Ui∩VjVj,recUi,Vj=Ui∩VjUj,(9)FUi,Vj=β2+1prec⋅recβ2prec+rec,where β is a nonnegative real number that is set to 1. For the Ui divided by each real label, the nearest one in Vj is selected as its F value:(10)FUi=max1≤j≤CFUi,Vj.Then, we use the weighted average ofFUi to get the final F value:(11)F=∑i=1Rωi⋅FUi,ωi=Uin.The Normalized Mutual Information (NMI) measures the information that the predicted labelsY˜ share with the ground truth Y. NMI is defined as the following equation:(12)NMI=IY˜,YHY˜HY,where IY˜,Y is the mutual information between clustering result and ground truth. HY˜ and HY denote the entropy of clustering result and ground truth, respectively.The Adjusted Rand Index (ARI) is the extension of Rand Index (RI). ARI is defined as the following equation:(13)ARI=RI−ERImaxRI−ERI,where RI=uv+uv¯/uv+uv¯+u¯v+uv¯, uv denotes the data pairs which are in the same class in U and in the same class in V, uv¯ denotes the data pairs which are in different classes in U and in different classes in V. u¯v denotes the data pairs which are in different classes in U and in the same class in V. uv¯ denotes the data pairs which are in the same class in U and in different classes in V. The value of ARI is in the range [− 1, 1]. The upper bound of these evaluation criterions is 1. The larger these criterions are, the better the clustering results are.In the feature reduction module, some parameters are set in advance. For t-SNE, the learning rate is 500, the number of perplexity is 30, and the number of epochs is 800. For AE, the learning rate is 0.01, optimizer is Adam, and the number of epochs is 300.


## 4.2. Experimental Results on Labeled Data Sets

In this section, 9 UCI data sets in Table1 are used to verify the performance of QMC-DPC. All data are normalized to between [0, 1]. To avoid extreme cases, each algorithm runs 10 times and records the average results. The values of evaluation criteria are shown in Table 2 and the best values are highlighted in bold. The relevant parameters of the QMC-DPC are recorded in Table 3.Table 2
The comparison of all algorithms in terms of Acc, F, NMI, and ARI on UCI data sets.
AlgorithmAccFNMIARIAccFNMIARIAccFNMIARIIrisWineSegmentQMC-DPC (PCA)0.8600.7600.6770.7420.5280.6480.5230.3450.6810.6110.7510.539QMC-DPC (AE)0.8830.7850.7870.7710.5160.6110.5880.4060.6160.5780.6120.562QMC-DPC (t-SNE)0.9060.7950.7300.7620.5880.6610.5170.6710.6100.5250.5290.439DPC-KNN-PCA0.0460.6260.6200.4670.4180.5620.4790.2340.6430.3770.4820.539DLORE-DP0.7900.7980.7770.7440.5370.5860.5780.1780.6310.4750.5490.540SNN-DPC0.6000.7400.6890.5570.4420.5680.526−0.0050.6170.3740.0160.429DPC0.8860.7850.7830.7190.4650.6100.4860.3530.6170.5340.7010.539DBSCAN0.6800.7750.7330.5680.3310.5770.009−0.0020.4420.3770.4310.227AP0.8070.7690.6180.3760.4280.4600.5260.2680.6700.3280.5860.502K-means0.6670.6990.5930.5140.3610.5890.4780.3840.6430.5720.6250.493WpbcWaveformBreastQMC-DPC (PCA)0.7150.6990.0360.0420.5220.4980.2070.1550.4720.6440.0730.017QMC-DPC (AE)0.7790.5730.0530.0220.4950.5130.3680.2630.5050.6390.0620.017QMC-DPC (t-SNE)0.6810.6720.0270.0220.4720.6300.4310.4370.5230.6540.0680.014DPC-KNN-PCA0.7620.7970.0150.0120.5060.5610.2600.2470.2850.7640.0270.020DLORE-DP0.6730.6500.020−0.0610.5950.5870.3820.3330.3030.7410.0520.004SNN-DPC0.7520.7860.019−0.0130.3750.5300.0680.0160.2130.6850.0710.016DPC0.6420.6910.015−0.0070.2220.5460.2170.2160.5160.5410.0000.004DBSCAN0.7520.7860.009−0.0130.3310.5770.0000.0250.3530.4380.0590.015AP0.4150.2210.0250.0050.2130.1050.2310.0160.0860.1780.0590.012K-means0.5500.5670.0290.0030.3140.5080.3740.2590.4910.5380.0410.003LandsatPimaZooQMC-DPC (PCA)0.6300.5510.4920.4210.6900.7350.0610.1240.6930.7920.8110.808QMC-DPC (AE)0.6180.5030.5390.3820.6340.7580.0040.0220.6840.7890.7960.796QMC-DPC (t-SNE)0.6120.5170.4580.3700.3900.6870.0070.0270.7120.8130.8220.803DPC-KNN-PCA0.6170.4560.3810.1410.3470.7380.0040.0020.5890.7860.6890.731DLORE-DP0.6350.5460.5400.3580.3520.7090.0020.0110.0290.7390.6900.644SNN-DPC0.5170.4630.2670.0890.6510.7360.0000.0010.0490.8560.8310.713DPC0.6360.5730.5470.4110.3470.7380.0040.0020.3760.3520.3480.076DBSCAN0.5060.4300.0000.0000.3430.7330.0020.0050.6930.7920.7610.691AP0.1040.3270.5040.1870.0100.1590.0790.0170.2670.7580.7920.573K-means0.5650.6470.5480.4690.6220.5590.0280.0540.6740.7120.7430.633The bold values mean the best results.Table 3
Parameter settings on all data sets.
Data setsIrisWineSegmentWpbcWaveformBreastLandsatPimaZooKDDFlameAggregationS2Feature dimension2222424223222r0.350.550.450.350.450.250.400.200.450.350.400.400.35N020020020001500250070020001700180500040010002500As shown in Table2, our proposed algorithm is superior to other algorithms on the whole. Acc indicates the ratio of the number of correct predicted samples to the number of total samples. In terms of Acc, QMC-DPC achieves the highest performance on all data sets except Waveform and Landsat. In particular, QMC-DPC is 33.6% and 34.3% higher than DPC on Zoo and Pima, respectively. F-measure indicates the matching degree between the predicted labels and the true labels of the data set, which is the weighted harmonic mean of precision and recall. In terms of F-measure, QMC-DPC achieves the highest performance on nearly half the data set. NMI quantifies the similarity between the predicted labels and the true labels, which measures the robustness of the algorithm. In terms of NMI, QMC-DPC achieves the highest performance on all data sets except Landsat, Pima, and Zoo. In particular, QMC-DPC is 21.4% higher than DPC on Waveform. ARI is used to measure the degree of coincidence of the two data distributions. In terms of ARI, QMC-DPC achieves the highest performance on all data sets except Breast and Landsat. The ARI value of QMC-DPC is 73.2% higher than DPC on Zoo. In addition, the evaluation criterion values of QMC-DPC (PCA), QMC-DPC (AE), and QMC-DPC (t-SNE) are similar, and the model performance is better than that of DPC on the whole. The above results indicate that the combination of the feature reduction module and the feature sampling module can improve the model performance.


## 4.3. Experimental Results of Unlabeled Data Sets

Since there are no real labels for the unlabeled data sets, the evaluation criteria Acc, F-measure, NMI, and ARI cannot be applied to the unlabeled data sets. To compare the performance on the unlabeled data sets, the evaluation criteria Silhouette Coefficient (SC) and Calinski-Harabasz (CH) are defined. For SC, we first calculate the silhouette coefficient for each data pointi:(14)si=bi−aimaxai,bi,where ai is average dissimilarity between data point i and other data points in the same class, bi is the minimum value of the average dissimilarity between data point i and other categories. Next, we obtain the silhouette coefficient for data set based on si:(15)SC=1n∑i=1nsi,where n is the number of all data points. The value of SC is in the range [−1, 1]. The larger the SC value is, the better the clustering result is.CH is defined as follows:(16)CH=traceB/k−1traceW/k−n,where traceB=∑i=1nniui−u2, ni is the number of data points in class i, ui is the average of data points in class i, and u is the average of all data points. traceW=∑j=1k∑i=1nxi−uj2, k is the cluster numbers. The larger the CH value is, the better the clustering result is.In this section, three synthetic data sets and KDD are selected to verify the performance of QMC-DPC. Flame, Aggregation, and S2 are the classical synthetic data sets. KDD is a large-scale data set with high-dimensional features. Table4 shows the SC and CH of all algorithms on unlabeled data sets. The best values are highlighted in bold. The relevant parameters of the QMC-DPC are recorded in Table 3.Table 4
The comparison of all algorithms in terms of SC and CH on unlabeled data sets.
AlgorithmFlameAggregationS2KDDSCCHSCCHSCCHSCCHQMC-DPC (PCA)0.379153.6720.4611032.8760.45215 011.7490.941 537 569.031 7QMC-DPC (AE)0.303129.0280.4931202.9340.71019 744.3530.944 945 484.132 6QMC-DPC (t-SNE)0.409190.9380.4931202.9340.70419 149.117——DPC-KNN-PCA0.403178.2170.281329.0730.71019 744.353——DLORE-DP0.323108.2440.463883.7130.61117 689.904——SNN-DPC0.13237.0090.363851.9530.0021124.993——DPC0.347133.6150.4931202.9340.71019 744.353——DBSCAN0.2956.8940.318606.2850.5293178.6350.22918 701.700AP0.334247.0170.421660.4220.49617 747.519——K-means0.24580.4060.425967.3940.5397293.5330.69413 042.686The bold values mean the best results.As shown in Table4, our proposed method obtains the best clustering results on the whole, especially QMC-DPC (AE). The “—” in Table 4 indicates that the algorithm cannot execute because it exceeds the virtual memory. For the SC, QMC-DPC (t-SNE) is higher than DPC on Flame. And, DPC obtains the same results as our proposed method on Aggregation and S2. DPC-KNN-PCA also obtains the same results as our proposed method on S2. In general, QMC-DPC (AE) and QMC-DPC (t-SNE) achieve the better performance than QMC-DPC (PCA) except KDD. Limited by the t-SNE method, QMC-DPC (t-SNE) fails to perform clustering on KDD. In Section 4.6, we will make further comprehensive analysis. In addition, we visualized the classification results on synthetic data sets. Figure 6 shows the classification results on Aggregation ans S2.Figure 6
The visualization of classification results on aggregation (a) and S2 (b).


## 4.4. Experimental Results of Running Time

In this subsection, we further verify that our proposed method can effectively reduce the computational overhead. We select data sets with more than 2000 data points and record the running time in Table5.Table 5
The comparison of running time on Segment, Waveform, Landsat, and S2 (unit: seconds).
AlgorithmData setsSegmentWaveformLandsatS2KDDQMC-DPC (PCA)17.737 475.160 128.773 881.083 1341.018 2QMC-DPC (AE)17.563 482.874 130.359 880.144 5368.837 1QMC-DPC (t-SNE)26.369 4115.627 143.406 8124.259 4—DPC40.241 1302.698 358.336 1252.817 5—SNN-DPC279.264 71305.837 4208.851 81208.926 8—AP261.218 3903.003 6144.370 3819.570 3—The bold values mean the best results.As shown in Table5, compared with DPC, SNN-DPC, and AP, QMC-DPC achieves the best performance in terms of running time. QMC-DPC is at least 34.47%, 61.80%, 25.59%, and 50.85% lower than DPC on Segment, Waveform, Landsat, and s2, respectively. Generally speaking, the larger the data size, the more the time saved. For KDD, QMC-DPC (PCA) and QMC-DPC (AE) obtain the results, while QMC-DPC (t-SNE) will exceed memory. This is limited by the t-SNE method. In addition, DPC, SNN-DPC, and AP also exceed memory. This further confirms the effectiveness of our method. How to select QMC-DPC (PCA), QMC-DPC (AE), and QMC-DPC (t-SNE) will be discussed in Section 4.6. In addition, it can be seen that the running time of the QMC-DPC (PCA) and QMC-DPC (AE) is close. However, the computational overhead of QMC-DPC (t-SNE) is higher than that of QMC-DPC (PCA) and QMC-DPC (AE). The reason is that t-SNE requires a huge computational overhead, while auto-encoder only has a shallow structure and does not contain a large number of training parameters. Furthermore, we compare the time complexity of our proposed method with that of the baselines methods. The results are recorded in Table 6. In this part, we set the number of data points to n, the number of cluster categories to k, the number of neighbors to m, the number of iteration to t, and the number of selected Quasi-Monte Carlo points to N. Although the time complexity of QMC-DPC is square, N is much smaller than n in practice. Hence, the time overhead of QMC-DPC will be significantly reduced and the conclusion can also be proved in Table 5.Table 6
The comparison of time complexity.
AlgorithmTime complexityQMC-DPCOn×N+N2DPC-KNN-PCAOn2DLORE-DPOnlognSNN-DPCOm+kn2DPCOn2DBSCANOnlogn∼On2APOn3K-meansOnkt


## 4.5. Experimental Results of Sensitivity Analysis

In this section, we conduct parameter sensitivity analysis from multiple aspects, such as how feature dimensions affect model performance and running time. Specifically, we first calculate Acc, F, NMI, and ARI on UCI data sets where the feature dimension is in the range [16, 24]. The final results are recorded in Tables 7–10, respectively.Table 7
The comparison of Acc on UCI data sets.
Data setsDimensionAlgorithmQMC-DPC (PCA)QMC-DPC (AE)QMC-DPC (t-SNE)Iris20.8600.8830.90630.8600.8130.91340.8430.8390.829Wine20.5280.5160.58830.5620.5560.58940.5620.5560.519Segment20.6810.6160.61030.5440.6020.51940.6140.6150.631Wpbc20.7150.7790.68130.6840.5150.54140.7230.5300.589Waveform20.5650.5610.47930.3860.3330.38040.5220.4950.472Breast20.4720.5050.52330.5230.4690.61040.5270.5680.419Landsat20.6130.6960.60130.5800.6240.58240.6300.6180.612Pima20.6900.6340.39030.6530.5540.65240.6350.6770.638Zoo20.6930.6840.71230.7010.6530.70440.6870.6210.695Table 8
The comparison of F on UCI data sets.
Data setsDimensionAlgorithmQMC-DPC (PCA)QMC-DPC (AE)QMC-DPC (t-SNE)Iris20.7600.7850.89530.7830.7090.94740.7560.7420.595Wine20.6480.6110.66130.6140.6100.50040.5870.6450.578Segment20.6110.5780.52530.4230.3010.41240.3470.3230.356Wpbc20.6990.5730.67230.6320.5640.57640.7330.5620.569Waveform20.5950.5340.47930.5150.5040.52340.4980.5130.630Breast20.6440.6390.65430.5400.5460.63940.5390.5780.598Landsat20.5290.6110.54330.4750.5910.55340.5510.5030.517Pima20.7350.7580.68730.7120.7110.62640.5870.7130.599Zoo20.7920.7890.81330.8010.7740.76340.7650.7520.698Table 9
The comparison of NMI on UCI data sets.
Data setsDimensionAlgorithmQMC-DPC (PCA)QMC-DPC (AE)QMC-DPC (t-SNE)Iris20.6770.7870.77130.7830.7090.94740.7090.7030.362Wine20.5230.5580.51730.4370.4350.24840.3770.4700.384Segment20.7510.6120.52930.3210.2960.46840.0130.3240.343Wpbc20.0360.0530.02730.0180.0120.02340.7330.5620.569Waveform20.4260.3960.32330.5150.5040.52340.2070.3680.431Breast20.0730.0620.06830.0490.0180.05840.0210.0180.039Landsat20.5310.5900.55530.4300.5980.60540.4920.5390.458Pima20.0610.0040.00730.0020.0010.00240.0350.0400.005Zoo20.8110.7960.82230.7840.7350.78640.7620.7130.722Table 10
The comparison of ARI on UCI data sets.
Data setsDimensionAlgorithmQMC-DPC (PCA)QMC-DPC (AE)QMC-DPC (t-SNE)Iris20.7420.7710.76230.6700.5290.92240.5600.5630.266Wine20.3450.4060.67130.3180.2920.14940.2880.3800.353Segment20.5390.5620.43930.1030.1290.29540.0020.1290.197Wpbc20.0420.0220.0223−0.040−0.0080.02840.030−0.000−0.018Waveform20.3000.3010.33630.2670.2550.27340.1550.2630.437Breast20.0730.0620.0683−0.001−0.004−0.0034−0.000−0.001−0.022Landsat20.4280.5280.45130.2850.4880.46140.4210.3820.370Pima20.1240.0220.02730.0100.0080.06440.0760.0590.024Zoo20.8080.7960.80330.7740.7220.78540.7650.6840.752From Tables7 to 10, it can be seen that the performance of the model will decrease slightly with the increase of dimension on the whole. This is limited by the loss of information caused by the sampling strategy as the dimension increases. As the dimensions increase, data distribution will become more complex. To address this issue, there are two methods to reduce the information loss caused by sampling: (1) increase the number of Quasi-Monte Carlo points and (2) appropriately increase the radius r of the circular data unit. If we adopt the first method, the time complexity of QMC-DPC in generating and storing Quasi-Monte Carlo points is ON0, which increases the time and space overhead i as the number of Quasi-Monte Carlo points increases. If the second method is adopted, the selection of radius r is very important. When r is too large and contains the entire data set, the QMC-DPC does not perform sampling operation. Since the main purpose of this paper is to reduce the time overhead of DPC, we give priority to the second method.In addition, we further study the impact of feature dimension on model performance and running time, where the feature dimension is extended to [2, 9]. In this part, KDD is selected and the results are shown in Figure 7. As shown in Figure 7, QMC-DPC (AE) and QMC-DPC (PCA) achieve high performance in terms of SC. On the contrary, QMC-DPC (AE) and QMC-DPC (PCA) have a poor value in terms of CH when the feature dimension is 7. However, the value of CH increases heavily when the feature dimension is 9. The reason is that when we generate more Quasi-Monte Carlo points to execute sampling strategy, the corresponding running time also increases to a great extent. The relevant parameters on KDD are recorded in Table 11.Figure 7
Clustering results of KDD under different feature dimensions. (a) The value of SC on KDD. (b) The value of CH on KDD. (c) The value of time on KDD.
(a)(b)(c)Table 11
Parameter settings on KDD.
Feature dimension23456789r0.350.550.550.650.550.550.650.65N030003000500060008800900012 00025 000


## 4.6. Algorithm Summary

Based on the above experiments, we have a comprehensive discussion on QMC-DPC. Specifically, as shown in Tables2 and 4, it can be found that QMC-DPC achieves the best performance on the whole. On the UCI data sets, QMC-DPC (PCA), QMC-DPC (AE), and QMC-DPC (t-SNE) obtain the highest values of 8, 7, and 9 times, respectively. On the unlabeled data sets, QMC-DPC (PCA), QMC-DPC (AE), and QMC-DPC (t-SNE) obtain the highest values of 0, 6, and 3 times, respectively. Obviously, QMC-DPC combined with nonlinear feature reduction methods achieves better performance, on the whole. In terms of running time, it is obvious that our proposed method has superior performance. Especially when dealing with a large-scale data set, such as KDD, QMC-DPC achieves good performance, while most other baselines cannot be executed due to being out of memory. This further verifies the effectiveness of our method. From Section 4.5, we can find that the feature dimension has an impact on the model performance and various evaluation criteria are affected differently. In general, the model performance will decrease as the feature dimension increases. This is due to the loss of information caused by sampling. In Section 4.5, we propose two methods to overcome this problem, including generating more Quasi-Monte Carlo points and increasing the radius r. The purpose of both methods is to expand the sampling area. For our proposed method, we make a trade-off between running time and model performance, which generates fewer Quasi-Monte Carlo points and sets fewer iterations for t-SNE and AE. The above operations will reduce the running time while reducing the model performance. In particular, we also increase the radius r to reduce the information loss.We summarize the following views on QMC-DPC:(i)
In general, we choose QMC-DPC combined with nonlinear feature reduction methods, such as QMC-DPC (AE) and QMC-DPC (t-SNE). When dealing with a large-scale data set, we prefer QMC-DPC (AE).(ii)
To reduce information loss, we give priority to expanding the radiusr. Secondly, we consider adding Quasi-Monte Carlo points.In addition, there are still exploration directions for our proposed algorithm in the future, which are summarized as follows:(i)
How to select feature dimensions is a heuristic work. In future work, we hope to build a multi-layer auto-encoder and construct the loss function based on hidden layer features. We aim to design the automatic encoder as a multi-tasks neural network.(ii)
We hope to propose a more comprehensive sampling method to reduce the loss of information. We can take the sample point itself as the center for sampling, and then filter out the data samples in the sparse area. Finally, we need to have a strategy for the classification of outliers.(iii)
We hope to propose a more comprehensive sampling method to reduce the loss of information. We can take the sample point itself as the center for sampling, and then filter out the data samples in the sparse area. Finally, we need to have a strategy for the classification of outliers.


## 5. Conclusion

In this paper, a new density peaks clustering algorithm with high computational efficiency is proposed. The original feature space is compressed by different feature reduction methods. We sample the reduced feature space based on the super-uniformly distributed sequence generated by the Quasi-Monte Carlo method. Our work can effectively overcome the high computation overhead of DPC while improving the model performance. Theoretically, the time complexity can be reduced fromon2 to oNn, where N≪n. The experimental results show that QMC-DPC improves the model performance of the DPC while greatly reducing the time overhead with the increase of data set size.



---

*Source: 8046620-2022-01-06.xml*