基于约束三角剖分的k-means聚类

k-MEANS CLUSERING BASED ON CONSTRAINED TRIANGULATION

提出基于约束三角剖分的k-means聚类算法.笔者首先按照约束三角剖分规则对数据点集进行三角网格化,删除大于给定阈值的长边形成k个连通子图,每个连通子图作为一个子类；然后对删除长边的孤立数据点在其邻域内进行局部划分,将其归到最接近的子类中.实验结果表明本文算法无需事先输入聚类数目,可以发现任意非凸形状簇.

A new method named k -means clustering algorithm based on constrained triangulation is proposed. Firstly,the set of data points is triangled mesh according to constrained triangulation rule, deleted the long edges greater than the given threshold, forming k connected subgraphs and each connected subgraph is a subclass. The isolated points deleted the long side are clustered in the neighborhood, classified into the closest a subclass. The experimental results show that this algorithm does not need to input the number of clusters in advance, can discover arbitrary non -convex shape clusters.