江慧娟，余 洋

（1.武漢大學 遙感信息工程學院，湖北 武漢 430079）

出租車載客熱點精細提取的改進DBSCAN算法

江慧娟1*，余 洋1

（1.武漢大學 遙感信息工程學院，湖北 武漢 430079）

隨著城市化水平的提高和居民公共交通出行的需求增長，要求有更精細化的聚類方法提取出租車載客的熱點區(qū)域。針對基于密度聚類在出租車數(shù)據(jù)聚類中存在的問題，設(shè)計一種基于路網(wǎng)約束的改進DBSCAN算法。該算法通過將行程距離引入DBSCAN算法中，改進原有DBSCAN算法在出租車數(shù)據(jù)聚類中存在的精細尺度聚類參數(shù)選擇和設(shè)置困難問題，彌補現(xiàn)有聚類算法在出租車載客熱點區(qū)域提取方面的不足。利用武漢市出租車GPS軌跡數(shù)據(jù)進行的實驗結(jié)果表明，在加入道路約束后，算法在出租車載客熱點區(qū)域的精確提取方面具有較好的效果。

載客熱點；密度聚類； DBSCAN算法；路網(wǎng)約束；出租車數(shù)據(jù)

當前研究中，基于出租車數(shù)據(jù)進行載客熱點的提取主要包括兩種方法[1,2]：一種是通過劃分統(tǒng)計單元的方式，將研究空間劃分為有限數(shù)目的單元以形成網(wǎng)格結(jié)構(gòu)，然后統(tǒng)計每個網(wǎng)格中載客點的數(shù)量，對載客數(shù)量超過閾值的網(wǎng)格按照空間鄰近進行合并，從而形成大小不同的相似特征區(qū)域，實現(xiàn)熱點區(qū)域的提取[3-5]。另一種方式采用無監(jiān)督聚類方式“自下而上”地發(fā)現(xiàn)出租車載客點的聚集情況[6-8]，通過遍歷一定時間內(nèi)的所有載客點，在計算載客點之間距離的基礎(chǔ)上，通過設(shè)置點的數(shù)量閾值和搜索半徑，計算點所在區(qū)域的密度，進而得到聚類，形成聚類熱點區(qū)域[9-11]。但這兩種方法都有一定的局限性。

本文提出一種顧及路網(wǎng)約束的改進DBSCAN算法（Road Limitation DBSCAN，簡稱RL-DBSCAN），該算法針對現(xiàn)有算法在出租車載客熱點區(qū)域提取結(jié)果的不足，將道路拓撲關(guān)系、路段長度信息作為約束條件加入聚類算法的相似性度量中，并利用武漢市出租車GPS軌跡數(shù)據(jù)進行了實驗。實驗結(jié)果表明，RLDBSCAN算法對出租車載客熱點區(qū)域的精確提取方面具有較好的效果，可為細粒度的城市載客熱點提取、居民出行時空特征分析、輔助居民生活進行智慧行為決策提供更精準的信息支持。

1 基于路網(wǎng)約束的改進DBSCAN算法

1.1 基于DBSCAN算法的載客熱點提取

DBSCAN算法是基于密度聚類算法中的一種簡單有效且比較典型的算法。算法主要通過調(diào)整Eps和MinPts兩個參數(shù)進行熱點和熱度的提取。由于這些出租車載客點一般沿道路分布，所以聚類結(jié)果容易產(chǎn)生條帶狀的類簇，而一般方法均以簇的質(zhì)心作為載客熱點，這樣就容易導(dǎo)致所提取的載客熱點難以準確反映實際的乘車熱點位置。如圖1所示，用不同的顏色表示聚類形成的類簇，可以發(fā)現(xiàn)紅色載客點形成的類簇，能反映這條道路上的乘車熱度較大，由于道路較長，若以這一類簇的質(zhì)心作為熱點，則難以真實反映這條道路上不同地段的熱點聚類情況。

圖1 DBSCAN算法形成的載客聚類結(jié)果

分析DBSCAN算法的基本原理，可以發(fā)現(xiàn)由于該算法主要只考慮了載客點之間的距離和每個類簇包含的點數(shù)目，因此，算法容易將處于道路交叉點（圖2a）或同一路段不同方向的載客點聚為一類（圖2b）。

圖2 DBSCAN算法在不考慮道路拓撲關(guān)系時產(chǎn)生的聚類結(jié)果

城市道路上存在大量交通標識的限制，例如紅綠燈、轉(zhuǎn)向、限行等。如果需要能更加精確地分辨出道路載客熱點，必須考慮道路拓撲關(guān)系對載客點間距離計算的影響，即載客點間是否密度可達需要考慮二者之間的行程距離，如圖3所示。

圖3 道路網(wǎng)絡(luò)中載客點間的距離

因此，在道路網(wǎng)絡(luò)中，p與q之間的行程距離計算可寫成：

一方面，城市道路中兩點的距離一般是兩點間的網(wǎng)絡(luò)距離，可以通過計算兩載客點之間的道路最短距離得到，可記為distsp（p,q）；另一方面，在城市系統(tǒng)中由p至q如果經(jīng)過路口，需要減速或停留，因此p與q之間的道路交叉口停駐時間distTime(p,q)同樣應(yīng)計算在可達性中，distTime(p,q)可通過計算道路交叉口數(shù)量N得到：

其中，WaitTimeavg為城市路口的平均停留時間，Speedavg為城市車輛的平均行程速度。在對點p查找鄰近載客點時，可以用行程距離替代歐氏距離，從而實現(xiàn)這一目標。

1.3 顧及路網(wǎng)約束的載客點聚類算法流程

基于以上分析，本文設(shè)計了RL-DBSCAN算法，在計算兩點間距離時，用行程距離dist(p,q)進一步判斷，將歐氏距離鄰近但是網(wǎng)絡(luò)距離較遠的載客點進行區(qū)分。具體算法如表1所示。

算法1 RL-DBSCAN主算法

輸入： D — 全部載客點集合，eps — 鄰域半徑，mPts—最少載客點個數(shù)

10. ExpandCluster(p, NeighborPts, C, eps, mPts)

其中， ExpandCluster函數(shù)用于將鄰近載客聚類簇進行合并。

算法2 生成聚類簇ExpandCluster

輸入： p — 載客點，NeighborPts— 某點p的所有鄰近載客點集合，C—新聚類載客數(shù)據(jù)集，eps — 鄰域半徑，mPts—最少載客點個數(shù)

1. add p to cluster C

2. for each point p' in NeighborPts

3. if p' is not visited

4. mark p' as visited

5. NeighborPts' = regionQuery(p', eps)

6. if Density (NeighborPts) < mPts

7. NeighborPts = NeighborPts joined with NeighborPts'

8. if p' is not yet member of any cluster

9. add P' to cluster C

2 系統(tǒng)實驗與分析

本文的實驗運行環(huán)境是Windows操作系統(tǒng)，實驗的硬件配置是Intel(R) Core(TM)i5-4509 CPU@3．30 GHz八核CPU，內(nèi)存為8 GB，算法采用python語言編寫。

2.1 算法實驗數(shù)據(jù)集

本文采用武漢市的出租車軌跡數(shù)據(jù)作為算法實驗測試數(shù)據(jù)集，數(shù)據(jù)中包含有出租車編號、時間、出租車經(jīng)緯度、方向（正N 0°，正E 180°）、速度（km）、ACC狀態(tài) （開：車是發(fā)動的，關(guān)：停車熄火） 、載客狀態(tài)（0表示出租車空駛，1表示出租車載客）。

實驗采用的數(shù)據(jù)集采用2014-05-01出租車軌跡數(shù)據(jù)，數(shù)據(jù)集覆蓋地理空間的經(jīng)度范圍為[113°41',115°05']，維度范圍為 [29°58',31°22']，區(qū)域面積約為1 171．70 km2，覆蓋武漢市主城區(qū)及周邊區(qū)域。包含了9 700輛車共1 130萬條出租車定位數(shù)據(jù)。

2.2 數(shù)據(jù)預(yù)處理

原始數(shù)據(jù)以TXT文本形式保存，在進行載客點聚類之前，需要對原始數(shù)據(jù)進行預(yù)處理主要包括屬性值異常數(shù)據(jù)剔除、數(shù)據(jù)空間化、坐標偏移數(shù)據(jù)剔除等。

GPS數(shù)據(jù)本身存在精度誤差，在與武漢市基礎(chǔ)地圖數(shù)據(jù)疊加的時候會出現(xiàn)一定的偏離，導(dǎo)致載客點不在對應(yīng)的出行路徑上，影響GPS點提取道路信息的準確性，因此需要進行道路匹配。其基本原理是將待匹配的GPS點數(shù)據(jù)與路網(wǎng)數(shù)據(jù)進行對比，搜索出對應(yīng)的道路線作為待匹配的樣本。通過道路匹配算法，計算匹配樣本與匹配點的匹配相似度，選取匹配相似度最高的匹配樣本最為GPS點的最終匹配道路，獲取浮動車軌跡點的準確定位點。

2.3 聚類結(jié)果統(tǒng)計

為了比較兩種算法在不同參數(shù)條件下的聚類穩(wěn)定性，本文分別選擇了聚類簇中包含點的最小閾值分別為3、4、6、8，聚類半徑eps在50 m、100 m、200 m、300 m、400 m、500 m時的類簇數(shù)量變化情況進行實驗分析，結(jié)果如圖4所示?？梢园l(fā)現(xiàn)，在加入道路約束后，聚類結(jié)果對聚類半徑的閾值不敏感，當閾值增大到一定程度后聚類結(jié)果變化較小。聚類結(jié)果對聚類簇包含點的數(shù)量閾值較為敏感，不同的點數(shù)閾值得到的聚類結(jié)果差異較大。同時，在考慮道路約束的情況下，當聚類簇包含的最小點閾值不變時，聚類半徑達到200 m后RL-DASCAN得到的聚類簇數(shù)量基本趨于穩(wěn)定，不再隨半徑的變化而變化，而DBSCAN算法得到的類簇數(shù)量則根據(jù)聚類半徑的變化而快速下降，這是因為當半徑變大后，DBCSAN算法將更多鄰近的類簇合并到了一起，而RL-DBSCAN算法中由于歐氏距離鄰近的簇在行程距離下并不能形成合并，去除了部分聚類中的噪音。

圖4 DBSCAN與RL-DBSCAN算法不同參數(shù)聚類數(shù)量統(tǒng)計

圖5是比較在不同條件下兩種算法生成的聚類簇所包含的平均載客點數(shù)?？梢钥闯鯠BSCAN算法得到的聚類簇中平均載客點數(shù)量隨著聚類半徑的增加而不斷增加，而RL-DBSCAN算法得到聚類簇包含的載客點數(shù)則始終變化較小。RL-DBSCAN算法得到的聚類簇大小受聚類半徑和最小簇內(nèi)點數(shù)量的參數(shù)影響較小，對于載客區(qū)域的精細提取與分析而言，這種結(jié)果可以更好地為分析某個微觀區(qū)域的載客熱度變化情況提供數(shù)據(jù)支持。

2.4 聚類效果實驗分析

為了對比RL-DBSCAN和DBSCAN算法的差異，提取出一些典型區(qū)域（交叉路口，雙向道路）的浮動車軌跡，對算法進行實驗分析。實驗結(jié)果表明，DBSCAN算法通常將處于道路交叉口處且密度比較大的軌跡點都歸為一類（圖6a），而RL-DBSCAN算法在處理交叉路口軌跡點時，對各個不同方向的軌跡點都能進行有效的聚類（圖6b）。

圖5 DBSCAN與RL-DBSCAN簇內(nèi)平均載客點數(shù)量統(tǒng)計

圖6 十字路口聚類結(jié)果

在處理對向道路上的軌跡點時，DBSCAN算法會籠統(tǒng)地將同一段路單方向不通的軌跡點聚類成簇（圖 7a），這并不符合實際情況，RL-DBSCAN算法對于軌跡點之間距離的處理中加入了路網(wǎng)的限制，因此能有效處理雙向道路的軌跡點聚類（圖7b）,不同方向的軌跡點即被歸類成不同的簇，聚類結(jié)果更符合其空間數(shù)據(jù)的分布規(guī)律。

同時，選取武漢市幾個具體的區(qū)域，將類別平均中心點作為熱點，分別用DBSCAN和RL-DBSCAN算法提取同一時段的熱點區(qū)域進行對比分析（圖8）。提取的熱點分別用綠色點和紅色點表示，點的大小表示熱點所在類別所包含的載客點數(shù)目的多少。

圖7 雙向道路聚類結(jié)果

從街道口附近熱點圖來看（圖8a），RL-DBSCAN算法在武珞路上提取到鵬程蕙園小區(qū)路口及其馬路對面、新世界百貨、未來城小區(qū)門口以及未來城大酒店附近的熱點，而DBSCAN算法提取出的熱點偏離了道路，并不符合實際。漢口火車站附近（圖8b），DBSCAN算法忽略了公交站牌處和車站南廣場附近以及路邊的多個熱點，其顯示的熱點在地鐵出口，而地鐵附近并沒有提取到上客點。改進算法不僅對載客熱點區(qū)域進行了細致的提取，而且道路兩邊的熱點信息也沒有忽略。所以，對比DBSCAN算法，改進算法在提取熱點時更加準確，更加符合實際情況。

2.5 聚類性能評價

由于載客點數(shù)據(jù)大多為歷史數(shù)據(jù)，實地檢驗較為困難，本文從內(nèi)部指標對兩種聚類算法的結(jié)果進行比較。主 要 引 入 了 Dunn[12]，Davies-Bouldin[13]，Silhouette[14]，I[15]等4種常見的聚類算法內(nèi)部評價指標。它們都是通過計算各類中對象之間的距離以及類別之間對象的距離來衡量聚類質(zhì)量的，即在類內(nèi)緊密度和類間分離度之間尋找一個平衡點，其中Dunn、 Silhouette、I指標最大化時聚類效果最優(yōu)，Davies-Bouldin是指標最小化時聚類效果最優(yōu)。

圖8 DBSCAN與RL-DBSCAN算法提取熱點區(qū)域?qū)Ρ葓D

表1 兩種算法的聚類評價指標比較

表1是兩種算法在不同參數(shù)下各指標的計算情況，不論是DBSCAN還是RL-DBSCAN算法，各指標在eps=100時的值都優(yōu)于其他情況，說明該參數(shù)下的聚類質(zhì)量比其他參數(shù)下要好。對比在參數(shù)相同情況下兩種算法的各個指標可發(fā)現(xiàn)，RL-DBSCAN算法的各個指標值普遍優(yōu)于DBSCAN算法，進一步說明了RLDBSCAN算法在提取精細熱點區(qū)域上的優(yōu)勢。

為了測試該算法的性能，抽取同一數(shù)據(jù)集分別采用DBSCAN算法、RL-DBSCAN算法進行試驗并進行橫向?qū)Ρ?，結(jié)果如表1所示。從實驗測試可知，雖然改進算法提取效果較好，由于算法在進行路網(wǎng)距離計算時花費時間較多，導(dǎo)致整個算法運行時間較長，所需內(nèi)存也較大。所以算法在優(yōu)化程度上有待進一步提高。

表2 算法性能測試

3 結(jié) 語

本文利用武漢市的出租車GPS軌跡數(shù)據(jù)，采用基于密度的DBSCAN算法對提取出的載客點進行聚類分析，提取載客熱點區(qū)域。鑒于傳統(tǒng)DBSCAN算法提取范圍分布廣的特點，根據(jù)出租車數(shù)據(jù)與道路數(shù)據(jù)的分布特征，將路網(wǎng)約束引入到傳統(tǒng)的DBSCAN算法中，提出一種基于RL-DBSCAN算法的出租車載客數(shù)據(jù)聚類方法。該算法針對現(xiàn)有算法在出租車載客熱點區(qū)域提取結(jié)果的不足，將道路拓撲關(guān)系及路段長度信息作為約束條件加入DBSCAN算法的點相似性判斷中，并利用武漢市出租車GPS軌跡數(shù)據(jù)進行實驗。實驗結(jié)果表明，RL-DBSCAN算法對出租車載客熱點區(qū)域的精確提取方面具有較好的效果，能更好地反映道路的載客熱度。通過傳統(tǒng)算法和改進算法的比較，證明改進算法對于道路兩邊或者十字路口處的載客點在提取效果上有一定的優(yōu)勢，但算法運行速度較慢，優(yōu)化程度有待提高，在后期的研究中計劃加入并行處理的方法，以提高計算速度。

[1] 柴彥威, 張文佳, 張艷,等． 微觀個體行為時空數(shù)據(jù)的生產(chǎn)過程與質(zhì)量管理:以北京居民活動日志調(diào)查為例[J]．人文地理, 2009(6):1-9

[2] 吳志峰,柴彥威,黨安榮,等． 地理學碰上“大數(shù)據(jù)”:熱反應(yīng)與冷思考[J]．地理研究, 2015, 34(12): 2 207-2 221

[3] Qi G, Li X, Li S, et al． Measuring Social Functions of City Regions from Large-scale Taxi Behaviors[C]．IEEE International Conference on Pervasive Computing & Communications, IEEE,2011:384-388

[4] Zheng Y, Liu Y, Yuan J, et al． Urban Computing with Taxicabs[C]．International Conference on Ubiquitous Computing,ACM,2011:89-98

[5] Liu Y, Kang C,Gao S, et al． Understanding Intra-urban Trip Patterns from Taxi Trajectory Data[J]． Journal of Geographical Systems, 2012, 14(4):1-21

[6] Zheng Y, Capra L, Wolfson O, Yang H． Urban Computing:Concepts, Methodologies, and Applications[J]． ACM Transactions on Intelligent Systems & Technology, 2014, 5(3):222–235

[7] Tang J, Liu F, Wang Y, et al． Uncovering Urban Human Mobility from Large Scale Taxi GPS Data[J]． Physica A Statistical Mechanics & Its Applications,2015, 438(15):140-153

[8] Yuan J,Zheng Y, Xie X． Discovering Regions of Different Functions in a City Using Human Mobility and POIs[C]．Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,ACM,2012． 186-194

[9] 廖律超, 蔣新華, 鄒復(fù)民,等． 浮動車軌跡數(shù)據(jù)聚類的有向密度方法[J]．地球信息科學學報, 2015(10):1 152-1 161

[10] Ester M, Kriegel H P, Sander J, et al． A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise[C]．KDD,1996, 96(34): 226-231

[11] 莊立堅,何兆成,楊文臣,等．基于大規(guī)模浮動車數(shù)據(jù)的交叉口轉(zhuǎn)向規(guī)則自動提取算法[J]．武漢理工大學學報（交通科學與工程版）,2013, 37(5): 1 084-1 088

[12] Dunn J C． Well-Separated Clusters and Optimal Fuzzy Partitions[J]． Journal of Cybernetics, 2008, 4(1):95-104

[13] Hubert L J, Arabie P． Comparing Partitions[J]． J Classification,1985(2):193-218

[14] Rousseeuw P J． Silhouettes: A Graphical Aid to the Interpretation and Validation of Cluster Analysis[J]． Journal of Computational& Applied Mathematics, 1987, 20(20):53-65

[15] Maulik U, Bandyopadhyay S． Performance Evaluation of Some Clustering Algorithms and Validity Indices．[J]． IEEE Transactions on Pattern Analysis & Machine Intelligence, 2002, 24(12):1 650-1 654

P208

B

1672-4623（2017）10-0016-05

10.3969/j.issn.1672-4623.2017.10.005

2016-09-29。

項目來源：國家自然科學基金資助項目（41471326）；中央高?；究蒲袠I(yè)務(wù)費專項資金資助項目（204216kf0190）。（*為通訊作者）

江慧娟，碩士，研究方向為軌跡數(shù)據(jù)挖掘。