基于记忆传递旗鱼优化的K均值混合迭代聚类

doi:10.16183/j.cnki.jsjtu.2021.292

上海交通大学学报 ›› 2022, Vol. 56 ›› Issue (12): 1638-1648.doi: 10.16183/j.cnki.jsjtu.2021.292

所属专题：《上海交通大学学报》2022年“电子信息与电气工程”专题

基于记忆传递旗鱼优化的K均值混合迭代聚类

黄鹤^a^,^b, 熊武^a^,^b, 吴琨^a^,^b, 王会峰^b, 茹锋^a^,^b, 王珺^a()

a.长安大学西安市智慧高速公路信息融合与控制重点实验室, 西安 710064
b.长安大学电子与控制工程学院, 西安 710064

收稿日期:2021-08-05 出版日期:2022-12-28 发布日期:2023-01-05
通讯作者: 王珺 E-mail:jwang@nwu.edu.cn.
作者简介:黄鹤(1979-),男,河南省南阳市人,教授,博士生导师,主要从事信息融合、图像处理等研究.
基金资助:
国家重点研发计划(2018YFB1600600);陕西省重点研发计划(2021SF-483);陕西省自然科学基础研究计划(2021JM-184);长安大学中央高校基本科研业务费专项资金项目(300102329401);长安大学中央高校基本科研业务费专项资金项目(300102329501);西安市智慧高速公路信息融合与控制重点实验室(长安大学)开放基金项目(300102321502)

K-means Hybrid Iterative Clustering Based on Memory Transfer Sailfish Optimization

HUANG He^a^,^b, XIONG Wu^a^,^b, WU Kun^a^,^b, WANG Huifeng^b, RU Feng^a^,^b, WANG Jun^a()

b. Xi’an Key Laboratory of Intelligent Expressway Information Fusion and Control, Chang’an University, Xi’an 710064, China
b. School of Electronics and Control Engineering, Chang’an University, Xi’an 710064, China

Received:2021-08-05 Online:2022-12-28 Published:2023-01-05
Contact: WANG Jun E-mail:jwang@nwu.edu.cn.

摘要/Abstract

摘要：

针对现有K均值聚类(KMC)算法受初始化影响较大,随机产生的聚类中心极易使聚类结果陷入局部最优而停止迭代,导致聚类精度低、鲁棒性差的问题,提出一种基于记忆传递旗鱼优化的K均值混合迭代聚类(MTSFO-HIKMC)算法.首先,借鉴已有改进思路,引入最大最小距离积来初始化KMC聚类中心,避免随机初始化带来的不确定性;同时,在迭代过程中,令当前最优解在局部进行自适应记忆传递修正,解决由于旗鱼算法搜索路径单一带来的全局寻优能力差和搜索精度不足的问题.利用Iris、Seeds、CMC和Wine国际标准数据集对MTSFO-HIKMC、旗鱼优化的K均值混合迭代聚类 (SFO-KMC)算法、引入改进飞蛾扑火的K均值交叉迭代聚类(IMFO-KMC)算法、KMC算法和模糊C均值(FCM)算法进行比较测试,从得到的收敛曲线和性能指标可知,所提出的MTSFO-HIKMC算法相较于IMFO-KMC算法具有更快的收敛速度;在高维度空间较IMFO-KMC算法具有更高的搜索精度;相较于KMC和FCM算法具有更高的搜索精度;相比SFO-KMC算法在收敛速度和搜索精度方面都有明显提升,在高维数据集方面尤其明显.

关键词: 旗鱼算法, 自适应记忆传递修正策略, K均值聚类, 最大最小距离积法, UCI标准数据集

Abstract:

Aimed at the problem that the existing K-means clustering (KMC) algorithm is greatly affected by initialization, and the randomly generated clustering center can easily make the clustering result fall into local optimum and stop iterating, resulting in low clustering accuracy and poor robustness, a K-means hybrid iterative clustering algorithm based on memory transfer sailfish optimization (MTSFO-HIKMC) is proposed. First, learning from the existing improvement ideas, the maximum and minimum distance product is introduced to initialize the KMC cluster center, to avoid the uncertainty caused by random initialization. At the same time, in the iterative process, the current optimal solution is made to locally perform adaptive memory transfer correction to solve the problem of poor global optimization ability and insufficient search accuracy caused by the single search path of the sailfish algorithm. Using the Iris, Seeds, CMC and Wine international standard data sets, the MTSFO-HIKMC, the sailfish optimized K-means hybrid iterative clustering (SFO-KMC) algorithm, the introduction of the improved Moth-to-fire K-means cross iterative clustering (IMFO-KMC) algorithm, the KMC algorithm, and the fuzzy C-means (FCM) algorithm are compared and tested. From the obtained convergence curves and performance indicators, it can be seen that the MTSFO-HIKMC algorithm proposed in this paper has a faster convergence speed than IMFO-KMC. Compared with the IMFO-KMC algorithm, the dimensional space has a higher search accuracy. Compared with the KMC algorithm and FCM, it has a higher search accuracy. Compared with the SFO-KMC algorithm, its convergence speed and search accuracy are significantly improved, especially in high-dimensional data sets.

Key words: sailfish algorithm, adaptive memory transfer correction strategy, K-means clustering (KMC), maximum and minimum distance product, UCI standard data set

中图分类号:

TP301.6

黄鹤, 熊武, 吴琨, 王会峰, 茹锋, 王珺. 基于记忆传递旗鱼优化的K均值混合迭代聚类[J]. 上海交通大学学报, 2022, 56(12): 1638-1648.

HUANG He, XIONG Wu, WU Kun, WANG Huifeng, RU Feng, WANG Jun. K-means Hybrid Iterative Clustering Based on Memory Transfer Sailfish Optimization[J]. Journal of Shanghai Jiao Tong University, 2022, 56(12): 1638-1648.

图/表 12

图1

图2

图3

表1

图4

图5

表2

表3

表4

图6

图7

表5

参考文献 20

[1]	杨恺, 黄树成. 融合K-means和RBF神经网络的汉字识别算法[J]. 计算机与数字工程, 2021, 49(7): 1286-1289.
	YANG Kai, HUANG Shucheng. Chinese character recognition algorithm based on K-means and RBF neural network[J]. Computer & Digital Engineering, 2021, 49(7): 1286-1289.
[2]	GUO Z Z, SHI Y, HUANG F M, et al. Landslide susceptibility zonation method based on C5.0 decision tree and K-means cluster algorithms to improve the efficiency of risk management[J]. Geoscience Frontiers, 2021, 12(6): 101249. doi: 10.1016/j.gsf.2021.101249 URL
[3]	陈湘中, 万烂军, 李泓洋, 等. 基于蚁群优化K均值聚类算法的滚轴故障预测[J]. 计算机工程与设计, 2020, 41(11): 3218-3223.
	CHEN Xiangzhong, WAN Lanjun, LI Hongyang, et al. Rolling bearing fault prediction based on ant colony optimization K-Means clustering algorithm[J]. Computer Engineering and Design, 2020, 41(11): 3218-3223.
[4]	马健. 基于改进的K-means算法初始化方法研究[J]. 云南民族大学学报(自然科学版), 2020, 29(3): 274-278.
	MA Jian. An initialization method based on an improved K-means algorithm[J]. Journal of Yunnan Minzu University (Natural Sciences Edition), 2020, 29(3): 274-278.
[5]	王述红, 朱宝强, 王鹏宇. 模拟退火聚类算法在结构面产状分组中的应用[J]. 东北大学学报(自然科学版), 2020, 41(9): 1328-1333.
	WANG Shuhong, ZHU Baoqiang, WANG Pengyu. Application of simulated annealing clustering algorithm in grouping of discontinuity orientation[J]. Journal of Northeastern University (Natural Science), 2020, 41(9): 1328-1333.
[6]	李勇, 赵杰. 一种用于彩色图像分割的GA-K-Means方法[J]. 科学技术与工程, 2020, 20(32): 13309-13316.
	LI Yong, ZHAO Jie. A method based on GA-K-means for segmentation to color image[J]. Science Technology and Engineering, 2020, 20(32): 13309-13316.
[7]	黄鹤, 李昕芮, 吴琨, 等. 引入改进飞蛾扑火的K均值交叉迭代聚类算法[J]. 西安交通大学学报, 2020, 54(9): 32-39.
	HUANG He, LI Xinrui, WU Kun, et al. Hybrid ite-rative K-means clustering with improved moth-flame optimization[J]. Journal of Xi’an Jiaotong University, 2020, 54(9): 32-39.
[8]	HADI M S, ALI S K, FADZILAN M F, et al. Modelling of flexible beam based on ant colony optimization and cuckoo search algorithms[J]. Journal of Vibroengineering, 2021, 23(4): 810-822. doi: 10.21595/jve.2020.21730 URL
[9]	SHADRAVAN S, NAJI H R, BARDSIRI V K. The Sailfish Optimizer: A novel nature-inspired metaheuristic algorithm for solving constrained engineering optimization problems[J]. Engineering Applications of Artificial Intelligence, 2019, 80: 20-34. doi: 10.1016/j.engappai.2019.01.001 URL
[10]	SINGH P, PRAKASH S. Optical network unit placement in Fiber-Wireless (FiWi) access network by Moth-Flame optimization algorithm[J]. Optical Fiber Technology, 2017, 36: 403-411. doi: 10.1016/j.yofte.2017.05.018 URL
[11]	刘振宇, 宋晓莹. 一种可用于分类型属性数据的多变量决策树算法[J]. 东北大学学报(自然科学版), 2020, 41(11): 1521-1527.
	LIU Zhenyu, SONG Xiaoying. An applicable multivariate decision tree algorithm for categorical attribute data[J]. Journal of Northeastern University (Natural Science), 2020, 41(11): 1521-1527.
[12]	李伟琨, 阙波, 王万良, 等. 基于多目标飞蛾算法的电力系统无功优化研究[J]. 计算机科学, 2017, 44 (Sup.2): 503-509.
	LI Weikun, QUE Bo, WANG Wanliang, et al. Multi-objective moth-flame optimization algorithm based optimal reactive power dispatch for power system[J]. Computer Science, 2017, 44 (Sup.2): 503-509.
[13]	李建美, 高兴宝. 基于自适应变异的混沌粒子群优化算法[J]. 计算机工程与应用, 2016, 52(10): 44-49.
	LI Jianmei, GAO Xingbao. Chaotic particle swarm optimization algorithm with adaptive mutation[J]. Computer Engineering and Applications, 2016, 52(10): 44-49.
[14]	张滨丽, 卞兴超. 改进蚁群优化算法的最优物流配送路径设计[J]. 现代电子技术, 2020, 43(9): 105-108.
	ZHANG Binli, BIAN Xingchao. An optimal logistics distribution path design based on improved ant colony optimization[J]. Modern Electronics Technique, 2020, 43(9): 105-108.
[15]	NIU L D, XIONG L R. Optimisation and application research of ant colony algorithm in vehicle routing problem[J]. International Journal of Computing Science and Mathematics, 2021, 13(2): 177. doi: 10.1504/IJCSM.2021.114177 URL
[16]	TIAN H. Research on robot optimal path planning method based on improved ant colony algorithm[J]. International Journal of Computing Science and Mathematics, 2021, 13(1): 80-92. doi: 10.1504/IJCSM.2021.114182 URL
[17]	张保东, 张亚楠, 郭黎明, 等. 基于交叉算子和非均匀变异算子的飞蛾扑火优化算法[J]. 计算机与数字工程, 2020, 48(11): 2622-2627.
	ZHANG Baodong, ZHANG Yanan, GUO Liming, et al. Moth-flame optimization algorithm based on crossover operator and non-uniform mutation operator[J]. Computer & Digital Engineering, 2020, 48(11): 2622-2627.
[18]	YU J, YOU X M, LIU S. Dynamic reproductive ant colony algorithm based on piecewise clustering[J]. Applied Intelligence, 2021, 51(12): 8680-8700. doi: 10.1007/s10489-021-02312-7 URL
[19]	ZOU P, RAJORA M, LIANG S Y. Multimodal optimization of permutation flow-shop scheduling problems using a clustering-genetic-algorithm-based approach[J]. Applied Sciences, 2021, 11(8): 3388. doi: 10.3390/app11083388 URL
[20]	LIU S L, ZHANG Z Q, GUAN C, et al. An improved fireworks algorithm for the constrained single-row facility layout problem[J]. International Journal of Production Research, 2021, 59(8): 2309-2327. doi: 10.1080/00207543.2020.1730465 URL

数据集	n	d	k	3类样本数
Iris	150	4	3	(50, 50, 50)
Seeds	210	7	3	(70, 70, 70)
CMC	1473	9	3	(629, 333, 511)
Wine	178	13	3	(59, 71, 48)

数据集	算法	适应度
Iris	IMFO-KMC	96.4719
	K-means++	97.3617
	FCM	97.3580
	MTSFO-HIKMC	96.4351
Seeds	IMFO-KMC	312.0161
	K-means++	313.3064
	FCM	313.7096
	MTSFO-HIKMC	311.9355
CMC	IMFO-KMC	5532.8767
	K-means++	5545.7534
	FCM	5542.1917
	MTSFO-HIKMC	5532.6027
Wine	IMFO-KMC	16448.5294
	K-means++	16941.1765
	FCM	16566.1765
	MTSFO-HIKMC	16419.1177

数据集	算法	Acc	ARI	NMI
Iris	IMFO-KMC	0.894 3	0.743 7	0.763 6
	K-means++	0.885 2	0.721 8	0.716 3
	FCM	0.893 1	0.729 6	0.759 8
	MTSFO-HIKMC	0.894 3	0.732 5	0.755 9
Seeds	IMFO-KMC	0.895 4	0.716 5	0.703 3
	K-means++	0.892 4	0.712 9	0.693 1
	FCM	0.894 3	0.714 6	0.694 2
	MTSFO-HIKMC	0.895 2	0.716 6	0.694 9
CMC	IMFO-KMC	0.712 3	0.371 2	0.425 5
	K-means++	0.566 3	0.365 1	0.418 1
	FCM	0.700 2	0.368 7	0.420 0
	MTSFO-HIKMC	0.707 9	0.371 5	0.420 6
Wine	IMFO-KMC	0.707 9	0.371 5	0.419 3
	K-means++	0.651 8	0.349 2	0.403 1
	FCM	0.696 6	0.360 2	0.405 2
	MTSFO-HIKMC	0.709 1	0.361 2	0.410 5

数据集	算法	单次迭代时间/s
Iris	IMFO-KMC	0.035 1
	K-means++	0.004 2
	FCM	0.005 5
	MTSFO-HIKMC	0.032 9
Seeds	IMFO-KMC	0.170 9
	K-means++	0.006 4
	FCM	0.007 8
	MTSFO-HIKMC	0.164 7
CMC	IMFO-KMC	0.281 3
	K-means++	0.035 1
	FCM	0.062 7
	MTSFO-HIKMC	0.259 3
Wine	IMFO-KMC	0.033 5
	K-means++	0.004 5
	FCM	0.009 7
	MTSFO-HIKMC	0.031 9

序号	测试函数	精度
1	Sphere	5.358×10^-7
2	Ackley	1.493×10^-6
3	Three-hump Camel	2.812×10^-7
4	Levy	6.815×10^-6
5	Bukin	8.763×10^-8

基于记忆传递旗鱼优化的K均值混合迭代聚类

K-means Hybrid Iterative Clustering Based on Memory Transfer Sailfish Optimization

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 20

相关文章 3

编辑推荐

Metrics

本文评价

[1]	李翠明, 王宁, 张晨. 基于改进遗传算法的光伏板清洁分级任务规划[J]. 上海交通大学学报, 2021, 55(9): 1169-1174.
[2]	麦家骥，陈峰. 基于循环取料的不确定越库调度模型与算法 [J]. 上海交通大学学报（自然版）, 2011, 45(02): 159-0163.
[3]	白杰，杨根科，潘常春，孙凯. 基于改进分散搜索算法的无人机路径规划 [J]. 上海交通大学学报（自然版）, 2011, 45(02): 173-0178.