# A Fast Density Peak Clustering Method with Autoselect Cluster Centers

Authors: Zhihe Wang; Yongbiao Li; Hui Du; Xiaofen Wei
Journal: Mobile Information Systems
 (2022)

---

## Abstract

Aiming at density peaks clustering needs to manually select cluster centers, this paper proposes a fast new clustering method with auto-select cluster centers. Firstly, our method groups the data and marks each group as core or boundary groups according to its density. Secondly, it determines clusters by iteratively merging two core groups whose distance is less than the threshold and selects the cluster centers at the densest position in each cluster. Finally, it assigns boundary groups to the cluster corresponding to the nearest cluster center. Our method eliminates the need for the manual selection of cluster centers and improves clustering efficiency with the experimental results.


---

## Body

## 1. Introduction

Clustering [1–4] is an unsupervised or semisupervised learning method. This method aims at dividing the samples into different clusters according to the similarity between samples so that the samples in the same cluster are as similar as possible and the samples in different clusters are as dissimilar as possible. Clustering has a wide range of applications, such as image analysis [5], pattern recognition [6], data analysis [7], and wireless sensor networks [8]. Under the wide applications, many clustering methods have emerged, such as K-means [9] and fuzzy c-means (FCM) [10] clustering methods, which are only effective for spherical data and have an inferior effect on nonspherical data. But density-based clustering methods [11] such as density peaks clustering (DPC) [12] did not have this problem. However, DPC still has some drawbacks, so improving the density-based clustering method has great significance.Aiming at the problem that DPC needs manual participation in selecting cluster centers, Flores et al. [13] proposed a density peaks clustering with a gap-based automatic center detection method. This method calculates a threshold to distinguish between cluster center samples and noncenter samples. Lv et al. [14] proposed a density peak clustering algorithm based on shared nearest neighbor and adaptive cluster center. This method selects the cluster center by narrowing the search range. However, the cluster centers obtained by the above methods are the same as that of DPC. In other words, if DPC cannot achieve good results on some data, the above methods cannot achieve good results.Aiming at the high time complexity of DPC, Lu et al. [15] proposed a fast distributed density peaks clustering method based on the Z-value index. This method effectively reduces the time complex from On2 to On⋅logn, but the clustering effect is significantly reduced because the data need to be reduced from multidimensional to one dimension. Xu et al. [16] proposed a fast density peaks clustering method based on spare search. This method ensures the clustering effect and effectively reduces the time complexity below On2, but it still needs to select the cluster centers manually. Although the above methods improve the efficiency of DPC, they also have shortcomings.Recently, there have been many ways to improve the precision of DPC [17–20]. These methods have more advantages for some data with considerable noise and complex structures. In [17], dense cores are introduced as a representative of the original data to reduce runtimes. The density threshold is used to eliminate the interference from noise samples. However, it has difficulties processing high-dimensional data. In [18], local density peaks are used to construct a minimum spanning tree to avoid noises and reduce runtimes. However, it cannot automatically determine the number of clusters. In [19], local cores representation dataset is introduced, which avoids noise interference and reduces runtimes by only calculating the graph distance between local cores. Nevertheless, it needs to build a decision diagram. In [20], introducing natural neighbor to find local representations, calculating the adaptive distance between local representations effectively reduces the runtimes. Nevertheless, it cannot automatically determine the cluster centers. Du et al. [21] proposed a k-nearest neighbor DPC method based on principal component analysis. It uses k-nearest neighbor to calculate the sample density and principal component analysis to process high-dimensional data. Nevertheless, it is not effective in dealing with manifold data.This paper presents a new density peak clustering method (GDPC) that can fast and autodetermine the cluster centers by grouping. Our method aims at grouping the datasets to ensure that sample categories of each group are the same and try to minimize the number of groups. In this way, we no longer need to calculate the similarity between all samples but only between groups. At the same time, we find that the cluster centers usually appear in the densest place of each cluster. We can divide each cluster into core and boundary regions according to the feature that the density from cluster center to cluster edge decreases gradually. The distance between the two core regions is considerable so that we can find the cluster centers.The rest of this paper is as follows: in Section 2, we review the DPC. Section 3 introduces our proposed method. In Section 4, we do experiments on the effectiveness and efficiency of synthetic datasets and real datasets. Finally, we summarize this article and put forward further challenges.


## 2. DPC

### 2.1. Quantities

DPC needs to use the density of the sample (ρ) and the distance between the sample and its nearest high-density sample (δ) when finding the cluster centers and determining the sample labels.The density of the samplei is the number of other samples within its cutoff distance (dc) range. The density of the sample i is defined as(1)ρi=∑j∈Dχdij−dc,where dij is the distance between sample i and sample j, and χx=1 if x<0; otherwise, χx=0.The distance between samplei and its nearest high-density sample is defined as(2)δi=minj:ρj>ρidij.For the samplei with the highest density, δi=maxj∈Ddij.


### 2.2. Similarity Matrix

When calculatingρ and δ and determining the sample label, the distance between samples will be calculated many times. To improve efficiency, DPC only calculates the distance between samples once and saves it. It is no longer necessary to recalculate it when it is used again. The similarity matrix is defined as(3)S=d11…d1n⋮⋱⋮dn1…dnn,where dij is the distance between sample i and sample j. n is the number of samples.


### 2.3. Process

After calculatingρ and δ with the above method, we use ρ as abscissa and δ as ordinate to draw a decision diagram, as shown in Figure 1. Figure 1(a) displays the distribution of samples. Figure 1(b) is the corresponding decision diagram. We can find that the upper right corner of the decision diagram indicates the cluster centers.Figure 1
Density peak clustering method. (a) Samples distribution. (b) Decision diagram.
(a)(b)After selecting the cluster centers, the labels of the remaining samples are the same as that of the nearest high-density sample.


### 2.4. Time Complexity

The time complexity of DPC has three main parts: (a) calculatingρ requires On2 time complexity; (b) calculating δ needs On2 complexity; and (c) determining labels of noncenter samples demands On time complexity, where n is the size of the dataset. Based on the above three parts, the time complexity of DPC is On2.


## 2.1. Quantities

DPC needs to use the density of the sample (ρ) and the distance between the sample and its nearest high-density sample (δ) when finding the cluster centers and determining the sample labels.The density of the samplei is the number of other samples within its cutoff distance (dc) range. The density of the sample i is defined as(1)ρi=∑j∈Dχdij−dc,where dij is the distance between sample i and sample j, and χx=1 if x<0; otherwise, χx=0.The distance between samplei and its nearest high-density sample is defined as(2)δi=minj:ρj>ρidij.For the samplei with the highest density, δi=maxj∈Ddij.


## 2.2. Similarity Matrix

When calculatingρ and δ and determining the sample label, the distance between samples will be calculated many times. To improve efficiency, DPC only calculates the distance between samples once and saves it. It is no longer necessary to recalculate it when it is used again. The similarity matrix is defined as(3)S=d11…d1n⋮⋱⋮dn1…dnn,where dij is the distance between sample i and sample j. n is the number of samples.


## 2.3. Process

After calculatingρ and δ with the above method, we use ρ as abscissa and δ as ordinate to draw a decision diagram, as shown in Figure 1. Figure 1(a) displays the distribution of samples. Figure 1(b) is the corresponding decision diagram. We can find that the upper right corner of the decision diagram indicates the cluster centers.Figure 1
Density peak clustering method. (a) Samples distribution. (b) Decision diagram.
(a)(b)After selecting the cluster centers, the labels of the remaining samples are the same as that of the nearest high-density sample.


## 2.4. Time Complexity

The time complexity of DPC has three main parts: (a) calculatingρ requires On2 time complexity; (b) calculating δ needs On2 complexity; and (c) determining labels of noncenter samples demands On time complexity, where n is the size of the dataset. Based on the above three parts, the time complexity of DPC is On2.


## 3. The Proposed Method

To solve the manual intervention in selecting cluster centers of DPC and the high time complexity of DPC, we proposed GDPC. In GDPC, we isolate the core regions of different clusters to find the cluster centers and use the grouping method to reduce the amount of calculation.


### 3.1. Grouping

Under the condition of ensuring that the sample labels in each group are the same, the fewer the number of groups, the more efficient our method can be.We define the distance between the ungrouped samplexi and the first sample in group g as xi−g. We divide sample i into group g if xi−g<dc. If no group g makes xi−g<dc, we create a new group. Sample i is the first sample in this group. Algorithm 1 explains the grouping method in detail.These groups have the following characteristics:(1)
xi−g<dcxi∈g: the distance between the first sample and other samples in the group is less than dc.(2)
gi∩gj=∅i≠j: the same sample does not exist in two different groups.(3)
xi∈Cjxi∈g,ifg1∈Cj, where Cj is cluster j and g1 is first sample in group g. All samples in the same group belong to the same cluster.To distinguish whether groupi is a core group or a boundary group, we need to use the group density, which is defined as(4)ρi=gi−1.Algorithm 1: Grouping.
(1)
Input: data set D=x1,x2,…,xn, dc(2)
Output: group set G=g1,g2,…,gm(3)
Create setG=∅(4)
For each sample x in D do(5)
If exist x−g<dc then(6)
g←g∪x(7)
Else(8)
Create new group (x)(9)
End if(10)
End forDefinition 1.
(zero density group). The group with only one sample. If groupi is zero density group, ρi=0.
Through experience, we first remove groups with zero density and then arrange the remaining group density in descending order. Finally, if the density of the groupi is greater than or equal to the density threshold (ρt), group gi is defined as the core group; otherwise, it is defined as the boundary group. The density threshold is defined as(5)ρt=f⌈0.7×n⌉−1,where n is the number of nonzero density group and fi is the density of the i-th group after descending sorting.
As shown in Table1, there are 7 nonzero density groups. The density threshold ρt calculated by equation (5) is f⌈0.7×7⌉−1, f4=2. Because the density of groups 0, 1, 2, 3, 4, 5 is greater than or equal to ρt, they are core groups. The density of groups 6, 7 is less than ρt, so it is a boundary group. The density of group 7 is 0, so it is a zero density group.Table 1
Examples of core and boundary groups.
i01234567ρ43322210


### 3.2. Select Cluster Centers and Determine Core Group Sample Labels

When we determine the core group set, we need to find the core region of each cluster through its spatial relationship. Then, we can select the cluster center of each cluster where the density is the densest.We propose the following definitions.Definition 2.
(key sample). The first sample in each group.Definition 3.
(transitivity). If the distance between any sample in groupp and the key sample in group q is less than 2dc, p can reach q through transitivity.
The two groupsp and q with transitivity satisfy the following equation:(6)p−q≤2dc,where p−q is the distance between any sample in group p and the key sample in group q. We can combine core groups (join the same cluster) through equation (6).
Figure2, because g1−g2≤2dc, so, group 1 can reach group 2 through transitivity. Therefore, there is also transitivity between groups 2 and 3. By transitivity, we can connect group 1, group 2, and group 3, so they belong to the same cluster.
Assume that the density of group3 is the highest in groups 1, 2, and 3, and group 3 is already in cluster c, whereas groups 2 and 3 are not in any cluster. Because there is transitivity between groups 2 and 3 (g2−g3≤2dc), and group 3 is in cluster c. So it can be regarded as transitivity between group 2 and cluster c (g2−c≤2dc). After group 2 is added to cluster c, group 1 and cluster c also have transitivity, so group 1 can be added to cluster c.
Algorithm2 shows the specific steps, where o−c is the distance between sample o in core set and any sample in cluster c. go is the set of all samples in the group whose first sample is o. o1 is the first sample in the current core set. Firstly, we select the first sample in the core set as the initial cluster center. Secondly, connect its corresponding group with other core groups through transitivity. The following unconnected sample in the core set is selected as the cluster center when more core groups cannot be connected. Repeat the above steps until all the core groups have been assigned clusters.Algorithm 2: Select cluster centers and determine core group sample labels.
(1)
Input: Core set O=o1,o2,…,om, Group set G=g1,g2,…,gm, dc(2)
Output: Center set T=t1,t2,…,tk, Cluster set C=c1,c2,…,ck(3)
Create setC=∅(4)
While exist o in O do(5)
/∗ Merge all core groups ∗/(6)
Flag=0(7)
For each sample o in O do(8)
/∗ When a core group is added to a cluster or a cluster is created, the transitivity between the remaining core groups and the cluster is judged ∗/(9)
If exist o−c≤2dc then(10)
/∗ transitivity judgment ∗/(11)
c←c∪go(12)
O\o(13)
Flag=1(14)
Break(15)
End if(16)
End for(17)
IfFlag==0 then(18)
/∗ group o1 is not transitive to any existing label group ∗/(19)
Create new cluster (o1)(20)
T←T∪o1(21)
O\o1(22)
Flag=1(23)
End if(24)
End whileFigure 2
Transitivity.


### 3.3. Determine Boundary Group Sample Labels

When selecting the cluster center, we mark two transitive core groups as the same cluster. In this way, we can determine the labels of the core group sample simultaneously when selecting the cluster centers.After finding the cluster centers, we calculate the distance between the boundary group and the core group sample. If the distance between groupi and core group sample j is less than 2dc, all samples in group i have the same label as sample j, where the distance between group i and sample j is the distance between the key sample in group i and sample j. After that, we need to determine the label of the remaining boundary group sample. We calculate the distance between the key samples in each nonzero density boundary group and each cluster center. We divide the nonzero density boundary group into the cluster corresponding to the nearest cluster center and mark the zero density boundary group samples as noise samples.


### 3.4. Process

Our method (Algorithm3) consists of the following five main steps: (1) group the datasets using dc; (2) select the cluster centers and determine the core group sample labels through transitivity; (3) calculate the distance between the boundary group and the core group sample and determine the boundary group labels with distances less than 2dc; (4) calculate the distance between the remaining nonzero density boundary groups and the cluster centers, and determine the labels of the remaining nonzero density boundary group; and (5) mark the remaining zero density group samples as noise samples.Algorithm 3: GDPC.
(1)
Input: data set D=x1,x2,…,xn, dc(2)
Output: center set T=t1,t2,…,tk, cluster set C=c1,c2,…,ck(3)
Grouping data using Algorithm1(4)
Select the cluster centers and determine the core group sample labels using Algorithm2(5)
Calculate the distance between the boundary group and the core group sample and determine boundary group labels with distances less than2dc(6)
Determine the label of the remaining nonzero density boundary group sample(7)
Mark the remaining zero density group samples as noise samples


### 3.5. Example

In this subsection, we introduce the process of our method through an example, as shown in Figure3 and Table 2.(1)
Group the data: calculate the distance between samplex1 and the existing group. Since there is no group yet, create a new group g1, and add sample x1 to group g1. Calculate the distance between sample x2 and the existing group (g1). Because x2−g1>dc, create a new group g2 and add sample x2 to group g2. Calculate the distance between sample x3 and the existing group (g1, g2). Because x3−g1>dc and x3−g2≤dc, so add sample x3 to group g2. Repeat the above steps until all samples are added to the group. Calculate the density of each group by equation (4). The grouping results and density are shown in Table 2.(2)
Distinguish core or boundary groups: firstly, we sort the groups in descending order of density, and the result isg3,g1,g2,g4,g6,g9,g5,g7,g8. Secondly, we remove the zero density group and calculate the density threshold is 1 from equation (5) (⌈0.7×6⌉−1=4), where 4th group is g6, and its density is 1. So groups g3,g1,g2,g4,g6,g9 are the core groups, and groups g5,g7,g8 are the boundary groups.(3)
Determine core group labels: select the key samplex4 of group g3 as the first cluster center, and create a new cluster c1 to add group g3 to cluster c1. Since g1−c1≤2dc, add group g1 to cluster c1. Because the distances between groups g2,g4,g6,g9 and cluster c1 are greater than 2dc, take the key sample x2 of group g2 as the second cluster center, create a new cluster c2, and add group g2 to cluster c2. Since g4−c1>2dc and g4−c2≤2dc, add group g4 to cluster c2. Since g6−c1>2dc and g6−c2≤2dc, add group g6 to cluster c2. Since g9−c1>2dc and g9−c2≤2dc, add group g9 to cluster c2.(4)
Determine boundary group labels: becauseg5−c1>2dc and g5−c2>2dc, group g5 is not processed temporarily. Because g7−c1>2dc and g7−c2>2dc, group g7 is not processed temporarily. Since g8−c1≤2dc, add group g8 to cluster c1. Next, we divide the nonzero boundary groups into a cluster corresponding to the nearest cluster center. In this example, there is no nonzero density boundary group, so this step ends here.(5)
Determine noise samples: in the previous step, the zero density boundary groups not divided into cluster are considered noise samples. In this example, samplesx8 and x14 in groups g5 and g7 are marked as noise samples.Figure 3
Clustering example.Table 2
The grouping results.
GroupSample (s)Densityg1x1,x5,x62g2x2,x3,x182g3x4,x9,x10,x13,x19,x215g4x7,x11,x152g5x80g6x12,x161g7x140g8x170g9x20,x221After completing the above steps, the clustering process is over. The clustering results are shown in Table3. This example generates two clusters, including 10 samples in cluster c1, 10 samples in cluster c2, and 2 noise samples.Table 3
Clustering results of example.
ClustersSamplesInstancesc1x4,x9,x10,x13,x19,x21,x1,x5,x6,x1710c2x2,x3,x18,x7,x11,x25,x12,x16,x20,x2210Noisesx8,x142


### 3.6. Time Complexity

The time complexity of our method has four main parts:It is assumed that the dataset withn samples is divided into a core groups and b boundary groups.(a)
Grouping requiresOa+b⋅n time complexity(b)
Sorting core group density needsOa⋅loga time complexity(c)
Finding the cluster centers and determining the core group sample labels needOa⋅n time complexity(d)
Determining labels of noncenter samples demandsOb⋅n+b time complexityBased on the above four parts, the time complexity of our method isOa+b⋅n, where a+b<n. Therefore, the time complexity of our method is less than On2.


## 3.1. Grouping

Under the condition of ensuring that the sample labels in each group are the same, the fewer the number of groups, the more efficient our method can be.We define the distance between the ungrouped samplexi and the first sample in group g as xi−g. We divide sample i into group g if xi−g<dc. If no group g makes xi−g<dc, we create a new group. Sample i is the first sample in this group. Algorithm 1 explains the grouping method in detail.These groups have the following characteristics:(1)
xi−g<dcxi∈g: the distance between the first sample and other samples in the group is less than dc.(2)
gi∩gj=∅i≠j: the same sample does not exist in two different groups.(3)
xi∈Cjxi∈g,ifg1∈Cj, where Cj is cluster j and g1 is first sample in group g. All samples in the same group belong to the same cluster.To distinguish whether groupi is a core group or a boundary group, we need to use the group density, which is defined as(4)ρi=gi−1.Algorithm 1: Grouping.
(1)
Input: data set D=x1,x2,…,xn, dc(2)
Output: group set G=g1,g2,…,gm(3)
Create setG=∅(4)
For each sample x in D do(5)
If exist x−g<dc then(6)
g←g∪x(7)
Else(8)
Create new group (x)(9)
End if(10)
End forDefinition 1.
(zero density group). The group with only one sample. If groupi is zero density group, ρi=0.
Through experience, we first remove groups with zero density and then arrange the remaining group density in descending order. Finally, if the density of the groupi is greater than or equal to the density threshold (ρt), group gi is defined as the core group; otherwise, it is defined as the boundary group. The density threshold is defined as(5)ρt=f⌈0.7×n⌉−1,where n is the number of nonzero density group and fi is the density of the i-th group after descending sorting.
As shown in Table1, there are 7 nonzero density groups. The density threshold ρt calculated by equation (5) is f⌈0.7×7⌉−1, f4=2. Because the density of groups 0, 1, 2, 3, 4, 5 is greater than or equal to ρt, they are core groups. The density of groups 6, 7 is less than ρt, so it is a boundary group. The density of group 7 is 0, so it is a zero density group.Table 1
Examples of core and boundary groups.
i01234567ρ43322210


## 3.2. Select Cluster Centers and Determine Core Group Sample Labels

When we determine the core group set, we need to find the core region of each cluster through its spatial relationship. Then, we can select the cluster center of each cluster where the density is the densest.We propose the following definitions.Definition 2.
(key sample). The first sample in each group.Definition 3.
(transitivity). If the distance between any sample in groupp and the key sample in group q is less than 2dc, p can reach q through transitivity.
The two groupsp and q with transitivity satisfy the following equation:(6)p−q≤2dc,where p−q is the distance between any sample in group p and the key sample in group q. We can combine core groups (join the same cluster) through equation (6).
Figure2, because g1−g2≤2dc, so, group 1 can reach group 2 through transitivity. Therefore, there is also transitivity between groups 2 and 3. By transitivity, we can connect group 1, group 2, and group 3, so they belong to the same cluster.
Assume that the density of group3 is the highest in groups 1, 2, and 3, and group 3 is already in cluster c, whereas groups 2 and 3 are not in any cluster. Because there is transitivity between groups 2 and 3 (g2−g3≤2dc), and group 3 is in cluster c. So it can be regarded as transitivity between group 2 and cluster c (g2−c≤2dc). After group 2 is added to cluster c, group 1 and cluster c also have transitivity, so group 1 can be added to cluster c.
Algorithm2 shows the specific steps, where o−c is the distance between sample o in core set and any sample in cluster c. go is the set of all samples in the group whose first sample is o. o1 is the first sample in the current core set. Firstly, we select the first sample in the core set as the initial cluster center. Secondly, connect its corresponding group with other core groups through transitivity. The following unconnected sample in the core set is selected as the cluster center when more core groups cannot be connected. Repeat the above steps until all the core groups have been assigned clusters.Algorithm 2: Select cluster centers and determine core group sample labels.
(1)
Input: Core set O=o1,o2,…,om, Group set G=g1,g2,…,gm, dc(2)
Output: Center set T=t1,t2,…,tk, Cluster set C=c1,c2,…,ck(3)
Create setC=∅(4)
While exist o in O do(5)
/∗ Merge all core groups ∗/(6)
Flag=0(7)
For each sample o in O do(8)
/∗ When a core group is added to a cluster or a cluster is created, the transitivity between the remaining core groups and the cluster is judged ∗/(9)
If exist o−c≤2dc then(10)
/∗ transitivity judgment ∗/(11)
c←c∪go(12)
O\o(13)
Flag=1(14)
Break(15)
End if(16)
End for(17)
IfFlag==0 then(18)
/∗ group o1 is not transitive to any existing label group ∗/(19)
Create new cluster (o1)(20)
T←T∪o1(21)
O\o1(22)
Flag=1(23)
End if(24)
End whileFigure 2
Transitivity.


## 3.3. Determine Boundary Group Sample Labels

When selecting the cluster center, we mark two transitive core groups as the same cluster. In this way, we can determine the labels of the core group sample simultaneously when selecting the cluster centers.After finding the cluster centers, we calculate the distance between the boundary group and the core group sample. If the distance between groupi and core group sample j is less than 2dc, all samples in group i have the same label as sample j, where the distance between group i and sample j is the distance between the key sample in group i and sample j. After that, we need to determine the label of the remaining boundary group sample. We calculate the distance between the key samples in each nonzero density boundary group and each cluster center. We divide the nonzero density boundary group into the cluster corresponding to the nearest cluster center and mark the zero density boundary group samples as noise samples.


## 3.4. Process

Our method (Algorithm3) consists of the following five main steps: (1) group the datasets using dc; (2) select the cluster centers and determine the core group sample labels through transitivity; (3) calculate the distance between the boundary group and the core group sample and determine the boundary group labels with distances less than 2dc; (4) calculate the distance between the remaining nonzero density boundary groups and the cluster centers, and determine the labels of the remaining nonzero density boundary group; and (5) mark the remaining zero density group samples as noise samples.Algorithm 3: GDPC.
(1)
Input: data set D=x1,x2,…,xn, dc(2)
Output: center set T=t1,t2,…,tk, cluster set C=c1,c2,…,ck(3)
Grouping data using Algorithm1(4)
Select the cluster centers and determine the core group sample labels using Algorithm2(5)
Calculate the distance between the boundary group and the core group sample and determine boundary group labels with distances less than2dc(6)
Determine the label of the remaining nonzero density boundary group sample(7)
Mark the remaining zero density group samples as noise samples


## 3.5. Example

In this subsection, we introduce the process of our method through an example, as shown in Figure3 and Table 2.(1)
Group the data: calculate the distance between samplex1 and the existing group. Since there is no group yet, create a new group g1, and add sample x1 to group g1. Calculate the distance between sample x2 and the existing group (g1). Because x2−g1>dc, create a new group g2 and add sample x2 to group g2. Calculate the distance between sample x3 and the existing group (g1, g2). Because x3−g1>dc and x3−g2≤dc, so add sample x3 to group g2. Repeat the above steps until all samples are added to the group. Calculate the density of each group by equation (4). The grouping results and density are shown in Table 2.(2)
Distinguish core or boundary groups: firstly, we sort the groups in descending order of density, and the result isg3,g1,g2,g4,g6,g9,g5,g7,g8. Secondly, we remove the zero density group and calculate the density threshold is 1 from equation (5) (⌈0.7×6⌉−1=4), where 4th group is g6, and its density is 1. So groups g3,g1,g2,g4,g6,g9 are the core groups, and groups g5,g7,g8 are the boundary groups.(3)
Determine core group labels: select the key samplex4 of group g3 as the first cluster center, and create a new cluster c1 to add group g3 to cluster c1. Since g1−c1≤2dc, add group g1 to cluster c1. Because the distances between groups g2,g4,g6,g9 and cluster c1 are greater than 2dc, take the key sample x2 of group g2 as the second cluster center, create a new cluster c2, and add group g2 to cluster c2. Since g4−c1>2dc and g4−c2≤2dc, add group g4 to cluster c2. Since g6−c1>2dc and g6−c2≤2dc, add group g6 to cluster c2. Since g9−c1>2dc and g9−c2≤2dc, add group g9 to cluster c2.(4)
Determine boundary group labels: becauseg5−c1>2dc and g5−c2>2dc, group g5 is not processed temporarily. Because g7−c1>2dc and g7−c2>2dc, group g7 is not processed temporarily. Since g8−c1≤2dc, add group g8 to cluster c1. Next, we divide the nonzero boundary groups into a cluster corresponding to the nearest cluster center. In this example, there is no nonzero density boundary group, so this step ends here.(5)
Determine noise samples: in the previous step, the zero density boundary groups not divided into cluster are considered noise samples. In this example, samplesx8 and x14 in groups g5 and g7 are marked as noise samples.Figure 3
Clustering example.Table 2
The grouping results.
GroupSample (s)Densityg1x1,x5,x62g2x2,x3,x182g3x4,x9,x10,x13,x19,x215g4x7,x11,x152g5x80g6x12,x161g7x140g8x170g9x20,x221After completing the above steps, the clustering process is over. The clustering results are shown in Table3. This example generates two clusters, including 10 samples in cluster c1, 10 samples in cluster c2, and 2 noise samples.Table 3
Clustering results of example.
ClustersSamplesInstancesc1x4,x9,x10,x13,x19,x21,x1,x5,x6,x1710c2x2,x3,x18,x7,x11,x25,x12,x16,x20,x2210Noisesx8,x142


## 3.6. Time Complexity

The time complexity of our method has four main parts:It is assumed that the dataset withn samples is divided into a core groups and b boundary groups.(a)
Grouping requiresOa+b⋅n time complexity(b)
Sorting core group density needsOa⋅loga time complexity(c)
Finding the cluster centers and determining the core group sample labels needOa⋅n time complexity(d)
Determining labels of noncenter samples demandsOb⋅n+b time complexityBased on the above four parts, the time complexity of our method isOa+b⋅n, where a+b<n. Therefore, the time complexity of our method is less than On2.


## 4. Experimental Evaluation

This section has carried out precision and efficiency experiments and has exposed our method source code and synthetic data (download URL=[https://github.com/yongbiaoLi/GDPC.git]), respectively.


### 4.1. Precision Experiment

#### 4.1.1. Synthetic Datasets

In this section, we used K-means, FCM, DPC, and GDPC to experiment in ThreeCircles, Lineblobs, Spiral, and Compound [22] synthetic datasets. Table 4 shows specific information about the datasets.Table 4
Properties of synthetic datasets.
DatasetInstancesDimensionsClustersThreeCircles29923Lineblobs26623Spiral31223Compound39926From Figures4, 5, 6, and 7, the cluster centers obtained by K-means and FCM are not necessarily samples in the data, but those obtained by DPC and GDPC are samples. For nonspherical data such as Figures 4 and 6, K-means and FCM cannot obtain the correct cluster centers and result. For data such as Figures 5 and 7, which combine spherical and nonspherical data, K-means and FCM can only obtain partially correct cluster centers and results. DPC can obtain some clustering centers and results of data such as Figures 5 and 7 because DPC is effective not only for nonspherical data but also for spherical data. However, from Figures 4, 5, 6, and 7, because DPC is stringent in distributing nonspherical data, it is impossible to obtain correct cluster centers and results. Our method is not affected by these distributions.Figure 4
Clusters obtained by K-means, FCM, DPC, and GDPC over ThreeCircles dataset. (a) K-means; (b) FCM; (c) DPC; (d) GDPCdc=0.05.
(a)(b)(c)(d)Figure 5
Clusters obtained by K-means, FCM, DPC, and GDPC over Lineblobs dataset. (a) K-means; (b) FCM; (c) DPC; (d) GDPCdc=0.089.
(a)(b)(c)(d)Figure 6
Clusters obtained by K-means, FCM, DPC, and GDPC over Spiral dataset. (a) K-means; (b) FCM; (c) DPC; (d) GDPCdc=0.058.
(a)(b)(c)(d)Figure 7
Clusters obtained by K-means, FCM, DPC, and GDPC over Compound dataset. (a) K-means; (b) FCM; (c) DPC; (d) GDPCdc=0.026.
(a)(b)(c)(d)


#### 4.1.2. Real-World Datasets

In this section, we use Zoo [23], Thyroid [23], Ecoli [24], Machine [23], Hayes-Roth [23], Sobar-72 [25], Segment [23], and Pendigits [23] real-world data (details are shown in Table 5) to experiment with K-means, FCM, DPC, and our algorithm.Table 5
Properties of real-world datasets.
DatasetInstancesDimensionsClustersZoo101167Thyroid21553Ecoli33688Machine20978Hayes-Roth13243Sobar-7272192Segment2310187Pendigits200001626From Table6, we can see that ARI [26, 27], NMI [28], and homogeneity [29] of GDPC are all higher than those of K-means, FCM, and DPC on Zoo and Thyroid datasets. On machine, Sobar-72 and Sobar-72 datasets, GDPC has two higher metrics than K-means, FCM, and DPC. On Ecoli, Segment, and Pendigits data, only one metric of GDPC is the best. In parentheses is the value of the parameter dc.Table 6
Comparison of the evaluation metrics of the four algorithms on the real-world datasets.
DatasetAlgorithmARINMIHomogeneityZooK-means0.420690.643960.63305FCM0.364690.624330.66487DPC0.30560.422230.32649GDPC (0.718)0.801580.841290.84208ThyroidK-means0.547070.395040.40321FCM0.44130.343440.37DPC0.520630.478180.40368GDPC (0.045)0.683860.554970.57709EcoliK-means0.438840.614930.70525FCM0.349350544860.6399DPC0.450870.607430.63245GDPC (0.093)0.632270.605980.53881MachineK-means0.061950.284020.32626FCM0.409540.448390.54375DPC0.389290.431890.38985GDPC (0.106)0.501510.530980.42842Hayes-RothK-means0.037310.055750.05575FCM-0.014910.00.0DPC0.005910.131450.08757GDPC (0.166)0.032230.256940.50898Sobar-72K-means0.266710.21060.22378FCM0.266710.21060.22378DPC-0.073990.065230.05014GDPC (0.629)0.185690.318030.50194SegmentK-means0.363360.461230.44182FCM0.506320.610170.60989DPC0.240250.526230.40106GDPC (0.089)0.430380.580430.75747PendigitsK-means0.355280.531780.52341FCM0.436470.578680.53033DPC0.554220.724330.69383GDPC (0.15)0.503520.602010.69527The meaning of the bold value is to emphasize that the value is the best result of the four algorithms on the same dataset and metric.The experimental results show that although GDPC is inferior to K-means, FCM, and DPC in some datasets and metrics, its performance is better than that in general.


### 4.2. Efficiency Experiment

#### 4.2.1. Synthetic Datasets

In this section, we use the moons dataset to test the efficiency of DPC and our methods,. The distribution of the moons dataset is shown in Figure8. From Figure 9, we can see that, with the increasing amount of data, the time required for DPC increases significantly, and our method is better than DPC, and it becomes more and more apparent.Figure 8
Moons.Figure 9
Experiments with different instances.


#### 4.2.2. Real-World Datasets

In this section, we use the real-world datasets to test the efficiency of DPC and our methods. As shown in Table7, our method has always been more efficient than DPC. The larger the dc, the faster our method is. The more significant the amount of data, the greater the gap between our method and DPC.Table 7
Runtimes (s) of real-world datasets.
DatasetDPCGDPCZoo0.3740.093Thyroid0.4010.234Ecoli0.8750.462Machine0.3980.265Hayes-Roth0.3750.234Sobar-720.370.031Segment1576.3841046.281Pendigits5294.013595.974The meaning of the bold value is to emphasize the best result of the two algorithms on the same dataset.


### 4.3. Influence of Parameterdc

In this section, we use the moons dataset to test the influence of parameterdc on the clustering results. As shown in Table 8, dc  = 0.05, 0.2, 0.25, and 0.3 cannot make the clustering results completely correct. As dc increases from 0.05 to 0.3, the running time decreases from 277.5 seconds to 1.34375 seconds.Table 8
Results of different parameters on the moon datasets.
ParameterdcRuntimes (s)ARINMIHomogeneity0.05277.50.997990.994290.994290.149.7181.01.01.00.1512.1251.01.01.00.22.31250.00.00.00.251.45310.00.00.00.31.313750.00.00.0The influence ofdc on clustering results mainly has two aspects. (a) Efficiency: the larger the dc, the fewer the number of groups after grouping, and the faster the clustering speed. (b) Precision: too small dc will lead to grouping errors, which will reduce the precision. Too small dc will lead to too many noise samples. Combining the above two aspects, we select the largest dc to ensure that all samples in each group belong to the same cluster.According to the synthetic data experiment,dc is generally half of the distance between the core regions of the two nearest clusters. Because high-dimensional real data cannot be observed, it is challenging to select dc for real data. How to obtain the value of dc in real data is also a limitation of this method.


## 4.1. Precision Experiment

### 4.1.1. Synthetic Datasets

In this section, we used K-means, FCM, DPC, and GDPC to experiment in ThreeCircles, Lineblobs, Spiral, and Compound [22] synthetic datasets. Table 4 shows specific information about the datasets.Table 4
Properties of synthetic datasets.
DatasetInstancesDimensionsClustersThreeCircles29923Lineblobs26623Spiral31223Compound39926From Figures4, 5, 6, and 7, the cluster centers obtained by K-means and FCM are not necessarily samples in the data, but those obtained by DPC and GDPC are samples. For nonspherical data such as Figures 4 and 6, K-means and FCM cannot obtain the correct cluster centers and result. For data such as Figures 5 and 7, which combine spherical and nonspherical data, K-means and FCM can only obtain partially correct cluster centers and results. DPC can obtain some clustering centers and results of data such as Figures 5 and 7 because DPC is effective not only for nonspherical data but also for spherical data. However, from Figures 4, 5, 6, and 7, because DPC is stringent in distributing nonspherical data, it is impossible to obtain correct cluster centers and results. Our method is not affected by these distributions.Figure 4
Clusters obtained by K-means, FCM, DPC, and GDPC over ThreeCircles dataset. (a) K-means; (b) FCM; (c) DPC; (d) GDPCdc=0.05.
(a)(b)(c)(d)Figure 5
Clusters obtained by K-means, FCM, DPC, and GDPC over Lineblobs dataset. (a) K-means; (b) FCM; (c) DPC; (d) GDPCdc=0.089.
(a)(b)(c)(d)Figure 6
Clusters obtained by K-means, FCM, DPC, and GDPC over Spiral dataset. (a) K-means; (b) FCM; (c) DPC; (d) GDPCdc=0.058.
(a)(b)(c)(d)Figure 7
Clusters obtained by K-means, FCM, DPC, and GDPC over Compound dataset. (a) K-means; (b) FCM; (c) DPC; (d) GDPCdc=0.026.
(a)(b)(c)(d)


### 4.1.2. Real-World Datasets

In this section, we use Zoo [23], Thyroid [23], Ecoli [24], Machine [23], Hayes-Roth [23], Sobar-72 [25], Segment [23], and Pendigits [23] real-world data (details are shown in Table 5) to experiment with K-means, FCM, DPC, and our algorithm.Table 5
Properties of real-world datasets.
DatasetInstancesDimensionsClustersZoo101167Thyroid21553Ecoli33688Machine20978Hayes-Roth13243Sobar-7272192Segment2310187Pendigits200001626From Table6, we can see that ARI [26, 27], NMI [28], and homogeneity [29] of GDPC are all higher than those of K-means, FCM, and DPC on Zoo and Thyroid datasets. On machine, Sobar-72 and Sobar-72 datasets, GDPC has two higher metrics than K-means, FCM, and DPC. On Ecoli, Segment, and Pendigits data, only one metric of GDPC is the best. In parentheses is the value of the parameter dc.Table 6
Comparison of the evaluation metrics of the four algorithms on the real-world datasets.
DatasetAlgorithmARINMIHomogeneityZooK-means0.420690.643960.63305FCM0.364690.624330.66487DPC0.30560.422230.32649GDPC (0.718)0.801580.841290.84208ThyroidK-means0.547070.395040.40321FCM0.44130.343440.37DPC0.520630.478180.40368GDPC (0.045)0.683860.554970.57709EcoliK-means0.438840.614930.70525FCM0.349350544860.6399DPC0.450870.607430.63245GDPC (0.093)0.632270.605980.53881MachineK-means0.061950.284020.32626FCM0.409540.448390.54375DPC0.389290.431890.38985GDPC (0.106)0.501510.530980.42842Hayes-RothK-means0.037310.055750.05575FCM-0.014910.00.0DPC0.005910.131450.08757GDPC (0.166)0.032230.256940.50898Sobar-72K-means0.266710.21060.22378FCM0.266710.21060.22378DPC-0.073990.065230.05014GDPC (0.629)0.185690.318030.50194SegmentK-means0.363360.461230.44182FCM0.506320.610170.60989DPC0.240250.526230.40106GDPC (0.089)0.430380.580430.75747PendigitsK-means0.355280.531780.52341FCM0.436470.578680.53033DPC0.554220.724330.69383GDPC (0.15)0.503520.602010.69527The meaning of the bold value is to emphasize that the value is the best result of the four algorithms on the same dataset and metric.The experimental results show that although GDPC is inferior to K-means, FCM, and DPC in some datasets and metrics, its performance is better than that in general.


## 4.1.1. Synthetic Datasets

In this section, we used K-means, FCM, DPC, and GDPC to experiment in ThreeCircles, Lineblobs, Spiral, and Compound [22] synthetic datasets. Table 4 shows specific information about the datasets.Table 4
Properties of synthetic datasets.
DatasetInstancesDimensionsClustersThreeCircles29923Lineblobs26623Spiral31223Compound39926From Figures4, 5, 6, and 7, the cluster centers obtained by K-means and FCM are not necessarily samples in the data, but those obtained by DPC and GDPC are samples. For nonspherical data such as Figures 4 and 6, K-means and FCM cannot obtain the correct cluster centers and result. For data such as Figures 5 and 7, which combine spherical and nonspherical data, K-means and FCM can only obtain partially correct cluster centers and results. DPC can obtain some clustering centers and results of data such as Figures 5 and 7 because DPC is effective not only for nonspherical data but also for spherical data. However, from Figures 4, 5, 6, and 7, because DPC is stringent in distributing nonspherical data, it is impossible to obtain correct cluster centers and results. Our method is not affected by these distributions.Figure 4
Clusters obtained by K-means, FCM, DPC, and GDPC over ThreeCircles dataset. (a) K-means; (b) FCM; (c) DPC; (d) GDPCdc=0.05.
(a)(b)(c)(d)Figure 5
Clusters obtained by K-means, FCM, DPC, and GDPC over Lineblobs dataset. (a) K-means; (b) FCM; (c) DPC; (d) GDPCdc=0.089.
(a)(b)(c)(d)Figure 6
Clusters obtained by K-means, FCM, DPC, and GDPC over Spiral dataset. (a) K-means; (b) FCM; (c) DPC; (d) GDPCdc=0.058.
(a)(b)(c)(d)Figure 7
Clusters obtained by K-means, FCM, DPC, and GDPC over Compound dataset. (a) K-means; (b) FCM; (c) DPC; (d) GDPCdc=0.026.
(a)(b)(c)(d)


## 4.1.2. Real-World Datasets

In this section, we use Zoo [23], Thyroid [23], Ecoli [24], Machine [23], Hayes-Roth [23], Sobar-72 [25], Segment [23], and Pendigits [23] real-world data (details are shown in Table 5) to experiment with K-means, FCM, DPC, and our algorithm.Table 5
Properties of real-world datasets.
DatasetInstancesDimensionsClustersZoo101167Thyroid21553Ecoli33688Machine20978Hayes-Roth13243Sobar-7272192Segment2310187Pendigits200001626From Table6, we can see that ARI [26, 27], NMI [28], and homogeneity [29] of GDPC are all higher than those of K-means, FCM, and DPC on Zoo and Thyroid datasets. On machine, Sobar-72 and Sobar-72 datasets, GDPC has two higher metrics than K-means, FCM, and DPC. On Ecoli, Segment, and Pendigits data, only one metric of GDPC is the best. In parentheses is the value of the parameter dc.Table 6
Comparison of the evaluation metrics of the four algorithms on the real-world datasets.
DatasetAlgorithmARINMIHomogeneityZooK-means0.420690.643960.63305FCM0.364690.624330.66487DPC0.30560.422230.32649GDPC (0.718)0.801580.841290.84208ThyroidK-means0.547070.395040.40321FCM0.44130.343440.37DPC0.520630.478180.40368GDPC (0.045)0.683860.554970.57709EcoliK-means0.438840.614930.70525FCM0.349350544860.6399DPC0.450870.607430.63245GDPC (0.093)0.632270.605980.53881MachineK-means0.061950.284020.32626FCM0.409540.448390.54375DPC0.389290.431890.38985GDPC (0.106)0.501510.530980.42842Hayes-RothK-means0.037310.055750.05575FCM-0.014910.00.0DPC0.005910.131450.08757GDPC (0.166)0.032230.256940.50898Sobar-72K-means0.266710.21060.22378FCM0.266710.21060.22378DPC-0.073990.065230.05014GDPC (0.629)0.185690.318030.50194SegmentK-means0.363360.461230.44182FCM0.506320.610170.60989DPC0.240250.526230.40106GDPC (0.089)0.430380.580430.75747PendigitsK-means0.355280.531780.52341FCM0.436470.578680.53033DPC0.554220.724330.69383GDPC (0.15)0.503520.602010.69527The meaning of the bold value is to emphasize that the value is the best result of the four algorithms on the same dataset and metric.The experimental results show that although GDPC is inferior to K-means, FCM, and DPC in some datasets and metrics, its performance is better than that in general.


## 4.2. Efficiency Experiment

### 4.2.1. Synthetic Datasets

In this section, we use the moons dataset to test the efficiency of DPC and our methods,. The distribution of the moons dataset is shown in Figure8. From Figure 9, we can see that, with the increasing amount of data, the time required for DPC increases significantly, and our method is better than DPC, and it becomes more and more apparent.Figure 8
Moons.Figure 9
Experiments with different instances.


### 4.2.2. Real-World Datasets

In this section, we use the real-world datasets to test the efficiency of DPC and our methods. As shown in Table7, our method has always been more efficient than DPC. The larger the dc, the faster our method is. The more significant the amount of data, the greater the gap between our method and DPC.Table 7
Runtimes (s) of real-world datasets.
DatasetDPCGDPCZoo0.3740.093Thyroid0.4010.234Ecoli0.8750.462Machine0.3980.265Hayes-Roth0.3750.234Sobar-720.370.031Segment1576.3841046.281Pendigits5294.013595.974The meaning of the bold value is to emphasize the best result of the two algorithms on the same dataset.


## 4.2.1. Synthetic Datasets

In this section, we use the moons dataset to test the efficiency of DPC and our methods,. The distribution of the moons dataset is shown in Figure8. From Figure 9, we can see that, with the increasing amount of data, the time required for DPC increases significantly, and our method is better than DPC, and it becomes more and more apparent.Figure 8
Moons.Figure 9
Experiments with different instances.


## 4.2.2. Real-World Datasets

In this section, we use the real-world datasets to test the efficiency of DPC and our methods. As shown in Table7, our method has always been more efficient than DPC. The larger the dc, the faster our method is. The more significant the amount of data, the greater the gap between our method and DPC.Table 7
Runtimes (s) of real-world datasets.
DatasetDPCGDPCZoo0.3740.093Thyroid0.4010.234Ecoli0.8750.462Machine0.3980.265Hayes-Roth0.3750.234Sobar-720.370.031Segment1576.3841046.281Pendigits5294.013595.974The meaning of the bold value is to emphasize the best result of the two algorithms on the same dataset.


## 4.3. Influence of Parameterdc

In this section, we use the moons dataset to test the influence of parameterdc on the clustering results. As shown in Table 8, dc  = 0.05, 0.2, 0.25, and 0.3 cannot make the clustering results completely correct. As dc increases from 0.05 to 0.3, the running time decreases from 277.5 seconds to 1.34375 seconds.Table 8
Results of different parameters on the moon datasets.
ParameterdcRuntimes (s)ARINMIHomogeneity0.05277.50.997990.994290.994290.149.7181.01.01.00.1512.1251.01.01.00.22.31250.00.00.00.251.45310.00.00.00.31.313750.00.00.0The influence ofdc on clustering results mainly has two aspects. (a) Efficiency: the larger the dc, the fewer the number of groups after grouping, and the faster the clustering speed. (b) Precision: too small dc will lead to grouping errors, which will reduce the precision. Too small dc will lead to too many noise samples. Combining the above two aspects, we select the largest dc to ensure that all samples in each group belong to the same cluster.According to the synthetic data experiment,dc is generally half of the distance between the core regions of the two nearest clusters. Because high-dimensional real data cannot be observed, it is challenging to select dc for real data. How to obtain the value of dc in real data is also a limitation of this method.


## 5. Conclusion

This paper presents a new method to improve DPC. We divide the data into minor groups while ensuring that the sample labels in each group are the same, so we only need to calculate the similarity between groups to reduce the amount of calculation. At the same time, we isolate the core regions of different clusters, which makes it easy for us to find the cluster center at the densest location. Among many methods to improve DPC efficiency, the automatic selection of cluster centers is not solved. Our method not only improves DPC efficiency but also solves the problem of automatic selection of cluster centers.GDPC has a good effect on some spherical and nonspherical data, but it does not perform well in some complex data with noise samples. Because GDPC only uses onedc in one data, it is difficult to achieve a good grouping result in some complex data, resulting in unsatisfactory clustering results and efficiency. In addition, how to obtain the value of dc in real data is also a limitation of this method. These are also where we need to improve.The advantages of the density-based clustering method in nonspherical data are difficult to replace. In the future, we still need to consider how to improve the efficiency under reducing parameters.


## 6. Application

Clustering can be applied to wireless sensor data annotation. We apply the clustering method to the activity data [30] of the elderly to identify the four states of the elderly: (a) sit on the bed; (b) sit on a chair; (c) lying; and (d) ambulating. The data were obtained by Torres et al. through a battery-free wearable sensor. As shown in Figure 10, the experimental results show that our proposed method has certain advantages in wireless sensor data annotation.Figure 10
Performance comparison of different methods.



---

*Source: 4176101-2022-01-11.xml*