基于模拟退火改进的近邻传播聚类在群决策中的应用
来源:用户上传
作者:张煜 王磊 俞璐 马昊 郁楠
摘 要： 多属性群体决策中，因决策问题复杂、群体成员众多难以形成一致的决策，对群体成员进行聚类形成子群体以减少群体集结复杂度，这是群体决策的重要基础。通过聚类算法提高群决策的效率与质量，首先，结合皮尔逊相关系数和切比雪夫距离定义了新的相似性度量;其次，利用模拟退火算法的参数全局寻优特性改进近邻传播算法;最后，通过实例应用与对比分析，说明新的相似性度量的优势并展示了改进算法的有效性和稳定性。
关键词： 群体决策; 偏好聚类; 相似性度量; 近邻传播; 模拟退火
中图分类号：TP311.52 文献标识码：A 文章编号：1006-8228（2022）10-45-06
Group preference clustering algorithm based on simulated annealing
and affinity propagation algorithm
Zhang Yu Wang Lei Yu Lu Ma Hao Yu Nan
（1. College of Communications Engineering， Army Engineering University of PLA， Nanjing， Jiangsu 210007， China; 2. Unit 31121 of PLA）
Abstract： In multi-attribute group decision making， it is difficult to form consistent decisions due to the complexity of decision making and the number of group members. Preference clustering of group members to form sub-groups to reduce the complexity of group assembly is an important basis for group decision making. To improve the efficiency and quality of group decision making by clustering algorithm， firstly， a new similarity measure is defined by combining Pearson correlation coefficient and Chebyshev distance; secondly， the affinity propagation algorithm is improved by using the parameter global optimization feature of simulated annealing algorithm; finally， the advantages of the new similarity measure are illustrated and the effectiveness and stability of the improved algorithm is demonstrated by example application and comparative analysis.
Key words： group decision making; preference clustering; similarity measure; affinity propagation; simulated annealing
0 引言
S着信息通信技术的迅猛发展，只有少数精英参与的小群体决策已无法适应信息社会的发展。为了体现决策的科学性和民主性，由不同经验背景和知识结构的成员，从不同视角和评判准则对方案进行评价，并依据特定的规则集结为群体判断的多属性群体决策，已广泛应用于实际复杂决策问题中。然而，决策成员数量大、评判准则类型多、准则间关联关系复杂，使得决策群体难以形成比较一致的决策。因此，对群体成员进行偏好聚类，形成若干子群体从而减少群体集结的复杂度，这是群体决策的重要基础[1]。
聚类是一种典型的无监督学习算法，根据相似性度量准则将数据分组成多个簇或者类，并且最大化类内数据的同质性和类间数据的异质性[2]。相似性度量一般可以分为基于距离的、基于密度的、基于连接的三类[3]，其中基于距离的最常用。在群体决策聚类应用方面，XU等[4]将偏好矢量间的相关度作为相似性度量，TANG等[5]以偏好矢量间的欧氏距离作为相似性度量，Ma等[6]针对犹豫模糊语言术语以期望距离和犹豫度相结合作为相似性度量，其中矢量相关度应用较为广泛。为适用群决策应用，合理度量决策者意见相似性，实现整体相似性与最大分歧点的折衷，本文拟结合皮尔逊相关系数和切比雪夫距离作为度量决策者给出的评价向量间相似性的准则。
聚类算法研究上，K-means聚类[7]作为最经典的聚类算法因原理简单、计算量小得到了广泛应用，Fuzzy C-means聚类[3]引入模糊数作为隶属度降低了对聚类个数的敏感度，随着应用深入Hierarchical[8]、K-medoids[9]、DBSCAN[10]等经典聚类算法及各类改进不断推出。在群决策应用上，LIU等[11]针对 FCM 聚类算法存在的局部极值和伸缩性差等问题提出了基于全部最小连通支配集的改进聚类算法，XU[12]等提出基于群体智能的改进的蚁群聚类算法，TANG[13]等对K-means聚类进行改进，结合群体共识达成应用于群决策。2007年，Brendan J.Frey提出的近邻传播聚类 （Affinity Propagation，AP）[14]是一种快速有效的聚类算法，具有无需设置聚类簇个数、聚类中心为原始数据、对野值不敏感等优点。模拟退火算法[15] （Simulated Annealing，SA）是基于Monte-Carlo迭代求解策略的一种随机寻优算法，具有强大的全局寻优能力。本文拟发挥模拟退火算法在全局参数寻优方面的优势，提升AP算法的稳定性和聚类效果，并将其应用于群决策。
nlc202210171915
1 基A理论
1.1 多属性群体决策问题
1.2 相似性度量
1.2.1 皮尔逊相关系数
1.2.2 切比雪夫距离
1.3 一致性度量
2 新的相似性度量
3 改进的近邻传播聚类算法
3.1 近邻传播算法
3.2 模拟退火算法
3.3 基于模拟退火改进的近邻传播聚类算法
4 实例应用
5 对比分析
5.1 相似性度量对比
5.2 算法改进分析
5.3 不同算法比较
6 结论
在大数据时代背景下，随着决策参与个体的不断丰富，信息集结前进行合理的聚类显得越发重要。本文在定义新的相似性度量基础上，有效利用模拟退火算法设置最优差异化偏向度，改进的AP聚类算法无需人工调节参数就可获得稳定的聚类结果和良好的一致性指标，经实验对比证明了其良好性能。由于篇幅有限，本文在评价信息上未采用区间模糊数、概率语言术语等较先进的评价模式，在聚类后，对子群体代表的评价信息进行简单的加权集结。下一步，可将信息表示方式扩展至概率语言集等不同信息表示环境，还可对共识达成和排序方法进行扩展研究。
参考文献（References）：
[1] 徐选华，尹儇鹏，钟香玉，等.大群体决策理论与方法研究综述：问题与挑战[J].信息与控制，2021，50（1）：54-64，74
[2] Han J，KamberM，Pei J. Data Mining Concepts andTechniques 3rd Edition[J]，2012
[3] 钱卫宁，周傲英.从多角度分析现有聚类算法（英文）[J].软件学报，2002（8）：1382-1394
[4] 徐选华，陈晓红.基于矢量空间的群体聚类方法研究[J].系统工程与电子技术，2005（6）：1034-1037
[5] Tang M，ZhouX，Liao H， et al. Ordinal Consensus Measurewith Objective Threshold for Heterogeneous Large-scale Group Decision Making[J].Crossref，2019，180：62-74
[6] Ma Z，ZhuJ，Ponnambalam K， et al. A Clustering Method forLarge-scale Group Decision-making with Multi-stage Hesitant Fuzzy Linguistic Terms[J]. Crossref，2019，50：231-250
[7] Na Shi，XuminLiu，Yong Guan. Research on k-meansClustering Algorithm：An Improved k-means Clustering Algorithm[Z]： IEEE，2010，4
[8] Zhu J，ZhangS，Chen Y， et al. A Hierarchical ClusteringApproach Based on Three-dimensional Gray Relational Analysis for Clustering a Large Group of Decision Makers with Double Information[J]. Crossref，2015，25（2）：325-354
[9] Li Xue. K-Means and K-Medoids[Z]. Boston， MA：Springer US：1588-1589
[10] Ram A，JalalS，Jalal AS， et al. A Density Based Algorithmfor Discovering Density Varied Clusters in Large Spatial Databases[J]. Crossref，2010，3（6）：1-4
[11] 陈晓红，刘蓉.改进的聚类算法及在复杂大群体决策中的应用[J].系统工程与电子技术，2006（11）：1695-1699
[12] 徐选华，范永峰.改进的蚁群聚类算法及在多属性大群体决策中的应用[J].系统工程与电子技术，2011，33（2）：346-349
[13] Tang M，Liao H. Multi-attribute Large-scale GroupDecision Making with Data Mining and Subgroup Leaders： an Application to the Development of the Circular Economy[J]. Crossref， 2021，167：120719
[14] Frey BJ，Dueck D. Clustering By Passing MessagesBetween Data Points[J].Crossref，2007，315（5814）：972-976
[15] ZelinkaIvan，SkanderovLenka. Simulated Annealing inResearch and Applications[Z]：InTech，2012
[16] 张峰，谢振华，程江涛，等.基于向量皮尔森相关系数的组合赋权法[J].火力与指挥控制，2015，40（5）：83-86
[17] Afghani SA，Putra WYM. Clustering with EuclideanDistance， Manhattan-Distance， Mahalanobis-Euclidean Distance， and Chebyshev Distance with Their Accuracy[J].Crossref，2021，5（2）： 369-376
[18] 李建新.混沌序列密码设计及其应用研究[D].西安电子科技大学，2019
[19] Chen Z，MartínezL，Chin K， et al. Two-stageAggregation Paradigm for Hflts Possibility Distributions： a Hierarchical Clustering Perspective[J].Crossref，2018，104：43-66
[20] Wu Z，Xu J. A Consensus Model for Large-scale GroupDecision Making with Hesitant Fuzzy Information and Changeable Clusters[J].Crossref，2018，41：217-231
[21] Tang M，LiaoH，Xu J， et al. Adaptive Consensus ReachingProcess with Hybrid Strategies for Large-scale Group Decision Making[J]. Crossref，2020，282（3）：957-971
nlc202210171915
转载注明来源:https://www.xzbu.com/8/view-15441143.htm
