Page 113 - 《软件学报》2021年第10期

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2021,32(10):30853103 [doi: 10.13328/j.cnki.jos.006016] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563


一种采用新型聚类方法的最佳类簇数确定算法 

2
1,2
2
3
2
朱二周 , 孙 悦 , 张远翔 , 高 新 , 马汝辉 , 李学俊 2
1
(计算智能与信号处理教育部重点实验室(安徽大学),安徽 合肥 230601)
2
(安徽大学 计算机科学与技术学院,安徽 合肥 230601)
3 (上海交通大学 电子信息与电气工程学院,上海 200240)
通讯作者: 朱二周, E-mail: ezzhu@ahu.edu.cn

摘 要: 聚类分析是统计学、模式识别和机器学习等领域的研究热点.通过有效的聚类分析,数据集的内在结构与
特征可以被很好地发掘出来.然而,无监督学习的特性使得当前已有的聚类方法依旧面临着聚类效果不稳定、无法
对多种结构的数据集进行正确聚类等问题.针对这些问题,首先将 K-means 算法和层次聚类算法的聚类思想相结合,
提出了一种混合聚类算法 K-means-AHC;其次,采用拐点检测的思想,提出了一个基于平均综合度的新聚类有效性
指标 DAS(平均综合度之差,difference of average synthesis degree),以此来评估 K-means-AHC 算法聚类结果的质量;
最后,将 K-means-AHC 算法和 DAS 指标相结合,设计了一种寻找数据集最佳类簇数和最优划分的有效方法.实验将
K-means-AHC 算法用于测试多种结构的数据集,结果表明:该算法在不过多增加时间开销的同时,提高了聚类分析
的准确性.与此同时,新的 DAS 指标在聚类结果的评价上要优于当前已有的常用聚类有效性指标.
关键词: 聚类分析;聚类算法;聚类有效性指标;最佳类簇数;数据挖掘
中图法分类号: TP181

中文引用格式: 朱二周,孙悦,张远翔,高新,马汝辉,李学俊.一种采用新型聚类方法的最佳类簇数确定算法.软件学报,2021,
32(10):30853103. http://www.jos.org.cn/1000-9825/6016.htm
英文引用格式: Zhu EZ, Sun Y, Zhang YX, Gao X, Ma RH, Li XJ. Optimal clustering number determining algorithm by the new
clustering method. Ruan Jian Xue Bao/Journal of Software, 2021,32(10):30853103 (in Chinese). http://www.jos.org.cn/1000-
9825/6016.htm
Optimal Clustering Number Determining Algorithm by the New Clustering Method

2
3
1,2
2
2
ZHU Er-Zhou , SUN Yue , ZHANG Yuan-Xiang , GAO Xin , MA Ru-Hui , LI Xue-Jun 2
1 (Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education, Anhui University, Hefei 230601, China)
2 (School of Computer Science and Technology, Anhui University, Hefei 230601, China)
3 (School of Electronic Information and Electrical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China)
Abstract: Clustering analysis is a hot research topic in the fields of statistics, pattern recognition, and machine learning. Through
effective clustering analysis, the intrinsic structure and characteristics of datasets can be well discovered. However, due to the
unsupervised learning feature, the existing clustering methods are still facing the problems of unstable and inaccurate on processing
different types of datasets. In order to solve these problems, a hybrid clustering algorithm, K-means-AHC, is firstly proposed based on the
combination of the K-means algorithm and the hierarchical clustering algorithm. Then, based on the inflexion point detection, a new
clustering validity index, DAS (difference of average synthesis degree), is proposed to evaluate the results of the K-means-AHC clustering
algorithm. Finally, through the combination of the K-means-AHC algorithm and the DAS index, an effective method of finding the
optimal clustering numbers and optimal partitions of datasets is designed. The K-means-AHC algorithm is used to test many kinds of

 基金项目: 安徽省自然科学基金(2008085MF188); 国家自然科学基金(61972001)
Foundation item: Natural Science Foundation of Anhui Province, China (2008085MF188); National Natural Science Foundation of
China (61972001)
收稿时间: 2019-09-09; 修改时间: 2019-11-17, 2020-01-18; 采用时间: 2020-02-13