Please wait a minute...
浙江大学学报(工学版)
Journal of ZheJiang University (Engineering Science)  2023, Vol. 57 Issue (11): 2147-2159    DOI: 10.3785/j.issn.1008-973X.2023.11.002
    
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
Download: HTML     PDF(2119KB) HTML
Export: BibTeX | EndNote (RIS)      

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     
Received: 28 November 2022      Published: 11 December 2023
CLC:  U 666.1  
Fund:  国家重点研发计划资助项目（2021YFB2501200）；国家自然科学基金资助项目（52172324，52172379）；陕西省重点研发计划资助项目(2021SF-483)；陕西省博士后科研资助项目（2018BSHYDZZ64）；西安市智慧高速公路信息融合与控制重点实验室(长安大学)开放基金资助项目(300102323502)；中央高校基本科研业务费资助项目（300102323501）
Corresponding Authors: Lan YANG     E-mail: huanghe@chd.edu.cn;lanyang@chd.edu.cn
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
He HUANG
Xia-lu WEN
Lan YANG
Hui-feng WANG
Tao GAO
Feng RU
Cite this article:

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.

URL:

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


基于疯狂捕猎秃鹰算法的K均值互补迭代聚类优化

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


关键词： K均值聚类(KMC),  体元密度,  秃鹰搜索（BES）算法,  点云聚类,  部件分割 
Fig.1 Initial clustering results of point cloud model
Fig.2 Change curve of escape factor
Fig.3 Flowchart of QO-BESCH algorithm
函数 表达式 取值范围
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} } }$
Tab.1 Functional test functions
Fig.4 3D space of test function and fitness curve
函数 算法 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
Tab.2 Comparison of mean and standard deviation of algorithms on test functions
算法 测试函数
F1 F2 F3 F9 F10 F11
MFO ? ? ? ? ? ?
POA ? ? ? ? ? ?
GWO ? ? ? ? ? ?
BES ? ? ? ? ? =
MHHO ? ? ? = = +
Tab.3 Wilcoxon rank and test for five algorithms
Fig.5 Flow chart of QO-BESCH-KMC algorithm
数据集 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
Tab.4 UCI standard data set characteristics
Fig.6 Fitness curves of clustering algorithms on different data sets
数据集 算法 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
Tab.5 Evaluation indicators of each algorithm for four data sets
Fig.7 Ablation experiment of initializing method
Fig.8 Ablation experiment with improved strategies
Fig.9 Comparison of evaluation indexes between proposed algorithm and KMC algorithm
模型 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
Tab.6 Filtering results of voxel filter
Fig.10 Filtering effects of different point cloud models
模型 算法 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
Tab.7 Evaluation indexes of clustering of nine point cloud models by different algorithms
Fig.11 Clustering segmentation effect of proposed algorithm on different data sets
[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] Yi-yu LIN,Xu-dong ZHENG,Hai-bin WU,Zhi-peng MA,Zhong-he JIN. MEMS gyroscopes parametric excitation control scheme with constant resonant frequency[J]. Journal of ZheJiang University (Engineering Science), 2019, 53(9): 1795-1804.