基于子博弈完美均衡的启发式聚类算法

常璐瑶; 牛新征; 罗涛; 钱早国

doi:10.12263/DZXB.20221206

您当前的位置：

首页 >

文章列表页 >

基于子博弈完美均衡的启发式聚类算法

学术论文 | 更新时间：2025-12-11

- 基于子博弈完美均衡的启发式聚类算法
- Heuristic Clustering Algorithm Based on Sub-Game Perfect Equilibrium
- 电子学报 2024年52卷第3期页码：740-750
- 作者机构：
  
  电子科技大学计算机科学与工程学院，四川成都 611731
- 作者简介：
  
  [ "常璐瑶女，1999年6月出生于河南省平顶山市.电子科技大学硕士研究生.主要研究方向为数据挖掘与机器学习. E-mail: chang_ly16@163.com" ]
  [ "牛新征男，1978年5月出生于贵州省贵阳市.现为电子科技大学教授级高级工程师，主要研究方向为数据挖掘和信息安全. E-mail: xinzhengniu@uestc.edu.cn" ]
  [ "罗涛男，1999年6月出生于四川省峨眉山市.电子科技大学硕士研究生.主要研究方向为图神经网络. E-mail: lllttt0603@163.com" ]
  [ "钱早国男，1999年4月出生于贵州省遵义市.电子科技大学硕士研究生.主要研究方向为分布式计算. E-mail: mansurn@163.com" ]
- 基金信息：
  
  国家自然科学基金(62272087);四川省科技计划项目(2021YFS0391)
- DOI：10.12263/DZXB.20221206
  中图分类号： TP18
- 收稿：2022-10-25，
  
  修回：2023-02-01，
  
  纸质出版：2024-03-25
- 稿件说明：
移动端阅览
常璐瑶,牛新征,罗涛,等.基于子博弈完美均衡的启发式聚类算法[J].电子学报,2024,52(03):740-750.

CHANG Lu-yao, NIU Xin-zheng, LUO Tao, et al.Heuristic Clustering Algorithm Based on Sub-Game Perfect Equilibrium[J].Acta Electronica Sinica, 2024, 52(03): 740-750.
常璐瑶,牛新征,罗涛,等.基于子博弈完美均衡的启发式聚类算法[J].电子学报,2024,52(03):740-750. DOI：10.12263/DZXB.20221206

CHANG Lu-yao, NIU Xin-zheng, LUO Tao, et al.Heuristic Clustering Algorithm Based on Sub-Game Perfect Equilibrium[J].Acta Electronica Sinica, 2024, 52(03): 740-750. DOI：10.12263/DZXB.20221206

摘要

聚类是一种典型且重要的数据挖掘方法，但现有聚类算法大多需要人为指定聚类的数量，并且聚类结果对参数敏感.针对上述不足，本文提出一种基于子博弈完美均衡的启发式聚类算法（Heuristic Clustering algorithm based on Sub-game Perfect Equilibrium，HCSPE）.该算法充分挖掘数据点自身的分布特征信息，通过启发式方法得到自适应的参数值，从而使数据点局部密度属性值的得出具有客观性和普适性，降低了聚类结果对参数的敏感性.基于博弈的思想，综合局部密度和相对距离两个属性形成数据点的竞争力，依靠竞争机制完成聚类数量的自动计算以及聚类中心的

确定.在多个规模和类型均不相同的数据集上的实验结果表明，本文所提出算法的性能指标整体优于其他算法，并且聚类结果更符合客观所需

Abstract

Clustering is a typical and important data mining method

but most of the existing clustering algorithms need to specify the number of clusters artificially

and the clustering results are sensitive to parameters. To address the above shortcomings

this paper proposes a heuristic clustering algorithm based on sub-game perfect equilibrium (HCSPE). The algorithm fully exploits the information of the distribution characteristics of data points themselves and obtains the adaptive parameter values by heuristic methods

so that the local density attribute values of data points are derived with objectivity and universality

and the sensitivity of clustering results to parameters is reduced. Based on the idea of game

the two attributes of local density and relative distance are integrated to form the competitiveness of data points

and the automatic calculation of the number of clusters and the determination of cluster centers are completed by relying on the competition mechanism. The experimental results on several data sets of different sizes and types show that the performance indexes of the proposed algorithm are better than other algorithms in general

and the clustering results are more in line with the objective requirements.

关键词

Keywords

references

WANG G T , SONG Q B . Automatic clustering via outward statistical testing on density metrics [J ] . IEEE Transactions on Knowledge and Data Engineering , 2016 , 28 ( 8 ): 1971 - 1985 .

CHAO G Q , SUN S L , BI J B . A survey on multi-view clustering [J ] . IEEE Transactions on Artificial Intelligence , 2021 , 2 ( 2 ): 146 - 168 .

FLORES-VIDAL P A , OLASO P , GÓMEZ D , et al . A new edge detection method based on global evaluation using fuzzy clustering [J ] . Soft Computing , 2019 , 23 ( 6 ): 1809 - 1821 .

LIEW A W C , YAN H , YANG M S . Pattern recognition techniques for the emerging field of bioinformatics: A review [J ] . Pattern Recognition , 2005 , 38 ( 11 ): 2055 - 2073 .

BRUSE J L , ZULUAGA M A , KHUSHNOOD A , et al . Detecting clinically meaningful shape clusters in medical image data: Metrics analysis for hierarchical clustering applied to healthy and pathological aortic Arches [J ] . IEEE Transactions on Bio-Medical Engineering , 2017 , 64 ( 10 ): 2373 - 2383 .

GAO J , CHANG M T , JOHNSEN H C , et al . 3D clusters of somatic mutations in cancer reveal numerous rare mutations as functional targets [J ] . Genome Med , 2017 , 9 ( 1 ): 4 .

KUMAR D , WU H Y , RAJASEGARAR S , et al . Fast and scalable big data trajectory clustering for understanding urban mobility [J ] . IEEE Transactions on Intelligent Transportation Systems , 2018 , 19 ( 11 ): 3709 - 3722 .

COOPER C , FRANKLIN D , ROS M , et al . A comparative survey of VANET clustering techniques [J ] . IEEE Communications Surveys & Tutorials , 2017 , 19 ( 1 ): 657 - 681 .

DUAN X Y , LIU Y N , WANG X B . SDN enabled 5G-VANET: Adaptive vehicle clustering and beamformed transmission for aggregated traffic [J ] . IEEE Communications Magazine , 2017 , 55 ( 7 ): 120 - 127 .

JUNG J Y , BAE J , LIU L . Hierarchical clustering of business process models [J ] . International Journal of Innovative Computing, Information and Control , 2009 , 5 ( 12 ): 4501 - 4511 .

PUNHANI R , ARORA V P S , SABITHA S , et al . Application of clustering algorithm for effective customer segmentation in E-commerce [C ] // 2021 International Conference on Computational Intelligence and Knowledge Economy (ICCIKE) . Piscataway : IEEE , 2021 : 149 - 154 .

FU D Q , HE S J . New combination algorithms in commercial area data mining and clustering [C ] // 2016 IEEE International Conference on Big Data Analysis (ICBDA) . Piscataway : IEEE , 2016 : 1 - 5 .

MUSMECI N , ASTE T , MATTEO T D . Relation between financial market structure and the real economy: Comparison between clustering methods [J ] . PLoS One , 2015 , 10 ( 3 ): e0116201 .

TETE T N , KAMLU S . Detection of plant disease using threshold, k-mean cluster and ann algorithm [C ] // 2017 2nd International Conference for Convergence in Technology (I2CT) . Piscataway : IEEE , 2017 : 523 - 526 .

BABKIN A , TASHENOVA L , SMIRNOVA O , et al . Analyzing the trends in the digital economy and the factors of industrial clustering [C ] // Proceedings of the 2nd International Scientific Conference on Innovations in Digital Economy . New York : ACM , 2020 : 1 - 10 .

BORDOGNA G , PASI G . A quality driven hierarchical data divisive soft clustering for information retrieval [J ] . Knowledge-Based Systems , 2012 , 26 : 9 - 19 .

MURTAGH F , CONTRERAS P . Algorithms for hierarchical clustering: An overview [J ] . WIREs Data Mining and Knowledge Discovery , 2012 , 2 ( 1 ): 86 - 97 .

RUSPINI E H , BEZDEK J C , KELLER J M . Fuzzy clustering: A historical perspective [J ] . IEEE Computational Intelligence Magazine , 2019 , 14 ( 1 ): 45 - 55 .

RODRIGUEZ A , LAIO A . Clustering by fast search and find of density peaks [J ] . Science , 2014 , 344 ( 6191 ): 1492 - 1496 .

MEHMOOD R , ZHANG G Z , BIE R F , et al . Clustering by fast search and find of density peaks via heat diffusion [J ] . Neurocomputing , 2016 , 208 : 210 - 217 .

XIE J Y , GAO H C , XIE W X , et al . Robust clustering by detecting density peaks and assigning points based on fuzzy weighted K -nearest neighbors [J ] . Information Sciences , 2016 , 354 : 19 - 40 .

GAN G J , ZHANG Y P , DEY D K . Clustering by propagating probabilities between data points [J ] . Applied Soft Computing , 2016 , 41 : 390 - 399 .

JAHANGOSHAI REZAEE M , ESHKEVARI M , SABERI M , et al . GBK-means clustering algorithm: An improvement to the K-means algorithm based on the bargaining game [J ] . Knowledge-Based Systems , 2021 , 213 : 106672 .

程乐峰 . 电力市场多群体策略博弈的长期演化稳定均衡理论研究 [D ] . 广州 : 华南理工大学 , 2019 .

CHENG Y F . Theoretical Investigation on the Long-Term Evolutionarily Stable Equilibrium of Multi-population Strategic Games in Electricity Market [D ] . Guangzhou : South China University of Technology , 2019 . (in Chinese)

ALDERSHOF B , MARRON J S , PARK B U , et al . Facts about the Gaussian probability density function [J ] . Applicable Analysis , 1995 , 59 ( 1/2/3/4 ): 289 - 306 .

CHANG S , SHIHONG Y , Qi L . Clustering characteristics of UCI dataset [C ] // 2020 39th Chinese Control Conference (CCC) . IEEE , 2020 : 6301 - 6306 .

AL-JABERY K , OBAFEMI-AJAYI T , OLBRICHT G , et al . Computational Learning Approaches to Data Analytics in Biomedical Applications [M ] . San Diego : Academic Press , 2020 .

HARTIGAN J A , WONG M A . A K-means clustering algorithm [J ] . Journal of the Royal Statistical Society Series C: Applied Statistics , 1979 , 28 ( 1 ): 100 - 108 .

Bäcklund H , Hedblom A , Neijman N . A density-based spatial clustering of application with noise [J ] . Data Mining TNM 033 , 2011 : 11 - 30 .

LOTFI A , MORADI P , BEIGY H . Density peaks clustering based on density backbone and fuzzy neighborhood [J ] . Pattern Recognition , 2020 , 107 : 107449 .

WANG S L , LI Q , ZHAO C F , et al . Extreme clustering—A clustering method via density extreme points [J ] . Information Sciences , 2021 , 542 : 24 - 39 .

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于时序-脉幅聚类的未知雷达辐射源信号分选方法

基于动态关系原型的持续关系抽取技术

基于伪标签去噪和SAM优化的大规模无监督语义分割

面向流形数据的测地距离与余弦互逆近邻密度峰值聚类算法