基于Hive的海量公交客流起訖點(diǎn)挖掘方法

許智宏， 王怡崢， 王利琴*， 董永峰

(1. 河北工業(yè)大學(xué)人工智能與數(shù)據(jù)科學(xué)學(xué)院,天津 300401；2. 河北省大數(shù)據(jù)計(jì)算重點(diǎn)實(shí)驗(yàn)室,天津 300401)

城市公交系統(tǒng)的發(fā)展和優(yōu)化,需要全面而又準(zhǔn)確的客流分析。在實(shí)際的客流分析工作中經(jīng)常使用公交客流起訖點(diǎn)(origin-destination，OD)。OD是對乘坐公交車的乘客一次出行的描述,其中O代表起點(diǎn),即乘客的上車站點(diǎn)；D代表終點(diǎn),即乘客的下車站點(diǎn)。按照客流OD統(tǒng)計(jì)一個時間段內(nèi)各站點(diǎn)上、下車人數(shù)并繪制成矩陣,即可得出OD矩陣(origin-destination matrix)。OD矩陣可視化后,可直觀地看出站點(diǎn)的客流量大小,以分析公交運(yùn)營的現(xiàn)狀。OD可作為靜態(tài)交通規(guī)劃的基礎(chǔ)數(shù)據(jù)[1],對于智慧交通的建設(shè)[2]具有重要的現(xiàn)實(shí)意義。然而,在實(shí)際的交通規(guī)劃任務(wù)中,以合理的時間和資源開銷,挖掘、獲取大量的OD數(shù)據(jù),是一項(xiàng)具有挑戰(zhàn)性的任務(wù)。

1 相關(guān)研究

不同于早期OD獲取所采用的人工跟車調(diào)查方法,現(xiàn)今OD的挖掘主要依靠車聯(lián)網(wǎng)設(shè)備在公交運(yùn)營過程中產(chǎn)生的數(shù)據(jù),包括IC刷卡記錄、全球定位系統(tǒng)(global positioning system，GPS)定位記錄、調(diào)度記錄等。OD挖掘需要解決兩個問題:上車站點(diǎn)的匹配和下車站點(diǎn)的預(yù)測。由于刷卡機(jī)、調(diào)度機(jī)、位置記錄儀這些不同的設(shè)備分別有各自的數(shù)據(jù)模型,上車站點(diǎn)匹配實(shí)質(zhì)上是對同一個公交的不同設(shè)備所產(chǎn)生的數(shù)據(jù)做關(guān)聯(lián)操作。常見的方法是:若有調(diào)度表,則刷卡信息表匹配調(diào)度表直接得到站點(diǎn)記錄；若無調(diào)度表則按照GPS定位記錄推算出每次刷卡得到的站點(diǎn)；兩者均無的情況較少,一般使用API或其他手段補(bǔ)全站點(diǎn)信息。Cui[3]以調(diào)度表每條時間記錄為中心,以5 min的閾值匹配刷卡記錄。Wang[4]提出線路-天-出行-點(diǎn)位的層級匹配方法,匹配調(diào)度表中同分鐘的記錄,若匹配失敗,則增加30 s再進(jìn)行匹配,若刷卡時間落在前一站出站時間與后一站進(jìn)站時間之間,找時間差最近的記錄。鄔群勇等[5]以刷卡時間為中心,向前3 min向后7 min作為閾值匹配多條調(diào)度記錄,之后逐一相減取最小的時間差。豐海寬[6]利用IC卡數(shù)據(jù)介于當(dāng)前站點(diǎn)和下一站進(jìn)站時間的不等關(guān)系,直接匹配當(dāng)前站點(diǎn)作為上車站點(diǎn)。李佳怡等[7]先將時間排序,對多個GPS記錄中的時間相減,取最短時間距離,利用DBSCAN聚類方法由經(jīng)緯度識別站點(diǎn)。鄧一凌等[8]將每條刷卡數(shù)據(jù)匹配兩條時間較近的GPS記錄并計(jì)算坐標(biāo)和置信度,匹配完成后應(yīng)用DPSCAN空間聚類反推站點(diǎn)位置。

下車站點(diǎn)的匹配有兩種常見的方法:基于優(yōu)化算法的下車站點(diǎn)推算、單獨(dú)使用出行鏈算法(trip-chaining method)或結(jié)合基于概率的推算方法預(yù)測下車站點(diǎn)。極大熵模型[9]、雙層模型[10]等基于優(yōu)化算法的OD推算方法,優(yōu)勢在于精確反推OD矩陣或OD數(shù)值,但很難在大量數(shù)據(jù)中按照每條刷卡記錄精確至每個乘客的下車站點(diǎn)位置。出行鏈算法可追溯至早期國外學(xué)者對地鐵客流OD的挖掘[11],也有很多在公交客流OD挖掘流程的應(yīng)用和改進(jìn)。Wang[4]應(yīng)用地理信息系統(tǒng)中的空間連接功能,得到最近站點(diǎn)集并預(yù)測下車站點(diǎn),實(shí)現(xiàn)出行鏈算法。Gordon等[12]在預(yù)測下車站點(diǎn)后預(yù)測下車時間,并通過測試來確保下車站點(diǎn)預(yù)測的正確性。Alsger等[13]基于出行鏈算法進(jìn)行了大量實(shí)驗(yàn),探索換乘時間閾值和步行距離閾值,根據(jù)匹配率與準(zhǔn)確度得出合適的閾值,提出“當(dāng)日對稱”思想的不完善之處并改進(jìn)。基于站點(diǎn)下車概率的推算與出行鏈算法相結(jié)合[14-16],可彌補(bǔ)出行鏈算法預(yù)測不完整的問題,提升下車站點(diǎn)預(yù)測率。豐海寬[6]考慮多種情況的出現(xiàn),例如當(dāng)日最后一次上車與當(dāng)日最早上車線路的關(guān)系、本次上車與下次上車站點(diǎn)的距離關(guān)系等,分別制定多個規(guī)則挖掘OD和換乘信息。李佳怡等[7]基于出行鏈定義出行節(jié),區(qū)分4種出行節(jié)鏈接方式,并結(jié)合站點(diǎn)下車吸引權(quán)來挖掘OD,提出站點(diǎn)位置評分方法來衡量精確程度。鄧一凌等[8]利用個體出行鏈推斷下車站點(diǎn),應(yīng)用個人出行規(guī)律和分線路的概率矩陣提升預(yù)測率。基于大數(shù)據(jù)框架應(yīng)用出行鏈算法將帶來效率的提升,鄔群勇等[5]將上車站點(diǎn)數(shù)據(jù)分塊,提出連續(xù)型和非連續(xù)型出行鏈算法,并將算法前置到Map階段來挖掘OD。孫慈嘉等[15]應(yīng)用MapReduce分線路統(tǒng)計(jì)站點(diǎn)熱度形成下車熱度矩陣后求解乘客轉(zhuǎn)移人數(shù)。OD挖掘所用的原始數(shù)據(jù)不一定是完整的,宋竹等[17]不關(guān)聯(lián)調(diào)度表或GPS信息,提出自適應(yīng)的調(diào)整算法標(biāo)注站點(diǎn)序號,利用貪心生長算法對全局公交車行駛方向進(jìn)行標(biāo)注,補(bǔ)全站點(diǎn)信息。此外還有OD矩陣可視化的最佳實(shí)踐[18]和對公交-地鐵多元數(shù)據(jù)的OD挖掘的具體應(yīng)用[3,19]。

以上研究中,上車站點(diǎn)使用一個固定的時間閾值進(jìn)行匹配,無法應(yīng)對多種公交車停車時間的變化；有些方法利用時間不等關(guān)系來進(jìn)行匹配,這樣會降低效率；有些還需要預(yù)先排序,也會降低效率。部分下車站點(diǎn)預(yù)測方法沒有并行的思想,只能處理一條或幾條線路；部分方法沒有結(jié)合大數(shù)據(jù)處理框架實(shí)現(xiàn)資源高效利用,且會受到換乘時間閾值的干擾。已有基于大數(shù)據(jù)框架的方法存在下車站點(diǎn)預(yù)測率較低的問題。在數(shù)據(jù)量較大的情況下,傳統(tǒng)數(shù)據(jù)庫也存在性能較弱的問題[20-23]。

上車站點(diǎn)匹配方法中,時間閾值可以根據(jù)集群能力任意擴(kuò)大,提升魯棒性；將時間不等關(guān)系轉(zhuǎn)化為相等關(guān)系進(jìn)行關(guān)聯(lián),無需預(yù)先排序,提升效率；結(jié)合站點(diǎn)上客數(shù)的概率思想,達(dá)到較高的匹配率。下車站點(diǎn)預(yù)測方法中,無需設(shè)定換乘時間閾值,排除人為確定因素的干擾,不考慮過多邊界和換乘次數(shù)。可并行處理多條線路,以出行鏈算法結(jié)合基于概率的預(yù)測方法達(dá)到較高的預(yù)測率。方法全部以Hive的查詢方式進(jìn)行,無需另行將數(shù)據(jù)讀出再進(jìn)行操作,方便實(shí)際的生產(chǎn)環(huán)境部署。依靠Hive相對于傳統(tǒng)數(shù)據(jù)庫查詢性能上的優(yōu)勢,再利用調(diào)優(yōu)技術(shù),在較短的離線耗時下,實(shí)現(xiàn)海量數(shù)據(jù)中基于表連接操作和概率思想的OD挖掘方法。

2 數(shù)據(jù)源

數(shù)據(jù)來自石家莊市運(yùn)營的公交車配套的車聯(lián)網(wǎng)設(shè)備,包含如圖1所示的3張表。IC刷卡記錄表、調(diào)度表時間跨度為2018年1月1日—2018年3月27日,共包含164條公交線路的調(diào)度數(shù)據(jù)；基礎(chǔ)信息表覆蓋了石家莊市所有公交站點(diǎn)。各表均包含多個字段,而在OD挖掘的過程中僅使用圖1所示的少量關(guān)鍵字段。

圖1 數(shù)據(jù)源及關(guān)聯(lián)關(guān)系Fig.1 Data sources and their relationship

由于車聯(lián)網(wǎng)設(shè)備在同一時刻僅能允許一名乘客刷卡,應(yīng)用IC刷卡記錄表時,經(jīng)常以卡號和刷卡時間來唯一定位一條刷卡記錄。該表并不記錄刷卡的站點(diǎn)信息,而是記錄線路號和車輛號。因此針對一條刷卡記錄,需要根據(jù)刷卡時間、線路號、車輛號進(jìn)行上車站點(diǎn)的匹配。成功完成上車站點(diǎn)匹配的IC卡記錄的刷卡時間被看作上車時間。

調(diào)度表中的字段相互組合后,有不同的業(yè)務(wù)含義:線路號、子線路號確定一條線路；線路號、子線路號、上下行確定公交運(yùn)行方向；線路號、子線路號、上下行、站點(diǎn)序號確定具體公交站點(diǎn)；進(jìn)出站類型辨別公交進(jìn)站還是出站。

基礎(chǔ)信息表中,站點(diǎn)經(jīng)度與站點(diǎn)緯度基于WGS84坐標(biāo)系,其他字段業(yè)務(wù)含義與調(diào)度表相同。

3 上車站點(diǎn)匹配

上車站點(diǎn)匹配主要為兩部分:基于時間閾值的上車站點(diǎn)匹配,基于站點(diǎn)上客數(shù)的上車站點(diǎn)匹配。前者關(guān)聯(lián)IC刷卡記錄表和調(diào)度表進(jìn)行匹配,失配的記錄將由后者再次進(jìn)行匹配。

3.1 基于時間閾值的上車站點(diǎn)匹配

得到IC刷卡記錄表和調(diào)度表后,常規(guī)的上車站點(diǎn)匹配方式是使用一個時間段直接進(jìn)行兩表關(guān)聯(lián)。這樣的連接有很大不確定性，可能會出現(xiàn)一條IC刷卡記錄連接多條調(diào)度記錄,或者因?yàn)槌鰰r間段一點(diǎn)而失配。為解決以上問題,提出基于時間閾值的連接方法。

設(shè)IC刷卡記錄表為表A,調(diào)度表為表B,表A刷卡時間字段為Ta,表B進(jìn)出站時間字段為Tb,Txy為刷卡時間和進(jìn)出站時間差的絕對值,如式(1)所示。

Txy=|Ax·Ta-By·Tb|≤F

(1)

式(1)中：Ax表示表A的第x條記錄；By表示表B的第y條記錄；點(diǎn)運(yùn)算Ax·Ta表示取表A第x條記錄對應(yīng)字段Ta的值；F為時間閾值。

以表A中第x條記錄為中心,對表B中所有滿足式(1)的記錄,計(jì)算Txy后執(zhí)行連接。獲得記錄集合:

S={(Ax,By,Txy)|Txy≤F}

(2)

取Txy最小值對應(yīng)的調(diào)度記錄b,如式(3)所示,b中的站點(diǎn)信息即為記錄Ax對應(yīng)的上車站點(diǎn)信息,b的進(jìn)出站時間,與Ax的刷卡時間最接近。

(3)

本方法中S的求解與MapReduce中的Map類似,是對表數(shù)據(jù)的抽取與連接；對S的處理與Reduce類似,是對連接后的數(shù)據(jù)進(jìn)行排序和篩選。

時間閾值F的提出,實(shí)質(zhì)是控制連接條件的寬松或嚴(yán)格,避免查詢中出現(xiàn)笛卡爾積,減小集群負(fù)擔(dān)。F根據(jù)實(shí)際的公交停車時間統(tǒng)計(jì)得到。首先統(tǒng)計(jì)所有站點(diǎn)歷史上下客時間數(shù)據(jù)的75%四分位數(shù)作為站點(diǎn)參考停車時間,在全部站點(diǎn)中,1路公交上行至省民航站的參考停車時間為中位數(shù)34 s。320路公交下行至實(shí)驗(yàn)小學(xué)站的參考停車時間為平均值40.75 s。參考停車時間介于2～280.6 s的站點(diǎn)占總站點(diǎn)數(shù)的99.7%。取F=280.6 s。每條刷卡記錄在此非常寬松的閾值F內(nèi),選擇最合理的、時間最近的調(diào)度記錄。

上述F取法僅為一建議,由式(1)～式(3)可得,F可以根據(jù)集群的運(yùn)算能力自由擴(kuò)大,F的擴(kuò)大會增加集群負(fù)擔(dān),提升匹配魯棒性,但不改變最終匹配結(jié)果。若F取無窮大,查詢對于時間字段做笛卡爾積。

基于時間閾值的上車站點(diǎn)匹配可以總結(jié)為以下流程:首先根據(jù)IC刷卡記錄中的刷卡時間和調(diào)度表中的出站時間應(yīng)用基于時間閾值的連接,匹配出上車站點(diǎn)。剩下的失配記錄在調(diào)度表中以進(jìn)站時間再次進(jìn)行匹配。仍無法匹配到上車站點(diǎn)的IC刷卡記錄,即認(rèn)為調(diào)度表缺少數(shù)據(jù),合并該記錄進(jìn)入失配記錄集，如圖2所示。

圖2 基于時間閾值的上車站點(diǎn)匹配流程Fig.2 The flow of the boarding station matching method based on the time threshold

3.2 基于站點(diǎn)上客數(shù)的上車站點(diǎn)匹配

若某時刻,IC刷卡記錄存在,而調(diào)度信息未被設(shè)備記錄,則上述方法失效。一般情況下,公交車的IC刷卡機(jī)比公交調(diào)度記錄設(shè)備要更加穩(wěn)定,這種情況大部分由調(diào)度記錄設(shè)備在短時間內(nèi)的故障導(dǎo)致。因此,應(yīng)用基于站點(diǎn)上客數(shù)的上車站點(diǎn)匹配方法求得上車站點(diǎn)。

基于站點(diǎn)上客數(shù)的上車站點(diǎn)匹配的詳細(xì)步驟如下。

輸入3.2節(jié)上車站點(diǎn)匹配結(jié)果、失配記錄集,IC刷卡記錄表,基礎(chǔ)信息表。

步驟1 根據(jù)已有的上車站點(diǎn)匹配記錄,求得所有站點(diǎn)的歷史上客數(shù)。

步驟2 求每條失配的IC刷卡記錄候選站點(diǎn)集M。

步驟3 根據(jù)站點(diǎn)歷史上客數(shù),求出每條記錄的M中每一站點(diǎn)上車概率Px。

步驟4 自每條記錄的M中依據(jù)每一Px選出一個上車站點(diǎn),與對應(yīng)的IC刷卡記錄匹配。

在每條失配的IC刷卡記錄中取出線路號和車輛號,在調(diào)度表中查詢對應(yīng)車輛號的車輛在對應(yīng)線路號的線路中同方向駛過的所有站點(diǎn)作為候選上車站點(diǎn)加入候選站點(diǎn)集M。乘客在M中每一站點(diǎn)的上車概率為

(4)

式(4)中：bx為M中第x個站點(diǎn)的歷史上客數(shù)；m為M中的元素個數(shù)。

每條記錄對應(yīng)的M中每一站點(diǎn)被選中的概率已知,按此概率選擇M中一個站點(diǎn)進(jìn)行連接,成功匹配上車站點(diǎn)。

4 下車站點(diǎn)預(yù)測

得出上車站點(diǎn)匹配表之后,需要根據(jù)已知的上車站點(diǎn)信息預(yù)測下車站點(diǎn),總體流程如圖3所示。首先構(gòu)造出行規(guī)律表和距離關(guān)系表,再以兩表為輸入,基于表連接執(zhí)行出行鏈算法,進(jìn)行下車站點(diǎn)預(yù)測。出行鏈算法預(yù)測失敗的記錄將由后續(xù)的基于下車概率的預(yù)測流程再次進(jìn)行預(yù)測。

圖3 下車站點(diǎn)預(yù)測Fig.3 Alighting station prediction

4.1 出行鏈算法

出行鏈算法實(shí)質(zhì)上是已被驗(yàn)證[3]的兩個假設(shè)。

出行(trip)指自乘客上車刷卡起至下車的過程。首先,公交車乘客上車刷卡一次,下車不刷卡,則訖點(diǎn)無從得知。則有假設(shè):乘客此次出行的訖點(diǎn)與下次出行的起點(diǎn)很接近,即站點(diǎn)最近(the closet stop)。由此,可通過下一次上車刷卡的信息獲知下次出行的起點(diǎn),根據(jù)距離預(yù)測出此次出行的訖點(diǎn)。其次,若記錄為當(dāng)日最后一次出行,并無對應(yīng)的“下一次出行”,則有假設(shè):乘客當(dāng)日最后一次出行完畢,將回到當(dāng)日首次出行較近的位置,即當(dāng)日對稱(daily symmetry)。由此,可將當(dāng)日首次出行當(dāng)作乘客當(dāng)日最后一次出行的“下一次出行”,根據(jù)站點(diǎn)最近假設(shè),預(yù)測出下車站點(diǎn)。

4.2 基于表連接的出行鏈算法

大多數(shù)出行鏈算法的實(shí)現(xiàn)是以命令式編程(imperative programming)即利用順序、分支、循環(huán)等語句組合,循環(huán)處理每一條出行記錄,考慮很多邊界條件進(jìn)行下車站點(diǎn)預(yù)測,執(zhí)行效率較低。為提高算法執(zhí)行速度,基于Hive在海量數(shù)據(jù)上的查詢性能優(yōu)勢,提出一種新的出行鏈算法實(shí)現(xiàn)方式:批量處理上車站點(diǎn)記錄,計(jì)算得到出行規(guī)律表和距離關(guān)系表,然后應(yīng)用以上兩表對所有的上車站點(diǎn)記錄批量進(jìn)行下車站點(diǎn)的預(yù)測。算法無需考慮過多的邊界條件。

4.2.1 構(gòu)造出行規(guī)律

根據(jù)出行鏈算法的已知條件——已知此次上車站點(diǎn)和下次上車站點(diǎn),將乘客單日的上車記錄按時間先后進(jìn)行兩兩連接。根據(jù)出行鏈算法的“當(dāng)日對稱”假設(shè),將乘客當(dāng)日最后一次上車記錄連接當(dāng)日首次上車記錄,連接后的結(jié)果即為此乘客的出行規(guī)律，如圖4所示。

圖4 構(gòu)造出行規(guī)律Fig.4 Construct the trip regulation

乘客201813***3216在2018年3月3日共乘坐5次公交車,首先在56路上行方向的聯(lián)邦空中花園站刷卡上車,在未知地點(diǎn)下車后,在73路上行方向的世紀(jì)花園東站再次刷卡上車。將這兩條記錄按時間先后兩兩相連作為(上車站點(diǎn),下次上車站點(diǎn))二元組,其他的記錄以此類推。當(dāng)天最后在56路下行翟營塔南路口站上車的記錄,與當(dāng)天第一條上車記錄連接。將原刷卡記錄的線路、上下行、站點(diǎn),替換為上車站點(diǎn)、下次上車站點(diǎn)。

4.2.2 計(jì)算距離關(guān)系表

運(yùn)用出行鏈算法的“站點(diǎn)最近”假設(shè),需要得到乘客的下次上車站點(diǎn)、候選下車站點(diǎn)以及兩者之間的距離。將出行規(guī)律表中所有乘客的(此次上車站點(diǎn),下次上車站點(diǎn))二元組提取出,則乘客此次上車站點(diǎn)同線路的下游站點(diǎn),為乘客的候選下車站點(diǎn)。將上述二元組加工成(候選下車站點(diǎn),下次上車站點(diǎn))二元組,并求出距離(候選下車站點(diǎn),下次上車站點(diǎn),兩者距離)三元組。距離關(guān)系表的實(shí)質(zhì)即為上述距離三元組。站點(diǎn)間距離公式使用相比Haversine公式更簡單的球面余弦公式[24],如式(5)所示。

(5)

式(5)中：n為緯度；e為經(jīng)度；x為某一候選下車站點(diǎn)；y為下次上車站點(diǎn)。

4.2.3 下車站點(diǎn)預(yù)測

以上兩表為出行鏈算法的執(zhí)行做準(zhǔn)備,而此步是出行鏈算法以表連接方式的實(shí)際執(zhí)行。首先根據(jù)構(gòu)造好的兩表進(jìn)行初步預(yù)測,再探測出代刷卡記錄進(jìn)行預(yù)測結(jié)果的復(fù)制,最后將兩步的結(jié)果進(jìn)行合并即完成了下車站點(diǎn)預(yù)測。前者使用到了距離關(guān)系表中的距離,后者復(fù)用了基于時間閾值的連接方法。

將批量讀入的出行規(guī)律記錄,按刷卡是否在同一線路進(jìn)行分組:兩次刷卡在同一線路的,下次上車站點(diǎn)即上次下車站點(diǎn)；不同線路的,根據(jù)“站點(diǎn)最近”假設(shè),查詢距離關(guān)系表得到結(jié)果。具體地:以上次上車刷卡記錄的公交線路的對應(yīng)公交行駛方向?yàn)橐阎獥l件,在距離關(guān)系表中查找多個在上次上車站點(diǎn)之后的站點(diǎn),作為候選下車站點(diǎn)。其中,與下次上車站點(diǎn)最近的候選下車站點(diǎn)即為上次出行對應(yīng)的下車站點(diǎn)。此預(yù)測結(jié)果作為初步預(yù)測結(jié)果表。

考慮某人早上在公司附近站點(diǎn)下車工作,晚上下班之后在同一站點(diǎn)上車的場景,這中間的時間間隔差可能超過8 h,因此,若設(shè)立1 h的換乘時間閾值來限制換乘,超過1 h的前后出行記錄不被連接,則OD記錄將無法被挖掘到。為避免此影響,不設(shè)立換乘閾值。

IC刷卡記錄中,有很多代刷卡記錄,在出行規(guī)律表中表現(xiàn)為下次上車站點(diǎn)與上次下車站點(diǎn)相等,且經(jīng)過上述流程無法被預(yù)測出下車站點(diǎn)。代刷卡乘客的下車站點(diǎn)看作與原持卡乘客相同的下車站點(diǎn)。得到初步預(yù)測結(jié)果后,在出行規(guī)律表中單獨(dú)篩選出代刷卡記錄形成表,并以此表和初步預(yù)測結(jié)果表分別作為A、B表,按照3.1節(jié)基于時間閾值的連接方法,以每條代刷卡記錄為中心,識別時間最近的非代刷卡記錄預(yù)測結(jié)果,即原持卡乘客的下車站點(diǎn)預(yù)測結(jié)果,并復(fù)制,即完成了代刷卡記錄的下車站點(diǎn)預(yù)測。

4.3 基于概率的下車站點(diǎn)預(yù)測

若乘客的出行鏈斷裂,即下次上車站點(diǎn)未知,則無法順利預(yù)測下車站點(diǎn)。此時需要進(jìn)行兩步基于概率的下車站點(diǎn)預(yù)測,即圖3中基于個體下車概率的下車站點(diǎn)預(yù)測和基于站點(diǎn)上客數(shù)的下車站點(diǎn)預(yù)測。

乘客乘車后,其候選下車站點(diǎn)為同線路乘車站點(diǎn)的所有下游站點(diǎn),求出這些站點(diǎn)作為候選下車站點(diǎn)集T。T中每一站點(diǎn)是乘客下車站點(diǎn)的概率為

(6)

式(6)中：ux為該乘客前后30 d內(nèi),在T中第x個站點(diǎn)上車的次數(shù)；t為T中的站點(diǎn)個數(shù)。

若:

?x∈T,Px=0

(7)

則:

(8)

式(8)中：hx為T中第x個站點(diǎn)的歷史上客數(shù)。

按照式(6)在T中選擇一個下車站點(diǎn),即基于個體下車概率的下車站點(diǎn)預(yù)測,若該乘客在30 d內(nèi)均無乘車記錄,則式(7)條件成立,則上述預(yù)測失敗。須基于式(8)在T中選擇一個下車站點(diǎn),即基于站點(diǎn)上客數(shù)的下車站點(diǎn)預(yù)測。

5 實(shí)驗(yàn)及結(jié)果分析

5.1 數(shù)據(jù)清洗

車聯(lián)網(wǎng)設(shè)備可能有數(shù)據(jù)缺失,需要將車聯(lián)網(wǎng)設(shè)備的數(shù)據(jù)進(jìn)行關(guān)聯(lián)并清洗,按如下步驟去除因?yàn)樵O(shè)備功能而導(dǎo)致問題的記錄。

步驟1 若某條調(diào)度記錄的站點(diǎn)信息在基礎(chǔ)信息表中不存在,則在調(diào)度表中刪除該記錄。

步驟2 若某條刷卡記錄的線路號和車輛號在調(diào)度表中不存在,則在IC刷卡記錄表中刪除該記錄。

步驟3 將調(diào)度表中全部線路號和車輛號按日分組形成分組記錄,若某條刷卡記錄的線路號和車輛號在同一天分組記錄中查不到,則在IC刷卡記錄表中刪除該記錄。

步驟1～步驟3分別考慮車輛調(diào)度設(shè)備的配置有誤或發(fā)生故障、刷卡機(jī)與車輛調(diào)度設(shè)備的某些設(shè)置不一致、在某一天調(diào)度設(shè)備故障的問題進(jìn)行針對性清洗。不排除例如網(wǎng)絡(luò)問題等其他極少數(shù)情況出現(xiàn)以上數(shù)據(jù)問題。

數(shù)據(jù)清洗結(jié)束后將輸出清洗后的IC刷卡記錄表和調(diào)度表。清洗前數(shù)據(jù)大小約15.6 G,清洗后由于IC刷卡記錄表、調(diào)度表以gzip格式壓縮并以序列文件存放,大小約3 G。

5.2 基于Hive的OD挖掘

5.2.1 代理鍵

代理鍵(surrogate key)在實(shí)際的HiveQL實(shí)現(xiàn)中經(jīng)常被使用。即在內(nèi)層或者先執(zhí)行的查詢根據(jù)條件分組新增一列標(biāo)識,一般是行號,用于外層或后執(zhí)行的查詢來識別順序、大小和其他記錄間關(guān)系,具體的使用方法如下。

(1)距離度量。在3.1節(jié)感知時間遠(yuǎn)近,4.2.1節(jié)構(gòu)造出行規(guī)律表時需要連接時間最近的下次上車記錄,4.2.2節(jié)衡量一個下次上車站點(diǎn)中多個候選下車站點(diǎn)的遠(yuǎn)近,均以代理鍵實(shí)現(xiàn)。先執(zhí)行的查詢做批量連接,計(jì)算所得時間差或兩站點(diǎn)幾何距離作為度量值。3.1節(jié)按卡號、刷卡時間分組,4.2.2節(jié)按下次上車站點(diǎn)分組,按度量值升序排序生成一列行號。外層的查詢僅讀行號即可知道兩條連接結(jié)果的時間、距離的遠(yuǎn)近,最小的行號所在行即最近時間或最近幾何距離的連接結(jié)果。

(2)臨時主鍵。3.2、4.3節(jié)在實(shí)現(xiàn)時,需要根據(jù)概率在一張表中選擇站點(diǎn)。然而,4個字段才能確定1個公交站點(diǎn)。可以先對記錄站點(diǎn)信息的子表去重,生成一列不重復(fù)的行號作為代理鍵作為臨時主鍵,并構(gòu)成(臨時主鍵,概率)二元組。根據(jù)概率選擇一代理鍵的值,之后通過代理鍵連接具體的站點(diǎn)信息。

5.2.2 輪盤賭策略

若一張表每行存儲如下二元組:(s,ws)，其中s為候選站點(diǎn),ws為該候選站點(diǎn)的權(quán)值。

需要按照權(quán)值求概率,再以概率選擇某一s。然而,在表查詢的過程中,表的每一行,可能分布在不同的從節(jié)點(diǎn)上。需要先應(yīng)用to_map()策略,將所有站點(diǎn)及其概率歸并至一個map結(jié)構(gòu)中,即{(s1,w1),(s2,w2)，…，(sn,wn)}。

設(shè)策略r()可處理上述map結(jié)構(gòu),分析站點(diǎn)、權(quán)值的類型,并根據(jù)具體的式(4)、式(6)、式(8)求sx概率Px,根據(jù)多個Px對將[0,1]分割成多個域,隨后生成該范圍一隨機(jī)數(shù),隨機(jī)數(shù)落在某一域,取出該域?qū)?yīng)的s。上述策略即為輪盤賭策略。

在Hive中,to_map() 可實(shí)現(xiàn)為用戶自定義聚合函數(shù)(user defined aggregate function, UDAF),將多行二元組聚合為一個map結(jié)構(gòu)。策略r()已被實(shí)現(xiàn)為用戶自定義函數(shù)(user defined function, UDF),并貢獻(xiàn)[25]至開源項(xiàng)目Apache Hivemall。

5.2.3 時間不等關(guān)系轉(zhuǎn)換為相等關(guān)系

Hive中on條件不能表達(dá)不等關(guān)系,所以不等關(guān)系需要用數(shù)學(xué)方法轉(zhuǎn)換為相等關(guān)系。3.1節(jié)執(zhí)行表連接時通過式(9)來等價替換式(1):

Ax·TaF=By·TbF

(9)

式(9)中：運(yùn)算符“”即取模運(yùn)算,其他同式(1)。

4.3節(jié)求個體下車概率需要查詢30 d之內(nèi)的上車次數(shù)、4.2.3節(jié)求最近的非代刷卡預(yù)測結(jié)果,同樣使用了此連接方式。式(9)的意義是:兩時間字段可以有差值,但不能相差超過一個F的量,否則式(9)的相等關(guān)系不成立。式(9)可直接代入HiveQL的on表達(dá)式作為連接條件,相比使用where直接表示式(1)的不等關(guān)系,時間消耗更少,中間數(shù)據(jù)量更小。

5.2.4 Hive調(diào)優(yōu)

已有的日志挖掘的實(shí)踐表明[26],針對具體的查詢?nèi)蝿?wù),對Hive做針對性地調(diào)優(yōu),有利于任務(wù)順利執(zhí)行并提高效率。

Hive提交任務(wù)后,轉(zhuǎn)化為Hadoop MapReduce來執(zhí)行,MapReduce中間結(jié)果將保留在硬盤上。若所有從節(jié)點(diǎn)磁盤空間都不夠,則任務(wù)將無法執(zhí)行。需要開啟中間結(jié)果和產(chǎn)出結(jié)果的壓縮,節(jié)省IO數(shù)據(jù)量。開啟壓縮后,表文件全部存儲為序列文件,防止單一壓縮文件過大且不能分割,下次只能分配一個Map讀取全表的問題。

并行調(diào)優(yōu)的開啟可保證Hive充分利用集群的所有資源,并行執(zhí)行多個無關(guān)聯(lián)的查詢,節(jié)省時間。

執(zhí)行5.2.2節(jié)的to_map()函數(shù)時,載入內(nèi)存的是一張表多個行的數(shù)據(jù)量,遠(yuǎn)超出默認(rèn)堆內(nèi)存容量。需要將所在查詢獨(dú)立成CREATE TABLE流程,并進(jìn)行Map端聚合關(guān)閉、Reduce數(shù)增加等針對性調(diào)優(yōu)。否則將帶來堆內(nèi)存溢出的風(fēng)險(xiǎn)。

關(guān)閉Map端聚合防止不合理的Map端聚合造成Job失敗。

5.3 OD挖掘及結(jié)果分析

基于Hive及站點(diǎn)上客數(shù)的下車站點(diǎn)預(yù)測過程如下。

算法1基于站點(diǎn)上客數(shù)的下車站點(diǎn)預(yù)測

輸入:部分下車站點(diǎn)預(yù)測表, 代理站點(diǎn)表

輸出:下車站點(diǎn)預(yù)測表

a) WITH 歷史上客數(shù)權(quán)值表 AS(

b) SELECT 站點(diǎn), 代理鍵

c) count(*) AS 權(quán)值

d) FROM 部分下車站點(diǎn)預(yù)測表 p

e) JOIN代理站點(diǎn)表 d

f) ON p.上車站點(diǎn) = d. 站點(diǎn)

g) GROUP BY 站點(diǎn), 代理鍵

h) ), 下游站點(diǎn)權(quán)值表 AS(

i) SELECT 刷卡信息, 代理鍵, 權(quán)值

j) FROM 部分下車站點(diǎn)預(yù)測表 d

k) JOIN 歷史上客數(shù)權(quán)值表 h

l) WHERE d.站點(diǎn)序號 < h.站點(diǎn)序號

m) AND d基于個體下車概率預(yù)測失敗

n) ), 預(yù)測簡表 AS(

o) SELECT 刷卡信息,

p) r(to_map(代理鍵, 權(quán)值)) 預(yù)測站點(diǎn)鍵

q) FROM 下游站點(diǎn)權(quán)值表

r) GROUP BY刷卡信息

s) )

t) CREATE TABLE下車站點(diǎn)預(yù)測表

u) AS SELECT 預(yù)測簡表

v) UNION部分下車站點(diǎn)預(yù)測表;

實(shí)驗(yàn)使用一臺服務(wù)器搭載兩個8核處理器,32 G內(nèi)存,1 TB存儲空間，在其上虛擬出5個虛擬機(jī),分別為1個主節(jié)點(diǎn)與4個從節(jié)點(diǎn)，配置均分且不超額分配，主節(jié)點(diǎn)僅負(fù)責(zé)調(diào)度,從節(jié)點(diǎn)承擔(dān)所有運(yùn)算任務(wù)。整套算法在此平臺處理全部數(shù)據(jù)的實(shí)際耗時為17 613.8 s,這一時間開銷能滿足生產(chǎn)環(huán)境中離線數(shù)據(jù)挖掘業(yè)務(wù)的需求。實(shí)驗(yàn)結(jié)果如表1所示。上車站點(diǎn)匹配率為清洗后IC刷卡數(shù)據(jù)的100%,下車站點(diǎn)預(yù)測率達(dá)到清洗后IC刷卡數(shù)據(jù)的99.6%。剩余的0.6%是由于上車站點(diǎn)匹配時,將某刷卡記錄匹配到了公交的末站,這類記錄無法進(jìn)行下車站點(diǎn)預(yù)測。

表1 數(shù)據(jù)清洗與OD挖掘結(jié)果Table 1 The result of data cleaning and OD mining

將石家莊市2018年2月1日15路的OD結(jié)果處理成OD矩陣,繪制成熱力圖，如圖5所示，其中OD矩陣的行坐標(biāo)為上車站點(diǎn),列坐標(biāo)為下車站點(diǎn)。熱力圖顏色越深說明在行坐標(biāo)所指站點(diǎn)上車,在列坐標(biāo)所指站點(diǎn)下車的客流越多,其上數(shù)值為具體的人數(shù)。由圖5可知,站點(diǎn)當(dāng)日上客量:八一站10人,最少；南郭站148人,最多。站點(diǎn)當(dāng)日下客量:八一站28人,最少；南郭站122人,最多。當(dāng)天南郭站上車至南郭小區(qū)下車的乘客最多,38人。西王小區(qū)站上車至南郭站下車,長興街南口站上車至南郭站下車的乘客較多。由此可推斷,南郭站是非常重要的站點(diǎn)。若南郭站因施工或其他原因無法使用,則其周邊站點(diǎn)的客流將會被大幅影響,對于大多數(shù)乘客,必定會出行不便。

圖5 OD矩陣Fig.5 OD matrix

5.4 與其他方法的比較

在已挖掘的OD數(shù)據(jù)中,選取2018年1月1日—2018年3月27日536路單條線路所有站點(diǎn)的OD記錄,按站點(diǎn)分別累加上車人數(shù)、下車人數(shù),分別作為x、y,對得到的所有站點(diǎn)x、y做線性回歸,即進(jìn)行出行與吸引校驗(yàn)[16]。如圖6所示,每一公交站的上車人數(shù),下車人數(shù)為圖中一點(diǎn)。回歸方程的斜率接近1,證明出行量與吸引量基本相等,挖掘出的OD記錄有較高的質(zhì)量,可用于實(shí)際業(yè)務(wù)中。

圖6 536路累計(jì)OD量線性回歸Fig.6 Linear regression of OD aggregation of 536 bus lines

將本文模型與廣東省智能交通系統(tǒng)重點(diǎn)實(shí)驗(yàn)室的兩次研究成果[16,19]進(jìn)行比較,結(jié)果如表2所示,文獻(xiàn)[16]在單條線路的小數(shù)據(jù)集上有較好的性能,但文獻(xiàn)[19]在大數(shù)據(jù)集上的O匹配率,D預(yù)測率均遜色于文獻(xiàn)[16]在小數(shù)據(jù)集上的表現(xiàn)。本文方法：O匹配率、D預(yù)測率在大數(shù)據(jù)集上均優(yōu)于文獻(xiàn)[19]。

表2 實(shí)驗(yàn)結(jié)果對比Table 2 Comparison of experimental results

6 結(jié)論

在海量數(shù)據(jù)中離線挖掘乘客OD是目前城市公共交通行業(yè)最迫切的需求之一。可視化的OD矩陣可向上層決策提供支持。能否全面、準(zhǔn)確、快速地挖掘OD,對于后續(xù)的站點(diǎn)變動影響分析、靜態(tài)交通規(guī)劃等工作有重要的現(xiàn)實(shí)意義。

基于Hive實(shí)現(xiàn)了客流OD的挖掘,其具有如下優(yōu)勢。

(1)算法基于Hive實(shí)現(xiàn),實(shí)際應(yīng)用場景下相比于傳統(tǒng)數(shù)據(jù)庫有更強(qiáng)的性能優(yōu)勢。

(2)上車站點(diǎn)匹配的時間閾值可靈活調(diào)整,基于相等關(guān)系的表關(guān)聯(lián)手法效率高,下車站點(diǎn)預(yù)測無需考慮過多的邊界條件,無需設(shè)立換乘時間閾值,無需逐一掃描單條記錄進(jìn)行循環(huán)而是并行處理多條線路挖掘OD。

(3)純HiveQL代碼部署簡單,對生產(chǎn)環(huán)境友好。

(4)應(yīng)用Hive調(diào)優(yōu)提高了資源利用率,縮短了任務(wù)執(zhí)行時間,提高了離線任務(wù)的效率和穩(wěn)定性。

(5)算法上車站點(diǎn)匹配率達(dá)到100%,下車站點(diǎn)預(yù)測率達(dá)到99.6%。實(shí)驗(yàn)結(jié)果表明,出行量與吸引量基本相等,結(jié)果合理。在換乘分析等OD應(yīng)用方面,有待進(jìn)一步研究。