结合蝙蝠算法和紧密度改进的三支K-means算法

Three-way K-means algorithm combining the bat algorithm and the improved compactness

摘要

本文结合蝙蝠算法和紧密度改进三支K-means算法，利用黄金分割系数和种群平均位置优化蝙蝠算法，根据优化后的蝙蝠算法搜索初始聚类中心，提高三支K-means算法的稳定性。依据紧密度判断核心域和边界域的阈值，减少边界域样本数量，提高三支K-means算法的准确性。对比实验采用９个数据集与６种聚类算法，实验结果表明本文算法提升聚类性能，验证本文算法有效性和实用性。

Abstract

The three way K-means algorithm is improved by integrating the bat algorithm with closeness degree optimization. The bat algorithm is optimized by employing the golden section coefficient and population average position. The optimized bat algorithm searches for initial cluster centers which improving the stability of the three way K-means algorithm. Additionally, the threshold for core and boundary regions is determined based on closeness degree, which reduces the number of boundary samples and enhances the accuracy of the three way K-means algorithm. Comparative experiments is conducted on nine datasets against six clustering algorithms. It is shown that the proposed method improves clustering performance and is confirming its effectiveness and practical utility.

关键词

K-means聚类 / 蝙蝠算法 / 紧密度 / K-means算法 / 三支决策

Key words

K-means clustering / bat algorithm / compactness / K-means algorithm / three way decision

参考文献

[1] SAMBASIVAM S, THEODOSOPOULOS N. Advanced data clustering methods of mining web documents[J]. Issues in Informing Science and Information Technology, 2006, 5(3): 563-579.

[2] 章永来， 周耀鉴. 聚类算法综述[J]. 计算机应用， 2019， 39(7): 1869-1882.

[3] ZHANG Yonglai, ZHOU Yaojian. Review of clustering algorithms[J]. Journal of Computer Applications, 2019, 39(7): 1869-1882.

[4] 张雨如. 基于动态建模的层次聚类算法研究[D]. 徐州: 中国矿业大学， 2022.

[5] ZHANG Yuru. Research on hierarchical clustering using dynamic modeling[D]. Xuzhou: China University of Mining and Technology, 2022.

[6] 陈叶旺， 申莲莲， 钟才明， 等. 密度峰值聚类算法综述[J]. 计算机研究与发展， 2020， 57(2): 378-394.

[7] CHEN Yewang, SHEN Lianlian, ZHONG Caiming, et al. Survey on density peak clustering algorithm[J]. Journal of Computer Research and Development, 2020, 57(2): 378-394.

[8] 马福民， 宫婷， 杨帆， 等. 基于Zipf分布的网格密度峰值聚类算法[J]. 控制与决策， 2024， 39(2): 577-587.

[9] MA Fumin, GONG Ting, YANG Fan, et al. Grid density peak clustering algorithm based on zipf distribution[J]. Control and Decision, 2024, 39(2): 577-587.

[10] YAO Yiyu, PAWAN Lingras, WANG Ruizhi, et al. Interval set cluster analysis: a reformulation[C]// Rough Sets, Fuzzy Sets, Data Mining and Granular Computing. Berlin: Springer, 2009: 398-405.

[11] YAO Yiyu. The superiority of three way decisions in probabilistic rough set models[J]. Information Sciences, 2011, 181(6): 1080-1096.

[12] 于洪， 王国胤， 姚一豫. 决策粗糙集理论研究现状与展望[J]. 计算机学报， 2015， 38(8): 1628-1639.

[13] YU Hong, WANG Guoyin, YAO Yiyu. Current research and future perspectives on decision—theoretic rough sets[J]. Chinese Journal of Computers, 2015, 38(8): 1628-1639.

[14] YU Hong, ZHANG Cong, WANG Guoyin. Overlapping clustering method using the three—way decision theory[J]. Knowledge Based Systems, 2016, 91: 189-203.

[15] 于洪， 毛传凯. 基于k—means的自动三支决策聚类方法[J]. 计算机应用， 2016， 36(8): 2061-2065.

[16] YU Hong, MAO Chuankai. Automatic three—way decision clustering algorithm based on k—means[J]. Journal of Computer Applications, 2016, 36(8): 2061-2065.

[17] 解滨， 董新玉， 梁皓伟. 基于三支动态阈值K—means聚类的入侵检测算法[J]. 郑州大学学报(理学版)， 2020， 52(2): 64-70.

[18] 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.

[19] 李洪梅， 姜冬勤， 王平心. 基于邻域样本稳定性的三支聚类方法[J]. 山西大学学报(自然科学版)， 2020， 43(4): 874-879.

[20] 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.

[21] 李飞江， 钱宇华， 王婕婷， 等. 基于样本稳定性的聚类方法[J]. 中国科学(E辑: 信息科学)， 2020， 50(8): 1239-1254.

[22] LI Feijiang, QIAN Yuhua, WANG Jieting, et al. Clustering method based on sample̓s stability[J]. Science in China (Series E: Information Sciences), 2020, 50(8): 1239-1254.

[23] 李浩溥. 基于稳定性和相似性的三支聚类算法研究[D]. 哈尔滨: 哈尔滨师范大学， 2023.

[24] LI Haobo. Three way K—means algorithm based on sample stability and similarity[D]. Harbin: Harbin Normal University, 2023.

[25] 花遇春， 赵燕， 马建敏. 基于共现概率的三支聚类模型[J]. 西北大学学报(自然科学版)， 2022， 52(5): 797-804.

[26] HUA Yuchun, ZHAO Yan, MA Jianmin. Three—way clustering model based on co—occurrence probability[J]. Journal of Northwest University (Natural Science Edition), 2022, 52(5): 797-804.

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

[28] 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.

[29] 李兆彬， 叶军， 周浩岩， 等. 变异萤火虫优化的粗糙K—均值聚类算法[J]. 山东大学学报(工学版)， 2023， 53(4): 74-82.

[30] LI Zhaobin, YE Jun, ZHOU Haoyan, et al. A rough K—means clustering algorithm optimized by mutation firefly algorithm[J]. Journal of Shandong University (Engineering Science), 2023, 53(4): 74-82.

[31] 李兆彬， 叶军， 周浩岩， 等. 融合变异萤火虫算法的三支聚类方法[J]. 系统仿真学报， 2025， 37(3): 646-656.

[32] LI Zhaobin, YE Jun, ZHOU Haoyan, et al. Three—way decision clustering algorithm fusion of mutant fireflies algorithm[J]. Journal of System Simulation, 2025, 37(3): 646-656.

[33] 徐天杰， 王平心， 杨习贝. 基于人工蜂群的三支K—means聚类算法[J]. 计算机科学， 2023， 50(6): 116-121.

[34] XU Tianjie, WANG Pingxin, YANG Xibei. Three—way K—means clustering based on artificial bee colony[J]. Computer Science, 2023, 50(6): 116-121.

[35] 王梦绚， 万仁霞， 苗夺谦， 等. 基于三支决策的蚁群聚类算法[J]. 昆明理工大学学报(自然科学版)， 2024， 49(1): 83-97.

[36] WANG Mengxun, WAN Renxia, MIAO Duoqian, et al. An ant colony clustering algorithm based on three way decision[J]. Journal of Kunming University of Science and Technology (Natural Science), 2024, 49(1): 83-97.

[37] 高艳龙， 万仁霞， 陈瑞典. 基于粒子群的三支聚类算法[J]. 福州大学学报(自然科学版)， 2022， 50(3): 301-307.

[38] GAO Yanlong, WANG 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.

[39] YANG Xin—she. A new metaheuristic bat—inspired algorithm[J]. Computer Knowledge & Technology, 2010, 284: 65-74.

[40] 许德刚， 赵萍. 蝙蝠算法研究及应用综述[J]. 计算机工程与应用， 2019， 55(15): 1-12.

[41] XU Degang, ZHAO Ping. Literature survey on research and application of bat algorithm[J]. Computer Engineering and Applications, 2019, 55(15): 1-12.

[42] 倪昌浩， 邹海. 基于改进蝙蝠算法的移动机器人路径规划方法研究[J]. 制造业自动化， 2021， 43(6): 53—56, 62.

[43] NI Changhao, ZOU Hai. Research on path planning method of mobile robot based on improved bat algorithm[J]. Manufacturing Automation, 2021, 43(6): 53—56, 62.

[44] 丁元明， 侯孟珂. 改进蝙蝠算法的无人机路径规划[J]. 兵器装备工程学报， 2023， 44(9): 26-33.

[45] DING Yuanming, HOU Mengke. UAV path planning based on improved bat algorithm[J]. Journal of Ordnance Equipment Engineering, 2023, 44(9): 26-33.

[46] 张瑾， 洪莉， 戴二壮. 求解带容量和时间窗约束车辆路径问题的改进蝙蝠算法[J]. 计算机工程与科学， 2021， 43(8): 1479-1487.

[47] ZHANG Jin, HONG Li, DAI Erzhuang. An improved bat algorithm for the vehicle routing problem with time windows and capacity constraints[J]. Computer Engineering & Science, 2021, 43(8): 1479-1487.

[48] TAN YILDIZ I E, ÖZKAYA G. An improved golden sine algorithm for global optimization problems[J]. Applied Soft Computing, 2018, 68(3): 160-175.

[49] DAVIES D L, BOULDIN D W. A cluster separation measure[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1979, 1(2): 224-227.

[50] ROUSSEEUW P J. Silhouettes: a graphical aid to the interpretation and validation of cluster analysis[J]. Journal of Computational and Applied Mathematics, 1987, 20(7): 53-65.

基金资助

江西省教育厅科技基金资助项目(GJJ211920)

国家自然科学基金资助项目(62566041)