# A Density Peak Clustering Algorithm Based on the K-Nearest Shannon Entropy and Tissue-Like P System

Authors: Zhenni Jiang; Xiyu Liu; Minghe Sun
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

This study proposes a novel method to calculate the density of the data points based on K-nearest neighbors and Shannon entropy. A variant of tissue-like P systems with active membranes is introduced to realize the clustering process. The new variant of tissue-like P systems can improve the efficiency of the algorithm and reduce the computation complexity. Finally, experimental results on synthetic and real-world datasets show that the new method is more effective than the other state-of-the-art clustering methods.


---

## Body

## 1. Introduction

Clustering is an unsupervised learning method, which aims to divide a given population into several groups or classes, called clusters, in such a way that similar objects are put into the same group and dissimilar objects are put into different groups. Clustering methods generally include five categories: partitioning methods, hierarchical methods, density-based methods, grid-based methods, and model-based methods ‎[1]. Partitioning and hierarchical methods can find spherical-shaped clusters but do not perform well on arbitrary clusters. Density-based clustering ‎[2] methods can be used to overcome this problem, which can model clusters as dense regions and boundaries as sparse regions. Three representative approaches of the density-based clustering method are DBSCAN (Density-Based Spatial Clustering of Application with Noise), OPTICS (Ordering Points to Identify the Clustering Structure), and DENCLUE (DENsity-based CLUstEring).Usually, an objective function measuring the clustering quality is optimized by an iterative process in some clustering algorithms. However, this approach may cause low efficiency. Thus, the density peaks clustering (DPC) algorithm was proposed by Rodriguez and Laio ‎[3] in 2014. This method can obtain the clusters in a single step regardless of the shape and dimensionality of the space. DPC is based on the idea that cluster centers are characterized by a higher density than the surrounding regions by a relatively large distance from points with higher densities. For the DPC algorithm, scholars have done a lot of research. However, DPC still has several challenges that need to be addressed. First, the local density of data points can be affected by the cut off distance, which can influence the clustering results. Second, the number of clusters needs to be decided by users, but the manual selection of the cluster centers can influence the clustering result. Cong et al. ‎[4] proposed a clustering model for high dimensional data based on DPC that accomplishes clustering simply and directly for data with more than six-dimensions with arbitrary shapes. The problem in this model is that clustering effect is not ideal for different classes and big differences in order of magnitude. Xu et al. ‎[5] introduced a novel approach, called density peaks clustering algorithm based on grid (DPCG). But this method also needs to rely on the user experiment in the choice of clustering centers. Bie et al. ‎[6] proposed a fuzzy-CFSFDP method for adaptively but effectively selecting the cluster centers. Du et al. ‎[7] proposed a new DPC algorithm using geodesic distances. And Du et al. ‎[8] also proposed a FN-DP (fuzzy neighborhood density peaks) clustering algorithm. But they cannot select clustering center automatic and the FN-DP algorithm can cost much time in the calculation of the similarity matrix. Hou and Cui ‎[9] introduced a density normalization step to make large-density clusters partitioned into multiple parts and small-density clusters merged with other clusters. Xu et al. proposed a FDPC algorithm based on a novel merging strategy motivated by support vector machines ‎[10]. But it also has the problem of higher complexity and needs to select the clustering center by users. Liu et al. ‎[11] proposed a shared-nearest-neighbor-based clustering by fast search and find of density peaks (SNN-DPC) algorithm. Based on prior assumptions of consistency for semisupervised learning algorithms, some scholars also made assumptions of consistency for density-based clustering. The first assumption is of local consistency, which means nearby points are likely to have similar local density, and the second assumption is of global consistency, which means points in the same high-density area (or the same structure, i.e., the same cluster) are likely to have the same label ‎[12]. This method also cannot find the clustering centers automatically. Although many studies about DPC have been reported, it still has many problems that need to be studied.Membrane computing proposed by Pǎun ‎[13], as a new branch of natural computing, abstracts out computational models from the structures and functions of biological cells and from the collaboration between organs and tissues. Membrane computing mainly includes three basic computational models, i.e., the cell-like P system, the tissue-like P system, and the neural-like P system. In the computation process, each cell is treated as an independent unit, each unit operates independently and does not interfere with each other, and the entire membrane system operates in maximally parallel. Over the past years, many variants of membrane systems have been proposed ‎[14–18], including membrane algorithms of solving global optimization problems. In recent years, applications of membrane computing have attracted a lot of attention from researchers ‎[19–22]. There are also some other applications; for example, membrane systems are used to solve multiobjective fuzzy clustering problems ‎[23], solve unsupervised learning algorithms ‎[24], solve automatic fuzzy clustering problems ‎[25], and solve the problems of fault diagnosis of power systems ‎[26]. Liu et al. ‎[27] proposed an improved Apriori algorithm based on an Evolution-Communication tissue-Like P System. Liu and Xue ‎[28] introduced a P system on simplices. Zhao et al. ‎[29] proposed a spiking neural P system with neuron division and dissolution.Based on previous works, the main motivation of this work is using membrane systems to develop a framework for a density peak clustering algorithm. A new method of calculating the density of the data points is proposed based on the K-nearest neighbors and Shannon entropy. A variant of the tissue-like P system with active membranes is used to realize the clustering process. The new model of the P system can improve efficiency and reduce computation complexity. Experimental results show that this method is more effective and accurate than the state-of-the-art methods.The rest of this paper is organized as follows. Section2 describes the basic DPC algorithm and the tissue-like P system. Section 3 introduces the tissue-like P system with active membranes for DPC based on the K-nearest neighbors and Shannon entropy and describes the clustering procedure. Section 4 reports experimental results on synthetic datasets and UCI datasets. Conclusions are drawn and future research directions are outlined in Section 5.


## 2. Preliminaries

### 2.1. The Original Density Peak Clustering Algorithm

Rodriguez and Laio [3] proposed the DPC algorithm in 2014. This algorithm is based on the idea that cluster centers have higher densities than the surrounding regions and the distances among cluster centers are relatively large. It has three important parameters. The first one ρi is the local density of data point i, the second one δi is the minimum distance between data point i and other data points with higher density, and the third one γi=ρi×δi is the product of the other two. The first two parameters correspond to two assumptions of the DPC algorithm. One assumption is that cluster centers have higher density than the surrounding regions. The other assumption is that this point has larger distance from the points in other clusters than from points in the same cluster. In the following, the computations of ρi and δi are discussed in detail.LetX={x1,x2,…,xn} be a dataset with n data points. Each xi has M attributes. Therefore, xij is thejth attribute of data point xi. The Euclidean distance between the data points xi and xj can be expressed as follows:(1)dij=dxi,xj=xi-xjThe local densityρi of the data point xi is defined as(2)ρi=∑j≠iχdxi-xj-dcwith(3)χx=1,x<00,x>0,where dc is the cutoff distance. In fact, ρi is the number of data points adjacent to data point xi. The minimal distance δi between data point xi and any other data points xi′ with a higher density ρi′ is given by(4)δi=minj:ρi′>ρi⁡dij,if∃ii,s.t.ρi′>ρimaxi′⁡dii′,otherwiseAfterρi and δi are calculated for each data point xi, a decision graph with δi on the vertical axis and ρi on the horizontal axis can be plotted. This graph can be used to find the cluster centers and then to assign each remaining data point to the cluster with the shorted distance.The computation of the local densities of the data points is a key factor for the effectiveness and efficiency of the DPC. There are many other ways to calculate the local densities. For example, the local density ofxi can be computed using (5) in the following [3]: (5)ρi=∑jexp⁡-dij2dc2The way in (5) is suitable for “small” datasets. In fact, it is difficult to judge if the dataset is small or large. When (5) is used to calculate the local density, the results can be greatly affected by the cutoff distance dc.Each component on the right side of (5) is a Gaussian function. Figure 1 visualizes the function exp⁡(-t) and two Gaussian functions exp⁡(-t2/σ2) with different values of σ. The blue and red curves are the curves of exp⁡(-t2/σ2) with σ=1 and σ=2, respectively. The curve with a smaller value of σ declines more quickly than the curve with a larger value of σ. Comparing the curve of exp⁡(-t), the yellow dash dotted curve, with the curves of exp⁡(-t2/σ2), it can be found that values of exp⁡(-t2/σ2) are greater than those of exp⁡(-t) when t<σ2 but decay faster when t>σ2. This means that if the value of the parameter σ needs to be decided manually in the density calculation, the result of the calculated densities will be influenced by the selected value. This analysis shows that the parameter σ has a big effect on the calculated results. Furthermore, the density in (5) can be influenced by the cutoff distance dc. To eliminate the influence from the cutoff distance dc and give a uniform metric for datasets with any size, Du et al. [30] proposed the K-nearest neighbor method. The local density in Du et al. [30] is given by(6)ρi=exp⁡-1K∑j∈KNNidij2,where K is an input parameter and KNNi is the set of the K nearest neighbors of data point xi. However, this method did not consider the influence of the position of the data point on its own density. Therefore, this current study proposes a novel method to calculate the densities.Figure 1
Three different function curves.


### 2.2. The Tissue-Like P System with Active Membrane

A tissue-like P system has a graphical structure. The nodes of the graph correspond to the cells and the environment in the tissue-like P system, whereas the edges of the graph represent the channels for communication between the cells. The tissue-like P system is slightly more complicated than the cell-like P system. Each cell has a different state. Only the state that meets the requirement specified by the rules can be changed. The basic framework of the tissue-like P system used in this study is shown in Figure2.Figure 2
Membrane structure of a tissue-like P system.A P system with active membranes is a construct:(7)∏=O,Z,H,ω1,…,ωm,E,ch,si,ji,j∈ch,Ri,ji,j∈ch,i0where(1)
O is the set of alphabets of all objects which appear in the system;(2)
Z represents the states of the alphabets;(3)
H is the set of labels of the membranes;(4)
ω1,…,ωm are the initial multiple objects in cells 1 tom;(5)
E⊆O is the set of objects present in an arbitrary number of copies in the environment;(6)
ch⊆{(i,j)∣i,j∈{0,1,…,m},i≠j} is the set of channels between cells and between cells and the environment;(7)
s(i,j) is the initial state of the channel (i, j);(8)
R(i,j) is a finite set of symport/antiport rules of the form (s,x/y,s′) with s,s′∈Z and x,y∈O:
(i)
[a→b]h, where h∈H, a∈O, and b∈O.(Object evolution rules: an object is evolved into another in a membrane).(ii)
a[]h→[b]h, where h∈H and a,b∈O. (Send-in communication rules: an object is introduced into a membrane and may be modified during the process).(iii)
[a]h→[]hb, where h∈H,a,b∈O. (Send-out communication rules: an object is sent out of the membrane and may be modified during the process).(iv)
[a]h→[b]h1[c]h2, where h,h1,h2∈H and a,b∈O. (Division rules for elementary membranes: the membrane is divided into two membranes with possibly different labels; the object specified in the rule is replaced by possibly new objects in the two new membranes; and the remaining objects are duplicated in the process).(9)
i0∈{1,…,m} is the output cell.The biggest difference between a cell-like P system and a tissue-like P system is that each cell can communicate with the environment in the tissue-like P system, but only the skin membrane can communicate with the environment in the cell-like P system. This does not mean that any two cells in the tissue-like P system can communicate with each other. If there is no direct communication channel between the two cells, they can communicate through the environment indirectly.


## 2.1. The Original Density Peak Clustering Algorithm

Rodriguez and Laio [3] proposed the DPC algorithm in 2014. This algorithm is based on the idea that cluster centers have higher densities than the surrounding regions and the distances among cluster centers are relatively large. It has three important parameters. The first one ρi is the local density of data point i, the second one δi is the minimum distance between data point i and other data points with higher density, and the third one γi=ρi×δi is the product of the other two. The first two parameters correspond to two assumptions of the DPC algorithm. One assumption is that cluster centers have higher density than the surrounding regions. The other assumption is that this point has larger distance from the points in other clusters than from points in the same cluster. In the following, the computations of ρi and δi are discussed in detail.LetX={x1,x2,…,xn} be a dataset with n data points. Each xi has M attributes. Therefore, xij is thejth attribute of data point xi. The Euclidean distance between the data points xi and xj can be expressed as follows:(1)dij=dxi,xj=xi-xjThe local densityρi of the data point xi is defined as(2)ρi=∑j≠iχdxi-xj-dcwith(3)χx=1,x<00,x>0,where dc is the cutoff distance. In fact, ρi is the number of data points adjacent to data point xi. The minimal distance δi between data point xi and any other data points xi′ with a higher density ρi′ is given by(4)δi=minj:ρi′>ρi⁡dij,if∃ii,s.t.ρi′>ρimaxi′⁡dii′,otherwiseAfterρi and δi are calculated for each data point xi, a decision graph with δi on the vertical axis and ρi on the horizontal axis can be plotted. This graph can be used to find the cluster centers and then to assign each remaining data point to the cluster with the shorted distance.The computation of the local densities of the data points is a key factor for the effectiveness and efficiency of the DPC. There are many other ways to calculate the local densities. For example, the local density ofxi can be computed using (5) in the following [3]: (5)ρi=∑jexp⁡-dij2dc2The way in (5) is suitable for “small” datasets. In fact, it is difficult to judge if the dataset is small or large. When (5) is used to calculate the local density, the results can be greatly affected by the cutoff distance dc.Each component on the right side of (5) is a Gaussian function. Figure 1 visualizes the function exp⁡(-t) and two Gaussian functions exp⁡(-t2/σ2) with different values of σ. The blue and red curves are the curves of exp⁡(-t2/σ2) with σ=1 and σ=2, respectively. The curve with a smaller value of σ declines more quickly than the curve with a larger value of σ. Comparing the curve of exp⁡(-t), the yellow dash dotted curve, with the curves of exp⁡(-t2/σ2), it can be found that values of exp⁡(-t2/σ2) are greater than those of exp⁡(-t) when t<σ2 but decay faster when t>σ2. This means that if the value of the parameter σ needs to be decided manually in the density calculation, the result of the calculated densities will be influenced by the selected value. This analysis shows that the parameter σ has a big effect on the calculated results. Furthermore, the density in (5) can be influenced by the cutoff distance dc. To eliminate the influence from the cutoff distance dc and give a uniform metric for datasets with any size, Du et al. [30] proposed the K-nearest neighbor method. The local density in Du et al. [30] is given by(6)ρi=exp⁡-1K∑j∈KNNidij2,where K is an input parameter and KNNi is the set of the K nearest neighbors of data point xi. However, this method did not consider the influence of the position of the data point on its own density. Therefore, this current study proposes a novel method to calculate the densities.Figure 1
Three different function curves.


## 2.2. The Tissue-Like P System with Active Membrane

A tissue-like P system has a graphical structure. The nodes of the graph correspond to the cells and the environment in the tissue-like P system, whereas the edges of the graph represent the channels for communication between the cells. The tissue-like P system is slightly more complicated than the cell-like P system. Each cell has a different state. Only the state that meets the requirement specified by the rules can be changed. The basic framework of the tissue-like P system used in this study is shown in Figure2.Figure 2
Membrane structure of a tissue-like P system.A P system with active membranes is a construct:(7)∏=O,Z,H,ω1,…,ωm,E,ch,si,ji,j∈ch,Ri,ji,j∈ch,i0where(1)
O is the set of alphabets of all objects which appear in the system;(2)
Z represents the states of the alphabets;(3)
H is the set of labels of the membranes;(4)
ω1,…,ωm are the initial multiple objects in cells 1 tom;(5)
E⊆O is the set of objects present in an arbitrary number of copies in the environment;(6)
ch⊆{(i,j)∣i,j∈{0,1,…,m},i≠j} is the set of channels between cells and between cells and the environment;(7)
s(i,j) is the initial state of the channel (i, j);(8)
R(i,j) is a finite set of symport/antiport rules of the form (s,x/y,s′) with s,s′∈Z and x,y∈O:
(i)
[a→b]h, where h∈H, a∈O, and b∈O.(Object evolution rules: an object is evolved into another in a membrane).(ii)
a[]h→[b]h, where h∈H and a,b∈O. (Send-in communication rules: an object is introduced into a membrane and may be modified during the process).(iii)
[a]h→[]hb, where h∈H,a,b∈O. (Send-out communication rules: an object is sent out of the membrane and may be modified during the process).(iv)
[a]h→[b]h1[c]h2, where h,h1,h2∈H and a,b∈O. (Division rules for elementary membranes: the membrane is divided into two membranes with possibly different labels; the object specified in the rule is replaced by possibly new objects in the two new membranes; and the remaining objects are duplicated in the process).(9)
i0∈{1,…,m} is the output cell.The biggest difference between a cell-like P system and a tissue-like P system is that each cell can communicate with the environment in the tissue-like P system, but only the skin membrane can communicate with the environment in the cell-like P system. This does not mean that any two cells in the tissue-like P system can communicate with each other. If there is no direct communication channel between the two cells, they can communicate through the environment indirectly.


## 3. The Proposed Method

### 3.1. Density Metric Based on the K-Nearest Neighbors and Shannon Entropy

DPC still has some defects. The current DPC algorithm has the obvious shortcoming that it needs to set the value of the cutoff distancedc manually in advance. This value will largely affect the final clustering results. In order to overcome this shortcoming, a new method is proposed to calculate the density metric based on the K-nearest neighbors and Shannon entropy.K-nearest neighbors (KNN) is usually used to measure a local neighborhood of an instance in the fields of classification, clustering, local outlier detection, etc. The aim of this approach is to find the K-nearest neighbors of a sample among N samples. In general, the distances between points are achieved by calculating the Euclidean distance. Let KNN(i) be a set of nearest neighbors of a point i and it can be expressed as(8)KNNi=j∣dij≤di,kthi,where d(xi,xj) is the Euclidean distance between xi and xj and kth(i) is the k-th nearest neighbor of i. Local regions measured by KNN are often termed K-nearest neighborhood, which, in fact, is a circular or spherical area or radius R=di,kth(i). Therefore, KNN-based method cannot apply to handle datasets with clusters nonspherical distributions. Therefore, these methods usually have poor clustering results when handling datasets with clusters of different shapes.Shannon entropy measures the degree of molecular activity. The more unstable the system is, the larger the value of the Shannon entropy is, and vice versa. The Shannon entropy, represented byH(X), is given by(9)HX=-∑i=0Npilog2⁡pi,where X is the set of objects and pi is the probability of object i appearing in X. When H(X) is used to measure the distance between the clusters, the smaller the value of H(X) is, the better the clustering result is. Therefore, the Shannon entropy is introduced to calculate the data point density in the K-nearest neighbor method, so that the final density calculation not only considers the distance metric, but also adds the influence of the data point position to the density of the data point.However, the decision graph is calculated by the product ofρi and δi. A larger value of ρi makes it easier to choose the best clustering centers. Therefore, the reciprocal form of the Shannon entropy is adopted. The metrics for ρi and δi may be inconsistent, which directly leads to ρi and δi playing different roles in the calculation of the decision graph. Hence, it is necessary to normalize ρi and δi.The specific calculation method is as follows. First, the local density of data pointxi is calculated:(10)wi′=∑j=1,j≠in1xj-xi,where xi and xj are data points and wi′ is the density of data point xi. Next, the density of data point xi is normalized and the normalized density is denoted as wi:(11)wi=wi′∑i=1nwi′.Finally, the density metric which uses the idea of the K-nearest neighbor method is defined as(12)ρi=-11/K∑i∈KNNwilog⁡wi.To guarantee the consistence of the metrics ofρi and δi, δi also needs to be normalized.


### 3.2. Tissue-Like P System with Active Membranes for Improved Density Peak Clustering

In the following, a tissue-like P system with active membranes for density peak clustering, called KST-DPC, is proposed. As mentioned before, assume the dataset withn data points is represented by X={x1,x2,…,xn}. Before performing any specific calculation of the DPC algorithm, the Euclidean distance between each pair of data points in the dataset is calculated and the result is stored in the form of a matrix. The initial configuration of this P system is shown in Figure 3.Figure 3
The initial configuration of the tissue-like P system.When the system is initialized, the objectsxi,b1,b2,…,bn are in membrane i for 1≤i≤n and object λ is in membrane n+1, where λ means there is no object. First, the Euclidean distance wij between the data points xi and xj (represented by bj for 1≤j≤n) is calculated with the rule r1={[xib1b2⋯bn]i→[di,1wi,1di,2wi,2⋯di,nwi,n]i∣1≤i≤n}. Note that xj for 1≤j≤n are expressed as b1b2⋯bn. The results are stored as the distance matrix, also called the dissimilarity matrix, Dnn,(13)Dnn=w11w12⋯w1nw21w22⋯w2n⋯wn1wn2⋯wnn.At the beginning, there aren+1 membranes in the P system. After the distances are calculated, objects xi,di,1wi1,di,2wi2⋯di,nwi,n are placed in membrane i for 1≤i≤n. In the next step, the densities of the data points are calculated by the rule r2={[di,1wi,1di,2wi,2⋯di,nwi,n]i→[wi′]i∣1≤i≤n}. Then the send-in and send-out communication rules are used to calculate the values of ρi, δi, and γi and to put them in membrane i for 1≤i≤n. Next, according to the sorted results of γi for 1≤i≤n, the number of clusters k can be determined. The rule of the active membranes is used to split membrane n+1 into k membranes as shown in Figure 4. The k cluster centers are put in membranes n+1 to n+k, respectively. Finally, the remaining data points are divided and each is put into a membrane with a cluster center that is closest to the data point. Up to this point, the clusters are obtained.Figure 4
The tissue-like membrane system in the calculation process.The main steps of KST-DPC is summarized as in Algorithm1.Algorithm 1:
Inputs:dataset X, parameter K Output:Clusters Step1: The objects xi,b1,b2,…,bn are in membrane i for 1≤i≤n and object λ is in membrane n+1; Step2: Compute the Euclidean distance matrix wij by the rule1; Step3: Compute the local densities of the data points by the rule2 and normalize them using (10) and (11); Step4: Calculate ρi and δi for data point i using (12) and (4) in every membrane i, respectively; Step5: Calculate γi=ρi×δi for all 1≤i≤n in membrane i and sort them by descend, and select the top K values as the initial cluster center. So as to determine the centers of the clusters; Step6: Split the membrane n+1 to Kmembranes by the division rules, which membranes can be number from n+1 to n+k; Step7: The K clustering centers are put in membranes n+1 to n+k, respectively. Step8: Assign each remaining point to the membrane with the nearest cluster center; Step9: Return the clustering result.


### 3.3. Time Complexity Analysis of KST-DPC

As usual, computations in the cells in the tissue-like P system can be implemented in parallel. Because of the parallel implementation, the generation of the dissimilarity matrix usesn computation steps. The generation of the data points densities needs 1 computation step. The calculation of the final density ρi uses k computation steps. The calculation of δi needs n steps. The calculation of γi uses 1 step. nlog⁡n steps are used to sort γi for 1≤i≤n. Finally, the final clustering needs 1 more computation step. Therefore, the total time complexity of KST-DPC is n+1+k+n+1+nlog⁡n+1=O(nlog⁡n). The time complexity of the DPC-KNN is O(n2). As compared to DPC-KNN, KST-DPC reduces the time complexity by transferring time complexity to space complexity. The above analysis demonstrates that the overall time complexity of KST-DPC is superior to that of DPC-KNN.


## 3.1. Density Metric Based on the K-Nearest Neighbors and Shannon Entropy

DPC still has some defects. The current DPC algorithm has the obvious shortcoming that it needs to set the value of the cutoff distancedc manually in advance. This value will largely affect the final clustering results. In order to overcome this shortcoming, a new method is proposed to calculate the density metric based on the K-nearest neighbors and Shannon entropy.K-nearest neighbors (KNN) is usually used to measure a local neighborhood of an instance in the fields of classification, clustering, local outlier detection, etc. The aim of this approach is to find the K-nearest neighbors of a sample among N samples. In general, the distances between points are achieved by calculating the Euclidean distance. Let KNN(i) be a set of nearest neighbors of a point i and it can be expressed as(8)KNNi=j∣dij≤di,kthi,where d(xi,xj) is the Euclidean distance between xi and xj and kth(i) is the k-th nearest neighbor of i. Local regions measured by KNN are often termed K-nearest neighborhood, which, in fact, is a circular or spherical area or radius R=di,kth(i). Therefore, KNN-based method cannot apply to handle datasets with clusters nonspherical distributions. Therefore, these methods usually have poor clustering results when handling datasets with clusters of different shapes.Shannon entropy measures the degree of molecular activity. The more unstable the system is, the larger the value of the Shannon entropy is, and vice versa. The Shannon entropy, represented byH(X), is given by(9)HX=-∑i=0Npilog2⁡pi,where X is the set of objects and pi is the probability of object i appearing in X. When H(X) is used to measure the distance between the clusters, the smaller the value of H(X) is, the better the clustering result is. Therefore, the Shannon entropy is introduced to calculate the data point density in the K-nearest neighbor method, so that the final density calculation not only considers the distance metric, but also adds the influence of the data point position to the density of the data point.However, the decision graph is calculated by the product ofρi and δi. A larger value of ρi makes it easier to choose the best clustering centers. Therefore, the reciprocal form of the Shannon entropy is adopted. The metrics for ρi and δi may be inconsistent, which directly leads to ρi and δi playing different roles in the calculation of the decision graph. Hence, it is necessary to normalize ρi and δi.The specific calculation method is as follows. First, the local density of data pointxi is calculated:(10)wi′=∑j=1,j≠in1xj-xi,where xi and xj are data points and wi′ is the density of data point xi. Next, the density of data point xi is normalized and the normalized density is denoted as wi:(11)wi=wi′∑i=1nwi′.Finally, the density metric which uses the idea of the K-nearest neighbor method is defined as(12)ρi=-11/K∑i∈KNNwilog⁡wi.To guarantee the consistence of the metrics ofρi and δi, δi also needs to be normalized.


## 3.2. Tissue-Like P System with Active Membranes for Improved Density Peak Clustering

In the following, a tissue-like P system with active membranes for density peak clustering, called KST-DPC, is proposed. As mentioned before, assume the dataset withn data points is represented by X={x1,x2,…,xn}. Before performing any specific calculation of the DPC algorithm, the Euclidean distance between each pair of data points in the dataset is calculated and the result is stored in the form of a matrix. The initial configuration of this P system is shown in Figure 3.Figure 3
The initial configuration of the tissue-like P system.When the system is initialized, the objectsxi,b1,b2,…,bn are in membrane i for 1≤i≤n and object λ is in membrane n+1, where λ means there is no object. First, the Euclidean distance wij between the data points xi and xj (represented by bj for 1≤j≤n) is calculated with the rule r1={[xib1b2⋯bn]i→[di,1wi,1di,2wi,2⋯di,nwi,n]i∣1≤i≤n}. Note that xj for 1≤j≤n are expressed as b1b2⋯bn. The results are stored as the distance matrix, also called the dissimilarity matrix, Dnn,(13)Dnn=w11w12⋯w1nw21w22⋯w2n⋯wn1wn2⋯wnn.At the beginning, there aren+1 membranes in the P system. After the distances are calculated, objects xi,di,1wi1,di,2wi2⋯di,nwi,n are placed in membrane i for 1≤i≤n. In the next step, the densities of the data points are calculated by the rule r2={[di,1wi,1di,2wi,2⋯di,nwi,n]i→[wi′]i∣1≤i≤n}. Then the send-in and send-out communication rules are used to calculate the values of ρi, δi, and γi and to put them in membrane i for 1≤i≤n. Next, according to the sorted results of γi for 1≤i≤n, the number of clusters k can be determined. The rule of the active membranes is used to split membrane n+1 into k membranes as shown in Figure 4. The k cluster centers are put in membranes n+1 to n+k, respectively. Finally, the remaining data points are divided and each is put into a membrane with a cluster center that is closest to the data point. Up to this point, the clusters are obtained.Figure 4
The tissue-like membrane system in the calculation process.The main steps of KST-DPC is summarized as in Algorithm1.Algorithm 1:
Inputs:dataset X, parameter K Output:Clusters Step1: The objects xi,b1,b2,…,bn are in membrane i for 1≤i≤n and object λ is in membrane n+1; Step2: Compute the Euclidean distance matrix wij by the rule1; Step3: Compute the local densities of the data points by the rule2 and normalize them using (10) and (11); Step4: Calculate ρi and δi for data point i using (12) and (4) in every membrane i, respectively; Step5: Calculate γi=ρi×δi for all 1≤i≤n in membrane i and sort them by descend, and select the top K values as the initial cluster center. So as to determine the centers of the clusters; Step6: Split the membrane n+1 to Kmembranes by the division rules, which membranes can be number from n+1 to n+k; Step7: The K clustering centers are put in membranes n+1 to n+k, respectively. Step8: Assign each remaining point to the membrane with the nearest cluster center; Step9: Return the clustering result.


## 3.3. Time Complexity Analysis of KST-DPC

As usual, computations in the cells in the tissue-like P system can be implemented in parallel. Because of the parallel implementation, the generation of the dissimilarity matrix usesn computation steps. The generation of the data points densities needs 1 computation step. The calculation of the final density ρi uses k computation steps. The calculation of δi needs n steps. The calculation of γi uses 1 step. nlog⁡n steps are used to sort γi for 1≤i≤n. Finally, the final clustering needs 1 more computation step. Therefore, the total time complexity of KST-DPC is n+1+k+n+1+nlog⁡n+1=O(nlog⁡n). The time complexity of the DPC-KNN is O(n2). As compared to DPC-KNN, KST-DPC reduces the time complexity by transferring time complexity to space complexity. The above analysis demonstrates that the overall time complexity of KST-DPC is superior to that of DPC-KNN.


## 4. Test and Analysis

### 4.1. Data Sources

Experiments on six synthetic datasets and four real-world datasets are carried out to test the performance of KST-DPC. The synthetic datasets are fromhttp://cs.uef.fi/sipu/datasets/. These datasets are commonly used as benchmarks to test the performance of clustering algorithms. The real-world datasets used in the experiments are from the UCI Machine Learning Repository [31]. These datasets are chosen to test the ability of KST-DPC in identifying clusters having arbitrary shapes without being affected by noise, size, or dimensions of the datasets. The numbers of features (dimensions), data points (instances), and clusters vary in each of the datasets. The details of the synthetic and real-world datasets are listed in Tables 1 and 2, respectively.Table 1
Synthetic datasets.
Dataset Instances Dimensions Clusters Spiral 312 2 3 Compound 7266 2 6 Jain 373 2 2 Aggregation 788 2 7 R15 600 2 15 D31 3100 2 31Table 2
Real-world datasets.
Dataset Instances Dimensions Clusters Vertebral 310 7 2 Seeds 210 7 3 Breast cancer 699 10 2 Banknotes 1372 5 2The performance of KST-DPC was compared with those of the well-known clustering algorithms SC ‎[32], DBSCAN ‎[33], and DPC-KNN ‎[28, 34]. The codes for SC and DBSCAN are provided by their authors. The code of DPC is optimized by using the matrix operation instead of iteration cycle based on the original code provided by Rodriguez and Laio [3] to reduce running time.The performances of the above clustering algorithms are measured in clustering quality or Accuracy (Acc) and Normalized Mutual Information (NMI). They are very popular measures for testing the performance of clustering algorithms. The larger the values are, the better the results are. The upper bound of these measures is 1.


### 4.2. Experimental Results on the Synthetic Datasets

In this subsection, the performances of KST-DPC, DPC-KNN, DBSCAN, and SC are reported on the six synthetic datasets. The clustering results by the four clustering algorithms for the six synthetic datasets are color coded and displayed in two-dimensional spaces as shown in Figures5–10. The results of the four clustering algorithms on a dataset are shown as four parts in a single figure. The cluster centers of the KST-DPC and DPC-KNN algorithms are marked in the figures with different colors. For DBSCAN, it is not meaningful to mark the cluster centers because they are chosen randomly. Each clustering algorithm ran multiple times on each dataset and the best result of each clustering algorithm is displayed.Figure 5
Clustering results of the Spiral dataset by the four clustering algorithms.
(a)
KST-DPC (b)
DPC-KNN (c)
DBSCAN (d)
SCFigure 6
Clustering results of the Compound dataset by the four clustering algorithms.
(a)
KST-DPC (b)
DPC-KNN (c)
DBSCAN (d)
SCFigure 7
Clustering results of the Jain dataset by the four clustering algorithms.
(a)
KST-DPC (b)
DPC-KNN (c)
DBSCAN (d)
SCFigure 8
Clustering results of the Aggregation dataset by the four clustering algorithms.
(a)
KST-DPC (b)
DPC-KNN (c)
DBSCAN (d)
SCFigure 9
Clustering results of the R15 dataset by the four clustering algorithms.
(a)
KST-DPC (b)
DPC-KNN (c)
DBSCAN (d)
SCFigure 10
Clustering results of the D31 dataset by the four clustering algorithms.
(a)
KST-DPC (b)
DPC-KNN (c)
DBSCAN (d)
SCThe performance measures of the four clustering algorithms on the six synthetic datasets are reported in Table3. In Table 3, the column “Par” for each algorithm is the number of parameters the users need to set. KST-DPC and DPC-KNN have only one parameterK, which is the number of nearest neighbors to be prespecified. In this paper, the value of K is determined by the percentage of the data points. It references the method in [34]. For each dataset, we adjust the percentage of data points in the KNN for the multiple times and find the optimal percentage that can make the final clustering reach the best. Because we perform more experiments, we only list the best result in Tables 3 and 4. And in order to be consistent wi other parameters in the table, we directly convert the percentage of data points into specific K values. DBSCAN has two input parameters, the maximum radiusEps and the minimum pointMinPts. The SC algorithm needs the true number of clusters. C1 in Table 3 refers to the number of cluster centers found by the algorithms. The performance measures including Acc and NMI are presented in Table 3 for the four clustering algorithms on the six synthetic datasets.Table 3
Results on the synthetic datasets.
Algorithm Par C1 Acc NMI Algorithm Par C1 Acc NMI Spiral     Compound KST-DPC 16 3 1.00 1.00 KST-DPC 217 6 0.98 0.95 DPC-KNN 20 3 1.00 1.00 DPC-KNN 360 6 0.6466 0.7663 DBSCAN 1.2/3 3 1.00 1.00 DBSCAN 1.5/3 5 0.8596 0.9429 SC 3 3 1.00 1.00 SC 6 6 0.6015 0.7622 Jain     Aggregation KST-DPC 4 2 1.00 1.00 KST-DPC 40 7 1.00 1.00 DPC-KNN 8 2 0.9035 0.5972 DPC-KNN 40 7 0.9987 0.9957 DBSCAN 2.62/4 2 1.00 1.00 DBSCAN 1.59/3 5 0.8274 0.8894 SC 2 2 1.00 1.00 SC 7 7 0.9937 0.9824 R15     D31 KST-DPC 20 15 1.00 0.99 KST-DPC 25 31 1.0000 1.0000 DPC-KNN 20 15 1.00 0.99 DPC-KNN 25 31 0.9700 0.9500 DBSCAN 0.4/5 13 0.78 0.9155 DBSCAN 0.46/3 27 0.6516 0.8444 SC 15 15 0.9967 0.9942 SC 31 31 0.9765 0.9670Table 4
Results on the real-world datasets.
Algorithm Par C1 Acc NMI Algorithm Par C1 Acc NMI Vertebral     Seeds KST-DPC 9 2 0.6806 0.0313 KST-DPC 4 3 0.8429 0.6574 DPC-KNN 9 2 0.6806 0.0821 DPC-KNN 6 3 0.8143 0.6252 DBSCAN 7/48 2 0.6742 -- DBSCAN 0.92/7 3 0.5857 0.4835 SC 2 2 -- -- SC 3 3 0.6071 0.5987 Breast cancer     Banknotes KST-DPC 70 2 0.8624 0.4106 KST-DPC 68 2 0.8434 0.7236 DPC-KNN 76 2 0.7954 0.3154 DPC-KNN 82 2 0.7340 0.3311 DBSCAN 6/20 2 0.6552 0.0872 DBSCAN 6.5/5 2 0.5554 6.7210e-16 SC 2 2 -- -- SC 2 2 0.6152 0.0598The Spiral dataset has 3 clusters with 312 data points embracing each other. Table3 and Figure 5 show that KST-DPC, DPC-KNN, DBSCAN, and SC can all find the correct number of clusters and get the correct clustering results. All the benchmark values are 1.00 reflecting the four algorithms all performing perfectly well on the Spiral dataset.The Compound dataset has 6 clusters with 399 data points. From Table3 and Figure 6, it is obvious that KST-DPC can find the ideal clustering result; DBSCAN cannot find the right clusters whereas DPC-KNN and SC cannot find the clustering centers. Because DPC has a special assignment strategy [3], it may assign data points erroneously to clusters once a data point with a higher density is assigned to an incorrect cluster. For this reason, some data points belonging to cluster 1 are incorrectly assigned to cluster 2 or 3 as shown in Figures 6(b)–6(d). DBSCAN has some prespecified parameters that can have heavy effects on the clustering results. As shown in Figure 6(c), two clusters are merged into one cluster in two occasions. KST-DPC obtained Acc and NMI values higher than those obtained by the other algorithms.The Jain dataset has two clusters with 373 data points in a 2 dimensional space. The clustering results show that KST-DPC, DBSCAN, and SC can get correct results and both of the benchmark values are 1.00. The experimental results of the 4 algorithms are shown in Table3 and the clustering results are displayed in Figure 7. DPC-KNN devides some points that should belong to the bottom cluster into the upper cluster. Although all the four clustering algorithms can find the correct number of clusters, KST-DPC, DBSCAN, and SC are more effective because they can put all the data points into the correct clusters.The Aggregation dataset has 7 clusters with different sizes and shapes and two pairs of clusters connected to each other. Figure8 shows that both the KST-DPC and DPC-KNN algorithms can effectively find the cluster centers and correct clusters, except that an individual data point is put into an incorrect cluster by DPC-KNN. Table 3 shows that the benchmark values of KST-DPC are all 1.00 and those of DPC-KNN are close to 1.00. SC also can recognize all clusters, but the values of Acc and NMI are lower than those of DPC-KNN. DBSCAN did not find all clusters and could not partition the clusters connected to each other.The R15 dataset has 15 clusters containing 600 data points. The clusters are slightly overlapping and are distributed randomly in a 2-dimensional space. One cluster lays in the center of the 2-dimensional space and is closely surrounded by seven other clusters. The experimental results of the 4 algorithms are shown in Table3 and the clustering results are displayed in Figure 9. KST-DPC and DPC-KNN can both find the correct cluster centers and assign almost all data points to their corresponding clusters. SC also obtained good experimental result, but DBSCAN did not find all clusters.The D31 dataset has 31 clusters and contains 3100 data points. These clusters are slightly overlapping and distribute randomly in a 2-dimensional space. The experimental results of the 4 algorithms are shown in Table3 and the clustering results are displayed in Figure 10. The values of Acc and NMI obtained by KST-DPC are all 1.00. This shows that KST-DPC obtained perfect clustering results on the D31 dataset. DPC and SC obtained similar results to those of KST-DPC on this dataset, but DBSCAN was not able to find all clusters.


### 4.3. Experimental Results on the Real-World Datasets

This subsection reports the performances of the clustering algorithms on the four real-world datasets. The varying sizes and dimensions of these datasets are useful in testing the performance of the algorithms under different conditions.The number of clusters, Acc and NMI are also used to measure the performances of the clustering algorithms on these real-world datasets. The experimental results are reported in Table4 and the best results of the each dataset are shown in italic. The symbol “--” indicates there is no value for that entry.The Vertebral dataset consists of 2 clusters and 310 data points. As Table4 shows, the value of Acc got by KST-DPC is equal to that got by DPC-KNN, but the value of NMI got by KST-DPC is lower than that got by DPC-KNN. No values of Acc and NMI were obtained by SC. As Table 4 shows, all algorithms could find the right number of clusters.The Seeds dataset consists of 210 data points and 3 clusters. Results in Table4 show that KST-DPC obtained the best, whereas DBSCAN obtained the worst, values of Acc and NMI. It is obvious that all four clustering algorithms could get the right number of clusters.The Breast Cancer dataset consists of 699 data points and 2 clusters. The results on this dataset in Table4 show that all four clustering algorithms could find the right number of clusters. KST-DPC obtained the Acc and NMI values of 0.8624 and 0.4106, respectively, which are higher than those obtained by other clustering algorithms. The results also show that DBSCAN has the worst performance on this dataset, except that SC did not get experimental results on these benchmarks.The Banknotes dataset consists of 1372 data points and 2 clusters. From Table4, it is obvious that KST-DPC got the best values of Acc and NMI among all four clustering algorithms. The values of Acc and NMI obtained by KST-DPC are 0.8434 and 0.7260, respectively. Larger values of these benchmarks indicate that the experimental results obtained by KST-DPC are closer to the true results than those obtained by the other clustering algorithms.All these experimental results show that KST-DPC outperform the other clustering algorithms. It obtained larger values of Acc and NMI than the other clustering algorithms.


## 4.1. Data Sources

Experiments on six synthetic datasets and four real-world datasets are carried out to test the performance of KST-DPC. The synthetic datasets are fromhttp://cs.uef.fi/sipu/datasets/. These datasets are commonly used as benchmarks to test the performance of clustering algorithms. The real-world datasets used in the experiments are from the UCI Machine Learning Repository [31]. These datasets are chosen to test the ability of KST-DPC in identifying clusters having arbitrary shapes without being affected by noise, size, or dimensions of the datasets. The numbers of features (dimensions), data points (instances), and clusters vary in each of the datasets. The details of the synthetic and real-world datasets are listed in Tables 1 and 2, respectively.Table 1
Synthetic datasets.
Dataset Instances Dimensions Clusters Spiral 312 2 3 Compound 7266 2 6 Jain 373 2 2 Aggregation 788 2 7 R15 600 2 15 D31 3100 2 31Table 2
Real-world datasets.
Dataset Instances Dimensions Clusters Vertebral 310 7 2 Seeds 210 7 3 Breast cancer 699 10 2 Banknotes 1372 5 2The performance of KST-DPC was compared with those of the well-known clustering algorithms SC ‎[32], DBSCAN ‎[33], and DPC-KNN ‎[28, 34]. The codes for SC and DBSCAN are provided by their authors. The code of DPC is optimized by using the matrix operation instead of iteration cycle based on the original code provided by Rodriguez and Laio [3] to reduce running time.The performances of the above clustering algorithms are measured in clustering quality or Accuracy (Acc) and Normalized Mutual Information (NMI). They are very popular measures for testing the performance of clustering algorithms. The larger the values are, the better the results are. The upper bound of these measures is 1.


## 4.2. Experimental Results on the Synthetic Datasets

In this subsection, the performances of KST-DPC, DPC-KNN, DBSCAN, and SC are reported on the six synthetic datasets. The clustering results by the four clustering algorithms for the six synthetic datasets are color coded and displayed in two-dimensional spaces as shown in Figures5–10. The results of the four clustering algorithms on a dataset are shown as four parts in a single figure. The cluster centers of the KST-DPC and DPC-KNN algorithms are marked in the figures with different colors. For DBSCAN, it is not meaningful to mark the cluster centers because they are chosen randomly. Each clustering algorithm ran multiple times on each dataset and the best result of each clustering algorithm is displayed.Figure 5
Clustering results of the Spiral dataset by the four clustering algorithms.
(a)
KST-DPC (b)
DPC-KNN (c)
DBSCAN (d)
SCFigure 6
Clustering results of the Compound dataset by the four clustering algorithms.
(a)
KST-DPC (b)
DPC-KNN (c)
DBSCAN (d)
SCFigure 7
Clustering results of the Jain dataset by the four clustering algorithms.
(a)
KST-DPC (b)
DPC-KNN (c)
DBSCAN (d)
SCFigure 8
Clustering results of the Aggregation dataset by the four clustering algorithms.
(a)
KST-DPC (b)
DPC-KNN (c)
DBSCAN (d)
SCFigure 9
Clustering results of the R15 dataset by the four clustering algorithms.
(a)
KST-DPC (b)
DPC-KNN (c)
DBSCAN (d)
SCFigure 10
Clustering results of the D31 dataset by the four clustering algorithms.
(a)
KST-DPC (b)
DPC-KNN (c)
DBSCAN (d)
SCThe performance measures of the four clustering algorithms on the six synthetic datasets are reported in Table3. In Table 3, the column “Par” for each algorithm is the number of parameters the users need to set. KST-DPC and DPC-KNN have only one parameterK, which is the number of nearest neighbors to be prespecified. In this paper, the value of K is determined by the percentage of the data points. It references the method in [34]. For each dataset, we adjust the percentage of data points in the KNN for the multiple times and find the optimal percentage that can make the final clustering reach the best. Because we perform more experiments, we only list the best result in Tables 3 and 4. And in order to be consistent wi other parameters in the table, we directly convert the percentage of data points into specific K values. DBSCAN has two input parameters, the maximum radiusEps and the minimum pointMinPts. The SC algorithm needs the true number of clusters. C1 in Table 3 refers to the number of cluster centers found by the algorithms. The performance measures including Acc and NMI are presented in Table 3 for the four clustering algorithms on the six synthetic datasets.Table 3
Results on the synthetic datasets.
Algorithm Par C1 Acc NMI Algorithm Par C1 Acc NMI Spiral     Compound KST-DPC 16 3 1.00 1.00 KST-DPC 217 6 0.98 0.95 DPC-KNN 20 3 1.00 1.00 DPC-KNN 360 6 0.6466 0.7663 DBSCAN 1.2/3 3 1.00 1.00 DBSCAN 1.5/3 5 0.8596 0.9429 SC 3 3 1.00 1.00 SC 6 6 0.6015 0.7622 Jain     Aggregation KST-DPC 4 2 1.00 1.00 KST-DPC 40 7 1.00 1.00 DPC-KNN 8 2 0.9035 0.5972 DPC-KNN 40 7 0.9987 0.9957 DBSCAN 2.62/4 2 1.00 1.00 DBSCAN 1.59/3 5 0.8274 0.8894 SC 2 2 1.00 1.00 SC 7 7 0.9937 0.9824 R15     D31 KST-DPC 20 15 1.00 0.99 KST-DPC 25 31 1.0000 1.0000 DPC-KNN 20 15 1.00 0.99 DPC-KNN 25 31 0.9700 0.9500 DBSCAN 0.4/5 13 0.78 0.9155 DBSCAN 0.46/3 27 0.6516 0.8444 SC 15 15 0.9967 0.9942 SC 31 31 0.9765 0.9670Table 4
Results on the real-world datasets.
Algorithm Par C1 Acc NMI Algorithm Par C1 Acc NMI Vertebral     Seeds KST-DPC 9 2 0.6806 0.0313 KST-DPC 4 3 0.8429 0.6574 DPC-KNN 9 2 0.6806 0.0821 DPC-KNN 6 3 0.8143 0.6252 DBSCAN 7/48 2 0.6742 -- DBSCAN 0.92/7 3 0.5857 0.4835 SC 2 2 -- -- SC 3 3 0.6071 0.5987 Breast cancer     Banknotes KST-DPC 70 2 0.8624 0.4106 KST-DPC 68 2 0.8434 0.7236 DPC-KNN 76 2 0.7954 0.3154 DPC-KNN 82 2 0.7340 0.3311 DBSCAN 6/20 2 0.6552 0.0872 DBSCAN 6.5/5 2 0.5554 6.7210e-16 SC 2 2 -- -- SC 2 2 0.6152 0.0598The Spiral dataset has 3 clusters with 312 data points embracing each other. Table3 and Figure 5 show that KST-DPC, DPC-KNN, DBSCAN, and SC can all find the correct number of clusters and get the correct clustering results. All the benchmark values are 1.00 reflecting the four algorithms all performing perfectly well on the Spiral dataset.The Compound dataset has 6 clusters with 399 data points. From Table3 and Figure 6, it is obvious that KST-DPC can find the ideal clustering result; DBSCAN cannot find the right clusters whereas DPC-KNN and SC cannot find the clustering centers. Because DPC has a special assignment strategy [3], it may assign data points erroneously to clusters once a data point with a higher density is assigned to an incorrect cluster. For this reason, some data points belonging to cluster 1 are incorrectly assigned to cluster 2 or 3 as shown in Figures 6(b)–6(d). DBSCAN has some prespecified parameters that can have heavy effects on the clustering results. As shown in Figure 6(c), two clusters are merged into one cluster in two occasions. KST-DPC obtained Acc and NMI values higher than those obtained by the other algorithms.The Jain dataset has two clusters with 373 data points in a 2 dimensional space. The clustering results show that KST-DPC, DBSCAN, and SC can get correct results and both of the benchmark values are 1.00. The experimental results of the 4 algorithms are shown in Table3 and the clustering results are displayed in Figure 7. DPC-KNN devides some points that should belong to the bottom cluster into the upper cluster. Although all the four clustering algorithms can find the correct number of clusters, KST-DPC, DBSCAN, and SC are more effective because they can put all the data points into the correct clusters.The Aggregation dataset has 7 clusters with different sizes and shapes and two pairs of clusters connected to each other. Figure8 shows that both the KST-DPC and DPC-KNN algorithms can effectively find the cluster centers and correct clusters, except that an individual data point is put into an incorrect cluster by DPC-KNN. Table 3 shows that the benchmark values of KST-DPC are all 1.00 and those of DPC-KNN are close to 1.00. SC also can recognize all clusters, but the values of Acc and NMI are lower than those of DPC-KNN. DBSCAN did not find all clusters and could not partition the clusters connected to each other.The R15 dataset has 15 clusters containing 600 data points. The clusters are slightly overlapping and are distributed randomly in a 2-dimensional space. One cluster lays in the center of the 2-dimensional space and is closely surrounded by seven other clusters. The experimental results of the 4 algorithms are shown in Table3 and the clustering results are displayed in Figure 9. KST-DPC and DPC-KNN can both find the correct cluster centers and assign almost all data points to their corresponding clusters. SC also obtained good experimental result, but DBSCAN did not find all clusters.The D31 dataset has 31 clusters and contains 3100 data points. These clusters are slightly overlapping and distribute randomly in a 2-dimensional space. The experimental results of the 4 algorithms are shown in Table3 and the clustering results are displayed in Figure 10. The values of Acc and NMI obtained by KST-DPC are all 1.00. This shows that KST-DPC obtained perfect clustering results on the D31 dataset. DPC and SC obtained similar results to those of KST-DPC on this dataset, but DBSCAN was not able to find all clusters.


## 4.3. Experimental Results on the Real-World Datasets

This subsection reports the performances of the clustering algorithms on the four real-world datasets. The varying sizes and dimensions of these datasets are useful in testing the performance of the algorithms under different conditions.The number of clusters, Acc and NMI are also used to measure the performances of the clustering algorithms on these real-world datasets. The experimental results are reported in Table4 and the best results of the each dataset are shown in italic. The symbol “--” indicates there is no value for that entry.The Vertebral dataset consists of 2 clusters and 310 data points. As Table4 shows, the value of Acc got by KST-DPC is equal to that got by DPC-KNN, but the value of NMI got by KST-DPC is lower than that got by DPC-KNN. No values of Acc and NMI were obtained by SC. As Table 4 shows, all algorithms could find the right number of clusters.The Seeds dataset consists of 210 data points and 3 clusters. Results in Table4 show that KST-DPC obtained the best, whereas DBSCAN obtained the worst, values of Acc and NMI. It is obvious that all four clustering algorithms could get the right number of clusters.The Breast Cancer dataset consists of 699 data points and 2 clusters. The results on this dataset in Table4 show that all four clustering algorithms could find the right number of clusters. KST-DPC obtained the Acc and NMI values of 0.8624 and 0.4106, respectively, which are higher than those obtained by other clustering algorithms. The results also show that DBSCAN has the worst performance on this dataset, except that SC did not get experimental results on these benchmarks.The Banknotes dataset consists of 1372 data points and 2 clusters. From Table4, it is obvious that KST-DPC got the best values of Acc and NMI among all four clustering algorithms. The values of Acc and NMI obtained by KST-DPC are 0.8434 and 0.7260, respectively. Larger values of these benchmarks indicate that the experimental results obtained by KST-DPC are closer to the true results than those obtained by the other clustering algorithms.All these experimental results show that KST-DPC outperform the other clustering algorithms. It obtained larger values of Acc and NMI than the other clustering algorithms.


## 5. Conclusion

This study proposed a density peak clustering algorithm based on the K-nearest neighbors, Shannon entropy and tissue-like P systems. It uses the K-nearest neighbors and Shannon entropy to calculate the density metric. This algorithm overcomes the shortcoming that DPC has that is to set the value of the cutoff distancedc in advance. The tissue-like P system is used to realize the clustering process. The analysis demonstrates that the overall time taken by KST-DPC is shorter than those taken by DPC-KNN and the traditional DPC. Synthetic and real-world datasets are used to verify the performance of the KST-DPC algorithm. Experimental results show that the new algorithm can get ideal clustering results on most of the datasets and outperforms the three other clustering algorithms referenced in this study.However, the parameterK in the K-nearest neighbors is prespecified. Currently there is no technique available to set this value. Choosing a suitable value for K is a future research direction. Moreover, some other methods can be used to calculate the densities of the data points. In order to improve the effectiveness of DPC, some optimization techniques can also be employed.



---

*Source: 1713801-2019-07-31.xml*