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

来源：计算机应用杂志2017年第5期北京时间：

作者：李焱, 刘弘, 郑向伟

单位：1. 山东师范大学 信息科学与工程学院, 济南 250014;2. 山东省分布式计算机软件新技术重点实验室, 济南 250014

摘要：运用社会力模型（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中心聚类,人群疏散仿真,社会力模型

基金资助：国家自然科学基金资助项目（61472232，61373149，61572299，61402269）；山东省自然科学基金资助项目（ZR2014FQ009）。