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

发布时间：2018-07-29 18:27

【摘要】：运用社会力模型(SFM)模拟人群疏散之前,需要先对人群进行聚类分组;然而,k中心聚类(k-medoids)和统计信息网格聚类(STING)这两大传统聚类算法,在聚类效率和准确率上都不能满足要求。针对这个问题,提出了折半聚类算法(BCA)。该算法结合了围绕中心点聚类和基于网格聚类两类方式,并利用二分法查找思想划分网格,不需要反复聚类。先将数据用二分法划分成网格,再根据网格内数据密度选出核心网格,接着以核心网格为中心将邻居网格聚类,最后按就近原则归并剩余网格。实验结果表明,在聚类时间上,BCA平均仅是STING算法的48.3%,不到k-medoids算法的14%;而在聚类准确率上,k-medoids算法平均仅是BCA的50%,STING算法平均也只是BCA的88%。因此,BCA无论在效率还是准确率上都明显优于STING和k-medoids算法。
[Abstract]:The social force model (SFM) is used to simulate the evacuation of people, but the traditional clustering algorithms such as k-medoids and (STING) can not meet the requirements of clustering efficiency and accuracy. In order to solve this problem, a reduced half clustering algorithm (BCA).) is proposed. The algorithm combines the clustering around the center and the grid clustering, and uses the idea of dichotomy to divide the grid without the need of repeated clustering. Firstly, the data is divided into grids by dichotomy, then the core grid is selected according to the data density in the grid, then the neighbor grid is clustered around the core grid, and the remaining grid is merged according to the principle of proximity. The experimental results show that the average clustering time is only 48.3% of the STING algorithm, less than 14% of the k-medoids algorithm, while the average clustering accuracy of the k-medoids algorithm is only 50% of the BCA algorithm, and the average is only 88% of the BCA algorithm. Therefore, BCA is superior to STING and k-medoids in efficiency and accuracy.
【作者单位】：山东师范大学信息科学与工程学院;山东省分布式计算机软件新技术重点实验室;
【基金】：国家自然科学基金资助项目(61472232,61373149,61572299,61402269) 山东省自然科学基金资助项目(ZR2014FQ009)~~
【分类号】：TP311.13;U491.226

【相似文献】