李 焱，劉 弘，鄭向偉

(1.山東師范大學(xué) 信息科學(xué)與工程學(xué)院,濟南 250014; 2.山東省分布式計算機軟件新技術(shù)重點實驗室,濟南 250014)

折半聚類算法在基于社會力的人群疏散仿真中的應(yīng)用

李 焱1,2，劉 弘1,2*，鄭向偉1,2

(1.山東師范大學(xué) 信息科學(xué)與工程學(xué)院,濟南 250014; 2.山東省分布式計算機軟件新技術(shù)重點實驗室,濟南 250014)

(*通信作者電子郵箱1304788495@qq.com)

運用社會力模型(SFM)模擬人群疏散之前，需要先對人群進行聚類分組; 然而，k中心聚類(k-medoids)和統(tǒng)計信息網(wǎng)格聚類(STING)這兩大傳統(tǒng)聚類算法，在聚類效率和準(zhǔn)確率上都不能滿足要求。針對這個問題，提出了折半聚類算法(BCA)。該算法結(jié)合了圍繞中心點聚類和基于網(wǎng)格聚類兩類方式，并利用二分法查找思想劃分網(wǎng)格，不需要反復(fù)聚類。先將數(shù)據(jù)用二分法劃分成網(wǎng)格，再根據(jù)網(wǎng)格內(nèi)數(shù)據(jù)密度選出核心網(wǎng)格，接著以核心網(wǎng)格為中心將鄰居網(wǎng)格聚類，最后按就近原則歸并剩余網(wǎng)格。實驗結(jié)果表明，在聚類時間上，BCA平均僅是STING算法的48.3%，不到k-medoids算法的14%；而在聚類準(zhǔn)確率上，k-medoids算法平均僅是BCA的50%，STING算法平均也只是BCA的88%。因此，BCA無論在效率還是準(zhǔn)確率上都明顯優(yōu)于STING和k-medoids算法。

聚類算法；統(tǒng)計信息網(wǎng)格；k中心聚類；人群疏散仿真；社會力模型

0 引言

人群疏散研究涉及到避免踐踏等公共安全問題，是近年來研究的熱點。為了定量分析、模擬人群運動，很多研究人員已經(jīng)作了大量調(diào)查、實驗?zāi)酥潦枭⒀萘?xí)并收集了觀測數(shù)據(jù)，因此，很多研究人員轉(zhuǎn)向運用計算機模擬來仿真人群疏散， 也取得了很多成果，而以真人作模擬實驗會發(fā)生很多不受控制的情況，有一定危險性，而且實驗成本也很高。

1)人群疏散數(shù)學(xué)模型。

研究人員紛紛采用像排隊論之類的數(shù)學(xué)理論或思想，建立人群疏散仿真的數(shù)學(xué)模型，比如排隊模型[1-2]、格子氣模型[3-5]、元胞自動機模型[6-7]、基于代理的疏散模型[8-9]、社會力模型[10-13]等。這些模型大致可以分為兩類：微觀和宏觀[14]。其中，除排隊模型是宏觀模型，其余4個模型都是微觀模型。

文獻[1-2]結(jié)合排隊模型，更多地是從整體研究人群流動特性，但是沒有考慮個體間的作用和關(guān)系(如物理上的摩擦與碰撞、心理上的排斥與吸引等)，所以本文從個體間作用入手，運用微觀模型研究人群疏散問題。文獻[3-5]運用改進的格子氣模型模擬了人流狀態(tài)，文獻[5]還增加了對個體步長的調(diào)整；文獻[6-7]都利用元胞自動機模型研究了火災(zāi)時的人群疏散；文獻[8-9]則分別在平面建筑和多層建筑中運用基于代理的模型仿真人群疏散。以上文獻雖然都采用了微觀模型，具體研究了行人的步長、恐慌等個體因素，取得了較好的效果，但沒有涉及到個體間的相互作用。而文獻[10-13]則采用了社會力模型對人群疏散進行了微觀仿真研究, 尤為難得的是社會力模型描述了人群中的個體，在與其他個體及環(huán)境的相互作用力的作用下以期望速度向著給定目標(biāo)運動的狀態(tài)[13]。因此，本文采用了基于社會力模型的方法仿真人群疏散。

2)人群疏散的特征。

在人群疏散過程中，個體自身的心理狀態(tài)及個體間的相互作用可能影響人流運動，尤其在緊急狀態(tài)下，人群運動的盲目性、從眾性的特征更加顯著，這將導(dǎo)致較為典型的現(xiàn)象發(fā)生：

1)“瓶頸節(jié)點”。危急情況下，人流速度明顯加快，而相對于房間、中廳、走廊等位置，出口顯然會成為人流的目標(biāo)，極易因爭搶而降低通行效率，從而造成阻塞[11]，成為通行中的“瓶頸節(jié)點”。

2)盲目從眾。即個體行為很容易被其周圍人群的行為所影響[15]。因為不僅周圍人群的恐慌情緒會感染該個體，而且他們的行為也將影響該個體并引發(fā)衍生效應(yīng)。

3)聚團運動。即群體運動中關(guān)系親密的個體傾向于在運動中形成一個個的小團體，比如家庭、朋友、同學(xué)等。這些小組對疏散速度的影響是顯著的，但其影響是不確定的，有時能幫助個體快速找到出口，有時小組運動也會阻礙其他個體的運動。同組個體間的作用也呈現(xiàn)明顯的非線性特征[16]。

盡管社會力模型很好地模擬了“瓶頸節(jié)點”、出口“拱形效應(yīng)”“快即是慢”[11]等典型現(xiàn)象，也很細(xì)致地描述了個體自身的驅(qū)動力及個體與個體、個體與環(huán)境間的相互作用力，但是它忽略了現(xiàn)實中的人際關(guān)系，即人群在運動過程中，關(guān)系親密的人比如情侶、家庭等，不能有效地模擬聚團分組運動，那么，如何快速地識別出人群中的有關(guān)系的人并準(zhǔn)確地聚類成組，就成了模擬人群疏散中的重要一環(huán)。本文在社會力模型中增加了團組劃分信息，促使人群在社會力作用下進行聚團分組運動，以便更真實地模擬人群疏散。

本文把聚類算法用到了人群分組中，并把分組信息加入了社會力模型，用以仿真人群疏散，因為人群運動中分組可能隨時變化，這就需要聚類算法具有較高的速度和準(zhǔn)確度。本文通過對比統(tǒng)計信息網(wǎng)格(STatistical INformation Grid, STING)[17]算法和k中心聚類(k-medoids)[18]算法，在傳統(tǒng)的圍繞中心點聚類的思想上結(jié)合了網(wǎng)格劃分思想，并在劃分網(wǎng)格時引入了非均勻的折半劃分思想，提出了折半聚類算法(Binary Clustering Algorithm, BCA)，并嘗試把該算法運用到人群分組的聚類中；通過仿真實驗同傳統(tǒng)的STING和k-medoids兩種算法作對比，展現(xiàn)了折半聚類算法在速度和準(zhǔn)確度上的優(yōu)勢。

1 聚類算法

聚類算法大體分為基于劃分的、基于層次的、基于密度的、基于網(wǎng)格的、基于模型的、模糊聚類、基于圖論的、基于分形的、復(fù)雜網(wǎng)絡(luò)聚類、仿生法及核聚類等11種方法[19]。本文選取了其中兩種經(jīng)典的算法進行了人群分組聚類實驗：一種是基于劃分的k-medoids算法, 另一種是基于網(wǎng)格的STING算法，發(fā)現(xiàn)效果不佳。

k-medoids算法 它是最經(jīng)典的聚類算法k-means的延伸，不僅可以處理數(shù)值屬性類數(shù)據(jù)，還可以處理分類屬性類數(shù)據(jù)，并且它在處理存在“噪聲”和孤立點的數(shù)據(jù)時，比k-means更健壯、更有效，不像k-means那樣容易受極端數(shù)據(jù)影響。不過，它用于人群分組，運行時間很長，整體準(zhǔn)確度也較低，不能滿足人群分組的要求。

STING算法 它是傳統(tǒng)的基于網(wǎng)格的多分辨率聚類算法，將空間區(qū)域劃分為矩型單元。針對不同級別的分辨率，通常存在多個級別的矩形單元，這些單元形成了一個層次結(jié)構(gòu)；高層的每個單元被劃分為多個低一層的單元。每個網(wǎng)格單元屬性的統(tǒng)計信息(例如平均值、最大值和最小值)被預(yù)先計算和存儲[20]。相對于傳統(tǒng)的劃分算法，該算法具有時間復(fù)雜度較低、執(zhí)行效率較高、聚類準(zhǔn)確度也相對較高的優(yōu)點。

但是，由于STING算法采用了一個均勻劃分的方法來進行聚類，其聚類的質(zhì)量取決于網(wǎng)格結(jié)構(gòu)的最底層的粒度[21]。其實，由網(wǎng)格最低層粒度決定的不僅是聚類的質(zhì)量，還有聚類的時間復(fù)雜度，即粒度越粗(底層格子密度越低)，聚類的準(zhǔn)確度就越低，而時間復(fù)雜度也就隨之降低；反之則都會提高。因為人群分組對于實時性和準(zhǔn)確性都有較高要求，所以對于聚類算法，不僅要求質(zhì)量高還要滿足速度快，但是，在實驗過程中，發(fā)現(xiàn)STING算法中這兩個指標(biāo)是一對矛盾體，質(zhì)量高速度就會降低，而且STING算法因為算法自身的局限，它的準(zhǔn)確度本身就有瓶頸，而且所要付出的代價太大，時間耗費得太多不符合實時性要求。

針對人群分組的自身特點和要求，本文嘗試了一種非均勻的折半聚類方法，該方法在結(jié)合上面兩類算法的思想上增加了折半劃分的思路，即先把場景網(wǎng)格化，但這個網(wǎng)格化過程是基于折半思路的非均勻二分法劃分的過程，再利用圍繞中心點聚類的思想，找出核心網(wǎng)格(內(nèi)部個體密度高的網(wǎng)格)，然后進行聚類分組，這樣減少了最終的網(wǎng)格劃分?jǐn)?shù)量，提高了聚類效率。

2 折半聚類算法

人群的分布狀態(tài)隨著行人的運動隨時會發(fā)生變化，在整個場景中人群的局部疏密度也會發(fā)生變化，而折半聚類的方法可以區(qū)分疏密區(qū)域、粗分稀疏區(qū)域或舍棄空白區(qū)域、細(xì)分稠密區(qū)域，在提高準(zhǔn)確度的同時減少了網(wǎng)格數(shù)量。

2.1 算法思想及過程

折半聚類的思想是以二分法對整個場景劃分網(wǎng)格，劃分原則是網(wǎng)格中個體屬于同一屬性組(下簡稱同組)則不分，否則繼續(xù)二分。該算法整體分為如下三個階段。

首先，對整個場景進行二分的非均勻網(wǎng)格劃分，比較場景的邊長，把長邊均分兩半，形成兩個格子，再檢測每個格子，如果格子里是空的或者是同組的個體則停止，否則就把該格子按同樣規(guī)則二等分，這樣繼續(xù)二等分下去，直到格子為空或者格子里的個體都是同組的為止。這個過程類似以先根遍歷建立了一棵不含度為1節(jié)點的二叉樹，只不過樹葉都是同組個體或者空的網(wǎng)格。

其次，把最終的非空葉子網(wǎng)格聚成k(k是事先給定的，為了減少擁塞提高疏散效率，人群的最佳分組數(shù)目將取決于封閉場景中的出口數(shù)目，通常是其三倍)組，小組聚合的規(guī)則是以核心網(wǎng)格為中心聚合其周圍鄰居的葉子網(wǎng)格。首先把這些非空葉子網(wǎng)格按密度(密度等于格子內(nèi)的個體數(shù)目除以個體所占實際面積)非遞增排序，次序靠前的葉子網(wǎng)格的是核心網(wǎng)格，檢測核心網(wǎng)格周圍的鄰居葉子網(wǎng)格是否與其同組，同組則聚合，否則以剩余的葉子網(wǎng)格為核心網(wǎng)格繼續(xù)聚合，直到所有的葉子網(wǎng)格都檢測一遍。

最后，如果存在未同核心網(wǎng)格聚合的網(wǎng)格(主要是只含個體的網(wǎng)格)，就把這些網(wǎng)格中的個體同前面完成聚合的小組中心位置對比距離，聚合到最近的網(wǎng)格小組中。

過程 折半聚類。

1)外層循環(huán)。以場景為根，用先序遍歷建立一棵二叉樹。先二等分較長的邊，形成左右子樹即兩個網(wǎng)格，再檢測左子樹即第一個格子，若格子內(nèi)的個體不同組則繼續(xù)二等分，否則，若同組或為空，則設(shè)為葉子格子，然后檢測右子樹即第二個格子，依此類推，直到所有的格子為同組或為空，即生成了所有的葉子格子。

2)內(nèi)層循環(huán)。檢測非空網(wǎng)格內(nèi)的個體是否同組。以個體的實際中心為中心位置，即以邊界個體的坐標(biāo)而不是網(wǎng)格頂點坐標(biāo)來計算中心位置，以個體到中心距離的均值為鄰域半徑，距離在半徑內(nèi)的個體則同組并設(shè)置同組屬性，否則是異組。

3)按網(wǎng)格密度非遞增排序葉子網(wǎng)格。

4)按順序依次提取葉子網(wǎng)格為核心網(wǎng)格，聚合其周圍的同組鄰居網(wǎng)格，聚合規(guī)則是鄰居網(wǎng)格中任意一個體的屬性與核心網(wǎng)格屬性相同則為同組，因為葉子網(wǎng)格內(nèi)的個體都是同組的。

5)按距離就近原則，聚合剩余的非核心網(wǎng)格(主要是單個體的網(wǎng)格)。聚類結(jié)束。

2.2 定義及公式描述

為了更準(zhǔn)確地介紹該算法，下面給出算法中使用的定義及公式。

定義1 場景面積定義為p=L*W，其中，L、W分別代表場景的長和寬，場景中的坐標(biāo)用(x,y)表示。

定義2 人群疏散個體數(shù)據(jù)集定義如下：

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

其中，ei表示在數(shù)據(jù)集中的第i號個體，num是個體總數(shù)，pi和gj分別表示第i號個體和j號網(wǎng)格的小組屬性,j=1,2,…,n，n是非空葉子網(wǎng)格數(shù)目。

定義3 個體數(shù)據(jù)集E到場景S的映射是E→S，被定義為S={ei(x,y)}，其中，ei是E中第i號個體(1≤i≤num)；(x,y)是場景中的坐標(biāo)，1≤x≤W，1≤y≤L，ei(x,y)表示i號個體的位置。

定義4 同組個體屬性設(shè)定，先求得j號網(wǎng)格內(nèi)的個體序號，再確定網(wǎng)格內(nèi)個體實際范圍左下方及右上方的邊界點 (xld,yld)和(xru,yru)，就可以算出中心位置 (xm,ym)(如圖1所示)，得到同組個體的鄰域半徑rj，從而確定同組內(nèi)個體的屬性值pi(在實際仿真中，pi是個體間的關(guān)系閾值，而個體間的關(guān)系值則在初始化時給定的關(guān)系矩陣確定)。

定義5 網(wǎng)格密度den(cj)，表示網(wǎng)格第j號葉子網(wǎng)格cj的密度(1≤j≤n)，n是葉子網(wǎng)格的總數(shù)。den(cj)=count(cj)/s(cj)，其中count()、s()分別是計算網(wǎng)格內(nèi)個體數(shù)目和個體所占實際面積的函數(shù)。如圖2所示，實際面積是通過網(wǎng)格內(nèi)個體實際范圍左下方及右上方的邊界點 (xld,yld)和(xru,yru)計算得到的。

圖1 網(wǎng)格內(nèi)個體實際邊界Fig. 1 Individual’s actual boundaries in a grid

圖2 網(wǎng)格密度Fig. 2 Grid density

定義6 核心網(wǎng)格是包含的個體數(shù)目大于1的葉子網(wǎng)格且核心網(wǎng)格數(shù)目不大于k。如圖3所示，每個核心網(wǎng)格的鄰居網(wǎng)格是和它直接相連的網(wǎng)格，最多有8個。

圖3 核心網(wǎng)格及其鄰居網(wǎng)格Fig. 3 Core grid and its neighbors

2.3 折半聚類算法流程

算法 折半聚類。

輸入E,S,k；

輸出G(包含k個分組的個體序號)。

1)外層循環(huán)，到所有格子為空或格子內(nèi)個體同組為止。

2)判斷是非二等分當(dāng)前j號網(wǎng)格，計算rj，若網(wǎng)格為空或內(nèi)個體到中心的距離均不大于rj則停止當(dāng)前網(wǎng)格劃分，標(biāo)記屬性并計算當(dāng)前網(wǎng)格密度den(cj)，再轉(zhuǎn)向其他網(wǎng)格；否則，二等分當(dāng)前網(wǎng)格。

3)直到生成全部葉子網(wǎng)格，循環(huán)結(jié)束。

4)按照den(cj)非遞增排序葉子網(wǎng)格，并設(shè)置網(wǎng)格屬性gj的值。

5)內(nèi)層循環(huán)，檢查非空格子是否為空，遍歷完為止。

6)聚合核心網(wǎng)格周圍的鄰居網(wǎng)格并把個體屬性值都更新成核心網(wǎng)格的屬性值gj。

7)直到遍歷完核心網(wǎng)格或者其數(shù)目達到k，則結(jié)束循環(huán)。

8)若有剩余的非核心葉子網(wǎng)格，則歸并到離其最近的核心網(wǎng)格; 否則轉(zhuǎn)向9)。

9)輸出聚類結(jié)果。

2.4 算法時間復(fù)雜度分析

對于同樣規(guī)模的數(shù)據(jù)集，數(shù)據(jù)量是num，聚類成k組。下面簡要分析k-medoids、STING和折半聚類算法的時間復(fù)雜度。

k-medoids算法，不僅對初始中心點的選擇比較敏感，總體準(zhǔn)確率較低，而且聚類過程需要反復(fù)迭代，每次更新中心點時都要遍歷所有數(shù)據(jù)，所以聚類效率較低，其平均時間復(fù)雜度是O(k(num-k)2)[22]。

與之相比，STING算法的聚類效率較高。該算法創(chuàng)建網(wǎng)格信息表時，只需要計算相關(guān)網(wǎng)格的信息，其劃分網(wǎng)格的時間復(fù)雜度是O(n)[23](n是底層網(wǎng)格數(shù)目，本文中n通常取num的1/4)，若再計算選擇和歸并核心網(wǎng)格時間，即使不重復(fù)訪問鄰近網(wǎng)格，其時間復(fù)雜度也是O(n(n-1)/2)?？傮w時間復(fù)雜度是O(n2)級的。該算法的聚類效率、質(zhì)量都取決于網(wǎng)格結(jié)構(gòu)最低層的劃分粒度，隨著粒度加細(xì)，其處理的代價會顯著增加。在人群疏散聚類實驗中，其處理時間并不理想。

而折半聚類算法，劃分網(wǎng)格相當(dāng)于建立一棵沒有度為1的節(jié)點的二叉樹，所以其時間復(fù)雜度僅為O(2n-1)，n是度為2的葉子網(wǎng)格數(shù)目，網(wǎng)格總數(shù)最大為num，所以n最差取值(num+1)/2，最好取值k，所以平均復(fù)雜度是O(k+(num-1)/2)；因為該算法保證同一個網(wǎng)格內(nèi)的個體同組，所以選擇和歸并核心網(wǎng)格時，可以直接歸并成k組網(wǎng)格，所以其平均時間復(fù)雜度是O((k2-1)n/(2k)-(k-1)/2);若還有剩余的葉子網(wǎng)格，設(shè)其數(shù)目為m(m不大于n-k)，則歸并它們的時間復(fù)雜度為O(km)。

綜上所述，折半聚類算法的總體時間復(fù)雜度為O((k2-1)n/(2k)+(k+1)m+(num-k)/2-1)也就是O(kn+km+num/2)，即O(cn)，c是常數(shù)，顯然這是個O(n)級接近線性時間的復(fù)雜度。

3 仿真實驗

為了展示折半聚類算法(BCA)在人群疏散過程中的效果，本文采用了Matlab R2013a作為仿真平臺，在300×250的矩形場景中，對于多種規(guī)模的人群疏散的聚類效果，同k-medoids算法和STING算法在效率和準(zhǔn)確率兩方面分別作了對比實驗；而在3.3節(jié)的實驗中，為了更直觀地演示分組效果，則采用Microsoft .Net FrameWork 4.5框架，以Mcrisoft Visual Studio 2012作為編譯環(huán)境，并配置了開放場景圖形庫3.2.1版(OpenSceneGraph-3.2.1， OSG-3.2.1)，最終以三維造型演示行人群體。

3.1 聚類效率的對比實驗

本實驗針對300、500、700、900、1 100共5種規(guī)模的人群疏散的聚類效率進行對比，分別作了10組實驗，記錄了k-medoids、STING、BCA這三種算法的運行時間，取其平均值為對比數(shù)據(jù)，其實驗數(shù)據(jù)平均值如表1所示。

表1 聚類時間表 sTab. 1 Clustering time s

從表1的實驗數(shù)據(jù)可以說明，在聚類效率上BCA最高，STING算法次之，k-medoids算法最差。從表1中還能看出隨著人群規(guī)模逐漸增大，各自的時間也呈上升趨勢，但BCA耗時最少也最平穩(wěn)，而k-medoids算法和STING算法都有不同程度的起伏變化。 對比分析表1中的數(shù)據(jù)，本文可以計算出BCA聚類耗時平均僅是STING算法的48.3%，k-medoids算法的13.9%。

3.2 聚類準(zhǔn)確率的對比實驗

本實驗針對300、500、700、900、1 100共5種規(guī)模的人群疏散的聚類準(zhǔn)確率進行對比，用BCA、STING、k-medoids三種算法進行對比實驗，分別作了10組實驗，取其平均值為對比數(shù)據(jù)。而聚類準(zhǔn)確率則是正確個數(shù)與事先給定的組內(nèi)個體數(shù)目的比值(聚類分組后，每組的個體序號與事先給定的該組個體序號一一匹配，記錄正確的數(shù)目，與該組給定的個體數(shù)目的比值就是該組的準(zhǔn)確率，各組準(zhǔn)確率加和求得平均值，就是總的準(zhǔn)確率)。因為人群中的社會關(guān)系是客觀存在的，所以仿真程序會事先給定人群的關(guān)系矩陣，為了便于比較，人群里個體間并非人人都有關(guān)系，而是分成人數(shù)不等的多個朋友圈和一部分互不認(rèn)識的陌生人，并且這些朋友圈間兩兩沒有交集，于是每個朋友圈就是一個事先給定的分組，單個孤立的陌生人歸入與距離(即該個體到組心位置的距離)最近的分組，最后只要把聚類結(jié)果和這些分組進行匹配就可以得到聚類的準(zhǔn)確率了。實驗數(shù)據(jù)平均值如表2所示。

表2 聚類準(zhǔn)確率表Tab. 2 Clustering accuracy rate

從表2的實驗數(shù)據(jù)可以看出，k-medoids的準(zhǔn)確率最低，平均僅是BCA準(zhǔn)確率的50%，這個和該算法自身特點有關(guān)，雖然它比k-means算法有較強的處理噪聲點的能力，但是對于極端數(shù)據(jù)點處理還是較弱，人群中的孤立陌生人給它造成了很大的麻煩；而相對而言，STING算法的準(zhǔn)確率就很高，平均能達到BCA準(zhǔn)確率的88%，當(dāng)然隨著人群規(guī)模增加，STING算法的準(zhǔn)確率也在下降，這同它均分網(wǎng)格的劃分方式有關(guān)，人越多人群分布就可能越復(fù)雜，不僅其精度降低，其耗時也會大幅增加。

3.3 聚類后的人群疏散實驗

為了展示加入分組信息后的人群疏散的效果，本實驗在場景(300 m×250 m)中，仿真了規(guī)模是300人的疏散效果。其中，初始化狀態(tài)如圖4；分組后效果如圖5，圖5中不同顏色代表不同的分組。

圖4 人群分組前的初始狀態(tài)Fig. 4 Initialization before grouping

圖5 人群分組后的聚類狀態(tài)Fig. 5 Clustering state after grouping

在向著出口疏散過程中，聚類后同組的個體會向著一起聚攏，而且為了跟上同伴，同組個體的速度基本保持一致。這類同組個體的聚團運動現(xiàn)象如圖6所示，而人群出門時形成拱形的“拱效應(yīng)”則如圖7所示。

圖6 人群疏散中的聚團運動狀態(tài)Fig. 6 Gathering movement state in crowd evacuation

圖7 人群疏散出門“拱效應(yīng)”Fig. 7 Arch effect in exits

上面的仿真實驗的結(jié)果表明，本文提出的折半聚類算法很適合用于人群疏散仿真中的聚類分組。在同樣規(guī)模、同樣場景下，對設(shè)定同樣社會關(guān)系的疏散人群進行聚類，其優(yōu)點有如下：

1)在聚類效率上有顯著優(yōu)勢。具體表現(xiàn)是聚類平均耗費的時間，BCA是STING算法的48.3%，僅是k-medoids算法的13.9%。

2)在聚類精度上有明顯提高。具體表現(xiàn)是聚類的平均準(zhǔn)確率，BCA比STING算法提高了14%，更比k-medoids算法提高了100%。

3)聚類后聚團運動現(xiàn)象明顯。具體表現(xiàn)是在社會力模型中添加了行人個體的分組信息后，個體在運動過程中的“聚團現(xiàn)象”非常明顯，更加符合人群疏散的現(xiàn)實情況。

4 結(jié)語

在人群疏散的問題研究中，為了克服社會力模型沒有考慮人群中人際關(guān)系的缺陷，從而更真實地模擬人群疏散現(xiàn)象，本文運用CBA對疏散人群進行聚類，從而快速、準(zhǔn)確地得到了個體的分組信息。本文把兩種經(jīng)典的聚類算法：k-medoids和STING，同CBA作了對比，既從理論上分析了這三種算法的時間復(fù)雜度，又經(jīng)過了反復(fù)實驗對比，驗證了k-medoids算法和STING算法，在人群疏散過程中進行聚類時，無論從效率上還是從準(zhǔn)確率上都不如CBA。

盡管如此，本文的研究仍顯粗糙，比如本文還沒有嘗試對無人際關(guān)系的數(shù)據(jù)集進行聚類，所以，不好說該算法有良好的適應(yīng)性；另外，雖然通過實驗可以觀察到孤立陌生人的數(shù)量將會影響聚類結(jié)果的準(zhǔn)確率，但還沒有定量地對其研究分析，后面將進一步在通用數(shù)據(jù)集上進行實驗，完善實驗細(xì)節(jié)參數(shù)，以便更進一步地改進、完善該算法。

References)

[1] 魏國強, 楊永清. 應(yīng)急資源布局評估與調(diào)整策略研究. 計算機工程與應(yīng)用, 2011, 47(28):215-218. (WEI G Q, YANG Y Q. Study on emergency resources location and allocation assessment and adjustment[J]. Computer Engineering and Applications, 2011, 47(28):215-218.)

[2] 于瑛英, 池宏, 祁明亮,等. 應(yīng)急管理中資源布局評估與調(diào)整的模型和算法[J]. 系統(tǒng)工程, 2008, 26(1):75-81. (YU Y Y, CHI H, QI M L, et al. Modelling and algorithm of resource location and allocation assessment and adjustment in emergency management[J]. Systems Engineering, 2008, 26(1):75-81.)

[3] MURAMATSU M, IRIE T, NAGATANI T. Jamming transition in pedestrian counter flow[J]. Physica A: Statistical Mechanics & Its Applications, 1999, 267(3/4):487-498.

[4] TAJIMA Y, NAGATANI T. Clogging transition of pedestrian flow in T-shaped channel[J]. Physica A: Statistical Mechanics & Its Applications, 2002, 303(1):239-250.

[5] SHANG H Y, HUANG H J, ZHANG Y M. An extended mobile lattice gas model allowing pedestrian step size variable[J]. Physica A: Statistical Mechanics & Its Applications, 2015, 424:283-293.

[6] ZHENG Y, JIA B, LI X G, et al. Evacuation dynamics with fire spreading based on cellular automaton[J]. Physica A: Statistical Mechanics & Its Applications, 2011, 390(18):3147-3156.

[7] 劉全平, 梁加紅, 李猛,等. 基于多智能體和元胞自動機人群疏散行為研究[J]. 計算機仿真, 2014, 31(1):328-332.(LIU Q P, LIANG J H, LI M, et al. Study on crowd evacuation behaviors based on multi-Agent and cellular automata technology[J]. Computer Simulation, 2014, 31(1):328-332.)

[8] SHI J, REN A, CHEN C. Agent-based evacuation model of large public buildings under fire conditions[J]. Automation in Construction, 2009, 18(2):338-347.

[9] HA V, LYKOTRAFITIS G. Agent-based modeling of a multi-room multi-floor building emergency evacuation[J]. Physica A: Statistical Mechanics & Its Applications, 2012, 391(8):2740-2751.

[10] HELBING D, MOLNAR P. Social force model for pedestrian dynamics[J]. Physical Review E: Statistical Physics Plasmas Fluids & Related Interdisciplinary Topics, 1998, 51(5):4282-4286.

[11] HELBING D, FARKAS I, VICSEK T. Simulating dynamical features of escape panic[J]. Nature, 2000, 407(6803): 487-490.

[12] HELBING D, BUZNA L, JOHANSSON A, et al. Self-organized pedestrian crowd dynamics: experiments, simulations, and design solutions[J]. Transportation Science, 2005, 39(1): 1-24.

[13] JOHANSSON F, PETERSON A, TAPANI A. Waiting pedestrians in the social force model[J]. Physica A: Statistical Mechanics & Its Applications, 2015, 419: 95-107.

[14] TWAROGOWSKA M, GOATIN P, DUVIGNEAU R. Macroscopic modeling and simulations of room evacuation[J]. Applied Mathematical Modelling, 2014, 38(24): 5781-5795.

[15] FANG Z, LO S M, LU J A. On the relationship between crowd density and movement velocity[J]. Fire Safety Journal, 2003, 38(3):271-283.

[16] HENEIN C M, WHITE T. Macroscopic effects of microscopic forces between Agents in crowd models[J]. Physica A: Statistical Mechanics & Its Applications, 2007, 373(36):694-712.

[17] WANG W, YANG J, MUNTZ R. STING: a statistical information Grid approach to spatial data mining[C]// Proceedings of the 23rd International Conference on Very Large Data Bases. San Francisco, CA: Morgan Kaufmann, 1997:186-195.

[18] KAUFMAN L, ROUSSEEUW P J. Finding Groups in Data: an Introduction to Cluster Analysis[M]. Hoboken, NJ: Wiley, 1990: 145-193.

[19] 金建國. 聚類方法綜述[J]. 計算機科學(xué), 2014, 41(Z2):288-293. (JIN J G. Review of clustering method[J]. Computer Science, 2014, 41(Z2):288-293.)

[20] 錢衛(wèi)寧, 周傲英. 從多角度分析現(xiàn)有聚類算法[J]. 軟件學(xué)報, 2002, 13(8):1382-1394.(QIAN W N, ZHOU A Y. Analyzing popular clustering algorithms from different viewpoints[J]. Journal of Software, 2002, 13(8):1382-1394.)

[21] 伍育紅. 聚類算法綜述[J]. 計算機科學(xué), 2015, 42(S1):491-499. (WU Y H. General overview on clustering algorithms[J]. Computer Science, 2015, 42(S1):491-499.)

[22] HAN J W, KAMBER M, PEI J. 數(shù)據(jù)挖掘: 概念與技術(shù)[M]．范明, 孟小峰,譯．北京: 機械工業(yè)出版社，2012: 293-297.(HAN J W, KAMBER M, PEI J. Data Mining: Concepts and Techniques[M]. FAN M, MENG X F, translated. Beijing: China Machine Press，2012: 293-297.)

[23] 張書春, 孫秀英. 基于網(wǎng)格結(jié)構(gòu)的CLARANS改進算法[J]. 計算機工程, 2012, 38(6):56-59.(ZHANG S C, SUN X Y. Improved CLARANS algorithm based on grid structure[J]. Computer Engineering, 2012, 38(6):56-59.)

This work is partially supported by the National Natural Science Foundation of China (61472232, 61373149, 61572299, 61402269), the Shandong Provincial Natural Science Foundation of China (ZR2014FQ009).

LI Yan, born in 1980, Ph. D. candidate, lecturer. His research interests include computer simulation, clustering analysis.

LIU Hong, born in 1955, Ph. D., professor. Her research interests include distributed artificial intelligence, software engineering, computer aided design.

ZHENG Xiangwei, born in 1971, Ph. D., professor. His research interests include computer network, computational intelligence, computer aided education.

Application of binary clustering algorithm to crowd evacuation simulation based on social force

LI Yan1,2, LIU Hong1,2*, ZHENG Xiangwei1,2

(1.SchoolofInformationScienceandEngineering,ShandongNormalUniversity,JinanShandong250014,China;2.ShandongProvincialKeyLaboratoryforDistributedComputerSoftwareNovelTechnology,JinanShandong250014,China)

Pedestrian crowd needs to be divided into groups by using clustering algorithms before using the Social Force Model (SFM) to simulate crowd evacuation. Nevertheless,k-medoids and STatistical INformation Grid (STING) are two traditional clustering algorithms, cannot meet the requirements in the aspect of efficiency and accuracy. To solve the above problem, a new method named Binary Clustering Algorithm (BCA) was proposed in this paper. BCA was composed of two kinds of algorithms: center point clustering and grid clustering. Moreover, the dichotomy was used to divide the grid without repeated clustering. First of all, the data was divided into grids, through the use of dichotomy. Next, the core grid would be selected, according to the data density in a grid. Then, the core grid was used as the center, and the neighbors were clustered. Finally, the residual grids were was merged according to the nearest principle. The experimental results show that, in the clustering time, BCA is only 48.3% of the STING algorithm, less than 14% of thek-medoids algorithm; and in the clustering accuracy,k-medoids is only 50% of BCA, STING doesn’t reach to 90% of BCA. Therefore, BCA is better thank-medoids and STING algorithm in both efficiency and accuracy.

clustering algorithm; STatistical INformation Grid (STING);k-medoids; crowd evacuation simulation; Social Force Model (SFM)

2016-09-30;

2016-12-09。

國家自然科學(xué)基金資助項目(61472232, 61373149, 61572299, 61402269)；山東省自然科學(xué)基金資助項目(ZR2014FQ009)。

李焱(1980—)，男，山東菏澤人，講師，博士研究生，CCF會員，主要研究方向：計算機仿真、聚類分析； 劉弘(1955—)，女，山東濟南人，教授，博士，CCF會員，主要研究方向：分布式人工智能、軟件工程、計算機輔助設(shè)計； 鄭向偉 (1971—)，男，山東泰安人，教授，博士，CCF會員，主要研究方向：計算機網(wǎng)絡(luò)、計算智能、計算機輔助教育。

1001-9081(2017)05-1491-05

10.11772/j.issn.1001-9081.2017.05.1491

TP301.6

A