多要素約束下的非法游行路徑動態預測方法*

鄧 敏，徐 亮，石 巖，陳袁芳，羅 靚，郭藝文

(中南大學地球科學與信息物理學院，湖南 長沙 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)多要素約束的非法游行路徑動態預測?；趧討B加權無向圖，建立顧及多要素影響力的游行路徑優化目標函數，并借助動態規劃的思想計算目標函數最優解，實現游行群體的移動路徑預測。

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 結束語

本文針對非法游行事件提出了一種多要素約束下的非法游行路徑動態預測方法，通過與現有方法進行對比實驗發現，本文方法能夠耦合事件場景中多要素對游行群體的吸引和排斥作用，可以獲得更加穩定、準確的非法游行路徑預測結果。未來研究將借助社交媒體的數據，顧及鄰近場景多要素空間布局對游行群體產生的更加復雜的綜合效應，實現對非法游行事件的全生命周期時空過程推理。