INSDPC: A density peaks clustering algorithm based on interactive neighbors similarity

1.   Introduction

Cluster analysis, a pivotal branch of data mining, plays a significant role in statistical analysis and is one of the core methods in unsupervised machine learning ^[1]. Clustering operates by evaluating the similarity between points, dividing the dataset into multiple categories to maximize intra-cluster similarity and minimize inter-cluster similarity ^[2]. More importantly, cluster analysis reveals underlying patterns and trends within a dataset, thus supporting a deeper understanding of the data. This technique has been extensively utilized across multiple domains, including community detection ^[3], market research ^[4], document clustering ^[5], and gene expression analysis ^[6].

Over the past few decades, the field of clustering has undergone rapid development, with algorithms generally categorized into partition-based, hierarchical, grid-based, model-based, and density-based clustering methods. Partition-based clustering algorithms, such as K-means, aims to minimize the distance between points within a cluster and their centroid, but is highly sensitive to center initialization. To address this limitation, refined variants such as K-means++ ^[7] and K-medoids ^[8] have been proposed. Hierarchical clustering algorithms, such as clustering using representatives (CURE) ^[9] and balanced iterative reducing and clustering using hierarchies (BIRCH) ^[10], perform effectively but are constrained by high computational complexity. Grid-based clustering algorithms, such as statistical information grid (STING) ^[11], partition the feature space into grid cells, with the effectiveness of the algorithm strongly influenced by the choice of grid size. The expectation-maximization (EM) algorithm ^[12], a model-based clustering algorithm, utilizes maximum likelihood estimation to determine the probabilistic model parameters of the data.

Density-based clustering algorithms are widely applicable due to their ability to detect clusters of arbitrary shapes. Among them, density-based spatial clustering of applications with noise (DBSCAN) ^[13] is a classic algorithm known for its effectiveness in handling irregularly shaped clusters. However, its performance heavily depends on two key parameters: the neighborhood radius (Eps) and the minimum number of points within a neighborhood (MinPts). The lack of theoretical guidance for parameter selection makes clustering results highly sensitive to these settings. Consequently, determining optimal parameter values is critical for optimizing the algorithm's performance.

A novel density-based algorithm, named clustering by fast search and find of density peaks (DPC), was proposed by Rodriguez and Laio in 2014 ^[14]. Unlike traditional clustering algorithms, DPC requires only a single parameter $d_c$ and eliminates the need for iterative optimization of an objective function to complete clustering. By calculating the local density and relative distance, DPC efficiently identifies cluster centers and assigns points to clusters. This method demonstrates exceptional clustering performance when handling data of various forms and achieves high computational efficiency ^[15]. As a result, DPC has been widely applied in various domains, including image recognition, computer vision, and scheduling ^[16].

Although the DPC algorithm offers notable advantages, it also has certain limitations. The computation of local density relies heavily on the choice of the cutoff distance $d_c$ ^[17]. If $d_c$ is too large, the local densities of most points converge, potentially classifying all points into a single cluster. Conversely, an overly small $d_c$ can result in numerous clusters, incorrectly partitioning points that belong to the same cluster. However, the selection of $d_c$ depends on the global distribution of the dataset, ignoring local data characteristics. Consequently, the clustering performance of the DPC algorithm might not be optimal when applied to datasets with cross-winding structures or uneven density distributions. Additionally, its one-step assignment strategy means that if a point is misassigned, the subsequent assignment process may lead to more errors.

Figure 1 illustrates these issues. In the Flame dataset, Figure 1(a, b) both apply the Gaussian kernel function for local density estimation, though with different cutoff distances, and Figure 1(a) successfully achieves perfect clustering. When Figure 1(b, c) use the same cutoff distance but different kernel functions, the clustering results become completely inconsistent. It can be observed that the clustering results largely depend on the method used to compute local density and the choice of the cutoff distance. Moreover, in Figure 1(b), parts of the upper left and upper right corners are incorrectly assigned to the closer red cluster, further emphasizing the limitations of the DPC algorithm's assignment strategy.

The local density computation method in the DPC algorithm exhibits limitations when addressing data with diverse distributions ^[18]. To overcome these challenges, researchers have proposed various enhancements. Tong et al. ^[19] utilized continuous functions to effectively differentiate the density of points. Li et al. ^[20] introduced a fuzzy semantic unit model, reformulating the density estimation problem into an optimization framework. Chen et al. ^[21] optimized the cutoff distance using the sparrow search algorithm, with the ACC index as the objective function, effectively reducing the impact of the cutoff distance on clustering results. Zhang et al. ^[22] improved DPC in density measurement and cluster center identification. Gao et al. ^[23] improved the local density calculation by constructing an optimization function based on dataset uncertainty and using the extended pattern search algorithm to automatically optimize the cutoff distance.

To address the limitations of the assignment strategy in the DPC algorithm, Yang et al. ^[24] proposed a generalized density peak clustering algorithm based on sequential similarity, and optimized the point assignment strategy through a graph-based approach. Guo et al. ^[25] ensured that points are correctly assigned to appropriate clusters by selecting local centers, estimating connectivity, and applying distance penalties. Qin et al. ^[26] proposed a method based on label propagation and similarity metrics. This method initially assigns labels to cluster centers and propagates them to other points based on their proximity to the nearest labeled points, reducing error propagation and enhancing clustering accuracy. Yu et al. ^[27] optimized the assignment process using three-way decision theory and D-S evidence theory.

The above algorithms effectively improve the clustering performance of DPC and achieve better application results. However, most algorithms do not simultaneously consider the local neighborhood information of points when calculating local density and assigning points. They typically use traditional Euclidean distance to calculate local density, and although some methods improve by optimizing the cutoff distance, they still rely on global distribution, resulting in suboptimal performance on certain two-dimensional complex datasets or high-dimensional real-world datasets. Therefore, we propose a new similarity measure that not only considers the distance between two points but also takes into account their neighborhood distribution, integrating this similarity measure throughout the clustering process. Based on this, we propose the interactive neighbors similarity-based density peaks clustering (INSDPC) algorithm. The primary contributions of this study are listed as follows:

● A novel similarity measure, termed interactive neighbors similarity, has been introduced. This measure integrates information from interactive neighbors and shared neighbors.

● A local density calculation method based on interactive neighbors similarity has been proposed. Not only does it effectively handle simple datasets, but it also addresses complex datasets with varying densities and high-dimensional features.

● A two-step assignment strategy based on interactive neighbors similarity and neighborhood information has been proposed. This approach enhances the likelihood of correctly assigning non-center points, addressing the chain reaction of errors that occurs when a point is misclassified.

The remainder of this paper is organized as follows. Section 2 provides some preliminaries. Section 3 presents the proposed INSDPC algorithm in detail. Some necessary experimental components are presented in Section 4. Section 5 shows the experimental results and analysis. Section 5.3 concludes the paper and suggests potential directions for future research.

2.   Preliminaries

In this section, we introduce the notations of this paper as well as some basic concepts that are closely related to this work, such as DPC, $K\!N\!N$, and $S\!N\!N$. For more detailed description, one can refer to the literatures ^[14,28].

2.1.   Notations and descriptions

Some of the necessary notations are summarized in Table 1 for an easy read.

2.2.   The DPC algorithm

The mechanism of DPC can be divided into two stages: how to select the cluster centers, and how to assign non-center points to correct clusters. Taking $x_i\in X$ for example, can be selected as the cluster center if and only if it satisfy the following two conditions at the same time: $(1)$ $\rho{_i}$, the local density of $x_i$, must be greater than that of its neighboring points; $(2)$ $x_i$ must be relatively distant from points with a bigger $\rho{_j}$ for some $j = 1, 2, \cdots, n$.

The value of $\rho{_i}$ can be computed by the equation

where $d_c$ is the cutoff distance ^[21], and $\chi(x)$ represents the indicator function computed by the following equation:

Moreover, the value of $\rho{_i}$ can also be computed by equation

In fact, Eq (2.1) is called the cutoff kernel method, and Eq (2.3) is called the Gaussian kernel method. Regardless of which method is choosed, it can be observed that $\rho{_i}$ is highly sensitive to $d_c$.

The value of $\delta_i$ can be computed by the following equation:

Once a decision graph with $\rho{_i}$ as the $x-$axis and $\delta_i$ as the $y-$axis is constructed, the points located at the upper right corner can be selected as the cluster centers more easily. In numerical terms, the higher the value of $\gamma_i$, the more easily $x_i$ is selected as the cluster center. Here, $\gamma_i$ is the decision value of $x_i$ and can be computed by the following equation:

Bearing $\rho{_i}$, $\delta_i$, and $\gamma_i$ of $x_i \in X$ in mind, the cluster centers, take {$x_{i1}, x_{i2}, \cdots, x_{ik}$} for example, can be determined. After that, DPC assigns the remaining points to the cluster with the closest high-density center, completing the clustering.

2.3.   $K\!N\!N$ and $S\!N\!N$

In this subsection, we define the k-nearest neighbors and shared nearest neighbors, which are essential components of the proposed method.

The k-nearest neighbors of $x_i \in X$ is a subset of $X$, and it can be calculated by

The shared nearest neighbors of $x_i$ and $x_j$ is also a subset of $X$, and has the mathematical expression

3.   The proposed INSDPC method

In this section, we provide detailed information about the proposed method, including the motivation, the relevant definitions, the main mechanism, the algorithm pseudo-code and the computational complexity analysis.

3.1.   Motivation

The performance of the traditional DPC algorithm is often suboptimal on complex datasets, primarily due to its reliance on the calculation of $\rho{_i}$ and its sensitivity to the parameter $d_c$. The parameter $d_c$ is typically determined based solely on the global data distribution, neglecting local characteristics. However, during clustering, the nearest neighbors of a point often belong to the same cluster. Furthermore, the one-step assignment strategy of the DPC algorithm has led to this issue: if a high-density point is misassigned, the error may affect the assignment of its neighboring points, potentially resulting in more severe allocation errors. To address these issues, we propose a similarity measure that integrates information from both interactive neighbors and shared neighbors. Based on this similarity, we redefine $\rho{_i}$ and design a new two-step assignment strategy.

3.2.   Definitions of interactive neighbors similarity, local density and relative distance

3.2.1.   Interactive neighbors similarity

We provide a detailed definition of interactive neighbors similarity, its related properties, and compare it with other similarity measures.

Definition 1 (Interactive Neighbors Similarity). Given that $x_i$, $x_j \in X$, the equation for calculating the interactive neighbors similarity between $x_i$ and $x_j$ can be expressed as follows:

where the first term on the right-hand side of the equation represents the reciprocal of the average distance between the $K\!N\!N$ of $x_i$ and $x_j$, accounting for the $k^2$ points and reflecting the density around the two points. The second term represents the number of shared neighbors between $x_i$ and $x_j$, considering the overlap among these neighbors.

Obviously, Eq (3.1) satisfies the following mathematical properties.

Property 1. Given that $x_i$, $x_j \in X$, then $Ins(i, j) \geq 0$.

Proof. Because $k^2 > 0$, $\sum d_{pq} > 0$, and $|S\!N\!N(i, j)| \geq 0$ are true forever, the inequality

is obvious.

This completes the proof. □

Property 2. Given that $x_i$, $x_j \in X$, then $Ins(i, j) = Ins(j, i)$.

Proof. Because the distance $d_{pq}$ satisfies $d_{pq} = d_{qp},$ and the number of shared neighbors $|S\!N\!N(i, j)|$ satisfies

$Ins(i, j)$ is independent of the order of the points.

This completes the proof. □

In addition to the above mathematical properties, interactive neighbors similarity also exhibits locality, which considers local neighborhood information. Specifically, it depends on the $K\!N\!N$ of $x_i$ and $x_j$, as well as the shared neighbors between them.

We compare interactive neighbors similarity with Euclidean distance and cosine similarity, as shown in Table 2.

As shown in Figure 2, we consider two points $x_i$ and $x_j$, with their respective $K\!N\!N$ represented as blue dots, while $x_i$ and $x_j$ themselves are depicted as red dots. In Figure 2(a), the $K\!N\!N$ of $x_i$ and $x_j$ are in close proximity, with some of them even overlapping. This close distribution means that $x_i$ and $x_j$ have more shared neighbors, making it more likely that they belong to the same cluster. In contrast, Figure 2(b) shows that the $K\!N\!N$ of $x_i$ and $x_j$ are relatively far apart, with few shared neighbors, suggesting that $x_i$ and $x_j$ likely belong to two different clusters. Obviously, the proposed interactive neighbors similarity helps to identify similar points more accurately during the clustering process.

3.2.2.   Local density and relative distance

Following the definition of the interactive neighbors similarity between any two points, we define a new $\rho{_i}$ for $x_i$.

Definition 2 (Local Density). The local density for $x_i \in X$ is defined as follows:

The summation process aggregates the interactive neighbors similarity between $x_i$ and $x_j$ for $j = 1, 2, \cdots, n$. It considers both distance factors and the number of shared neighbors, effectively capturing the clustering structure in the dataset and revealing the intrinsic relationships between points. This approach helps to identify dense and sparse regions in the dataset.

Definition 3 (Relative Distance). The relative distance of $x_i \in X$ is defined as follows:

The calculation method of relative distance is the same as that in the DPC algorithm.

3.3.   The main mechanism of the INSDPC

The INSDPC algorithm retains the basic framework of the traditional DPC algorithm while improving its key stages. The following is a detailed explanation of the algorithm process.

3.3.1.   Selection of cluster centers

Similar to the DPC algorithm, the initial stage of our method identifies cluster centers based on two critical parameters: $\rho_i$ and $\delta_i$. Before calculating these parameters, we propose the interactive neighbors similarity, as defined by Eq (3.1). Based on the given similarity measure, $\rho_i$ is calculated using Eq (3.2), and $\delta_i$ is subsequently calculated using Eq (3.3). The $\gamma_i$ for each point is then calculated using Eq (2.5) and sorted in descending order of their values. Finally, the top $K$ points with the largest $\gamma_i$ are selected as cluster centers, denoted as $\omega = \{c_1, c_2, \cdots, c_K\}$.

3.3.2.   Assignment of core points based on interactive neighbors similarity

During the point assignment stage, instead of using the one-step assignment strategy in the traditional DPC, we adopt a two-step assignment method. First, core points are assigned to each cluster based on interactive neighbors similarity. These core points are close to the cluster center and have high $\rho_i$. The specific procedure for this step is described in Algorithm 2. In simple terms, if an unassigned point $x_j$ are the $k$ nearest neighbors of an assigned point $x_i$, and

then $x_j$ is assigned to the cluster that $x_i$ belongs to. Otherwise, if

$x_j$ will be allocated in the second step.

The calculation of the average interactive neighbors similarity is as follows:

where $k$ is the number of nearest neighbors, and $Ins(i, j)$ is the interactive neighbors similarity between the points $x_i$ and $x_j$. This equation reflects the average similarity between $x_i$ and the other points in its nearest neighborhood.

3.3.3.   Allocation of remaining points

Core points have already been successfully assigned to their respective cluster, and it is necessary to allocate the remaining points in this step. The procedure for this step is outlined in Algorithm 3.

To begin with, the algorithm identifies all remaining points $x_i$ for $i = 1, 2, \cdots, m$, and creates an allocation matrix $N \in \mathbb{R}^{m \times K}$, where each row corresponds to a remaining point and each column corresponds to a cluster in $\{C_1, C_2, \cdots, C_K\}$. For each remaining point $x_i$, the algorithm checks its k nearest neighbors to determine whether they have already been assigned to a cluster. If a neighbor $x_j$ is assigned to cluster $C_{c_j}$, the count in the allocation matrix $N$ corresponding to the row of $x_i$ and the column of $C_{c_j}$, represented by $N_{i, c_j}$, is incremented by 1.

Then, the algorithm analyzes the matrix $N$ to identify the cluster $C_{c_i}$ with the highest count in each row, denoted as $max(N)$. If $max(N) > 0$, it indicates that at least one neighbor has already been assigned to cluster $C_{c_i}$, and the remaining point $x_i$ will be allocated to this cluster. Conversely, if $max(N) = 0$, it means that none of the neighbors have been assigned to any cluster. In this case, the algorithm increases the value of $k$ to expand the neighborhood for cluster assignment. This iterative process continues until all remaining points are successfully allocated to their respective clusters, ultimately forming the cluster set

3.4.   The pseudo-code of the proposed algorithm

The procedures of the proposed algorithm are outlined in Algorithms 1–3.

3.5.   Complexity analysis

In this section, we analyze the time complexity of the proposed algorithm. Let $n$ represent the total number of points, $k$ represent the number of neighbors and $K$ represent the number of clusters.

In the cluster centers selection stage of Algorithm 1, the computational complexity of the distance matrix calculation is $O(n^2)$. Subsequently, computing the interactive neighbors similarity for all point pairs has a time complexity of $O(kn^2)$. The computation of $\rho_i$ and $\delta_i$ is the same as in the traditional DPC algorithm, with a time complexity of $O(n^2)$. Computing $\gamma_i$ and selecting cluster centers require $O(n \log n)$. Therefore, the total time complexity of the cluster center selection stage is $O(kn^2)$.

The time complexity of Algorithm 2 is mainly determined by the initialization of the queue $Q$ and the while loop. During the initialization phase, $K$ cluster centers are added to the queue, and the time complexity is $O(K)$. In the while loop, the queue processes up to all $n$ points, so the number of iterations is $O(n)$. Each iteration's time complexity is mainly determined by calculating the average interactive neighbors similarity and traversing and assigning unallocated neighbors, both of which have a time complexity of $O(k)$. In summary, the time complexity of each iteration is $O(k)$, and the overall complexity of the while loop is $O(nk)$. Including the initialization step, the total time complexity is $O(K+nk)$. Since $K$ is usually much smaller than $n$, the time complexity of the core point assignment stage is $O(nk)$.

The time complexity of Algorithm 3 is mainly determined by the while loop and matrix operations. In the worst case, all points are allocated in this stage, so the while loop needs to be executed $O(n)$ times. During each iteration, the algorithm needs to traverse all remaining points and check the cluster assignments of each point's $k$ nearest neighbors, constructing an $n \times K$ allocation matrix, the time complexity of this step is $O(nk+nK)$. Afterward, the algorithm needs to find the maximum value in the matrix to determine the final cluster assignment of the point, which has a time complexity of $O(nK)$. Therefore, the time complexity for a single iteration of the loop is $O(nk+nK)$, and the total time complexity is $O((k+K)n^2)$.

In conclusion, the time complexity of the INSDPC algorithm is $O((k+K)n^2)$. However, since both $k$ and $K$ are relatively small compared to $n$, the overall time complexity of the proposed INSDPC algorithm is $O(n^2)$.

4.   Experimental components

In this section, we introduce several experimental components, including the datasets, evaluation metrics, compared algorithms, and parameter setting. The specified experimental environment we used is listed in Table 3.

4.1.   Datasets

To assess the effectiveness of our algorithm, we use two categories of datasets for performance evaluation: synthetic and real-world datasets. Most synthetic datasets are two-dimensional, making them suitable for visualization and effective as evaluation tools for clustering algorithms. They are primarily used to test the performance of algorithms in identifying different types of clusters. Real-world datasets exhibit higher complexity, with varying dimensions and scales, enabling a more comprehensive evaluation of the algorithm's practical applicability. The synthetic and real-world datasets used in the experiments are detailed in Tables 4 and 5, respectively.

4.2.   Evaluation metrics

We select four widely used evaluation metrics to assess the quality of the clustering results: accuracy (ACC) ^[39], adjusted mutual information (AMI) ^[40], adjusted rand index (ARI) ^[40] and Fowlkes-Mallows index (FMI) ^[41]. Among these, ACC and FMI range from 0 to 1, while AMI and ARI range from -1 to 1. In all cases, higher values indicate better clustering performance.

4.3.   Compared algorithms

In the experiments, we select 9 clustering algorithms for comparison, which are DPC, K-means, FCM, DBSCAN, SNN-DPC, DPCSA, DPC-CE, HFDPC, and R-MDPC. Among them, DPC serves as the baseline method, K-means and FCM are distance-based clustering algorithms, DBSCAN is a representative density-based clustering algorithm, SNN-DPC is a satisfactory improvement of the DPC algorithm, and HFDPC and R-MDPC are two recent improvement algorithms for DPC. The description of each algorithm is as follows.

K-means ^[42]: The K-means algorithm iteratively assigns points to the nearest cluster center and updates the center's position until convergence.

FCM ^[43]: The FCM algorithm is a clustering algorithm that assigns membership degrees to points, enabling fuzzy classification into multiple clusters.

DBSCAN ^[13]: A density-based clustering algorithm that finds clusters of arbitrary shapes and detects noise points.

DPC ^[14]: This algorithm identifies high-density regions as cluster centers by combining density and distance, and then performs clustering.

SNN-DPC ^[44]: It combines shared nearest neighbor and density peak clustering, improving clustering performance on complex and noisy data by shared neighborhoods.

DPCSA ^[45]: Clustering by density peaks using weighted local density sequence and nearest neighbor assignment.

DPC-CE ^[25]: DPC-CE algorithm combines DPC and clustering effectiveness metrics, optimizing clustering results by introducing an evaluation mechanism.

HFDPC ^[46]: HFDPC preserves privacy via federated learning, integrates similar density chain, and enhances clustering performance through dimension reduction and image encryption.

R-MDPC ^[47]: It suppresses interference through relevant region allocation and a robust decision graph, accurately identifies main density peaks, and accelerates large-scale clustering based on KNN.

4.4.   Parameter setting

To guarantee a fair comparison of experimental results across different algorithms, we perform parameter tuning for each algorithm to ensure optimal performance. The specific parameter settings are provided in Table 6.

For our algorithm, there is only one integer parameter $k$ that requires tuning, and its range is restricted to [4,50]. The lower bound is set to 4 because smaller values of $k$ may cause the algorithm to become endless and cause an error. The upper bound is set at 50 because excessively large values of $k$ have little impact on the algorithm's results, making further increases unnecessary ^[44].

We test the clustering results for each $k$ value in the range [4,50] with a step size of 1, and evaluate the clustering quality using four evaluation metrics. Finally, we select the $k$ value that maximizes the ARI as the optimal value.

5.   Results and analysis

In this section, we comprehensively evaluate the performance of the INSDPC algorithm on synthetic and real-world datasets, and finally analyze the impact of the parameter $k$ on the results.

5.1.   Results on synthetic datasets

In this subsection, we evaluate the performance of various clustering algorithms on 8 widely used synthetic datasets. Table 7 presents the performance of these algorithms on the datasets listed in Table 4, along with their parameter settings. The best performance is highlighted in bold. Overall, the results show that the proposed INSDPC algorithm outperforms other algorithms on most datasets, such as R15, D31, and S2, where it consistently demonstrates the best performance.

On the Aggregation and Flame datasets, the performance of the INSDPC algorithm is slightly lower than that of the R-MDPC algorithm. This may be because the R-MDPC algorithm's strategy is better suited for handling such datasets. Notably, on the Spiral and DIM512 datasets, the INSDPC algorithm achieves perfect scores of 1 across all four evaluation metrics, showcasing its ability to accurately classify all points in these datasets. Consequently, our algorithm exhibits advantages across most datasets.

Next, we present the visualization results of several synthetic datasets, as illustrated in Figures 3–8. In each figure, subplots (a)–(h) correspond sequentially to the clustering results from INSDPC, DPC, DPCSA, SNN-DPC, DBSCAN, DPC-CE, FCM, K-means, R-MDPC, and HFDPC. Points in different colors represent distinct clusters. Additionally, except for DBSCAN, cluster centers selected by other algorithms are marked with asterisks, whereas noise points identified by DBSCAN are marked with crosses. It is important to note that the HFDPC algorithm does not explicitly mark cluster centers, as it uses grid points as cluster centers instead of traditional sample points.

As illustrated in Figure 3, the INSDPC algorithm and most DPC variants can perform clustering effectively. For the DBSCAN algorithm, despite some points being classified as noise, the overall clustering shape is correct. In contrast, DPCSA and SNN-DPC exhibit certain misclassifications in the clusters on the right side of the figure. Additionally, FCM and K-means erroneously divide a single cluster into multiple clusters and selected cluster centers between clusters, resulting in less accurate clustering outcomes.

Figure 4 illustrates the ability of various algorithms to process cross-winding datasets. It is clear that our algorithm, along with other improved DPC variants, achieves exceptional performance in clustering. Notably, the positioning of cluster centers makes INSDPC distinct from traditional DPC. The cluster centers of INSDPC are closer to the endpoints of each cluster, reducing the risk of incorrect center selection and demonstrating the effectiveness of the proposed method. However, the clustering performance of FCM and K-means remains suboptimal. Even though the correct number of clusters is provided, these algorithms uniformly partition the dataset into three regions, selecting the centroids of each partition as cluster centers. This is because the Spiral dataset cannot be divided by straight lines, and algorithms like K-means and FCM, which rely solely on distance for clustering, perform poorly when handling this dataset.

Figure 5 illustrates the clustering results of various algorithms on the Flame dataset. As the cluster shapes become increasingly complex, the performance of FCM and K-means is still not satisfactory. Both algorithms incorrectly assign some points from the lower cluster to the upper cluster, highlighting the limitations of these two algorithms in handling manifold-shaped clusters. The DBSCAN algorithm effectively identifies the two clusters, yet it still struggles with managing noise points. In contrast, INSDPC, along with DPC and its improved variants, demonstrates outstanding performance by accurately identifying clusters and their centers.

Figure 6 illustrates the clustering results for the R15 dataset, which contains 15 spherical clusters with uniformly distributed points. Although each algorithm has some minor imperfections, they all effectively identify the cluster centers and complete the clustering task.

Figure 7 illustrates the clustering results for the Pathbased dataset. With the exception of the R-MDPC algorithm, most algorithms accurately identify the cluster centers. The HFDPC and SNN-DPC algorithms perform the best, and our method outperforms other algorithms, with only a few misassignments in the lower-right region. The DPC algorithm and its variants, as well as distance-based algorithms, misassign some points from the left and right sides of the half-ring clusters to other clusters, leaving only a small portion of the half-ring cluster at the top. The DBSCAN algorithm is prone to point misassignments and generates considerable noise in the half-ring cluster. This issue arises because the density of this cluster is far below the value set by Minpts.

Figure 8 illustrates the results of various clustering algorithms on the S2 dataset, which poses greater challenges due to its features, including noise, complex structures and uneven density distributions. The DPC-CE algorithm incorrectly identifies the cluster center, leading to suboptimal results. The DBSCAN algorithm fails to distinguish the three clusters in the lower-right region and erroneously classifies numerous boundary points as noise. The remaining algorithms correctly identify all clusters, but INSDPC outperforms them in capturing finer details.

From the results and analysis above, it is evident that the INSDPC algorithm outperforms other algorithms on most datasets. It not only accurately identifies cluster centers, but also effectively manages clusters with complex shapes. The main reason is that our algorithm takes into account the local neighborhood information of points. Specifically, in the selection of cluster centers, the calculation of local density relies on interactive neighbors similarity, which considers both the distance between two points and the number of shared nearest neighbors. The closer the points are, the greater their contribution to the density. During the point assignment stage, the remaining points are assigned based on the distribution of their neighbors. Considering these factors, our algorithm demonstrates relatively good clustering performance.

5.2.   Results on real-world datasets

To further assess the effectiveness of the INSDPC, we conduct experiments on 10 real-world datasets. Table 8 summarizes the clustering performance of 10 algorithms on these datasets, along with the parameter settings for each algorithm. The best performance is highlighted in bold. Due to the increase in data dimensions and the presence of outliers in real-world datasets, all algorithms generally perform worse on real-world datasets compared to synthetic datasets. Nevertheless, the INSDPC algorithm demonstrates remarkable advantages, achieving the best performance on the Wine, Seeds, and Ionosphere datasets, which proves its excellent capability in handling high-dimensional and large-scale datasets. On the Iris dataset, both INSDPC and SNN-DPC achieve the highest clustering performance, significantly outperforming other algorithms. Although the INSDPC algorithm did not achieve the best AMI on the Waveform and the Glass datasets, it obtained the best ACC, ARI, and FMI, significantly better than those of the other algorithms. On the WDBC dataset, although the INSDPC algorithm has a lower FMI score than HFDPC, its ACC, AMI, and ARI are higher, making INSDPC the best in overall performance on the WDBC dataset. On the Dermatology dataset, INSDPC demonstrates excellent performance in the ACC metric, markedly outperforming other algorithms, although it is slightly surpassed by the SNN-DPC algorithm across other evaluation metrics. Overall, the INSDPC algorithm consistently achieves better performance than DPC across all datasets. The experimental results demonstrate that the algorithm exhibits good robustness in complex real-world environments.

5.3.   Parameter analysis

In this subsection, we analyze the impact of the parameter $k$ on the performance of the INSDPC algorithm. As a critical parameter, $k$ specifies the number of neighboring points considered within the local neighborhood of each point during the clustering process. The value of $k$ significantly affects the selection of cluster centers and the assignment of points. Consequently, the choice of $k$ directly determines the performance of our algorithm.

Figure 9 illustrates the variations in AMI, ARI, ACC, and FMI for seven representative datasets with varying parameter $k$. We observe that the trends of the four metrics across datasets with varying $k$ are generally consistent. The R15 dataset exhibits stability across all evaluation metrics, showing low sensitivity to $k$ variations and maintaining consistently high scores for most $k$ values. The Flame and D31 datasets show lower performance for small values of $k$ $(k < 10)$. However, as $k$ increases, the performance gradually stabilizes, possibly because the expanded neighborhood range allows the algorithm to better identify the clustering structure. For most other datasets, the performance is better for lower $k$ values, but declines gradually as $k$ increases. A particularly notable exception is observed in the Ionosphere dataset, where an inflection point appears around $k = 17$. At this point, all evaluation metrics show a marked decline, followed by stabilization. This indicates that larger $k$ are ineffective for this dataset. In summary, as $k$ increases, the metrics for most datasets fluctuate within a small range or stabilize, which proves the robustness of our algorithm across different datasets.

6.   Conclusions and future work

This paper improves upon the traditional DPC algorithm and proposes a density peaks clustering algorithm based on interactive neighbors similarity, called INSDPC. The algorithm incorporates interactive neighbor relationships and shared neighbor information to redefine $\rho{_i}$, effectively addressing the limitations of the traditional DPC algorithm in handling clusters with varying densities. Additionally, INSDPC introduces a two-step assignment strategy that leverages interactive neighbors similarity and neighborhood information. This strategy addresses the joint assignment errors of the one-step assignment strategy in the traditional DPC algorithm. To evaluate the performance of INSDPC, we conduct experiments on both synthetic and real-world datasets. The results show that INSDPC more accurately identifies cluster centers and achieves higher clustering accuracy on most complex datasets.

Although the INSDPC algorithm exhibits outstanding clustering performance, determining the parameter $k$ inevitably adds computational overhead. Future research will explore ways to automatically select the optimal $k$ or propose an adaptive method to improve the algorithm's efficiency. On the application side, we aim to expand the algorithm to domains such as social network analysis, image segmentation, and bioinformatics to address practical challenges and further validate its applicability across various fields.

Author contributions

Shihu Liu: Writing-original draft, Software, Methodology, Conceptualization; Yirong He: Writing-review & editing, Data Curation, Visualization, Validation; Xiyang Yang: Formal analysis, Funding acquisition; Zhiqiang Yu: Supervision, Project administration. All authors have read and approved the final version of the manuscript for publication.

Use of Generative-AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

We are hugely grateful to the possible anonymous reviewers for their constructive comments with respect to the original manuscript. Additionally, we acknowledge the support received from the Fundamental Research Project of Yunnan Province (Grant No. 202301AT070015), the Xingdian Talent Support Program for Young Talents (Grant Nos.XDYC-QNRC-2022-0518, XDYC-QNRC-2023-0388) and the Open Project of Fujian Provincial Key Laboratory of Data-Intensive Computing (Grant No. SJXY202401).

Conflict of interest

The authors declare that they have no conflict of interest.