A fast minimum spanning tree algorithm based on K-means

Minimum spanning trees (MSTs) have long been used in data mining, pattern recognition and machine learning. However, it is difficult to apply traditional MST algorithms to a large dataset since the time complexity of the algorithms is quadratic. In this paper, we present a fast MST (FMST) algorithm on the complete graph of N points. The proposed algorithm employs a divide-and-conquer scheme to produce an approximate MST with theoretical time complexity of O(N-1.5), which is faster than the conventional MST algorithms with O(N-2). It consists of two stages. In the first stage, called the divide-and-conquer stage, K-means is employed to partition a dataset into root N clusters. Then an exact MST algorithm is applied to each cluster and the produced root N MSTs are connected in terms of a proposed criterion to form an approximate MST. In the second stage, called the refinement stage, the clusters produced in the first stage form root N - 1 neighboring pairs, and the dataset is repartitioned into root N - 1 clusters with the purpose of partitioning the neighboring boundaries of a neighboring pair into a cluster. With the root N - 1 clusters, another approximate MST is constructed. Finally, the two approximate MSTs are combined into a graph and a more accurate MST is generated from it. The proposed algorithm can be regarded as a framework, since any exact MST algorithm can be incorporated into the framework to reduce its running time. Experimental results show that the proposed approximate MST algorithm is computationally efficient, and the approximation is close to the exact MST so that in practical applications the performance does not suffer. (C) 2014 Elsevier Inc. All rights reserved.