基于路網(wǎng)拓撲的聚類分析算法研究與實現(xiàn)*

黃 敏，李爾達，袁 媛，鄭 健

(1.中山大學(xué)工學(xué)院//廣東省智能交通系統(tǒng)重點實驗室，廣東廣州510006;2.北京交通大學(xué)城市交通復(fù)雜系統(tǒng)理論與技術(shù)教育部重點實驗室，北京100044)

“物以類聚，人以群分”。在自然科學(xué)和社會科學(xué)中，存在著大量的分類問題。聚類分析是分類問題的一種統(tǒng)計分析方法，其目的是在相似的基礎(chǔ)上對數(shù)據(jù)進行分類［1］。聚類分析作為數(shù)據(jù)挖掘的核心技術(shù)，在不同的應(yīng)用領(lǐng)域都得到了很好的發(fā)展。其中，對空間數(shù)據(jù)的聚類分析一直是研究熱點之一?？臻g聚類分析是指通過對空間數(shù)據(jù)進行聚類，發(fā)現(xiàn)數(shù)據(jù)屬性之間的相互關(guān)系［2］。聚類分析算法在交通領(lǐng)域有著廣泛的應(yīng)用［3］。在交通誘導(dǎo)系統(tǒng)中，通過對興趣點的聚類分析得到的區(qū)域聚類，可用于指路系統(tǒng)中的整體誘導(dǎo)等;在交通規(guī)劃中，通過對興趣點的聚類分析得到的可達性聚類，可用于分析居民出行的可達性［4］。

目前的空間聚類分析算法，大多數(shù)都是針對歐式幾何空間中的數(shù)據(jù)對象［5－6］。然而在交通領(lǐng)域的應(yīng)用中，空間對象的訪問受限于道路網(wǎng)絡(luò)。而且，很多興趣點間的路網(wǎng)距離和歐式距離有很大的差別［7］。如圖1，從新華社廣東分社到廣東省政府，歐氏距離約為270 m。而實際上如圖2，從新華社廣東分社到廣東省政府，要經(jīng)過東風(fēng)中路，路網(wǎng)距離約為3.5 km?？梢?，網(wǎng)絡(luò)距離遠遠大于歐式距離。因此，在交通領(lǐng)域中，研究基于路網(wǎng)拓撲的聚類分析算法更具有應(yīng)用價值。

圖1 對象間的歐式距離Fig.1 The Euclidean distance between objects

圖2 對象間的網(wǎng)絡(luò)距離Fig.2 The network distance between objects

Yiu等［8］首次提出在空間網(wǎng)絡(luò)中對象聚類的問題，并提出相應(yīng)的解決方案來擴展存在的聚類方法，將其運用到空間網(wǎng)絡(luò)中的對象上，但算法復(fù)雜，實用性不高。唐良［9］在其博士論文上也曾提過空間網(wǎng)絡(luò)的聚類分析算法，但并沒有考慮到空間上如何限制聚類的擴展，適用性不強。本文針對道路網(wǎng)絡(luò)的特點，建立了實用性和適用性都較高的基于路網(wǎng)拓撲的聚類分析算法模型。并利用C#語言及ArcEngine二次開發(fā)組件實現(xiàn)算法的可視化，應(yīng)用于廣州珠江新城，研究居民出行的可達性。

1 基本模型和問題定義

本節(jié)引入道路網(wǎng)絡(luò)以及對象之間的網(wǎng)絡(luò)距離等定義［9］，然后根據(jù)道路網(wǎng)絡(luò)的聚類特點，給出了對象與聚類的網(wǎng)絡(luò)距離定義。

定義1 道路網(wǎng)絡(luò)與興趣點。

為了降低道路網(wǎng)絡(luò)復(fù)雜性，可以將路網(wǎng)的交叉口建模為網(wǎng)絡(luò)圖的結(jié)點，將交叉口之間的弧段建模為網(wǎng)絡(luò)圖的邊［10］。一個道路網(wǎng)絡(luò)可以表示為一個無向帶權(quán)圖G=(V，E，W)，其中:V是結(jié)點的集合;E是弧段集合;W為路段對應(yīng)權(quán)值的正實數(shù)集合。

確定興趣點間的路距離，首先要建立興趣點與路網(wǎng)的關(guān)系。

興趣點 p(p∈P)位于弧段 (vi，vj))上，用一個三元組 (vi，vj，pos)來表示興趣點與路網(wǎng)的關(guān)系。這里，vi和 vj為興趣點所在弧段 (vi，vj))的起終點 (vi為起點，vj為終點)，pos為興趣點p與結(jié)點vi在弧段上的距離。如圖3，p1=(A，B，30)，p2=(A，B，75)。

圖3 興趣點與路網(wǎng)的關(guān)系Fig.3 The relationship between POI and network

定義2 對象之間的網(wǎng)絡(luò)距離dD。

1)同一弧段上的對象之間的直接距離:

2)結(jié)點之間的網(wǎng)絡(luò)距離。dD(vi，vj)為從結(jié)點vi到結(jié)點vj的最短路徑距離。最短路徑距離用 Dijkstra 算法計算［11］。

3)不同弧段上的興趣點之間的網(wǎng)絡(luò)距離:

定義3 興趣點與聚類間的最小距離dN。

最小距離dN為興趣點與聚類不同興趣點間最小的網(wǎng)絡(luò)距離。

設(shè)有興趣點p，聚類C的興趣點為q1，q2，…，qm，則興趣點p與聚類Cx的網(wǎng)絡(luò)距離表示為:

定義4 興趣點與聚類間的最大距離dM。

最大距離dM為興趣點與聚類不同興趣點間最大的網(wǎng)絡(luò)距離。

設(shè)有興趣點 p，聚類 C的興趣點為 q1，q2，…，qm，則興趣點p與聚類C的最大距離表示為:

2 基于路網(wǎng)拓撲的空間聚類算法模型

2.1 算法介紹

現(xiàn)有的空間聚類算法中的一些概念，如聚類中心、聚類特征等，都難以在道路網(wǎng)絡(luò)中進行定義［11］。具體來說，給定道路網(wǎng)絡(luò)中的一組對象，由于可能在網(wǎng)絡(luò)邊上不存在一個唯一點，與聚類中所有對象之間的平均距離最小，所以不能使用網(wǎng)絡(luò)距離來定義它們的聚類中心。

因此，本文提出一種沿著路網(wǎng)拓撲方向進行的廣度搜索，利用凝聚度 (α)和擴展度 (β)為聚類限制條件的聚類分析算法，α和β的取值直接影響到聚類的結(jié)果。其中，定義興趣點與聚類間的最小距離的限制值為凝聚度α，α控制對象之間在網(wǎng)絡(luò)上的凝聚程度;興趣點與聚類間的最大距離的限制值為擴展度β，β控制整個聚類在網(wǎng)絡(luò)上的擴展程度。

2.2 算法步驟

基于路網(wǎng)拓撲的空間聚類算法需要一個列表Q來保存結(jié)點周圍待遍歷的鄰接路段信息，即項(v1，v2，w)。這里，w為弧段 (v1，v2)的權(quán)值。

任取一個興趣點pi(va，vb，posi)的聚類分析主要步驟如下:

Step1創(chuàng)建聚類，設(shè)定參數(shù)。

創(chuàng)建新聚類C，將興趣點pi加入C。設(shè)定限制值α和β，進行Step2。

Step2由興趣點Pi沿所在路段的方向擴展搜索至路段結(jié)點。

設(shè)pk為興趣點pi在結(jié)點vb方向上的鄰接興趣點。

1)若存在興趣點pk，則判斷dN(pk，C)≤α且dM(pk，C)≤β，符合則將pk加入C，繼續(xù)向vb方向擴展，直到結(jié)點vb，進行Step3;不符合則直接轉(zhuǎn)到Step5;

2)若不存在興趣點pk，則直接轉(zhuǎn)到Step3。

Step3遍歷結(jié)點vb的鄰接結(jié)點，構(gòu)造列表Q。

設(shè)vb有鄰接結(jié)點i個，遍歷vb鄰接結(jié)點，v2c，……，設(shè) pk為路段 (vb，)上鄰接vb的興趣點。設(shè)當(dāng)前操作結(jié)點，初始設(shè)定j=1，進行以下循環(huán)判斷:

1)若邊 (vb，)上存在興趣點，則將 (vb，w(v，v))插入到Q隊首。j=j+1，繼續(xù)進行bc循環(huán)判斷;

2)若邊 (vb，)上無興趣點，比較 (vb，vc)和凝聚度α的值:小于凝聚度α，則將 (vb，vc，w(vb，vc))插入到Q隊首，大于凝聚度α，不操作。j=j+1，繼續(xù)進行循環(huán)判斷。

至到j(luò)=i，結(jié)束循環(huán)判斷，進行Step4。

Step4取出Q隊首項，繼續(xù)進行聚類。

判斷隊列Q是否為空:

1)若Q為空，結(jié)束整個算法;

2)不為空，取出Q隊首項。由vb向vc遍歷路段 (vb，vc)上的興趣點，將滿足聚類限制條件，即興趣點與聚類間最小距離小于α，且興趣點與聚類間最大距離小于β的興趣點加入聚類C中。

Step5擴展鄰接結(jié)點，遍歷該結(jié)點的鄰接結(jié)點，擴充列表Q。

設(shè)路段 (vb，vc)上鄰接vb的興趣點為pt。

1)若dD(pt，vc)≤α，則轉(zhuǎn)到Step3對vc的鄰接結(jié)點進行遍歷，擴充優(yōu)先隊列Q;

2)若dD(pt，vc)＞α，則轉(zhuǎn)到Step4繼續(xù)進行聚類。

下面介紹算法流程圖，如圖4所示。其中，遍歷vb的鄰接結(jié)點的算法流程圖如圖5所示。

3 應(yīng)用示例

根據(jù)本文提出的基于路網(wǎng)拓撲的聚類分析算法，以廣州市珠江新城路網(wǎng)為實例，利用C#語言以及ArcEngine二次開發(fā)組件構(gòu)建應(yīng)用分析模塊，實現(xiàn)后界面如圖6所示。

這一節(jié)將利用基于路網(wǎng)拓撲的聚類分析算法分析行人的可達性情況?？蛇_性是交通規(guī)劃中評價交通網(wǎng)絡(luò)系統(tǒng)性的一項有效的綜合性指標(biāo)［12］?？蛇_性的主要定義的其中一種是，一定空間范圍內(nèi)可獲得或接近的目標(biāo)對象的數(shù)量多少。因此，研究的具體的作法是，選擇兩個地物點，通過聚類分析分別計算一定范圍內(nèi)，行人可獲得的公共交通站點的數(shù)量。以此比較這兩個地物點的可達性。

HCM2000中規(guī)定行人的步行速度取決于行人中老年人的比例，推薦1.22 m/s作為標(biāo)準(zhǔn)步行速度值［13］。一般來說，行人步行可接受時間為5～10 min，因此取步行適宜距離L=600 m。

圖4 算法流程圖Fig.4 Algorithm flow chat

圖5 遍歷鄰接結(jié)點算法流程圖Fig.5 Algorithm flow chat of extending to the adjacent node

選取珠江新城的廣州大劇院和富力盈凱廣場，設(shè)置限制值α=600 m，運行程度得到的結(jié)果如圖7和圖8。

由結(jié)果可得，在廣州大劇院的600 m范圍內(nèi)，行人可到達的公共交通站點共有3個，分別是華穗路公交車站、廣州大劇院西門公交車站、海心沙公園公交車站。而在富力盈凱廣場的600 m范圍內(nèi)，行人可到達的公共交通站點共有4個，分別是珠江新城地鐵站、華穗路口公交車站、友誼國金店公交車站和市政務(wù)服務(wù)中心公交車站。

圖6 程序界面Fig.6 The program interface

圖7 廣州大劇院聚類結(jié)果Fig.7 The clustering result of Guangzhou Theater

圖8 富力盈凱廣場聚類結(jié)果Fig.8 The clustering result of Decimating Surplus Kay Square

行人在富力盈凱廣場600 m范圍內(nèi)可獲得的公共交通站點比在廣州大劇院多。因此，從這個角度出發(fā)，600 m范圍內(nèi)行人在富力盈凱廣場的可達性比在廣州大劇院強［14］。

4 結(jié)語

基于路網(wǎng)拓撲的空間聚類分析算法，解決了以往大多數(shù)空間聚類算法不適用于道路網(wǎng)絡(luò)的交通問題。其次，利用C#語言和ArcGIS，將模型應(yīng)用在珠江新城路網(wǎng)，通過算法，成功聚類出可用于分析城市居民可達性的區(qū)域。這表明了基于路網(wǎng)拓撲的空間聚類分析算法是可行且具有應(yīng)用價值的。但是，本聚類算法，并沒有考慮標(biāo)志性地物點的具體屬性，下一步將考慮地物點的具體屬性，進行有選擇的聚類。

［1］許麗利.聚類分析的算法及應(yīng)用［D］.長春:吉林大學(xué)，2010.

［2］劉生鑫.空間數(shù)據(jù)聚類分析算法研究及實現(xiàn)［D］.武漢:中國地質(zhì)大學(xué)，2010.

［3］李桃映.交通領(lǐng)域中的聚類分析方法研究［D］.大連:大連海事大學(xué)，2010.

［4］劉賢騰.空間可達性研究綜述［J］.城市交通，2007，5(6):36－43.

［5］席景科，譚海樵.空間聚類分析及評價方法［J］.計算機工程與設(shè)計，2009，30(7):1712－1715.

［6］JAIN A K，MURTY M N，F(xiàn)LYNN P J.Data clustering:A review［J］.ACM Computing Surveys，1999，31(3):264－323.

［7］沙志仁，余志，黃敏，等.面向指路標(biāo)志系統(tǒng)的非平面交通路網(wǎng)模型［J］.測繪科學(xué)技術(shù)學(xué)報，2011，28(6):442－445.

［8］YIU M L，MAMOULIS N.Clustering objects on a spatial network［C］.SIGMOD，2004:443－454.

［9］唐良.城市道路交通指路標(biāo)志智能設(shè)計系統(tǒng)的研究與實現(xiàn)［D］.合肥:中國科學(xué)技術(shù)大學(xué)，2008.

［10］黃敏，李敏，鈕中銘，等.基于指引可達性的指路標(biāo)志布設(shè)優(yōu)化模型［J］.中山大學(xué)學(xué)報:自然科學(xué)版，2014，53(3):19－23.

［11］張開廣，孟紅玲，亢金軒.基于路徑的聚類分析［J］.測繪科學(xué)技術(shù)學(xué)報，2006，23(2):145－148.

［12］陳繼東，孟小峰，賴彩鳳.基于道路網(wǎng)絡(luò)的對象聚類［J］.軟件學(xué)報，2007，18(2):332－344.

［13］Transportation Research Board.Highway capacity manual 2000［M］.Washington D C:National Research Council，2000.

［14］肖國榮，余志，黃敏.基于偏離指數(shù)的指路標(biāo)志優(yōu)化模型研究［J］.中山大學(xué)學(xué)報:自然科學(xué)版，2008，47(1):38－41.