陳麗璐,聶文惠

(江蘇大學(xué) 計算機科學(xué)與通信工程學(xué)院,鎮(zhèn)江 212013)

隨著人們生活水平不斷提高,城市車輛數(shù)量急劇上升,城市交通問題隨之日益突出,人民日常出行駕駛車輛常常會遇到交通堵塞情況,尤其是在北京、上海、廣州等大城市,居民如果想快速、方便地出行,特別是在暴雨、寒冬等惡劣天氣條件下,出租車無疑是眾多公共交通工具中的最佳選擇之一.出租車數(shù)量的不斷增長也使出租車行業(yè)面臨了越來越多的問題,如空駛率高、分布不均衡、供不應(yīng)求等等,這些問題也一定程度上導(dǎo)致了居民打車難的問題.

近年來,隨著全球定位系統(tǒng)GPS (Global Position System)技術(shù)的飛速發(fā)展和智能定位終端的廣泛應(yīng)用,基于位置的信息服務(wù)得到了飛速發(fā)展.城市出租車上基本都安裝了GPS 傳感器,能夠記錄當(dāng)前車輛的位置、采集時間等信息.很多國內(nèi)外學(xué)者基于出租車軌跡信息展開了各項研究,例如：路徑規(guī)劃[1,2]、基于位置的社交網(wǎng)絡(luò)[3]、智能交通系統(tǒng)[4]和城市計算[5-7]等.文獻[8]通過對首爾的出租車GPS 數(shù)據(jù)進行多維分析,指出可以運用數(shù)據(jù)分析手段指導(dǎo)出出租車運營公司進行合理調(diào)度.文獻[9]應(yīng)用K-means 聚類模型分析出租車載客的熱點區(qū)域,應(yīng)用遺傳算法進行出租車的應(yīng)急調(diào)度；文獻[10]將K-means 算法和具有噪聲的基于密度的聚類算法(Density-Based Spatial Clustering of Applications with Noise,DBSCAN)在軌跡數(shù)據(jù)研究方面進行了對比,Kmeans 算法在處理大數(shù)據(jù)時效率較高,但對于噪聲點和孤立點數(shù)據(jù)較為敏感；DBSCAN 算法不需要進行預(yù)處理亦可在帶有噪聲點的數(shù)據(jù)中發(fā)現(xiàn)任意形狀的聚類,但對輸入?yún)?shù)的敏感性較高.

本文提出了一種服務(wù)于出租車司機和乘客的載客熱點與打車熱點的研究方法.主要研究步驟為：首先對軌跡數(shù)據(jù)進行預(yù)處理,形成基礎(chǔ)數(shù)據(jù)集；接著對基礎(chǔ)數(shù)據(jù)集采用速度與時間結(jié)合算法進行出租車停留點和出租車載客點的提?。蝗缓髮Τ鲎廛囃Ａ酎c進行DBSCAN聚類得到核心停留點；最后對核心停留點和出租車載客點分別進行K-means 聚類分析得到推薦熱點.

1 軌跡點預(yù)處理

由于軌跡數(shù)據(jù)量巨大,并且對于城市交通來說,頻繁擁堵狀態(tài)下緩慢行駛車輛的GPS(全球定位系統(tǒng))定位信息易產(chǎn)生冗余定位點與噪聲,例如建筑物會對信號產(chǎn)生阻隔,就會存在一些信號缺失的現(xiàn)象,因此需對軌跡數(shù)據(jù)進行預(yù)處理.

1.1 相關(guān)定義

軌跡G 通常由一系列的包含時間和空間信息的點組成,表示為 G=P1,P2,···,Pn,其中,n為一條軌跡的點的總數(shù)；Pi(1≤i≤n)為軌跡點,且Pi=(X,Y,T),X和Y分別為第i個軌跡點的經(jīng)度和緯度坐標(biāo),T為時間戳,有Pi.T＜Pi+1.T.

定義1.出租車停留點Sp (Stay Point of Taxi)

根據(jù)實際生活常識,通常出租車在載客狀態(tài)時,其駕駛的平均速度會超過一定的閾值,而在沒有載客時,為了尋找乘客,其行駛速度通常低于某個值.因此設(shè)定出租車在載客時的平均駕駛速度高于閾值Vs,未載客時速度低于該閾值.

在出租車GPS 軌跡點中存在這樣一些點,此類點的駕駛速度V小于給定的速度閾值Vs,并且以小于該速度閾值的速度連續(xù)行駛一段時間T,而T大于給定的時間閾值Ts,同時此類點所在的移動范圍小于給定的距離閾值Ds,那么我們就認為此類點是出租車停留點.

定義2.核心停留點Sc (central stay point)

給定距離閾值ε、最小密度數(shù)m,給定一條軌跡中的軌跡點P,記N為P 的ε距離鄰域內(nèi)同屬于該軌跡點的點的集合,如∣N∣≥m,則稱P 為核心停留點.

定義3.出租車載客點St (Pick-up Point of Taxi)

出租車搭載乘客的地點,如圖1所示,當(dāng)行程1 中的平均速度小于速度閾值,行程2 中的速度超過一定速度閾值,且行程2 的行駛距離超過一定的距離閾值,則定義停留點S1 是一個歷史載客點.當(dāng)行程3 的速度大于一定的速度閾值時,行程3 作為出租車載客行駛的一部分行程.

圖1 出租車載客點示意圖

出租車停留點Sp是由出租車停留或徘徊所產(chǎn)生的點的集合,核心停留點Sc是對出租車停留點進行DBSCAN 算法聚類得到的點的集合,出租車載客點St是根據(jù)出租車的行駛速度和時間進行判斷得出的點的集合.三者的關(guān)系如圖2所示.

圖2 定義點關(guān)系圖

1.2 軌跡點處理

根據(jù)以上的定義,在提取出租車停留點和出租車載客點之前,首先需要對軌跡數(shù)據(jù)中的漂移數(shù)據(jù)進行處理.本文采用Douglas-Peucker(曲線數(shù)據(jù)壓縮)算法進行軌跡數(shù)據(jù)的漂移處理.算法步驟如下：首先,提取三個位置相鄰的數(shù)據(jù)點分別為點A,點B 和點C,如圖3,根據(jù)三角形面積公式,三角形ABC 的面積為：

其次,判斷點B 到前后兩點A 與C 的距離是否滿足公式：

其中,derror是指允許偏移的最大值,一般由地圖精度、GPS 接收機精度和道路寬度之和計算得出.比較h與derror之間的大小,如果小于derror,則直線AC 段作為曲線AC 的近似,該段曲線處理完畢；如果h大于derror,則點B 不可忽略,將曲線AC 近似為直線AB 和BC 兩段.

圖3 Douglas-Peucker (DP)線路優(yōu)化示意圖

接著對軌跡數(shù)據(jù)進行噪聲處理,根據(jù)定義1 中出租車停留點的含義,在出租車GPS 軌跡點中,停留點并不僅僅代表速度為零的軌跡點,“?！敝皇荊PS 軌跡點的一種狀態(tài),因此本文通過計算和分析出租車GPS數(shù)據(jù),提取出租車停留點,進而獲取相關(guān)熱點.

YE[11]、KARLI[12]等人將移動對象活動分為四種模式：內(nèi)空間模式(inside)、伴隨模式(along)、環(huán)繞模式(around)、駐留模式(stop).如果出租車GPS 軌跡數(shù)據(jù)符合環(huán)繞模式或駐留模式中其中一種模式,我們就將該GPS 軌跡點視為出租車停留點.如圖4所示,圖中點均為出租車GPS 軌跡點,圓圈內(nèi)的點表示出租車停留點,Sp1 中沒有路線規(guī)律的GPS 軌跡點是由駐留模式產(chǎn)生得到出租車停留點,而Sp2 中有一定路線規(guī)律的GPS 軌跡點是由駐留模式產(chǎn)生得到出租車停留點.

圖4 停留點提取示意圖

駐留模式下的停留點均符合出租車停留點的定義,但也可能存在一種特殊情況需要分析處理,即駐留模式下由交通狀況產(chǎn)生的停留點.比如等待交通信號燈或者道路堵塞等狀況,將這種情況下產(chǎn)生的停留點視為噪聲.進一步分析研究得知,等待交通信號燈和交通堵塞大部分情況是發(fā)生在交通路口,為了處理這些噪聲,參考譚川豫等人[13]對移動對象軌跡的研究,定義如果在某處有50%以上的出租車軌跡發(fā)生了方向轉(zhuǎn)變,并且轉(zhuǎn)變角度超過30%,將該處視為交通路口,并對該處周圍50m 范圍內(nèi)的所有出租車停留點視為噪聲,予以刪除.

2 熱點處理

本文從出租車司機端和乘客端兩方面考慮,對于出租車司機端進行載客熱點的推薦,乘客端進行打車熱點的推薦,盡可能降低出租車司機的空載率、減少乘客的等待時間.為了達到更好地推薦效果,對軌跡點根據(jù)時間這一因素劃分并進行聚類處理.對出租車停留點采用基于密度的聚類算法得到核心停留點,對核心停留點和出租車載客點采用基于劃分的聚類算法進行聚類.

2.1 劃分思想

2.1.1 用戶劃分

受眾目標(biāo)的考慮不僅包括出租車司機還包括乘客,對于出租車司機我們進行載客熱點的推薦,而對于乘客我們進行打車熱點的推薦.

出租車司機的載客熱點由兩部分組成.一部分是由軌跡數(shù)據(jù)處理得到的出租車停留點進行DBSCAN初步聚類得到的核心停留點；另一部分是提取得到的出租車載客點.

對于乘客更多的是需要考慮出租車可能停留的地點,所以對于打車熱點的聚類研究是基于出租車停留點的相關(guān)數(shù)據(jù)基礎(chǔ)上的,即對核心停留點直接進行聚類研究.

2.1.2 時間劃分

眾所周知,人類的活動受到空間、時間及其他限制條件的影響,為了研究這些限制條件的影響,瑞典地理學(xué)家赫格斯特蘭德提出了時間地理學(xué)的概念[14],其認為人類在時空中的活動受到三類限制：(1)能力限制,指生理或物理因素對人類果凍產(chǎn)生的限制,如我們必須分配一定的時間來滿足吃飯、睡覺等生理需求；(2)權(quán)利限制,指因活動場所常由不同的人或單位控制而對他人產(chǎn)生的限制,如,某商場的營業(yè)時間是上午九點至晚上十點,一般顧客只有在此時間段內(nèi)可以進入這個商場的空間；(3)結(jié)對限制,指我們在特定的地點從事某項活動(如到上班地點工作、到商場購物),或必須和其他人共同從事某項活動(例如開會),因此要在時間和空間上彼此相互協(xié)調(diào)配合.人們應(yīng)在這些限制條件下合理的安排時間和空間,以滿足我們的生理、經(jīng)濟、社交等各方面的需求.

出租車司機的駕車行為和乘客打車行為均屬于人類活動,同樣受上述三類限制,如果協(xié)調(diào)好司機與乘客之間的行為,司機在相應(yīng)的時段到乘客相對集中的地點拉客人,乘客在相應(yīng)時段到司機經(jīng)常路過的地點打車,這樣不僅司機能快速地找到乘客降低空載幾率,也方便了乘客打車.圖5選取了8 點至10 點和14 點至18 點兩個時間段部分停留點可視化效果圖,該圖驗證了不同時段停留點的分布情況不同,說明人群的集中地在各個時段內(nèi)的分布情況不同.車輛的載客情況會隨時間的變化而變化,劃分時間能更好地進行熱點推薦有一定的數(shù)據(jù)支持.

圖5 8：00-10：00(圓形點)和14：00-18：00(三角點)兩個時段部分停留點的情況

2.2 算法思想

本文處理軌跡數(shù)據(jù)的算法思路如下：(1)對初始軌跡數(shù)據(jù)進行預(yù)處理,預(yù)處理包括軌跡數(shù)據(jù)的漂移和噪聲處理；(2)對基礎(chǔ)數(shù)據(jù)集(即經(jīng)過預(yù)處理后的數(shù)據(jù)集合)結(jié)合時間和速度進行出租車停留點和出租車載客點的提?。?3)對提取的出租車停留點進行DBSCAN算法進行聚類得到核心停留點；(4)對核心停留點和出租車載客點進行K-means 算法的聚類得到載客熱點和打車熱點.具體過程如圖6所示.

圖6 算法流程圖

DBSCAN 算法是通過不斷地搜索臨近點,使該點周圍的密度逐漸增加,以尋找到一個區(qū)域內(nèi)所查找點密度大的地方.出租車停留點是軌跡數(shù)據(jù)中符合環(huán)繞模式或駐留模式的軌跡點,環(huán)繞模式或駐留模式的軌跡點大多聚集在一個區(qū)域內(nèi).這些軌跡點所圍繞的區(qū)域即是需要找的出租車停留區(qū)域,故對這些停留點進行基于密度的聚類可以得到代表該區(qū)域的停留點,即本文定義的核心停留點.DBSCAN 算法的相關(guān)定義如下：

(1)密度直達：給定距離閾值ε、最小密度數(shù)m,則滿足下述兩個條件時,點P是從點Q出發(fā)直接密度可達：P屬于Q的ε距離范圍內(nèi),記為P∈N；P為核心?？奎c,即∣N∣≥m.

(2)密度可達：給定自軌跡序列P1,P2,···,Pn,P1=Q,Pn=P,對于任意i(1≤i≤n-1),Pi+1 是從Pi關(guān)于ε和m直接密度可達的,則稱點P是從Q關(guān)于ε和m密度可達的,反之不一定成立.

(3)密度相連：若一條軌跡中存在一個點O,使得點P和Q是從關(guān)于ε和m密度可達的,則稱P和Q關(guān)于ε和m密度相連.

采用DBSCAN 算法處理出租車停留點能快速且有效地處理噪聲點和發(fā)現(xiàn)任意形狀的空間聚類,與Kmeans 算法相比不需要輸入要劃分的聚類個數(shù).

對于核心停留點和出租車載客點的聚類采用Kmeans 算法進行聚類,K-means 算法的主要思想是通過迭代的過程把數(shù)據(jù)集劃分為不同的類,從而使生成的每個類的內(nèi)部數(shù)據(jù)緊湊,類與類之間獨立.K-means 算法處理大數(shù)據(jù)集具有良好的可伸縮性和高效性,其缺點是需設(shè)定聚類簇的數(shù)量,利用這一點可以實現(xiàn)對聚類中心的質(zhì)量的控制.

3 實驗結(jié)果與分析

本文的實驗數(shù)據(jù)選取了北京市7 個月的軌跡數(shù)據(jù)作為一個實驗樣本進行實驗,對上述方法進行驗證與研究.

3.1 實驗環(huán)境

實驗計算機配置：CPUCore(TM)3.40 GHz,內(nèi)存16 GB,顯存8 GB；操作系統(tǒng)：Windows 7；使用軟件：MATLAB,Pycharm,MySQL,SQLyog.

3.2 評價標(biāo)準(zhǔn)

為了評價本文獲取的熱點的準(zhǔn)確率,采用精度(Precision,即查準(zhǔn)率)和召回率(Recall,即查全率)對相關(guān)熱點進行評定[15].查準(zhǔn)率是指正確識別的相似重復(fù)記錄與實際的相似重復(fù)記錄的比值,查準(zhǔn)率越高,表明提取出來的相關(guān)熱點精度越高.召回率是各熱點被正確識別的百分率,召回率越高,表明該方法識別各熱點的能力越強.查準(zhǔn)率和召回率定義如下：

其中,tp表示正確識別的熱點數(shù),fp表示錯誤識別的熱點數(shù),fn表示未識別的熱點數(shù).

文獻[16]中認為在興趣點半徑50 米范圍內(nèi)的出租車載客點都是正確的,借鑒文獻中判斷出租車載客點的正確性的方法進行測試.本文把各時段的出租車載客熱點作為測試點,地圖上的興趣點(火車站、超市、公園、寫字樓等)作為已知點,用測試點和已知點進行比較,從而判斷測試點的正確性.

3.3 實驗分析

本文實驗數(shù)據(jù)為微軟公開的軌跡數(shù)據(jù),其中包含緯度、經(jīng)度、海拔、時間等信息.將數(shù)據(jù)集按時間進行時段劃分,總結(jié)處理后數(shù)據(jù)的時間分布規(guī)律,將數(shù)據(jù)點按時間點分布所占比例進行分類,如圖7所示,各時間段出租車的載客情況各有不同,低谷期在凌晨到次日早高峰之間.

圖7 不同時段GPS 數(shù)據(jù)點的分布比例

實驗數(shù)據(jù)是每5 秒采集一次,對停留點的定義是符合環(huán)繞模式和駐留模式的點,這兩種模式會產(chǎn)生多個位置相近但不重復(fù)的點,對于這些點進行DBSCAN聚類可以提高停留點的質(zhì)量.但對于在路口附近50 米范圍的點予以刪除,如圖8所示,小圓是經(jīng)過DBSCAN聚類形成的簇,而三角形的點和大圓中的點可能是擁堵或交通信號燈產(chǎn)生的點,為避免影響停留點質(zhì)量,做刪除處理.停留點的優(yōu)化一定程度上也提高了聚類的時間效率.表1為部分停留點聚類結(jié)果.

圖8 停留點聚類處理示意圖

表1 停留點聚類效果對比

將本文獲取出租車載客熱點的方法TDKC 分別與文獻[17]中的層次聚類(MSRA)獲取出租車載客點方法、文獻[18]中的時空聚類(STA)獲取出租車載客熱點的方法進行比較,結(jié)果如圖9和與圖10所示,可以看出本文的方法獲取的出租車熱點在緩沖半徑為20 米時的精度和召回率分別達到了85.9%和82%,而當(dāng)緩沖半徑為50 米時,本文方法的精度和召回率達到了95.7%和95.5%,較優(yōu)于上述兩種聚類方法,95%以上的精度和召回率說明了推薦的熱點具有較高的推薦價值,提高了推薦熱點的準(zhǔn)確性.鑒于乘客的打車熱點包含于出租車載客熱點之內(nèi),因此打車熱點的準(zhǔn)確性也有所提高.

圖10 熱點召回率對緩存半徑變化圖

4 結(jié)論

為降低出租車司機的空載率和減少乘客的等待時間,本文改進了面向出租車司機的載客熱點和面向乘客的打車熱點的模型和算法.在對GPS 軌跡點的處理上,對提取出來的出租車停留點采用DBSCAN 算法進行聚類,提高停留點的準(zhǔn)確度；由于時間因素對出租車司機和乘客的影響較大,本文在對停留點和載客點聚類分析時,運用劃分思想,將數(shù)據(jù)集按時間進行劃分,在各個分段中進行數(shù)據(jù)的聚類分析.最后通過實驗驗證,結(jié)合DBSCAN 算法對停留點進行核心停留點的提取,提高了停留點的準(zhǔn)確性,同時也提高了聚類分析的時間效率.考慮時間因素對停留點和載客點進行分析在查準(zhǔn)率和召回率方面都有所提高.

受實驗環(huán)境的制約,本文僅對部分數(shù)據(jù)進行了處理和分析,后期將進一步對其他數(shù)據(jù)處理分析,對各個候選熱點根據(jù)推薦公式進行熱點的推薦.