# Improved Density Peaks Clustering Based on Natural Neighbor Expanded Group

Authors: Lin Ding; Weihong Xu; Yuantao Chen
Journal: Complexity
 (2020)

---

## Abstract

Density peaks clustering (DPC) is an advanced clustering technique due to its multiple advantages of efficiently determining cluster centers, fewer arguments, no iterations, no border noise, etc. However, it does suffer from the following defects: (1) difficult to determine a suitable value of its crucial cutoff distance parameter, (2) the local density metric is too simple to find out the proper center(s) of the sparse cluster(s), and (3) it is not robust that parts of prominent density peaks are remotely assigned. This paper proposes improved density peaks clustering based on natural neighbor expanded group (DPC-NNEG). The cores of the proposed algorithm contain two parts: (1) define natural neighbor expanded (NNE) and natural neighbor expanded group (NNEG) and (2) divide all NNEGs into a goal number of sets as the final clustering result, according to the closeness degree of NNEGs. At the same time, the paper provides the measurement of the closeness degree. We compared the state of the art with our proposal in public datasets, including several complex and real datasets. Experiments show the effectiveness and robustness of the proposed algorithm.


---

## Body

## 1. Introduction

Clustering algorithm, usually as unsupervised learning, is a type of fundamental technique of machine learning [1]. It aims to divide a dataset into several subsets, which are also called categories, clusters, groups, etc, according to similarity, dissimilarity, or distance of samples. Hence, unlike supervised learning [2–18], clustering methods implement classification tasks without any prior knowledge and have been applied to image processing, pattern recognition, bioinformatics, data mining, the Internet of things, and other fields.Due to flexibility and validity, various clustering algorithms have been proposed one after another. Jain classified these methods into partitioning-based, model-based, hierarchical-based, grid-based, and density-based approaches [19]. Partitioning methods aim for grouping the dataset into a preset number of clusters via an iterative process. K-means [20, 21] and Fuzzy c-means [22, 23] are two famous partitioning-based clusterings. Although they are simple to understand and easy to implement, K-means is extremely sensitive to outliers and the selection of the initial cluster centers; besides, Fuzzy c-means approaches suffer from initial partition dependence [1]. Model-based clustering methods require one or more appropriate probability models to represent the dataset and often use the expectation-maximization approach to maximize the likelihood function [24]. Hierarchical-based approaches [25–28] partition the dataset into several categories using two opposite ways: top-down or bottom-up approach [23]. The first one considers the whole dataset as a cluster and split it into a suitable number of subclusters. Another regards each sample as a cluster and then merging these atomic clusters into more and more massive clusters. However, the effectiveness of hierarchical clustering algorithms depends on the type of distance measurement chosen for the clusters. Grid-based [29] and density-based [30, 31] approaches automatically determine the number of categories using suitable and preset parameters such as epsilon, min-pts, or others. While it is necessary to take a mass of argument adjustments to obtain optimal clustering results, these two types of algorithms generate noise at the cluster borders.To overcome the above shortcomings, recently, density peaks clustering [32] is proposed and based on the assumption that cluster centers are relatively denser and are far from each other. Using a suitable value of cutoff distance (namely, dc, the only parameter of DPC), this approach manually selects the appropriate center of each cluster from a decision graph. It then assigns each of the remaining elements to the nearest denser point (NDP) that is the nearest one of neighbors possessing bigger density than the assigned sample. It has many advantages, including higher efficiency in finding cluster centers, fewer parameters, no iterations, and no noise around the cluster border. However, the algorithm is still affected by the following defects:(1)
It is challenging to determine suitable dc. It must also be mentioned that the original DPC algorithm does not cover a reliable and specific method to ensure proper dc. Besides, this was demonstrated in several studies [33, 34] that DPC is sensitive to its parameter, and even when being normalized or using the relative percentage method, a small change in dc will still cause a conspicuous fluctuation in the result.(2)
The formula of local density is too simple to find out suitable center(s) of the sparse cluster(s) and is only useful in datasets with balanced density [33]. As shown in Figure 1(a), the Jain dataset has two clusters: the upper one is sparse and the lower one is denser. However, DPC overlooks the center of the upper cluster, instead of a prominent density peak of the lower cluster.(3)
Its assignment strategy is not robust [35]. Each point is assigned to its NDP, which results in some prominent density peaks (PDP) that are relatively bigger on density and δi value but not cluster centers are mistakenly attributed to a denser superordinate but are far away from each other. Accordingly, the subordinates of the incorrect-assigned PDP are portioned to an incorrect group. Figure 1(b) shows that we manually modify the center to the densest point of the upper cluster. However, the prominent local peak of the top cluster is assigned to its NDP belonging to the lower cluster, which leads to the incorrect assignment of its subordinates. And there is a distinct gap between the assignment path.Figure 1
Clustering results of DPC on the Jain dataset. The diverse colors present different clusters, and the stars mark the cluster centers and prominent local peaks. (a) Clustering results of DPC on Jain. (b) Clustering results of DPC with modified center.
(a)(b)To improve the performance of DPC and inspired by the idea of natural neighbor (NN) [36], we propose an improved density peaks clustering based on natural neighbor expanded group. The main innovations and improvements in our algorithm are as follows:(1)
Define natural neighbor expanded and natural neighbor expanded group based on the well-knownK-nearest neighbor method and its optimal version named natural neighbor. The concept of natural neighbor expanded is to absorb those close neighbors overlooked by the NN method. And NNEG is able to overcome the shortcoming of the remote assignment of PDP and mine the potential structure of data.(2)
Provide a density metric formula based on NNE. With the aid of NNE, the new measurement adaptively calculates the local density for each sample without any arguments, unlike one of the original DPC.(3)
Propose the measurement of the closeness degree of NNEGs that based on the mutual and pairwise neighbors which belonged to different NNEGs. Due to its application, all NNEGs are divided into the goal number of sets as the final clustering result.(4)
The time complexity isOKnlogn, where K is a constant, while the time complexity of all of the optimization algorithms and DPC is On2 [34].The remainder of this paper comprises four sections. Section2 describes the related works. Section 3 represents the DPC, NN method, and details of our algorithm. Section 4 presents the clustering results on our proposal and related works. In Section 5, we have a summary of the contributions and features of this paper.


## 2. Related Works

To improve the performance of the DPC algorithm, scholars proposed many optimization methods, as shown in Figure2. Xie et al. modified the density metric formula using the K-nearest neighbor (KNN), which used the number of the nearest neighbors to replace dc. Besides, they devised an entirely new assignment scheme based on fuzzy weighted K-nearest neighbors (FKNN-DPC) [33]. Furthermore, this method is easier to determine the suitable value of parameter. Lotfi et al. proposed a technique called IDPC [37]. The algorithm sorts samples using the local density and then apportions the labels of centers to their KNN to develop cluster cores. Finally, IDPC implements a specific propagation strategy to attach the remaining points with labels. Guo et al. capitalized on the linear regression method to fit the decision values of DPC with a preset proper dc required (DPC-LRA) and then choose the instances above the fitting function as the centers [38]. Ding et al. proposed an algorithm based on the generalized extreme value distribution (GEV) to fit the DPC decision values in the descending order (DPC-GVE). To reduce the time complexity, they also represented a substitution method using Chebyshev inequality (DPC-CI) [39]. Ni et al. presented the definitions of density gap and the density path, as well as a new threshold [35]. Instead of the decision graph of DPC, the proper value of dc is determined by manually observing a summary graph incorporating the density gaps calculated by different dc. The method, named PPC, is able to reduce obviously the difficulty on threshold determination. Jiang et al. provided a novel density peaks clustering algorithm based on K-nearest neighbors (DPC-KNN) to overcome the issue of the assignment [40]. In this method, there are two sets for each sample i: the first one is Si, which is composed of sample i and its KNN, while the second is Hi, which covers the data points possessing higher densities than sample i in the whole dataset. The cluster centers are determined via the decision graph of DPC, DPC-KNN assigns each remaindering sample to an element of Hi, who has the smallest distance from any member of Si to any member of Hi. Lotfi et al. improve DPC using density backbone and fuzzy neighborhood (DPC-DBFN). They use a fuzzy kernel for improving the separability of clusters. DPC-DBFN uses a density-based KNN graph for labeling backbones and effectively assigns correct category labels to samples around the group borders to effectively cluster data with various shapes and densities [34].Figure 2
Improvement methods of DPC.However, FKNN-DPC, IDPC, DPC-KNN, PPC, and DPC-DBFN require manual operations. And a preset dc is necessary for DPC-LRA, DPC-GVE, and DPC-CI. Moreover, DPC and these algorithms require the time complexity ofOn2 [34].


## 3. Methods

This section aims to present the short versions of the original DPC algorithm and NN method and show a detailed description of our method.


### 3.1. The Original DPC Algorithm

DPC is the basis on which cluster centers are relatively denser and are distant from each other. For a given datasetX=x1,x2,…,xn, where xi=xi1,xi2,…,xim,i=1,2,…,n, cluster centers are manually picked from the decision graph, which is two-dimensional with δi as the ordinate and the local density as the abscissa. Local density is to measure the neighbor number and distances of each sample in its neighborhood, which is a crucial concept of DPC. The ordinate δi is the distance between the sample i and its nearest denser point. Since the centers have relative lager density, each of them must be far away from their NDP, namely, has an enormous value of δi. In the two-dimensional coordinate system, cluster centers simultaneously possess big values of δi and local density and appear in the upper right corner of the graph. To measure the local density of each element, the author provides two formulae expressed as equations (1) and (2). δi is calculated by equation (3):(1)ρi=∑jℵdij−dc,ℵ⋅=1,⋅<0,0,⋅≥0,(2)ρi=∑jexp−dijdc2,where dij is the distance between pairwise elements i and j, dc is the cutoff distance, the only argument of DPC. Therefore, The DPC algorithm inherits a defect, where Gaussian kernel is sensitive to bandwidth:(3)δi=minj:ρi<ρjdij,if∃js.t.ρi<ρj,maxjdij,otherwise,As shown in equation (3), δi is the minimum distance between elements i and j whose density is higher than i. For i with the highest density, its δi is the maximum distance between i and j. After the cluster centers have been found, each remaining point is assigned to the same cluster as its nearest neighbor of higher density.


### 3.2. Natural Neighbor Method

K-nearest neighbor is a popular method in machine learning to complete the tasks of classification and clustering. However, the crucial argument K is preset manually. And natural neighbor is an adaptive method to find the relative near neighbors of each sample. The basic idea of NN is that samples of the dense regions have more neighbors; data points of the sparse area have relatively fewer neighbors; the outliers only have a few or no natural neighbors.In the datasetX, the authors assume that sij is the similarity between two points xi and xj. With the help of comparing the similarity, let find KNNxi,n denote the function of KNN searching which returns the rth nearest neighbor of the point xi, KNNrxi is a subset of X, and it is defined as follows:(4)KNNrxi=∪n=1rfind KNNxi,n.Definition 1.
(natural neighbor). Natural neighbor ofxi is defined as(5)xj∈NNxi⇔xi∈KNNλxj∧xj∈KNNλxi.Definition 2.
(natural neighbor eigenvalue). When the algorithm reaches the Stable Searching State, Natural Neighbor Eigenvalue (NaNE)λ is equal to the searching round r:(6)λ≜rr∈Nr|∀xi∃xjr∈N∧xi≠xj⟶xi∈KNNrxj∧xj∈KNNrxi.


### 3.3. The Proposed Method

In this section, the improved density peaks clustering based on natural neighbor expanded group is presented. Our method includes three major steps, including (1) calculating the local density of each sample according to the formula proposed, (2) determining natural neighbor expanded groups, and (3) grouping NNEGs into several sets as the final clustering result. The details of these steps are described in the remaining part of this section. To realize the above processing, we define the concept of natural neighbor expanded and then provide a straightforward but useful formula for local density. Besides, the definition of the natural neighbor expanded group is to reveal the structure of the dataset and divide the dataset into several local groups. For ensuring the grouping of NNEGs accuracy, we propose a measurement of closeness degree. And more details are presented in the rest content of this section.


#### 3.3.1. Basic Concepts

The NN method only considers the relationship of mutual neighbors and overlooks the impact of distance between samples. And to fit the density metric and the searching of density peaks, we propose the concept of Natural Neighbor Expanded.Definition 3.
(natural neighbor expanded). Natural Neighbor Expanded is defined as the following equation:(7)NNExi=KNN2Kixi,where we assume that the number of NN of xi is NNi and the NNithNNxi is the KithKNNrxi. Hence, Ki<=r. As shown in Figure 3, sample 1 is not the NN of sample 8, since it does not belong to the KNN68. However, sample 1 is closer to sample 8 than 14. Hence, for calculating the density more wholly and accurately, we expand the natural neighborhood of sample 8 to include samples 1, 2, and 7.
Natural Neighbor is the set of close neighbors. Still, as shown in equation (2), the local density formula measures not only the close neighbors whose distances to sample i are smaller than dc but also the rest samples of whole datasets. In the latter part, the distance to sample i being approximate to dc and the corresponding sample also impacts the density of i. Therefore, 2Ki of equation (7) is to cover the more secondary-adjacent samples beside the close neighbors. And the new local density formula based on NNE is shown as(8)ρi=∑j∈NNEximaxdistNNE−dijmaxdistNNE−mindistNNE,where NNE=∪i=1nNNExi, distNNE=∪i=1ndistNNExi, and distNNExi is the set of the distances of xi to all of the elements in NNExi. Inspired by the famous K-means method, equation (8) considers each point as core and calculates the sum of distances of it to its NNE. And the smaller the distance sum is, the more likely it is to be the local center.
Equation (2) maps the distances to similarities using the Gaussian kernel and calculates the accumulation sum of similarities linking to xi as ρi. Hence, equation (2) based on Gaussian kernel can resist the interference of outliers that possess vast distances to xi. However, the equation covers too many negligible samples that have the distances to sample i much bigger than dc because their contribution to density is tiny through the mapping of the Gaussian kernel. Moreover, it brings the original DPC to the time complexity of On2.
In contrast, our formula only considers NNE. It, therefore, also gets rid of the passive impact of outliers since they usually are distant from its nearest point and are not in any NNE(s) of other(s), at the same time, reduce the computational complexity. And unlike the Gaussian kernel mapping, equation (8) retains the original information of data, does not require any arguments, and avoids the sensitivity caused by dc.Figure 3
A schematic diagram with parts of samples and itsr equals 6. Sample 1 has six NNEs, including samples 2, 3, 4, 5, 6, and 7; sample 8 has six NNEs, including samples 9, 10, 11, 12, 13, and 14.Definition 4.
(natural neighbor expanded group). Natural Neighbor Expanded Group consists of a prominent density peak and its subordinates.
In our method, each point is assigned to the nearest denser point of its NNE. The assignment process is stored in a list: the index numbers represent the samples in the given dataset, respectively; each unit stores the index number of its superordinate one, and if the density of a sample is bigger than all of its NDP, the related unit saves 0. Namely, zero samples are prominent density peaks. The assignment divides the dataset into several NNEGs, adaptively.
Essentially, NNEGs reveal the potential structure of the dataset analyzed and are relatively tighter subcluster and local groups in the cluster of the Ground Truth. Due to the application of NNEG, each sample only points to a neighbor, and our method could avoid the long-distance assignment of the PDP.
As shown in Figure4, after NNEGs are determined, our method only needs to merge such local groups into the goal number of clusters and hence remove the operation of the center selection from the decision graph, which overcomes the mentioned issue of the density metric of DPC. To clarify the close relationship between NNEGs, we proposed the concept of the adjacent group graph.Figure 4
NNEGs of the Jain dataset. The diverse colors present different NNEGs, and the stars mark the zero samples.Definition 5.
(adjacent group graph).AGG=GV,E, where V=v1,v2,…,vk is a set of NNEGs, E=Evt,vτ|t≠τ,vt,vτ∈V, and Evt,vτ is a set of edges linked to NNEGs vt and vτ, and subject to(9)Evt,vτ=exi,xj|xi∈vt∧NNExj∧xj∈vτ∧NNExi.
Adjacent Group Graph usually is a multigraph, since there could be severalexi,xj between vt and vr. And the more the edges are, the closer the two groups are. Obviously, in Figure 4, there are no edges between the upper and the lower clusters. Moreover, the degree of closeness (DC) of the neighboring pairwise NNEGs is calculated by(10)DCvt,vτ=∑exi,xj∈Evt,vτwiwjmaxdistNNE−dijmaxdistNNE−mindistNNE,where wi=NNExi∩vt/NNExi and wj=NNExj∩vr/NNExj. As shown in equation (10), the formula of closeness degree is constituted with two parts: the weight and the similarity normalized. It is based on an assumption where the more compact the endpoints and their respective NNEGs are, the more reliable the edge is. wi represents the compactness between the sample xi and the group vt, viz., the bigger number of intersected elements of NNEGxi and vt means the relationship between them is intenser. To ensure wi∈0,1, the number of the elements intersected divided by NNExi.


#### 3.3.2. The Specific Processing

Inputs: datasetX, the goal number of clusters.Output: the clustering result.Step 1: Create ak-d tree. Search NNE for each sample using the k-d tree.Step 2: Calculate local density according to equation (8).Step 3: Determine NNEG according to Definition4.Step 4: Generate the Adjacent Group Graph as in Definition5, and find all edges of each pairwise NNEGs as equation (9).Step 5: Calculate the degree of closeness, according to equation (10).Step 6: Break up the original cluster containing all NNEGs into the goal number of sets, according to the closeness degree.To clarify Step 6 in detail, we present an example in Table1. As shown in Table 1 (A), there are five NNEGs in a dataset. And the closeness degrees of adjacent pairwise NNEGs are recorded. Assume the goal number is 2. Our method considers the whole dataset as a cluster, since DCv1,v2,DCv2,v3,DCv3,v4,DCv3,v5,DCv4,v5>0. We force the minimum DCv2,v3=0 as shown in Table 1 (B), which means those NNEGs are split into two parts: v1,v2 and v3,v4,v5, i.e., split is a for-loop operation which let the minimum DC=0 until the cluster number equals to the goal one.Table 1
An example of Step 6.And more details are as shown in the pseudocode. In the 6th line, AGG is a matrix where each row and each column correspond to one of NNEGs. In the 16th line, inspired by the Top-down hierarchical clustering, we consider the whole dataset as a cluster containing all NNEGs and break the weakest Evt,vτ in the AGG until the cluster number equals the goal, which corresponds to the process, Table 1 (A) and (B).


#### 3.3.3. Time Complexity Analyses

This section aims to analyze the computational complexity of our method, and suppose that the number of total samples in a dataset isn, the number of NNEG is equal to nNNEG, the goal number of clusters is G, the NDP of sample i is the nNDPith neighbor, and the biggest Ki equals K^. (Algorithm 1).Algorithm 1: DPC-NNEG.
Require: Dataset X=x1,x2,…,xn, the goal number of clusters GEnsure: The result of clustering: C=C1,C2,…,Cn(1)
Create ak-d tree;(2)
Search thek-d tree;(3)
Determine NN according to [34], and record Ki, which means NNExi determined;(4)
Calculate local densityρi according to equation (8).;(5)
Assign each point to its NDP of its NNE to generate several NNEGs;(6)
Create a matrix AGG = (NNEG, NNEG);(7)
fori = 1 : ndo(8)
fort = 1 : 2Kido(9)
if the tth NNE and sample i belongs to different NNEGs do(10)
Calculate the closeness degree of this edge, referring to equation (10);(11)
Add the DC of this edge to the corresponding unit of AGG;(12)
end if(13)
end for(14)
end for(15)
while the number of clusters does not equal G do(16)
Store zero in the unit with the min value but greater than zero;(17)
Count the number of clusters;(18)
end whileThe time complexity of creating a k-d tree isOnlogn [41]. It is demonstrated that determining NN for all samples also requires the cost of Onlogn [36]. And for finding NNE, we can record the Ki in the processing of searching NN. Hence, the searching NNE of a sample only needs to 2Ki times search operation, and its whole complexity for all samples is less than O2K^n. Our local density metric is based on NNE, and it is not necessary to generate a distance matrix and only needs to 2Ki times plus operations for each sample. Therefore, it is required with at most O2K^n for the time cost to calculate local densities of all instances. For each sample, the method takes nNDPi time search to find its NDP via the k-d tree in the round 2Ki, and nNDPi<=2Ki. In the process of generating each NNEG, we store the labels of its prominent density peak to a list where the first unit is any unallocated instance, and the end is an assigned one or prominent density peak. And the operation of storing labels of all samples only needs to the time cost of On. And the cost required is O2K^n on dividing a dataset into G NNEGs. In equations (9) and (10), exi,xj is requested and determined via searching the NNE of each sample to find the neighbors having different labels. Thus, for all edges, it is equal to O2K^n for the magnitude of how many times the searching operation is performed. Furthermore, the time complexity of grouping in the last step must be less than G. Overall, we can conclude that the time complexity of the entire algorithm is OKnlogn.


## 3.1. The Original DPC Algorithm

DPC is the basis on which cluster centers are relatively denser and are distant from each other. For a given datasetX=x1,x2,…,xn, where xi=xi1,xi2,…,xim,i=1,2,…,n, cluster centers are manually picked from the decision graph, which is two-dimensional with δi as the ordinate and the local density as the abscissa. Local density is to measure the neighbor number and distances of each sample in its neighborhood, which is a crucial concept of DPC. The ordinate δi is the distance between the sample i and its nearest denser point. Since the centers have relative lager density, each of them must be far away from their NDP, namely, has an enormous value of δi. In the two-dimensional coordinate system, cluster centers simultaneously possess big values of δi and local density and appear in the upper right corner of the graph. To measure the local density of each element, the author provides two formulae expressed as equations (1) and (2). δi is calculated by equation (3):(1)ρi=∑jℵdij−dc,ℵ⋅=1,⋅<0,0,⋅≥0,(2)ρi=∑jexp−dijdc2,where dij is the distance between pairwise elements i and j, dc is the cutoff distance, the only argument of DPC. Therefore, The DPC algorithm inherits a defect, where Gaussian kernel is sensitive to bandwidth:(3)δi=minj:ρi<ρjdij,if∃js.t.ρi<ρj,maxjdij,otherwise,As shown in equation (3), δi is the minimum distance between elements i and j whose density is higher than i. For i with the highest density, its δi is the maximum distance between i and j. After the cluster centers have been found, each remaining point is assigned to the same cluster as its nearest neighbor of higher density.


## 3.2. Natural Neighbor Method

K-nearest neighbor is a popular method in machine learning to complete the tasks of classification and clustering. However, the crucial argument K is preset manually. And natural neighbor is an adaptive method to find the relative near neighbors of each sample. The basic idea of NN is that samples of the dense regions have more neighbors; data points of the sparse area have relatively fewer neighbors; the outliers only have a few or no natural neighbors.In the datasetX, the authors assume that sij is the similarity between two points xi and xj. With the help of comparing the similarity, let find KNNxi,n denote the function of KNN searching which returns the rth nearest neighbor of the point xi, KNNrxi is a subset of X, and it is defined as follows:(4)KNNrxi=∪n=1rfind KNNxi,n.Definition 1.
(natural neighbor). Natural neighbor ofxi is defined as(5)xj∈NNxi⇔xi∈KNNλxj∧xj∈KNNλxi.Definition 2.
(natural neighbor eigenvalue). When the algorithm reaches the Stable Searching State, Natural Neighbor Eigenvalue (NaNE)λ is equal to the searching round r:(6)λ≜rr∈Nr|∀xi∃xjr∈N∧xi≠xj⟶xi∈KNNrxj∧xj∈KNNrxi.


## 3.3. The Proposed Method

In this section, the improved density peaks clustering based on natural neighbor expanded group is presented. Our method includes three major steps, including (1) calculating the local density of each sample according to the formula proposed, (2) determining natural neighbor expanded groups, and (3) grouping NNEGs into several sets as the final clustering result. The details of these steps are described in the remaining part of this section. To realize the above processing, we define the concept of natural neighbor expanded and then provide a straightforward but useful formula for local density. Besides, the definition of the natural neighbor expanded group is to reveal the structure of the dataset and divide the dataset into several local groups. For ensuring the grouping of NNEGs accuracy, we propose a measurement of closeness degree. And more details are presented in the rest content of this section.


### 3.3.1. Basic Concepts

The NN method only considers the relationship of mutual neighbors and overlooks the impact of distance between samples. And to fit the density metric and the searching of density peaks, we propose the concept of Natural Neighbor Expanded.Definition 3.
(natural neighbor expanded). Natural Neighbor Expanded is defined as the following equation:(7)NNExi=KNN2Kixi,where we assume that the number of NN of xi is NNi and the NNithNNxi is the KithKNNrxi. Hence, Ki<=r. As shown in Figure 3, sample 1 is not the NN of sample 8, since it does not belong to the KNN68. However, sample 1 is closer to sample 8 than 14. Hence, for calculating the density more wholly and accurately, we expand the natural neighborhood of sample 8 to include samples 1, 2, and 7.
Natural Neighbor is the set of close neighbors. Still, as shown in equation (2), the local density formula measures not only the close neighbors whose distances to sample i are smaller than dc but also the rest samples of whole datasets. In the latter part, the distance to sample i being approximate to dc and the corresponding sample also impacts the density of i. Therefore, 2Ki of equation (7) is to cover the more secondary-adjacent samples beside the close neighbors. And the new local density formula based on NNE is shown as(8)ρi=∑j∈NNEximaxdistNNE−dijmaxdistNNE−mindistNNE,where NNE=∪i=1nNNExi, distNNE=∪i=1ndistNNExi, and distNNExi is the set of the distances of xi to all of the elements in NNExi. Inspired by the famous K-means method, equation (8) considers each point as core and calculates the sum of distances of it to its NNE. And the smaller the distance sum is, the more likely it is to be the local center.
Equation (2) maps the distances to similarities using the Gaussian kernel and calculates the accumulation sum of similarities linking to xi as ρi. Hence, equation (2) based on Gaussian kernel can resist the interference of outliers that possess vast distances to xi. However, the equation covers too many negligible samples that have the distances to sample i much bigger than dc because their contribution to density is tiny through the mapping of the Gaussian kernel. Moreover, it brings the original DPC to the time complexity of On2.
In contrast, our formula only considers NNE. It, therefore, also gets rid of the passive impact of outliers since they usually are distant from its nearest point and are not in any NNE(s) of other(s), at the same time, reduce the computational complexity. And unlike the Gaussian kernel mapping, equation (8) retains the original information of data, does not require any arguments, and avoids the sensitivity caused by dc.Figure 3
A schematic diagram with parts of samples and itsr equals 6. Sample 1 has six NNEs, including samples 2, 3, 4, 5, 6, and 7; sample 8 has six NNEs, including samples 9, 10, 11, 12, 13, and 14.Definition 4.
(natural neighbor expanded group). Natural Neighbor Expanded Group consists of a prominent density peak and its subordinates.
In our method, each point is assigned to the nearest denser point of its NNE. The assignment process is stored in a list: the index numbers represent the samples in the given dataset, respectively; each unit stores the index number of its superordinate one, and if the density of a sample is bigger than all of its NDP, the related unit saves 0. Namely, zero samples are prominent density peaks. The assignment divides the dataset into several NNEGs, adaptively.
Essentially, NNEGs reveal the potential structure of the dataset analyzed and are relatively tighter subcluster and local groups in the cluster of the Ground Truth. Due to the application of NNEG, each sample only points to a neighbor, and our method could avoid the long-distance assignment of the PDP.
As shown in Figure4, after NNEGs are determined, our method only needs to merge such local groups into the goal number of clusters and hence remove the operation of the center selection from the decision graph, which overcomes the mentioned issue of the density metric of DPC. To clarify the close relationship between NNEGs, we proposed the concept of the adjacent group graph.Figure 4
NNEGs of the Jain dataset. The diverse colors present different NNEGs, and the stars mark the zero samples.Definition 5.
(adjacent group graph).AGG=GV,E, where V=v1,v2,…,vk is a set of NNEGs, E=Evt,vτ|t≠τ,vt,vτ∈V, and Evt,vτ is a set of edges linked to NNEGs vt and vτ, and subject to(9)Evt,vτ=exi,xj|xi∈vt∧NNExj∧xj∈vτ∧NNExi.
Adjacent Group Graph usually is a multigraph, since there could be severalexi,xj between vt and vr. And the more the edges are, the closer the two groups are. Obviously, in Figure 4, there are no edges between the upper and the lower clusters. Moreover, the degree of closeness (DC) of the neighboring pairwise NNEGs is calculated by(10)DCvt,vτ=∑exi,xj∈Evt,vτwiwjmaxdistNNE−dijmaxdistNNE−mindistNNE,where wi=NNExi∩vt/NNExi and wj=NNExj∩vr/NNExj. As shown in equation (10), the formula of closeness degree is constituted with two parts: the weight and the similarity normalized. It is based on an assumption where the more compact the endpoints and their respective NNEGs are, the more reliable the edge is. wi represents the compactness between the sample xi and the group vt, viz., the bigger number of intersected elements of NNEGxi and vt means the relationship between them is intenser. To ensure wi∈0,1, the number of the elements intersected divided by NNExi.


### 3.3.2. The Specific Processing

Inputs: datasetX, the goal number of clusters.Output: the clustering result.Step 1: Create ak-d tree. Search NNE for each sample using the k-d tree.Step 2: Calculate local density according to equation (8).Step 3: Determine NNEG according to Definition4.Step 4: Generate the Adjacent Group Graph as in Definition5, and find all edges of each pairwise NNEGs as equation (9).Step 5: Calculate the degree of closeness, according to equation (10).Step 6: Break up the original cluster containing all NNEGs into the goal number of sets, according to the closeness degree.To clarify Step 6 in detail, we present an example in Table1. As shown in Table 1 (A), there are five NNEGs in a dataset. And the closeness degrees of adjacent pairwise NNEGs are recorded. Assume the goal number is 2. Our method considers the whole dataset as a cluster, since DCv1,v2,DCv2,v3,DCv3,v4,DCv3,v5,DCv4,v5>0. We force the minimum DCv2,v3=0 as shown in Table 1 (B), which means those NNEGs are split into two parts: v1,v2 and v3,v4,v5, i.e., split is a for-loop operation which let the minimum DC=0 until the cluster number equals to the goal one.Table 1
An example of Step 6.And more details are as shown in the pseudocode. In the 6th line, AGG is a matrix where each row and each column correspond to one of NNEGs. In the 16th line, inspired by the Top-down hierarchical clustering, we consider the whole dataset as a cluster containing all NNEGs and break the weakest Evt,vτ in the AGG until the cluster number equals the goal, which corresponds to the process, Table 1 (A) and (B).


### 3.3.3. Time Complexity Analyses

This section aims to analyze the computational complexity of our method, and suppose that the number of total samples in a dataset isn, the number of NNEG is equal to nNNEG, the goal number of clusters is G, the NDP of sample i is the nNDPith neighbor, and the biggest Ki equals K^. (Algorithm 1).Algorithm 1: DPC-NNEG.
Require: Dataset X=x1,x2,…,xn, the goal number of clusters GEnsure: The result of clustering: C=C1,C2,…,Cn(1)
Create ak-d tree;(2)
Search thek-d tree;(3)
Determine NN according to [34], and record Ki, which means NNExi determined;(4)
Calculate local densityρi according to equation (8).;(5)
Assign each point to its NDP of its NNE to generate several NNEGs;(6)
Create a matrix AGG = (NNEG, NNEG);(7)
fori = 1 : ndo(8)
fort = 1 : 2Kido(9)
if the tth NNE and sample i belongs to different NNEGs do(10)
Calculate the closeness degree of this edge, referring to equation (10);(11)
Add the DC of this edge to the corresponding unit of AGG;(12)
end if(13)
end for(14)
end for(15)
while the number of clusters does not equal G do(16)
Store zero in the unit with the min value but greater than zero;(17)
Count the number of clusters;(18)
end whileThe time complexity of creating a k-d tree isOnlogn [41]. It is demonstrated that determining NN for all samples also requires the cost of Onlogn [36]. And for finding NNE, we can record the Ki in the processing of searching NN. Hence, the searching NNE of a sample only needs to 2Ki times search operation, and its whole complexity for all samples is less than O2K^n. Our local density metric is based on NNE, and it is not necessary to generate a distance matrix and only needs to 2Ki times plus operations for each sample. Therefore, it is required with at most O2K^n for the time cost to calculate local densities of all instances. For each sample, the method takes nNDPi time search to find its NDP via the k-d tree in the round 2Ki, and nNDPi<=2Ki. In the process of generating each NNEG, we store the labels of its prominent density peak to a list where the first unit is any unallocated instance, and the end is an assigned one or prominent density peak. And the operation of storing labels of all samples only needs to the time cost of On. And the cost required is O2K^n on dividing a dataset into G NNEGs. In equations (9) and (10), exi,xj is requested and determined via searching the NNE of each sample to find the neighbors having different labels. Thus, for all edges, it is equal to O2K^n for the magnitude of how many times the searching operation is performed. Furthermore, the time complexity of grouping in the last step must be less than G. Overall, we can conclude that the time complexity of the entire algorithm is OKnlogn.


## 3.3.1. Basic Concepts

The NN method only considers the relationship of mutual neighbors and overlooks the impact of distance between samples. And to fit the density metric and the searching of density peaks, we propose the concept of Natural Neighbor Expanded.Definition 3.
(natural neighbor expanded). Natural Neighbor Expanded is defined as the following equation:(7)NNExi=KNN2Kixi,where we assume that the number of NN of xi is NNi and the NNithNNxi is the KithKNNrxi. Hence, Ki<=r. As shown in Figure 3, sample 1 is not the NN of sample 8, since it does not belong to the KNN68. However, sample 1 is closer to sample 8 than 14. Hence, for calculating the density more wholly and accurately, we expand the natural neighborhood of sample 8 to include samples 1, 2, and 7.
Natural Neighbor is the set of close neighbors. Still, as shown in equation (2), the local density formula measures not only the close neighbors whose distances to sample i are smaller than dc but also the rest samples of whole datasets. In the latter part, the distance to sample i being approximate to dc and the corresponding sample also impacts the density of i. Therefore, 2Ki of equation (7) is to cover the more secondary-adjacent samples beside the close neighbors. And the new local density formula based on NNE is shown as(8)ρi=∑j∈NNEximaxdistNNE−dijmaxdistNNE−mindistNNE,where NNE=∪i=1nNNExi, distNNE=∪i=1ndistNNExi, and distNNExi is the set of the distances of xi to all of the elements in NNExi. Inspired by the famous K-means method, equation (8) considers each point as core and calculates the sum of distances of it to its NNE. And the smaller the distance sum is, the more likely it is to be the local center.
Equation (2) maps the distances to similarities using the Gaussian kernel and calculates the accumulation sum of similarities linking to xi as ρi. Hence, equation (2) based on Gaussian kernel can resist the interference of outliers that possess vast distances to xi. However, the equation covers too many negligible samples that have the distances to sample i much bigger than dc because their contribution to density is tiny through the mapping of the Gaussian kernel. Moreover, it brings the original DPC to the time complexity of On2.
In contrast, our formula only considers NNE. It, therefore, also gets rid of the passive impact of outliers since they usually are distant from its nearest point and are not in any NNE(s) of other(s), at the same time, reduce the computational complexity. And unlike the Gaussian kernel mapping, equation (8) retains the original information of data, does not require any arguments, and avoids the sensitivity caused by dc.Figure 3
A schematic diagram with parts of samples and itsr equals 6. Sample 1 has six NNEs, including samples 2, 3, 4, 5, 6, and 7; sample 8 has six NNEs, including samples 9, 10, 11, 12, 13, and 14.Definition 4.
(natural neighbor expanded group). Natural Neighbor Expanded Group consists of a prominent density peak and its subordinates.
In our method, each point is assigned to the nearest denser point of its NNE. The assignment process is stored in a list: the index numbers represent the samples in the given dataset, respectively; each unit stores the index number of its superordinate one, and if the density of a sample is bigger than all of its NDP, the related unit saves 0. Namely, zero samples are prominent density peaks. The assignment divides the dataset into several NNEGs, adaptively.
Essentially, NNEGs reveal the potential structure of the dataset analyzed and are relatively tighter subcluster and local groups in the cluster of the Ground Truth. Due to the application of NNEG, each sample only points to a neighbor, and our method could avoid the long-distance assignment of the PDP.
As shown in Figure4, after NNEGs are determined, our method only needs to merge such local groups into the goal number of clusters and hence remove the operation of the center selection from the decision graph, which overcomes the mentioned issue of the density metric of DPC. To clarify the close relationship between NNEGs, we proposed the concept of the adjacent group graph.Figure 4
NNEGs of the Jain dataset. The diverse colors present different NNEGs, and the stars mark the zero samples.Definition 5.
(adjacent group graph).AGG=GV,E, where V=v1,v2,…,vk is a set of NNEGs, E=Evt,vτ|t≠τ,vt,vτ∈V, and Evt,vτ is a set of edges linked to NNEGs vt and vτ, and subject to(9)Evt,vτ=exi,xj|xi∈vt∧NNExj∧xj∈vτ∧NNExi.
Adjacent Group Graph usually is a multigraph, since there could be severalexi,xj between vt and vr. And the more the edges are, the closer the two groups are. Obviously, in Figure 4, there are no edges between the upper and the lower clusters. Moreover, the degree of closeness (DC) of the neighboring pairwise NNEGs is calculated by(10)DCvt,vτ=∑exi,xj∈Evt,vτwiwjmaxdistNNE−dijmaxdistNNE−mindistNNE,where wi=NNExi∩vt/NNExi and wj=NNExj∩vr/NNExj. As shown in equation (10), the formula of closeness degree is constituted with two parts: the weight and the similarity normalized. It is based on an assumption where the more compact the endpoints and their respective NNEGs are, the more reliable the edge is. wi represents the compactness between the sample xi and the group vt, viz., the bigger number of intersected elements of NNEGxi and vt means the relationship between them is intenser. To ensure wi∈0,1, the number of the elements intersected divided by NNExi.


## 3.3.2. The Specific Processing

Inputs: datasetX, the goal number of clusters.Output: the clustering result.Step 1: Create ak-d tree. Search NNE for each sample using the k-d tree.Step 2: Calculate local density according to equation (8).Step 3: Determine NNEG according to Definition4.Step 4: Generate the Adjacent Group Graph as in Definition5, and find all edges of each pairwise NNEGs as equation (9).Step 5: Calculate the degree of closeness, according to equation (10).Step 6: Break up the original cluster containing all NNEGs into the goal number of sets, according to the closeness degree.To clarify Step 6 in detail, we present an example in Table1. As shown in Table 1 (A), there are five NNEGs in a dataset. And the closeness degrees of adjacent pairwise NNEGs are recorded. Assume the goal number is 2. Our method considers the whole dataset as a cluster, since DCv1,v2,DCv2,v3,DCv3,v4,DCv3,v5,DCv4,v5>0. We force the minimum DCv2,v3=0 as shown in Table 1 (B), which means those NNEGs are split into two parts: v1,v2 and v3,v4,v5, i.e., split is a for-loop operation which let the minimum DC=0 until the cluster number equals to the goal one.Table 1
An example of Step 6.And more details are as shown in the pseudocode. In the 6th line, AGG is a matrix where each row and each column correspond to one of NNEGs. In the 16th line, inspired by the Top-down hierarchical clustering, we consider the whole dataset as a cluster containing all NNEGs and break the weakest Evt,vτ in the AGG until the cluster number equals the goal, which corresponds to the process, Table 1 (A) and (B).


## 3.3.3. Time Complexity Analyses

This section aims to analyze the computational complexity of our method, and suppose that the number of total samples in a dataset isn, the number of NNEG is equal to nNNEG, the goal number of clusters is G, the NDP of sample i is the nNDPith neighbor, and the biggest Ki equals K^. (Algorithm 1).Algorithm 1: DPC-NNEG.
Require: Dataset X=x1,x2,…,xn, the goal number of clusters GEnsure: The result of clustering: C=C1,C2,…,Cn(1)
Create ak-d tree;(2)
Search thek-d tree;(3)
Determine NN according to [34], and record Ki, which means NNExi determined;(4)
Calculate local densityρi according to equation (8).;(5)
Assign each point to its NDP of its NNE to generate several NNEGs;(6)
Create a matrix AGG = (NNEG, NNEG);(7)
fori = 1 : ndo(8)
fort = 1 : 2Kido(9)
if the tth NNE and sample i belongs to different NNEGs do(10)
Calculate the closeness degree of this edge, referring to equation (10);(11)
Add the DC of this edge to the corresponding unit of AGG;(12)
end if(13)
end for(14)
end for(15)
while the number of clusters does not equal G do(16)
Store zero in the unit with the min value but greater than zero;(17)
Count the number of clusters;(18)
end whileThe time complexity of creating a k-d tree isOnlogn [41]. It is demonstrated that determining NN for all samples also requires the cost of Onlogn [36]. And for finding NNE, we can record the Ki in the processing of searching NN. Hence, the searching NNE of a sample only needs to 2Ki times search operation, and its whole complexity for all samples is less than O2K^n. Our local density metric is based on NNE, and it is not necessary to generate a distance matrix and only needs to 2Ki times plus operations for each sample. Therefore, it is required with at most O2K^n for the time cost to calculate local densities of all instances. For each sample, the method takes nNDPi time search to find its NDP via the k-d tree in the round 2Ki, and nNDPi<=2Ki. In the process of generating each NNEG, we store the labels of its prominent density peak to a list where the first unit is any unallocated instance, and the end is an assigned one or prominent density peak. And the operation of storing labels of all samples only needs to the time cost of On. And the cost required is O2K^n on dividing a dataset into G NNEGs. In equations (9) and (10), exi,xj is requested and determined via searching the NNE of each sample to find the neighbors having different labels. Thus, for all edges, it is equal to O2K^n for the magnitude of how many times the searching operation is performed. Furthermore, the time complexity of grouping in the last step must be less than G. Overall, we can conclude that the time complexity of the entire algorithm is OKnlogn.


## 4. Results

In this section, several datasets are used to evaluate the performance of our method in comparison with some state-of-the-art techniques such as DPC-DBFN [34], DPC-KNN [40], IDPC [37], and FKNN-DPC [33]. The experiments are performed on a computer with a Windows 10, Intel (R) Core (TM) i7-8750H, 16 GB memory, and Matlab 2016b. The results represented are measured by several performance metrics, including Normalized Mutual Information (NMI) [42], Rand Index (RI) [43], and the Adjusted Rand Index (ARI) [44]. In this section, the similarity between points is measured using the Euclidean distance metric.


### 4.1. Datasets

In this paper, all tested datasets include three low-dimensional datasets and five high-dimensional datasets, which are public and from UCI. The two-dimensional datasets have different numbers of samples and different objective distributions. The DMI512 dataset containing 1024 elements with 512-dimensional features, which belonged to 16 Gaussian clusters sampled from a Gaussian distribution, is often used to test algorithm performance in high-dimensional space. Experiments of the four datasets, including Statlog (Shuttle), Abalone, Wine Quality, and Libras Movement, are applications of our method on Physical (the positioning of radiators in the Space Shuttle), Population Biology, Model Wine Preferences, and Hand Movement Recognition, respectively. And more details are presented in Table2.Table 2
Detailed information on tested datasets.
Dataset#Instance#Attribute#ClusterJain37327Flame24022Spiral30023Statlog (shuttle)5800097Abalone4177728Wine quality4898117DIM512102451216Libras movement3609015To reduce the influence of dimension weights and ensure the validity of the experimental comparison, we processed each dataset and normalized all dataset tested. The normalization formula is as follows:(11)xij′=xij−minxjmaxxj−minxj,where xij is the jth feature value of the ith sample, while maxxj and minxj represent the maximum and minimum values of the jth feature, respectively.


### 4.2. Evaluation Measures

We tested our algorithm and several related works on the above datasets. For intuitive comparison, we chose RI, ARI, and NMI to measure the clustering results.The RI formula is shown in(12)RI=TP+TNCn2,where TP indicates true positive, TN indicates real negative, and the denominator Cn2 is the total number of sample pairs in a dataset consisting of n samples.The ARI formula is shown in(13)ARI=RI−ERIMAXRI−ERI,where ERI represents the expectations of RI.The NMI formula is shown in(14)NMI=−2MIA,BHA+HB,where HA=∑i=1APilog2Pi, HB=∑i=1BPjlog2Pj, EMIA,B represents the expectations of MIA,B, and MIA,B is expressed as(15)MIA,B=∑i=1A∑j=1BPi,jlog2Pi,jPiPj,where Pi=Ai/n, Pj=Bj/n, Pi,j=Ai∩Bj/n, A=Ai|i=1,2,…,A, and B=Bj|j=1,2,…,B. A and B represent two allocation methods for a dataset containing n elements, and Ai and Bj are clusters. In experimental verification, let A and B be the original labels and the clustering results of an algorithm, respectively. If the clustering results are as same as the real labels, the three metrics take the value of 1, and if the clustering results are entirely different from the labels, the values will be equal to 0.


### 4.3. Results

This section aims to show the detailed clustering results and evaluate the performance of different clustering algorithms on the various datasets. Tables3–5 compare the performance of our method with DPC-DBFN, DPC-KNN, IDPC, and FKNN-DPC in terms of NMI, RI, and ARI measures, respectively. All these methods are using the KNN method, and the number of nearest neighbors (K) can be set from 1 to n. In these tables, the numbers in the parenthesis are the value of K, where the corresponding algorithm obtains the results represented, and boldface marks the best results.Table 3
Clustering results measured by NMI.
DatasetDPC-KNNIDPCFKNN-DPCDPC-DBFNDPC-NNEGJain1.0000 (9)1.0000 (9)1.0000 (10)1.0000 (9)1.0000Flame1.0000 (4)1.0000 (7)1.0000 (6)1.0000 (9)1.0000Spiral1.0000 (7)1.0000 (5)1.0000 (5)1.0000 (4)1.0000Statlog (shuttle)0.3734 (150)0.1552 (90)0.4226 (150)0.5490 (7)0.6101Abalone0.1780 (50)0.1791 (758)0.1828 (2)0.1846 (2)0.1852Wine quality0.0359 (28)0.0339 (68)0.0364 (244)0.0701 (1)0.0935DIM5121.0000 (10)1.0000 (15)1.0000 (8)1.0000 (9)1.0000Libras movement0.5287 (53)0.5697 (5)0.5607 (11)0.5848 (6)0.5855Table 4
Clustering results measured by RI.
DatasetDPC-KNNIDPCFKNN-DPCDPC-DBFNDPC-NNEGJain1.0000 (9)1.0000 (9)1.0000 (10)1.0000 (9)1.0000Flame1.0000 (4)1.0000 (7)1.0000 (6)1.0000 (9)1.0000Spiral1.0000 (7)1.0000 (5)1.0000 (5)1.0000 (4)1.0000Statlog (shuttle)0.6780 (150)0.4180 (90)0.7274 (150)0.7512 (7)0.7814Abalone0.8042 (14)0.8236 (60)0.7635 (5)0.8354 (500)0.8428Wine quality0.6277 (52)0.6063 (35)0.5107 (3)0.5578 (1)0.5751DIM5121.0000 (10)1.0000 (15)1.0000 (8)1.0000 (9)1.0000Libras movement0.8839 (4)0.9089 (9)0.8995 (10)0.8945 (6)0.9187Table 5
Clustering results measured by ARI.
DatasetDPC-KNNIDPCFKNN-DPCDPC-DBFNDPC-NNEGJain1.0000 (9)1.0000 (9)1.0000 (10)1.0000 (9)1.0000Flame1.0000 (4)1.0000 (7)1.0000 (6)1.0000 (9)1.0000Spiral1.0000 (7)1.0000 (5)1.0000 (5)1.0000 (4)1.0000Statlog (shuttle)0.3396 (150)0.1049 (90)0.3197 (150)0.3584 (7)0.5688Abalone0.0567 (3)0.0589 (10)0.0553 (7)0.0654 (2)0.0657Wine quality0.0275 (25)0.0356 (64)0.0214 (3)0.0575 (1)0.0511DIM5121.0000 (10)1.0000 (15)1.0000 (8)1.0000 (9)1.0000Libras movement0.2492 (19)0.3337 (9)0.2846 (11)0.3130 (6)0.4862The Jain dataset has 373 points and two clusters: the upper one and the lower one. As shown in Figure5, DPC-NNEG divides the dataset into nineteen NNEGs and then successfully and efficiently groups them into two sets since there are no edges between the two clusters. Homoplastically, as shown in Figure 6, our algorithm divides the Spiral dataset into several local groups and subsequently merges all NNEGs accurately into the goal number of clusters.Figure 5
The clustering results of the Jain dataset. The diverse colors present different NNEGs and clusters, and the stars mark the zero samples. (a) NNEGs of Jain. (b) DPC-NNEG on Jain. (c) Ground truth.
(a)(b)(c)Figure 6
The clustering results of the Spiral dataset. The diverse colors present different NNEGs, and the stars mark the zero samples. (a) NNEGs of spiral. (b) DPC-NNEG on spiral. (c) Ground truth.
(a)(b)(c)Unlike Jain and Spiral, as shown in Figure7, the Flame dataset containing 240 data points has no clear gap between the two adjacent clusters. Hence, it is more sensitive to the value of dc of the DPC algorithm because a tiny change in dc will cause the border point is assigned to another cluster. However, our method not only partitions all samples into eight NNEGs but also measures the tightness between different groups accurately, which realizes the correct grouping of those local groups. And Figure 7 shows that the clustering result of Flame by DPC-NNEG is consonant with the Ground Truth.Figure 7
The clustering results of the Flame dataset. The diverse colors present different NNEGs, and the stars mark the zero samples. (a) NNEGs of flame. (b) DPC-NNEG on spiral. (c) Ground truth.
(a)(b)(c)As shown in Tables3–5, there is no difference in performance among our algorithm, DPC-DBFN, DPC-KNN, IDPC, and FKNN-DPC in three two-dimensional datasets. However, as shown in Table 2, the clustering results of more complex high-dimensional datasets show the outperformance of our method: DPC-NNEG gains the best marks measured by NMI in all datasets. For example, the results of DPC-NNEG in the Statlog (Shuttle), Abalone, Wine Quality, DIM512, and Libras Movement datasets are 0.6101, 0.1852, 0.0935, 1.0000, and 0.5855, respectively. Moreover, its improvements to the second-best method (in %) for Statlog (Shuttle), Abalone, Wine Quality, and Libras Movement datasets are respectively 11.13, 0.32, 33.38, and 0.12.Tables4 and 5 show similar results, respectively, measured by RI and ARI. These results also demonstrate that the proposed method, in most cases, obtains the biggest values of NMI except the Wine Quality dataset. Hence, based on these results, it can be concluded that DPC-NNEG has given an overall excellent performance in clustering.


## 4.1. Datasets

In this paper, all tested datasets include three low-dimensional datasets and five high-dimensional datasets, which are public and from UCI. The two-dimensional datasets have different numbers of samples and different objective distributions. The DMI512 dataset containing 1024 elements with 512-dimensional features, which belonged to 16 Gaussian clusters sampled from a Gaussian distribution, is often used to test algorithm performance in high-dimensional space. Experiments of the four datasets, including Statlog (Shuttle), Abalone, Wine Quality, and Libras Movement, are applications of our method on Physical (the positioning of radiators in the Space Shuttle), Population Biology, Model Wine Preferences, and Hand Movement Recognition, respectively. And more details are presented in Table2.Table 2
Detailed information on tested datasets.
Dataset#Instance#Attribute#ClusterJain37327Flame24022Spiral30023Statlog (shuttle)5800097Abalone4177728Wine quality4898117DIM512102451216Libras movement3609015To reduce the influence of dimension weights and ensure the validity of the experimental comparison, we processed each dataset and normalized all dataset tested. The normalization formula is as follows:(11)xij′=xij−minxjmaxxj−minxj,where xij is the jth feature value of the ith sample, while maxxj and minxj represent the maximum and minimum values of the jth feature, respectively.


## 4.2. Evaluation Measures

We tested our algorithm and several related works on the above datasets. For intuitive comparison, we chose RI, ARI, and NMI to measure the clustering results.The RI formula is shown in(12)RI=TP+TNCn2,where TP indicates true positive, TN indicates real negative, and the denominator Cn2 is the total number of sample pairs in a dataset consisting of n samples.The ARI formula is shown in(13)ARI=RI−ERIMAXRI−ERI,where ERI represents the expectations of RI.The NMI formula is shown in(14)NMI=−2MIA,BHA+HB,where HA=∑i=1APilog2Pi, HB=∑i=1BPjlog2Pj, EMIA,B represents the expectations of MIA,B, and MIA,B is expressed as(15)MIA,B=∑i=1A∑j=1BPi,jlog2Pi,jPiPj,where Pi=Ai/n, Pj=Bj/n, Pi,j=Ai∩Bj/n, A=Ai|i=1,2,…,A, and B=Bj|j=1,2,…,B. A and B represent two allocation methods for a dataset containing n elements, and Ai and Bj are clusters. In experimental verification, let A and B be the original labels and the clustering results of an algorithm, respectively. If the clustering results are as same as the real labels, the three metrics take the value of 1, and if the clustering results are entirely different from the labels, the values will be equal to 0.


## 4.3. Results

This section aims to show the detailed clustering results and evaluate the performance of different clustering algorithms on the various datasets. Tables3–5 compare the performance of our method with DPC-DBFN, DPC-KNN, IDPC, and FKNN-DPC in terms of NMI, RI, and ARI measures, respectively. All these methods are using the KNN method, and the number of nearest neighbors (K) can be set from 1 to n. In these tables, the numbers in the parenthesis are the value of K, where the corresponding algorithm obtains the results represented, and boldface marks the best results.Table 3
Clustering results measured by NMI.
DatasetDPC-KNNIDPCFKNN-DPCDPC-DBFNDPC-NNEGJain1.0000 (9)1.0000 (9)1.0000 (10)1.0000 (9)1.0000Flame1.0000 (4)1.0000 (7)1.0000 (6)1.0000 (9)1.0000Spiral1.0000 (7)1.0000 (5)1.0000 (5)1.0000 (4)1.0000Statlog (shuttle)0.3734 (150)0.1552 (90)0.4226 (150)0.5490 (7)0.6101Abalone0.1780 (50)0.1791 (758)0.1828 (2)0.1846 (2)0.1852Wine quality0.0359 (28)0.0339 (68)0.0364 (244)0.0701 (1)0.0935DIM5121.0000 (10)1.0000 (15)1.0000 (8)1.0000 (9)1.0000Libras movement0.5287 (53)0.5697 (5)0.5607 (11)0.5848 (6)0.5855Table 4
Clustering results measured by RI.
DatasetDPC-KNNIDPCFKNN-DPCDPC-DBFNDPC-NNEGJain1.0000 (9)1.0000 (9)1.0000 (10)1.0000 (9)1.0000Flame1.0000 (4)1.0000 (7)1.0000 (6)1.0000 (9)1.0000Spiral1.0000 (7)1.0000 (5)1.0000 (5)1.0000 (4)1.0000Statlog (shuttle)0.6780 (150)0.4180 (90)0.7274 (150)0.7512 (7)0.7814Abalone0.8042 (14)0.8236 (60)0.7635 (5)0.8354 (500)0.8428Wine quality0.6277 (52)0.6063 (35)0.5107 (3)0.5578 (1)0.5751DIM5121.0000 (10)1.0000 (15)1.0000 (8)1.0000 (9)1.0000Libras movement0.8839 (4)0.9089 (9)0.8995 (10)0.8945 (6)0.9187Table 5
Clustering results measured by ARI.
DatasetDPC-KNNIDPCFKNN-DPCDPC-DBFNDPC-NNEGJain1.0000 (9)1.0000 (9)1.0000 (10)1.0000 (9)1.0000Flame1.0000 (4)1.0000 (7)1.0000 (6)1.0000 (9)1.0000Spiral1.0000 (7)1.0000 (5)1.0000 (5)1.0000 (4)1.0000Statlog (shuttle)0.3396 (150)0.1049 (90)0.3197 (150)0.3584 (7)0.5688Abalone0.0567 (3)0.0589 (10)0.0553 (7)0.0654 (2)0.0657Wine quality0.0275 (25)0.0356 (64)0.0214 (3)0.0575 (1)0.0511DIM5121.0000 (10)1.0000 (15)1.0000 (8)1.0000 (9)1.0000Libras movement0.2492 (19)0.3337 (9)0.2846 (11)0.3130 (6)0.4862The Jain dataset has 373 points and two clusters: the upper one and the lower one. As shown in Figure5, DPC-NNEG divides the dataset into nineteen NNEGs and then successfully and efficiently groups them into two sets since there are no edges between the two clusters. Homoplastically, as shown in Figure 6, our algorithm divides the Spiral dataset into several local groups and subsequently merges all NNEGs accurately into the goal number of clusters.Figure 5
The clustering results of the Jain dataset. The diverse colors present different NNEGs and clusters, and the stars mark the zero samples. (a) NNEGs of Jain. (b) DPC-NNEG on Jain. (c) Ground truth.
(a)(b)(c)Figure 6
The clustering results of the Spiral dataset. The diverse colors present different NNEGs, and the stars mark the zero samples. (a) NNEGs of spiral. (b) DPC-NNEG on spiral. (c) Ground truth.
(a)(b)(c)Unlike Jain and Spiral, as shown in Figure7, the Flame dataset containing 240 data points has no clear gap between the two adjacent clusters. Hence, it is more sensitive to the value of dc of the DPC algorithm because a tiny change in dc will cause the border point is assigned to another cluster. However, our method not only partitions all samples into eight NNEGs but also measures the tightness between different groups accurately, which realizes the correct grouping of those local groups. And Figure 7 shows that the clustering result of Flame by DPC-NNEG is consonant with the Ground Truth.Figure 7
The clustering results of the Flame dataset. The diverse colors present different NNEGs, and the stars mark the zero samples. (a) NNEGs of flame. (b) DPC-NNEG on spiral. (c) Ground truth.
(a)(b)(c)As shown in Tables3–5, there is no difference in performance among our algorithm, DPC-DBFN, DPC-KNN, IDPC, and FKNN-DPC in three two-dimensional datasets. However, as shown in Table 2, the clustering results of more complex high-dimensional datasets show the outperformance of our method: DPC-NNEG gains the best marks measured by NMI in all datasets. For example, the results of DPC-NNEG in the Statlog (Shuttle), Abalone, Wine Quality, DIM512, and Libras Movement datasets are 0.6101, 0.1852, 0.0935, 1.0000, and 0.5855, respectively. Moreover, its improvements to the second-best method (in %) for Statlog (Shuttle), Abalone, Wine Quality, and Libras Movement datasets are respectively 11.13, 0.32, 33.38, and 0.12.Tables4 and 5 show similar results, respectively, measured by RI and ARI. These results also demonstrate that the proposed method, in most cases, obtains the biggest values of NMI except the Wine Quality dataset. Hence, based on these results, it can be concluded that DPC-NNEG has given an overall excellent performance in clustering.


## 5. Conclusions and Future Works

This paper proposed an efficient clustering algorithm called DPC-NNEG, which can easily split a dataset into local groups and then merge those groups into the goal number of clusters with various densities, shapes, and sizes. The proposed method aims at clustering the data by three major steps: calculating the local density of each sample, identifying natural neighbor expanded groups, and merge those groups into clusters. The first step utilizes the natural neighbor method in the local density calculation. And it is entirely different from the formula of the original DPC and could avoid the impact of outliners and reduce the sensitivity of dc. In the second step, the NNE defined is used to mine the potential structure of data, which is useful to divide the dataset into several relatively more compact local groups called NNEGs. And the last step groups all NNEGs into the goal number of clusters using the proposed formula of the closeness degree of local groups. And the application of the second and third steps not only overcomes the issue of remote assignment of the prominent density peaks but also removes the step of center selection in the original DPC. The effectiveness of the method proposed was verified on several datasets. The results show that our approach is more effective against the related improvement algorithms of DPC. In future work, we shall contribute to developing the concept of NNE to find a more suitable method for secondary-adjacent samples, instead of the given and fixated parameter2Ki in equation (7). Fuzzy theory is a proper technique to mine relatively adjacent samples, in which NNE is used to construct the membership function of closeness, and then deduce the functions of secondary-adjacent samples and remote samples.



---

*Source: 8864239-2020-10-23.xml*