一种新型高效的无参数化聚类算法

作者：陈靖飒; 程开丰; 吴怀岗^*

来源：小型微型计算机系统, 2020, 41(04): 699-703.

• 无参数化聚类
• 赋权完全图
• 最小生成树
• 一维权重空间

为了解决K-means算法对初始聚类数k和初始聚类中心经验参数的依赖问题,提出了一种基于最小生成树的无参数化聚类MNC算法(MST based Non-parameterized Clustering).首先将待聚类数据集抽象成赋权完全图WCG(Weighted Complete Graph),其中的点代表向量,赋权边代表数据间的相似关系;然后将WCG转换成全连通的最小生成树M ST(M inimum Spanning Tree);接着利用k=2的经典K-means算法对M ST边集的一维权重空间进行聚类,得到剪枝的阈值;最后对M ST进行剪枝和噪声过滤,得到的连通分量即为聚类的簇.实验结果表明,相对传统聚类算法,MNC算法不仅能够识别不同形状的数据簇,而且其无参数化的特点可以大大减少聚类时间,提高聚类效率.

• 单位
  南京大学; 南京师范大学