# ConDPC: Data Connectivity-Based Density Peak Clustering
## 2 Original Algorithm  
DPC algorithm was proposed by [PERSON] et al. in 2014 [PERSON] et al. (2014). The algorithm is based on the assumption that the local densities of cluster centers are high, and different centers are far apart. [PERSON] et al. (2014) obtained two intermediate results for each point in the data set, which were used for the subsequent judgment of density clustering centers and neighbor assignment. Taking point \(i\) as an example, the two results are: (1) Local density \(\rho\) of point \(i\); (2) The minimum distance between point \(i\) and the points of greater local density than it (For the convenience of description, this distance is called the neighbor distance in the following text). The authors provided a local density definition based on a Gaussian kernel which is used in our study. The definition is as follows:  
\[\rho_{i}{=}\sum_{i\
eq j}\exp(-(\frac{d_{ij}}{d_{c}})^{2}) \tag{1}\]  
where \(d_{ij}\) is the Euclidean distance between points \(i\) and \(j\) and \(d_{c}\) is a given cut-off distance. The set of points with a density greater than this point can be defined as follows:  
\[N_{i}=\left\{x_{j}\in X|\rho_{i}<\rho_{j}\right\} \tag{2}\]  
For the convenience of subsequent descriptions, we call the points in \(N_{i}\) the big neighbors of point \(i\). For point \(i\), the nearest point with a local density greater than it is its neighbor. Then, the neighbor distance is defined as follows (2014):  
\[\delta_{i}=\left\{ \begin{array}{ll}\min(d_{i(N_{i})}),&N_{i}\;\text{is not}\;\;null\\ \max(\delta),&otherwise\end{array} \right. \tag{3}\]  
With the help of local density and neighbor distance, the paper leads to the definition of \(\gamma\) as follows:  
\[\gamma_{i}=\rho_{i}*\delta_{i} \tag{4}\]  
The larger the \(\gamma\) value, the more likely the corresponding point is to be the cluster center point. That is to say, the point with a larger local density and neighbor distance value is more likely to be selected as the cluster center point. Taking \(\rho\) as the \(x\)-axis and \(\delta\) as the \(y\)-axis to draw the decision graph, the points with a higher \(\gamma\) value can be intuitively found, thus providing strong support for the selection of clustering centers. It can be concluded from Formula (1) that the calculation method of local density is the same for each point, that is, the case of large density difference is not considered. This can lead to incorrect cluster center selection. As shown in Figure 1, when the density difference is large, the DPC algorithm may find multiple center points in the group with higher density, while no center points are found in the group with lower density. The two larger dots (marked in red and turquoise) in Figure 1a,b represent the clustering centers selected by the DPC algorithm. In all of the following clustering result figures, the cluster centers are labeled with star shapes. The different clusters produced by the clustering algorithms are distinguished by different colors. From Formula (3), it can be concluded that the calculation of delta is based on the Euclidean distance. This calculation does not take into account data with manifold structures. This may lead to poor accuracy in neighbor selection. Figure 2 shows the neighbor selection of point \(p\) in the external cluster on the Halfernal dataset. As shown in Figure 2a, the blue point \(p\) has several big neighbors (the points marked in black with greater densities than \(p\)). As shown in Figure 2b, the blue point \(p\) selects the nearest point \(q\) among all the big neighbors as its neighbor. This kind of neighbor selection error leads to the inaccurate assignment of points to the cluster to which they belong. The clustering result is shown in Figure 2c. To sum up, the DPC algorithm does not consider the density difference and the distance calculation problem caused by the manifold structure, which may lead to the wrong selection of clustering centers or neighbors. In this study, data connectivity is integrated into the original algorithm to solve the above problems.