李 焱，劉 弘，鄭向偉

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

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

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

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

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

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

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

0 引言

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

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

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

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

2)人群疏散的特征。

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

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

2)盲目從眾。即個(gè)體行為很容易被其周?chē)巳旱男袨樗绊慬15]。因?yàn)椴粌H周?chē)巳旱目只徘榫w會(huì)感染該個(gè)體，而且他們的行為也將影響該個(gè)體并引發(fā)衍生效應(yīng)。

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

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

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

1 聚類(lèi)算法

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

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

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

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

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

2 折半聚類(lèi)算法

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

2.1 算法思想及過(guò)程

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

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

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

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

過(guò)程 折半聚類(lèi)。

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

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

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

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

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

2.2 定義及公式描述

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

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

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

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

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

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

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

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

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

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

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

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

2.3 折半聚類(lèi)算法流程

算法 折半聚類(lèi)。

輸入E,S,k；

輸出G(包含k個(gè)分組的個(gè)體序號(hào))。

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

2)判斷是非二等分當(dāng)前j號(hào)網(wǎng)格，計(jì)算rj，若網(wǎng)格為空或內(nèi)個(gè)體到中心的距離均不大于rj則停止當(dāng)前網(wǎng)格劃分，標(biāo)記屬性并計(jì)算當(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)格周?chē)泥従泳W(wǎng)格并把個(gè)體屬性值都更新成核心網(wǎng)格的屬性值gj。

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

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

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

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)

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

3.1 聚類(lèi)效率的對(duì)比實(shí)驗(yàn)

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

表1 聚類(lèi)時(shí)間表 sTab. 1 Clustering time s

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

3.2 聚類(lèi)準(zhǔn)確率的對(duì)比實(shí)驗(yàn)

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

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

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

3.3 聚類(lèi)后的人群疏散實(shí)驗(yàn)

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

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

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

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

圖6 人群疏散中的聚團(tuán)運(yùn)動(dòng)狀態(tài)Fig. 6 Gathering movement state in crowd evacuation

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

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

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

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

3)聚類(lèi)后聚團(tuán)運(yùn)動(dòng)現(xiàn)象明顯。具體表現(xiàn)是在社會(huì)力模型中添加了行人個(gè)體的分組信息后，個(gè)體在運(yùn)動(dòng)過(guò)程中的“聚團(tuán)現(xiàn)象”非常明顯，更加符合人群疏散的現(xiàn)實(shí)情況。

4 結(jié)語(yǔ)

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

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

References)

[1] 魏國(guó)強(qiáng), 楊永清. 應(yīng)急資源布局評(píng)估與調(diào)整策略研究. 計(jì)算機(jī)工程與應(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)急管理中資源布局評(pí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] 劉全平, 梁加紅, 李猛,等. 基于多智能體和元胞自動(dòng)機(jī)人群疏散行為研究[J]. 計(jì)算機(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] 金建國(guó). 聚類(lèi)方法綜述[J]. 計(jì)算機(jī)科學(xué), 2014, 41(Z2):288-293. (JIN J G. Review of clustering method[J]. Computer Science, 2014, 41(Z2):288-293.)

[20] 錢(qián)衛(wèi)寧, 周傲英. 從多角度分析現(xiàn)有聚類(lèi)算法[J]. 軟件學(xué)報(bào), 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] 伍育紅. 聚類(lèi)算法綜述[J]. 計(jì)算機(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]．范明, 孟小峰,譯．北京: 機(jī)械工業(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] 張書(shū)春, 孫秀英. 基于網(wǎng)格結(jié)構(gòu)的CLARANS改進(jìn)算法[J]. 計(jì)算機(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。

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

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

1001-9081(2017)05-1491-05

10.11772/j.issn.1001-9081.2017.05.1491

TP301.6

A