期刊
INFORMATION SCIENCES
卷 295, 期 -, 页码 1-17出版社
ELSEVIER SCIENCE INC
DOI: 10.1016/j.ins.2014.10.012
关键词
Minimum spanning tree; Clustering; Manifold learning; K-means
资金
- Natural Science Foundation of China [61175054]
- Center for International Mobility (CIMO)
- K.C. Wong Magna Fund in Ningbo University
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据