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

doi:10.6040/j.issn.1671-9352.0.2024.353

摘要/Abstract

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

关键词: 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.

Key words: K-means clustering, bat algorithm, compactness, K-means algorithm, three way decision

中图分类号:

TP391

孙清,叶军,曾广财,宋苏洋,汪一心. 结合蝙蝠算法和紧密度改进的三支K-means算法[J]. 《山东大学学报(理学版)》, 2026, 61(1): 65-75.

SUN Qing, YE Jun, ZENG Guangcai, SONG Suyang, WANG Yixin. Three-way K-means algorithm combining the bat algorithm and the improved compactness[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2026, 61(1): 65-75.

参考文献

[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. ZHANG Yonglai, ZHOU Yaojian. Review of clustering algorithms[J]. Journal of Computer Applications, 2019,39(7):1869-1882.
[3] 张雨如. 基于动态建模的层次聚类算法研究[D]. 徐州:中国矿业大学,2022. ZHANG Yuru. Research on hierarchical clustering using dynamic modeling [D]. Xuzhou: China University of Mining and Technology, 2022.
[4] 陈叶旺,申莲莲,钟才明,等. 密度峰值聚类算法综述[J]. 计算机研究与发展,2020,57(2):378-394. 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.
[5] 马福民,宫婷,杨帆,等. 基于Zipf分布的网格密度峰值聚类算法[J]. 控制与决策,2024,39(2):577-587. 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.
[6] 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.
[7] YAO Yiyu. The superiority of three way decisions in probabilistic rough set models[J]. Information Sciences, 2011, 181(6):1080-1096.
[8] 于洪,王国胤,姚一豫. 决策粗糙集理论研究现状与展望[J]. 计算机学报,2015,38(8):1628-1639. 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.
[9] YU Hong, ZHANG Cong, WANG Guoyin. Overlapping clustering method using the three-way decision theory[J]. Knowledge Based Systems, 2016, 91:189-203.
[10] 于洪,毛传凯. 基于k-means的自动三支决策聚类方法[J]. 计算机应用,2016,36(8):2061-2065. YU Hong, MAO Chuanka. Automatic three-way decision clustering algorithm based on k-means[J]. Journal of Computer Applications, 2016, 36(8):2061-2065.
[11] 解滨,董新玉,梁皓伟. 基于三支动态阈值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.
[12] 李洪梅,姜冬勤,王平心. 基于邻域样本稳定性的三支聚类方法[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.
[13] 李飞江,钱宇华,王婕婷,等. 基于样本稳定性的聚类方法[J]. 中国科学(E辑:信息科学),2020,50(8):1239-1254. 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.
[14] 李浩溥. 基于稳定性和相似性的三支聚类算法研究[D]. 哈尔滨:哈尔滨师范大学,2023. LI Haobo. Three way K-means algorithm based on sample stability and similarity[D]. Harbin: Harbin Normal University, 2023.
[15] 花遇春,赵燕,马建敏. 基于共现概率的三支聚类模型[J]. 西北大学学报(自然科学版),2022,52(5):797-804. 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.
[16] 叶廷宇,叶军,王晖,等. 结合人工蜂群优化的粗糙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.
[17] 李兆彬,叶军,周浩岩,等. 变异萤火虫优化的粗糙K-均值聚类算法[J]. 山东大学学报(工学版),2023,53(4):74-82. 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.
[18] 李兆彬,叶军,周浩岩,等. 融合变异萤火虫算法的三支聚类方法[J]. 系统仿真学报,2025,37(3):646-656. 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.
[19] 徐天杰,王平心,杨习贝. 基于人工蜂群的三支K-means聚类算法[J]. 计算机科学,2023,50(6):116-121. XU Tianjie, WANG Pingxin, YANG Xibei. Three-way K-means clustering based on artificial bee colony[J]. Computer Science, 2023, 50(6):116-121.
[20] 王梦绚,万仁霞,苗夺谦,等. 基于三支决策的蚁群聚类算法[J]. 昆明理工大学学报(自然科学版),2024,49(1):83-97. 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.
[21] 高艳龙,万仁霞,陈瑞典. 基于粒子群的三支聚类算法[J]. 福州大学学报(自然科学版),2022,50(3):301-307. 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.
[22] YANG Xinshe. A new metaheuristic bat-inspired algorithm[J]. Computer Knowledge & Technology, 2010, 284:65-74.
[23] 许德刚,赵萍. 蝙蝠算法研究及应用综述[J]. 计算机工程与应用,2019,55(15):1-12. XU Degang, ZHAO Ping. Literature survey on research and application of bat algorithm[J]. Computer Engineering and Applications, 2019, 55(15): 1-12.
[24] 倪昌浩,邹海. 基于改进蝙蝠算法的移动机器人路径规划方法研究[J]. 制造业自动化,2021,43(6):53-56,62. 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.
[25] 丁元明,侯孟珂. 改进蝙蝠算法的无人机路径规划[J]. 兵器装备工程学报,2023,44(9):26-33. DING Yuanming, HOU Mengke. UAV path planning based on improved bat algorithm[J]. Journal of Ordnance Equipment Engineering, 2023, 44(9):26-33.
[26] 张瑾,洪莉,戴二壮. 求解带容量和时间窗约束车辆路径问题的改进蝙蝠算法[J]. 计算机工程与科学,2021,43(8):1479-1487. 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.
[27] TANYILDIZI E, ÖZKAYA G. An improved golden sine algorithm for global optimization problems[J]. Applied Soft Computing, 2018, 68(3):160-175.
[28] DAVIES D L, BOULDIN D W. A cluster separation measure[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1979, 1(2):224-227.
[29] 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.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed