網絡空間中線要素的核密度估計方法

唐爐亮，闞子涵，劉匯慧,2，孫 飛，吳華意

1. 武漢大學測繪遙感信息工程國家重點實驗室，湖北 武漢 430079； 2. 武漢大學測繪學院，湖北 武漢 430079

網絡空間中線要素的核密度估計方法

唐爐亮1，闞子涵1，劉匯慧1,2，孫 飛1，吳華意1

1. 武漢大學測繪遙感信息工程國家重點實驗室，湖北 武漢 430079； 2. 武漢大學測繪學院，湖北 武漢 430079

核密度估計(KDE)方法是分析點要素或線要素空間分布模式的一種重要方法，但目前線要素核密度方法只能分析線要素在二維均質平面空間的密度分布，不能正確分析交通擁堵、交叉口排隊、出租車載客等線事件在一維非均質道路網絡空間中的密度分布。本文提出了一種網絡空間中線要素的核密度估計方法(網絡線要素KDE方法)，首先確定每個線要素在網絡空間上的密度分布，然后根據網絡空間距離和拓撲關系確定網絡空間的線要素核密度與時空分布。以出租車GPS軌跡數據中提取的“上客”線事件為例，分析出租車“上客”線事件在網絡空間中的密度分布，通過與現有方法比較的試驗結果表明，本文提出的方法更能準確反映路網空間中線事件的分布特征。

線事件；網絡空間；核密度；時空GPS軌跡

在道路網絡空間中，有一類具有起止點和發(fā)生過程的事件或現象，通常稱為線事件，如交通擁堵、交叉口排隊等候、出租車載客等，這些線事件的發(fā)生和分布受道路網絡的空間格局與拓撲關系的影響，在道路網絡中呈現連續(xù)線狀分布?，F有線要素分布模式分析方法只能分析線要素在二維延展均質平面空間的密度分布，不能正確分析線要素在非均質道路網絡空間中的密度分布，因此研究一種非均質網絡空間中線要素分布模式分析方法具有重要意義。

核密度估計(kernel density estimation，KDE)是分析空間要素聚集效應的一種重要的非參數化方法[1-2],通過將整個研究區(qū)域生成一個光滑的密度表面來分析點事件的空間聚集特征，找出事件的高發(fā)區(qū)域，在經濟、人口統(tǒng)計以及影像分類處理等方面都有廣泛應用[3-8]。典型的KDE方法基于各向同性的二維均質空間，但對于發(fā)生和分布受一維網絡格局限制的事件來說，各向同性的假設就過于牽強[9]。網絡KDE方法以網絡距離代替歐氏距離[4-5，10-13]，如文獻[4—5]根據網絡距離得到一個多邊形搜索區(qū)域，代替整個均質平面；文獻[10]以路網線性單元為密度估計的基本單位，得到整個路網的核密度分布；文獻[11]提出非連續(xù)和連續(xù)等分核函數法兩種網絡的核密度估計模型,并驗證了交叉口處的無偏性；文獻[12]將文獻[4—5]的方法和文獻[10]提出的方法進行了比較；文獻[13]提出了網絡KDE方法的一般形式，分析了城市路網中設施POI分布特征。

目前線要素的分布模式分析方法仍然有所欠缺。已有線要素分析方法主要將線要素空間分布轉化為點要素空間分布[14-15]、采用平面線要素KDE方法估計道路網密度分布[16-17]或利用三維空間的KDE方法估計時空軌跡的密度分布[18-19]。通過分析可知，目前線要素密度分布分析方法都以均質空間為基礎，沒有考慮交通擁堵、交叉口排隊、出租車載客等線事件受路網格局和網絡方向的限制而呈現的分布特征。本文提出一種網絡空間的線要素核密度估計方法，以網絡距離為度量，顧及網絡拓撲方向，分析線事件在網絡空間中的分布特征和分布模式。

1 網絡空間中線要素的核密度估計方法

網絡空間中線要素的核密度估計方法(網絡線要素KDE方法)，首先定義交通擁堵、交叉口排隊、出租車載客等線事件，并在平面線要素KDE方法的基礎上，進行以下兩個方面的改進和拓展。

(1) 在核密度延展方向和衰減效應方面，將平面線要素KDE方法中線要素核密度“均質二維方向延展”和“平面距離衰減效應”改進和拓展為“非均質網絡方向延展”和“網絡距離衰減效應”。

(2) 在線要素密度計算方面，考慮線要素的起止方向和網絡方向及拓撲連通性，考慮網絡節(jié)點處密度計算的特殊情況，保證節(jié)點密度估計的無偏性。

1.1 線事件的定義及表達

在網絡空間中，具有起止點并呈線狀連續(xù)分布的事件稱為線事件(linear event,LE)，可表達為

LE={ID,S,E,L,TS,TE}

式中，ID為線事件LE的編號；S、E分別為LE發(fā)生的起止位置點；L為起止點間發(fā)生和分布的網絡空間,數學表達為路網N的子集：L∈N；TS和TE分別為線事件起止時間點，網絡空間中的線事件表達如圖1所示。

圖1 路網中線事件的表達Fig.1 Representation of linear events in road network

1.2 單個線要素在網絡空間中的密度分布

平面線要素KDE和網絡線要素KDE均以標準點要素平面 KDE方法為基礎，通過為每個點生成一個光滑的密度表面來估計整個平面的密度值，如圖2所示。

圖2 標準點平面要素KDEFig.2 Standard planar KDE for point features

圖2中，函數f(x)為單個點要素i在均質平面中的密度分布函數；r為距離閾值。在r范圍內，隨著與點要素i距離的增加，對應的密度值f(x)減小，與i距離大于等于r的位置處f(x)等于零，即通過考慮“距離衰減效應”確定每個點要素的密度分布。f(x)的值由式(1)確定

(1)

式中，si為點要素i所在位置；x-si為位置x與i的歐氏距離；k為距離衰減函數，也稱為核函數。k的形式有多種，如高斯函數、二次多項式函數、四次多項式函數等。

與平面點要素KDE類似，平面線要素KDE在閾值r的范圍內在線要素上方覆蓋一個核表面，表示線要素密度影響的各向同性“距離衰減效應”，如圖3(a)所示。而與平面線要素KDE的各向同性性質不同，網絡空間中線要素的密度分布受網絡空間格局和網絡方向的約束，其影響范圍限制在非均質網絡空間內，所以網絡線要素KDE方法將以往的平面歐氏距離改進和拓展為網絡距離，在閾值r范圍內按照網絡空間中的“網絡距離衰減效應”在每個線要素上方覆蓋一條平滑曲線，即核曲線f(x)，表示單個線要素在網絡空間中的密度分布，如圖3(b)所示。

圖3 網絡線要素KDE核曲線與平面線要素KDE核表面Fig.3 Kernel surface in planar KDE and kernel curve in network KDE

線要素在網絡空間中的密度分布函數f(x)由點要素推導而來。由于線要素l可以看作由起點S和終點E之間無限個連續(xù)分布的點要素組成，因此網絡空間中單個線要素的密度分布應為線要素上所有點的密度分布在網絡空間中的矢量和。在線要素影響域r范圍內，網絡線要素的密度值f(x)在數學上應表示為從線要素起點S至終點E，連續(xù)移動核函數在線要素上的積分，即核函數與線要素圍成的面積。如圖4所示，陰影部分面積即分別為位置S、O、E處的密度f(S)、f(O)、f(E)?？梢钥闯觯诰€要素外距離線要素端點大于等于r的位置線密度為零，越接近線要素中心的位置，密度越大，在線要素內且與端點網絡距離大于等于r的位置處陰影部分面積充滿整個核函數，密度達到最大，之后將保持不變，以此得到線要素核密度分布曲線為圖4中紅色曲線。因此對于單個線要素l來說，其在網絡空間中的密度分布曲線f(x)為

(2)

本文選擇二次多項式函數作為核函數，如式(3)所示

(3)

圖4 網絡空間線要素核密度分布Fig.4 Kernel density distribution for linear feature in network space

1.3 顧及網絡拓撲關系的線事件密度分布

現有道路網絡中事件的空間分布研究均將道路視作單線且雙向連通[4-5,10-11]，然而一方面由于路網的復雜性和線事件本身具有的起止方向性，另一方面事件的發(fā)生機制受交通流的影響，即使同一條道路的不同方向上事件分布模式并不相同，因此在計算網絡空間線密度分布時，需要顧及路網拓撲方向的約束。

1.3.1 網絡空間弧段上的密度分布

線事件在網絡空間弧段上的密度分布顧及網絡拓撲關系，以網絡距離r作為距離衰減閾值，得到閾值范圍內的線要素。圖5中的灰色區(qū)域分別為平面線要素KDE方法和網絡線要素KDE方法得到的閾值范圍，網絡線要素KDE對網絡距離與拓撲關系的考慮體現在兩個方面，一是通過網絡距離得到網絡閾值范圍，而非平面線要素KDE方法得到的各向同性圓形閾值范圍；二是顧及了局部網絡的可達性及線事件的方向性，例如線要素3的方向與估計點X所在道路方向相反，對X處密度影響應為零，而在平面線要素KDE中，圓形范圍內的線要素則都要考慮。

在得到范圍r內的線要素之后，網絡空間中線要素密度估計結果應該是每個線要素密度分布曲線值在路網中的疊加。對網絡空間弧段上每點進行密度估計時，考慮范圍r內所有線要素，得到的空間位置x處的線密度應為

(4)

式中，li為x閾值范圍內的線要素；n為閾值范圍內線要素總個數。

圖5 平面線要素KDE和網絡線要素KDEFig.5 Planar KDE and network KDE for linear feature

1.3.2 網絡空間節(jié)點處的線事件密度估計

節(jié)點是網絡拓撲性質改變的位置，節(jié)點處由于邊數增多，考慮范圍會增大，無論是平面線要素KDE方法還是普通的網絡KDE方法均無法保證節(jié)點處密度估計的正確性。本文按照文獻[11]提出的點要素等分核函數方法實現節(jié)點處線要素密度估計的無偏性。等分核函數計算原理如圖6所示，節(jié)點I的度為4，對于待估計的位置，與X同一邊的核函數形式保持不變，X鄰接邊核函數k減小為原來的1/3；若X的閾值范圍r內包括多個節(jié)點，設每個節(jié)點的度ni，則X網絡節(jié)點下行方向上的每條邊核函數依次減少為上一邊核函數的1/(ni-1)，這使無論空間位置X附近是否存在節(jié)點，X處密度最大值為核函數在整個閾值范圍r內的積分，從而保證X密度的最大值不變，避免了密度值的過度估計，保證交叉口處線密度估計的真實性。核函數k(s-x/r)的形式如式(5)所示

(5)

最后，結合式(3)—式(5)，即可得到路網空間中的線要素密度分布。

圖6 節(jié)點處核密度估計Fig.6 Kernel density estimation at nodes

1.4 網絡空間線要素核密度估計模型算法實現

網絡空間線要素核密度的算法實現如圖7所示，主要分為3個部分：網絡分割、線要素處理和密度計算。將網絡在節(jié)點處斷開，得到一系列網絡弧段，將弧段按照一定長度等分成基本線性單元(basic segment unit，BSU)，構建以BSU為基本單位的拓撲結構。將網絡中的線要素起止點分配到最近的BSU端點上，此時每個線要素視作經過整數個BSU，記錄每個BSU上經過的線要素個數。確定距離閾值r，依次計算網絡中每個BSU的密度，計算方法為：首先根據網絡距離r確定閾值范圍內的BSU，然后將每個BSU上的線要素個數作為數乘因子(沒有線要素經過則為0)，在網絡距離閾值范圍內計算每個BSU的密度權重，最后累加閾值范圍內所有BSU的密度權重得到待估計BSU的密度值。

圖7 網絡線要素KDE算法實現Fig.7 Algorithm and implementation of KDE for network linear feature

密度計算如式(6)所示

(6)

2 試 驗

本文以Microsoft Visual C# 2010為開發(fā)語言，采用ESRI ArcGIS 10.1對線要素核密度計算結果進行可視化，選取武漢市路網和浮動車數據為研究對象，該數據按照40 s等時間間隔采集，包含出租車ID、經度、緯度、速度、方向、載客狀態(tài)(滿載為“1”，空載為“0”)。本文針對出租車“上客”事件抽取出相鄰兩條載客狀態(tài)分別為“0”和“1” 的數據，由于出租車GPS軌跡采集具有時間間隔，相鄰載客狀態(tài)分別為“0”和“1”的記錄所對應的位置只能代表數據采集瞬間出租車的載客狀態(tài)，只能確定“上客”事件發(fā)生在0→1之間，無法獲知其具體發(fā)生的時間和地點，因此“上客”事件成為有起點和終點的“上客”線事件，本文提取相鄰狀態(tài)分別為0和1的“上客”事件共278個，其分布如圖8所示。

圖8 試驗區(qū)域路網和“上客”線事件起止點分布Fig.8 Road network in experiment region and distribution of start and end point of “pick-up” linear events

試驗中以20 m BSU長度對路網進行分割，統(tǒng)計“上客”線事件在每個BSU上的分布，并以100 m為距離衰減閾值，采用本文提出的顧及網絡空間距離和拓撲關系的線要素核密度分析方法對該“上客”線事件數據進行密度計算和分布模式分析，并將結果與樣方法(20 m樣方大小)和平面線要素KDE方法(20 m×20 m柵格大小，100 m閾值)進行比較，按照本文方法處理“上客”線事件密度分布結果如圖9(a)所示，樣方法處理的“上客”線事件密度分布結果如圖9(b)所示，平面線要素KDE方法處理的“上客”線事件密度分布結果如圖9(c)所示,處理結果的局部放大效果如圖10所示。

圖9 不同處理方法的“上客”線事件在網絡空間的密度分布Fig.9 Density distribution of “pick-up” linear events in network space processed by different methods

圖10 局部范圍3種方法的比較Fig.10 Comparison of the three methods for linear features in a local scale

從圖9可以看出，本文提出的網絡線要素KDE方法和樣方法、平面線要素KDE方法都能在一定程度上反映出線事件的網絡空間分布特征，“上客”事件發(fā)生密集分布于珞獅路、武珞路中部、中南路南部、中山路南部。這些道路上有街道口商圈、中南路商圈等經濟熱點地帶，以及軌道交通地鐵2號線站點、武昌火車站等交通熱點地帶，這些位置對于出租車的需求較大，因此是“上客”事件的高發(fā)點。通過對圖9、圖10的分析可以看出，本文提出的網絡線要素KDE方法處理的“上客”線事件將密度分布限制于城市道路網絡空間內，更加符合“上客”事件本身發(fā)生和影響在道路網絡上，而非覆蓋在道路網絡外的事實。本文方法處理的“上客”線事件的密度在同一道路上分布很連續(xù)，在不同等級道路上分布較均衡，密度分布具有差異性但不存在突變情況，可以如實地反映“上客”線事件在路網中分布特征, 并且能更好地體現細節(jié)信息，如圖9(a)、圖10(a)所示。圖9(b)、圖10(b)為樣方法處理的“上客”線事件密度分布結果，圖中出現密度在一條道路中間突然斷開、分布不連續(xù)的情況，這表示“上客”線事件在這一位置發(fā)生的概率有突變，即這一位置不可能有“上客”線事件的發(fā)生，這顯然不符合事實。圖9(c)和圖10(c)中的平面線要素KDE方法由于計算整個平面的線密度分布，以二維歐氏距離度量事件的發(fā)生和影響范圍，沒有考慮路網空間的非均質空間特性，使“上客”線事件的影響范圍向道路空間外延展，因此處理結果中“上客”線事件的核密度存在于二維延展的均質空間，覆蓋于城市道路網絡之外，不符合“上客”線事件發(fā)生在道路范圍內的事實。

3 結 論

鑒于現有的點模式分析方法和線要素核密度方法只能分析線要素在二維延展均質平面空間的密度分布，不能正確分析交通擁堵、交叉口排隊、出租車載客等線事件在非均質道路網絡空間中的密度分布，本文提出一種網絡線要素KDE方法，該方法首先確定線要素在網絡空間的密度分布，然后根據網絡空間距離和拓撲關系確定網絡空間中線要素密度分布，并以出租車GPS軌跡數據中提取出的“上客”線事件為例，分析了出租車“上客”線事件在網絡空間中的線密度分布。試驗結果表明，本文方法處理的“上客”線事件的密度在同一道路上分布連續(xù)，在不同等級道路上分布較均衡，密度分布具有差異性但不存在突變情況，能更好地體現細節(jié)信息，通過與現有方法的比較認為，本文提出的方法更能準確地反映路網空間中線事件的分布特征。在提高算法效率、計算線要素的密度衰減效應時應考慮道路等級、并對交通流特性作定量分析。作者將對此作進一步研究和完善。

[1] SILVERMAN B W. Density Estimation for Statistics and Data Analysis[M]. New York: Chapman & Hall, 1986.

[2] BAILEY T C, GATRELL A C. Interactive Spatial Data Analysis[M]. Harlow Essex, England: Longman, 1995.

[3] TIMOTHéE P, NICOLAS L B, EMANUELE S, et al. A Network Based Kernel Density Estimator Applied to Barcelona Economic Activities[C]∥Proceedings of International Conference on Computational Science and Its Applications-ICCSA 2010. Berlin Heidelberg: Springer, 2010: 32-45.

[4] BORRUSO G. Network Density Estimation: A GIS Approach for Analyzing Point Patterns in Network Space[J]. Transactions in GIS, 2008, 12(3): 377-402.

[5] BORRUSO G. Network Density Estimation: Analysis of Point Patterns over a Network[C]∥Proceedings of International Conference on Computational Science and Its Applications-ICCSA 2005. Berlin Heidelberg: Springer, 2005: 126-132.

[6] 呂安民, 李成名, 林宗堅, 等. 人口密度的空間連續(xù)分布模型[J]. 測繪學報, 2003, 32(4): 344-348. Lü Anmin, LI Chengming, LIN Zongjian, et al. Spatial Continuous Surface Model of Population Density[J]. Acta Geodaetica et Cartographica Sinica, 2003, 32(4): 344-348.

[7] 楊紅磊, 彭軍還. 基于馬爾可夫隨機場的模糊c-均值遙感影像分類[J]. 測繪學報, 2012, 41(2): 213-218. YANG Honglei, PENG Junhuan. Remote Sensing Classification Based on Markov Random Field and Fuzzy c-means Clustering[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(2): 213-218.

[8] 周恩策, 劉純平, 張玲燕, 等. 基于時間窗的自適應核密度估計運動檢測方法[J]. 通信學報, 2011, 32(3): 106-114, 124. ZHOU Ence, LIU Chunping, ZHANG Lingyan, et al. Foreground Object Detection Based on Time Information Window Adaptive Kernel Density Estimation[J]. Journal of Communications, 2011, 32(3): 106-114, 124.

[9] MILLER H J. Potential Contributions of Spatial Analysis to Geographic Information Systems for Transportation (GIS-T)[J]. Geographical Analysis, 1999, 31(4): 373-399.

[10] XIE Zhixiao, YAN Jun. Kernel Density Estimation of Traffic Accidents in a Network Space[J]. Computers, Environment and Urban Systems, 2008, 32(5): 396-406.

[11] OKABE A, SATOH T, SUGIHARA K. A Kernel Density Estimation Method for Networks,Its Computational Method and a GIS-based Tool[J]. International Journal of Geographical Information Science, 2009, 23(1): 7-32.

[12] LI Qingquan, ZHANG Tong, WANG Handong, et al. Dynamic Accessibility Mapping Using Floating Car Data: A Network-constrained Density Estimation Approach[J]. Journal of Transport Geography, 2011, 19(3): 379-393.

[13] 禹文豪, 艾廷華. 核密度估計法支持下的網絡空間POI點可視化與分析[J]. 測繪學報, 2015, 44(1): 82-90. DOI: 10.11947/j.AGCS.2015.20130538. YU Wenhao, AI Tinghua. The Visualization and Analysis of POI Features under Network Space Supported by Kernel Density Estimation[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(1): 82-90. DOI: 10.11947/j.AGCS.2015.20130538.

[14] BORRUSO G. Network Density and the Delimitation of Urban Areas[J]. Transactions in GIS, 2003, 7(2): 177-191.

[15] WORTON B J. Kernel Methods for Estimating the Utilization Distribution in Home-range Studies[J]. Ecology, 1989, 70(1): 164-168.

[16] CAI Xuejiao, WU Zhifeng, CHENG Jiong. Using Kernel Density Estimation to Assess the Spatial Pattern of Road Density and Its Impact on Landscape Fragmentation[J]. International Journal of Geographical Information Science, 2013, 27(2): 222-230.

[17] YING Lingxiao, SHEN Zehao, CHEN Jiding, et al. Spatiotemporal Patterns of Road Network and Road Development Priority in Three Parallel Rivers Region in Yunnan, China: An Evaluation Based on Modified Kernel Distance Estimate[J]. Chinese Geographical Science, 2014, 24(1): 39-49.

[18] SCHEEPENS R, WILLEMS N, VAN DE WETERING H, et al.Composite Density Maps for Multivariate Trajectories[J]. IEEE Transactions on Visualization and Computer Graphics, 2011, 17(12): 2518-2527.

[19] LEE D, HAHN M. A Study on Density Map Based Crash Analysis[C]∥Proceedings of 2014 International Conference on Information Science and Applications (ICISA). Seoul, South Korea: IEEE, 2014: 1-3.

(責任編輯：宋啟凡)

A Kernel Density Estimation Method for Linear Features in Network Space

TANG Luliang1, KAN Zihan1, LIU Huihui1,2, SUN Fei1, WU Huayi1

1. Department of State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan 430079, China; 2. School of Geodesy and Geomatics, Wuhan University, Wuhan 430079, China

Kernel density estimation(KDE) is an important method for analyzing spatial distributions of point features or linear features. So far the KDE methods for linear features analyze the features’ spatial distributions by producing a smooth density surface over 2D homogeneous planar space, However, the planar KDE methods are not suited for analyzing the distribution characteristics of certain kinds of linear events, such as traffic jams, queue at intersections and taxi carrying passenger events, which usually occur in inhomogeneous 1D network space. This article presents a KDE method for linear features in network space, which first confirms the density distribution of each single linear feature, then computes the density distributions of all linear features in terms of distance and topology relationship in network space. This article extracts “pick-up” linear events from taxi GPS trajectory data and analyzes their distribution patterns in network space. By comparison with existing methods, experiment results show that the proposed method is able to represent the distribution patterns of linear events in network space more accurately.

linear events; network space; kernel density estimation(KDE); spatial-temporal GPS trajectory

The National Natural Science Foundation of China (Nos. 41671442;41571430;41271442)

TANG Luliang(1973—)，male, professor,PhD, PhD supervisor, majors in space-time GIS, trajectory data analyzing and mining.

KAN Zihan

唐爐亮，闞子涵，劉匯慧，等.網絡空間中線要素的核密度估計方法[J].測繪學報，2017,46(1)：107-113.

10.11947/j.AGCS.2017.20150158. TANG Luliang, KAN Zihan, LIU Huihui,et al.A Kernel Density Estimation Method for Linear Features in Network Space[J]. Acta Geodaetica et Cartographica Sinica,2017,46(1):107-113. DOI:10.11947/j.AGCS.2017.20150158.

P208

A

1001-1595(2017)01-0107-07

國家自然科學基金(41671442；41571430；41271442)

2015-03-25

唐爐亮(1973—)，男，教授，博士，博士生導師，研究方向為時空GIS、軌跡大數據分析與挖掘。

E-mail： tll@whu.edu.cn

闞子涵

E-mail： kzh@whu.edu.cn

修回日期： 2016-10-08