基于连通图动态分裂的聚类算法

Clustering Algorithm Based on Dynamic Division of Connected Graph

当前大部分的聚类算法都难以处理任意形状和大小、存在孤立点和噪音以及密度多变的簇,为此,文中提出了一种基于连通图动态分裂的聚类算法.首先构造数据集的l-连通图,然后采用动态分裂策略对l-连通图进行分割,把数据集分成多个互不相连的连通图子集,每个连通图子集为一类.实验结果表明,所提出的算法能够有效地解决任意形状和大小、存在孤立点和噪音以及密度多变的簇的聚类问题,具有广泛的适用性.

Most clustering algorithms have a difficulty in dealing with the cluster with arbitrary shape and,size, outher points and noises, as well as highly variable density. In order to overcome this difficulty, a clustering algorithm based on dynamic division of connected graph is proposed. In this algorithm, a l-connected graph of data set is first constructed, which is then divided with the strategy of dynamic division. Therefore, the data set is divided into several disconnected subsets of connected graph, each of which forms a clustering. Experimental results show that the proposed algorithm is of great applicability because it can effectively solve the clustering problem of the cluster with arbitrary shape and size, outlier points and noises, as well as highly variable density.