A novel density peaks clustering algorithm for automatic selection of clustering centers based on K-nearest neighbors

1.   Introduction

Clustering is a powerful technique for data analysis, with an irreplaceable role in data mining. It essentially exploits the similarities between samples to divide them into several different clusters. Its application is found in numerous popular areas, including image processing ^[1,2], medicine ^[3,4], text segmentation ^[5], community network analysis ^[6], bioinformatics ^[7,8], etc. So far, researchers have developed multiple algorithms with satisfactory performance, including the division-based method K-means ^[9], the layer structure-based method BIRCH ^[10], the density-based method DBSCAN ^[11], the grid-based method WaveCluster ^[12] and the graph theory-based spectral clustering ^[13]. Among them, DBSCAN is a well-performing density-based clustering algorithm that determines clusters based on density connectivity relationships. It has the advantage of being able to cluster arbitrarily shaped datasets and presents a high resistance to noise. However, the presence of the two parameters ϵ and MinPts in the algorithm significantly impacts the final clustering results, and it shows poor performance on datasets with varying densities.

In 2014, Alex Rodriguez et al. ^[14] published the DPC (density peak clustering algorithm). Due to its high efficiency, robustness and simplicity of understanding, an increasing number of researchers are emphasizing the aforementioned algorithm. DPC uses two criteria when selecting cluster centers. First, the centers of the different clusters are far from each other, and secondly, the clustering center will be enclosed by some low densities of points. Considering the rest of the points, the DPC employs a one-step strategy to assign each point in a cluster to the nearest high-density cluster. While it presents multiple obvious advantages over other classical algorithms, the DPC suffers from a few problems: 1) It requires manual involvement when selecting cluster centers, and this is extremely difficult in datasets where the boundaries between clusters are not clear. 2) The DPC tends to fail to find peaks in sparse areas; consequently, it does not achieve satisfactory clustering results when large differences in data density between different clusters are present. 3) The assignment of non-peak points by the DPC tends to ignore the real situation in the area where the sample is located. Hence, when a misclassification of one point occurs during the assignment process, a domino effect is triggered. In light of the aforementioned problems, scholars have suggested various improved clustering algorithms on the basis of DPC to address its drawbacks.

In this context, ADPC-KNN ^[15] used K-nearest neighbors to determine the cut-off distance, with a novel method proposed for automatically selecting cluster centers, but it still underperformed on datasets with varying densities. The NDPC ^[16] reduced the density gap between samples from sparse areas and those from dense areas through a new method that calculated local densities so that peaks could also be found in sparse regions. Unfortunately, the NDPC was unable to discover all peaks in datasets with large density differences. The AmDPC ^[17] employed density deviation to replace the original local density, and the authors proposed a density deviation multi-peak auto-clustering approach that overcame the poor performance of the original DPC on non-convex datasets with low-density peaks. Nevertheless, its parameter selection process was complex. The FKNN-DPC ^[18] solved the sample assignment error problem in the DPC assignment strategy using the fuzzy weighted K-nearest neighbor technique. Although it was more robust than the DPC, the FKNN-DPC still required manual intervention for the selection of clustering centers. Meanwhile, the SNN-DPC ^[19] adopted a two-step distribution method of necessary and possible subordination to overcome the consequences of the domino effect caused by the shortcomings of the DPC allocation rules. However, it required human involvement and was more complex compared to the DPC. 3W-DPET ^[20] suggested a three-way density peak clustering approach on the basis of evidence theory, which solved the problem of mislabel propagation in the DPC. However, the 3W-DPET could not automatically determine the number of clusters. On the other hand, the DPC-KNN ^[21] joined the notion of K-nearest neighbors for distance calculation and sample assignment to improve the clustering effect in non-spherical datasets. However, the algorithm still required a manual selection of clustering centers. Through the analysis of multiple algorithms that have improved the DPC in recent years, it is clear that the above algorithms generally still do not address the problem that the DPC performs poorly on datasets with varying density differences or non-convexity; and despite the aforementioned improvement of individual algorithms to tackle this issue, manual involvement is still required when selecting clustering centers.

The primary contribution of this study is the proposal of a novel density-peak clustering algorithm (AKDPC) that automatically selects clustering centers and adaptively completes the corresponding clusters. The suggested method divides the samples into core and non-core points by mutual K-nearest neighbor values, where non-core points are placed in the second assignment, reducing the impact on the final clustering. Simultaneously, only the average distance between the K-nearest neighbors of a sample is used as an indicator to select the cluster center. Specifically, the one with the lowest average distance among the K-nearest neighbors in remaining core points will be selected as a cluster center. Afterwards, the AKDPC adds core points that satisfy the merging condition to the corresponding clusters. Finally, the non-core points are clustered. The clustering of the AKDPC is fully automatic and is better suited to complex datasets with large density differences or non-convexity.

2.   DPC

The DPC is an extremely efficient density clustering algorithm. It considers that the locations surrounded by some low local density data samples should be the cluster centers; furthermore, the clustering centers of different clusters should not be too close to each other. The DPC constructs decision diagrams to select centers from the sample local densities ρ and relative distances ${\rm{ \mathsf{ δ}}}$.

The original DPC uses both cut-off distance and kernel distance to compute the densities of the samples, and these two methods might apply to different datasets. The local density of sample i is defined as Eq (1).

Alternatively, obtained by Gaussian kernels defined as Eq (2),

where ${d}_{ij}$ is the distance between two different samples, and ${d}_{c}$ is the cut-off distance.

${\rm{ \mathsf{ δ}}}$ denotes the distance from a sample to the nearest sample with a density bigger than it, and the formula is defined as follows:

The relative distance for the sample with the highest density is specified to be the highest value among all samples, and it is defined as Eq (4).

After getting the ρ and $\delta$ values for all samples, the DPC considers the points with simultaneously larger ρ and $\delta$ to be the clustering centers. Finally, the DPC makes the labels for the leftover points consistent with the labels of the closest high-density points.

3.   AKDPC

To overcome the issue that the DPC requires manual intervention to choose clustering centers and poor performance on complex datasets with varying densities or non-convexity, we propose AKDPC. The AKDPC consists of three main parts: 1) classifying samples into core and non-core points based on the sizes of their mutual K-nearest neighbor values; 2) Clustering the core points; 3) Allocation of remaining non-core points.

3.1.   Classification of core and non-core points

The classification method determines whether to classify each sample point as core or non-core by its mutual K-nearest neighbor value.

The mutual K-nearest neighbor value ${MK}_{i}$ of sample ${x}_{i}$ is the sum of points in the sample ${x}_{i}$'s K-nearest neighbor collection that incorporates sample ${x}_{i}$ into its K-nearest neighbor collection, and ${MK}_{i}$ is defined as Eq (5).

where ${KNN}_{i}$ is a collection of K nearest neighbors of sample i, defined as Eq (6), and where K is the first parameter to be specified in our algorithm.

The MK values of samples have the following characteristics:

1) The MK value of a point represents its spatial relationship with its neighbors. If the value is large, the sample point is closely distributed with its neighbors or is in the same distribution area, so it is treated as a core point. If the value is smaller, the sample point is isolated from the surrounding points and treated as a non-core point.

2) The MK value of a sample point is not affected by the fact that the sample is located in a different density area because the MK value reflects the proximity of the sample to its neighbors.

We classify all points into core and non-core points by defining a classification threshold MKT, which is defined by Eq (7).

where N is the sum of samples.

Definition 1 (Core point). If the mutual K-nearest neighbor value ${MK}_{i}$ of sample i is larger than or equal to MKT, then it is a core point.

Definition 2 (Non-core point). If the mutual K-nearest neighbor value ${MK}_{i}$ of sample i is less than the MKT, then it is a non-core point.

With our proposed method above some non-core points can be accurately identified to prevent the possibility of a large impact on the final clustering, and Algorithm 1 explains in detail the classification of the sample points.

3.2.   Clustering of core points

To prevent the old DPC algorithm from requiring manual intervention to select centers of all clusters and the problem of easily ignoring clustering centers that exist in low-density areas, we redefine the local density of a sample based on the distance relationship from sample points to their nearest neighbors and suggest a new approach for merging core points. Our method does not need human involvement in the selection of clustering centers, and the whole clustering process is fully automatic. Figure 1 displays the clustering results of the original DPC algorithm and our algorithm for clustering on the classical dataset Jain ^[22]. As shown in the figure, the original DPC selected clustering centers located in the lower branches with higher density, no matter how the distance is chosen up to the end. The correct classification is not completed in the end, while our method accurately identifies the clustering centers in two different density regions.

First, we define the ${D}_{i}^{k}$ of core sample point i as the average distance from core sample i to its K-nearest neighbor set of points, and ${D}^{k}$ is defined as Eq (8).

where ${N}_{i}^{k}$ denotes the collection of k nearest neighbors of the core point i, defined as Eq (9), and where k is the second parameter to be specified in our algorithm.

The nearest neighbor mean ${D}^{k}$ of a sample point has the following properties:

1) If the ${D}^{k}$ of the core point is particularly small, it is a good indication that the core point is in a very dense area, and its surrounding neighbors are all very close to it. Conversely, if the ${D}^{k}$ value is very large, it means that the core is far away from its neighbors.

2) There is no doubt that the smaller the ${D}^{k}$ value of a core point is, the greater the indicated density and the more qualified it is to be a cluster center. However, some clusters have a low overall density, which results in their overall ${D}^{k}$ values being larger. It would be unwise for us to select cluster centers directly based on their ${D}^{k}$ values. Therefore, we adopted a sequential clustering process. We first selected the point with the smallest ${D}^{k}$ value among all core points as the center of a new cluster, and then after completing the clustering of the new cluster, we selected the core point with the smallest ${D}^{k}$ value from the remaining core points for the center of another new cluster and then completed the clustering of the corresponding cluster. The above procedure was repeated until each core point has been allocated to different clusters. By using this method, we can correctly select the cluster centers even in data sets with uneven density distributions.

To better understand the process of clustering, we propose a definition of connectivity.

Definition 3 (Connectivity). A core point i is joinable to cluster C_j by connectivity if the distance from the core point i to the cluster C_j is smaller than the maximum value of ${D}^{k}$ for core point i and any core point in cluster C_j. The connectivity of core point i to cluster C_j satisfies Eq (10).

where $\Vert {X}_{i}-{C}_{j}\Vert$ denotes the minimum distance between core point i and any core point in cluster Cj, and $max\left({D}_{i}^{k}, {D}_{t}^{k}\right)$ denotes the maximum ${D}^{k}$ value in core point $i$ and cluster C_j.

As in Figure 2, the nearest distance between core point 5 and cluster 1 is ${d}_{45}$ = 0.32. Also, according to Table 1, the largest nearest neighbor mean ${D}^{k}$ in core point 5 and the core points in cluster 1 is ${D}_{5}^{k}$ = 0.38. Under this condition, ${d}_{45}$ is less than ${D}_{5}^{k}$ satisfies connectivity, therefore core point 5 is added to cluster 1. The closest distance between core point 6 and cluster 1 is ${d}_{56}$ = 0.33, and the maximum ${D}^{k}$ value in core point 6 and the core points in cluster 1 is ${D}_{6}^{k}$ = 0.41. ${\mathrm{d}}_{56}$ is less than ${D}_{6}^{k}$, satisfying the Connectivity, and thus core point 6 can join cluster 1. For the core point 7, the closest distance between it and cluster 1 is ${d}_{67}$ = 0.38, and the maximum ${D}^{k}$ value in core point 7 and the core points in cluster 1 is ${D}_{7}^{k}$ = 0.43. ${\mathrm{d}}_{67}$ is less than ${D}_{7}^{k}$, and thus core point 7 can join cluster 1. In contrast, the closest distance between core point 9 and cluster 1 is ${d}_{69}$ = 0.73, and the maximum ${D}^{k}$ value in core point 9 and the core points in the cluster is ${D}_{9}^{k}$ = 0.67, because ${d}_{69}$ is greater than ${D}_{9}^{k}$. The Connectivity cannot be satisfied, so core point 9 cannot be joined to cluster 1. Likewise, core point 8 cannot be joined to cluster 1.

Algorithm 2 shows the whole procedure of clustering the core points, where ${SD}^{n\times n}$ is the distance matrix after sorting in ascending order, and $\Vert g-{C}_{i}\Vert$ is the smallest distance from the core point g to cluster ${C}_{i}$. First, we create a new cluster and select the cluster center with the smallest ${D}^{k}$ value among all core points. Second, depending on the distance of the remaining core points from the center of that cluster, we traverse from near to far and add the core points that satisfy the connectivity condition to that cluster (note that the merging of cores with clusters is an adaptive process, as each traversal adds cores to the cluster that satisfy the condition, so the maximum ${D}^{k}$ value of the core points in the cluster will change, i.e., in the process of clustering Eq (6), the value on the right-hand side changes continuously), until no more cores can be added to the cluster. We repeat the above procedure until all core points have been grouped into clusters.

3.3.   Allocation of remaining non-core points

Once we had finished clustering the core points, to determine the labels of the non-core samples, we first sorted the non-core samples in ascending order based on their ${D}^{k}$ value. Empirically, we found that most of the neighboring samples were in the same cluster, so we label the unclassified non-core points with the same labels as the nearest points that have been classified. The above method is explained in detail in Algorithm 3.

3.4.   Example

To understand our algorithm more intuitively, we show the whole process of our algorithm using the manual dataset Aggregation ^[23] as an example. Aggregation has a total of 788 samples, and there were 7 correctly classified clusters. The results of each step in the clustering procedure are clearly shown in Figure 3 (algorithm parameters K = 11, k = 11).

3.5.   Time complexity analysis of AKDPC

Assume that there are n samples in the dataset, and then the n samples are divided into a core and b non-core points. The complexity of our method depends mainly on the following six aspects.

1) The complexity of computing MK values for each sample is O(kn);

2) The complexity of classifying samples based on MKT values is O(n);

3) The complexity of the calculation of the ${D}^{k}$ value for each sample is O(n);

4) The complexity of defining clustering centers and clustering the core points is O(${\mathrm{a}}^{2}$);

5) The complexity of distributing non-core points is O(ab);

6) The AKDPC has an overall time complexity of O(${\mathrm{n}}^{2}$) based on the analysis above, which is the same as the original DPC.

4.   Experiments

To prove the feasibility and validity of our suggested AKDPC algorithm, we used DPC and its improved algorithm DPC-KNN and DBSCAN for comparison. Since DBSCAN is a classical density-based clustering algorithm, and DPC-KNN is similar to this paper in that it is based on KNN to improve the original DPC, using them as a comparison can demonstrate the superiority of the AKDPC algorithm. Experiments were performed on eight classical manual datasets and eight real datasets obtained from ^[24,25]. To verify the performance of the algorithms for different density distributions and shapes, we used seven datasets that can represent different situations such as Aggregation, Jain, Flame ^[26], ThreeCircles, Pathbased ^[27], D9 ^[28], T4, etc., while the number of clusters and features of the samples are also different for each of the eight real datasets, for which experiments can be conducted to verify the generalizability of AKDPC. The detailed attribute tables for the data are given in Table 2. The source code and datasets used in this section are available at https://github.com/wanghuani/AKDPC.

We uniformly used adjusted rand index (ARI ^[29]), normalized mutual information (NMI ^[30]), and clustering accuracy (ACC) as performance evaluation metrics throughout the experiments, with an upper limit of 1 for the metrics and higher values indicating better performance. Among them, ACC is one of the most commonly used clustering performance evaluation metrics, defined as Eq (11).

where y_i is the true label, z_i is the label after clustering, and map(.) represents the reassignment of clustering labels, which is generally implemented using the Hungarian algorithm.

ARI is an adjusted RI. ARI measures the degree of agreement between two data distributions, and Eqs (12) and (13) show the calculation process of RI and ARI:

where Y represents the actual label, Z represents the clustering result, ${C}_{2}^{n}$ represents the total number of element pairs that can be composed in the data set, a represents the number of elements in both Y and Z that are of the same category, and b represents the number of elements that are not of the same category, while E represents the expectation.

NMI is also a commonly used measure of the similarity between the clustering results and the true results, as defined by Eq (14).

where Y represents the true category, Z represents the result after clustering, H represents the cross entropy, and I(Y, Z) represents the mutual information.

To ensure the fairness of the experiment, all datasets used before starting the experiment were mapped linearly to the range [0, 1] by pre-processing.

In this paper, all parameters of the four algorithms are tuned to make sure that the overall experiment demonstrates the best possible clustering for each algorithm. AKDPC requires two parameters, K and k, taking values between 1 and 100. In addition, according to experience, for some simple low-dimensional datasets, the parameters K and k are generally chosen around 10–20, and the same values can be taken in most cases. Meanwhile, for data sets with more samples, the performance of AKDPC is generally better by choosing larger values of K and k. At the same time, we both need to choose a cut-off distance dc for the DPC and DPC-KNN, and empirically we choose a dc that is 1–2% after we sort the data points in ascending order by distance from each other. Furthermore, DPC-KNN requires manual determination of the number of the nearest neighbor K, which we choose from 4 to 15. As for the two parameters of DBSCAN, we choose ε between 0.01 and 2, and minpts between 1 and 50. Finally, for both DPC-KNN and DPC algorithms, we manually set the number of clusters.

4.1.   Experiments with artificial datasets

In this part, we have selected the classical manual datasets which were used to test various clustering algorithms. The final clustering outcomes of the manual dataset are given in Table 3. Just as Table 3 shows, AKDPC shows near-perfect results for all types of datasets, while other algorithms are not as generalizable as AKDPC. For example, DPC is unable to handle large density differences and some complex non-convex datasets, while DPC-KNN generally does better than DPC on these datasets overall but also has the problem of being unable to handle some complex non-convex datasets. DBSCAN shows good results in processing each dataset though, but it tends to misidentify some samples as noise points. The overall effect is not as good as AKDPC.

We have visualized the final clustering results in Figures 4–10, and we have used asterisks to indicate the cluster centers obtained by other algorithms, except for the DBSCAN algorithm. In Figure 4, DPC, DPC-KNN and AKDPC can identify the structure of aggregated datasets consisting of arbitrarily distributed non-spherical clusters, and for DBSCAN the general shape of each cluster is correct although some points are labeled as noise.

The result of the clustering of the classic dataset Jain is shown in Figure 5. Since DPC always prefers to select clustering centers in high-density areas, it cannot detect clustering centers in sparse areas above the dataset Jain, which leads to wrong results in the end. At the same time, DBSCAN incorrectly classifies the left side of the top sparse region as a new cluster, while identifying some points on the right end as noise. In contrast, both AKDPC and DPC-KNN identified density peaks distributed over different density regions.

The results of the Flame dataset are presented in Figure 6, where DPC, DPC-KNN and AKDPC all effectively aggregate the two clusters, while DBSCAN correctly detects both clusters, but it incorrectly identifies some edge points as noise, which affects the outcome of the clustering.

The clustering results of the clustering of the ThreeCircles dataset are presented in Figure 7. As the graph shows, DPC and DPC-KNN select three clustering centers in the middle two rings, making the final outer ring without a center, resulting in the final incorrect clustering result, but DBSCAN correctly identifies three clusters, while our algorithm AKDPC not only identifies the clustering centers of the three rings. The final clustering result is also completely correct.

Figure 8 displays the clustering results for the Pathbased dataset. For this typical non-convex dataset, DPC and DPC-KNN are not performing well. DPC and DPC-KNN correctly identify the three clustering centers, but they wrongly assign the left and right sides of the dataset to the two clusters in the middle, while DBSCAN correctly identifies only two clusters, leaving the remaining samples in the outer sparse region as noise. On this dataset, only AKDPC not only succeeded in identifying three clustering centers, but the final clustering result was also relatively perfect.

As shown in Figure 9, dataset D6 has many discrete points, which often have a significant impact on algorithm performance. Not surprisingly, DPC and DPC-KNN were not up to the task of processing such a large curvature dataset, and only DBSCAN and AKDPC succeeded in identifying the four clusters, with DBSCAN having the slight flaw of identifying almost all of the discrete points as noise.

The results of the T4 dataset for all algorithms are shown in Figure 10, which contains six clusters, most of which are cross-tangled, and many discrete points at the edges of each cluster, testing the ability of the algorithms to handle complex datasets. While DBSCAN and AKDPC showed their performance in adapting to various complex situations and successfully identified six clusters of different shapes, DPC and DPC-KNN showed less satisfactory results on this complex dataset with large cross-tangles.

4.2.   Experiments with real datasets

We further demonstrate the excellent capability of the AKDPC clustering algorithm using eight real datasets. Table 4 displays the clustering performance for the ACC, ARI and NMI metrics on the real datasets. Bold text within the table denotes the optimum results of the same dataset. As we can see from Table 4, no algorithm can always outperform the other algorithms due to the diversity of real datasets with different data, but we can also observe from Table 4 that in most situations, AKDPC does better, indicating that the AKDPC algorithm is more generalizable and can handle datasets with different situations.

5.   Discussion

To address the weaknesses of the original DPC, we propose a density peak clustering algorithm for the automatic selection of clustering centers based on K-nearest neighbors. We use relationships between samples and their surrounding neighbors to classify the sample into core and non-core samples while eliminating any possible adverse effects of non-core samples on the final clustering results by batch clustering. At the same time, we use the information on the distance of the sample from its surrounding neighbors to replace the density of samples in the original DPC. Through a novel sequential clustering method, we solve the problem of the former DPC requiring human intervention to determine the clustering centers and can also achieve better performance on complex datasets with large differences in density or non-convexity. Of course, our algorithm AKDPC has some drawbacks. First, we need to manually determine two parameters K and k. Second, we assign non-core points by labeling them as the same as the nearest points that have been classified and do not consider the effect of cluster shape, which may lead to incorrect assignments.

In future research we will try to reduce the number of parameters while maintaining the current accuracy, and for unassigned non-core points, we will propose a new method to reduce incorrect assignments. Finally, we will try to combine it with some supervised algorithms to test it with some excellent variants of the KNN algorithm used in this paper, such as CDNN ^[31,32] and ECDNN ^[33], and explore them with respect to their application in some related research ^[34].

Acknowledgments

The financial support for this project was provided by the National Natural Science Foundation of China [61962054].

Conflict of interest

The authors declare no conflict of interest.