張忠貴，蘆婭

(1.中國地質(zhì)大學(xué)(武漢)信息工程學(xué)院，湖北武漢430074;2.武漢中地數(shù)碼科技有限公司，湖北武漢430074; 3.湖北省地震局，湖北武漢430071)

一種通用的生命線工程網(wǎng)絡(luò)事件空間聚類分析算法*

張忠貴1，2，蘆婭3

(1.中國地質(zhì)大學(xué)(武漢)信息工程學(xué)院，湖北武漢430074;2.武漢中地數(shù)碼科技有限公司，湖北武漢430074; 3.湖北省地震局，湖北武漢430071)

網(wǎng)絡(luò)事件空間聚類分析可發(fā)現(xiàn)供水、排水、燃?xì)?、電力等生命線工程爆管、漏損事件的高發(fā)區(qū)域。生命線工程事件由網(wǎng)絡(luò)邊約束，可抽象為網(wǎng)絡(luò)事件。若不考慮網(wǎng)絡(luò)拓?fù)潢P(guān)系，將產(chǎn)生網(wǎng)絡(luò)事件空間聚類結(jié)果與實際分類不符的問題?；谑录W(wǎng)絡(luò)距離，提出了一種通用的網(wǎng)絡(luò)事件空間聚類方法，給出了核心概念的形式化定義以及算法描述，可廣泛應(yīng)用于生命線工程事件高發(fā)區(qū)域的發(fā)現(xiàn)，具有較強(qiáng)的實用性。并結(jié)合供水管網(wǎng)生命線工程爆管事件高發(fā)區(qū)域分析實例，給出算法參數(shù)的確定原則和范圍，驗證了所提出的算法的有效性。

生命線工程;網(wǎng)絡(luò);事件;空間聚類;網(wǎng)絡(luò)距離

生命線工程設(shè)施是維系現(xiàn)代城市與區(qū)域經(jīng)濟(jì)功能的基礎(chǔ)性工程設(shè)施［1］，包括供水、排水、燃?xì)?、電力等基礎(chǔ)設(shè)施。隨著我國城鎮(zhèn)化進(jìn)程顯著加快，城市生命線工程設(shè)施規(guī)模迅速擴(kuò)大，運營條件愈發(fā)復(fù)雜，管道爆管、燃?xì)庑孤?、漏損等生命線工程事件也進(jìn)入高發(fā)期，根據(jù)對規(guī)劃范圍內(nèi)184個城市的不完全統(tǒng)計，2000-2003年因供水管網(wǎng)爆管停水的事故達(dá)13.7萬次，影響的用水范圍涉及到總計3 819萬人次［2］，嚴(yán)重影響了社會公眾的生產(chǎn)生活和生命財產(chǎn)安全。生命線工程設(shè)施的維護(hù)以及改造是降低事件發(fā)生頻率的根本。但是整個城市建成區(qū)范圍很大，而每年網(wǎng)絡(luò)基礎(chǔ)設(shè)施改造的經(jīng)費和人力有限，先改造哪些區(qū)域才能顯著降低事件發(fā)生的頻率，是管理部門面對的難題。

生命線工程設(shè)施具有典型的網(wǎng)絡(luò)特征，具有緊密的網(wǎng)絡(luò)拓?fù)潢P(guān)系。爆管、泄露、漏損等生命線工程事件必然發(fā)生于網(wǎng)絡(luò)上，具有空間聚集性。對于生命線工程事件，僅在城市建成區(qū)歐式空間上進(jìn)行聚類分析，而不考慮其網(wǎng)絡(luò)拓?fù)潢P(guān)系，難以準(zhǔn)確地契合生命線工程事件的空間分布規(guī)律。

本文將生命線工程事件抽象為網(wǎng)絡(luò)事件，針對目前網(wǎng)絡(luò)事件空間聚類存在的問題，提出一種普適性的網(wǎng)絡(luò)事件空間聚類算法，可廣泛應(yīng)用于供水、排水、燃?xì)?、電力、電信等具有網(wǎng)絡(luò)特征的生命線工程事件高發(fā)區(qū)域的發(fā)現(xiàn)，從而為制定合理的改造計劃提供支撐，降低突發(fā)事件發(fā)生的頻率。

1 聚類方法分析

1.1 聚類分析原理

聚類分析一個非監(jiān)督分類的過程，可以形式化描述為:令P={p1，p2，…，pN}表示一個包含N個實體的數(shù)據(jù)集，根據(jù)相似性度量函數(shù)將P劃分為k+ 1(k≥1)個簇，即P={C0，C1，C2，…，Ck}，同一簇內(nèi)實體的相似度要盡可能大于不同簇的實體之間的相似度;其中，C0為噪聲，Ci(i≥1)為簇，且需要滿足以下條件［3-4］:

對于?Cm，Cn?P，m≠n，需同時滿足:

式中:Similar()表示相似性度量函數(shù)。

1.2 聚類分析方法選擇

聚類分析算法從方法上可分為:劃分方法、層次方法、基于密度的方法、基于網(wǎng)格的方法［5-6］。聚類分析算法分類如圖1所示。

圖1 聚類分析算法分類

上述聚類算法中，劃分方法和基于密度的方法［6］的研究和應(yīng)用最為深入和廣泛，本文重點對劃分方法和基于密度的方法進(jìn)行分析。其中，kmedoids難以處理大數(shù)據(jù)集［7］，K-Means算法對于離群點敏感。生命線工程事件頻發(fā)［1］，要求聚類分析算法能夠處理較大的數(shù)據(jù)集。網(wǎng)絡(luò)事件的本體為網(wǎng)絡(luò)設(shè)施，不能脫離網(wǎng)絡(luò)設(shè)施而存在，均分布在線形網(wǎng)絡(luò)上，而不是在歐式空間上泊松分布，在空間上可能存在較多噪聲點。因此，要求聚類分析算法對離群點不敏感。

根據(jù)基于網(wǎng)絡(luò)突發(fā)事件的空間聚類應(yīng)用場景，結(jié)合聚類分析算法特征，可知k-medoids、K-Means算法難以適應(yīng)生命線工程事件空間聚類應(yīng)用需求。

因此，基于聚類分析算法的應(yīng)用廣泛性、算法效率、離群點敏感程度等指標(biāo)，選擇DBSCAN［8］作為實現(xiàn)網(wǎng)絡(luò)事件空間聚類分析算法的基礎(chǔ)。

2 面臨的問題

網(wǎng)絡(luò)事件點數(shù)據(jù)集由網(wǎng)絡(luò)邊約束，決定鄰域距離參數(shù)需順著網(wǎng)絡(luò)邊搜索。目前DBSCAN算法常用的距離度量方法包括歐式距離、曼哈頓距離等［9］。生命線工程事件總是分布在線形網(wǎng)絡(luò)上，采用歐氏距離判定核心對象、密度可達(dá)、密度相連，會產(chǎn)生與實際分類不符的情況。

本文以圖2為例，詳細(xì)描述上述問題。某街區(qū)生命線工程管道A上發(fā)生3起漏損事件，生命線工程管道B發(fā)生1起漏損事件、管道C發(fā)生1起漏損事件、管道D發(fā)生1起漏損事件。漏損事件的空間及屬性信息如表1所示。

圖2 漏損事件分布

表1 事件表

對于圖2所示的網(wǎng)絡(luò)事件集合，設(shè)空間半徑ε=2.0、鄰域密度閥值(Min Pts=3)，基于歐氏距離DBSCAN算法可能得到的聚類結(jié)果如圖3所示。

圖3 漏損事件聚類結(jié)果(基于歐氏距離)

基于歐氏距離的DBSCAN算法將所有的事件劃為一個簇:C={1，2，3，4，5，6}，管道A、B、C、D改造的優(yōu)先級相同，難以提高改造的效率。

3 核心概念形式化定義

網(wǎng)絡(luò)事件空間聚類算法的主要原則是:網(wǎng)絡(luò)事件具有空間聚集性，基于網(wǎng)絡(luò)距離，以核心網(wǎng)絡(luò)事件為基礎(chǔ)，通過密度可達(dá)，發(fā)現(xiàn)網(wǎng)絡(luò)事件簇。以下對算法中涉及核心概念的進(jìn)行形式化定義［8，10］。

定義1網(wǎng)絡(luò)事件E的ε-鄰域Nε(E):以事件E為中心，網(wǎng)絡(luò)事件Ei與事件E的網(wǎng)絡(luò)距離(網(wǎng)絡(luò)最短距離)小于等于半徑參數(shù)ε的事件集合。形式化描述為:

定義2核心網(wǎng)絡(luò)事件E:如果網(wǎng)絡(luò)事件E的ε-鄰域至少包含最小數(shù)目MinPts的網(wǎng)絡(luò)事件，則稱該網(wǎng)絡(luò)事件是核心網(wǎng)絡(luò)事件。形式化描述為:

定義3直接密度可達(dá):如果網(wǎng)絡(luò)事件Ej是在Ei的ε-領(lǐng)域內(nèi)，而Ei是一個核心網(wǎng)絡(luò)事件，則稱網(wǎng)絡(luò)事件Ej從網(wǎng)絡(luò)事件Ei出發(fā)是直接密度可達(dá)的。形式化描述為:

圖4 網(wǎng)絡(luò)事件空間聚類算法核心概念

定義4密度可達(dá):存在網(wǎng)絡(luò)事件序列E1，E2，…，En，若Ei+1從Ei直接密度可達(dá)，則EN從E1出發(fā)密度可達(dá)。形式化描述為:

定義5網(wǎng)絡(luò)事件簇與噪聲:基于密度可達(dá)的最大密度相連的網(wǎng)絡(luò)事件集合稱為網(wǎng)絡(luò)事件簇。不屬于任何網(wǎng)絡(luò)事件簇的網(wǎng)絡(luò)對象為噪聲。

上述核心概念的形式化定義可通過圖4直觀說明。基于上述核心概念的定義，提出網(wǎng)絡(luò)事件空間聚類的核心數(shù)據(jù)結(jié)構(gòu):事件網(wǎng)絡(luò)距離矩陣、st-鄰域、鄰接表，如表2所示。

表2 核心數(shù)據(jù)結(jié)構(gòu)

4 網(wǎng)絡(luò)事件空間聚類算法描述

給定:網(wǎng)絡(luò)NetWork、事件集合EventSet={I0，I1，I2，…，In}、空間半徑ε、鄰域密度閥值(MinPts)，網(wǎng)絡(luò)事件空間聚類算法可描述為:

STEP 1構(gòu)建事件網(wǎng)絡(luò)距離矩陣MatrixEventNet-Dis=BulidMatrix(NetWork，EventSet);

STEP 2構(gòu)建事件鄰接表EventLinkhashList= BulidLinkList(MatrixEventNetDis，ε);

STEP 3構(gòu)建事件訪問標(biāo)識數(shù)組NewEventVisit-Flag［Max(EventID)］，均置0;

STEP 4構(gòu)建噪聲簇New Noise;初始化事件均為噪聲Noise=EventSet;

STEP 5構(gòu)建簇集合NewClusterSet;ClusterSet+ =Noise;

STEP 6對于任意網(wǎng)絡(luò)事件Ei，Ei∈EventSet，設(shè)置訪問標(biāo)識為1。根據(jù)事件鄰接表EventLinkhash-List查找事件Ei的ε-鄰域Nε(Ei)，并判斷Ei是否為核心網(wǎng)絡(luò)事件。若Ei為核心網(wǎng)絡(luò)事件，則建立一個新簇C包含Ei［5］，并從噪聲集合中移除Ei。

STEP 7對于Ej∈Nε(Ei)，設(shè)置訪問標(biāo)識為1。根據(jù)事件鄰接表EventLinkhashList查找事件Ej的ε -鄰域Nε(Ej)，并判斷Ej是否為核心網(wǎng)絡(luò)事件。若Ej為核心網(wǎng)絡(luò)事件，則根據(jù)密度連接原則，擴(kuò)展Nε(Ei)［4］:Nε(Ei)+=Nε(Ej);若事件Ej不屬于任意簇，添加事件Ej到簇C，并從噪聲集合中移除Ej。

STEP 8循環(huán)執(zhí)行STEP7，直至Nε(Ei)遍歷完成，則簇C構(gòu)建完成，添加簇C到簇集合Cluster-Set。

STEP 9循環(huán)執(zhí)行STEP6、STEP7、STEP8，直到所有網(wǎng)絡(luò)事件的訪問標(biāo)識為1時，算法結(jié)束，輸出簇集合ClusterSet。

為了便于算法描述，本文以圖2為例，設(shè)空間半徑ε=2.0、鄰域密度閥值(MinPts=3)，對于網(wǎng)絡(luò)事件空間聚類算法的核心步驟進(jìn)行說明。

4.1 事件網(wǎng)絡(luò)距離矩陣與事件鄰接表構(gòu)建

基于網(wǎng)絡(luò)的最短路徑分析算法，實現(xiàn)事件網(wǎng)絡(luò)距離矩陣的構(gòu)建，算法偽碼如下所示。

STEP 1求解網(wǎng)絡(luò)事件Eventi、Eventj所屬的網(wǎng)段Lini、Linj，以及與之最近的網(wǎng)段Lini、Linj鏈接的結(jié)點Nodei、Nodej。

STEP 2求解Nodei、Nodej網(wǎng)絡(luò)最短路徑Short-Path={Lin1，Lin2，…，Linn}。網(wǎng)絡(luò)最短路徑算法主要包括最短優(yōu)先搜索算法(LS算法，如Dijkstra算法［11］)，列表搜索算法(DS算法，如queue、deque算法)。長期以來，專家學(xué)者們對LS和LC算法的效率比較進(jìn)行了深入的研究［12］，在GIS中已經(jīng)提供了成熟的接口，本文不再贅述。

STEP 3求解最短路徑距離PathDis，最短路徑距離即為最短路徑網(wǎng)段長度的和。

STEP 4求解事件點Eventi與Nodei的網(wǎng)段距離ΔDisi;若Lini∈ShortPath，則ΔDisi=-ΔDisi。

STEP 5求解事件點Eventj與Nodej的網(wǎng)段距離ΔDisj;若Linj∈ShortPath，則ΔDisj=-ΔDisj。

STEP 6求解線性網(wǎng)絡(luò)空間距離NetDis=pathDis +ΔDisi+ΔDisj，并賦值:

MatrixEventNetDis［Eventi］［Eventj］=NetDis; MatrixEventNetDis［Eventj］［Eventi］=NetDis。

基于上述算法，構(gòu)建的網(wǎng)絡(luò)距離矩陣如下:

基于線性距離矩陣，以距離半徑為判斷標(biāo)準(zhǔn)，構(gòu)建網(wǎng)絡(luò)事件鄰接表，如圖5所示。

圖5 網(wǎng)絡(luò)事件鄰接表

4.2 事件簇構(gòu)建算法

以核心網(wǎng)絡(luò)事件為基礎(chǔ)，構(gòu)建事件簇。執(zhí)行如下構(gòu)建簇的算法，得到如圖6所示的漏損事件聚類結(jié)果:

遍歷事件集合，當(dāng)所有事件均訪問時終止

求解事件Ei的ε-鄰域Nε(Ei)

若事件Ei為網(wǎng)絡(luò)核心事件

創(chuàng)建新簇，添加事件Ei，并從噪聲移出

求解事件Ej的ε-鄰域Nε(Ej);

若事件Ej為網(wǎng)絡(luò)核心事件，Ei與Ej直接密度可達(dá)，擴(kuò)展事件Ei的ε-鄰域

若事件Ej不屬于任意簇，添加事件Ej，并從噪聲移出

圖6 漏損事件聚類結(jié)果

網(wǎng)絡(luò)事件空間聚類將事件劃分為2簇:C= {{4，5}，{1，2，3，6}}，其中{4，5}為噪聲。在進(jìn)行管網(wǎng)改造計劃制定時，可首先改造管道A、D，從而可在人力和資金制約的情況下，降低事件發(fā)生的頻率。

5 網(wǎng)絡(luò)事件空間聚類算法的應(yīng)用

網(wǎng)絡(luò)事件空間聚類算法需要確定半徑參數(shù)、鄰域密度閥值。參數(shù)的選擇對于聚類分析結(jié)果的合理性具有很大的影響。參數(shù)的確認(rèn)很大程度依賴于領(lǐng)域知識、網(wǎng)絡(luò)空間分布情況、以及網(wǎng)絡(luò)事件發(fā)生的頻率。本文以供水管網(wǎng)事件空間聚類為例，提出了以下原則供參考:

(1)半徑參數(shù)的取值范圍:網(wǎng)絡(luò)事件空間聚類的目的之一為制定更合理的管網(wǎng)養(yǎng)護(hù)或改擴(kuò)建計劃提供參考依據(jù)。因此，半徑參數(shù)的取值范圍為歷史維修或改擴(kuò)建管網(wǎng)長度的最大值和最小值［10］。半徑參數(shù)的取值可選擇接近歷史維修管網(wǎng)長度的平均值。

(2)鄰域密度閥值的取值范圍:Min Pts選擇為2，會導(dǎo)致聚類分析產(chǎn)生的簇太小，從而產(chǎn)生過多離散的簇，這對于發(fā)現(xiàn)生命線工程事件高發(fā)區(qū)域沒有太大意義。因此，Min Pts必須在3及以上［10］，從而避免產(chǎn)生過多太小的簇。

結(jié)合爆管事件的網(wǎng)絡(luò)空間散點圖，本文選擇半徑參數(shù)為300 m、鄰域密度閥值為3，基于網(wǎng)絡(luò)事件空間聚類算法，進(jìn)行供水管網(wǎng)爆管事件高發(fā)區(qū)域分析，獲取一定時間內(nèi)投訴事件最多、較多、一般或較少的區(qū)域，如圖7陰影區(qū)域所示。同時還可通過空間統(tǒng)計分析，了解該區(qū)域內(nèi)爆管的主要原因，輔助管理人員采取有針對性的措施:如加強(qiáng)管網(wǎng)巡檢和養(yǎng)護(hù)，制定管網(wǎng)改造計劃等，從而降低事件發(fā)生的頻率。

圖7 爆管事件高發(fā)區(qū)域分析

6 結(jié)束語

當(dāng)前我國供水、排水、燃?xì)?、電力等生命線工程設(shè)施的爆管、漏損事件進(jìn)入高發(fā)期。通過網(wǎng)絡(luò)事件的空間聚類分析，在整個城市范圍內(nèi)發(fā)現(xiàn)突發(fā)事件高發(fā)區(qū)域，從而為制定合理的改造計劃提供支撐，降低突發(fā)事件發(fā)生的頻率，具有較強(qiáng)的現(xiàn)實和理論意義。

本文從網(wǎng)絡(luò)事件空間聚類面臨的問題出發(fā)，給出了網(wǎng)絡(luò)事件空間聚類核心概念的形式化定義，提出了一種通用的網(wǎng)絡(luò)事件空間聚類算法，并成功運用于城市供水管網(wǎng)的爆管事件高發(fā)區(qū)域分析，證明了算法的有效性和實用性。

網(wǎng)絡(luò)事件的發(fā)生與時間密切相關(guān)，本文后續(xù)需綜合考慮網(wǎng)絡(luò)事件的時空變化特征，進(jìn)一步研究從網(wǎng)絡(luò)事件時空聚類方法，發(fā)現(xiàn)網(wǎng)絡(luò)事件的時空分布規(guī)律。

［1］李杰，劉威，衛(wèi)書麟.生命線工程網(wǎng)絡(luò)抗震拓?fù)鋬?yōu)化研究［J］.災(zāi)害學(xué)，2010，25(Supp.1):4-9.

［2］宋蘭合.城市供水管網(wǎng)問題突出亟待改造［J］.建設(shè)科技，2008(5):72-73.

［3］唐建波，鄧敏，劉啟亮.時空事件聚類分析方法研究［J］.地理信息世界，2013(1):38-45.

［4］鄧敏，劉啟亮，王佳璆等.時空聚類分析的普適性方法［J］.中國科學(xué):信息科學(xué)，2012，42(1):111-124.

［5］Jianwei Han，Micheline Kamber，Jian Pei.數(shù)據(jù)挖掘概念與技術(shù)［M］.范明，孟小峰，譯.北京:機(jī)械工業(yè)出版社，2012.

［6］Jain A k.Data clustering:50 years beyond K-means［J］.Pattern Recognition Letters，2010，31(8):651-666.

［7］宋愛琪，劉曉紅，吳國洋.GML時空聚類算法性能綜述［J］.測繪標(biāo)準(zhǔn)化，2011，27(4):9-11.

［8］EsterM，KriegelH，Sander.A density-based algorithm for discovering clusters in large spatial database with noise［C］//Proceedings of the2nd International Conference on Knowledge and Discovery and Data Mining.Portland，OR:［s.n.］，1996:45-50.

［9］程顯洲，肖蘭喜，董翔，等.基于烈度衰減橢圓閉值空間散點聚類研究——以12322災(zāi)情速報平臺為例［J］.災(zāi)害學(xué)，2013，28(4):205-208.

［10］De Oliveira D P，Garrett Jr JH，Soibelman L.A density-based spatial clustering approach for defining local indicators of drinking water distribution pipe breakage［J］.Advanced Engineering Informatics，2011，25(2):380-389.

［11］劉春年，鄧青菁.應(yīng)急決策信息系統(tǒng)最優(yōu)路徑研究——基于路阻函數(shù)理論及Dijkstra算法［J］.災(zāi)害學(xué)，2014，29(3): 18-23.

［12］陸鋒.最短路徑算法:分類體系與研究進(jìn)展［J］.測繪學(xué)報，2001，30(3):269-275.

A General Spatial Clustering Analysis Algorithm of Lifeline Network Event

Zhang Zhonggui1，2and Lu Ya3
(1．Faculty of Information Engineering，China University of Geosciences，Wuhan 430074，China; 2．Wuhan Zondy Cyber-tech Co.，ltd.，Wuhan 430074，China;3．Earthquake Administration of Hubei Province，Wuhan 430071，China)

Spatial clustering analysis of network events can be used to find high incident area of lifeline infrastructure(such aswater supply，drainage，gas and electricity).Lifeline events are constrained by the network side and can be abstracted as network events.Spatial clustering will result inconsistent with the actual classification problem without considering the network topology.Based on events network distance，a general spatial clustering analysis algorithm of network event is proposed，which could be widely used to find high incidence areas of lifeline，and with strong practicality.Combined with the example analysis of events in high-risk areas of water supply pipe network of lifeline engineering blasting，the effectiveness of the proposed algorithm are verified with the example of the analysis burst high incidence area.

lifeline;network;event;spatial clustering;network distance

P208;X4

A

1000-811X(2015)01-0029-05

10.3969/j.issn.1000-811X.2015.01.007

張忠貴，蘆婭.一種通用的生命線工程網(wǎng)絡(luò)事件空間聚類分析算法［J］.災(zāi)害學(xué)，2015，30(1):29-33.［Zhang Zhonggui andLu Ya.A General Spatial Clustering Analysis Algorithm of Lifeline Network［J］.Journal of Catastrophology，2015，30(1):29 -33.］

2014-04-25

2014-08-11

國家“十二五”科技支撐計劃(2012BAB11B05，2011BAH06B04);武漢市應(yīng)用基礎(chǔ)研究計劃(2013010501010123);武漢市關(guān)鍵技術(shù)攻關(guān)計劃(2013010602010191)

張忠貴(1981-)，男，湖北宜昌人，博士，工程師，主要從事數(shù)字城市研究.E-Mail:zzg_yc@163.com