許春暉, 張安勤, 陳 鈺

(上海電力大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 上海 200090)

城市的發(fā)展使得市民對出行的便利、速度的要求隨之提升。對于城市交通而言,出租車司機(jī)能快速地接到顧客,可有效緩解交通問題,提高市民對城市交通的滿意度。對于出租車司機(jī)而言,準(zhǔn)確找到乘客多的地方可以接到更多的顧客,收入也會相應(yīng)增加。

出租車軌跡具有時空特征。馮琦森[1]利用出租車GPS軌跡數(shù)據(jù)分析識別居民感興趣的熱點(diǎn)路徑和區(qū)域。張俊濤等人[2]提出了一種基于高斯定律的軌跡挖掘方法,發(fā)現(xiàn)城市居民出行行為的時空特征以及城市的熱點(diǎn)區(qū)域。馬云飛[3]利用空間聚類算法對出租車軌跡點(diǎn)數(shù)據(jù)進(jìn)行時空數(shù)據(jù)挖掘,獲取其隱含的出行規(guī)律信息。SUN J等人[4]開發(fā)了一種新的基于聚類的方案,可以利用基于軌跡和道路特征的多源信息來推薦出租車取車點(diǎn)。ZHU W等人[5]通過對各種交通影響因素的綜合,以保證接駁點(diǎn)的設(shè)置與實(shí)際交通狀況適應(yīng)。

城市的變化在時間的分布上具有周期性,在空間的分布上也具有一定的規(guī)律。MAO F等人[6]提出城市居民的出行在時間上具有一定的周期性,在一天的完整時刻表上具有上下班高峰時間,也有深夜的交通流低谷時間。在工作日與休息日,城市居民的主要出行活動也不同。在空間上,QI G D等人[7]初步考慮了3個典型的類別區(qū)域,通過出租車軌跡分析可以很準(zhǔn)確地分析出該區(qū)域出租車數(shù)量和社會活動模式。

出租車空間軌跡的聚類有不少難點(diǎn)。僅基于密度的聚類方法不能準(zhǔn)確地反映出出租車軌跡在空間上的分布,出租車在城市中心與城郊地區(qū)的分布密度有較大差異,密度的閾值較難設(shè)定。每個地區(qū)可以是城市居民的出發(fā)地也可以是目的地,而吸引力值僅能反映地區(qū)作為目的地的出租車流量。此外,城市道路情況分布較為復(fù)雜,廣場、停車場、高架道路等均會造成錯誤的數(shù)據(jù)統(tǒng)計(jì)。

在現(xiàn)有的出租車載客推薦算法中,鮑冠文等人[8]提出改進(jìn)的DBSCAN(Density-based Spatial Clustering of Application with Noise)密度聚類算法,用于出租車載客熱點(diǎn)區(qū)域挖掘,但要用A*尋路算法搜索最短路徑,開銷較大,且領(lǐng)域范圍大小會對更大范圍、更好載客點(diǎn)的推薦造成影響。針對這些問題,魏為民等人[9]提出了一種改進(jìn)的A*+算法,即在原有算式上添加父節(jié)點(diǎn)啟發(fā)式,并計(jì)算臨界值篩選候選節(jié)點(diǎn),從而使節(jié)點(diǎn)排查能力得到優(yōu)化,搜索效率得到提高。張明月[10]提出了一種基于時空聚類的出租車載客推薦地點(diǎn)生成方法,但在推薦熱點(diǎn)地區(qū)時,僅考慮了吸引力,存在一定的問題,因大多數(shù)情況下,吸引力高的區(qū)域往往是乘客下車的地方而不是載客的最佳地點(diǎn)。ZHENG L J等人[11]利用基于網(wǎng)格密度的GScan聚類算法對時空熱點(diǎn)區(qū)域進(jìn)行分析與挖掘,但基于密度的熱點(diǎn)區(qū)域挖掘不能反映市民對出租車的需求分布。

針對上述問題,本文提出了基于時空數(shù)據(jù)挖掘的出租車司機(jī)載客點(diǎn)推薦算法。該方法對城市熱點(diǎn)區(qū)域進(jìn)行聚類,同時計(jì)算某一地區(qū)的人口流入量與流出量。流出量表明該地區(qū)的人搭乘出租車的概率,與流入量相比,具有更高的推薦價值。然后對出租車司機(jī)的日?；顒臃秶M(jìn)行分析,推薦載客點(diǎn)。

1 基于HITSK的熱點(diǎn)區(qū)域聚類算法

HIST(Hypelink-induced Topic Search)[12]算法是子集傳播算法的代表算法,通過Authority和Hub這兩個權(quán)值對網(wǎng)頁的質(zhì)量進(jìn)行評估。其中,Authority指的是內(nèi)容權(quán)威度,即頁面被引用的次數(shù);Hub指的是鏈接權(quán)威度,即指向其他頁面的數(shù)量。K-means[13]算法是使用最廣泛的基于劃分的聚類算法,通過把n個對象分為k個簇使簇內(nèi)具有較高的相似度。HITS-K算法是基于改進(jìn)的HITS算法與K-means算法組合而來的。

現(xiàn)有熱點(diǎn)地區(qū)算法大多數(shù)基于地區(qū)吸引力,這對于人口流動統(tǒng)計(jì)來說不夠準(zhǔn)確。本文通過改進(jìn)的HITS算法計(jì)算地區(qū)的交通流量值TF,挖掘出交通熱點(diǎn)區(qū)域與潛在的交通樞紐。

1.1 算法描述

首先將地圖進(jìn)行劃分。針對具體區(qū)域從經(jīng)度和緯度上進(jìn)行網(wǎng)格劃分,在地圖上將經(jīng)度和緯度劃分成等長區(qū)間。對每個網(wǎng)格記錄下4個頂點(diǎn)的經(jīng)緯度坐標(biāo),實(shí)現(xiàn)地圖網(wǎng)格化。

將OD點(diǎn)與地圖網(wǎng)格進(jìn)行對照來聚類計(jì)算,將所有的OD點(diǎn)劃分到相應(yīng)的地圖網(wǎng)格中,并將每個網(wǎng)格作為聚類,根據(jù)聚類中OD點(diǎn)的個數(shù)計(jì)算每個網(wǎng)格對應(yīng)的人的流出值。SumiO=|O|表示在地區(qū)i中O點(diǎn)的個數(shù),代表從該區(qū)域流出的人數(shù)。SumiD=|D|表示在地區(qū)i中D點(diǎn)的個數(shù),代表從該區(qū)域流入的人數(shù)。

在網(wǎng)格聚類劃分的基礎(chǔ)上進(jìn)行改進(jìn)的HITS算法。每個網(wǎng)格取初始值為Authority(i)=SumiD,每個網(wǎng)格所占的D點(diǎn)數(shù)反應(yīng)了網(wǎng)格所在地區(qū)的初始Authority值。以每個網(wǎng)格依次為起點(diǎn),統(tǒng)計(jì)該網(wǎng)格到其余每個網(wǎng)格(除本網(wǎng)格外)的人數(shù)Ni,j,Ni,j表示地區(qū)i到地區(qū)j的人數(shù)。其中,i=1,2,3,…,n;j=1,2,3,…,n。

(1)

計(jì)算每個地區(qū)的Hub值,每個網(wǎng)格取初始值為Hub(i)=sumiO。每個地區(qū)節(jié)點(diǎn)新的吸引力Hub值為

(2)

每一步計(jì)算完 Authority和Hub后,對其進(jìn)行規(guī)范化。公式為

(3)

(4)

(5)

(6)

Authority代表地區(qū)人口流入量;Hub代表地區(qū)人口流出量,所以地區(qū)的完整TF值是將Authority值與Hub值相結(jié)合,為

TF(i)=Authority(areai)+Hub(areai)

(7)

式中:TF(i)——地區(qū)i的交通總流量值。

最后,將迭代后的數(shù)據(jù)結(jié)果記錄下來,作為地區(qū)對地區(qū)的完整TF值,利用K-means算法對地區(qū)吸引力值進(jìn)行聚類。

2 出租車接客點(diǎn)推薦

不同的出租車司機(jī)駕駛模式不同,同一個出租車司機(jī)每天的活動軌跡也不相同。但大多數(shù)時間他們會在自己較為熟悉的區(qū)域活動。為了將出租車司機(jī)的日常活動核心區(qū)域挖掘出來。我們使用標(biāo)準(zhǔn)差橢圓[14]來描述出租車司機(jī)的活動軌跡。

計(jì)算軌跡中心位置的公式為

(8)

式中:xi——第i個軌跡坐標(biāo)的經(jīng)度;

yi——第i個軌跡坐標(biāo)的緯度;

n——軌跡點(diǎn)個數(shù)。

計(jì)算標(biāo)準(zhǔn)距離偏差的公式為

(9)

計(jì)算橢圓的偏轉(zhuǎn)角度的公式為

(10)

(11)

(12)

(13)

計(jì)算橢圓長短軸長度的公式為

(14)

(15)

將不同日期的出租車司機(jī)活動范圍重疊,選擇最大橢圓作為其日?；顒臃秶８鶕?jù)出租車司機(jī)的空間活動模式,選取推薦載客點(diǎn)。由于城市中不同區(qū)域具有不同的功能分區(qū),在不同的時段人們在不同的功能分區(qū)中移動。我們將不同時段的熱點(diǎn)地區(qū)進(jìn)行聚類分析。首先計(jì)算每一類熱點(diǎn)區(qū)域到出租車司機(jī)日常活動范圍的距離,取出每一類熱點(diǎn)區(qū)域聚類中前10個距出租車司機(jī)日?；顒臃秶嚯x最短的區(qū)域。對于挑選出來的區(qū)域判斷其Hub值。Hub值越高,代表上車的人數(shù)越多。

3 實(shí)驗(yàn)分析

3.1 數(shù)據(jù)格式

本文采用上海市出租車GPS數(shù)據(jù)。上海出租車GPS數(shù)據(jù)包含約5萬輛出租車的數(shù)據(jù),每輛車約隔1 min做一次記錄。其中,從2014年12月28日至2015年1月10日的上海出租車GPS原始數(shù)據(jù)有91.4 G,數(shù)據(jù)字段格式如表1所示。

表1 數(shù)據(jù)字段描述

3.2 預(yù)處理

實(shí)際的GPS數(shù)據(jù)包括由交通與人為因素造成的異常點(diǎn)與冗余數(shù)據(jù),不能直接用于軌跡數(shù)據(jù)的分析與挖掘。因此,需運(yùn)用Spark對數(shù)據(jù)進(jìn)行預(yù)處理。Spark 是一個分布式平臺,支持規(guī)模較大數(shù)據(jù)的快速處理。它既可以在一臺機(jī)器上運(yùn)行,也可以協(xié)調(diào)在多臺機(jī)器上進(jìn)行數(shù)據(jù)處理,符合需要支持任意數(shù)據(jù)規(guī)模的要求。在預(yù)處理中,Spark的排序語句對出租車ID和時間兩個維度進(jìn)行排序;用過濾功能與判斷語句將經(jīng)緯度不在上海市區(qū)的出租車軌跡進(jìn)行篩選,對停留時間較長的出租車軌跡進(jìn)行判斷與刪除;最后用Scala算法將OD點(diǎn)與原始數(shù)據(jù)集合分離。處理的步驟如下。

(1) 記錄中的GPS數(shù)據(jù)在出租車ID和時間兩個維度上進(jìn)行數(shù)據(jù)排序。

(2) 對經(jīng)緯度數(shù)據(jù)越界進(jìn)行處理。本文以上海市轄區(qū)為研究對象,不在此地理坐標(biāo)范圍內(nèi)的記錄予以去除。

(3) 對在一個地點(diǎn)停留太多時間的GPS數(shù)據(jù)進(jìn)行刪除。

(4) 去除出租車ID、經(jīng)緯度和記錄時間外的數(shù)據(jù),減少數(shù)據(jù)的維度。

(5) 對數(shù)據(jù)中的OD點(diǎn)數(shù)據(jù)進(jìn)行分析,出租車軌跡中間數(shù)據(jù)與OD點(diǎn)需要分離。

預(yù)處理后OD點(diǎn)數(shù)據(jù)與中間軌跡數(shù)據(jù)分離,OD點(diǎn)數(shù)據(jù)有4.28 G。

3.3 地區(qū)吸引力值聚類

對于東經(jīng)120°51′到122°12′,北緯30°40′到31°53′的上海地圖,將其經(jīng)度和緯度劃分成等長的小區(qū)間,每個柵格經(jīng)緯度之間的差為0.02,將經(jīng)度劃分成68個區(qū)間,緯度劃分成60個區(qū)間,共計(jì)4 080個地區(qū)。記錄每個網(wǎng)格下4個頂點(diǎn)的經(jīng)緯度坐標(biāo)。地圖柵格化效果如圖1所示。

圖1 地圖柵格化效果

地圖柵格化后,將OD點(diǎn)與地圖網(wǎng)格對照進(jìn)行聚類計(jì)算。如果O點(diǎn)在以4個經(jīng)緯度坐標(biāo)形成的四邊形中,則將它們聚類在一起。所有的OD點(diǎn)劃分到相應(yīng)的地圖網(wǎng)格中,每個網(wǎng)格作為一個聚類,根據(jù)聚類中樣本的個數(shù)計(jì)算每個網(wǎng)格的吸引力值。得到的聚類結(jié)果如圖2所示。圖2中,白色的點(diǎn)O表示該柵格中原有人數(shù),黑色的點(diǎn)D表示該柵格為終點(diǎn)。

圖2 聚類結(jié)果示意

通過HITS-K算法對地區(qū)吸引力值進(jìn)行計(jì)算,對計(jì)算結(jié)果進(jìn)行聚類,圖3展現(xiàn)了聚類后的地區(qū)分布。圖3中不同顏色的點(diǎn)表示不同的簇。地圖上簇的分布具有規(guī)律,吸引力值由城市中心向郊區(qū)遞減,最外層的吸引力最弱。一些場所雖遠(yuǎn)離市中心卻依然人數(shù)較多,如機(jī)場、橋梁或隧道出入口。這符合城市的空間布局。

圖3 熱點(diǎn)地區(qū)聚類分布

圖4是出租車司機(jī)a的日?；顒臃秶哪M圖。由圖4可以看出,出租車司機(jī)a的日?；顒勇肪€為城市的市中心區(qū)域,那里道路較多,人流量也相對較大。

圖4 司機(jī)a日?；顒雍诵姆秶M

結(jié)合本文算法,出租車司機(jī)a在早上與下午的推薦活動范圍分別如圖5和圖6所示。

圖5 早上推薦載客點(diǎn)

圖6 下午推薦載客點(diǎn)

由圖5和圖6可知,早上市民的主要活動方向?yàn)閺淖≌焦ぷ鲄^(qū)。雖然這段時間內(nèi)市中心與周圍的居民區(qū)都是熱點(diǎn)區(qū)域,且市中心的人口密度更大,但是人們大多是在市中心下車,上車的人相對較少,故不推薦在市中心搜尋顧客;而在推薦右下角的區(qū)域中,出租車司機(jī)a幾乎不去,實(shí)際上該區(qū)域同樣有顧客需要搭乘出租車。

下午市民需要從工作區(qū)返回居住區(qū),或從工作區(qū)去娛樂區(qū)。在上海,娛樂區(qū)與工作區(qū)的城市功能分區(qū)不明顯,都集中在市中心。相比周圍的居民住宅區(qū),娛樂區(qū)與工作區(qū)在這段時間的人流量較大,所以下午的推薦區(qū)域在市中心附近。

圖7是在出租車司機(jī)載客點(diǎn)挖掘方法中常用的傳統(tǒng)DBSCAN聚類方法。從圖7可以看出,出租車司機(jī)的推薦載客活動點(diǎn)同樣是集中在市中心區(qū)域。在離市中心較遠(yuǎn)的區(qū)域也有推薦,但該區(qū)域遠(yuǎn)離出租車司機(jī)的日?；顒狱c(diǎn),司機(jī)不太可能偏離日常活動軌跡去一個較遠(yuǎn)的地方載客。在市中心外圍有一圈細(xì)長的推薦帶圍繞,這些區(qū)域的載客點(diǎn)相互距離較遠(yuǎn),分布較稀疏,它們本來不應(yīng)該被推薦,但DBSCAN將他們聚類到一起形成一個較大的簇,對推薦造成了誤差。此外,DBSCAN方法的各個參數(shù)設(shè)定沒有依據(jù),不同的參數(shù)結(jié)果不同,對最終推薦結(jié)果會有不同的影響。

圖7 DBSCAN推薦載客點(diǎn)

4 結(jié) 語

針對傳統(tǒng)DBSCAN方法的不足,本文提出了基于時空數(shù)據(jù)挖掘的出租車司機(jī)載客點(diǎn)推薦算法。首先,通過使用Spark對城市路網(wǎng)信息、出租車軌跡數(shù)據(jù)進(jìn)行預(yù)處理;其次,通過HITS-K對具體地區(qū)進(jìn)行交通熱點(diǎn)地區(qū)聚類,充分體現(xiàn)人口流動在時間和空間維度上的變化;再次,用標(biāo)準(zhǔn)差橢圓對出租車司機(jī)的日?；顒臃秶M(jìn)行分析;最后,根據(jù)熱點(diǎn)區(qū)域聚類與熱點(diǎn)區(qū)域中的Hub值對特定的出租車司機(jī)進(jìn)行載客點(diǎn)推薦。與傳統(tǒng)的DBSCAN方法相比,該方法在司機(jī)日?；顒雍诵膮^(qū)域周圍挖掘出了司機(jī)不經(jīng)常去的推薦載客點(diǎn),證明了方法本身的有效性。