无参数聚类边界检测算法的研究

Research on Nonparametric Clustering Boundary Detection Algorithm

为自动快速地提取聚类的边界点,减少输入参数对边界检测结果的影响,提出一种无参数聚类边界检测算法。该算法不需要任何参数,在生成的三角剖分图上计算每个数据点的边界度,用k-means自动计算边界度阈值,按边界度阈值将数据集划分为候选边界点和非候选边界点两部分,根据噪声点在三角剖分图中的性质去除候选边界点中的噪声点,最终检测出边界点。实验结果表明,该算法能快速、有效地识别任意形状、不同大小和密度聚类的边界点。

In order to detect boundary points of clustering automatically and effectively, and to eliminate the impact of parameters on the results of the boundary detection, a new nonparametric boundary detection algorithm based on delaunay triangulation is presented. This algorithm calculates the boundary degree for each point in the generated delaunay triangulation without any parameters. According to the boundary degree＇s threshold that is automatically calculated by k-means, dataset is divided into two parts： candidate set of boundary points and the set of non-boundary points. Based on the characteristics of the noise points, the noise points are removed from the candidate set of boundary points. It detects out boundary points of clustering. Experimental results show that the algorithm can identify boundary points in noisy datasets containing clustering of different shapes and sizes effectively and efficiently.