# Boundary Matching and Interior Connectivity-Based Cluster Validity Analysis
## 2 Related Work
### Typical Clustering Algorithms
#### 2.1.3 DPC Algorithm  
DPC algorithm is the latest clustering algorithm, which combines the advantages of C-means and DBSCAN algorithms. For each point \(x_{i}\), DPC calculates its density \(\rho_{i}\) and its separated distance \(\delta_{i}\) as follows. \[\rho_{i}=\sum\
olimits_{j}\chi(d(x_{i},x_{j})-d_{c}),\ s.t.\chi(x)=1,\ if\ \chi(\bullet)<0;\ else\ 0, \tag{3}\]  
where \(d_{c}\) is a cutoff radius and \(d(x_{i}x_{j})=\|x_{i}-x_{j}\|\). \(\delta_{i}\) can be measured by finding the minimum distance between the data point \(x_{i}\) and other higher density points, i.e.,  
\[\delta_{i}=\min\
olimits_{j\rho_{j}>\rho_{i}}d(x_{i},x_{j}). \tag{4}\]  
The cluster centers are these points that have relatively higher \(\delta_{i}\) and \(\rho_{i}\). After the calculation of \(\gamma_{i}=\rho_{i}\delta_{i}\), \(i=1,2,\ldots,n\), the points with higher \(\gamma_{i}\) are regarded as cluster centers. After determining the number of cluster centers, the clustering process can be used after scanning all points only once. DPC, DBSCAN, and C-means have their own applicable ranges, respectively. Figure 2 shows three datasets with different characteristics: two nonspherical clusters in (a), three density-different clusters in (b), and three partially-overlapped clusters in (c), respectively. The clustering results by the above three algorithms are presented in these figures as well. Different numbers denote the real labels of the datasets, and different colors denote the clustering results by the corresponding clustering algorithms. Figure 2a represents that DPC cannot work well when the investigated dataset contains a cluster with multiple density peaks. When one cluster has multiple peaks, DPC may regard these peaks as cluster centers, resulting in wrong clustering partition. Figure 2b shows the clustering results using the DBSCAN algorithm. In this case, there is none value of \(\varepsilon\) to make DBSCAN find a correct clustering result. Figure 2c shows that the two clusters in the left are partially overlapped and have a similar density. C-means cannot find boundary points correctly, which leads to wrong clustering results. When dealing with datasets in high dimensional (HD) spaces, these three clustering algorithms show different characteristics. Different from C-means and DPC, DBSCAN cannot effectively cluster points in HD datasets. First, the computed densities in DBSCAN have little difference among various high-dimensional (HD) points and cause that core points are difficultly determined. Accordingly, the merging condition to the same cluster from one to another core points has high uncertainty. Second, to accelerate DBSCAN, an R* tree structure indexing all points have to be used to decrease computational complexity, but it is challenging to be built in an HD space. Inversely, C-means depends on distance computation rather than density computation, and the distance differences among points can be much larger than their density differences. Also, DPC uses not only density \(\rho\) but also separation  
Figure 2: Three datasets with different characteristics and the clustering results by using density peak-point-based clustering (DPC), Density-Based Spatial Clustering of Applications with Noise (DBSCAN) and C-means: (**a**) two nonspherical clusters; (**b**) three density-different clusters; (**c**) three partially-overlapped clusters. measure \(\delta\) to find all abnormal points as cluster centers, and can significantly avoid the HD problem in DBSCAN. Consequently, the HD problem plays little effect on C-means and DPC. C-means algorithm needs users to provide cluster number as the input parameter, which has an essential effect on clustering results. DPC has the same problem as C-means, which needs to provide the number of clusters in advance. The clustering process of DBSCAN has relevance with point density. Different values of neighborhood radius will result in different numbers of clusters, which can affect the clustering results.