Global Optimal Path-Based Clustering Algorithm

Abstract--Combinatorial optimization problems for clustering are known to be NPhard. Most optimization methods are not able to find the global optimum solution for all datasets. T o solve this problem, we propose a global optimal path-based clustering (GOPC) algorithm in this paper. The GOPC algorithm is based on two facts: (1) medoids have the minimum degree in their clusters; (2) the minimax distance between two objects in one cluster is smaller than the minimax distance between objects in different clusters. Extensive experiments are conducted on synthetic and real-world datasets to evaluate the performance of the GOPC algorithm. The results on synthetic datasets show that the GOPC algorithm can recognize all kinds of clusters regardless of their shapes, sizes, or densities. Experimental results on real-world datasets demonstrate the effectiveness and efficiency of the GOPC algorithm. In addition, the GOPC algorithm needs only one parameter, i.e., the number of clusters, which can be estimated by the decision graph. The advantages mentioned above make GOPC a good candidate as a general clustering algorithm. In clustering algorithms, measuring the dissimilarity between any pair of points is very important. The most commonly used dissimilarity method is Euclidean distance. However, in many real-world applications of pattern classification and data mining, we are often confronted with high-dimensional features of the investigated data, which adversely affects clustering performance due to the curse of dimensionality [9], [10]. It is widely acknowledged that many real-world datasets stringently obey low-rank rules, which means that they are distributed on a manifold of a dimensionality that is often much lower than that of ambient space [11], [12], [13].