A domain density peak clustering algorithm based on natural neighbor

Abstract

Density peaks clustering (DPC) is as an efficient algorithm due for the cluster centers can be found quickly. However, this approach has some disadvantages. Firstly, it is sensitive to the cutoff distance; secondly, the neighborhood information of the data is not considered when calculating the local density; thirdly, during allocation, one assignment error may cause more errors. Considering these problems, this study proposes a domain density peak clustering algorithm based on natural neighbor (NDDC). At first, natural neighbor is introduced innovatively to obtain the neighborhood of each point. Then, based on the natural neighbors, several new methods are proposed to calculate corresponding metrics of the points to identify the centers. At last, this study proposes a new two-step assignment strategy to reduce the probability of data misclassification. A series of experiments are conducted that the NDDC offers higher accuracy and robustness than other methods.

Keywords

Density-based clustering natural neighbors local density peaks assignment strategy

1. Introduction

As an unsupervised process, clustering aims to partition data points to different clusters according to the similarity between data samples. The data in the same category should be as similar as possible, and those in different categories should be as different as possible. Clustering has been widely used in image processing [1], medical information analysis [2], pattern recognition [3], geography [4], and biological information analysis [5]. In the past few decades, numerous clustering methods have been proposed, including partition-based clustering [6, 7, 8], grid-based clustering [9, 10], hierarchical clustering [11, 12], model-based clustering [13, 14], depth clustering [15, 16], and density-based clustering [17]. Density-based clustering methods have become a research hotspot because this method can process clusters of any shape and number. The most representative method is density-based spatial clustering of applications with noise (DBSCAN) [18], which can identify clusters and filter outliers without specifying the number of clusters. However, it is sensitive to the parameter settings, such as the radius and density. The ordering points used to identify the clustering structure (OPTICS) algorithm is an improvement of DBSCAN and it can obtain clusters of different densities by ordering the queue of the output [19]. Subsequently, many variants of these two methods have been developed and discussed to improve the clustering performance [20, 21].

In 2014, Rodriguez and Laio presented a novel density-based algorithm called density peak clustering (DPC) [22]. It uses the local density and $\delta$ distance to describe the data and create a decision graph to find the cluster centers rapidly. Although this algorithm can handle datasets of any shape, the method of calculating the local density is relatively simple because it is affected by the cutoff distance and does not consider the neighborhood relationship of the data. The k-nearest neighbor (KNN) method has been combined with the DPC to solve this problem and consider the neighborhood relationship when calculating the metrics [23, 24, 25, 26]. However, it is challenging to choose the optimum value of k in the KNN method. When the k value is too small, the neighborhood relationship is ignored, and the data points with the same properties will be misclassified into different clusters. In contrast, when the value is too large, data points with different properties will be misclassified into the same cluster. Recently, a new neighborhood relationship expression, i.e., the natural neighbor, has provided a good solution to tackle this issue. It is an adaptive neighborhood relationship that can solve the problem of neighborhood selection and accurately reflect the relationship between the data [27].

In summary, the existing methods have two limitations: Firstly, the DPC algorithm and its improved are sensitive to parameters, the changes of $d_{c}$ value in the original DPC algorithm and K value in the improved algorithm will greatly affect the clustering result. Secondly, During the allocation phase of the DPC, “domino effect” may occur, where one allocation error can lead to additional errors. In this paper, inspired by the concept of natural neighbors, we propose a novel natural neighbor-based domain density peak clustering algorithm (NDDC). Firstly, we adaptively obtain the global natural eigenvalues and the natural neighborhood of each point by continuously expanding the neighborhood range. Then the corresponding metrics are calculated based on the natural neighbors, and the center points are selected. In the assignment stage, we first assign the dense points to form the cluster prototype, followed by the assignment of the remaining points. Experiments show that our proposed method is self-adaptive, robust, and effective. The main novelties and properties of the proposed method in comparison with state-of-the-art methods are as follows:

1.
We use the natural neighbors instead of the nearest neighbors to describe the relationship between data. Each point has different numbers of natural neighbors. Points in dense regions have more neighbors than in sparse regions, and outliers have no natural neighbors. This neighborhood relationship can better reflect the data distribution and the relationship between data than the nearest neighbor method.
2.
We propose several new methods to calculate corresponding metrics of the points based on natural neighbors. Most DPC extensions select the same neighborhood size for all data. In contrast, natural neighbors can adaptively define the neighborhood size of each point. Thus, based on natural neighbors, we calculate the local density, the local domain density and $\delta$ distance. These calculation methods improve the robustness and efficiency of the proposed algorithm.
3.
We design a two-step assignment strategy based on the natural eigenvalue. In DPC, a single assignment error may produce additional errors. In our proposed, we divide the points into dense points and remaining points. If the number of natural neighbors of a point is greater than the ratio of the natural eigenvalue, it is a dense point; otherwise, it is a remaining point. The dense points around the same center should be in the same cluster; therefore, the first step is assigning the dense points to form the cluster prototype. In the second step, the remaining points are assigned to their superior points. Since the clustering prototype has been formed, it does not require too many times to find the superior point, thereby reducing the probability of generating errors.
4.
The proposed algorithm is effective and robust. Existing algorithms need to adjust the cutoff distance or the number of neighbors, and a change in parameters significantly influences the results. Our algorithm only needs to adjust one parameter to determine the definition of the dense point, and changing the parameter does not substantially impact the clustering results. Experiments show that our algorithm is extremely robust and can be applied to datasets with any cluster size.

The remainder of this paper is organized as follows: Section 2 outlines the related works. Section 3 describes our proposed NDDC method. In Section 4, the experimental results are given and analyzed. Section 5 summarizes the paper.
2. Related works

In this section, we introduce the DPC process and recent studies. Regarding the natural neighbor, we introduce various neighborhood relationships and describe the concepts of the natural neighbor, stable state, natural eigenvalue, and noise.

2.1 DPC algorithm

DPC is based on two premises: 1) the local density of the center point is greater than that of its neighbors. 2) The distance between the center points of different clusters is relatively large. DPC uses the local density and the distance from the nearest larger density point to describe the data points. DPC uses the cutoff distance method defined in Eq. (1) or the kernel function method in Eq. (2) to calculate the local density $\rho$ .

$\displaystyle{\rho_{i}}=\sum\limits_{{{j}}=1}^{n}{\chi({d_{ij}}-{d_{{c}}})}% \quad\chi=\left\{\begin{array}[]{ll}1&x\leqslant 0\\ 0&\text{otherwise}\\ \end{array}\right.$ (1) $\displaystyle{\rho_{i}}=\sum\limits_{j=1\atop j\neq i}^{n}{\exp\left[{-{{\left% ({\frac{{{d_{ij}}}}{{{d_{c}}}}}\right)}^{2}}}\right]}$ (2)

where $n$ represents the data size, and $d_{ij}$ represents the Euclidean distance between the data points $i$ and $j$ . $d_{c}$ represents the cutoff distance set by the user. In Eq. (1) the local density of data point $i$ is the number of points that are less than $d_{c}$ from this point. Equation (1) deals with discrete values, whereas Eq. (2) can deal with continuous values.

Equation (3) is used to calculate the parameter distance $\delta$ .

$\displaystyle{\delta_{i}}=\left\{\begin{array}[]{ll}\min({d_{ij}})&\text{if }{% \rho_{i}}\neq{\rho_{\max}}\ \&\ {\rho_{i}}<{\rm{}}{\rho_{j}}\\ \max({d_{ij}})&\text{otherwise}\\ \end{array}\right.$ (3)

The objective is to find a data point that is closest to point $i$ and has a density greater than this point. We define this point as the superior point, and the $\delta$ value is the distance from a point to its superior point. The $\delta$ value of the point with the highest density is the distance from it to the furthest point in space.

DPC draws a decision graph with $\rho$ plotted on the X-axis and $\delta$ plotted on the Y-axis to identify the centers rapidly. The center points with large $\rho$ and $\delta$ values are distributed in the upper right part of the decision graph. DPC also uses the $\gamma$ -decision graph. The $\gamma$ value is defined in Eq. (4). It decays exponentially; thus, it is preferable to select the centers.

$\displaystyle{\gamma_{i}}={\rho_{i}}\times{\delta_{i}}$ (4)

After the selection, the non-central point is assigned to its superior point’s cluster. If the superior point does not yet belong to a cluster, the algorithm finds the superior of the superior point until the clustering is completed.

The original DPC algorithm has been widely used in various fields, but it has several shortcomings. First, the definition of the local density requires the participation of all data, which is costly, and the neighborhood information of the data is not considered. Therefore, Du et al. incorporate the KNN into the DPC and propose the DPC-KNN [23], which limits the calculation space to the range of KNNs. They also use principal component analysis to preprocess high-dimensional data. Jiang et al. [24] also use the KNN to improve the calculation method of the $\delta$ distance. They believe that the $\delta$ distance of a point is affected by its neighbors; therefore, they focus on the center points. In order to reduce the computational complexity of DPC, a fast sparse density peak clustering algorithm (FSDPC) is proposed. In this algorithm, a new random third-party data point method is proposed to search the nearest neighbor, thus reducing the calculation times of similarity. FSDPC can improve efficiency while maintaining satisfactory clustering performance [28]. Second, the DPC does not automatically select the cluster centers. The domain adaptive density clustering algorithm (DADC [25]) sets thresholds for $\rho$ and $\delta$ so that the points greater than the threshold are the centers. This algorithm also uses the concept of domain density to highlight the cluster centers. Liu et al. present an adaptive DPC algorithm (ADPC-KNN [26]) and design a new method to select cluster centers adaptively and merge adjacent clusters. Third, in the assignment stage, the one-step assignment strategy is prone to the “domino effect”, i.e., a single assignment error may lead to additional errors. The FKNN-DPC [29] overcomes this problem by assigning non-outliers using the breadth-first search method, followed by using the fuzzy weighted KNN method to assign the remaining points. The method based on the density backbone and fuzzy neighborhood (DBFN [30]) first assigns dense points to form the backbone area. Then the KNN method is utilized to assign the boundary points to the related density backbone area. In addition, the shared nearest-neighbor-based clustering algorithm (SNN-DPC [31]) uses shared neighbors to describe the data. The authors propose a two-step assignment method to improve the algorithm’s robustness.

In recent years, the concepts of the reverse nearest neighbor and mutual nearest neighbor have also been applied to clustering [32, 33]. However, these methods have problems with neighborhood size selection. In the following section, we describe our proposed improvements.

2.2 Natural neighbors

Natural neighbors are inspired by human society. As a new concept of neighbors, this method can effectively solve the problem of neighborhood selection [27]. When two people regard each other as friends, they are natural neighbors. In a society, if everyone has at least one friend, the society is in a stable state. Similarly, if every point except noise has at least one natural neighbor, the dataset is in a relatively stable state. Several concepts related to natural neighbors are explained below.

(K-Nearest Neighbor).

Suppose the dataset is $X$ , the point to be processed is $p$ . The K nearest neighbors of $p$ is a set of objects $q$ , defined as follows:

$\displaystyle\textit{KNN}{(p)_{k}}=\{q\in X\mid\forall q\in X,\textit{dist}(p,% q)\leqslant\textit{dist}(p,u)\}$ (5)

where $\textit{dist}(p,u)$ represents the Euclidean distance between point $p$ and the $K$ th farthest object.

(Reverse K-Nearest Neighbor).

The reverse KNN of $p$ is a set of objects $q$ , which treat $p$ as their KNNs.

$\displaystyle\textit{RKNN}{(p)_{k}}=\{{q\in X\mid p\in\textit{KNN}{{(q)}_{k}}}\}$ (6)

(Natural neighbor).

If the natural neighbor of point $p$ is $q$ , then $p$ and $q$ are each other’s neighbors. This relationship is defined as follows:

$\displaystyle Na{N_{p}}=\{{q\in X\mid p\in\textit{KNN}{{(q)}_{k}}\wedge q\in% \textit{KNN}{{(p)}_{k}}}\}$ (7)

(Stable state and natural eigenvalue).

A natural neighbor search is a process of gradually expanding the search range until it reaches a stable state. The definition of the steady state is as follows:

$\displaystyle({\forall p})({\exists q})\wedge({q\neq p})\to({p\in\textit{KNN}{% {(q)}_{k}}})\wedge({q\in\textit{KNN}{{(p)}_{k}}})$ (8)

where $p$ represents the data point except noise in the dataset $X$ . The search range of KNN is $K\in[{1,n}]$ . When the dataset reaches a stable state, the value of $k$ is called the natural eigenvalue, denoted by $\lambda$ .

$\displaystyle\lambda\equiv\{{k\mid({\forall p})({\exists q})\wedge({q\neq p})% \to({p\in\textit{KNN}{{(q)}_{k}}})\wedge({q\in\textit{KNN}{{(p)}_{k}}})}\}$ (9)

(Noise points).

When the search range is $\lambda$ , $(\lambda>0)$ , all points except point $o$ have at least one natural neighbor,and when the search range is extended to $\lambda+\sqrt{\lambda}$ , the point $o$ still has no natural neighbors;this point is called a noise point.

We use a simple dataset to show the acquisition process of natural neighbors. Figure 1a–c shows the neighbor relationship obtained under the continuous expansion of the neighborhood search range. First, each point finds its nearest neighbor, and then verifies the reverse neighbor relationship. If the two data points are each other’s nearest neighbor, the neighbor relationship is established. AC, DG, and EF have established neighbor relationships with each other in Fig. 1a. Then expand the neighbor range and get the neighbor relationship as shown in Fig. 1b. All points except point H have at least one neighbor. After the neighbor range is expanded again, point H still has no neighbor, so H is an outlier, the dataset reaches the stable state, and the natural eigenvalue is the current neighborhood search range.

Figure 1.

The process of obtaining the natural neighbors of the dataset. (a) neighbor relationship ( $k=$ 1); (b) neighbor relationship ( $k=$ 2); (e) neighbor relationship ( $k=$ 3).

Because the natural neighbor search process is self-adaptive and the natural neighbor relationship is effective and robust to describe the data, it has been used in machine learning applications, such as classification and anomaly detection [34]. In this paper, we use this approach to improve the DPC.

3. Natural neighbor-based domain density peak clustering algorithm

This section introduces the details of the proposed algorithm. First, we obtain the natural neighbors of each point and the global natural eigenvalue; the local density $\rho$ , the domain density $D D$ , and the $\delta$ distance of each point are calculated based on the natural neighbors. Then, we select several points with large $\gamma$ values as center points. In the assignment stage, the dense points with more natural neighbors are assigned first to form a cluster protype, followed by the assignment of the remaining points to their superior point. Figure 2 shows the flowchart of the algorithm. In the rest of this section, we provide the details of the three main steps: (1) calculating the metric values of each point based on the natural neighbors and identify the center points; (2) assigning the dense points based on the natural eigenvalue; (3) assigning the remaining points and analyze the algorithm complexity.

Figure 2.

Workflow of the proposed NDDC algorithm.

3.1 Step 1: Calculate metric values based on natural neighbors and identify cluster centers

We obtain the neighborhood information based on the natural neighbors and calculate the relevant metric values. This approach does not require manual selection of the k value to determine neighborhood information.

The first step is obtaining the natural neighbors and natural eigenvalue. We initialize the $K$ value to 1. After finding the $K$ neighbors of each point, the algorithm determines whether the two points are natural neighbors. Then, the value of $K$ is expanded until the dataset reaches a steady state. The first half of Algorithm 1 focuses on the search process of the natural neighbors. The entire search process does not require inputting any parameters. After obtaining the natural neighbors, we use three kernel functions (inverse distance kernel, Eq. (10); exponential kernel, Eq. (11); Gaussian kernel, Eq. (12)) to calculate the local density and select the best one with the highest clustering accuracy to ensure that the algorithm can adapt to different distributions.

$\displaystyle{\rho_{i}}=\frac{{{nn(i)}}}{\sum\limits_{j\in nn(i)}{\textit{dist% }(i,j)}}$ (10) $\displaystyle{\rho_{i}}=\sum\limits_{j\in nn(i)}{\exp(-\textit{dist}(i,j))}$ (11) $\displaystyle{\rho_{i}}=\exp\left({-\frac{{\sum\nolimits_{j\in nn(i)}{\textit{% dist}{{(i,j)}^{2}}}}}{{{nn(i)}}}}\right)$ (12)

where $nn(i)$ represents the natural neighbors of point $i$ . All three kernels all satisfy the condition that the more neighbors, and the closer the distance, the greater the local density of the point is.

Next, we calculate the local domain density based on the local density to highlight the center points.

(Local domain density).

The local domain density of point $i$ is equal to the weighted sum of its local density and the local density of the surrounding neighbors.

$\displaystyle D{D_{i}}={\rho_{i}}+\sum\limits_{j\in nn(i)}{\omega{\rho_{j}}({% \rho_{j}}<{\rho_{i}})}\quad\omega=\frac{1}{{\textit{dist}(i,j)}}$ (13)

The weight coefficient $\omega$ is the reciprocal of the distance from the natural neighbor to the point. The closer the distance, the higher the weight is. $D D$ is calculated based on $\rho$ . Because the difference between the $D D$ value of the center point and the other points is greater than the $\rho$ value, the center point is more easily noticed. Since dense points have more natural neighbors than sparse points, we use the local domain density instead of the local density to describe the data.

Subsequently, for each point, the algorithm finds the nearest point with the highest local domain density. The distance between these two points is the $\delta$ value of the point, which is calculated using Eq. (14):

$\displaystyle{\delta_{i}}=\left\{\begin{array}[]{ll}\min({d_{ij}})&\text{if }D% {D_{i}}\neq D{D_{\max}}\&D{D_{i}}<D{D_{j}}\\ \max({d_{ij}})&\text{otherwise}\\ \end{array}\right.$ (14)

After obtaining the $D D$ and $\delta$ of each data point, we refer to Eq. (4) of DPC and use Eq. (15) to redefine $\gamma$ . The difference between the two formulas is the use of $D D$ (local density) or $\rho$ (local density) in the calculation. As noted above, As noted above, using $D D$ better emphasizes the center point; thus, we use $D D$ instead of $\rho$ . Then we select $c$ points with higher $\gamma$ values as the centers.

$\displaystyle{\gamma_{i}}=DD_{i}\times{\delta_{i}}$ (15)

This measure requires parameter $c$ to identify the cluster centers. It is worth mentioning that the difference between the $\gamma$ values of the cluster centers and the other points is very large; therefore, the number of cluster centers is easy to determine. In addition, this method also provides an approach to identify cluster centers through expert interaction.

The detailed algorithm is shown in Algorithm 1. $\textit{NaN}_{\textit{Edge}}$ contains all the natural neighbor pairs in the dataset. If $A$ and $B$ are natural neighbors, they are stored in $\textit{NaN}_{\textit{Edge}}$ in the form of $\{A,B\}$ . During the natural neighbor search, the count function counts the number of points without natural neighbors $(\textit{NaN}_{\textit{Num}_{(x_{i})}}==0)$ and assigns that value to cnt. When all the points except the noise found their natural neighbors, the number of points without neighbors remains the same even when the search scope is extended. We use the repeat function to count the number of times cnt remains unchanged. When it is greater than the specified number, the algorithm ends and the natural neighbors of each point are obtained. We use a k-dimensional (k-d) tree as the data structure, and the overall time complexity is $O(n\log n)$ . The proof of the properties, such as the stability of the natural eigenvalue, has been provided in Ref. [27]. The time complexity required to calculate the distance between two points is $O({n^{2}})$ . When calculating the local density and local domain density, the calculation space will be reduced to the neighborhood range; thus, the time complexity is $O(kn)$ . where $k$ is the number of natural neighbors. For calculating the $\delta$ distance to find the superior point, the time complexity is $O({n^{2}})$ . In addition, the time complexity required to select the center point is $O(n\log n)$ . The overall complexity of Algorithm 1 is $O(n\log n+kn+{n^{2}}+n\log n)$ , which can be simplified to $O({n^{2}})$ .

[H] : Calculate $\rho$ , $D D$ , and $\delta$ and select the cluster centers[1] dataset $X$ , $c$ (number of center points) cluster centers (with labels), $\lambda$ Initialization $r=$ 1, $\textit{flag}=$ 0, $\textit{NaN}_{\textit{Edge}}=\emptyset$ , $\forall x_{i}\in X$ , $\textit{NaN\_Num}_{x_{i}}=0$ ;

$\textit{flag}==0$ $x_{i}\in X$ find the $r$ -th neighbor, use the k-d tree, and define its $y$ ; $\textit{KNN}(x_{i})_{r}=\textit{KNN}(x_{i})_{r}\cup\{y\}$ ; $x_{i}\in\textit{KNN}(y)_{r}\&\&\{\textit{KNN}(x_{i})_{y},x_{i}\}\notin\textit{% NaN}_{\textit{Edge}}$ $\textit{NaN}_{\textit{Edge}}=\textit{NaN}_{\textit{Edge}}\cup\{x_{i},y\}$ ; $\textit{NaN\_Num}_{x_{i}}=\textit{NaN\_Num}_{x_{i}}+1$ ; $\textit{NaN\_Num}_{y}=\textit{NaN\_Num}_{y}+1$ ; $\textit{cnt}=\textit{count}(\textit{NaN\_Num}_{x_{i}}==0);\textit{rep}=\textit% {repeat}(\textit{cnt})$ ; $\textit{all}(\textit{NaN\_Num}_{x_{i}}\not=0)\|\textit{rep}\geqslant\sqrt{% \textit{r-rep}}$ $\textit{flag}=1$ ; $r=r+1$ ;

$\lambda=r$ ;

$x_{i}\in X$ calculate $\rho_{i}$ use Eq. (10) or Eq. (11) or Eq. (12); calculate $DD_{i}$ use Eq. (13);

get the maximum Domain Density $DD_{\max}$ ; $x_{i}\in X$ calculate $\delta_{i}$ use Eq. (14); draw $DD_{i}-\delta$ and the $\gamma$ decision graph; Sort the data points in descending order according to the $\gamma$ value; Select the first $c$ points as the centers and assign labels to them; return $\lambda$ , the center points, and their labels;

3.2 Step 2: Assign dense points based on the natural eigenvalue

This step assigns dense points to form the prototype of the cluster. In the allocation process, we introduce a ratio parameter $\alpha\in[0,1]$ to define the dense point.

(Dense point).

The dense point is a point with many natural neighbors. The global natural eigenvalue $\lambda$ has been obtained from Algorithm 1. We define points whose natural neighbor number is greater than or equal to a certain ratio of natural eigenvalue as dense points:

$\displaystyle\textit{Dense}=\{{{x_{i}}\in X\mid nn(i)\geqslant\alpha\times% \lambda}\}$ (16)

First, the label of the center point is assigned to the dense point of its natural neighbors. Then, the label is assigned to the natural neighbor’s natural neighbor. This process is repeated until all the dense points are allocated.

The ratio parameter $\alpha$ is the only parameter that needs to be adjusted in our proposed algorithm. Compared with parameters in other algorithms, the ratio parameter has a smaller value range and is easier to adjust. As mentioned earlier, $\alpha\in[0,1]$ , which means that the maximum number of neighbors is the natural eigenvalue, and the minimum is 0. When the maximum value is used, only points whose number of neighbors are natural eigenvalues are called dense points, and the remaining points are assigned in the second step. Although all points are regarded as dense points, when the value is 0, not all data points may be assigned in the iterative allocation process. Thus, we need to determine whether the data point has been assigned. If it was assigned, the point is not processed, nor will it continue to process its natural neighbors. Therefore, it may happen that one point has been assigned, but its natural neighbors have not been assigned. In this case, we assume that the point has been assigned, but the natural neighbors of this point will be only assigned in the second step.

Figure 3.

Details of the two stages of label assignment. (a) The original data (Aggregation); (b) identified cluster prototype; (c) assigning labels to the remaining points.

3.3 Step 3: Assign remaining points

After assigning the dense points and forming the cluster prototype, the final step is to assign the remaining data points to form the final cluster. We use the DPC, i.e., we find a point that is closest to it and whose local domain density is greater than that of the point. The label of this point is the same as that of its superior point. Since the clustering prototype has been formed, the superior point can be found easily, thereby minimizing the “domino effect”.

Figure 3 depicts the clustering results of the two-stage strategy. Figure 3a shows the data distribution of the dataset consisting of seven clusters. First, the natural neighbors of each data point are obtained through Algorithm 1, and the global natural eigenvalue is 5. Then we select several points with the highest $\gamma$ values as the center points and assign them labels. Through experimental tuning, we select the ratio parameter $\alpha=$ 0.9, which means that the number of natural neighbors is greater than or equal to 0.9*5 $=$ 4.5 (the number of neighbors is an integer; thus, 4.5 is rounded to 5) points, which are dense points. Starting from the center point, the dense points are assigned first, and the labels are continuously assigned to the dense points’ natural neighbors, forming the prototype of each cluster. Figure 3b shows the prototype of the clusters. Figure 3c shows the final clusters. After two allocations, the data are successfully divided into seven clusters.

Algorithm 2 provides the steps of the two-step allocation strategy, which is described in Section 3.2 and Section 3.3. The first step of the allocation strategy uses a queue as the data structure and enqueue and dequeue operations to allocate the dense points. The time complexity of this step is $O({n_{d}})$ , where ${n_{d}}$ is the number of dense points. When assigning the remaining points, the algorithm first evaluates whether the point has been assigned; the time complexity of this step is $O({n})$ . If the point has not been assigned, the assignment is performed by iteratively querying the superior point; the time complexity is $O({n^{2}})$ . Therefore, the time complexity of the overall NDDC algorithm is $O({n^{2}})$ .

We also analyze the space complexity. A distance matrix is constructed when calculating the local density and other metrics, and the space complexity is $O({n^{2}})$ . A dense point queue is constructed during allocation, and the required space complexity is $O({n})$ . Thus, the overall space complexity is $O({n^{2}})$ , which is the same as that of the DPC.

[H] : NDDC’s two-step allocation strategy[1] PMC list, ratio parameter $\alpha$ final clustering resultCreate a clustering result array and set all points to the unassigned state; Create a dense point queue called Dense, and put the centers into the queue; Dense is not empty Pop a point at Dense’s head, call tmp; $nn(\textit{tmp})$ $\textit{len}(nn(\textit{tmp}))\geqslant\lambda\times\alpha$ and $nn(\textit{tmp})$ is unlabeled assign the label of tmp to $nn(\textit{tmp})$ ; $\textit{Dense.append}(nn(\textit{tmp}))$ ; Update the assigned data point lable in the result array; remaining points Use the second-step strategy for allocation; return result;

4. Experimental results and analysis

We use some synthetic datasets and the UCI datasets for testing to verify the effectiveness of the NDDC algorithm. The experimental results are compared with the K-Means, DBSCAN [18], DPC [22], FKNN [29], SNN-DPC [31], DBFN [30], and FSDPC algorithms [28].

4.1 Evaluation measures

The evaluation measures used in this article include the clustering accuracy (Acc), normalized mutual information (NMI), and the adjusted Rand index (ARI). The Acc is defined in Eq. (17):

$\displaystyle\textit{Acc}=\frac{{\sum\nolimits_{i=1}^{n}{\delta({s_{i}},% \textit{map}({r_{i}}))}}}{n}\quad\delta(x,y)=\left\{\begin{array}[]{ll}1&\text% {if }x=y\\ 0&\text{otherwise}\\ \end{array}\right.$ (17)

where $n$ represents the data size, $r_{i},s_{i}$ , respectively represent the experimental label and the true label. The resulting label is mapped to the equivalent real label using the $\textit{map}()$ function and the Hungarian algorithm.

Given two variables $A$ , $B$ , the NMI between $A$ and $B$ is defined as:

$\displaystyle\textit{NMI}(A,B)=\frac{{2\times I(A,B)}}{{H(A)+H(B)}}$ (18)

where $I(A,B)$ represents the mutual information between $A$ and $B$ , and $H(·)$ is the information entropy. Therefore, for the real category $A$ and the predicted category $B$ , the NMI values are as follows:

$\displaystyle\textit{NMI}(A,B)=\frac{{-2\sum\nolimits_{i=1}^{CA}{\sum\nolimits% _{j=1}^{CB}{{C_{ij}}\log\left(\frac{{n{C_{ij}}}}{{{C_{i}}\times{C_{j}}}}\right% )}}}}{{\sum\nolimits_{i=1}^{CA}{{C_{i}}\log\left(\frac{{{C_{i}}}}{n}\right)+% \sum\nolimits_{j=1}^{CB}{{C_{j}}\log\left(\frac{{{C_{j}}}}{n}\right)}}}}$ (19)

where $C A$ and $C B$ , respectively, represent the number of data points in cluster $A$ and cluster $B$ , $C_{i}$ represents the data point in cluster $A$ , $C_{j}$ represents the data point in cluster $B$ , and $C_{ij}$ represents the common data points in clusters $A$ and $B$ . If the result is the same as the ground truth, the NMI value is 1, and if the two clustering results are entirely different, the NMI is 0.

The ARI is often used to evaluate clustering results. The Rand index (RI) is the proportion of correctly allocated results. $T P$ is the number of data pairs that belong to the same category in clusters $A$ and $B$ . $T N$ is the number of data pairs that do not belong to the same category in cluster $A$ and cluster $B$ .

$\displaystyle RI=\frac{{TP+TN}}{{\left({{}_{2}^{n}}\right)}}$ (20)

The ARI is defined based on the RI and measures the degree of agreement between the two data distributions:

$\displaystyle\textit{ARI}(A,B)=\frac{{\sum\nolimits_{i,j}{(_{2}^{{n_{ij}}})}-% \sum\nolimits_{i}{(_{2}^{{n_{i}}})}\sum\nolimits_{j}{(_{2}^{{n_{j}}})}/(_{2}^{% {n_{i}}})}}{{\frac{1}{2}\left[{\sum\nolimits_{i}{(_{2}^{{n_{i}}})}+\sum% \nolimits_{j}{(_{2}^{{n_{j}}})}}\right]-\sum\nolimits_{i}{(_{2}^{{n_{i}}})}% \sum\nolimits_{j}{(_{2}^{{n_{j}}})}/(_{2}^{{n_{i}}})}}$ (21)

where $n_{i}$ represents the data point in cluster $A$ , $n_{j}$ represents the data point in cluster $B$ , and $n_{ij}$ represents the common data points of cluster $A$ and cluster $B$ . The value range of this indicator is $\textit{ARI}\in[-1,1]$ . The ARI is highly discriminative.

4.2 Datasets

We make 16 databases for the results in the experiments, including 6 synthetic datasets and 10 UCI real datasets. In order to ensure the reliability of the dataset, all the test datasets we selected did not contain missing values. The details of the synthetic and UCI real datasets are listed in Tables 1 and 2, respectively.

Table 1
Synthetic datasets

Dataset	Source	No. of records	No. of attributes	No. of clusters
Aggregation	[35]	788	2	7
Compound	[36]	399	2	6
Flame	[37]	240	2	2
Path-based	[38]	300	2	3
R15	[39]	600	2	15
4k2-far	[40]	400	2	4

Table 2

UCI datasets

Dataset	Source	No. of records	No. of attributes	No. of clusters
Iris	[41]	150	4	3
Haberman	[41]	306	3	2
Libras Movement	[41]	360	90	15
E-coli	[41]	336	8	8
Seeds	[42]	210	7	3
Ionosphere	[43]	351	34	2
Heart failure clinical	[44]	299	13	2
Teaching Assistant Evaluation	[41]	151	5	3
Banknote authentication	[41]	1372	4	2
Shill Bidding	[45]	6321	9	2

Table 3

Performances of different algorithms on different synthetic datasets

Algorithm	Acc	NMI	ARI	Arg.	Algorithm	Acc	NMI	ARI	Arg.
Aggregation					Compound
NDDC	0.999	0.996	0.998	7/0.9	NDDC	0.872	0.912	0.853	5/0.8
K-Means	0.785	0.879	0.762	7	K-Means	0.669	0.759	0.580	5
DBSCAN	0.897	0.884	0.893	0.951/4	DBSCAN	0.880	0.869	0.875	0.951/3
DPC	0.991	0.970	0.982	2	DPC	0.862	0.880	0.834	9
FKNN	0.992	0.980	0.985	7/20	FKNN	0.827	0.763	0.778	5/11
SNN	0.978	0.955	0.959	7/15	SNN	0.797	0.769	0.741	5/6
DBFN	0.996	0.987	0.991	7/25/45	DBFN	0.855	0.822	0.809	5/8/45
FSDPC	0.999	0.996	0.998	7/2	FSDPC	0.676	0.792	0.589	5/2
Flame					Path-based
NDDC	0.987	0.912	0.950	2/0.8	NDDC	0.997	0.983	0.990	3/0.8
K-Means	0.837	0.399	0.453	2	K-Means	0.743	0.546	0.461	3
DBSCAN	0.958	0.736	0.805	0.801/4	DBSCAN	0.7	0.518	0.416	0.951/4
DPC	0.783	0.407	0.317	2	DPC	0.727	0.519	0.442	2
FKNN	1	1	1	2/6	FKNN	0.837	0.646	0.596	3/14
SNN	0.987	0.899	0.950	2/5	SNN	0.977	0.901	0.929	3/9
DBFN	0.992	0.927	0.967	2/13/45	DBFN	0.723	0.531	0.445	3/18/45
FSDPC	0.787	0.413	0.326	2/2	FSDPC	0.733	0.540	0.453	3/2
R15					4k2_far
NDDC	0.993	0.989	0.986	15/0.8	NDDC	1	1	1	4/0
K-Means	0.997	0.994	0.993	15	K-Means	1	1	1	4
DBSCAN	0.968	0.951	0.943	0.401/7	DBSCAN	1	1	1	0.601
DPC	0.973	0.954	0.942	2	DPC	0.992	0.966	0.980	2
FKNN	0.995	0.991	0.989	15/15	FKNN	1	1	1	4/20
SNN	0.997	0.994	0.993	15/10	SNN	1	1	1	4/10
DBFN	0.997	0.994	0.993	15/22/45	DBFN	1	1	1	4/8/45
FSDPC	0.997	0.994	0.993	15/2	FSDPC	1	1	1	4/2

Table 4

Mean and variance of the accuracy of different algorithms

	NDDC	K-Means	DBSCAN	DPC	FKNN	SNN	DBFN	FSDPC
Avg.	0.9747	0.8397	0.9005	0.8881	0.9418	0.9560	0.9271	0.8653
Var.	0.0025	0.0183	0.0117	0.0132	0.0073	0.0061	0.0131	0.0225

Figure 4.

The clustering results of the 7 algorithms on the Aggregation dataset.

Figure 5.

The clustering results of the 7 algorithms on the Path-based dataset.

Table 5

Performances of different algorithms on different UCI datasets

Algorithm	Acc	NMI	ARI	Arg.	Algorithm	Acc	NMI	ARI	Arg.
Iris					Haberman
NDDC	0.947	0.845	0.851	3/0	NDDC	0.742	0.028	0.023	2/0.72
K-Means	0.893	0.758	0.730	3	K-Means	0.520	0.001	$-$ 0.01	2
DBSCAN	0.907	0.713	0.706	0.401/3	DBSCAN	0.735	0	0	0.001/4
DPC	0.893	0.769	0.728	2	DPC	0.712	0.006	$-$ 0.02	2
FKNN	0.967	0.885	0.904	3/22	FKNN	0.634	0.016	0.049	2/7
SNN	0.973	0.914	0.922	3/15	SNN	0.621	0.018	0.044	2/17
DBFN	0.920	0.793	0.787	3/20/45	DBFN	0.732	0.010	0.030	2/6/45
FSDPC	0.940	0.805	0.834	3/2	FSDPC	0.738	0.027	0.011	2/2
Libras Movement					E-coli
NDDC	0.489	0.591	0.348	15/0.3	NDDC	0.771	0.616	0.687	8/0.9
K-Means	0.447	0.577	0.295	15	K-Means	0.568	0.616	0.411	8
DBSCAN	0.355	0.502	0.137	0.751/4	DBSCAN	0.613	0.474	0.481	0.151/6
DPC	0.372	0.531	0.238	2	DPC	0.470	0.505	0.300	2
FKNN	0.333	0.566	0.306	15/11	FKNN	0.521	0.567	0.552	8/9
SNN	0.494	0.661	0.393	15/11	SNN	0.845	0.698	0.755	8/6
DBFN	0.319	0.446	0.108	15/6/45	DBFN	0.497	0.390	0.345	8/5/45
FSDPC	0.322	0.482	0.174	15/2	FSDPC	0.645	0.567	0.439	8/2
Seeds					Ionosphere
NDDC	0.905	0.692	0.739	3/0.9	NDDC	0.863	0.435	0.517	2/0.18
K-Means	0.895	0.695	0.717	3	K-Means	0.712	0.135	0.178	2
DBSCAN	0.781	0.547	0.484	0.751/6	DBSCAN	0.709	0.308	0.273	0.951/3
DPC	0.876	0.681	0.682	2	DPC	0.510	0.068	$-$ 0.03	2
FKNN	0.905	0.701	0.742	3/9	FKNN	0.721	0.167	0.193	2/10
SNN	0.919	0.742	0.778	3/6	SNN	0.855	0.381	0.495	2/5
DBFN	0.800	0.523	0.486	3/30/45	DBFN	0.644	0.011	0.028	2/29/45
FSDPC	0.885	0.698	0.702	3/2	FSDPC	0.643	0.025	0.004	2/2
Heart-failure-clinical					Teaching-Assistant-Evaluation
NDDC	0.669	0.014	0.004	2/0.6	NDDC	0.490	0.089	0.085	3/0.6
K-Means	0.622	0.002	0.017	2	K-Means	0.397	0.026	0.009	3
DBSCAN	0.659	0	0	0.001/4	DBSCAN	0.344	0.037	$-$ 0.00	0.001/3
DPC	0.555	0.002	0.005	2	DPC	0.424	0.039	0.015	6
FKNN	0.622	0.003	$-$ 0.02	2/29	FKNN	0.424	0.034	0.018	3/14
SNN	0.565	0.002	0.007	2/21	SNN	0.424	0.084	0.047	3/20
DBFN	0.649	0	0.002	2/5/45	DBFN	0.477	0.057	0.056	3/30/45
FSDPC	0.662	0.016	$-$ 0.00	2/2	FSDPC	0.390	0.028	0.003	3/2
Banknote-authentication					Shill Bidding
NDDC	0.896	0.573	0.590	2/0	NDDC	0.891	0.001	$-$ 0.00	2/1
K-Means	0.612	0.030	0.048	2	K-Means	0.548	0.000	$-$ 0.00	2
DBSCAN	0.555	0.001	0	0.001/6	DBSCAN	0.555	0.000	0.000	0.001/6
DPC	0.740	0.345	0.229	2	DPC	0.549	0.000	$-$ 0.00	2
FKNN	0.734	0.248	0.216	3/10	FKNN	0.883	0.111	0.276	2/13
SNN	0.896	0.583	0.628	2/8	SNN	0.563	0.137	0.011	2/16
DBFN	0.606	0.073	0.045	2/9/45	DBFN	0.818	0.003	0.010	2/10/45
FSDPC	0.741	0.347	0.230	2/2	FSDPC	0.548	0.000	$-$ 0.00	2/2

Table 6

The mean and variance of the clustering accuracy of each algorithm on the four datasets

	Eco-avg	Eco-var	Heart-avg	Heart-var	Lib-avg	Lib-var	Seeds-avg	Seeds-var
NDDC	0.7248	0.0002	0.6654	0.0001	0.4733	0.0002	0.8482	0.0011
FKNN	0.4261	0.0027	0.5938	0.0025	0.1707	0.011	0.7046	0.0073
SNN	0.6934	0.0061	0.5503	0.001	0.4257	0.0012	0.8546	0.0076
DBFN	0.5423	0.0024	0.5623	0.002	0.2557	0.0005	0.7446	0.0016

Figure 6.

Robustness analysis of the four algorithms on the E-coli dataset.

Figure 7.

Robustness analysis of the four algorithms on the Heart-failure-clinical dataset.

Figure 8.

Robustness analysis of the four algorithms on the Libras Movement dataset.

Figure 9.

Robustness analysis of the four algorithms on the Seeds dataset.

4.3 Experimental environment and parameter description

We adjust the parameters in each algorithm to reach the optimum state. The K-Means algorithm only requires the number of clusters. DBSCAN requires adjusting two parameters (eps and minpts); we set $\textit{eps}\in[0.001,1]$ , with a step size of 0.05, and ${\textit{minpts}}\in{{[2,10]}}$ , with a step size of 1. The author of the traditional DPC algorithm provides a rule of thumb that $d_{c}$ should be chosen so that the number of neighbors is between 1% and 2% of the total number of points. We use 2% in this study. For the Teaching Assistant Evaluation dataset, we use 5% to obtain better results. The parameters of FKNN and SNN include the number of clusters and the $K$ value of the number of neighbors. If $K$ is too large or too small, the clustering performance will suffer. Therefore, we stipulate that $K\in[5,30]$ . The parameters of DBFN include the number of clusters, the number of neighbors $K$ , and parameter $\delta$ . We also set $K\in[5,30]$ , and the value of $\delta$ set based on the source code provided by the author ( $\delta=45$ ). FSDPC requires users to set the iterative steps to determine the neighborhood, obtain the local density of points by giving the $d_{c}$ value, and manually specify the number of clustering centers. According to the definition in this paper, $\textit{step}=0.4n-1$ , where $n$ is the data size and $d_{c}$ value is 2%. The NDDC algorithm requires the number of clusters and the ratio parameter $\alpha$ , we set $\alpha\in[0,1]$ , with a step size of 0.02. The experiments are performed on a computer with an Intel(R) core i5-8500 and 16 GB of RAM.

4.4 Results on the synthetic datasets

Six synthetic datasets are used to test the performance of the proposed algorithm. These datasets have different distributions and sizes so that various situations can be simulated. For the NDDC, we select the kernel function with the best clustering performance. The final clustering results are listed in Table 3. Most of the algorithms provide satisfactory clustering results on the 4k2-far dataset, and our proposed method also obtained the best performance. The proposed method has the highest performance on the Aggregation and Path-based datasets when using the cutoff kernel and Gaussian kernel, respectively. Our proposed algorithm (exponential kernel) performs well on the Compound dataset based on the NMI indicator. None of the other algorithms reach 0.9. The FKNN algorithm has the best clustering performance on the Flame dataset, and the DBFN algorithm has the best clustering performance on the R15 dataset. FSDPC has the same excellent performance as our proposed algorithm on Aggregation dataset. However, the NDDC algorithm does not perform significantly better than these optimal algorithms, which is reflected in the numerical difference of about 0.01. We calculated the mean and variance of the Acc of each algorithm. Our proposed algorithm has the highest average accuracy and the smallest variance, and it is the most stable method. The results are listed in Table 4.

We choose the Aggregation and Path-based datasets to display the clustering results of different algorithms visually. Figures 4 and 5, respectively, show the clustering results of K-Means, DBSCAN, DPC, FKNN, SNN, DBFN, FSDPC, and the proposed NDDC algorithm on these two datasets. For the Aggregation dataset, Fig. 4h shows the results obtained by the NDDC algorithm, and Fig. 4a–g shows the results of the other state-of-the-art algorithms. The K-Means incorrectly divides a large cluster into three clusters, and DBSCAN does not predict the correct number of clusters; thus, these two algorithms cannot complete the basic clustering tasks. The DPC, FKNN, SNN, and DBFN algorithms can complete the basic clustering tasks, but there are some allocation errors. For example, in Fig. 4e, the three clusters in the lower-left corner have assignment errors, and there are errors in the upper left corner in Fig. 4f. Our proposed algorithm does not only complete the basic clustering tasks but also has the highest accuracy with FSDPC among all algorithms. Most algorithms cannot identify the true distribution of the Path-based dataset. The black dots in Fig. 5b represent unallocated data, indicating that the DBSCAN algorithm recognizes these data as noise because the density is less than the specified threshold. The K-Means, DPC, FKNN, DBFN, and FSDPC algorithms cannot identify the ring clusters. Only the SNN and our proposed algorithm correctly complete the clustering task. Based on the clustering accuracy and other indicators, our proposed algorithm provides the best performance.

4.5 Results on the UCI real datasets

Ten synthetic datasets are used to test the performance of the proposed algorithm. These datasets are often used to test the classification or clustering performance. The clustering results are listed in Table 5. On the Ionosphere and Teaching-Assistant-Evaluation datasets, our proposed algorithm provides the best clustering performance, with the top performance of all indicators. On the Haberman, Heart-failure-clinical, Banknote-authentication, and Shill Bidding datasets, our algorithm also reaches the top performance in several indicators. On the Iris, Libras Movement, E-coli, and Seeds datasets, our algorithm does not achieve the optimal results, but it exhibits strong robustness. We selected the Libras Movement, E-coli, Seeds and Heart-failure-clinical datasets to analyze the robustness of the NDDC, SNN, FKNN, DBFN. Since the parameter settings of FSDPC algorithm have been given, the robustness analysis of FSDPC algorithm is not performed. Figures 6 to 9 show the changes in the clustering accuracy of each algorithm as the parameters change. The X-axis represents the value of the parameter, and the Y-axis represents the clustering accuracy. On the E-coli dataset, the highest accuracy of the SNN algorithm is 0.84, but when K exceeds 20, the accuracy of the algorithm drops sharply. In contrast, the accuracy of the NDDC algorithm is maintained at about 0.7. On the Seeds dataset, the accuracy of our algorithm is stable at 0.8–0.9, whereas that of the SNN algorithm fluctuates considerably. The proposed algorithm is the most stable on the Heart-failure-clinical dataset, with almost no fluctuations. The mean and variance of the clustering accuracy of each algorithm on each dataset are listed in Table 6. The variance of the NDDC is the smallest on all datasets, and its average clustering accuracy is the highest on most datasets, demonstrating the superiority of the NDDC.

In summary, our proposed algorithm has better clustering results than the other algorithms on some datasets, and the parameters of the NDDC are easier to adjust than those of the other algorithms. The experiments show that the NDDC algorithm is highly robust on most datasets.

5. Conclusion

We used the natural neighbor instead of the nearest neighbor and proposed the NDDC to overcome the deficiencies of the DPC and its improvements. The algorithm first obtains the global natural eigenvalue and the natural neighbors of each point. Subsequently, the local density, local domain density, $\delta$ distance, and $\gamma$ value of the points are calculated based on the natural neighbors. A two-step assignment strategy was proposed. First, the dense points are assigned to form a cluster prototype, followed by assigning the remaining points by finding the superior points iteratively. The experimental results on synthetic and UCI datasets showed that the NDDC could process many types of datasets effectively and robustly.

In the future, we will adapt the NDDC to process streaming data to enable data analysis in the production environment, solve practical problems, and improve the production efficiency in related fields.

Footnotes

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China under Grants with No. 62273164, No. 61873324, No. 61903156, the Natural Science Foundation of Shandong Province under Grant with No. ZR2019MF040, and the Higher Educational Science and Technology Program of Jinan City under Grant with No. 2020GXRC057. We thank openbiox community and Hiplot team (https://hiplot.com.cn) for providing technical assistance and valuable tools for data analysis and visualization.

References

Ratnakumar

and Nanda

S.J.

, A high speed roller dung beetles clustering algorithm and its architecture for real-time image segmentation, Applied Intelligence, 2021, 1–32. doi: 10.1007/s10489-020-02067-7.

Zhang

Bai

Yang

L.T.

and Baker

, A cloud-edge-aided incremental high-order possibilistic c-means algorithm for medical data clustering, IEEE Transactions on Fuzzy Systems 29(1) (2021), 148–155. doi: 10.1109/TFUZZ.2020.3022080.

Zhou

Deng

Piao

and Zhao

, Few-shot traffic sign recognition with clustering inductive bias and random neural network, Pattern Recognition 100 (2020), 107160. doi: 10.1016/j.patcog.2019.107160.

Croitoru

and Yue

, Geodenstream: An improved denstream clustering method for managing entity data within geographical data streams, Computers & Geosciences 144 (2020), 104563. doi: 10.1016/j.cageo.2020.104563.

Jothi

Mohanty

S.K.

and Ojha

, Gene expression clustering using local neighborhood-based similarity measures, Computers & Electrical Engineering 91 (2021), 107032. doi: 10.1016/j.compeleceng.2021.107032.

Ahmad

and Khan

S.S.

, Initkmix-a novel initial partition generation algorithm for clustering mixed data using k-means-based clustering, Expert Systems with Applications 167 (2021), 114149. doi: 10.1016/j.eswa.2020.114149.

Dinh

D.-T.

and Huynh

V.-N.

, k-pbc: An improved cluster center initialization for categorical data clustering, Applied Intelligence 50(8) (2020), 2610–2632. doi: 10.1007/s10489-020-01677-5.

Cheung

Y.-M.

and Tang

Y.Y.

, Self-adaptive multiprototype-based competitive learning approach: A k-means-type algorithm for imbalanced data clustering, IEEE Transactions on Cybernetics 51(3) (2021), 1598–1612. doi: 10.1109/TCYB.2019.2916196.

and Chang

, A many-objective particle swarm optimization with grid dominance ranking and clustering, Applied Soft Computing 96 (2020), 106661. doi: 10.1016/j.asoc.2020.106661.

10.

Gui

Peng

and Long

, Msgc: Multi-scale grid clustering by fusing analytical granularity and visual cognition for detecting hierarchical spatial patterns, Future Generation Computer Systems 112 (2020), 1038–1056. doi: 10.1016/j.future.2020.06.053.

11.

Dogan

and Birant

, K-centroid link: a novel hierarchical clustering linkage method, Applied Intelligence, 2021, 1–24. doi: 10.1007/s10489-021-02624-8.

12.

Kim

H.-J.

and Kim

, Fraud detection for job placement using hierarchical clusters-based deep neural networks, Applied Intelligence 49(8) (2019), 2842–2861. doi: 10.1007/s10489-019-01419-2.

13.

Zhu

Guo

Zhang

and Pang

, Registration of multi-view point sets under the perspective of expectation-maximization, IEEE Transactions on Image Processing 29 (2020), 9176–9189. doi: 10.1109/TIP.2020.3024096.

14.

Allassonnière

and Chevallier

, A new class of stochastic em algorithms. escaping local maxima and handling intractable sampling, Computational Statistics & Data Analysis 159 (2021), 107159. doi: 10.1016/j.csda.2020.107159.

15.

Zhang

Cao

Xie

Tao

and Xu

, Generalized latent multi-view subspace clustering, IEEE Transactions on Pattern Analysis and Machine Intelligence 42(1) (2020), 86–99. doi: 10.1109/TPAMI.2018.2877660.

16.

Wang

Ding

Tao

Gao

and Fu

, Generative partial multi-view clustering with adaptive fusion and cycle consistency, IEEE Transactions on Image Processing 30 (2021), 1771–1783. doi: 10.1109/TIP.2020.3048626.

17.

Zhang

Zhu

Cheng

Liu

and Luo

, Density decay graph-based density peak clustering, Knowledge-Based Systems 224 (2021), 107075. doi: 10.1016/j.knosys.2021.107075.

18.

Ester

Kriegel

H.-P.

Sander

and Xu

, A density-based algorithm for discovering clusters in large spatial databases with noise, 1996, 226–231. doi: 10.5555/3001460.3001507.

19.

Ankerst

Breunig

M.M.

Kriegel

H.-P.

and Sander

, Optics: Ordering points to identify the clustering structure, in: Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data, SIGMOD ’99, Association for Computing Machinery, New York, NY, USA, 1999, pp. 49–60. doi: 10.1145/304182.304187.

20.

Zhu

Tang

and Elahi

, Application of the novel harmony search optimization algorithm for dbscan clustering, Expert Systems with Applications 178 (2021), 115054. doi: 10.1016/j.eswa.2021.115054.

21.

Wang

and Han

, A method of two-stage clustering learning based on improved dbscan and density peak algorithm, Computer Communications 167 (2021), 75–84. doi: 10.1016/j.comcom.2020.12.019.

22.

Rodriguez

and Laio

, Clustering by fast search and find of density peaks, Science 344(6191) (2014), 1492–1496. doi: 10.1126/science.1242072.

23.

Ding

and Jia

, Study on density peaks clustering based on k-nearest neighbors and principal component analysis, Knowledge-Based Systems 99 (2016), 135–145. doi: 10.1016/j.knosys.2016.02.001.

24.

Jiang

Chen

Meng

Wang

and Li

, A novel density peaks clustering algorithm based on k nearest neighbors for improving assignment process, Physica A: Statistical Mechanics and its Applications 523 (2019), 702–713. doi: 10.1016/j.physa.2019.03.012.

25.

Chen

and Yu

P.S.

, A domain adaptive density clustering algorithm for data with varying density distribution, IEEE Transactions on Knowledge and Data Engineering 33(6) (2021), 2310–2321. doi: 10.1109/TKDE.2019.2954133.

26.

Yaohui

Zhengming

and Fang

, Adaptive density peak clustering based on k-nearest neighbors with aggregating strategy, Knowledge-Based Systems 133 (2017), 208–220. doi: 10.1016/j.knosys.2017.07.010.

27.

Zhu

Feng

and Huang

, Natural neighbor: A self-adaptive neighborhood method without parameter k, Pattern Recognition Letters 80 (2016), 30–36. doi: 10.1016/j.patrec.2016.05.007.

28.

A fast density peaks clustering algorithm with sparse search, Information Sciences 554 (2021), 61–83. doi: 10.1016/j.ins.2020.11.050.

29.

Xie

Gao

Xie

Liu

and Grant

P.W.

, Robust clustering by detecting density peaks and assigning points based on fuzzy weighted k-nearest neighbors, Information Sciences 354 (2016), 19–40. doi: 10.1016/j.ins.2016.03.011.

30.

Lotfi

Moradi

and Beigy

, Density peaks clustering based on density backbone and fuzzy neighborhood, Pattern Recognition 107 (2020), 107449. doi: 10.1016/j.patcog.2020.107449.

31.

Liu

Wang

and Yu

, Shared-nearest-neighbor-based clustering by fast search and find of density peaks, Information Sciences 450 (2018), 200–226. doi: 10.1016/j.ins.2018.03.031.

32.

Bryant

and Cios

, Rnn-dbscan: A density-based clustering algorithm using reverse nearest neighbor density estimates, IEEE Transactions on Knowledge and Data Engineering 30(6) (2018), 1109–1121. doi: 10.1109/TKDE.2017.2787640.

33.

Abbas

El-Zoghabi

and Shoukry

, Denmune: Density peak based clustering using mutual nearest neighbors, Pattern Recognition 109 (2021), 107589. doi: 10.1016/j.patcog.2020.107589.

34.

Huang

Zhu

Yang

and Feng

, A non-parameter outlier detection algorithm based on natural neighbor, Knowledge-Based Systems 92 (2016), 71–77. doi: 10.1016/j.knosys.2015.10.014.

35.

Gionis

Mannila

and Tsaparas

, Clustering aggregation, Acm Transactions on Knowledge Discovery from Data (TKDD) 1(1) (2007), 4–es.

36.

Zahn

, Graph-theoretical methods for detecting and describing gestalt clusters, IEEE Transactions on Computers C-20(1) (1971), 68–86. doi: 10.1109/T-C.1971.223083.

37.

and Medico

, Flame, a novel fuzzy clustering method for the analysis of dna microarray data, BMC Bioinformatics 8(3) (2007). doi: 10.1186/1471-2105-8-3.

38.

Chang

and Yeung

D.-Y.

, Robust path-based spectral clustering, Pattern Recognition 41(1) (2008), 191–203. doi: 10.1016/j.patcog.2007.04.010.

39.

Veenman

Reinders

and Backer

, A maximum variance cluster algorithm, IEEE Transactions on Pattern Analysis and Machine Intelligence 24(9) (2002), 1273–1280. doi: 10.1109/TPAMI.2002.1033218.

40.

Yanlong

and Hua

, Research on optimization of clustering algorithm performance based on dataset compression, Application Research of Computers 35 (2018), 1450–1453.

41.

Dua

and Graff

, UCI machine learning repository, 2017. http://archive.ics.uci.edu/ml.

42.

Dias

D.B.

Madeo

R.C.B.

Rocha

Biscaro

H.H.

and Peres

S.M.

, Hand movement recognition for brazilian sign language: A study using distance-based neural networks, in: 2009 International Joint Conference on Neural Networks, 2009, pp. 697–704. doi: 10.1109/IJCNN.2009.5178917.

43.

Wing

Greenwald

R.A.

Meng

C.-I.

Sigillito

V.G.

and Hutton

L.V.

, Neural networks for automated classification of ionospheric irregularities in hf radar backscattered signals, Radio Science 38(4) (2003). doi: 10.1029/2003RS002869.

44.

Chicco

and Jurman

, Machine learning can predict survival of patients with heart failure from serum creatinine and ejection fraction alone, BMC Med Inform Decis Mak 20(13) (2020), 1273–1280. doi: 10.1186/s12911-020-1023-5.

45.

Alzahrani

and Sadaoui

, Clustering and labeling auction fraud data, 2020, 269–283.

A domain density peak clustering algorithm based on natural neighbor

Abstract

Keywords

1. Introduction

2.1 DPC algorithm

(K-Nearest Neighbor).

(Reverse K-Nearest Neighbor).

(Natural neighbor).

(Stable state and natural eigenvalue).

(Noise points).

(Local domain density).

(Dense point).

4. Experimental results and analysis

4.1 Evaluation measures

Table 1 Synthetic datasets

4.4 Results on the synthetic datasets

4.5 Results on the UCI real datasets

5. Conclusion

Footnotes

Acknowledgments

References

Table 1
Synthetic datasets