一种面向人群疏散的高效分组方法

doi:10.11896/j.issn.1002-137X.2019.06.035

摘要/Abstract

摘要： 在人群疏散的过程中,个体会依据关系的亲密度产生分组现象,因此人群分组行为是人群疏散仿真中不可忽略的因素。家人、朋友、同事等会根据亲密度形成分组,在疏散过程中同组人群会聚集成簇。聚类分组时常用的k-mediods聚类算法对噪声敏感,容易陷入局部最优,只能发现球状簇,且对初始聚类中心点的选择敏感,在聚类准确度上不尽人意。而DBSCAN算法具有抗噪声能力强、可发现任意形状的簇、无须指定初始聚类中心等优点,但只能识别密度相近的簇。对此,文中提出了折半DBSCAN聚类算法。该算法首先对关系数据进行二分划分,将有关系的数据划分到一个网格中,然后根据每个网格的人群密度决定聚类半径ε,最后对每个网格进行DBSCAN聚类,因此该算法可识别密度不同的簇。人群聚类分组后,在加入同组内个体吸引力的社会力模型中驱动个体运动,并模拟关系密切程度对聚集程度的影响。实验结果表明,在考虑了现实生活中有关系的人群空间分布状况下,所提方法具有较高的聚类精度,可真实地再现现实场景中的人群疏散情况,可作为紧急情况下预测人群疏散时间和疏散状况的重要工具。

关键词: DBSCAN聚类, k-mediods, 二分划分, 聚类算法, 人群疏散仿真

Abstract: In the crowd evacuation process,individuals usually produce the grouping phenomenon according to the intimacy of the relationship.Therefore,the grouping behavior is a factor that can not be neglected in the evacuation simulation of the crowd.The family,friends and colleagues usually form a group according to the degree of intimacy and gather together to a cluster in the evacuation process.The commonly used k-mediods clustering algorithm is sensitive to noise and easy to fall into the local optimum.It can only find the spherical cluster and is sensitive to the selection of the initial clustering center point,which is unsatisfactory in the accuracy of clustering.The DBSCAN algorithm has the advantages of strong ability to deal with noise and can find clusters of arbitrary shape and without specifying the initial clustering center,etc.But it can only identify clusters of similar density.Therefore,this paper proposed a binary DBSCAN clustering algorithm.This algorithm firstly divides the relational data to a grid,then it determines the cluster radius ε according to the density of population of the grid,and finally it executes the DBSCAN clustering algorithm for each grid,so these clusters with different densities can be identified.After clustering,the individual movement is driven in the social force modelwhich adds the individual attraction in the same group.And the influence of the intimacy degree on the aggregation degree is simulated.The experimental results show that,considering the spatial distribution of connected pedestrians in real life,this method has higher clustering accuracy.It can reappear the evacuation situation in the real scene and can be used as an important tool to predict evacuation time and evacuation situation.

Key words: Binary partition, Clustering algorithm, Crowd evacuation simulation, DBSCAN clustering, k-medoids

中图分类号:

TP319

张建新, 刘弘, 李焱. 一种面向人群疏散的高效分组方法[J]. 计算机科学, 2019, 46(6): 231-238. https://doi.org/10.11896/j.issn.1002-137X.2019.06.035

ZHANG Jian-xin, LIU Hong, LI Yan. Efficient Grouping Method for Crowd Evacuation[J]. Computer Science, 2019, 46(6): 231-238. https://doi.org/10.11896/j.issn.1002-137X.2019.06.035

参考文献

[1]LIU G P,LIU H,LV L,et al.Relationship-integrated crowds simulation[J].Journal of Chinese Mini-Micro Computer Systems,2016,37(8):1735-1740.(in Chinese)
柳广鹏,刘弘,吕蕾,等.融入关系分组的人群运动仿真[J].小型微型计算机系统,2016,37(8):1735-1740.
[2]FESTINGER L.A theory of social comparison processes[J].Human Relations,1954,7(7):117-140.
[3]TSAI J,FRIDMAN N,BOWRING E,et al.ESCAPES- Evacuation Simulation with Children,Authorities,Parents,Emotions,and Social comparison[J].Copyright,2013,50(6):563-564.
[4]LI Y,LIU H,LIU G P,ET A L.A grouping method based on grid density and relationship for crowd evacuation simulation[J].Physica A Statistical Mechanics & Its Applications,2017,473(1):319-336.
[5]TAN Y,HU R F,YIN G F.Adapted DBSCAN with multi-threshold[J].Journal of Computer Applications,2008,28(3):745-748.(in Chinese)
谭颖,胡瑞飞,殷国富.多密度阈值的 DBSCAN 改进算法[J].计算机应用,2008,28(3):745-748.
[6]XIA L N.SA-DBSCAN:A self-adaptive density-based clustering algorithm[J].Journal of the Graduate School of the Chinese Academy of Sciences,2009,26(4):530-538.
[7]KUMAR K M,REDDY A R M.A fast DBSCAN clustering algorithm by accelerating neighbor searching using Groups method[J].Pattern Recognition,2016,58:39-48.
[8]HE X X,GUAN J Y,YE X Z,et al.A density-based and grid-based cluster centers determination clustering algorithm[J].Control and Decision,2017,32(5):913-919.(in Chinese)
何熊熊,管俊轶,叶宣佐,等.一种基于密度和网格的簇心可确定聚类算法[J].控制与决策,2017,32(5):913-919.
[9]PATWARY M M A,PALSETIA D,AGRAWAL A,et al.A new scalable parallel DBSCAN algorithm using the disjoint-set data structure[C]∥High Performance Computing,Networking,Storage and Analysis.IEEE,2013:1-11.
[10]HE Y,TAN H,LUO W,et al.MR-DBSCAN:a scalable MapReduce-based DBSCAN algorithm for heavily skewed data[J].Frontiers of Computer Science,2014,8(1):83-99.
[11]LAKOBA T I,KAUP D J,FINKELSTEIN N M.Modifications of the Helbing-Molnar-Farkas-Vicsek social force model for pedestrian evolution[J].Simulation,2005,81 (5):339-352.
[12]OSARAGI T.Modeling of pedestrian behavior and its applications to spatial evaluation[C]∥Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems-Volume 2.IEEE Computer Society,2004:836-843.
[13]MOUSSAÏD M,HELBING D,THERAULAZ G.How simple rules determine pedestrian behavior and crowd disasters[J].Proceedings of the National Academy of Sciences,2011,108(17):6884-6888.
[14]HUGHES R L.A continuum theory for the flow of pedestrians[J].Transportation Research Part B:Methodological,2002,36(6):507-535.
[15]HOOGENDOORN S,BOVY P.Gas-kinetic modeling and simulation of pedestrian flows [J].Transportarion Research Record:Journal of the Transportation Research Board,2000,1710(1):28-36.
[16]HELBING D,JOHANSSON A,AL-ABIDEEN H Z.Dynamics of crowd disasters:An empirical study[J].Physical Review E,2007,75(4):046109.
[17]STEFFEN B.A modification of the social force model by foresight[M]∥Pedestrian and Evacuation Dynamics 2008.Berlin:Springer,2010:677-682.
[18]CAO M X,ZHANG G J,HUANG L J,et al.Crowd Animation Generation Method Based on Personalized Emotional Contagion[J].Computer Science,2017,44(6):306-311.(in Chinese)
曹梦晓,张桂娟,黄丽君,等.基于个性化情绪感染的人群动画生成方法[J].计算机科学,2017,44(6):306-311.
[19]PARISI D R,GILMAN M,MOLDOVAN H.A modification of the Social Force Model can reproduce experimental data of pedestrian flows in normal conditions[J].Physica A Statistical Mechanics and Its Applications,2012,388(17):3600-3608.
[20]JI Q G,HE H,WANG F C.Social Force Model for Crowd Simulation Using Density Field[J].Computer Science,2015,42(6):12-17.(in Chinese)
纪庆革,何浩,王福川.密度场下的短程社会力模型[J].计算机科学,2015,42(6):12-17.
[21]MUSSE S R,THALMANN D.A model of human crowd beha-vior:Group inter-relationship and collision detection analysis[J].Computer Animation and Simulation,1997,97(9):39-51.
[22]VIZZARI G,MANENTI L,CROCIANI L.Adaptive pedestrian behaviour for the preservation of group cohesion[J].Complex Adaptive Systems Modeling,2013,1(1):1-29.
[23]QIU F,HU X.Modeling group structures in pedestrian crowd simulation[J].Simulation Modelling Practice and Theory,2010,18(2):190-205.
[24]FU Y W,LIANG J H,LIU Q P,et al.Crowd Simulation for Evacuation Behaviors Based on Multi-agent System and Cellular Automaton[C]∥International Conference on Virtual Reality and Visualization.IEEE,2015:103-109.
[25]QIU F,HU X.A Framework for Modeling Social Groups in Agent-Based Pedestrian Crowd Simulations[J].International Journal of Agent Technologies and Systems,2012,4(1):39-58.
[26]QIN X,LIU H,ZHANG H,et al.A collective motion model based on two-layer relationship mechanism for bi-direction pedestrian flow simulation[J].Simulation Modelling Practice and Theory,2018,84:268-285.
[27]ZHANG H,LIU H,QIN X,et al.Modified two-layer social force model for emergency earthquake evacuation[J].Physica A Statistical Mechanics and Its Applications,2018,492:1107-1119.
[28]LIU B,LIU H,ZHANG H,et al.A social force evacuation model driven by video data[J].Simulation Modelling Practice and Theo-ry,2018,84:190-203.
[29]XU X,ZHANG L,SOTIRIADIS S,et al.CLOTHO:A Large-Scale Internet of Things based Crowd Evacuation Planning System for Disaster Management[J].IEEE Internet of Things Journal,2018,99:1-1.
[30]LIU H,XU B,LU D,et al.A Path Planning Approach for Crowd Evacuation in Buildings Based on Improved Artificial Bee Colony Algorithm[J].Applied Soft Computing,2018,68:360-376.
[31]MOUSSAÏD M,PEROZO N,GARNIER S,et al.The walking behaviour of pedestrian social groups and its impact on crowd dynamics[J].Plos One,2010,5(4):e10047.
[32]RODRIGUEZ A,LAIO A.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492-1496.
[33]FRIDMAN N, KAMINKA G A.Comparing human and synthetic group behaviors:A model based on social psychology[C]∥International Conference on Cognitive Modeling(ICCM-09).2009.
[34]FRIDMAN N,KAMINKA G A.Towards a cognitive model of crowd behavior based on social comparison theory[C]∥National Conference on Artificial Intelligence.AAAI Press,2007:731-737.
[35]WANG L,CAI Y,XU Q.Modifications to Social Force Model [J].Journal of Nanjing University of Science and Technology(Natural Science),2011,35(1):144-149.(in Chinese)
汪蕾,蔡云,徐青.社会力模型的改进研究[J].南京理工大学学报,2011,35(1):144-149.

相关文章 15

[1]	柴慧敏, 张勇, 方敏. 基于特征相似度聚类的空中目标分群方法 Aerial Target Grouping Method Based on Feature Similarity Clustering 计算机科学, 2022, 49(9): 70-75. https://doi.org/10.11896/jsjkx.210800203
[2]	张亚迪, 孙悦, 刘锋, 朱二周. 结合密度参数与中心替换的改进K-means算法及新聚类有效性指标研究 Study on Density Parameter and Center-Replacement Combined K-means and New Clustering Validity Index 计算机科学, 2022, 49(1): 121-132. https://doi.org/10.11896/jsjkx.201100148
[3]	李杉, 许新征. 基于双角度并行剪枝的VGG16优化方法 Parallel Pruning from Two Aspects for VGG16 Optimization 计算机科学, 2021, 48(6): 227-233. https://doi.org/10.11896/jsjkx.200800016
[4]	汤鑫瑶, 张正军, 储杰, 严涛. 基于自然最近邻的密度峰值聚类算法 Density Peaks Clustering Algorithm Based on Natural Nearest Neighbor 计算机科学, 2021, 48(3): 151-157. https://doi.org/10.11896/jsjkx.200100112
[5]	王茂光, 杨行. 一种基于AP-Entropy选择集成的风控模型和算法 Risk Control Model and Algorithm Based on AP-Entropy Selection Ensemble 计算机科学, 2021, 48(11A): 71-76. https://doi.org/10.11896/jsjkx.210200110
[6]	王卫东, 徐金慧, 张志峰, 杨习贝. 基于密度峰值聚类的高斯混合模型算法 Gaussian Mixture Models Algorithm Based on Density Peaks Clustering 计算机科学, 2021, 48(10): 191-196. https://doi.org/10.11896/jsjkx.200800191
[7]	张煜, 陆亿红, 黄德才. 基于密度峰值的加权犹豫模糊聚类算法 Weighted Hesitant Fuzzy Clustering Based on Density Peaks 计算机科学, 2021, 48(1): 145-151. https://doi.org/10.11896/jsjkx.200400043
[8]	徐守坤, 倪楚涵, 吉晨晨, 李宁. 基于YOLOv3的施工场景安全帽佩戴的图像描述 Image Caption of Safety Helmets Wearing in Construction Scene Based on YOLOv3 计算机科学, 2020, 47(8): 233-240. https://doi.org/10.11896/jsjkx.190600109
[9]	罗晋楠, 张济民. 基于扩展Haar特征和DBSCAN的钢轨识别算法 Rail Area Extraction Using Extended Haar-like Features and DBSCAN Clustering 计算机科学, 2020, 47(6A): 153-156. https://doi.org/10.11896/JsJkx.200100008
[10]	邓定胜. 一种改进的DBSCAN算法在Spark平台上的应用 Application of Improved DBSCAN Algorithm on Spark Platform 计算机科学, 2020, 47(11A): 425-429. https://doi.org/10.11896/jsjkx.190700071
[11]	田献珍, 孙立强, 田振中. 基于蚁群算法的图像重建 Image Reconstruction Based on Ant Colony Algorithm 计算机科学, 2020, 47(11A): 231-235. https://doi.org/10.11896/jsjkx.191000128
[12]	魏霖静, 宁璐璐, 郭斌, 侯振兴, 甘诗润. 基于混合蛙跳算法的K-mediods聚类挖掘与并行优化 K-mediods Cluster Mining and Parallel Optimization Based on Shuffled Frog Leaping Algorithm 计算机科学, 2020, 47(10): 126-129. https://doi.org/10.11896/jsjkx.190900113
[13]	胡闯, 杨庚, 白云璐. 面向差分隐私保护的聚类算法 Clustering Algorithm in Differential Privacy Preserving 计算机科学, 2019, 46(2): 120-126. https://doi.org/10.11896/j.issn.1002-137X.2019.02.019
[14]	陈子豪, 李强. 基于K-medoids的改进PBFT共识机制 Improved PBFT Consensus Mechanism Based on K-medoids 计算机科学, 2019, 46(12): 101-107. https://doi.org/10.11896/jsjkx.181002014
[15]	张天柱, 邹承明. 使用模糊聚类的胶囊网络在图像分类上的研究 Study on Image Classification of Capsule Network Using Fuzzy Clustering 计算机科学, 2019, 46(12): 279-285. https://doi.org/10.11896/jsjkx.190200315

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed