Recently, a new density-peak-based clustering method, called clustering with local density peaks-based minimum spanning tree (LDP-MST), was proposed, which has several attractive merits, e.g., being able to detect arbitrarily shaped clusters and not very sensitive to noise and parameters. Nevertheless, we also found the limitation of LDP-MST in efficiency. Specifically, LDP-MST has O(NlogN+M²) time, where N denotes the dataset size and M is an intermediate variable denoting the number of local density peaks. As our experimental results reveal, when processing large-size datasets, the value of M could be very large and consequently those steps of LDP-MST involving O(M²) time term would be time-consuming. And in the worst case, the value of M could be very close to that of N, which means that the time complexity of LDP-MST could be O(N²) in the worst case of M. In this study, we use more efficient algorithms to implement those steps of LDP-MST that involve the O(M²) time term such that the proposed method, Fast LDP-MST, has O(NlogN) time complexity even if MN. Our experiments demonstrate that Fast LDP-MST is overall more efficient than LDP-MST on large-size datasets, without sacrificing the merits of LDP-MST in effectiveness, robustness, and user-friendliness.

Clustering aims at discovering the natural groupings in a dataset, prevalent in many disciplines that involve multivariate data analysis. In this paper, we propose a physically inspired graph-theoretical clustering method, which first makes the data points organized into an attractive graph, called In-Tree, via a physically inspired rule, called Nearest Descent (ND). The rule of ND works to select the nearest node in the descending direction of potential as the parent node of each node, which is fundamentally different from the classical Gradient Descent. The constructed In-Tree proves a very good candidate for clustering due to its particular features and properties. In the In-Tree, the original clustering problem is reduced to a problem of removing the inter-cluster edges from this graph. Pleasingly, those inter-cluster edges are usually so distinguishable that they can be easily determined by different automatic edge-cutting methods. We also propose a visualized strategy to validate the effectiveness of the automatic edge-cutting methods. The experimental results reveal that the proposed method is superior to the related clustering methods. The results also reveal the characteristics of different automatic cutting methods and the meaningfulness of the visualized strategy in increasing the reliability of the clustering results in practice.

In our physically inspired in-tree (IT) based clustering algorithm and the series after it, there is only one free parameter involved in computing the potential value of each point. In this work, based on the Delaunay Triangulation or its dual Voronoi tessellation, we propose a nonparametric process to compute potential values by the local information. This computation, though nonparametric, is relatively very rough, and consequently, many local extreme points will be generated. However, unlike those gradient-based methods, our IT-based methods are generally insensitive to those local extremes. This positively demonstrates the superiority of these parametric (previous) and nonparametric (in this work) IT-based methods.

Previously, we proposed a physically-inspired method to construct data points into an effective in-tree (IT) structure, in which the underlying cluster structure in the dataset is well revealed. Although there are some edges in the IT structure requiring to be removed, such undesired edges are generally distinguishable from other edges and thus are easy to be determined. For instance, when the IT structures for the 2-dimensional (2D) datasets are graphically presented, those undesired edges can be easily spotted and interactively determined. However, in practice, there are many datasets that do not lie in the 2D Euclidean space, thus their IT structures cannot be graphically presented. But if we can effectively map those IT structures into a visualized space in which the salient features of those undesired edges are preserved, then the undesired edges in the IT structures can still be visually determined in a visualization environment. Previously, this purpose was reached by our method called IT-map. The outstanding advantage of IT-map is that clusters can still be found even with the so-called crowding problem in the embedding. In this paper, we propose another method, called IT-Dendrogram, to achieve the same goal through an effective combination of the IT structure and the single link hierarchical clustering (SLHC) method. Like IT-map, IT-Dendrogram can also effectively represent the IT structures in a visualization environment, whereas using another form, called the Dendrogram. IT-Dendrogram can serve as another visualization method to determine the undesired edges in the IT structures and thus benefit the IT-based clustering analysis. This was demonstrated on several datasets with different shapes, dimensions, and attributes. Unlike IT-map, IT-Dendrogram can always avoid the crowding problem, which could help users make more reliable cluster analysis in certain problems.