计算机应用 ›› 2017, Vol. 37 ›› Issue (5): 1491-1495.DOI: 10.11772/j.issn.1001-9081.2017.05.1491

• 应用前沿、交叉与综合 • 上一篇    下一篇

折半聚类算法在基于社会力的人群疏散仿真中的应用

李焱1,2, 刘弘1,2, 郑向伟1,2   

  1. 1. 山东师范大学 信息科学与工程学院, 济南 250014;
    2. 山东省分布式计算机软件新技术重点实验室, 济南 250014
  • 收稿日期:2016-09-30 修回日期:2016-12-09 出版日期:2017-05-10 发布日期:2017-05-16
  • 通讯作者: 刘弘
  • 作者简介:李焱(1980-),男,山东菏泽人,讲师,博士研究生,CCF会员,主要研究方向:计算机仿真、聚类分析;刘弘(1955-),女,山东济南人,教授,博士,CCF会员,主要研究方向:分布式人工智能、软件工程、计算机辅助设计;郑向伟(1971-),男,山东泰安人,教授,博士,CCF会员,主要研究方向:计算机网络、计算智能、计算机辅助教育。
  • 基金资助:
    国家自然科学基金资助项目(61472232,61373149,61572299,61402269);山东省自然科学基金资助项目(ZR2014FQ009)。

Application of binary clustering algorithm to crowd evacuation simulation based on social force

LI Yan1,2, LIU Hong1,2, ZHENG Xiangwei1,2   

  1. 1. School of Information Science and Engineering, Shandong Normal University, Jinan Shandong 250014, China;
    2. Shandong Provincial Key Laboratory for Distributed Computer Software Novel Technology, Jinan Shandong 250014, China
  • Received:2016-09-30 Revised:2016-12-09 Online:2017-05-10 Published:2017-05-16
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61472232, 61373149, 61572299, 61402269), the Shandong Provincial Natural Science Foundation of China (ZR2014FQ009).

摘要: 运用社会力模型(SFM)模拟人群疏散之前,需要先对人群进行聚类分组;然而,k中心聚类(k-medoids)和统计信息网格聚类(STING)这两大传统聚类算法,在聚类效率和准确率上都不能满足要求。针对这个问题,提出了折半聚类算法(BCA)。该算法结合了围绕中心点聚类和基于网格聚类两类方式,并利用二分法查找思想划分网格,不需要反复聚类。先将数据用二分法划分成网格,再根据网格内数据密度选出核心网格,接着以核心网格为中心将邻居网格聚类,最后按就近原则归并剩余网格。实验结果表明,在聚类时间上,BCA平均仅是STING算法的48.3%,不到k-medoids算法的14%;而在聚类准确率上,k-medoids算法平均仅是BCA的50%,STING算法平均也只是BCA的88%。因此,BCA无论在效率还是准确率上都明显优于STING和k-medoids算法。

关键词: 聚类算法, 统计信息网格, k中心聚类, 人群疏散仿真, 社会力模型

Abstract: Pedestrian crowd needs to be divided into groups by using clustering algorithms before using the Social Force Model (SFM) to simulate crowd evacuation. Nevertheless, k-medoids and STatistical INformation Grid (STING) are two traditional clustering algorithms, cannot meet the requirements in the aspect of efficiency and accuracy. To solve the above problem, a new method named Binary Clustering Algorithm (BCA) was proposed in this paper. BCA was composed of two kinds of algorithms:center point clustering and grid clustering. Moreover, the dichotomy was used to divide the grid without repeated clustering. First of all, the data was divided into grids, through the use of dichotomy. Next, the core grid would be selected, according to the data density in a grid. Then, the core grid was used as the center, and the neighbors were clustered. Finally, the residual grids were was merged according to the nearest principle. The experimental results show that, in the clustering time, BCA is only 48.3% of the STING algorithm, less than 14% of the k-medoids algorithm; and in the clustering accuracy, k-medoids is only 50% of BCA, STING doesn't reach to 90% of BCA. Therefore, BCA is better than k-medoids and STING algorithm in both efficiency and accuracy.

Key words: clustering algorithm, STatistical INformation Grid (STING), k-medoids, crowd evacuation simulation, Social Force Model (SFM)

中图分类号: