Three-way Decision Clustering Algorithm Fusion of Mutant Fireflies Algorithm

doi:10.16182/j.issn1004731x.joss.23-1300

Abstract

Abstract:

To address problems such as the premature phenomenon in the three-way clustering algorithm caused by the random selection of initial cluster centers and the need for repeated experiments to determine the value of q in the q-nearest neighbor concept, a three-way clustering algorithm optimized by a variant of the firefly algorithm is proposed. The firefly algorithm is employed to solve the problem of sensitivity to initial cluster centers. The target function value is taken as the brightness intensity of firefly to search the clustering center point, and the optimal solution is taken as the clustering center of the algorithm for iteration. The boundary domain attribution formula and adaptive threshold value are proposed, so that the samples in the boundary domain can be divided into the core domain as far as possible if they meet the threshold condition, avoiding the problem of too many boundary domain samples. The experimental results on the UCI datasets show that the improved algorithm significantly reduces the number of iterations, improves the accuracy of the clustering results, and verifies the stability and effectiveness of the algorithm。

Key words: clustering algorithm, K-means clustering, three-way decision clustering, firefly algorithm, mutation strategy

CLC Number:

TP391

Li Zhaobin, Ye Jun, Zhou Haoyan, Wang Yixin, Han Yuzhen. Three-way Decision Clustering Algorithm Fusion of Mutant Fireflies Algorithm[J]. Journal of System Simulation, 2025, 37(3): 646-656.

Figures/Tables 8

Fig. 1

Fig. 2

Fig. 3

Table 1

Table 2

ACC of data sets

数据集	算法1	算法2	算法3	算法4	\| $C$ _B\|
Iris	0.890	0.927	0.973	0.973	28
Wine	0.702	0.730	0.855	0.989	26
Seeds	0.891	0.959	0.959	0.976	42
Banknote	0.602	0.627	0.633	0.649	138
Spambase	0.636	0.825	0.830	0.872	932
Waveform	0.468	0.582	0.591	0.622	998

Table 2

Table 3

Fig. 4

Fig. 5

References 33

1	Hathaway R J, Bezdek J C. Switching Regression Models and Fuzzy Clustering[J]. IEEE Transactions on Fuzzy Systems, 1993, 1(3): 195-204.
2	Krishnapuram R, Keller J M. A Possibilistic Approach to Clustering[J]. IEEE Transactions on Fuzzy Systems, 1993, 1(2): 98-110.
3	Likas Aristidis, Vlassis Nikos, Verbeek Jakob J. The Global K-means Clustering Algorithm[J]. Pattern Recognition, 2003, 36(2): 451-461.
4	杨俊闯, 赵超. K-Means聚类算法研究综述[J]. 计算机工程与应用, 2019, 55(23): 7-14, 63.
	Yang Junchuang, Zhao Chao. Survey on K-means Clustering Algorithm[J]. Computer Engineering and Applications, 2019, 55(23): 7-14, 63.
5	赵杰, 雷秀娟, 吴振强. 基于最优类中心扰动的萤火虫聚类算法[J]. 计算机工程与科学, 2015, 37(2): 342-347.
	Zhao Jie, Lei Xiujuan, Wu Zhenqiang. An Improved Firefly Clustering Algorithm Based on Optimal Class-center Disturbance[J]. Computer Engineering & Science, 2015, 37(2): 342-347.
6	汤文亮, 张平, 汤树芳. 基于精英反向学习的萤火虫K-means改进算法[J]. 计算机工程与设计, 2019, 40(11): 3164-3169.
	Tang Wenliang, Zhang Ping, Tang Shufang. Improved Firefly K-means Algorithm Based on Elite Opposition-based Learning[J]. Computer Engineering and Design, 2019, 40(11): 3164-3169.
7	陈小雪, 尉永清, 任敏, 等. 基于萤火虫优化的加权K-means算法[J]. 计算机应用研究, 2018, 35(2): 466-470.
	Chen Xiaoxue, Wei Yongqing, Ren Min, et al. Weighted K-means Clustering Algorithm Based on Firefly Algorithm[J]. Application Research of Computers, 2018, 35(2): 466-470.
8	索郎王青, 杨海龙, 姚一豫. 三元思维: 三支决策理论与实践[J]. 陕西师范大学学报(自然科学版), 2022, 50(3): 7-16.
	Suo Langwangqing, Yang Hailong, Yao Yiyu. Triadic Thinking: The Theory and Practice of Three-way Decision[J]. Journal of Shaanxi Normal University(Natural Science Edition), 2022, 50(3): 7-16.
9	Yao Yiyu. The Superiority of Three-way Decisions in Probabilistic Rough Set Models[J]. Information Sciences, 2011, 181(6): 1080-1096.
10	Yao Yiyu. Three-way Decisions with Probabilistic Rough sets[J]. Information Sciences, 2010, 180(3): 341-353.
11	姚一豫, 祁建军, 魏玲. 基于三支决策的形式概念分析、粗糙集与粒计算[J]. 西北大学学报(自然科学版), 2018, 48(4): 477-487.
	Yao Yiyu, Qi Jianjun, Wei Ling. Formal Concept Analysis, Rough Set Analysis and Granular Computing Based on Three-way Decisions[J]. Journal of Northwest University(Natural Science Edition), 2018, 48(4): 477-487.
12	王国胤, 李帅, 杨洁. 知识与数据双向驱动的多粒度认知计算[J]. 西北大学学报(自然科学版), 2018, 48(4): 488-500.
	Wang Guoyin, Li Shuai, Yang Jie. A Multi-granularity Cognitive Computing Model Bidirectionally Driven by Knowledge and Data[J]. Journal of Northwest University(Natural Science Edition), 2018, 48(4): 488-500.
13	刘盾, 李天瑞, 李华雄. 粗糙集理论: 基于三支决策视角[J]. 南京大学学报(自然科学版), 2013, 49(5): 574-581.
	Liu Dun, Li Tianrui, Li Huaxiong. Rough Set Theory: A Three-way Decisions Perspective[J]. Journal of Nanjing University(Natural Science), 2013, 49(5): 574-581.
14	顾萍萍, 周献中. 基于概率语言术语集评价的三支决策方法研究[J]. 南京大学学报(自然科学版), 2020, 56(4): 505-514.
	Gu Pingping, Zhou Xianzhong. Approaches to Three⁃way Decisions Based on the Evaluation of Probabilistic Linguistic Terms Sets[J]. Journal of Nanjing University(Natural Science), 2020, 56(4): 505-514.
15	Yu Hong, Zhang Cong, Wang Guoyin. A Tree-based Incremental Overlapping Clustering Method Using the Three-way Decision Theory[J]. Knowledge-Based Systems, 2016, 91: 189-203.
16	于洪, 毛传凯. 基于K-means的自动三支决策聚类方法[J]. 计算机应用, 2016, 36(8): 2061-2065, 2091.
	Yu Hong, Mao Chuankai. Automatic Three-way Decision Clustering Algorithm Based on K-means[J]. Journal of Computer Applications, 2016, 36(8): 2061-2065, 2091.
17	陈波红, 张婷. 高维不确定数据三支决策聚类方法研究[J]. 计算机仿真, 2020, 37(12): 295-298, 370.
	Chen Bohong, Zhang Ting. Research on Three Decision Clustering Methods for High Dimensional Uncertain Data[J]. Computer Simulation, 2020, 37(12): 295-298, 370.
18	李洪梅, 姜冬勤, 王平心. 基于邻域样本稳定性的三支聚类方法[J]. 山西大学学报(自然科学版), 2020, 43(4): 874-879.
	Li Hongmei, Jiang Dongqin, Wang Pingxin. Three-way Clustering Based on Neighborhood Sample's Stability[J]. Journal of Shanxi University(Natural Science Edition), 2020, 43(4): 874-879.
19	Otsu Nobuyuki. A Threshold Selection Method from Gray-level Histograms[J]. IEEE Transactions on Systems, Man and Cybernetics, 1979, 9(1): 62-66.
20	Kumar Vijay, Kumar Dinesh. A Systematic Review on Firefly Algorithm: Past, Present, and Future[J]. Archives of Computational Methods in Engineering, 2021, 28(4): 3269-3291.
21	Cui Zhihua, Chang Yu, Zhang Jiangjiang, et al. Improved NSGA-III with Selection-and-elimination Operator[J]. Swarm and Evolutionary Computation, 2019, 49: 23-33.
22	Pan Linqiang, He Cheng, Tian Ye, et al. A Classification-based Surrogate-assisted Evolutionary Algorithm for Expensive Many-objective Optimization[J]. IEEE Transactions on Evolutionary Computation, 2019, 23(1): 74-88.
23	Cui Zhihua, Cao Yang, Cai Xingjuan, et al. Optimal LEACH Protocol with Modified Bat Algorithm for Big Data Sensing Systems in Internet of Things[J]. Journal of Parallel and Distributed Computing, 2019, 132: 217-229.
24	叶廷宇, 叶军, 王晖, 等. 结合人工蜂群优化的粗糙K-means聚类算法[J]. 计算机科学与探索, 2022, 16(8): 1923-1932.
	Ye Tingyu, Ye Jun, Wang Hui, et al. Rough K-means Clustering Algorithm Combined with Artificial Bee Colony Optimization[J]. Journal of Frontiers of Computer Science & Technology, 2022, 16(8): 1923-1932.
25	Senthilnath J, Omkar S N, Mani V. Clustering Using Firefly Algorithm: Performance Study[J]. Swarm and Evolutionary Computation, 2011, 1(3): 164-171.
26	Yao Yiyu. An Outline of a Theory of Three-way Decisions[C]//International Conference on Rough Sets and Current Trends in Computing. Berlin: Springer Berlin Heidelberg, 2012: 1-17.
27	Li Xiaonan, Wang Xuan, Sun Bingzhen, et al. Three-way Decision on Information Tables[J]. Information Sciences, 2021, 545: 25-43.
28	Yang Xinshe. Firefly Algorithms for Multimodal Optimization[C]//Stochastic Algorithms: Foundations and Applications. Berlin: Springer Berlin Heidelberg, 2009: 169-178.
29	张大力, 夏红伟, 张朝兴, 等. 改进萤火虫算法及其收敛性分析[J]. 系统工程与电子技术, 2022, 44(4): 1291-1300.
	Zhang Dali, Xia Hongwei, Zhang Zhaoxing, et al. Improved Firefly Algorithm and Its Convergence Analysis[J]. Systems Engineering and Electronics, 2022, 44(4): 1291-1300.
30	Yu Hui, Chen Luyuan, Yao Jingtao. A Three-way Density Peak Clustering Method Based on Evidence Theory[J]. Knowledge-Based Systems, 2021, 211: 106532.
31	解滨, 董新玉, 梁皓伟. 基于三支动态阈值K-means聚类的入侵检测算法[J]. 郑州大学学报(理学版), 2020, 52(2): 64-70.
	Xie Bin, Dong Xinyu, Liang Haowei. An Algorithm of Intrusion Detection Based on Three-way Dynamic Threshold K-means Clustering[J]. Journal of Zhengzhou University(Natural Science Edition), 2020, 52(2): 64-70.
32	高艳龙, 万仁霞, 陈瑞典. 基于粒子群的三支聚类算法[J]. 福州大学学报(自然科学版), 2022, 50(3): 301-307.
	Gao Yanlong, Wan Renxia, Chen Ruidian. A Three-way Clustering Algorithm Based on Particle Swarm Optimization[J]. Journal of Fuzhou University(Natural Science Edition), 2022, 50(3): 301-307.
33	Jayawardana C, Hewagamage K P, Hirakawa M. A Personalized Information Environment for Digital Libraries[J]. Information Technology & Libraries, 2001, 20(4): 185-196.

数据集	算法1	算法2	算法3	算法4
Iris	165.39	201.32	236.68	258.22
Wine	88.10	112.58	132.95	136.17
Seeds	176.56	189.24	287.46	296.76
Banknote	1 149.39	1 358.30	1 423.65	1 477.42
Spambase	1 528.75	1 754.88	1 958.76	2 013.65
Waveform	1 451.61	1 926.87	3 021.18	3 581.98

[1]	Chen Jing, Yang Guowei, Zhang Zhaochong, Wang Wei. City Regional Traffic Flow Prediction Based on Spatiotemporal Multi-view Attention Residual Network [J]. Journal of System Simulation, 2025, 37(3): 607-622.
[2]	Huang Zhiqin, Lu Tianying, Chen Zheyi. Multi-UAV Deployment and Collaborative Offloading for Large-scale IoT Systems [J]. Journal of System Simulation, 2025, 37(1): 25-39.
[3]	Zhao Jia, Lai Zhizhen, Wu Runxiu, Cui Zhihua, Wang Hui. Hierarchical Guided Enhanced Multi-objective Firefly Algorithm [J]. Journal of System Simulation, 2024, 36(5): 1152-1164.
[4]	Liu Ye, Ji Weixi, Su Xuan, Zhao Hongxuan. Research on Hybrid Solution Algorithm for Layout Problem of Rectangular Parts with Multiple Constraints [J]. Journal of System Simulation, 2024, 36(3): 743-755.
[5]	Chen Jing, Zhang Zhaochong, Wang Linkai, An Mai, Wang Wei. Short-term Bus Passenger Flow Prediction Based on Convolutional Long-short-term Memory Network [J]. Journal of System Simulation, 2024, 36(2): 476-486.
[6]	Zhou Yaqiong, Chen Junqi, Li Weishi, Qiu Sihang, Ju Rusheng. A Clustering-based Location Allocation Method for Delivery Sites under Epidemic Situations [J]. Journal of System Simulation, 2024, 36(12): 2782-2796.
[7]	Xu Wang, Weidong Ji, Guohui Zhou, Jiahui Yang. Multi-objective Optimization Algorithm Based on Multi-index Elite Individual Game Mechanism [J]. Journal of System Simulation, 2023, 35(3): 494-514.
[8]	Mingmei Li, Chenglin Wen, Shaolin Hu. A K-modes Clustering Method Based on Maximal Information Coefficient Data Preprocessing [J]. Journal of System Simulation, 2022, 34(10): 2204-2212.
[9]	Li Yuan, Geng Zewei. Fault Diagnosis of Industrial Process Based on LLE and K-means Clustering Algorithm [J]. Journal of System Simulation, 2021, 33(9): 2066-2073.
[10]	Cui Lizhen, Wang Qiaoli, Guo Qianqian, Yang Yong. Research on Fingerprint Location Algorithm Based on Dynamic Fingerprint Update [J]. Journal of System Simulation, 2021, 33(4): 818-824.
[11]	Wang Hui, Lü Xingshun. An Improved Firefly Algorithm and its Application in Washout Optimization [J]. Journal of System Simulation, 2021, 33(2): 306-314.
[12]	Li Yan, He Yigang. Parameter Matching Optimization of Pure Electric Vehicle Based on Firefly Algorithm [J]. Journal of System Simulation, 2019, 31(4): 795-801.
[13]	Xiao Di, Zhang Xiaoyong, Hu Yang. Urban Functional Area Identification Method Based on Mobile Big Data [J]. Journal of System Simulation, 2019, 31(11): 2281-2288.
[14]	Ding Jiale, Chen Guochu, Yuan Kuo. Short-term Wind Power Prediction Based on Improved Firefly Algorithm [J]. Journal of System Simulation, 2019, 31(11): 2509-2516.
[15]	Wang Yongji, Su Tingting, Liu Lei. Multi-strategy Cooperative Evolutionary PSO Based on Cauchy Mutation Strategy [J]. Journal of System Simulation, 2018, 30(8): 2875-2883.