 |
The steps in DPC algorithm are summarized in Algorithm 1. After calculating the local density and the relative distance of all data points (steps 1 and 2), the DPC algorithm establishes a decision graph (step 3). From the decision graph, it has been shown that the point with high values of both 𝜌_𝑖 and 𝛿_𝑖 is called a peak, then the cluster center can be selected from those peaks (steps 3 and 4). In the final step, the non-center points are assigned to the same cluster as their nearest neighbor peak (step 5). Suppose that there are n points in the dataset. The time complexity of DPC depends on the following parts: (1) calculating the Euclidean distance between points takes 𝑂(𝑛^2); (2) computing the local density and relative distance for all points takes (3) the assignment of non-center points to the clusters takes 𝑂(𝑛). Therefore, the total approximate time complexity of DPC is 𝑂(𝑛^2). |
IEEE/ICACT20220302 Slide.08
[Big Slide]