A Neighborhood Density Estimation Clustering Algorithm Based on Minimum Spanning Tree

摘要

In this paper a clustering algorithm based on the minimum spanning tree (MST) with neighborhood density difference estimation is proposed. Neighborhood are defined by patterns connected with the edges in the MST of a given dataset. In terms of the difference between patterns and their neighbor density, boundary patterns and corresponding boundary edges are detected. Then boundary edges are cut, and as a result the dataset is split into defined number clusters. For reducing time complexity of detecting boundary patterns, an rough and a refined boundary candidates estimation approach are employed, respectively. The experiments are performed on synthetic and real data. The clustering results demonstrate the proposed algorithm can deal with not well separated, shape-diverse clusters.