结合人工蜂群优化的粗糙K-means聚类算法

doi:10.3778/j.issn.1673-9418.2012099

计算机科学与探索 ›› 2022, Vol. 16 ›› Issue (8): 1923-1932.DOI: 10.3778/j.issn.1673-9418.2012099

• 理论与算法 • 上一篇

结合人工蜂群优化的粗糙K-means聚类算法

叶廷宇¹, 叶军¹^,⁺(), 王晖¹^,², 王磊¹^,²

1. 南昌工程学院信息工程学院，南昌 330000
2. 江西省水信息协同感知与智能处理重点实验室（南昌工程学院），南昌 330000

收稿日期:2020-12-28 修回日期:2021-03-05 出版日期:2022-08-01 发布日期:2021-04-08
通讯作者: +E-mail: 2003992646@nit.edu.cn。
作者简介:叶廷宇（1997—），男，江西南昌人，硕士研究生，主要研究方向为演化计算、群智能、机器学习。
叶军（1968—），男，江西万安人，硕士，教授，CCF会员，主要研究方向为粗糙集和粒计算、知识发现和数据挖掘等。
王晖（1982—），男，湖北红安人，博士，教授，CCF会员，主要研究方向为演化计算、群智能、调度和水资源优化。
王磊（1967—），男，湖北鄂州人，博士，副教授，CCF会员，主要研究方向为粗糙集和粒计算、知识发现和数据挖掘等。
基金资助:
国家自然科学基金(61562061);国家自然科学基金(61663028);江西省自然科学基金(20212BAB202022);江西省教育厅科技项目(GJJ170995)

Rough K-means Clustering Algorithm Combined with Artificial Bee Colony Optimization

YE Tingyu¹, YE Jun¹^,⁺(), WANG Hui¹^,², WANG Lei¹^,²

1. School of Information Engineering, Nanchang Institute of Technology, Nanchang 330000, China
2. Jiangxi Province Key Laboratory of Water Information Cooperative Sensing and Intelligent Processing (Nanchang Institute of Technology), Nanchang 330000, China

Received:2020-12-28 Revised:2021-03-05 Online:2022-08-01 Published:2021-04-08
About author:YE Tingyu, born in 1997, M.S. candidate. His research interests include evolutionary computing, swarm intelligence and machine learning.
YE Jun，born in 1968, M.S., professor, member of CCF. His research interests include rough set, granular computing, knowledge discovery, data mining, etc.
WANG Hui, born in 1982, Ph.D., professor, member of CCF. His research interests include evolutionary computing, swarm intelligence, dispatch and water resource optimization.
WANG Lei, born in 1967, Ph.D., associate professor, member of CCF. His research interests include rough set, granular computing, knowldge discovery, data mining, etc.
Supported by:
the National Natural Science Foundation of China(61562061);the National Natural Science Foundation of China(61663028);the Natural Science Foundation of Jiangxi Province(20212BAB202022);the Technology Project of Ministry of Education of Jiangxi Province(GJJ170995)

摘要/Abstract

摘要：

粗糙K-means聚类算法具有较强的处理边界不确定数据能力，但该算法也存在对初始聚类中心选取敏感，以及采用固定权重和阈值方式而导致聚类结果不稳定、精度下降等问题。许多研究工作从不同角度致力于解决这些问题。引入人工蜂群算法（ABC）从三方面对算法进行了改进：首先，以下近似和边界集中数据对象个数与对象在数据集中空间分布的差异性乘积的比值为基础，设计了一种更为合理的动态调整下近似和边界集的权重方法。其次，为加快算法的收敛速度，给出了一种与迭代次数相关联的自适应阈值 $ε$ 的实现方法。最后，通过构造蜜源位置的适应度函数，引导蜂群向高质量蜜源全局搜索，把蜂群每次迭代得到的最优源位置作为初始聚类中心，并在此基础上进行交替聚类。实验结果表明，改进后的算法提高了聚类结果的稳定性，获得了较好的聚类效果。

关键词: 粗糙K-means聚类算法, 人工蜂群算法（ABC）, 蜜源, 聚类中心, 适应度函数

Abstract:

The rough K-means clustering algorithm has strong ability to deal with data with uncertain boundaries. However, this algorithm also has limitations such as sensitivity to the selection of initial clustering centers, and use of fixed weights and thresholds resulting in unstable clustering results and decreased accuracy. A lot of research has been devoted to solving these problems from different angles. With introduction of artificial bee colony (ABC) algorithm, the algorithm is improved from three aspects. Firstly, based on the ratio of the number of objects in lower approximate set and the boundary set to the product of the difference of the objects in the dataset, a more reasonable method of dynamically adjusting the weights of approximation and boundary set is designed. Secondly, in order to speed up the convergence speed of the algorithm, an implementation method of adaptive threshold ε associated with the number of iterations is given. Thirdly, by constructing the fitness function of the nectar source location, the bee colony is guided to search for high-quality nectar sources globally. The best position of honey source obtained by each iteration is taken as the initial cluster center, and the cluster is carried out on the basis of this. Experimental results show that the improved algorithm improves the stability of the clustering results and obtains better clustering effect.

Key words: rough K-means algorithm, artificial bee colony (ABC) algorithm, nectar, cluster center, fitness function

中图分类号:

TP391

叶廷宇, 叶军, 王晖, 王磊. 结合人工蜂群优化的粗糙K-means聚类算法[J]. 计算机科学与探索, 2022, 16(8): 1923-1932.

YE Tingyu, YE Jun, WANG Hui, WANG Lei. Rough K-means Clustering Algorithm Combined with Artificial Bee Colony Optimization[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(8): 1923-1932.

图/表 13

参考文献 25

[1]	LINGRAS P, WEST C. Interval set clustering of Web user with rough K-means[J]. Journal of Intelligent Information Systems, 2004, 23(1): 5-16.
[2]	苗夺谦, 李道国. 粗糙集理论、算法与应用[M]. 北京: 清华大学出版社, 2008.
	MIAO D Q, LI D G. Rough sets theory algorithms and application[M]. Beijing: Tsinghua University Press, 2008.
[3]	MITRA S, BANKA H, PEDRYCZ W. Rough fuzzy collabo-rative clustering[J]. IEEE Transactions on Systems, Man and Cybernetics, 2006, 36(4): 795-805.
[4]	MAJI P, PAL S K. RFCM: a hybrid clustering algorithm using rough and fuzzy sets[J]. Fundamenta Informaticae, 2007, 80(4): 475-496.
[5]	周涛. 具有自适应参数的粗糙k-means聚类算法[J]. 计算机工程与应用, 2010, 46(26): 7-10.
	ZHOU T. Adaptive rough k-means clustering algorithm[J]. Computer Engineering and Applications, 2010, 46(26): 7-10.
[6]	周杨, 苗夺谦, 岳晓冬. 基于自适应权重的粗糙K-均值聚类算法[J]. 计算机科学, 2011, 38(6): 237-241.
	ZHOU Y, MIAO D Q, YUE X D. Rough K-means clus-tering based on self-adaptive weights[J]. Computer Science, 2011, 38(6): 237-241.
[7]	李莲, 罗可, 周博翔. 基于粒计算的粗糙集聚类算法[J]. 计算机应用研究, 2013, 30(10): 2916-2919.
	LI L, LUO K, ZHOU B X. Rough clustering algorithm based on granular computing[J]. Application Research of Compu-ters, 2013, 30(10): 2916-2919.
[8]	蒋亦樟, 邓赵红, 王骏, 等. 熵加权多视角协同划分模糊聚类算法[J]. 软件学报, 2014, 25(10): 2293-2311.
	JIANG Y Z, DENG Z H, WANG J, et al. Collaborative parti-tion multi-view fuzzy clustering algorithm using entropy weig-hting[J]. Journal of Software, 2014, 25(10): 2293-2311.
[9]	PETERS G. Rough clustering utilizing the principle of in-difference[J]. Information Sciences, 2014, 277: 358-374.
[10]	孙志鹏, 钱雪忠, 吴秦, 等. 基于加权距离计算的自适应粗糙 K-均值算法[J]. 计算机应用研究, 2016, 33(7): 1987-1991.
	SUN Z P, QIAN X Z, WU Q, et al. Self-adaptive rough K-means algorithm based on weighted distance[J]. Application Research of Computers, 2016, 33(7): 1987-1991.
[11]	洪亮亮, 罗可. 改进的基于遗传算法的粗糙聚类方法[J]. 计算机工程与应用, 2010, 46(25): 142-145.
	HONG L L, LUO K. Improved rough clustering method based on genetic algorithm[J]. Computer Engineering and Applications, 2010, 46(25): 142-145.
[12]	刘洋, 王慧琴, 张小红. 结合蚁群算法的改进粗糙K均值聚类算法[J]. 数据采集与处理, 2019, 34(2): 341-348.
	LIU Y, WANG H Q, ZHANG X H. An improved rough K-means clustering algorithm combining ant colony algori-thm[J]. Journal of Data Acquisition and Processing, 2019, 34(2): 341-348.
[13]	逯瑞强, 马福民, 张腾飞. 基于区间2-型模糊度量的粗糙K-means聚类算法[J]. 模式识别与人工智能, 2018, 31(3): 265-274.
	LU R Q, MA F M, ZHANG T F. Interval type-2 fuzzy mea-sure based rough K-means clustering[J]. Pattern Recogni-tion and Artificial Intelligence, 2018, 31(3): 265-274.
[14]	YANG M S, NATALIANI Y. Robust-learning fuzzy C-means clustering algorithm with unknown number of clusters[J]. Pattern Recognition, 2017, 71: 45-59.
[15]	ZHANG X T, MA F M, CHAO X, et al. Rough fuzzy K-means clustering algorithm based on mixed metrics and cluster adap-tive adjustment[J]. Pattern Recognition and Artificial Intel-ligence, 2019, 32(12): 1141-1150.
[16]	OFEK N, ROKACH L, STERN R, et al. Fast-CBUS: a fast clustering-based undersampling method for addressing the class imbalance problem[J]. Neuro Computing, 2017, 243: 88-102.
[17]	张腾飞, 李中文, 马福民, 等. 基于类簇规模不均衡度量的粗糙模糊K-means聚类算法[J]. 信息与控制, 2020, 49(3): 281-288.
	ZHANG T F, LI Z W, MA F M, et al. Improved rough fuzzy K-means clustering based on imbalanced measure of cluster sizes[J]. Information and Control, 2020, 49(3): 281-288.
[18]	王子龙, 李进, 宋亚飞. 基于距离和权重改进的K-means算法[J]. 计算机工程与应用, 2020, 56(23): 87-94.
	WANG Z L, LI J, SONG Y F. Improved K-means algo-rithm based on distance and weight[J]. Computer Enginee-ring and Applications, 2020, 56(23): 87-94.
[19]	郭永坤, 章新友, 刘莉萍, 等. 优化初始聚类中心的K-means聚类算法[J]. 计算机工程与应用, 2020, 56(15): 172-178.
	GUO Y K, ZHANG X Y, LIU L P, et al. K-means cluste-ring algorithm of optimizing initial clustering center[J]. Com-puter Engineering and Applications, 2020, 56(15): 172-178.
[20]	KARABOGA D, BASTURK B. A comparative study of artificial bee colony algorithm[J]. Applied Mathematics and Computation, 2009, 214(1): 108-132.
[21]	WANG H, WU Z J, RAHNAMAYAN S, et al. Multi-strategy ensemble artificial bee colony algorithm[J]. Infor-mation Sciences, 2014, 279(20): 587-603.
[22]	GAO W F, HUANG L L, WANG J, et al. Enhanced artifi-cial bee colony algorithm through differential evolution[J]. Applied Soft Computing, 2016, 48: 137-150.
[23]	于佐军, 秦欢. 基于改进蜂群算法的K-means算法[J]. 控制与决策, 2018, 33(1): 181-185.
	YU Z J, QIN H. K-means algorithm based on improved arti-fificial bee colony algorithm[J]. Control and Decision, 2018, 33(1): 181-185.
[24]	CUI L Z, LI G H, ZHU Z X, et al. A novel artificial bee colony algorithm with an adaptive population size for nume-rical function optimization[J]. Information Sciences, 2017, 414: 53-67.
[25]	王学恩, 韩德强, 韩崇昭. 采用不确定性度量的粗糙模糊C均值聚类参数获取方法[J]. 西安交通大学学报, 2013, 47(6): 55-60.
	WANG X E, HAN D Q, HAN C Z. Selection method for parameters of rough fuzzy C-means clustering based on uncer-tainty measurement[J]. Journal of Xi’an Jiaotong Univer-sity, 2013, 47(6): 55-60.

数据集	对象个数	属性数	类别数
Iris	150	4	3
Wine	178	13	3
Balance-Scale	625	4	3
Segmentation-test-tes	2 310	19	7
Sonar	208	60	2

数据集	对象个数	属性数	类别数
Iris	150	4	3
Wine	178	13	3
Balance-Scale	625	4	3
Segmentation-test-tes	2 310	19	7
Sonar	208	60	2

文献	类内距离	类间距离	准确率/%	误差平方	迭代次数	运行时间/s
文献[1]	839.101	24.932	85.323	119.100	9.930	0.015
文献[11]	123.972	32.833	90.014	83.527	8.121	0.087
文献[12]	122.341	29.550	90.121	81.674	8.432	0.093
本文算法	117.934	33.671	91.030	79.126	7.300	0.097

文献	类内距离	类间距离	准确率/%	误差平方	迭代次数	运行时间/s
文献[1]	839.101	24.932	85.323	119.100	9.930	0.015
文献[11]	123.972	32.833	90.014	83.527	8.121	0.087
文献[12]	122.341	29.550	90.121	81.674	8.432	0.093
本文算法	117.934	33.671	91.030	79.126	7.300	0.097

文献	类内距离	类间距离	准确率/%	误差平方	迭代次数	运行时间/s
文献[1]	16 553.721	464.671	69.113	2.418E+6	11.131	0.141
文献[11]	15 137.514	471.131	73.672	2.641E+6	9.140	0.132
文献[12]	15 096.421	474.342	73.702	2.351E+6	9.721	0.163
本文算法	15 013.141	481.252	74.834	2.317E+6	8.301	0.172

结合人工蜂群优化的粗糙K-means聚类算法

Rough K-means Clustering Algorithm Combined with Artificial Bee Colony Optimization

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 25

相关文章 6

编辑推荐

Metrics

文献	类内距离	类间距离	准确率/%	误差平方	迭代次数	运行时间/s
文献[1]	921.334	27.373	52.260	2.371 0E+3	17.891	0.942
文献[11]	837.471	35.490	56.134	2.332 6E+3	13.170	0.771
文献[12]	823.620	36.192	57.341	2.359 0E+3	13.793	1.030
本文算法	812.142	37.942	57.792	2.322 3E+3	11.132	1.021

文献	类内距离	类间距离	准确率/%	误差平方	迭代次数	运行时间/s
文献[1]	2 767.002	97.803	54.522	1.817E+7	26.014	53.231
文献[11]	2 519.413	121.214	62.791	1.749E+7	23.772	75.745
文献[12]	2 483.165	129.672	64.237	1.313E+7	21.431	90.674
本文算法	2 402.424	137.493	69.667	1.212E+7	19.343	90.903

文献	类内距离	类间距离	准确率/%	误差平方	迭代次数	运行时间/s
文献[1]	8 602.743	234.326	55.774	1.279E+5	13.974	0.521
文献[11]	6 478.157	341.314	71.176	1.154E+5	12.332	0.614
文献[12]	5 353.849	246.425	79.334	9.590E+4	11.041	0.679
本文算法	5 002.874	251.234	83.095	9.474E+4	9.011	0.673

[1]	郭佳，马朝斌，张绍博，苗萌萌. 优化的马尔可夫链人工蜂群算法[J]. 计算机科学与探索, 2020, 14(6): 985-995.
[2]	耿璐，李艳娟. 结合JADE和CoDE差分算子的人工蜂群算法[J]. 计算机科学与探索, 2019, 13(12): 2103-2116.
[3]	黄珊，高兴宝. 具有学习及十字交叉搜索的人工蜂群算法[J]. 计算机科学与探索, 2017, 11(12): 2004-2014.
[4]	谢娟英，屈亚楠. 密度峰值优化初始中心的K-medoids聚类算法[J]. 计算机科学与探索, 2016, 10(2): 230-247.
[5]	谢娟英，高瑞. 方差优化初始中心的K-medoids聚类算法[J]. 计算机科学与探索, 2015, 9(8): 973-984.
[6]	谢娟英，鲁肖肖，屈亚楠，高红超. 粒计算优化初始聚类中心的K-medoids聚类算法[J]. 计算机科学与探索, 2015, 9(5): 611-620.