Global Optimal Path-Based Clustering Algorithm
  Combinatorial optimization problems for clustering are known to be NP-hard.
Most optimization methods are not able to find the global optimum solution for
all datasets. To 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. Codes are available at
https://github.com/Qidong-Liu/Clustering.
