江慧娟，余 洋

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

出租車載客熱點(diǎn)精細(xì)提取的改進(jìn)DBSCAN算法

江慧娟1*，余 洋1

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

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

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

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

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

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

1.1 基于DBSCAN算法的載客熱點(diǎn)提取

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

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

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

圖2 DBSCAN算法在不考慮道路拓?fù)潢P(guān)系時(shí)產(chǎn)生的聚類結(jié)果

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

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

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

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

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

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

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

算法1 RL-DBSCAN主算法

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

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

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

算法2 生成聚類簇ExpandCluster

輸入： p — 載客點(diǎn)，NeighborPts— 某點(diǎn)p的所有鄰近載客點(diǎn)集合，C—新聚類載客數(shù)據(jù)集，eps — 鄰域半徑，mPts—最少載客點(diǎn)個(gè)數(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)實(shí)驗(yàn)與分析

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

2.1 算法實(shí)驗(yàn)數(shù)據(jù)集

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

實(shí)驗(yàn)采用的數(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文本形式保存，在進(jìn)行載客點(diǎn)聚類之前，需要對(duì)原始數(shù)據(jù)進(jìn)行預(yù)處理主要包括屬性值異常數(shù)據(jù)剔除、數(shù)據(jù)空間化、坐標(biāo)偏移數(shù)據(jù)剔除等。

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

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

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

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

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

2.4 聚類效果實(shí)驗(yàn)分析

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

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

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

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

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

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

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

2.5 聚類性能評(píng)價(jià)

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

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

表1 兩種算法的聚類評(píng)價(jià)指標(biāo)比較

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

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

表2 算法性能測試

3 結(jié) 語

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

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

[2] 吳志峰,柴彥威,黨安榮,等． 地理學(xué)碰上“大數(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ù)民,等． 浮動(dòng)車軌跡數(shù)據(jù)聚類的有向密度方法[J]．地球信息科學(xué)學(xué)報(bào), 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] 莊立堅(jiān),何兆成,楊文臣,等．基于大規(guī)模浮動(dòng)車數(shù)據(jù)的交叉口轉(zhuǎn)向規(guī)則自動(dòng)提取算法[J]．武漢理工大學(xué)學(xué)報(bào)（交通科學(xué)與工程版）,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。

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

江慧娟，碩士，研究方向?yàn)檐壽E數(shù)據(jù)挖掘。