0 引言

人群疏散研究涉及到避免践踏等公共安全问题，是近年来研究的热点。为了定量分析、模拟人群运动，很多研究人员已经作了大量调查、实验乃至疏散演习并收集了观测数据，因此，很多研究人员转向运用计算机模拟来仿真人群疏散，也取得了很多成果，而以真人作模拟实验会发生很多不受控制的情况，有一定危险性，而且实验成本也很高。

1) 人群疏散数学模型。

研究人员纷纷采用像排队论之类的数学理论或思想，建立人群疏散仿真的数学模型，比如排队模型^[1-2]、格子气模型^[3-5]、元胞自动机模型^[6-7]、基于代理的疏散模型^[8-9]、社会力模型^[10-13]等。这些模型大致可以分为两类：微观和宏观^[14]。其中，除排队模型是宏观模型，其余4个模型都是微观模型。

文献[1-2]结合排队模型，更多地是从整体研究人群流动特性，但是没有考虑个体间的作用和关系 (如物理上的摩擦与碰撞、心理上的排斥与吸引等)，所以本文从个体间作用入手，运用微观模型研究人群疏散问题。文献[3-5]运用改进的格子气模型模拟了人流状态，文献[5]还增加了对个体步长的调整；文献[6-7]都利用元胞自动机模型研究了火灾时的人群疏散；文献[8-9]则分别在平面建筑和多层建筑中运用基于代理的模型仿真人群疏散。以上文献虽然都采用了微观模型，具体研究了行人的步长、恐慌等个体因素，取得了较好的效果，但没有涉及到个体间的相互作用。而文献[10-13]则采用了社会力模型对人群疏散进行了微观仿真研究, 尤为难得的是社会力模型描述了人群中的个体，在与其他个体及环境的相互作用力的作用下以期望速度向着给定目标运动的状态^[13]。因此，本文采用了基于社会力模型的方法仿真人群疏散。

2) 人群疏散的特征。

在人群疏散过程中，个体自身的心理状态及个体间的相互作用可能影响人流运动，尤其在紧急状态下，人群运动的盲目性、从众性的特征更加显著，这将导致较为典型的现象发生：

1) “瓶颈节点”。危急情况下，人流速度明显加快，而相对于房间、中厅、走廊等位置，出口显然会成为人流的目标，极易因争抢而降低通行效率，从而造成阻塞^[11]，成为通行中的“瓶颈节点”。

2) 盲目从众。即个体行为很容易被其周围人群的行为所影响^[15]。因为不仅周围人群的恐慌情绪会感染该个体，而且他们的行为也将影响该个体并引发衍生效应。

3) 聚团运动。即群体运动中关系亲密的个体倾向于在运动中形成一个个的小团体，比如家庭、朋友、同学等。这些小组对疏散速度的影响是显著的，但其影响是不确定的，有时能帮助个体快速找到出口，有时小组运动也会阻碍其他个体的运动。同组个体间的作用也呈现明显的非线性特征^[16]。

尽管社会力模型很好地模拟了“瓶颈节点”、出口“拱形效应”“快即是慢”^[11]等典型现象，也很细致地描述了个体自身的驱动力及个体与个体、个体与环境间的相互作用力，但是它忽略了现实中的人际关系，即人群在运动过程中，关系亲密的人比如情侣、家庭等，不能有效地模拟聚团分组运动，那么，如何快速地识别出人群中的有关系的人并准确地聚类成组，就成了模拟人群疏散中的重要一环。本文在社会力模型中增加了团组划分信息，促使人群在社会力作用下进行聚团分组运动，以便更真实地模拟人群疏散。

本文把聚类算法用到了人群分组中，并把分组信息加入了社会力模型，用以仿真人群疏散，因为人群运动中分组可能随时变化，这就需要聚类算法具有较高的速度和准确度。本文通过对比统计信息网格 (STatistical INformation Grid, STING)^[17]算法和k中心聚类 (k-medoids)^[18]算法，在传统的围绕中心点聚类的思想上结合了网格划分思想，并在划分网格时引入了非均匀的折半划分思想，提出了折半聚类算法 (Binary Clustering Algorithm, BCA)，并尝试把该算法运用到人群分组的聚类中；通过仿真实验同传统的STING和k-medoids两种算法作对比，展现了折半聚类算法在速度和准确度上的优势。

1 聚类算法

聚类算法大体分为基于划分的、基于层次的、基于密度的、基于网格的、基于模型的、模糊聚类、基于图论的、基于分形的、复杂网络聚类、仿生法及核聚类等11种方法^[19]。本文选取了其中两种经典的算法进行了人群分组聚类实验：一种是基于划分的k-medoids算法, 另一种是基于网格的STING算法，发现效果不佳。

k-medoids算法 它是最经典的聚类算法k-means的延伸，不仅可以处理数值属性类数据，还可以处理分类属性类数据，并且它在处理存在“噪声”和孤立点的数据时，比k-means更健壮、更有效，不像k-means那样容易受极端数据影响。不过，它用于人群分组，运行时间很长，整体准确度也较低，不能满足人群分组的要求。

STING算法 它是传统的基于网格的多分辨率聚类算法，将空间区域划分为矩型单元。针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一个层次结构；高层的每个单元被划分为多个低一层的单元。每个网格单元属性的统计信息 (例如平均值、最大值和最小值) 被预先计算和存储^[20]。相对于传统的划分算法，该算法具有时间复杂度较低、执行效率较高、聚类准确度也相对较高的优点。

但是，由于STING算法采用了一个均匀划分的方法来进行聚类，其聚类的质量取决于网格结构的最底层的粒度^[21]。其实，由网格最低层粒度决定的不仅是聚类的质量，还有聚类的时间复杂度，即粒度越粗 (底层格子密度越低)，聚类的准确度就越低，而时间复杂度也就随之降低；反之则都会提高。因为人群分组对于实时性和准确性都有较高要求，所以对于聚类算法，不仅要求质量高还要满足速度快，但是，在实验过程中，发现STING算法中这两个指标是一对矛盾体，质量高速度就会降低，而且STING算法因为算法自身的局限，它的准确度本身就有瓶颈，而且所要付出的代价太大，时间耗费得太多不符合实时性要求。

针对人群分组的自身特点和要求，本文尝试了一种非均匀的折半聚类方法，该方法在结合上面两类算法的思想上增加了折半划分的思路，即先把场景网格化，但这个网格化过程是基于折半思路的非均匀二分法划分的过程，再利用围绕中心点聚类的思想，找出核心网格 (内部个体密度高的网格)，然后进行聚类分组，这样减少了最终的网格划分数量，提高了聚类效率。

2 折半聚类算法

人群的分布状态随着行人的运动随时会发生变化，在整个场景中人群的局部疏密度也会发生变化，而折半聚类的方法可以区分疏密区域、粗分稀疏区域或舍弃空白区域、细分稠密区域，在提高准确度的同时减少了网格数量。

2.1 算法思想及过程

折半聚类的思想是以二分法对整个场景划分网格，划分原则是网格中个体属于同一属性组 (下简称同组) 则不分，否则继续二分。该算法整体分为如下三个阶段。

首先，对整个场景进行二分的非均匀网格划分，比较场景的边长，把长边均分两半，形成两个格子，再检测每个格子，如果格子里是空的或者是同组的个体则停止，否则就把该格子按同样规则二等分，这样继续二等分下去，直到格子为空或者格子里的个体都是同组的为止。这个过程类似以先根遍历建立了一棵不含度为1节点的二叉树，只不过树叶都是同组个体或者空的网格。

其次，把最终的非空叶子网格聚成k(k是事先给定的，为了减少拥塞提高疏散效率，人群的最佳分组数目将取决于封闭场景中的出口数目，通常是其三倍) 组，小组聚合的规则是以核心网格为中心聚合其周围邻居的叶子网格。首先把这些非空叶子网格按密度 (密度等于格子内的个体数目除以个体所占实际面积) 非递增排序，次序靠前的叶子网格的是核心网格，检测核心网格周围的邻居叶子网格是否与其同组，同组则聚合，否则以剩余的叶子网格为核心网格继续聚合，直到所有的叶子网格都检测一遍。

最后，如果存在未同核心网格聚合的网格 (主要是只含个体的网格)，就把这些网格中的个体同前面完成聚合的小组中心位置对比距离，聚合到最近的网格小组中。

过程 折半聚类。

1) 外层循环。以场景为根，用先序遍历建立一棵二叉树。先二等分较长的边，形成左右子树即两个网格，再检测左子树即第一个格子，若格子内的个体不同组则继续二等分，否则，若同组或为空，则设为叶子格子，然后检测右子树即第二个格子，依此类推，直到所有的格子为同组或为空，即生成了所有的叶子格子。

2) 内层循环。检测非空网格内的个体是否同组。以个体的实际中心为中心位置，即以边界个体的坐标而不是网格顶点坐标来计算中心位置，以个体到中心距离的均值为邻域半径，距离在半径内的个体则同组并设置同组属性，否则是异组。

3) 按网格密度非递增排序叶子网格。

4) 按顺序依次提取叶子网格为核心网格，聚合其周围的同组邻居网格，聚合规则是邻居网格中任意一个体的属性与核心网格属性相同则为同组，因为叶子网格内的个体都是同组的。

5) 按距离就近原则，聚合剩余的非核心网格 (主要是单个体的网格)。聚类结束。

2.2 定义及公式描述

为了更准确地介绍该算法，下面给出算法中使用的定义及公式。

定义1 场景面积定义为p=L*W，其中，L、W分别代表场景的长和宽，场景中的坐标用 (x, y) 表示。

定义2 人群疏散个体数据集定义如下：

E={e_i, i=1, 2, …, num}

其中，e_i表示在数据集中的第i号个体，num是个体总数，p_i和g_j分别表示第i号个体和j号网格的小组属性, j=1, 2, …, n，n是非空叶子网格数目。

定义3 个体数据集E到场景S的映射是E→S，被定义为S={e_i(x, y)}，其中，e_i是E中第i号个体 (1≤i≤num)；(x, y) 是场景中的坐标，1≤x≤W，1≤y≤L，e_i(x, y) 表示i号个体的位置。

定义4 同组个体属性设定，先求得j号网格内的个体序号，再确定网格内个体实际范围左下方及右上方的边界点 (x_ld, y_ld) 和 (x_ru, y_ru)，就可以算出中心位置 (x_m, y_m)(如图 1所示)，得到同组个体的邻域半径r_j，从而确定同组内个体的属性值p_i(在实际仿真中，p_i是个体间的关系阈值，而个体间的关系值则在初始化时给定的关系矩阵确定)。

定义5 网格密度den(c_j)，表示网格第j号叶子网格c_j的密度 (1≤j≤n)，n是叶子网格的总数。den(c_j)=count(c_j)/s(c_j)，其中count()、s() 分别是计算网格内个体数目和个体所占实际面积的函数。如图 2所示，实际面积是通过网格内个体实际范围左下方及右上方的边界点 (x_ld, y_ld) 和 (x_ru, y_ru) 计算得到的。

定义6 核心网格是包含的个体数目大于1的叶子网格且核心网格数目不大于k。如图 3所示，每个核心网格的邻居网格是和它直接相连的网格，最多有8个。

2.3 折半聚类算法流程

算法 折半聚类。

输入 E, S, k；

输出 G(包含k个分组的个体序号)。

1) 外层循环，到所有格子为空或格子内个体同组为止。

2) 判断是非二等分当前j号网格，计算r_j，若网格为空或内个体到中心的距离均不大于r_j则停止当前网格划分，标记属性并计算当前网格密度den(c_j)，再转向其他网格；否则，二等分当前网格。

3) 直到生成全部叶子网格，循环结束。

4) 按照den(c_j) 非递增排序叶子网格，并设置网格属性g_j的值。

5) 内层循环，检查非空格子是否为空，遍历完为止。

6) 聚合核心网格周围的邻居网格并把个体属性值都更新成核心网格的属性值g_j。

7) 直到遍历完核心网格或者其数目达到k，则结束循环。

8) 若有剩余的非核心叶子网格，则归并到离其最近的核心网格; 否则转向9)。

9) 输出聚类结果。

2.4 算法时间复杂度分析

对于同样规模的数据集，数据量是num，聚类成k组。下面简要分析k-medoids、STING和折半聚类算法的时间复杂度。

k-medoids算法，不仅对初始中心点的选择比较敏感，总体准确率较低，而且聚类过程需要反复迭代，每次更新中心点时都要遍历所有数据，所以聚类效率较低，其平均时间复杂度是O (k(num-k)²)^[22]。

与之相比，STING算法的聚类效率较高。该算法创建网格信息表时，只需要计算相关网格的信息，其划分网格的时间复杂度是O(n)^[23](n是底层网格数目，本文中n通常取num的1/4)，若再计算选择和归并核心网格时间，即使不重复访问邻近网格，其时间复杂度也是O(n(n-1) /2)。总体时间复杂度是O(n²) 级的。该算法的聚类效率、质量都取决于网格结构最低层的划分粒度，随着粒度加细，其处理的代价会显著增加。在人群疏散聚类实验中，其处理时间并不理想。

而折半聚类算法，划分网格相当于建立一棵没有度为1的节点的二叉树，所以其时间复杂度仅为O(2n-1)，n是度为2的叶子网格数目，网格总数最大为num，所以n最差取值 (num+1) /2，最好取值k，所以平均复杂度是O(k+(num-1) /2)；因为该算法保证同一个网格内的个体同组，所以选择和归并核心网格时，可以直接归并成k组网格，所以其平均时间复杂度是O((k²-1) n/(2k)-(k-1) /2);若还有剩余的叶子网格，设其数目为m(m不大于n-k)，则归并它们的时间复杂度为O(km)。

综上所述，折半聚类算法的总体时间复杂度为O((k²-1) n/(2k)+(k+1) m+(num-k)/2-1) 也就是O (kn+km+num/2)，即O(cn)，c是常数，显然这是个O(n) 级接近线性时间的复杂度。

3 仿真实验

为了展示折半聚类算法 (BCA) 在人群疏散过程中的效果，本文采用了Matlab R2013a作为仿真平台，在300×250的矩形场景中，对于多种规模的人群疏散的聚类效果，同k-medoids算法和STING算法在效率和准确率两方面分别作了对比实验；而在3.3节的实验中，为了更直观地演示分组效果，则采用Microsoft.Net FrameWork 4.5框架，以Mcrisoft Visual Studio 2012作为编译环境，并配置了开放场景图形库3.2.1版 (OpenSceneGraph-3.2.1，OSG-3.2.1)，最终以三维造型演示行人群体。

3.1 聚类效率的对比实验

本实验针对300、500、700、900、1 100共5种规模的人群疏散的聚类效率进行对比，分别作了10组实验，记录了k-medoids、STING、BCA这三种算法的运行时间，取其平均值为对比数据，其实验数据平均值如表 1所示。

从表 1的实验数据可以说明，在聚类效率上BCA最高，STING算法次之，k-medoids算法最差。从表 1中还能看出随着人群规模逐渐增大，各自的时间也呈上升趋势，但BCA耗时最少也最平稳，而k-medoids算法和STING算法都有不同程度的起伏变化。对比分析表 1中的数据，本文可以计算出BCA聚类耗时平均仅是STING算法的48.3%，k-medoids算法的13.9%。

3.2 聚类准确率的对比实验

本实验针对300、500、700、900、1 100共5种规模的人群疏散的聚类准确率进行对比，用BCA、STING、k-medoids三种算法进行对比实验，分别作了10组实验，取其平均值为对比数据。而聚类准确率则是正确个数与事先给定的组内个体数目的比值 (聚类分组后，每组的个体序号与事先给定的该组个体序号一一匹配，记录正确的数目，与该组给定的个体数目的比值就是该组的准确率，各组准确率加和求得平均值，就是总的准确率)。因为人群中的社会关系是客观存在的，所以仿真程序会事先给定人群的关系矩阵，为了便于比较，人群里个体间并非人人都有关系，而是分成人数不等的多个朋友圈和一部分互不认识的陌生人，并且这些朋友圈间两两没有交集，于是每个朋友圈就是一个事先给定的分组，单个孤立的陌生人归入与距离 (即该个体到组心位置的距离) 最近的分组，最后只要把聚类结果和这些分组进行匹配就可以得到聚类的准确率了。实验数据平均值如表 2所示。

从表 2的实验数据可以看出，k-medoids的准确率最低，平均仅是BCA准确率的50%，这个和该算法自身特点有关，虽然它比k-means算法有较强的处理噪声点的能力，但是对于极端数据点处理还是较弱，人群中的孤立陌生人给它造成了很大的麻烦；而相对而言，STING算法的准确率就很高，平均能达到BCA准确率的88%，当然随着人群规模增加，STING算法的准确率也在下降，这同它均分网格的划分方式有关，人越多人群分布就可能越复杂，不仅其精度降低，其耗时也会大幅增加。

3.3 聚类后的人群疏散实验

为了展示加入分组信息后的人群疏散的效果，本实验在场景 (300 m×250 m) 中，仿真了规模是300人的疏散效果。其中，初始化状态如图 4；分组后效果如图 5，图 5中不同颜色代表不同的分组。

在向着出口疏散过程中，聚类后同组的个体会向着一起聚拢，而且为了跟上同伴，同组个体的速度基本保持一致。这类同组个体的聚团运动现象如图 6所示，而人群出门时形成拱形的“拱效应”则如图 7所示。

上面的仿真实验的结果表明，本文提出的折半聚类算法很适合用于人群疏散仿真中的聚类分组。在同样规模、同样场景下，对设定同样社会关系的疏散人群进行聚类，其优点有如下：

1) 在聚类效率上有显著优势。具体表现是聚类平均耗费的时间，BCA是STING算法的48.3%，仅是k-medoids算法的13.9%。

2) 在聚类精度上有明显提高。具体表现是聚类的平均准确率，BCA比STING算法提高了14%，更比k-medoids算法提高了100%。

3) 聚类后聚团运动现象明显。具体表现是在社会力模型中添加了行人个体的分组信息后，个体在运动过程中的“聚团现象”非常明显，更加符合人群疏散的现实情况。

4 结语

在人群疏散的问题研究中，为了克服社会力模型没有考虑人群中人际关系的缺陷，从而更真实地模拟人群疏散现象，本文运用CBA对疏散人群进行聚类，从而快速、准确地得到了个体的分组信息。本文把两种经典的聚类算法：k-medoids和STING，同CBA作了对比，既从理论上分析了这三种算法的时间复杂度，又经过了反复实验对比，验证了k-medoids算法和STING算法，在人群疏散过程中进行聚类时，无论从效率上还是从准确率上都不如CBA。

尽管如此，本文的研究仍显粗糙，比如本文还没有尝试对无人际关系的数据集进行聚类，所以，不好说该算法有良好的适应性；另外，虽然通过实验可以观察到孤立陌生人的数量将会影响聚类结果的准确率，但还没有定量地对其研究分析，后面将进一步在通用数据集上进行实验，完善实验细节参数，以便更进一步地改进、完善该算法。