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

Clustering Algorithm Based on Dynamic Division of Connected Graph

作　　者：邓健爽[1] 郑启伦[1] 彭宏[1] 邓维维[1] 

机构地区：[1]华南理工大学计算机科学与工程学院,广东广州510640

出　　处：《华南理工大学学报（自然科学版）》2007年第1期118-122,共5页Journal of South China University of Technology(Natural Science Edition)

基　　金：广州市科技攻关项目(2004Z2-D0091);广东省科技攻关项目(2005B10101033A10202001)

摘　　要：当前大部分的聚类算法都难以处理任意形状和大小、存在孤立点和噪音以及密度多变的簇,为此,文中提出了一种基于连通图动态分裂的聚类算法.首先构造数据集的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.

关 键 词：连通图 聚类算法 动态分裂 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]