基于加权二分图的K均值最佳聚类数确定算法  

Determination algorithm of K-means optimal clustering number based on weighted bipartite graph

作　　者：林伟杰 王勇 周林 LIN Wei-jie;WANG Yong;ZHOU Lin(College of Computer Science and Technology,Shanghai University of Electric Power,Shanghai 200120,China)

机构地区：[1]上海电力大学计算机科学与技术学院,上海200120

出　　处：《计算机工程与设计》2023年第4期1104-1111,共8页Computer Engineering and Design

基　　金：国家自然科学基金项目(61772327);上海自然科学基金项目(20ZR1455900);浙江大学工业控制技术国家重点实验室开放式基金项目(ICT1800380)。

摘　　要：针对传统K均值算法无法精确预设初始聚类中心数目的问题,提出基于加权二分图的K均值最佳聚类数确定算法。设计等比例随机采样的方式,从原始大数据集中产生小数据集集合并从中产生聚类中心点点集,提高应对大规模数据集的能力;用聚类中心点点集形成二分图,针对聚类算法特性改进其赋权函数;设计评价数,改进Kuhn-Munkres算法,将其用于求取二分图的最大权完美匹配,确定最佳聚类数。实验结果表明,相较其它6种对比算法,所提算法有更高的准确性,更好的稳定性,以及更强的处理大规模数据集能力。Aiming at the problem that the traditional K-means algorithm cannot preset the number of initial clustering centers accurately,a K-means optimal clustering number determination algorithm based on weighted bipartite graph was proposed.The equal-proportion random sampling method was designed to generate small datasets from the original large datasets and generate a cluster center point set from it,which made the algorithm improve the ability to deal with large data set.The bipartite graph was formed through clustering center point set and its weighting function was improved according to the characteristics of clustering algorithm.The evaluation index was designed to improve Kuhn-Munkres algorithm,which was used to solve the maximum weight perfect matching of bipartite graphs and determine the optimal clustering number.Results show that the proposed algorithm has higher accuracy,better stability,and the ability to handle large-scale datasets compared with the other six comparison algorithms.

关 键 词：K均值 初始聚类中心 随机采样 二分图 Kuhn-Munkres算法 最佳聚类数 完美匹配 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]