作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2011, Vol. 37 ›› Issue (15): 23-26. doi: 10.3969/j.issn.1000-3428.2011.15.006

• 专栏 • 上一篇    下一篇

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

邱保志,许 敏   

  1. (郑州大学信息工程学院,郑州 450001)
  • 收稿日期:2011-01-10 出版日期:2011-08-05 发布日期:2011-08-05
  • 作者简介:邱保志(1964-),男,教授、博士,主研方向:数据挖掘;许 敏,硕士研究生
  • 基金资助:

    国家自然科学基金资助项目(60673087);河南省教育厅自然科学基金资助项目(2009A520028);郑州大学骨干教师基金资助 项目

Research on Nonparametric Clustering Boundary Detection Algorithm

QIU Bao-zhi, XU Min   

  1. (School of Information Engineering, Zhengzhou University, Zhengzhou 450001, China)
  • Received:2011-01-10 Online:2011-08-05 Published:2011-08-05

摘要:

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

关键词: 边界点, 无参数, 边界度, 聚类, 三角剖分

Abstract:

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.

Key words: boundary points, nonparametric, boundary degree, clustering, delaunay triangulation

中图分类号: