基于密度的统计合并聚类算法

PDF下载HTML

Title:

Density-based statistical merging clustering algorithm

作者:

刘贝贝¹, 马儒宁¹, 丁军娣²

1. 南京航空航天大学 理学院, 江苏 南京 211100;
2. 南京理工大学 计算机科学与技术学院, 江苏 南京 210094

Author(s):

LIU Beibei¹, MA Runing¹, DING Jundi²

1. College of Science, Nanjing University of Aeronautics and Astronautics, Nanjing 211100, China;
2. School of Computer Science and Technology, Nanjing University of Science and Technology, Nanjing 210094, China

关键词:

数据点; 密度; 随机变量; 合并; 聚类; 噪声

Keywords:

data points; density; random variable; merging; clustering algorithm; noise

分类号:

O235;TP311

DOI:

10.11992/tis.201410028

文献标志码:

A

摘要:

针对现有聚类算法处理噪声能力差和速度较慢的问题,提出了一种基于密度的统计合并聚类算法(DSMC)。该算法将数据点的每一个特征看作一组独立随机变量,根据独立有限差分不等式得出统计合并判定准则;同时,结合数据点的密度信息,把密度从大到小的排序作为凝聚过程中的合并顺序,实现了各类数据点的统计合并。人工数据集和真实数据集的实验结果表明,DSMC算法不仅可以处理凸状数据集,对于非凸、重叠、加入噪声的数据集也有良好的聚类效果,充分表明了该算法的适用性和有效性。

Abstract:

The ability of existing clustering algorithms to deal with noise is poor, and the speed is slow, instead this paper proposes a density-based statistical merging clustering algorithm (DSMC). The new algorithm takes each group of data points as a set of independent random variables, and gathers statistical criteria from the independent bounded difference inequality. Meanwhile, combined with the density information of the data points, the DSMC algorithm takes the descending order of the density as the merging order in the process of condensation, and thereby achieves statistical merging of different types of data points. The experimental results with both artificial datasets and real datasets show that the DSMC algorithm can not only deal with convex data set, and also has good clustering effects on nonconvex shaped, overlapped and noisy, data sets. This proves that the algorithm has good applicability and validity.