Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)  2023, Vol. 57 Issue (11): 2147-2159    DOI: 10.3785/j.issn.1008-973X.2023.11.002
计算机技术     
基于疯狂捕猎秃鹰算法的K均值互补迭代聚类优化
黄鹤1,2(),温夏露1,2,杨澜1,*(),王会峰1,2,高涛1,茹锋1,2
1. 长安大学 电子与控制工程学院，陕西 西安 710064
2. 西安市智慧高速公路信息融合与控制重点实验室，陕西 西安 710064
K-means complementary iterative clustering optimization based on crazy-hunting bald eagle search algorithm
He HUANG1,2(),Xia-lu WEN1,2,Lan YANG1,*(),Hui-feng WANG1,2,Tao GAO1,Feng RU1,2
1. School of Electronic and Control Engineering, Chang’an University, Xi’an 710064, China
2. Xi’an Key Laboratory of Intelligent Expressway Information Fusion and Control, Xi’an 710064, China
 全文: PDF(2119 KB)   HTML
摘要：

在处理庞大复杂的点云数据时，传统聚类方法精度低、耗时长并且受离群点影响大，针对以上问题，提出基于疯狂捕猎的柯西反向秃鹰搜索算法(QO-BESCH)的K均值互补迭代聚类优化方法. 所提算法构建基于体元包围盒的初始聚类中心选择模型，提升初始化聚类中心质量；提出疯狂捕猎机制，同时融合动态自适应控制算子和柯西反向策略，提升秃鹰搜索算法 (BES)的寻优能力，增加寻找聚类中心的成功率；利用QO-BESCH优化K均值聚类(KMC)，在减小迭代次数的同时增加搜索效率，得到较好的聚类结果. 利用UCI标准数据集对所提算法进行测试，并与8种聚类算法进行对比，实验结果证明了所提算法的优越性. 将本研究算法结合PCL点云库应用于ModelNet40点云数据集聚类，结果表明，所提算法可以实现有效聚类，适用性较强.
关键词： K均值聚类(KMC);  体元密度;  秃鹰搜索（BES）算法;  点云聚类;  部件分割    
Abstract:

A K-means complementary iterative clustering method optimized by quasi-oppositional bald eagle search base on crazy-hunting（QO-BESCH）was proposed, in order to solve the problems of low precision, long time and large influence of outliers in the process of processing large and complex point cloud data by traditional clustering methods. Firstly, the initial clustering center selection model based on volume cell bounding box was constructed to improve the quality of initial clustering center. Secondly, a crazy hunting mechanism was proposed, which combined dynamic adaptive control operators and quasi-oppositional strategy, significantly improved the searching ability of bald eagle search (BES) algorithm, and increased the success rate of searching clustering center. Finally, the K-means clustering (KMC) was optimized by using QO-BESCH to reduce the number of iterations and increase the search efficiency, and better clustering results were obtained. The proposed algorithm was tested by using UCI standard data set and compared with eight clustering algorithms. The experimental results show the effectiveness and superiority of the proposed algorithm. Further, the proposed algorithm was applied in combination with PCL point cloud library to cluster ModelNet40 point cloud dataset. Results show that the proposed algorithm can realize effective clustering and has strong applicability.
Key words: K-means clustering (KMC)    voxel density    bald eagle search (BES) algorithm    point cloud clustering    component segmentation
收稿日期: 2022-11-28 出版日期: 2023-12-11
CLC:  U 666.1  
基金资助: 国家重点研发计划资助项目（2021YFB2501200）；国家自然科学基金资助项目（52172324，52172379）；陕西省重点研发计划资助项目(2021SF-483)；陕西省博士后科研资助项目（2018BSHYDZZ64）；西安市智慧高速公路信息融合与控制重点实验室(长安大学)开放基金资助项目(300102323502)；中央高校基本科研业务费资助项目（300102323501）
通讯作者: 杨澜     E-mail: huanghe@chd.edu.cn;lanyang@chd.edu.cn
作者简介: 黄鹤（1979—），男，教授，博导，从事无人机测控，信息融合研究. orcid.org/0000-0002-7149-0460. E-mail： huanghe@chd.edu.cn
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章　　
黄鹤
温夏露
杨澜
王会峰
高涛
茹锋

引用本文:

黄鹤,温夏露,杨澜,王会峰,高涛,茹锋. 基于疯狂捕猎秃鹰算法的K均值互补迭代聚类优化[J]. 浙江大学学报(工学版), 2023, 57(11): 2147-2159.

He HUANG,Xia-lu WEN,Lan YANG,Hui-feng WANG,Tao GAO,Feng RU. K-means complementary iterative clustering optimization based on crazy-hunting bald eagle search algorithm. Journal of ZheJiang University (Engineering Science), 2023, 57(11): 2147-2159.

链接本文:

https://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2023.11.002    或    https://www.zjujournals.com/eng/CN/Y2023/V57/I11/2147

图 1  点云模型初始化聚类结果
图 2  逃逸因子变化曲线
图 3  QO-BESCH算法流程图
函数 表达式 取值范围
Sphere $ f(x) = \displaystyle \sum\nolimits_{i = 1}^n {x_i^2} $ [?100,100]n
Schwefel 2.22 $ f(x) = \displaystyle \sum\nolimits_{i = 1}^n {\left| {{x_i}} \right|} +\prod\nolimits_{i = 1}^n {\left| {{x_i}} \right|} $ ${ {{[ - 10,10]} }^{{n} } }$
Schwefel 1.2 $ f(x) = {\displaystyle \sum\nolimits_{i = 1}^n {\left( {\displaystyle \sum\nolimits_{j = 1}^i {{x_j}} } \right)} ^2} $ [?100,100]n
Rastrigin $f(x) = \displaystyle \sum\nolimits_{i = 1}^{{n} } { { {\left( {x_i^2 - 10\cos \,\, \left( {2\text{π} {x_i} } \right)+10} \right)}^2} }$ [?5.12,5.12]n
Ackley $\begin{gathered} f(x) = - 20\exp \,\, \left( { - 0.2\sqrt {\dfrac{1}{n}\displaystyle \sum\nolimits_{i = 1}^n {x_i^2} } } \right) - \\\exp \,\, \left( {\dfrac{1}{n}\displaystyle \sum\nolimits_{i = 1}^n {\cos \,\, 2\text{π} {x_i} } } \right)+20+{\rm{e}} \end{gathered}$ [?32,32]n
Griewank $\begin{gathered} f(x) = \dfrac{1}{ {4\;000} }\displaystyle \sum\nolimits_{i = 1}^n { {\left( { {x_i} - 100} \right)}^2} - \\\prod\nolimits_{i = 1}^n {\cos \,\, \left( {\dfrac{ { {x_i} - 100} }{ {\sqrt i } } } \right)} +1 \end{gathered}$ ${ { {[ - 600,600]} }^{{n} } }$
表 1  功能测试函数
图 4  测试函数三维空间和适应度曲线
函数 算法 Mean Std
F1 MFO 3.025×103 4.308×103
POA 4.54×10?20 1.033×10?19
GWO 5.42×10?5 1.23×10?4
BES 8.77×10?1 1.993 953
MHHO 4.90×10?79 1.114×10?78
本研究算法 4.36×10?89 9.918×10?89
F2 MFO 5.98×10?10 1.360
POA 1.81×10?1 4.08×10?1
GWO 1.41×10?28 3.197×10?28
BES 4.96×10?1 3.227×10?1
MHHO 1.31×101 1.908 5
本研究算法 3.72×10?40 8.449×10?40
F3 MFO 2.148×103 1.3511×104
POA 2.30×10?19 5.23×10?19
GWO 1.19×101 2.55×101
BES 1.15×103 8.496×102
MHHO 3.74×10?76 8.51×10?76
本研究算法 9.28×10?112 2.1×10?111
F9 MFO 1.699×102 4.73×101
POA 0.00 0.00
GWO 9.12 1.2×101
BES 1.67×102 3.7×101
MHHO 0.00 0.00
本研究算法 0.00 0.00
F10 MFO 3.15×10?6 1.95×101
POA 1.25×10?1 1.27×10?1
GWO 2.51×10?9 3.82×10?9
BES 1.58 1.620
MHHO 0.00 0.00
本研究算法 0.00 0.00
F11 MFO 1.420 1.813
POA 4.59×10?2 9.375×10?2
GWO 2.67×10?10 6.08×10?10
BES 0.00 0.00
MHHO ?5.69×10?12 0.00
本研究算法 0.00 0.00
表 2  各算法在测试函数上的均值和标准差性能对比
算法 测试函数
F1 F2 F3 F9 F10 F11
MFO ? ? ? ? ? ?
POA ? ? ? ? ? ?
GWO ? ? ? ? ? ?
BES ? ? ? ? ? =
MHHO ? ? ? = = +
表 3  5种算法的Wilcoxon秩和检验
图 5  QO-BESCH-KMC算法流程图
数据集 Sam dim K sam
Aggregation 788 2 7 170、34、273、102、
130、45、34
Iris 150 4 3 50、50、50
Cancer 683 9 2 444、239
Vowel 871 3 6 72、89、172、
151、207、180
表 4  UCI标准数据集特征
图 6  各聚类算法在不同数据集上的适应度变化曲线
数据集 算法 ACC/% rand_index/% ARI/%
Aggregation KMC 90.86 92.50 76.32
IMFO-KMC 90.99 91.28 72.31
TSO-KMC 90.99 91.28 72.31
BES-KMC 90.36 93.13 78.43
SSA-KMC 87.94 92.45 76.20
DHSSA-KMC 90.36 93.74 82.71
DBSCAN 69.80 91.74 63.79
FCM 79.18 92.73 72.43
本研究算法 91.11 94.43 80.61
Iris KMC 90.00 77.24 40.88
IMFO-KMC 90.67 77.67 42.00
TSO-KMC 90.37 77.34 41.11
BES-KMC 91.33 80.63 52.86
SSA-KMC 90.33 80.30 51.72
DHSSA-KMC 91.20 80.44 52.68
DBSCAN 89.33 77.97 43.02
FCM 68.00 77.66 46.38
本研究算法 92.67 81.61 53.11
Cancer KMC 96.78 85.72 71.72
IMFO-KMC 95.22 85.82 71.93
TSO-KMC 95.90 82.12 65.00
BES-KMC 96.49 85.36 71.01
SSA-KMC 96.34 85.13 70.54
DHSSA-KMC 96.63 85.58 71.44
DBSCAN 94.06 82.39 62.65
FCM 75.26 63.67 53.63
本研究算法 96.90 85.32 71.96
Vowel KMC 59.70 80.47 34.56
IMFO-KMC 60.05 81.58 33.93
TSO-KMC 62.34 81.97 31.89
BES-KMC 57.75 78.24 30.29
SSA-KMC 55.68 77.78 28.64
DHSSA-KMC 56.95 78.20 29.63
DBSCAN 58.44 80.16 32.26
FCM 56.75 72.87 30.11
本研究算法 60.28 82.23 35.60
表 5  各算法对4个数据集的评价指标
图 7  初始化方法消融实验
图 8  改进策略消融实验
图 9  本研究算法与KMC算法各评价指标对比
模型 nb na
airplane 10000 1435
bathtub 10000 3271
bottle 10000 1560
bowl 10000 5865
chair 10000 752
curtain 10000 1216
lamp 10000 1921
flower_pot 10000 2517
desk 10000 1990
表 6  体素滤波器滤波结果
图 10  不同点云模型滤波效果
模型 算法 Scat Dens tc/s 模型 算法 Scat Dens tc/s 模型 算法 Scat Dens tc/s
Airplane KMC 0.271 4 164 2.62 bowl KMC 0.271 4 164 2.62 lamp KMC 0.813 7 373 2.99
BES-KMC 0.263 3 161 4.74 BES-KMC 0.263 3 161 4.74 BES-KMC 0.329 4 317 4.01
DBSCAN 0.271 2 219 2.56 DBSCAN 0.271 2 219 2.60 DBSCAN 0.322 5 577 2.46
FCM 0.265 2 202 4.45 FCM 0.265 2 202 4.45 FCM 0.852 2 544 3.99
本研究算法 0.206 3 124 4.80 本研究算法 0.206 3 124 4.80 本研究算法 0.264 2 283 4.02
bathtub KMC 0.518 2 321 2.98 chair KMC 0.412 7 116 1.30 flower_pot KMC 0.171 4 212 3.33
BES-KMC 0.544 2 310 4.01 BES-KMC 0.410 5 122 2.40 BES-KMC 0.166 6 199 5.37
DBSCAN 0.517 7 344 2.65 DBSCAN 0.410 2 129 0.93 DBSCAN 0.167 0 103 2.83
FCM 0.560 3 425 3.92 FCM 0.461 7 163 2.27 FCM 0.165 6 206 5.29
本研究算法 0.517 7 309 4.14 本研究算法 0.388 9 106 2.63 本研究算法 0.169 8 215 5.42
bottle KMC 0.293 6 222 2.62 curtain KMC 0.771 8 314 2.38 desk KMC 0.1960 190 2.55
BES-KMC 0.269 6 156 4.84 BES-KMC 0.7680 367 4.45 BES-KMC 0.1860 165 4.56
DBSCAN 0.293 6 134 2.42 DBSCAN 0.7680 324 2.38 DBSCAN 0.1860 165 2.42
FCM 0.253 5 166 4.74 FCM 0.790 6 524 4.40 FCM 0.182 8 212 4.48
本研究算法 0.263 6 141 4.86 本研究算法 0.756 4 312 4.61 本研究算法 0.144 4 114 4.58
表 7  不同算法对9个点云模型聚类的评价指标
图 11  本研究算法在不同数据集上的聚类分割效果
1 赵佳琦, 周勇, 何欣, 等 基于深度学习的点云分割研究进展分析[J]. 电子与信息学报, 2022, 44 (12): 4426- 4440
ZHAO Jia-qi, ZHOU Yong, HE Xin, et al Analysis on the progress of point cloud segmentation based on deep learning[J]. Journal of Electronics and Information, 2022, 44 (12): 4426- 4440
doi: 10.11999/JEIT210972
2 王子洋, 李琼琼, 张子蕴, 等 应用于无人驾驶车辆的点云聚类算法研究进展[J]. 世界科技研究与发展, 2021, 43 (3): 274- 285
WANG Zi-yang, LI Qiong-qiong, ZHANG Zi-yun, et al Research progress of point cloud clustering algorithm applied to driverless vehicles[J]. World Science and Technology Research and Development, 2021, 43 (3): 274- 285
doi: 10.16507/j.issn.1006-6055.2020.12.025
3 CHENG F, NIU G F, ZHANG Z Z, et al Improved CNN-based indoor localization by using RGB images and DBSCAN algorithm[J]. Sensors, 2022, 22 (23): 9531
doi: 10.3390/s22239531
4 SHI Y Q Application of FCM clustering algorithm in digital library management system[J]. Electronics, 2022, 11 (23): 3916
doi: 10.3390/electronics11233916
5 鲁斌, 范晓明 基于改进自适应k均值聚类的三维点云骨架提取的研究[J]. 自动化学报, 2022, 48 (8): 1994- 2006
LU Bin, FAN Xiao-ming Research on 3D point cloud skeleton extraction based on improved adaptive k-means clustering[J]. Acta Automatica Sinica, 2022, 48 (8): 1994- 2006
doi: 10.16383/j.aas.c200284
6 黄鹤, 李潇磊, 杨澜, 等 引入改进蝠鲼觅食优化算法的水下无人航行器三维路径规划[J]. 西安交通大学学报, 2022, 56 (7): 9- 18
HUANG He, LI Xiao-lei, YANG Lan, et al Underwater UAV 3D path planning with improved manta ray foraging optimization algorithm[J]. Journal of Xi'an Jiaotong University, 2022, 56 (7): 9- 18
7 黄鹤, 李昕芮, 吴琨, 等 引入改进飞蛾扑火的K均值交叉迭代聚类算法[J]. 西安交通大学学报, 2020, 54 (9): 32- 39
HUANG He, LI Xin-rui, WU Kun, et al Introducing an improved K-means cross iterative clustering algorithm[J]. Journal of Xi'an Jiaotong University, 2020, 54 (9): 32- 39
doi: 10.7652/xjtuxb202009003
8 WAN Y L, XIONG Q, QIU Z W, et al K-means clustering algorithm based on memristive chaotic system and sparrow search algorithm[J]. Symmetry, 2022, 14 (10): 2029
doi: 10.3390/sym14102029
9 ALSATTAR H A, ZAIDAN A A, ZAIDAN B B Novel meta-heuristic bald eagle search optimisation algorithm[J]. Artificial Intelligence Review: An International Science and Engineering Journal, 2020, 53 (8): 2237- 2264
10 冯文涛, 邓兵 一种基于交叉选择的柯西反向鲸鱼优化算法[J]. 兵器装备工程学报, 2020, 41 (8): 131- 137
FENG Wen-tao, DENG Bing A Cauchy inverse whale optimization algorithm based on cross selection[J]. Journal of Weapon and Equipment Engineering, 2020, 41 (8): 131- 137
doi: 10.11809/bqzbgcxb2020.08.026
11 BOSE P Moth-flame optimization algorithm for efficient cluster head selection in wireless sensor networks[J]. International Journal of Swarm Intelligence Research (IJSIR), 2022, 13 (1): 1- 14
12 TROKOVSKY P, DEHGHANI M Pelican optimization algorithm: a novel nature-inspired algorithm for engineering applications[J]. Sensors, 2022, 22 (3): 855
doi: 10.3390/s22030855
13 EDWIN D P, SANKARA G B A novel clustering algorithm by clubbing GHFCM and GWO for microarray gene data[J]. The Journal of Supercomputing, 2019, 76 (8): 5679- 5693
14 郭雨鑫, 刘升, 高文欣, 等 多策略改进哈里斯鹰优化算法[J]. 微电子学与计算机, 2021, 38 (7): 18- 24
GUO Yu-xin, LIU Sheng, GAO Wen-xin, et al Multi strategy improved Harris Hawk optimization algorithm[J]. Microelectronics and Computer, 2021, 38 (7): 18- 24
doi: 10.19304/j.cnki.issn1000-7180.2021.07.004
15 黄鹤, 李文龙, 杨澜, 等 DHSSA优化的K均值互补迭代车型信息数据聚类[J]. 汽车工程, 2022, 44 (5): 691- 700
HUANG He, LI Wen-long, YANG Lan, et al DHSSA optimized K-means complementary iterative model information data clustering[J]. Automotive Engineering, 2022, 44 (5): 691- 700
doi: 10.19562/j.chinasae.qcgc.2022.05.006
[1] 林一羽,郑旭东,吴海斌,马志鹏,金仲和. 采用恒频参量激励的微机械陀螺驱动控制方案[J]. 浙江大学学报(工学版), 2019, 53(9): 1795-1804.