多要素约束下的非法游行路径动态预测方法*

邓 敏，徐 亮，石 岩，陈袁芳，罗 靓，郭艺文

(中南大学地球科学与信息物理学院，湖南 长沙 410083)

1 引言

非法游行是一种未经法律许可在特定时间与地点聚集，沿城市主要道路移动以企图扩大社会影响力、严重危害公共安全、扰乱社会秩序的突发群体事件[1-4]。对非法游行群体的移动路径进行动态、精准预测将有助于辅助公安部门制定区域警力布控方案，从而最大程度减少事件的社会危害性[5]。

社会学和心理学领域的学者们在非法游行事件过程分析方面展开了相关研究[6]。其中，社会学领域研究主要从发生机理和发展过程的视角进行事件成因分析与全过程阶段划分。例如，毛振军等[7]通过非法游行事件的成因与区域风险分析，在制度和网络舆情监控等方面提出了应对政策；魏玖长等[8]从事件发展过程出发，将群体事件划分为形成、强化、执行和解体4个阶段。心理学领域研究则侧重于分析事件不同发展阶段参与者的心理与情绪状态规律及其对事件后续发展的影响。例如，张赛宜[9]借助群体事件的内部和外部推理分析来理解群体事件的形成过程；代珊[10]通过分析参与者在事件不同阶段的心理变化，提出系统的预防应对策略。在对群体事件的定性分析基础上，相关学者分别从微观和宏观2个视角构建仿真模型，定量分析群体的动态移动过程。其中，微观模型基于个体之间以及个体与事件场景间的相互作用分析，推断事件中每个参与者的未来运动趋势。例如，社会力模型[11,12]在个体运动受力驱动的假设下，综合考虑个体动机、相邻个体施加的从众吸引力以及障碍物或边界等形成的阻碍力计算个体运动合力，实现对个体运动趋势的仿真模拟；元胞自动机模型[13-15]将个体视为元胞单元，通过量化目的地吸引力和障碍物阻碍力，模拟各元胞的运动趋势。微观模型难以有效顾及事件群体的整体特征，且个体受力建模所需计算量较大。为此，一些学者从宏观视角对群体事件进行过程建模[16]。例如，巩青歌等[17]考虑多类城市地理要素对游行群体的吸引力构建路网图结构，并利用布谷鸟优化算法预测群体在游行过程中的重要兴趣点POI(Point of Interest)转移节点；Hughes等[18-20]考虑目的地对事件群体的吸引力，结合群体密度和速度信息推算群体到达目的地的最快移动路径。

文献[21]研究表明，非法游行的爆发源于征地拆迁、劳资纠纷等导致部分群体利益受损，该群体商定在特定时间与地点聚集，沿商定路线移动以尽可能扩大事件的社会影响范围。在非法游行事件核心内涵的指导下，本文耦合事件场景中吸引要素和排斥要素对游行群体的综合影响，通过一种多要素约束下的路径动态优化，实现游行移动路径预测(如图1所示)，主要包括：(1)耦合场景多要素的动态加权无向图构建。结合事件场景多要素空间分布和游行群体实时空间位置计算路段动态影响力，从而将城市路网建模为一个加权无向图。(2)多要素约束的非法游行路径动态预测。基于动态加权无向图，建立顾及多要素影响力的游行路径优化目标函数，并借助动态规划的思想计算目标函数最优解，实现游行群体的移动路径预测。

Figure 1 Framework of the multi-factor constrained approach for the dynamic prediction of illegal parade paths

2 耦合场景多要素的动态加权无向图构建

文献[22]指出，非法游行事件同时涉及诉求者和执法人员。其中，诉求者旨在通过游行示威以扩大事件的社会影响范围，并向相关机构施压来维护受损利益；执法人员则负责秩序管控，阻止非法游行事件的恶化发展。基于此，本文将非法游行影响要素分为吸引要素(如各类POI、多级城市道路等[23])和排斥要素(如公安局、武(特)警中队、派出所等)；进而，借鉴文献[17]提出的各类要素对游行群体的影响力分析结果，构建非法游行多影响要素体系，如表1所示。并结合多影响要素与游行群体实时空间位置构建动态加权无向图。

首先，将城市路网建模为一个无向图G=(V,E,A),其中，路段节点集合V={v1,v2,…,vn}；路段集合E={e1,e2,…,em}；A∈Rn×n表示路段节点间的邻接矩阵，若vi与vj相邻，aij值为1，否则，aij值为0。距离衰减理论表明，地理要素间的相互作用随距离增大而减小[24,25]。于是，给定任一s类POI吸引要素A_poisi，对位于位置gj的游行群体产生的影响力可以表达为：

Table 1 Influence factors of illegal parade

INF(A_poisi,gj)=

I(A_pois)*K[N_Dist(A_poisi,gj)]

K[N_Dist(A_poisi,gj)]=

exp{-[N_Dist(A_poisi,gj)]2/h2}

(1)

其中,I(A_pois)表示s类POI要素的固有吸引力；N_Dist(A_poisi,gj)表示A_poisi与当前游行群体所处位置间的路网距离；K(·)表示高斯空间权重函数[26]；带宽h表示游行群体在一定时间内的移动距离阈值。

同理，可以计算任一路段ei,j的吸引力以及任一l类POI排斥要素R_poili的排斥力，分别记为INF(ei,j,gj)和INF(R_poili,gj)。进而，游行群体在当前时刻受到路段ei,j的综合影响力可表达为：

Q(ei,j,gj)=a1*INF(ei,j,gj)+

(2)

其中,S和L分别表示匹配至路段ei,j上POI吸引要素和排斥要素集合，B和D分别表示路段ei,j上类别为s和l的POI编号集合；权重系数a1、a2、a3用来衡量不同影响要素的重要程度，满足a1+a2+a3=1，本文采用等权处理，即a1=a2=a3=1/3。结合无向图G的邻接矩阵A构建加权邻接矩阵WA，表达为：

(3)

其中，qij表示路段ei,j的综合影响力，Q表示综合影响力矩阵。

于是加权无向图WG=(V,E,WA)。

3 基于多要素约束优化的非法游行路径预测

非法游行事件可以分为游行终点已知和游行终点未知2类[17,27]。针对游行终点未知的情况，以游行群体当前位置节点vi为圆心、以移动距离阈值h为半径构建空间邻域，将与该邻域相交的所有路段作为候选目的路段集合，并对集合中每条候选路段ei,j计算适宜度F(ei,j)，表达为：

(4)

其中,I(ei,j)、I(A_pois)和I(R_poil)分别表示路段ei,j、s类POI吸引要素的数量和l类POI排斥要素的固有影响力；ns和nl分别表示路段ei,j上s类POI吸引要素的数量和l类POI排斥要素的数量。进而，根据适宜度对所有候选路段进行降序排列，选取前c个侯选路段的节点构成终点集合。

基于游行群体企图扩大事件影响范围的心理特征[21]以及移动单向性特征，游行路径应满足：(1)途经路段的影响力累加值最大，即加权无向图中路段的权重总值最小；(2)途经路段不再返回。基于此，构建以下目标函数：

(5)

其中,若群体在节点vi通过路段ei,j到达节点vj，则节点xi→j=1，否则xi→j=0；vs和vd分别表示游行起始和终止节点；n为无向图中节点个数。游行路径预测问题就转化为加权无向图中的最短路径搜索问题，对此本文采用Floyd算法[28-30]计算目标函数最优解，获得由当前节点vi到终止节点vd的游行路径path:ei,j→ej,k→…→eu,d。

Figure 2 An example of illegal parade path prediction

图2所示为一个终点未知游行事件路径预测简例，吸引要素包括：5个购物中心、2个政府单位、2个公园和4个等级的路段；排斥要素包含3个派出所。假设游行群体当前位于节点v5，通过以v5为圆心、以h=2 km为半径的空间邻域构建得到候选目的路段集合{e1,4,e2,5,e3,4,e4,5,e4,8,e5,6,e5,9,e8,9,e9,10,e9,12}；进而计算每条候选路段的适宜度。以图2c中路段e5,9为例，适宜度F(e5,9)=(1/3)*3+(1/3)*2=1.67，选取适宜度最大的路段节点构成候选终点集合{v4,v8}。然后构建加权无向图，如图2d所示，其中路段e5,9的综合影响力Q(e5,9)=(1/3)*2.34+(1/3)*1.56=1.3，该路段在无向图中的权重wa5,9=1/1.3=0.77。最后通过目标函数求解得到节点v5到候选终点A和B的游行路径分别为path:e5,4和path:e5,4→e4,8，分别如图2e和图2f所示。

4 实验分析

本文采用主题搜索获取的2006年南京市(http://news.ifeng.com/c/7fYZP2zsK3Y)、2007年宁波市(http://news.hexun.com/2007-12-18/102350333.html)和2018年江山市(http://www.21js.com/html/2018/01/275434.shtml)非法游行事件，利用自然语言处理与信息检索NLPIR(Nature Language Processing & Information Retrieval)大数据语义智能分析平台[31]提取上述新闻中描述游行过程的地名或者道路名称，进一步借助百度地图搜索提取的地名或道路名称实现地名或者道路名称的地图匹配，从而获得事件中游行群体的真实转移路径。通过与现有方法[11,17,32]进行对比来验证本文方法的有效性。实验中，路网数据来自OpenStreetMap开源地图，POI和公安机关空间分布数据来自百度地图。下面采用本文方法分别对终点未知和终点已知的游行路径进行预测分析。

4.1 终点未知的游行路径预测

首先，将移动距离阈值h设置为所有游行事件群体移动路径长度均值，选择适宜度最高的2条路段作为候选目的路段。以江山市非法游行事件为例，假设游行群体在江山小商品市场聚集，以此为起点展开游行示威。通过分析发现中山路适宜度最高，其次为县河东路，由于2条路段相交，共有3处候选终点Ⅰ、Ⅱ、Ⅲ，如图3a所示。其中，Ⅰ、Ⅱ、Ⅲ与该事件中真实终点的空间距离仅为132 m, 110 m和135 m。进而，分别以Ⅰ、Ⅱ、Ⅲ为终点进行游行路径预测，可得pathⅠ:(A)环城南路→(B)鹿溪南路→(C)中山路；pathⅡ:(A)环城南路→(B)鹿溪南路→(C)中山路；pathⅢ:(A)环城南路→(B)鹿溪南路→(C)中山路→(D)县河东路，分别如图3b～图3d所示。

4.2 终点已知的游行路径预测

实验中移动距离阈值h设置为各案例中游行起点到终点的空间距离。图4为2006年南京市非法游行事件移动路径预测结果，该事件中游行群体真实移动路径为：北京西路→(A)鼓楼广场→(B)北京东路→市政府，如图4a所示。南京市公安局警务工作服务站位于图4b中区域I上方路段，考虑到非法游行群体在游行过程中会尽可能避开公安部门，仅考虑排斥要素的方法预测得到非法游行群体经过区域I时选择远离公安部门的路线，然后经北京东路抵达南京市政府，如图4b所示。由于没有考虑对游行具有吸引作用的要素，导致该结果偏离真实路径。图4c和图4d分别为仅考虑吸引要素的方法和本文方法的游行路径预测结果，可以发现2组结果路径一致。通过分析发现，区域II中真实路径周边分布若干具有强吸引力的旅游景点(如鸡鸣寺、和平公园、考试院钟楼)，但由于本文方法仅考虑匹配至路网上的多要素对群体的影响，未顾及邻近路段多要素空间分布对游行群体的影响，导致预测结果与真实路径存在差异。

Figure 3 Results of parade paths prediction with unknown destinations

Figure 4 Results of parade paths prediction in Nanjing

图5给出了2007年宁波市非法游行事件的移动路径预测结果。

Figure 5 Results of parade paths prediction in Ningbo

其中，图5a为真实游行路径：解放南路→(A)开明街→(B)中山东路→(C)河清北路→宁波市政府。图5b中区域I和区域II下方路段分布有宁波市公安局交通警察局海曙大队一中队、宁波市公安局江东分局东郊派出所、宁波市福明派出所、东胜派出所大河社区警务室、庆安社区警务室、张斌社区警务室、江东公安分局东胜派出所113医院警务联络室以及东柳派出所华侨城社区警务室，仅考虑排斥要素的方法认为游行群体在经过这些区域时将选择远离以上警力部门的上方路段；然而，排斥要素法预测的移动路段上POI数量少且部分路段(如和义路)等级较低，游行群体难以扩大事件社会影响力，导致该预测路径与真实路径不符。图5c中区域Ⅳ和区域V包含海曙区政府、海曙区纪检委、海曙区人大常委会等强吸引要素，若考虑吸引要素的影响效应，游行群体将沿着区域Ⅳ和区域V中路段移动；实际上，该区域中道路(C)、道路(D)和道路(F)的等级较低且分布有海曙公安分局鼓楼派出所、宁波市公安局等强排斥要素，游行群体在选择移动路径时将在吸引要素与排斥要素之间做出权衡，从而仅考虑吸引要素的方法无法准确预测真实路径。本文方法由于同时考虑了吸引要素和排斥要素对游行群体的综合影响，图5d所示游行路径预测结果中除区域Ⅵ和Ⅶ外与真实路径保持完全一致。

2018年江山市非法游行事件路径预测结果如图6所示，图6a为该事件中游行群体的真实移动路径：小商品市场→(A)环城南路→(B)鹿溪南路→(C)中山路→市政府。若仅考虑排斥要素，由于区域I中的路段缺少对游行群体实行管制的公安部门，预测得到游行群体主要在该区域中沿最短路径抵达江山市政府，如图6b所示；然而，该区域仅包含少量吸引要素且路段影响力较低，难以实现游行群体企图扩大事件影响范围的动机，从而导致预测结果与真实游行路径存在显著差异。此外，对比图6a与图6c、图6d可以发现，仅考虑吸引要素的方法和本文方法均可得到完全符合现实的游行路径。

Figure 6 Results of parade paths prediction in Jiangshan

4.3 预测路径定量评价

为了进一步验证本文方法的优越性，下面采用长度吻合度、路段吻合度和节点吻合度3个评价指标对不同方法得到的游行路径预测结果进行量化对比分析。其中，长度吻合度为预测路径中与真实路径一致路段长度与预测路径总长度之比；路段吻合度为预测路径中与真实路径一致路段条数与预测路径路段总条数之比；节点吻合度为预测路径中与真实路径一致的路网节点个数与预测路径总节点数之比。

表2为分别采用3种方法预测的非法游行路径定量评价结果，可以发现：(1)在3个游行事件中，仅考虑排斥要素的方法得到的预测路径在3个吻合度指标方面均低于其他2种方法的预测结果；(2)2018年江山市和2006年南京市非法游行事件场景中所涉排斥要素较少，因此仅考虑吸引要素的方法和本文方法预测结果精度一致；(3)对于2007年宁波市非法游行事件，本文方法预测路径在长度、路段和节点方面的吻合度均明显高于其他方法的；(4)针对3个非法游行事件，仅考虑排斥要素的方法预测结果在3个维度的吻合度均值均低于60%，仅考虑吸引要素的方法预测结果的长度、路段和节点平均吻合度分别为77%，77%和83%，而本文方法预测结果与真实路径的吻合度最高。

此外，通过与基于元胞自动机[32]的路径预测方法对比，分析本文方法运行时间情况。文献[32]结合群体成员移动的特点，借助元胞自动机对群体事件进行建模，通过将事件发生的场景划分为若干个元胞单元，进而分析元胞所受的多种约束力(如吸引力、排斥力)，最后根据元胞的综合受力确定群体成员的路径选择，实现对移动路径的预测。程序运行环境：Windows10，Intel(R)Core(TM)i7 CPU，使用Matlab 2019a实现算法。表3为基于元胞自动机的方法和本文方法运行时间对比结果，可以发现：(1)在基于元胞自动机的方法中，通过将元胞的大小分别设定为不同大小(10 m, 15 m, 20 m, 25 m和30 m)，运行时间会随着元胞单元增大而降低；(2)3个非法游行案例中，本文方法运行时间均显著低于基于元胞自动机方法的，这是由于基于元胞自动机的方法从微观视角出发，将移动空间划分为若干个元胞单元，使建模的计算量增大，因而运行时间较长，而本文方法从宏观视角出发，能够快速对游行群体的路径预测进行建模。

综上所述，本文方法同时顾及非法游行事件场景中的吸引要素和排斥要素对游行路径选择产生的综合影响效应，能够在非法游行群体心理动机驱动下有效掌握群体移动规律，使得预测结果更加稳定和可靠。

Table 2 Quantitative evaluation results of predicted illegal parade paths by different methods

Table 3 Running time of illegal parade paths prediction by different methods

5 结束语

本文针对非法游行事件提出了一种多要素约束下的非法游行路径动态预测方法，通过与现有方法进行对比实验发现，本文方法能够耦合事件场景中多要素对游行群体的吸引和排斥作用，可以获得更加稳定、准确的非法游行路径预测结果。未来研究将借助社交媒体的数据，顾及邻近场景多要素空间布局对游行群体产生的更加复杂的综合效应，实现对非法游行事件的全生命周期时空过程推理。