# RFDPC: Density Peaks Clustering Algorithm Based on Resultant Force

Authors: Yongzhong Zhang; Hexiao Huang; Jie Du; Yan Ma
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

Density peaks clustering (DPC) is an efficient and effective algorithm due to its outstanding performance in discovering clusters with varying densities. However, the quality of this method is highly dependent on the cutoff distance. To improve the performance of DPC, the gravitation-based clustering (GDPC) algorithm is proposed. However, it cannot identify the clusters of varying densities. We developed a novel density peaks clustering algorithm based on the magnitude and direction of the resultant force acting on a data point (RFDPC). RFDPC is based on the idea that the resultant forces acting on the data points in the same cluster are more likely to point towards the cluster center. The cluster centers are selected based on the force directional factor and distance in the decision graph. Experimental results indicate superior performance of the proposed algorithm in detecting clusters of different densities, irregular shapes, and numbers of clusters.


---

## Body

## 1. Introduction

The main goal of clustering is to divide a data set into groups of data points so that the points within the same group are close to one another and those from different groups are distinct [1]. Clustering is widely used in many fields, such as image analysis, medical applications, data mining, and bioinformatics [2–5]. In general, the clustering algorithms can be categorized as partitional clustering [6], density-based clustering [7], hierarchical clustering [8], model-based clustering [9], grid-based clustering [10], and graph-based clustering [11].K-means algorithm partitions data into k clusters by iteratively minimizing the sum of distances between each data point and the cluster center [12]. Nevertheless, as a result of its sensitivity to the initial cluster centers, this algorithm may reach local optimum. In terms of density-based clustering, DBSCAN is one of the most widely adopted algorithms, which can discover arbitrarily shaped clusters using neighboring relationships among data points [13]. However, the choice of the density threshold has a significant impact on this algorithm.Rodriguez and Laio proposed a fast clustering algorithm that employs the density peaks of the data (DPC) [14]. In this algorithm, it is assumed that cluster centers will have a higher density than their neighbors and that the cluster centers will be relatively far from points with a higher density. DPC can detect cluster centers rapidly and recognize certain types of shaped data sets. However, DPC cannot detect clusters with no obvious center, and the cutoff distance impacts the performance. The clustering results of DPC on the two-circles data sets [1] are shown in Figure 1, where dc is the cutoff distance. We can see from Figure 1 that DPC cannot detect two-circles correctly when the cutoff distance dc is set as 0.1 and 1.21, respectively.Figure 1
Clustering results of DPC on the two-circles data set. (a)dc = 0.1. (b) dc = 1.21.
(a)(b)Numerous methods have been proposed to improve the DPC algorithm [15–18]. A residual error computation has been proposed by Parmar et al. [19] to measure local density in a neighborhood region. Guo et al. [20] proposed an improved DPC algorithm (DPC-CE) to estimate the local center connectivity. Wang et al. [21] developed a hierarchical density peak clustering algorithm McDPC that assumes that cluster centers are relatively far apart from one another. A new model by Wang et al. [22] illustrates the local gravitational effects of data points, where each data point is viewed as a mass, subject to a local force resulting from its neighbors. A density peaks clustering algorithm using gravity theory (GDPC) has been developed by Jiang et al. [23], which assumes that gravity is inversely proportional to the distance between data points. And the horizontal axis of the decision graph is density, and the vertical axis is the reciprocal of gravity. GDPC can discover outliers. However, this algorithm is challenged when clustering a data set with a wide variation in density among the clusters.Figure2 shows the clustering results of GDPC, where the cluster centers are represented by green stars. As shown in Figure 2(a), GDPC can identify the clusters with similar densities. But GDPC cannot discover the expected clusters with various densities shown in Figure 2(b). This is mainly because most of the data points in the upper right corner in Figure 2(b) have lower densities than those in the lower-left corner. And the density will affect the determination of the cluster center to a certain extent. So the two cluster centers are located in the same cluster, which leads to wrong clustering results.Figure 2
Clustering results of GDPC on the data set. (a) Clusters with similar densities. (b) Clusters with various densities.
(a)(b)This paper proposes a density peaks clustering algorithm based on the resultant force, called RFDPC. As shown in Table1, in comparison to algorithms such as k-means, DBSCAN, DPC, and GDPC, the proposed RFDPC algorithm has the ability to detect clusters of various densities, irregular shapes, and the number of clusters. Here are our thoughts:(1)
It is highly likely that the resultant forces acting on the data points in the same cluster point towards the cluster center. That is, for the cluster centerci, the resultant forces act on its neighbors towards ci.(2)
The cluster centers are generally located farther from points with higher densities.Table 1
Advantages of RFDPC overk-means, DBSCAN, DPC, and GDPC, where “×” refers to disable, “√” means able, and “∂” is partial.
AlgorithmsVarying densitiesIrregular shapesNumber of clustersk-means∂××DBSCAN∂√∂DPC∂∂∂GDPC∂√∂RFDPC√√√Therefore, it is more likely for a data point to be associated with a cluster center if most resultant forces acting on other points point towards it. In addition, two cluster centers have a larger distance than the points in the same cluster. Thus, the noncentral point can be assigned to its nearest cluster center.The key contributions of this paper are as follows:(1)
A data point can be viewed as a force object, and the resultant force acting on it can determine whether the data point is located near the cluster center.(2)
The clustering centers are selected based on force directional factor and distance in the decision graph.(3)
This paper proposes a clustering algorithm that is less sensitive to the shape or density of clusters.The rest of this paper is organized as follows: in Section2, we review the DPC algorithm. We next present our proposed algorithm in Section 3. The time complexity of the proposed algorithm is analyzed in Section 4. Section 5 discusses the proposed algorithm. Section 6 presents the experimental evaluations. Finally, the conclusion of our work is presented in Section 7.


## 2. Related Works

The DPC algorithm is based on the idea that the cluster centers are surrounded by neighbors with lower density and that they are at a relatively large distance from any point with a higher density. The densityρi of data point i can be defined as(1)ρi=∑jexp−dij2dc2,where dc is the cutoff distance, and dij is the Euclidean distance between points xi and xj.(2)dij=distancei,j.In addition, the densityρi of data point i can also be defined as(3)ρi=∑jχdij−dc,where χdij−dc=1 if dij−dc<0 and χdij−dc=0 otherwise.Letδi be the minimum distance from point xi to any other point with higher density.(4)δi=minj:ρi<ρjdij,ifρi<ρj,maxjdij,otherwise.The decision graph can be obtained after calculating the value ofρi and δi. The cluster centers are determined by selecting the data points with higher values of ρi and δi.DPC suffers many shortcomings such that it cannot identify the clusters of varying densities, as well as the number of clusters. The reason for the problem is that the density of the data point is determined by the cutoff distancedc, which can affect the clustering results. To address this issue, the algorithm proposed in this paper uses the force directional factor γ instead of the density of the data point by analyzing the resultant force acting on the data point.


## 3. Method

The RFDPC algorithm assumes that: (1) All points attract each other with a force of gravitational attraction; (2) The direction of the resultant force acting on a data point is mainly along with the line between the point and the cluster center. (3) The intercluster distance is larger than the intracluster distance. The RFDPC includes three major steps:Step 1: for data pointi, calculate the density ρi, distance δi, and resultant force Fi.Step 2: calculate the angleαij between the vector connecting two points and the resultant force, as well as the force directional factor γi.Step 3: determine the cluster centers and assign each remaining point to its nearest cluster.


### 3.1. Calculate and Sort the Density of Data Point

First, calculate the Euclidean distancedij in equation (2) between two data points i and j. The density of the data point ρi can be calculated according to equations (1) or (3). The choice of cutoff distance dc is presented in Ref. [14], that is, one can choose dc so that the average number of neighbors is about 1 to 2% of the total point number in the data set.Then, all data points are sorted according to their densities in descending order. The distanceδi is calculated from a data point i to any other point with a higher density as determined by equation (2).


### 3.2. Resultant Force Acting on a Data Point

The concept of gravity is introduced on the basis of DPC. Newton’s law of universal gravitation [23] states that any particle in the universe attracts any other with a force varying directly as the product of the masses and inversely as the square of the distance between their centers. The gravitational force is formulated as follows:(5)F=G×m1×m2r2,where G is the gravitational constant, m1 and m2 represent the two masses, r represents the distance between the centers of the masses. Table 2 provides a mapping of Newton’s law of universal gravitation with parameters of DPC.Table 2
A mapping of Newton’s law of universal gravitation with parameters of DPC.
Parameters of gravitationParameters of DPCm1ρim2ρjrdijIn equation (6), the Euclidean distance is used to calculate the gravitational force, which avoids the sensitivity of the algorithm to dc value. The gravitational force F acting between data points i and j is defined as equation (6) according to Table 2.(6)fij=ρi×ρjdij2,where fij is the gravitational force between the data point i and the data point j, whose direction is from i to j.For each data pointi, the gravitational force fij from the other data point j is calculated according to equation (6), and we further obtain the magnitude and direction of the resultant force Fi acting on data point i through decomposing and synthesizing the gravitational forces, as shown in equation.(7)Fi=∑jfij.An example of two-dimensional space is shown in Figure3. Suppose that the data point i is located at the origin of a coordinate system. Two gravitational forces F1 and F2 act on point i. F1 can further be decomposed into a force fx1 along the x axis and a force fy1 along the y axis. Similarly, F2 can also be decomposed into fx2 and fy2. Finally, the resultant force Fi acting on point i is obtained by combining the sum of the components of all forces along the x axis (including fx1 and fx2) and the y axis (including fy1 and fy2).Figure 3
Analysis of the resultant force acting on the data pointi.Figure4 shows the resultant force acting on each data point in Flame data set, where the direction of the arrow represents the direction of the resultant force acting on the data point and the length of the arrow represents the magnitude of the resultant force acting on the data point. As can be seen from Figure 4, most resultant forces point towards the two cluster centers. Meanwhile, the farther away the data point is from the cluster center, the less affected by the cluster center. In addition, the magnitude of resultant force in a higher density area is usually larger. In contrast, the resultant force will have a small magnitude in a lower density area.Figure 4
The magnitude and direction of resultant forces acting on each data point in the flame data set.


### 3.3. Force Directional Factor

Here, a parameterγi is introduced which represents the effect of data point i on the resultant forces acting on all other points. The detailed method is given as follows.Take pointsi and j in Figure 4, for example. For clarity, the points i and j are magnified in Figure 5. As shown in Figure 5, αij represents the angle between the vector ji⟶ connecting point j to point i and the resultant force Fj. And αij is in the range 0,180°. The range of αij can be normalized to [−1, 1] by cosαij, as shown in equation (8). cosαij is equal to 1 when αij is equal to 0, which means that the resultant force Fj acting on j points towards i. The larger the value of αij is, the smaller cosαij is, and the more the direction of resultant force Fj acting on j deviates from the data point i.(8)cosαij=Fj⋅ji⟶Fj||ji⟶.Figure 5
The angleα between the vector connecting point j to point i and the resultant force F.In addition, from Figure4, it can be seen that the resultant force acting on data point k also points towards point i. However, i and k belong to different clusters, which indicates that it will produce the clustering error while only considering cosαij. To address this issue, not only the resultant force should be considered but also the distance between data points. Thus, the parameter γij is defined as(9)γij=cosαijdij.For data pointi, γij is calculated between it and all other points. The force directional factor γi is further defined as follows:(10)γi=∑jγij.A larger value ofγi indicates that the point i has a significant effect on the resultant force acting on the other points. Hence, the point i may be most likely to be a cluster center or located near the cluster center.


### 3.4. Determine the Cluster Centers

For the data pointi near the cluster center, its value of γi will be larger due to the effect of the cluster center. Thus, both of δi and γi can be considered. Therefore, the cluster centers are selected according to the product of δi by γi. Each remaining point is assigned to the same cluster as its nearest neighbor of higher density. Algorithm 1 shows the proposed clustering algorithm based on the resultant force. Figure 6 illustrates the flowchart of RFDPC algorithm.Figure 6
The flowchart of the RFDPC algorithm.Algorithm 1: The clustering algorithm based on the resultant force.
Input: Data set X =  x1,x2,…,xn (n is the number of data points), number of clusters KOutput: A clustering resultStep 1. Calculate the densityρi and the distance δi of each data point i.(1.1)
Calculatedij from X according to equation (3).(1.2)
Determinedc value so that the average number of neighbors is about 1 to 2% of the total point number in the data set.(1.3)
Calculateρi based on equation (1) or equation (4) and sort all ρi in descending order.(1.4)
Calculate the distanceδi according to equation (2).Step 2. Calculate the resultant force acting on the data point.(2.1)
Calculate the gravitational force acting on the data point according to equation (6), and the resultant force according to equation (7).(2.2)
Calculateγi according to equations (9) and (10).Step 3. Determine the cluster center.(3.1)
Select the K cluster centers according to the product ofδi by γi, that is, the cluster center is selected from the data points with larger product values.(3.2)
Each remaining point is assigned to the same cluster as its nearest neighbor with higher density.


## 3.1. Calculate and Sort the Density of Data Point

First, calculate the Euclidean distancedij in equation (2) between two data points i and j. The density of the data point ρi can be calculated according to equations (1) or (3). The choice of cutoff distance dc is presented in Ref. [14], that is, one can choose dc so that the average number of neighbors is about 1 to 2% of the total point number in the data set.Then, all data points are sorted according to their densities in descending order. The distanceδi is calculated from a data point i to any other point with a higher density as determined by equation (2).


## 3.2. Resultant Force Acting on a Data Point

The concept of gravity is introduced on the basis of DPC. Newton’s law of universal gravitation [23] states that any particle in the universe attracts any other with a force varying directly as the product of the masses and inversely as the square of the distance between their centers. The gravitational force is formulated as follows:(5)F=G×m1×m2r2,where G is the gravitational constant, m1 and m2 represent the two masses, r represents the distance between the centers of the masses. Table 2 provides a mapping of Newton’s law of universal gravitation with parameters of DPC.Table 2
A mapping of Newton’s law of universal gravitation with parameters of DPC.
Parameters of gravitationParameters of DPCm1ρim2ρjrdijIn equation (6), the Euclidean distance is used to calculate the gravitational force, which avoids the sensitivity of the algorithm to dc value. The gravitational force F acting between data points i and j is defined as equation (6) according to Table 2.(6)fij=ρi×ρjdij2,where fij is the gravitational force between the data point i and the data point j, whose direction is from i to j.For each data pointi, the gravitational force fij from the other data point j is calculated according to equation (6), and we further obtain the magnitude and direction of the resultant force Fi acting on data point i through decomposing and synthesizing the gravitational forces, as shown in equation.(7)Fi=∑jfij.An example of two-dimensional space is shown in Figure3. Suppose that the data point i is located at the origin of a coordinate system. Two gravitational forces F1 and F2 act on point i. F1 can further be decomposed into a force fx1 along the x axis and a force fy1 along the y axis. Similarly, F2 can also be decomposed into fx2 and fy2. Finally, the resultant force Fi acting on point i is obtained by combining the sum of the components of all forces along the x axis (including fx1 and fx2) and the y axis (including fy1 and fy2).Figure 3
Analysis of the resultant force acting on the data pointi.Figure4 shows the resultant force acting on each data point in Flame data set, where the direction of the arrow represents the direction of the resultant force acting on the data point and the length of the arrow represents the magnitude of the resultant force acting on the data point. As can be seen from Figure 4, most resultant forces point towards the two cluster centers. Meanwhile, the farther away the data point is from the cluster center, the less affected by the cluster center. In addition, the magnitude of resultant force in a higher density area is usually larger. In contrast, the resultant force will have a small magnitude in a lower density area.Figure 4
The magnitude and direction of resultant forces acting on each data point in the flame data set.


## 3.3. Force Directional Factor

Here, a parameterγi is introduced which represents the effect of data point i on the resultant forces acting on all other points. The detailed method is given as follows.Take pointsi and j in Figure 4, for example. For clarity, the points i and j are magnified in Figure 5. As shown in Figure 5, αij represents the angle between the vector ji⟶ connecting point j to point i and the resultant force Fj. And αij is in the range 0,180°. The range of αij can be normalized to [−1, 1] by cosαij, as shown in equation (8). cosαij is equal to 1 when αij is equal to 0, which means that the resultant force Fj acting on j points towards i. The larger the value of αij is, the smaller cosαij is, and the more the direction of resultant force Fj acting on j deviates from the data point i.(8)cosαij=Fj⋅ji⟶Fj||ji⟶.Figure 5
The angleα between the vector connecting point j to point i and the resultant force F.In addition, from Figure4, it can be seen that the resultant force acting on data point k also points towards point i. However, i and k belong to different clusters, which indicates that it will produce the clustering error while only considering cosαij. To address this issue, not only the resultant force should be considered but also the distance between data points. Thus, the parameter γij is defined as(9)γij=cosαijdij.For data pointi, γij is calculated between it and all other points. The force directional factor γi is further defined as follows:(10)γi=∑jγij.A larger value ofγi indicates that the point i has a significant effect on the resultant force acting on the other points. Hence, the point i may be most likely to be a cluster center or located near the cluster center.


## 3.4. Determine the Cluster Centers

For the data pointi near the cluster center, its value of γi will be larger due to the effect of the cluster center. Thus, both of δi and γi can be considered. Therefore, the cluster centers are selected according to the product of δi by γi. Each remaining point is assigned to the same cluster as its nearest neighbor of higher density. Algorithm 1 shows the proposed clustering algorithm based on the resultant force. Figure 6 illustrates the flowchart of RFDPC algorithm.Figure 6
The flowchart of the RFDPC algorithm.Algorithm 1: The clustering algorithm based on the resultant force.
Input: Data set X =  x1,x2,…,xn (n is the number of data points), number of clusters KOutput: A clustering resultStep 1. Calculate the densityρi and the distance δi of each data point i.(1.1)
Calculatedij from X according to equation (3).(1.2)
Determinedc value so that the average number of neighbors is about 1 to 2% of the total point number in the data set.(1.3)
Calculateρi based on equation (1) or equation (4) and sort all ρi in descending order.(1.4)
Calculate the distanceδi according to equation (2).Step 2. Calculate the resultant force acting on the data point.(2.1)
Calculate the gravitational force acting on the data point according to equation (6), and the resultant force according to equation (7).(2.2)
Calculateγi according to equations (9) and (10).Step 3. Determine the cluster center.(3.1)
Select the K cluster centers according to the product ofδi by γi, that is, the cluster center is selected from the data points with larger product values.(3.2)
Each remaining point is assigned to the same cluster as its nearest neighbor with higher density.


## 4. Complexity Analysis

The computational complexity of RFDPC is analyzed as follows:Firstly, we calculate the densityρi and the distance δi of each data point i, which requires On2 calculations.Next, we calculate the resultant force acting on the data point. The time complexity of calculating the gravitational force acting on a data point and the resultant force isOn2. The time for the calculation of γi is On2.Finally, we determine the cluster center. SinceK≤n, the time for the selection of K cluster centers can be ignored. It takes about OKn to assign each remaining point to its nearest cluster.As a result, the total time complexity of the RFDPC algorithm is approximatelyOn2.


## 5. Experimental Results

For the purpose of testing the feasibility and effectiveness of the RFDPC algorithm, it is compared with k-means [6], DPC [14], GDPC [23], single linkage [8], spectral clustering [24], DPC-CE [20], and McDPC [21] on 11 synthetic data sets DS1-DS11 (https://github.com/milaan9/Clustering-Datasets) and 15 UCI real data sets [6] listed in Table 3. Both Shuttle and Eeg are large-scale data sets and Gene is a high-dimensional data set. The code used in this paper is released, which is written in Matlab and available at https://github.com/djhahaha/cluster.Table 3
List of 11 synthetic data sets and 15 real data sets from UCI.
Data setNumber of instancesNumber of attributesNumber of classesDS137322DS2100024DS364424DS431223DS578827DS63100231DS724022DS8150026DS9200025DS1040023DS1129923Australian credit approval690142E coli33678Heart270132Lenses2443Pendigits34981610SCADI702057Seeds21073Segmentation210197Soybean47354Synthetic_control600606Urban5071479Wifi localization200074Shuttle4350096Eeg14980142Gene801205315An example of a hierarchical clustering algorithm is a single linkage algorithm. Spectral clustering is one of the graph-based clustering algorithms. Fork-means and spectral clustering, the best clustering result was obtained from 50 trial runs according to the external clustering validity index. In addition, the parameter of dc in DPC, GDPC, DPC-CE, and RFDPC set as 1.2. McDPC includes three parameters γ, θ, and λ, and the values of these three parameters are determined by a heuristic algorithm [21]. The algorithms were all implemented in MATLAB. The experiments were carried out on a machine with Intel Core i5 2.2 GHz CPU and 8 GB RAM running Windows 10.This paper uses Rand Index (RI) [25], Adjusted rand index (ARI) [26], Jaccard (JC) [27], Purity (PR) [28], F-measure (F1) [23], and NMI [29] to evaluate the clustering performance of the above compared algorithms. The larger values of these indices mean better clustering result.


### 5.1. Detect Clusters of Varying Densities

There are two clusters in the DS1 data set, one with a higher density and another with a lower density. The DS2 has four clusters, one with higher densities and the other three with lower densities. The experiments are carried out on DS1 and DS2 in detecting clusters of varying densities. For DS1, in Figure7, it is obvious that k-means, GDPC, single linkage, and spectral clustering cannot identify the clusters of varying densities. All four remaining clustering algorithms can produce the correct clustering results. Figure 8 illustrates the clustering results on DS2. For DS2, the results of k-means, DPC-CE, and McDPC are not perfect, but they are better than those from DPC, GDPC, and single linkage. Both spectral clustering and RFDPC can identify the clusters correctly. The reason why RFDPC can aggregate clusters of varying densities properly is that it finds the cluster center based on the direction of the resultant force acting on the data point instead of the density of the data point.Figure 7
Clustering performance on DS1. (a)K-means. (b) DPC. (c) GDPC. (d) Single linkage. (e) Spectral clustering. (f) DPC-CE. (g) McDPC. (h) RFDPC.
(a)(b)(c)(d)(e)(f)(g)(h)Figure 8
Clustering performance on DS2. (a)K-means. (b) DPC. (c) GDPC. (d) Single linkage. (e) Spectral clustering. (f) DPC-CE. (g) McDPC. (h) RFDPC.
(a)(b)(c)(d)(e)(f)(g)(h)


### 5.2. Detect Clusters of Irregular Shapes

We evaluate the performance of RFDPC using nine data sets (DS3-DS11). The DS3 data set comprises a spherical cluster as well as three semi-moon clusters. The DS4 data set consists of three spiral clusters which are isolated from one another. The DS5 data set includes seven Gaussian distributed clusters. With regard to the DS6 data set, there are 31 two-dimensional Gaussian clusters, each with 100 data points. There are a crescentic cluster and a spherical cluster in the DS7 data set. In the DS8 data set, there are three spiral clusters and four Gaussian distributed clusters. The DS9 data set consists of four sphere-shaped clusters and one nonsphere-shaped cluster. The DS10 data set contains the following cluster types: linear cluster, ring-shaped cluster, and compact rectangular cluster. There are two round clusters in the DS11 data set, along with one Gaussian distributed cluster.Figure9 illustrates that spectral clustering and RFDPC perform better than other algorithms on DS3. Figure 10 illustrates the clustering results on DS4. Except for k-means and spectral clustering, all algorithms identify the expected clusters. Figure 11 describes the clustering results on DS5. Among these methods, DPC, GDPC, spectral clustering, DPC-CE, McDPC, and RFDPC give correct partitions, while k-means and single linkage do not. Figure 12 illustrates the clustering results on DS6. GDPC, DPC-CE, and RFDPC can discover the 31 clusters. We can see from Figure 13 that both of DPC-CE and RFDPC can produce the proper partitions. As for DS8 shown in Figure 14, DPC, DPC-CE, and RFDPC can discover the expected clusters. For DS9 shown in Figure 15, DPC, DPC-CE, McDPC, and RFDPC can identify the satisfactory partitions except for the outliers in the upper right corner. Figure 16 describes the clustering results on DS10. DPC, single linkage, DPC-CE, and RFDPC are capable of generating the proper partitions. In addition, we can see from Figure 17 that the proper partitions can only be identified by single linkage, spectral clustering, and DPC-CE.Figure 9
Clustering performance on DS3. (a)K-means. (b) DPC. (c) GDPC. (d) Single linkage. (e) Spectral clustering. (f) DPC-CE. (g) McDPC. (h) RFDPC.
(a)(b)(c)(d)(e)(f)(g)(h)Figure 10
Clustering performance on DS4. (a)K-means. (b) DPC. (c) GDPC. (d) Single linkage. (e) Spectral clustering. (f) DPC-CE. (g) McDPC. (h) RFDPC.
(a)(b)(c)(d)(e)(f)(g)(h)Figure 11
Clustering performance on DS5. (a)K-means. (b) DPC. (c) GDPC. (d) Single linkage. (e) Spectral clustering. (f) DPC-CE. (g) McDPC. (h) RFDPC.
(a)(b)(c)(d)(e)(f)(g)(h)Figure 12
Clustering performance on DS6. (a)K-means. (b) DPC. (c) GDPC. (d) Single linkage. (e) Spectral clustering. (f) DPC-CE. (g) McDPC. (h) RFDPC.
(a)(b)(c)(d)(e)(f)(g)(h)Figure 13
Clustering performance on DS7. (a)K-means. (b) DPC. (c) GDPC. (d) Single linkage. (e) Spectral clustering. (f) DPC-CE. (g) McDPC. (h) RFDPC.
(a)(b)(c)(d)(e)(f)(g)(h)Figure 14
Clustering performance on DS8. (a)K-means. (b) DPC. (c) GDPC. (d) Single linkage. (e) Spectral clustering. (f) DPC-CE. (g) McDPC. (h) RFDPC.
(a)(b)(c)(d)(e)(f)(g)(h)Figure 15
Clustering performance on DS9. (a)K-means. (b) DPC. (c) GDPC. (d) Single linkage. (e) Spectral clustering. (f) DPC-CE. (g) McDPC. (h) RFDPC.
(a)(b)(c)(d)(e)(f)(g)(h)Figure 16
Clustering performance on DS10. (a)K-means. (b) DPC. (c) GDPC. (d) Single linkage. (e) Spectral clustering. (f) DPC-CE. (g) McDPC. (h) RFDPC.
(a)(b)(c)(d)(e)(f)(g)(h)Figure 17
Clustering performance on DS11. (a)K-means. (b) DPC. (c) GDPC. (d) Single linkage. (e) Spectral clustering. (f) DPC-CE. (g) McDPC. (h) RFDPC.
(a)(b)(c)(d)(e)(f)(g)(h)We further explain the reason why RFDPC cannot identify the proper partitions for DS11. Figure18 shows the three cluster centers determined by RFDPC, where the cluster centers are represented by purple stars. According to Figure 18, it is evident that each of the three cluster centers is located in a different cluster. Following the determination of the three cluster centers, each remaining point is assigned to a cluster based on its nearest neighbor of higher density. An incorrectly assigned data point may result in the domino effect, that is, once one data point is incorrectly assigned, subsequent data points may also be incorrectly assigned.Figure 18
Three cluster centers of DS11 determined by RFDPC.


### 5.3. Determine the Number of Clusters

Figures19–21 show the decision graph for three data sets, including Wine, Seeds, and DS3. It can be seen from Figure 19 that RFDPC is more accurate than both DPC and GDPC in detecting the cluster number. DPC can distinguish only two cluster centers. And, GDPC can find one cluster center and cannot identify all of the three cluster centers. As can be seen from the decision graph (Figure 19(c)), there are three distinct points. Hence, RFDPC can find three cluster centers correctly. Figure 20 shows that GDPC can only discover one cluster center. Figure 21(a) shows that DPC can discover four cluster centers; however, the point in the red circle can easily be mistaken for the center. In contrast, it can be seen from Figure 21(c) that RFDPC can discover the proper cluster centers.Figure 19
Decision graph of Wine. (a) DPC. (b) GDPC. (c) RFDPC.
(a)(b)(c)Figure 20
Decision graph of seeds. (a) DPC. (b) GDPC. (c) RFDPC.
(a)(b)(c)Figure 21
Decision graph of DS3. (a) DPC. (b) GDPC. (c) RFDPC.
(a)(b)(c)


### 5.4. Experiments on the Real Data Sets

Tables4–18 list the performance comparison of eight clustering algorithms on 15 real data sets. In Tables 4–18, the optimal value for each index is indicated in bold. It can be seen from Tables 4–18 that RFDPC obtains the best performance for most data sets. For the large-scale Shuttle data set, RFDPC achieved the best results for all indices except the Purity index. In addition, RFDPC achieved the best results for FM and NMI on the Gene data set.Table 4
The performance comparison of eight clustering algorithms on Australian Credit Approval.
Indexk-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCRand0.65310.62220.49930.50570.68420.66590.49930.7257ARI0.30590.2443−0.01010.00070.36800.33160.46850.4513Jaccard0.49980.45980.47420.50490.53220.50410.66250.5739Purity0.75210.74780.55510.55650.80320.7884—0.8362FM0.65960.63000.67010.71010.69450.6703−0.00950.7293NMI0.42790.17990.00330.27410.32480.51830.03940.2440The optimal value for each index is indicated in bold.Table 5
The performance comparison of eight clustering algorithms on E coli.
Indexk-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCRand0.81490.74750.68090.34440.78910.75150.70500.7920ARI0.46590.30860.33770.04270.39900.31990.46420.4431Jaccard0.40660.30760.39200.28260.35790.31520.67170.4082Purity0.80790.73810.67860.45830.76640.74110.63990.7738FM0.59250.47480.58340.52320.53960.48360.42890.5822NMI0.58110.49730.39670.51490.52120.19440.51560.5411The optimal value for each index is indicated in bold.Table 6
The performance comparison of eight clustering algorithms on heart.
Indexk-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCRand0.63580.67880.49840.50350.67000.51030.49660.6878ARI0.27150.3573−0.0087−0.00150.34000.01980.32470.3753Jaccard0.47420.52540.44860.50190.50490.36340.49030.5370Purity0.74740.80000.55560.55560.79260.5778—0.8074FM0.64080.68910.63710.70700.67110.5334−0.00650.6990NMI0.27940.27800.00850.19830.25830.15190.01560.2780The optimal value for each index is indicated in bold.Table 7
The performance comparison of eight clustering algorithms on lenses.
Indexk-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCRand0.58790.58700.58700.40580.64130.61960.43840.7609ARI0.14010.13450.1345−0.16650.25470.15290.43840.5152Jaccard0.30560.29190.29190.26130.37340.16000.66210.5742Purity0.68630.66670.66670.62500.79170.91670.62500.8333FM0.46900.45810.45810.41820.54740.371100.7295NMI0.30960.40370.17130.50690.190405e − 160.4242The optimal value for each index is indicated in bold.Table 8
The performance comparison of eight clustering algorithms on pendigits.
Indexk-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCRand0.88800.92720.88160.47320.88120.89340.24750.9233ARI0.46430.61210.48580.10890.46550.52540.10480.6141Jaccard0.35690.48440.37890.15080.36080.41170.30610.4890Purity0.68210.73210.66120.21640.65720.6315—0.7410FM0.53250.65340.56610.37760.54210.59770.01390.6605NMI0.67980.74850.49000.75290.684800.16440.7626The optimal value for each index is indicated in bold.Table 9
The performance comparison of eight clustering algorithms on SCADI.
Indexk-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCRand0.81330.69930.61080.79920.66000.85300.70350.8381ARI0.45100.18910.05620.49700.19580.62460.09370.5630Jaccard0.39970.24060.19380.46470.27470.56810.18960.5038Purity0.79500.64290.52860.75710.64290.7429—0.7143FM0.57440.38820.32680.63610.43560.72530.02950.6706NMI0.57850.41380.57970.62580.390100.31480.3688The optimal value for each index is indicated in bold.Table 10
The performance comparison of eight clustering algorithms on seeds.
Indexk-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCRand0.86740.88170.80460.33980.85940.87990.88170.8817ARI0.70060.73410.57559e − 60.68340.72880.73140.7341Jaccard0.66640.69920.57000.32700.65120.69270.69920.6992Purity0.88870.90000.81430.34760.88400.90000.90000.9000FM0.79980.82310.72820.56640.78880.81850.82310.8231NMI0.66540.72380.57350.72270.66560.72010.72380.7238The optimal value for each index is indicated in bold.Table 11
The performance comparison of eight clustering algorithms on segmentation.
Indexk-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCRand0.84570.87760.76740.48610.83340.86480.82410.8835ARI0.45560.53710.35190.11190.42190.49630.35460.5445Jaccard0.37460.43740.31190.18520.34990.40360.54050.4416Purity0.60810.70000.52380.35710.59510.7000—0.7000FM0.55410.61250.51270.40200.52760.57980.42380.6144NMI0.62640.71060.46740.62180.53510.29300.64230.6854The optimal value for each index is indicated in bold.Table 12
The performance comparison of eight clustering algorithms on soybean.
Indexk-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCRand0.922910.39410.85940.93370.81960.57631ARI0.80831−0.01090.67380.83330.59240.16581Jaccard0.783810.22120.62650.79500.55780.28781Purity0.900110.38300.82980.92980.7872—1FM0.863310.41090.78340.88010.7327−0.00661NMI0.830910.80110.89540.883600.21451The optimal value for each index is indicated in bold.Table 13
The performance comparison of eight clustering algorithms on Synthetic_control.
Indexk-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCRand0.87370.82180.72020.88820.85860.84780.82590.8667ARI0.58980.53750.29750.67920.58670.53140.03660.6029Jaccard0.50000.46980.29450.59400.50550.45230.10950.5180Purity0.72190.50670.47000.67000.66730.6483—0.6667FM0.67170.67740.48690.76920.68690.63330.03300.6985NMI0.72320.71360.11170.69540.77040.53530.29640.7779The optimal value for each index is indicated in bold.Table 14
The performance comparison of eight clustering algorithms on urban.
Indexk-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCRand0.86940.83560.65530.16890.64840.83710.48040.8279ARI0.45060.41010.15790.00080.17750.39230.20630.4390Jaccard0.35750.33980.20080.14570.21440.32310.44060.3687Purity0.68520.58380.47730.20510.52270.6213—0.6134FM0.52710.51120.37170.37700.39840.49010.13650.5519NMI0.54130.50860.05080.49770.353900.34020.5490The optimal value for each index is indicated in bold.Table 15
The performance comparison of eight clustering algorithms on Wifi localization.
Indexk-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCRand0.92920.84590.25470.25110.82240.92430.75520.8728ARI0.81740.63690.00013∗10−70.53950.80130.02960.6935Jaccard0.76710.59060.24900.24940.49180.74230.14890.6402Purity0.91690.74600.73950.25150.72650.9100—0.7910FM0.86600.75300.49720.49890.65990.85240.03890.7883NMI0.83990.76880.42450.80250.70030.98450.23930.8139The optimal value for each index is indicated in bold.Table 16
The performance comparison of eight clustering algorithms on shuttle.
Indexk-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCRand0.55560.68970.57110.55660.74550.49670.74150.7830ARI0.35190.59480.55760.39770.66180.38690.59790.6720Jaccard0.56330.74680.72440.58680.79650.56230.77210.8140Purity0.20530.3497−0.08210.16530.45770.7821—0.5741FM0.86620.87490.78210.89520.9132−0.00580.51360.9232NMI0.33560.38950.03700.33410.50090.01060.47850.5395The optimal value for each index is indicated in bold.Table 17
The performance comparison of eight clustering algorithms on Eeg.
Indexk-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCRand0.50350.50690.50720.50710.50650.50160.50320.5093ARI0.00040.00050.00070.00040.0003−0.0086−0.00460.0047Jaccard0.43720.49640.50660.50670.49810.47790.47230.5049Purity0.56140.56140.56140.56140.56140.56140.56140.5694FM0.62100.69730.71130.71160.69980.67380.66590.7081NMI7e − 70.00013e − 50.00110.000200.00240.0181The optimal value for each index is indicated in bold.Table 18
The performance comparison of eight clustering algorithms on gene.
Indexk-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCRand0.89210.80860.24630.25030.85250.82750.29610.8651ARI0.71280.5683−0.0009−0.00590.63750.60860.23290.6892Jaccard0.64560.53520.24080.23760.58390.56850.46070.6398Purity0.85140.74280.37700.37710.82400.7266—0.8227FM0.78510.71730.48860.48110.74440.7446−0.00400.7986NMI0.80280.70800.00870.01790.828500.01620.8546


### 5.5. Parameter Setting

In this section, we will discuss the value ofdc involved in RFDPC. Table 19 shows the F-measure on the 15 UCI real data sets when dc is from 1 to 2. It can be seen from Table 19 that RFDPC performs better on the 15 data sets when dc is from 1.2 to 1.7. Thus, the best setting for dc is between 1.2 and 1.7.Table 19
F-measure on the 15 UCI real data sets when dc is from 1 to 2.
Data setdc11.11.21.31.41.51.61.71.81.92Australian credit approval0.67030.72930.72930.72930.72930.72930.72930.72930.67170.67170.6717E coli0.49660.58220.58220.58220.58220.58220.58220.53660.53660.53660.5366Heart0.66680.66680.66680.6990.6990.6990.6990.6990.6990.6990.699Lenses0.72950.72950.72950.72950.72950.72950.72950.72950.72950.72950.7295Pendigits0.66730.65870.65750.65610.6560.6560.66050.66050.62550.62550.6255SCADI0.67060.67060.67060.67060.67060.67060.67060.67060.67060.67060.6706Seeds0.82310.82310.82310.82310.82310.82310.82310.82310.82310.82310.8231Segmentation0.55320.57230.62380.6270.6270.62270.62270.62270.61440.61440.6144Soybean11111111111Synthetic control0.69560.69560.69560.69850.69850.69850.69850.69850.69850.69850.6985Urban0.54220.55190.55190.55190.55190.55190.55190.54670.54670.54670.5467Wifi localization0.79050.78940.85010.85010.78830.78830.78830.78830.75220.75220.7522Shuttle0.8140.8140.8140.82380.82380.82690.86470.92320.92320.92320.9232Eeg0.70810.70810.70810.70810.70810.70810.70810.70810.70810.70810.7081Gene0.79860.79860.79860.79860.79860.79860.79860.79860.79860.79860.7986Average0.70840.71930.72670.72990.72570.72560.72850.7290.71980.71980.7198


### 5.6. Running Time Comparison

A list of the time complexity is provided in Table20 for k-means, DPC, GDPC, single linkage, spectral clustering, DPC-CE, McDPC, and RFDPC, where n, D, K, and I denote the data point number in the data set, dimensionality, cluster number, and the iteration number for k-means, respectively. According to Table 20, single linkage and spectral clustering have the highest time complexity. In addition, DPC, GDPC, DPC-CE, McDPC, and RFDPC have a complexity of O (n2). Table 21 lists the running time of 8 algorithms on 15 real data sets. Table 21 indicates that the running time on real data sets is comparable to those in Table 20. In addition, the running time of single linkage and spectral clustering on three large-scale or high-dimensional data sets (including Shuttle, Gene, and Eeg) is significantly higher than other data sets. Although the calculation of resultant force is added to RFDPC, we optimize the code of RFDPC. So the running time of RFDPC on Gene and Eeg data sets is less than that of DPC.Table 20
The time complexity of eight algorithms.
AlgorithmTime complexityk-meansO (nDKI)DPCO (n2)GDPCO (n2)Single linkageO (n3)Spectral clusteringO (n3)DPC-CEO (n2)McDPCO (n2)RFDPCO (n2)Table 21
Running time of eight algorithms in seconds.
Data setK-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCAustralian credit approval0.150.530.612.590.670.280.320.57E coli0.220.470.491.670.410.540.340.37Heart0.170.440.481.770.350.380.300.47Lenses0.170.460.451.110.470.690.300.08Pendigits0.262.732.7710.0614.4233.91.743.08SCADI0.190.440.501.191.310.610.260.17Seeds0.180.460.481.690.280.590.330.51Segmentation0.210.450.451.670.510.460.260.46Soybean0.160.440.451.100.480.490.280.09Synthetic_control0.210.520.502.260.480.500.290.52Urban0.240.520.531.970.750.530.300.66Wifi localization0.211.291.255.253.4410.931.601.23Shuttle11.23200.55160.26897.351016.42210.8197.13214.70Gene3.2014.5414.4332.7333.1714.0115.578.50Eeg8.2131.2332.8479.5780.2636.7830.6226.61Average1.6717.0014.4369.4776.8920.7716.6417.20


## 5.1. Detect Clusters of Varying Densities

There are two clusters in the DS1 data set, one with a higher density and another with a lower density. The DS2 has four clusters, one with higher densities and the other three with lower densities. The experiments are carried out on DS1 and DS2 in detecting clusters of varying densities. For DS1, in Figure7, it is obvious that k-means, GDPC, single linkage, and spectral clustering cannot identify the clusters of varying densities. All four remaining clustering algorithms can produce the correct clustering results. Figure 8 illustrates the clustering results on DS2. For DS2, the results of k-means, DPC-CE, and McDPC are not perfect, but they are better than those from DPC, GDPC, and single linkage. Both spectral clustering and RFDPC can identify the clusters correctly. The reason why RFDPC can aggregate clusters of varying densities properly is that it finds the cluster center based on the direction of the resultant force acting on the data point instead of the density of the data point.Figure 7
Clustering performance on DS1. (a)K-means. (b) DPC. (c) GDPC. (d) Single linkage. (e) Spectral clustering. (f) DPC-CE. (g) McDPC. (h) RFDPC.
(a)(b)(c)(d)(e)(f)(g)(h)Figure 8
Clustering performance on DS2. (a)K-means. (b) DPC. (c) GDPC. (d) Single linkage. (e) Spectral clustering. (f) DPC-CE. (g) McDPC. (h) RFDPC.
(a)(b)(c)(d)(e)(f)(g)(h)


## 5.2. Detect Clusters of Irregular Shapes

We evaluate the performance of RFDPC using nine data sets (DS3-DS11). The DS3 data set comprises a spherical cluster as well as three semi-moon clusters. The DS4 data set consists of three spiral clusters which are isolated from one another. The DS5 data set includes seven Gaussian distributed clusters. With regard to the DS6 data set, there are 31 two-dimensional Gaussian clusters, each with 100 data points. There are a crescentic cluster and a spherical cluster in the DS7 data set. In the DS8 data set, there are three spiral clusters and four Gaussian distributed clusters. The DS9 data set consists of four sphere-shaped clusters and one nonsphere-shaped cluster. The DS10 data set contains the following cluster types: linear cluster, ring-shaped cluster, and compact rectangular cluster. There are two round clusters in the DS11 data set, along with one Gaussian distributed cluster.Figure9 illustrates that spectral clustering and RFDPC perform better than other algorithms on DS3. Figure 10 illustrates the clustering results on DS4. Except for k-means and spectral clustering, all algorithms identify the expected clusters. Figure 11 describes the clustering results on DS5. Among these methods, DPC, GDPC, spectral clustering, DPC-CE, McDPC, and RFDPC give correct partitions, while k-means and single linkage do not. Figure 12 illustrates the clustering results on DS6. GDPC, DPC-CE, and RFDPC can discover the 31 clusters. We can see from Figure 13 that both of DPC-CE and RFDPC can produce the proper partitions. As for DS8 shown in Figure 14, DPC, DPC-CE, and RFDPC can discover the expected clusters. For DS9 shown in Figure 15, DPC, DPC-CE, McDPC, and RFDPC can identify the satisfactory partitions except for the outliers in the upper right corner. Figure 16 describes the clustering results on DS10. DPC, single linkage, DPC-CE, and RFDPC are capable of generating the proper partitions. In addition, we can see from Figure 17 that the proper partitions can only be identified by single linkage, spectral clustering, and DPC-CE.Figure 9
Clustering performance on DS3. (a)K-means. (b) DPC. (c) GDPC. (d) Single linkage. (e) Spectral clustering. (f) DPC-CE. (g) McDPC. (h) RFDPC.
(a)(b)(c)(d)(e)(f)(g)(h)Figure 10
Clustering performance on DS4. (a)K-means. (b) DPC. (c) GDPC. (d) Single linkage. (e) Spectral clustering. (f) DPC-CE. (g) McDPC. (h) RFDPC.
(a)(b)(c)(d)(e)(f)(g)(h)Figure 11
Clustering performance on DS5. (a)K-means. (b) DPC. (c) GDPC. (d) Single linkage. (e) Spectral clustering. (f) DPC-CE. (g) McDPC. (h) RFDPC.
(a)(b)(c)(d)(e)(f)(g)(h)Figure 12
Clustering performance on DS6. (a)K-means. (b) DPC. (c) GDPC. (d) Single linkage. (e) Spectral clustering. (f) DPC-CE. (g) McDPC. (h) RFDPC.
(a)(b)(c)(d)(e)(f)(g)(h)Figure 13
Clustering performance on DS7. (a)K-means. (b) DPC. (c) GDPC. (d) Single linkage. (e) Spectral clustering. (f) DPC-CE. (g) McDPC. (h) RFDPC.
(a)(b)(c)(d)(e)(f)(g)(h)Figure 14
Clustering performance on DS8. (a)K-means. (b) DPC. (c) GDPC. (d) Single linkage. (e) Spectral clustering. (f) DPC-CE. (g) McDPC. (h) RFDPC.
(a)(b)(c)(d)(e)(f)(g)(h)Figure 15
Clustering performance on DS9. (a)K-means. (b) DPC. (c) GDPC. (d) Single linkage. (e) Spectral clustering. (f) DPC-CE. (g) McDPC. (h) RFDPC.
(a)(b)(c)(d)(e)(f)(g)(h)Figure 16
Clustering performance on DS10. (a)K-means. (b) DPC. (c) GDPC. (d) Single linkage. (e) Spectral clustering. (f) DPC-CE. (g) McDPC. (h) RFDPC.
(a)(b)(c)(d)(e)(f)(g)(h)Figure 17
Clustering performance on DS11. (a)K-means. (b) DPC. (c) GDPC. (d) Single linkage. (e) Spectral clustering. (f) DPC-CE. (g) McDPC. (h) RFDPC.
(a)(b)(c)(d)(e)(f)(g)(h)We further explain the reason why RFDPC cannot identify the proper partitions for DS11. Figure18 shows the three cluster centers determined by RFDPC, where the cluster centers are represented by purple stars. According to Figure 18, it is evident that each of the three cluster centers is located in a different cluster. Following the determination of the three cluster centers, each remaining point is assigned to a cluster based on its nearest neighbor of higher density. An incorrectly assigned data point may result in the domino effect, that is, once one data point is incorrectly assigned, subsequent data points may also be incorrectly assigned.Figure 18
Three cluster centers of DS11 determined by RFDPC.


## 5.3. Determine the Number of Clusters

Figures19–21 show the decision graph for three data sets, including Wine, Seeds, and DS3. It can be seen from Figure 19 that RFDPC is more accurate than both DPC and GDPC in detecting the cluster number. DPC can distinguish only two cluster centers. And, GDPC can find one cluster center and cannot identify all of the three cluster centers. As can be seen from the decision graph (Figure 19(c)), there are three distinct points. Hence, RFDPC can find three cluster centers correctly. Figure 20 shows that GDPC can only discover one cluster center. Figure 21(a) shows that DPC can discover four cluster centers; however, the point in the red circle can easily be mistaken for the center. In contrast, it can be seen from Figure 21(c) that RFDPC can discover the proper cluster centers.Figure 19
Decision graph of Wine. (a) DPC. (b) GDPC. (c) RFDPC.
(a)(b)(c)Figure 20
Decision graph of seeds. (a) DPC. (b) GDPC. (c) RFDPC.
(a)(b)(c)Figure 21
Decision graph of DS3. (a) DPC. (b) GDPC. (c) RFDPC.
(a)(b)(c)


## 5.4. Experiments on the Real Data Sets

Tables4–18 list the performance comparison of eight clustering algorithms on 15 real data sets. In Tables 4–18, the optimal value for each index is indicated in bold. It can be seen from Tables 4–18 that RFDPC obtains the best performance for most data sets. For the large-scale Shuttle data set, RFDPC achieved the best results for all indices except the Purity index. In addition, RFDPC achieved the best results for FM and NMI on the Gene data set.Table 4
The performance comparison of eight clustering algorithms on Australian Credit Approval.
Indexk-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCRand0.65310.62220.49930.50570.68420.66590.49930.7257ARI0.30590.2443−0.01010.00070.36800.33160.46850.4513Jaccard0.49980.45980.47420.50490.53220.50410.66250.5739Purity0.75210.74780.55510.55650.80320.7884—0.8362FM0.65960.63000.67010.71010.69450.6703−0.00950.7293NMI0.42790.17990.00330.27410.32480.51830.03940.2440The optimal value for each index is indicated in bold.Table 5
The performance comparison of eight clustering algorithms on E coli.
Indexk-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCRand0.81490.74750.68090.34440.78910.75150.70500.7920ARI0.46590.30860.33770.04270.39900.31990.46420.4431Jaccard0.40660.30760.39200.28260.35790.31520.67170.4082Purity0.80790.73810.67860.45830.76640.74110.63990.7738FM0.59250.47480.58340.52320.53960.48360.42890.5822NMI0.58110.49730.39670.51490.52120.19440.51560.5411The optimal value for each index is indicated in bold.Table 6
The performance comparison of eight clustering algorithms on heart.
Indexk-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCRand0.63580.67880.49840.50350.67000.51030.49660.6878ARI0.27150.3573−0.0087−0.00150.34000.01980.32470.3753Jaccard0.47420.52540.44860.50190.50490.36340.49030.5370Purity0.74740.80000.55560.55560.79260.5778—0.8074FM0.64080.68910.63710.70700.67110.5334−0.00650.6990NMI0.27940.27800.00850.19830.25830.15190.01560.2780The optimal value for each index is indicated in bold.Table 7
The performance comparison of eight clustering algorithms on lenses.
Indexk-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCRand0.58790.58700.58700.40580.64130.61960.43840.7609ARI0.14010.13450.1345−0.16650.25470.15290.43840.5152Jaccard0.30560.29190.29190.26130.37340.16000.66210.5742Purity0.68630.66670.66670.62500.79170.91670.62500.8333FM0.46900.45810.45810.41820.54740.371100.7295NMI0.30960.40370.17130.50690.190405e − 160.4242The optimal value for each index is indicated in bold.Table 8
The performance comparison of eight clustering algorithms on pendigits.
Indexk-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCRand0.88800.92720.88160.47320.88120.89340.24750.9233ARI0.46430.61210.48580.10890.46550.52540.10480.6141Jaccard0.35690.48440.37890.15080.36080.41170.30610.4890Purity0.68210.73210.66120.21640.65720.6315—0.7410FM0.53250.65340.56610.37760.54210.59770.01390.6605NMI0.67980.74850.49000.75290.684800.16440.7626The optimal value for each index is indicated in bold.Table 9
The performance comparison of eight clustering algorithms on SCADI.
Indexk-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCRand0.81330.69930.61080.79920.66000.85300.70350.8381ARI0.45100.18910.05620.49700.19580.62460.09370.5630Jaccard0.39970.24060.19380.46470.27470.56810.18960.5038Purity0.79500.64290.52860.75710.64290.7429—0.7143FM0.57440.38820.32680.63610.43560.72530.02950.6706NMI0.57850.41380.57970.62580.390100.31480.3688The optimal value for each index is indicated in bold.Table 10
The performance comparison of eight clustering algorithms on seeds.
Indexk-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCRand0.86740.88170.80460.33980.85940.87990.88170.8817ARI0.70060.73410.57559e − 60.68340.72880.73140.7341Jaccard0.66640.69920.57000.32700.65120.69270.69920.6992Purity0.88870.90000.81430.34760.88400.90000.90000.9000FM0.79980.82310.72820.56640.78880.81850.82310.8231NMI0.66540.72380.57350.72270.66560.72010.72380.7238The optimal value for each index is indicated in bold.Table 11
The performance comparison of eight clustering algorithms on segmentation.
Indexk-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCRand0.84570.87760.76740.48610.83340.86480.82410.8835ARI0.45560.53710.35190.11190.42190.49630.35460.5445Jaccard0.37460.43740.31190.18520.34990.40360.54050.4416Purity0.60810.70000.52380.35710.59510.7000—0.7000FM0.55410.61250.51270.40200.52760.57980.42380.6144NMI0.62640.71060.46740.62180.53510.29300.64230.6854The optimal value for each index is indicated in bold.Table 12
The performance comparison of eight clustering algorithms on soybean.
Indexk-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCRand0.922910.39410.85940.93370.81960.57631ARI0.80831−0.01090.67380.83330.59240.16581Jaccard0.783810.22120.62650.79500.55780.28781Purity0.900110.38300.82980.92980.7872—1FM0.863310.41090.78340.88010.7327−0.00661NMI0.830910.80110.89540.883600.21451The optimal value for each index is indicated in bold.Table 13
The performance comparison of eight clustering algorithms on Synthetic_control.
Indexk-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCRand0.87370.82180.72020.88820.85860.84780.82590.8667ARI0.58980.53750.29750.67920.58670.53140.03660.6029Jaccard0.50000.46980.29450.59400.50550.45230.10950.5180Purity0.72190.50670.47000.67000.66730.6483—0.6667FM0.67170.67740.48690.76920.68690.63330.03300.6985NMI0.72320.71360.11170.69540.77040.53530.29640.7779The optimal value for each index is indicated in bold.Table 14
The performance comparison of eight clustering algorithms on urban.
Indexk-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCRand0.86940.83560.65530.16890.64840.83710.48040.8279ARI0.45060.41010.15790.00080.17750.39230.20630.4390Jaccard0.35750.33980.20080.14570.21440.32310.44060.3687Purity0.68520.58380.47730.20510.52270.6213—0.6134FM0.52710.51120.37170.37700.39840.49010.13650.5519NMI0.54130.50860.05080.49770.353900.34020.5490The optimal value for each index is indicated in bold.Table 15
The performance comparison of eight clustering algorithms on Wifi localization.
Indexk-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCRand0.92920.84590.25470.25110.82240.92430.75520.8728ARI0.81740.63690.00013∗10−70.53950.80130.02960.6935Jaccard0.76710.59060.24900.24940.49180.74230.14890.6402Purity0.91690.74600.73950.25150.72650.9100—0.7910FM0.86600.75300.49720.49890.65990.85240.03890.7883NMI0.83990.76880.42450.80250.70030.98450.23930.8139The optimal value for each index is indicated in bold.Table 16
The performance comparison of eight clustering algorithms on shuttle.
Indexk-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCRand0.55560.68970.57110.55660.74550.49670.74150.7830ARI0.35190.59480.55760.39770.66180.38690.59790.6720Jaccard0.56330.74680.72440.58680.79650.56230.77210.8140Purity0.20530.3497−0.08210.16530.45770.7821—0.5741FM0.86620.87490.78210.89520.9132−0.00580.51360.9232NMI0.33560.38950.03700.33410.50090.01060.47850.5395The optimal value for each index is indicated in bold.Table 17
The performance comparison of eight clustering algorithms on Eeg.
Indexk-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCRand0.50350.50690.50720.50710.50650.50160.50320.5093ARI0.00040.00050.00070.00040.0003−0.0086−0.00460.0047Jaccard0.43720.49640.50660.50670.49810.47790.47230.5049Purity0.56140.56140.56140.56140.56140.56140.56140.5694FM0.62100.69730.71130.71160.69980.67380.66590.7081NMI7e − 70.00013e − 50.00110.000200.00240.0181The optimal value for each index is indicated in bold.Table 18
The performance comparison of eight clustering algorithms on gene.
Indexk-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCRand0.89210.80860.24630.25030.85250.82750.29610.8651ARI0.71280.5683−0.0009−0.00590.63750.60860.23290.6892Jaccard0.64560.53520.24080.23760.58390.56850.46070.6398Purity0.85140.74280.37700.37710.82400.7266—0.8227FM0.78510.71730.48860.48110.74440.7446−0.00400.7986NMI0.80280.70800.00870.01790.828500.01620.8546


## 5.5. Parameter Setting

In this section, we will discuss the value ofdc involved in RFDPC. Table 19 shows the F-measure on the 15 UCI real data sets when dc is from 1 to 2. It can be seen from Table 19 that RFDPC performs better on the 15 data sets when dc is from 1.2 to 1.7. Thus, the best setting for dc is between 1.2 and 1.7.Table 19
F-measure on the 15 UCI real data sets when dc is from 1 to 2.
Data setdc11.11.21.31.41.51.61.71.81.92Australian credit approval0.67030.72930.72930.72930.72930.72930.72930.72930.67170.67170.6717E coli0.49660.58220.58220.58220.58220.58220.58220.53660.53660.53660.5366Heart0.66680.66680.66680.6990.6990.6990.6990.6990.6990.6990.699Lenses0.72950.72950.72950.72950.72950.72950.72950.72950.72950.72950.7295Pendigits0.66730.65870.65750.65610.6560.6560.66050.66050.62550.62550.6255SCADI0.67060.67060.67060.67060.67060.67060.67060.67060.67060.67060.6706Seeds0.82310.82310.82310.82310.82310.82310.82310.82310.82310.82310.8231Segmentation0.55320.57230.62380.6270.6270.62270.62270.62270.61440.61440.6144Soybean11111111111Synthetic control0.69560.69560.69560.69850.69850.69850.69850.69850.69850.69850.6985Urban0.54220.55190.55190.55190.55190.55190.55190.54670.54670.54670.5467Wifi localization0.79050.78940.85010.85010.78830.78830.78830.78830.75220.75220.7522Shuttle0.8140.8140.8140.82380.82380.82690.86470.92320.92320.92320.9232Eeg0.70810.70810.70810.70810.70810.70810.70810.70810.70810.70810.7081Gene0.79860.79860.79860.79860.79860.79860.79860.79860.79860.79860.7986Average0.70840.71930.72670.72990.72570.72560.72850.7290.71980.71980.7198


## 5.6. Running Time Comparison

A list of the time complexity is provided in Table20 for k-means, DPC, GDPC, single linkage, spectral clustering, DPC-CE, McDPC, and RFDPC, where n, D, K, and I denote the data point number in the data set, dimensionality, cluster number, and the iteration number for k-means, respectively. According to Table 20, single linkage and spectral clustering have the highest time complexity. In addition, DPC, GDPC, DPC-CE, McDPC, and RFDPC have a complexity of O (n2). Table 21 lists the running time of 8 algorithms on 15 real data sets. Table 21 indicates that the running time on real data sets is comparable to those in Table 20. In addition, the running time of single linkage and spectral clustering on three large-scale or high-dimensional data sets (including Shuttle, Gene, and Eeg) is significantly higher than other data sets. Although the calculation of resultant force is added to RFDPC, we optimize the code of RFDPC. So the running time of RFDPC on Gene and Eeg data sets is less than that of DPC.Table 20
The time complexity of eight algorithms.
AlgorithmTime complexityk-meansO (nDKI)DPCO (n2)GDPCO (n2)Single linkageO (n3)Spectral clusteringO (n3)DPC-CEO (n2)McDPCO (n2)RFDPCO (n2)Table 21
Running time of eight algorithms in seconds.
Data setK-meansDPCGDPCSingle linkageSpectral clusteringDPC-CEMcDPCRFDPCAustralian credit approval0.150.530.612.590.670.280.320.57E coli0.220.470.491.670.410.540.340.37Heart0.170.440.481.770.350.380.300.47Lenses0.170.460.451.110.470.690.300.08Pendigits0.262.732.7710.0614.4233.91.743.08SCADI0.190.440.501.191.310.610.260.17Seeds0.180.460.481.690.280.590.330.51Segmentation0.210.450.451.670.510.460.260.46Soybean0.160.440.451.100.480.490.280.09Synthetic_control0.210.520.502.260.480.500.290.52Urban0.240.520.531.970.750.530.300.66Wifi localization0.211.291.255.253.4410.931.601.23Shuttle11.23200.55160.26897.351016.42210.8197.13214.70Gene3.2014.5414.4332.7333.1714.0115.578.50Eeg8.2131.2332.8479.5780.2636.7830.6226.61Average1.6717.0014.4369.4776.8920.7716.6417.20


## 6. Discussion

To further explain the proposed algorithm, let us consider the test case in Figure22. In Figure 22(a), 25 data points are embedded in a two-dimensional space. The data points are ranked in order of decreasing γ. The black arrow represents the direction of the resultant force acting on the data point. All arrows in Figure 22(a) are of the same length because the magnitude of the resultant force is not involved in the calculation of γ. Figure 22(b) shows the corresponding decision graphs.Figure 22
The algorithm in two dimensions. (a) Point distribution. Data points are ranked in order of decreasingγ. The black arrow represents the direction of the resultant force acting on the data point. (b) Decision graph for the data in (a). Different colors correspond to different clusters.
(a)(b)According to Step 1 of Algorithm 1, we calculate the densityρi and the distance δi of each data point. Specifically, we calculate the Euclidean distance from data point xi to other points. For simplicity, the value of dc in this example is set to 2%. Then, we calculate ρi and δi of each data point according to equations (1) and (2), respectively. Next, we calculate the resultant force acting on each data point according to Step 2 of Algorithm 1. We can see from Figure 22(a) that for the red cluster, most resultant forces point towards data point 1. In addition, we can find that there is no resultant force acting on the data point 1. This is mainly due to the fact that the magnitude of the resultant force acting on the data point 1 is equal to 0. Furthermore, the number of data points in the blue cluster is much smaller than that in the red cluster, so the resultant forces acting on the data points in the blue cluster are greatly affected by the data points in the red cluster. Hence, we can see from Figure 22(a) that for the blue cluster, the resultant forces do not point towards a certain data point. Next, we calculate γi according to equations (9) and (10). Finally, we determine the cluster centers according to the product of δi by γi. It can be seen from Figure 22(b) that the data points 1 and 17 with a larger product value are selected as the cluster center. Then, each remaining point is assigned to the same cluster as its nearest neighbor of higher density. The density of the red cluster is higher than that of the blue one in Figure 22(a). The γ value of data point 17 is smaller than that of the data point 1. But our algorithm considers both of δ and γ which can tackle the problem of varying densities. Since the δ value of data point 17 is close to 1, the data point 17 is selected as a cluster center.


## 7. Conclusions

This paper proposes a resultant force-based clustering algorithm based on gravitation theory. The clustering performance of RFDPC was evaluated using 5 synthetic data sets and 15 real data sets. The results indicate that the RFDPC performs well in the following aspects:(i)
Aggregating clusters with different shapes and densities in an efficient manner.(ii)
Detecting the cluster number.Experimental results indicate that RFDPC is superior to k-means, DPC, GDPC, single linkage, spectral clustering, DPC-CE, and McDPC. GDPC considers the magnitude of the gravitational force between two points but ignores the effect of gravitational forces coming from the other points. We extend the gravitational force in GDPC to the resultant force and select the cluster center depending on both the force directional factorγ and distance δ in the decision graph. Hence, RFDPC can accurately recognize the cluster centers.A major limitation of RFDPC is the assignment scheme for the remaining data points, which is prone to producing consecutive assignment errors. The future work will plan to improve RFDPC by reducing consecutive assignment errors. In addition, ensemble clustering techniques can improve clustering robustness by fusing the information of multiple clustering results [30]. Our algorithm may be improved by using ensemble clustering.



---

*Source: 9143727-2022-06-29.xml*