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

摘要

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