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

doi:10.16183/j.cnki.jsjtu.2021.292

Abstract

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

CLC Number:

TP301.6

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.

Figures/Tables 12

Fig.1

Fig.2

Fig.3

Tab.1

Fig.4

Fig.5

Tab.2

Tab.3

Tab.4

Fig.6

Fig.7

Tab.5

References 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