基于向前搜索和K均值聚類的信號(hào)交叉口行人群集分類方法研究

于 泉，王 萌 ，鄧小惠

(北京工業(yè)大學(xué) 交通研究中心，北京 100124)

?

基于向前搜索和K均值聚類的信號(hào)交叉口行人群集分類方法研究

于 泉，王 萌 ，鄧小惠

(北京工業(yè)大學(xué) 交通研究中心，北京 100124)

以信號(hào)交叉口行人群體為研究對(duì)象，借鑒生物界群集研究的成果，給出了行人群集的定義，同時(shí)提出群集半徑的概念和向前搜索的群集半徑計(jì)算方法。運(yùn)用K均值聚類方法對(duì)北京市信號(hào)交叉口60 h視頻資料的737個(gè)行人群集樣本進(jìn)行分析，得到描述行人群集的特征參數(shù)數(shù)值。研究結(jié)果表明：行人群集半徑能夠較好地評(píng)價(jià)我國(guó)城市信號(hào)交叉口人行橫道的服務(wù)水平，可以為信號(hào)交叉口大量行人過(guò)街的控制算法和模型的研究奠定基礎(chǔ)。

交通工程；信號(hào)交叉口；行人；群集；群集半徑

行人交通作為一種健康、可持續(xù)性交通方式倍受人們的重視，是城市交通系統(tǒng)的重要組成部分。據(jù)中國(guó)公路學(xué)會(huì)《交通工程手冊(cè)》統(tǒng)計(jì)，在人口大于200萬(wàn)的城市中，步行交通在城市總出行量中約占35%，100萬(wàn)～200萬(wàn)人口的城市中約占40%，少于100萬(wàn)人口的城市中約占45%[1]。2011北京市交通發(fā)展年度報(bào)告顯示，北京市居民出行方式中，步行比例早高峰達(dá)到24.5%，高于軌道交通、自行車和小汽車的出行比例[2]。

信號(hào)交叉口是行人大量集聚擴(kuò)散的地點(diǎn)。紅燈期間，行人高密度集聚等待通行，綠燈啟亮后，大量行人放行呈現(xiàn)出短時(shí)間內(nèi)密集通過(guò)信號(hào)交叉口的現(xiàn)象。這種短時(shí)間內(nèi)高密度行人交通流容易引發(fā)信號(hào)交叉口處行人與非機(jī)動(dòng)車、機(jī)動(dòng)車交通的相互沖突，造成信號(hào)交叉口秩序混亂。同時(shí)，由于交叉口行人信號(hào)配時(shí)設(shè)置的不合理也會(huì)引起行人過(guò)街時(shí)間不足，誘發(fā)行人搶行，導(dǎo)致交叉口交通事故發(fā)生。

因此筆者嘗試通過(guò)借鑒生物群集的定義和分類方法，總結(jié)出大量行人通過(guò)信號(hào)交叉口的運(yùn)動(dòng)規(guī)律，從而可以為研究行人群體過(guò)街模型奠定基礎(chǔ)，進(jìn)而為改善信號(hào)交叉口行人信號(hào)配時(shí)，以增加行人群體的過(guò)街安全性服務(wù)。

1 行人群集運(yùn)動(dòng)研究

群集行為是目前研究的一個(gè)焦點(diǎn)，雁群遷徙行為、鹿群逃避行為等都是群集行為的代表性的例子?，F(xiàn)有的群集研究多集中在鳥群、細(xì)菌群落、蜂群以及機(jī)器人群體等方面[3-4]。群集通常具有匿名性、情緒性、暗示性和感染性，能夠從事一定的集合行為[5]。不過(guò)，群集一般是由臨時(shí)參加或卷入事件、活動(dòng)的人們組成的，并不具備成為穩(wěn)定的社會(huì)構(gòu)成體的條件。判斷一定數(shù)量的人或物是否屬于群，可以從這些人或物之間是否相互影響，相互作用，是否具有該類群的共同特性來(lái)判斷。

信號(hào)交叉口人行橫道的行人密度較高，會(huì)導(dǎo)致行人在人行橫道上自動(dòng)集合“成群”過(guò)街的現(xiàn)象，這些群和生物界的群集類似，我們稱之為行人“群集”。行人的運(yùn)動(dòng)軌跡、過(guò)街時(shí)間和過(guò)街安全性等會(huì)被這種“成群”的現(xiàn)象嚴(yán)重影響，而這種現(xiàn)象在行人流量大的北京市信號(hào)交叉口更為常見。

信號(hào)交叉口處行人通行現(xiàn)象由于其道路空間環(huán)境和綠燈通行時(shí)間限制的影響而呈現(xiàn)出其特有的“短時(shí)驟放”的特性。紅燈期間聚集的行人只能在綠燈啟亮?xí)r開始通行，此時(shí)人行道會(huì)出現(xiàn)短時(shí)的行人高峰。筆者研究的目標(biāo)是通過(guò)對(duì)大量視頻的分析，借鑒生物界群集研究的成果，給出詳細(xì)的行人群集界定方法，從而為后期開展行人群體過(guò)街特性研究提供技術(shù)手段。

2 行人群集分類方法研究

信號(hào)交叉口的行人群集是在人行橫道上成群行走的多個(gè)行人組成的群體，組成群集的每個(gè)行人之間都存在互相的影響。當(dāng)然組成行人群集的行人要受到距離的約束，群集中的行人位置不能過(guò)于分散。為了更準(zhǔn)確地描述信號(hào)交叉口行人群集的概念，筆者提出了行人群集半徑的計(jì)算方法，來(lái)約束行人群集中行人位置的分散性。

2.1 行人群集半徑

判斷一組行人在信號(hào)交叉口人行橫道上是否構(gòu)成群集，主要約束因素有對(duì)行人數(shù)量的要求、對(duì)行人間互相作用的要求和對(duì)群集中行人位置的分散程度要求。其中定量描述行人群集的因素為群集中行人位置的分散程度。

美國(guó)HCM2000手冊(cè)中對(duì)行人在人行橫道上的服務(wù)水平劃分中提出了不同密度下的行人空間標(biāo)準(zhǔn)[6]。即不同密度的行人群對(duì)應(yīng)不同的服務(wù)水平，這是一種按行人平均占用空間大小分類的方法，表1中服務(wù)水平C，D，E下的行人群密度可以體現(xiàn)大流量下行人通行的情況。

表1 行人人行通道服務(wù)水平標(biāo)準(zhǔn)

作為高級(jí)生物群體，行人通行時(shí)并不是單純地跟隨前面的行人，而是在通行過(guò)程中搜尋可能的通行空間，因此在實(shí)際通行過(guò)程中，行人通行呈現(xiàn)出一個(gè)不斷地循環(huán)搜索周邊空間，以便實(shí)現(xiàn)盡可能快速通過(guò)的過(guò)程。因此為了體現(xiàn)行人群集中行人占用空間的影響因素，同時(shí)體現(xiàn)行人群集行進(jìn)的方向性特點(diǎn)，筆者提出一種基于方向搜索的群集半徑的計(jì)算方法。

2.2 行人群集半徑計(jì)算方法

群集半徑的計(jì)算過(guò)程是一個(gè)循環(huán)搜索過(guò)程，它是每個(gè)行人依次按行走方向搜索之后，與最鄰近的行人之間的距離的平均值，具體的計(jì)算過(guò)程如下。

如圖1某行人群體，由8個(gè)行人組成，分別標(biāo)號(hào)為A,B,C,D,E,F,G,H。以行人A為例，該行人在行進(jìn)過(guò)程中，其搜索范圍能夠看到除了行人H外的其他人，即行人A是以自身為圓心形成的前進(jìn)方向的半圓范圍進(jìn)行搜索的。

圖1 行人群集示意

如圖2，行人A會(huì)在前進(jìn)方向中不斷判斷自身與周邊行人的間距，即AB，AC，AD，AE以及AF，AG。選取行人A搜索范圍內(nèi)與其他行人的最小距離值min(AB，AC，AD，AE，AF，AG)，簡(jiǎn)記為minA。同理，行人H的搜索范圍內(nèi)與其他行人的最小間距值minH。取該群集中所有8個(gè)行人的最小間距值的平均值。即R=(minA+minB+minC+minD+minE+minF+minG)/8。該平均值R定義為群集半徑，該值表征了形成該群集的行人之間的最小平均間距，即該通行的群體內(nèi)行人能夠形成群集的最近距離的平均值。行人群集半徑客觀上體現(xiàn)了行人群體的最緊密的平均水平。

圖2 行人搜索示意

要計(jì)算群集半徑值，需要經(jīng)過(guò)搜索和計(jì)算兩個(gè)步驟。以圖3為例，人行橫道上某個(gè)群集由8個(gè)人組成，沿y軸方向(平行于行人行進(jìn)方向)行走，經(jīng)過(guò)4次搜索和距離計(jì)算共9個(gè)步驟，最終得出群集半徑值。

圖3 群集半徑計(jì)算方法示意

2.2.1 第1次搜索

步驟1：尋找群集中最后1人，即最小Y值點(diǎn)A。

步驟2：按行進(jìn)方向搜索，得到與A相鄰的行人分別為B、F、I，按照間距最小的原則，得到距離A最近的點(diǎn)B，其距離為x1。

步驟3：以點(diǎn)B為起點(diǎn)，按行進(jìn)方向搜索，得到與B相鄰的行人分別為C，G，同樣按照間距最小的原則，得到距離B最近的點(diǎn)C，其距離為x2；換C為起點(diǎn)，直到搜索到最大Y值點(diǎn)E停止。分別得到離C最近的行人D，間距為x3，離D最近的行人E，間距為x4。

2.2.2 第2次搜索

步驟4：在第1次搜索剩余的點(diǎn)(F,G,I,H)中，尋找最小Y值點(diǎn)F。

步驟5：同理，以F為起點(diǎn)，按行進(jìn)方向搜索，得到最近的行人G，其距離為x5；換G為起點(diǎn)，直到搜索到上一次搜索中的點(diǎn)D停止。分別得到距離G最近的行人H，其距離為x6；離H最近的行人D，其距離為x7。

2.2.3 第3次搜索

步驟6：前兩次搜索剩余的點(diǎn)，只有點(diǎn)I。

步驟7：以I為起點(diǎn)，按行進(jìn)方向搜索，得到最近點(diǎn)G，該行人在前兩次搜索中已經(jīng)搜索到，因此搜索停止。距離I最近的行人G，其距離為x8。

2.2.4 第4次搜索

步驟8：行人群集中所有行人都已經(jīng)搜索完成。

2.2.5 距離計(jì)算

步驟9：將確定的搜索路徑按搜索方向連接起來(lái)，如圖3，所有距離的均值即為群集半徑：

(1)

按以上群集半徑的計(jì)算方法和步驟，編寫計(jì)算機(jī)程序，很容易計(jì)算出每個(gè)群集的計(jì)算半徑。示例程序界面如圖4，通過(guò)輸入1組行人中每個(gè)行人的位置橫縱坐標(biāo)，按順序計(jì)算出每個(gè)行人的最臨近行人，以及與其之間的距離值，這些距離值的均值即群集半徑值。

圖4 行人群集半徑計(jì)算程序界面

2.3K均值聚類分析方法

1967年，J.B.MacQueen提出了K均值聚類算法，用來(lái)處理數(shù)據(jù)聚類的問(wèn)題，該種算法由于其算法簡(jiǎn)便，因此在科學(xué)和工業(yè)領(lǐng)域的應(yīng)用中影響力極為廣泛。該算法解決的是將含有n個(gè)數(shù)據(jù)點(diǎn)(實(shí)體)的集合X={x1,x2,…，xn}劃分為k個(gè)類簇cj的問(wèn)題，j=1，2,…,k，算法首先隨機(jī)選取k個(gè)數(shù)據(jù)點(diǎn)作為k個(gè)類簇的初始簇中心，集合中每個(gè)數(shù)據(jù)點(diǎn)被劃分到與其距離最近的簇中心所在的類簇之中，形成了k個(gè)聚類的初始分布。對(duì)分配完的每1個(gè)類簇計(jì)算新的簇中心,然后繼續(xù)進(jìn)行數(shù)據(jù)分配過(guò)程,這樣迭代若干次后,若簇中心不再發(fā)生變化,則說(shuō)明數(shù)據(jù)對(duì)象全部分配到自己所在的類簇中,聚類準(zhǔn)則函數(shù)收斂,否則繼續(xù)進(jìn)行迭代過(guò)程,直至收斂[7-8]。

運(yùn)用K均值聚類方法對(duì)觀測(cè)得到的所有行人群集半徑數(shù)值進(jìn)行數(shù)據(jù)分類分析，其結(jié)果能夠用于信號(hào)交叉口行人群體服務(wù)水平評(píng)價(jià)和大流量行人交通控制與管理。

3 實(shí)例應(yīng)用

采集了北京市八王墳交叉口高峰小時(shí)行人群集過(guò)街視頻，共60 h的視頻資料。八王墳路口位于北京市朝陽(yáng)區(qū)西大望路地鐵站路口，路口為4相位混合交通流信號(hào)控制交叉口。周邊環(huán)境為：西南角為SOHO現(xiàn)代城，其總建筑面積為48萬(wàn)m2，擁有48家店鋪，283套辦公室，1 897套公寓；東南角為在建商業(yè)樓,西北角為小區(qū)和商業(yè)街,東北角為華貿(mào)中心，正逐步成為國(guó)際金融、企業(yè)總部云集的聚集地，無(wú)論是現(xiàn)在還是未來(lái)都將是重要的交通吸引點(diǎn),因此該信號(hào)交叉口是一個(gè)行人流量很大的重要的交通節(jié)點(diǎn)。

八王墳路口的機(jī)動(dòng)車、自行車和行人流量均相對(duì)較大，除東南角外，其他各個(gè)方向均設(shè)置地鐵進(jìn)出口，因此吸引著眾多人群，在人行橫道大量行人過(guò)街相互干擾的現(xiàn)象時(shí)常發(fā)生。以八王墳交叉口視頻中提取的737個(gè)典型群集為研究樣本，樣本選擇如表2。

表2 群集樣本選擇

提取出樣本群集中每個(gè)行人的位置坐標(biāo)，按照行人群集半徑的計(jì)算方法，可得到每個(gè)群集的群集半徑值。

運(yùn)用K均值聚類分析方法對(duì)737個(gè)群集樣本的群集半徑進(jìn)行分類。分析的結(jié)果如表3。

表3 群集半徑的聚類分析結(jié)果

圖5為分析的2組行人群集及其計(jì)算的群集半徑值。第1組行人群集半徑計(jì)算值為0.87 m，依此值計(jì)算得到的行人空間(前方半圓面積)為1.19 m2/人；同理第2組行人群集半徑計(jì)算值為1.78 m，依此值計(jì)算得到的行人空間(前方半圓面積)為4.98 m2/人 。對(duì)比表1，HCM2000手冊(cè)中的服務(wù)水平，可以發(fā)現(xiàn)第1組的服務(wù)水平為E級(jí)，第2組的服務(wù)水平為B級(jí)。可見群集半徑值能反應(yīng)群集中行人位置的分散程度，可以作為評(píng)價(jià)行人服務(wù)水平的依據(jù)。

圖5 不同行人群集的群集半徑值

4 結(jié) 語(yǔ)

將大量行人組成的群體劃定為多個(gè)行人群集，與一般用密度劃分的方法不同，提出了一種用群集半徑描述群集行人間疏密程度的方法，將群集半徑確定為行人群集的主要?jiǎng)澐謽?biāo)準(zhǔn)。以北京市八王墳地鐵處大量行人分析結(jié)果為例，計(jì)算了不同行人群集半徑，并將數(shù)值與行人服務(wù)水平加以比照。對(duì)比的結(jié)果表明，行人群集半徑能夠作為信號(hào)交叉口行人服務(wù)水平的有效分析指標(biāo)。該方法與HCM2000手冊(cè)中使用行人密度進(jìn)行服務(wù)水平的劃分方法對(duì)比，能夠更細(xì)致地進(jìn)行大量行人的服務(wù)水平劃分，并給出更為合理的量化指標(biāo)。

后續(xù)研究將繼續(xù)在不同交叉口處繼續(xù)增加觀測(cè)樣本量，并能夠借此繼續(xù)開展我國(guó)信號(hào)交叉口行人群集過(guò)街樣本的采集，為我國(guó)行人服務(wù)水平的劃分標(biāo)準(zhǔn)值和服務(wù)水平提供依據(jù)。

[1] 中國(guó)公路學(xué)會(huì)《交通工程手冊(cè)》編委會(huì).交通工程手冊(cè)[M].北京:人民交通出版社,1998. China Highway Society “Traffic Engineering Handbook” Editorial Board.Traffic Engineering Manual [M].Beijing:China Communications Press,1998.

[2] 北京交通發(fā)展研究中心.北京市交通發(fā)展年度報(bào)告[R].北京:北京交通發(fā)展研究中心,2011:33. Beijing Traffic Development Research Center.Annual Report of Beijing Traffic Development [R].Beijing:Beijing Traffic Development Research Center,2011:33.

[3] Breder C M.Equations descriptive of fish schools and other animal aggregations [J].Ecology,1954,35(3):361-370.

[4] 程代展,陳翰馥.從群集到社會(huì)行為控制[J].科技導(dǎo)報(bào),2004(8):4-7. Cheng Daizhan,Chen Hanfu.From swarm to social behavior control [J].Science & Technology Review,2004(8):4-7.

[5] 陳世明.群集行為的建模與控制方法綜述[J]計(jì)算機(jī)工程與科學(xué),2007,29(7):102-105. Chen Shiming.Review of the modeling and control of swarm behavior [J].Computer Engineering and Science,2007,29(7):102-105.

[6] Transportation Research Board.Highway Capacity Manual [M].Washington D.C.:TRB National Research Council,2000.

[7] 蔣帥.K-均值聚類算法研究[D].西安:陜西師范大學(xué),2010:9-12. Jiang Shuai.K-Means Clustering Algorithm Research [D].Xi’an:Shaanxi Normal University,2010:9-12.

[8] 于翔.聚類分析中K-均值方法的研究[D].哈爾濱:哈爾濱工程大學(xué),2007. Yu Xiang.Research onK-Means Algorithm in Clustering Analysis [D].Harbin:Harbin Engineering University,2007.

Pedestrian Swarming Classification Method Based on Forward Searching andK-Means Clustering Algorithm at Signalized Intersection

Yu Quan, Wang Meng, Deng Xiaohui

(Transportation Research Center, Beijing University of Technology, Beijing 100124, China)

Pedestrian groups at signalized intersection were the researched object, the achievements of living things were used for reference, and the conception of pedestrian swarming was given. At the same time the conception of pedestrian swarming circus was defined. Also a method based on forward searching was provided.K-means clustering algorithm was used to analyze 737 pedestrian swarming samplings of 60 hours video data at the signalized intersection, and the values of feature parameters of different pedestrian swarming were obtained. The research result shows that pedestrian swarming circus can evaluate the level of service of pedestrian crossing at signalized intersection in China, and can make good foundation for control algorithm and model of pedestrian crossing.

traffic engineering; signalized intersection; pedestrian; swarming; swarming circus

10.3969/j.issn.1674-0696.2015.01.22

2013-08-20；

2013-09-02

國(guó)家自然科學(xué)基金項(xiàng)目(51108010)

于 泉(1976—)，男，山東海陽(yáng)人，副教授，工學(xué)博士，主要從事交通信息與控制方面的研究。E-mail：yuquan@bjut.edu.cn。

U491.31

A

1674-0696(2015)01-100-05