基于PageRank算法的出租車需求預(yù)測

周豐

(上海大學(xué) 通信與信息工程學(xué)院， 上海 200072)

0 引言

智慧城市作為實現(xiàn)城市資源的智能分配和科學(xué)管理的重要手段[1-2]，有利于解決城市交通問題。目前城市的交通問題之一是出租車司機(jī)與乘客面雙向面臨著接客難與打車難的問題，出租車的合理分配問題[3]亟待解決。

隨著嵌入式和傳感器設(shè)備的發(fā)展，城市中大量移動物體的軌跡已變得越來越容易獲得[4]。例如，中國的許多出租車公司為了管理目的需要會在每輛出租車上安裝GPS設(shè)備，這為記錄出租車當(dāng)前以及歷史軌跡提供了基礎(chǔ)設(shè)施。通過出租車軌跡數(shù)據(jù)可以知道，站點的流量狀態(tài)不是獨立演變的，會受到臨近站點流量狀態(tài)的影響，因此可以把交通系統(tǒng)看成復(fù)雜網(wǎng)絡(luò)[5]，來研究城市出租車系統(tǒng)中的人群流動模式[6-8]，從而發(fā)現(xiàn)出租車分配的更好方法。此前研究發(fā)現(xiàn)[9]，利用Google最初開發(fā)的PageRank算法可以從動態(tài)的角度對城市交通演化進(jìn)行建模，更深入的了解城市動態(tài)。

本文研究貢獻(xiàn)在于：

1.利用PageRank建模[10]時，把城市熱點區(qū)域作為節(jié)點，以此解決數(shù)據(jù)分區(qū)和網(wǎng)格分辨率對模型帶來的影響。

2.不僅利用ARIMA模型[11-12]預(yù)測熱點區(qū)域的乘客數(shù)量，而且還發(fā)現(xiàn)動態(tài)特征PageRank值與預(yù)測乘客量間的確定性關(guān)系。

3.根據(jù)北京市10000輛出租車軌跡數(shù)據(jù)實驗驗證結(jié)果的準(zhǔn)確性。

2 數(shù)據(jù)處理

2.1 數(shù)據(jù)

我們用于實驗的數(shù)據(jù)來自北京地區(qū)的10000出租車部分軌跡數(shù)據(jù)，如圖1所示。

數(shù)據(jù)主要來自2014年4月1日至15日，包含4個假期，2個周末和10個工作日。 在實驗期間， 15天的數(shù)據(jù)被分為3組，分別對應(yīng)假期，工作日和周末；同時，一天的數(shù)據(jù)分為3個不同的時間段：上午高峰時間(6：00-10：00)，工作時間(10：00-16：00)和晚上高峰時間(16:00-20：00)。 由于20:00 PM - 6:00AM時間段內(nèi)流量很少發(fā)生，因此在考慮PageRank值和ARIMA預(yù)測值之間的關(guān)系時，不考慮這段時間。

圖1 北京城區(qū)部分出租車軌跡圖

計算熱點區(qū)域交通狀態(tài)時，我們以15分鐘作為時間間隔，每天有96個時間間隔，熱點提取時使用前10天的數(shù)據(jù)，后五天的數(shù)據(jù)被用來對模型進(jìn)行預(yù)測準(zhǔn)確率的驗證。

每輛出租車都配有GPS設(shè)備，以約每60秒一次的采樣頻率記錄出租車的軌跡，其中包括以下項目：

TAXI_ID：出租車的唯一ID;

GPS_TIME：采樣時間戳;

GPS_LONGITUDE：出租車當(dāng)前經(jīng)度；

GPS_LATITUDE：出租車當(dāng)前緯度;

GPS_STATUS：GPS設(shè)備的當(dāng)前狀態(tài)，有效或無效，表示來自GPS設(shè)備的消息是否成功。

METER STATE：表示計程表是否正在運行，即出租車是否有乘客：如果出租車被占用，則為1；如果是空閑，則為0。

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

由于GPS信號和設(shè)備故障的多路徑效應(yīng)，GPS位置有時可能不正確。此外，由于駕駛員做出的無效操作，METER STATE也可能不正確。例如，當(dāng)一個出租車司機(jī)下班時，盡管出租車中沒有乘客，但他們可能會打開計程表。為了闡明真實的空置軌跡和占用軌跡(分別有無軌跡)，數(shù)據(jù)預(yù)處理如下：

我們對持續(xù)時間和平均速度超出正常范圍的占用軌跡進(jìn)行過濾。分析了占用軌跡的持續(xù)時間和平均速度的分布。平均速度范圍設(shè)定為5米/秒至40米/秒。 所有不符合這些條件的占用軌跡都將被視為無效。此外，也刪除了包含具有明顯的經(jīng)度或緯度的不正常的記錄。

3 PageRank流量建模

3.1 熱點提取

熱點是頻繁出現(xiàn)上下車事件的區(qū)域，如圖2所示。

圖2 規(guī)定閾值后熱點圖

本研究將熱點作為節(jié)點進(jìn)行復(fù)雜網(wǎng)絡(luò)建模，所以首先進(jìn)行熱點提取，出租車記錄中METER STATE的轉(zhuǎn)換被視為上/下車事件，即從0到1的METER STATE變化表示上車事件(PUQ)，并且METER STATE in從1到0的轉(zhuǎn)換指示一組下車事件(SDQ)，連續(xù)的0或1表示為空載或已有乘客。熱點提取步驟如下：

(1) 從10 000輛出租車隨機(jī)選取100倆抽樣分析。

(2) 從軌跡數(shù)據(jù)提取轉(zhuǎn)換事件，記錄事件數(shù)量。

(3) 設(shè)置熱點閾值，根據(jù)閾值提取出明顯的熱點。如圖3所示。

(a)

(b)

3.2 PageRank流量建模

顯然，每個地區(qū)上/下車的狀況都受到鄰近地區(qū)的影響，出租車經(jīng)常在這些熱點之間來回行駛，而這些行駛軌跡可以看成是連接這些熱點的鏈接。在這里，我們采用PageRank方法來研究整個網(wǎng)絡(luò)的動態(tài)行為。PageRank算法最初被Google用來根據(jù)網(wǎng)頁中的引用排列網(wǎng)頁的流行度。在PageRank算法中，網(wǎng)頁的受歡迎程度根據(jù)引用此頁面的網(wǎng)頁的得分進(jìn)行評分，其中由網(wǎng)頁貢獻(xiàn)的分?jǐn)?shù)被平均分配給此頁面引用的頁面。所有頁面的最終獲得的分?jǐn)?shù)用于排列它們的流行度。由于交通系統(tǒng)可以建模為復(fù)雜的網(wǎng)絡(luò)，因此我們利用PageRank對熱點的“流行度”進(jìn)行排序，并研究PageRank值的規(guī)律。直觀地說，“受歡迎的地區(qū)”或中心有很高的可能出租車需求量大。在以熱點為節(jié)點的城市交通復(fù)雜網(wǎng)絡(luò)模型中，一個熱點向鄰近熱點提供交通流量，熱點間交通流量的傳遞對熱點影響的傳播與PageRank機(jī)制相似。因此，PageRank算法用于量化出租車需求是可行的。

我們以北京為例，表明一個城市可以劃分為熱點區(qū)域。如果車輛從一個熱點前往相鄰區(qū)域，則意味著應(yīng)該有連接這兩個熱點的道路，并且通過兩個熱點的交通流作為連接它們的定向鏈路。圖3(a)和(b)給出了網(wǎng)絡(luò)模型的一個概念性例子。以熱點作為節(jié)點和交通流作為連接區(qū)域的鏈接，城市的交通系統(tǒng)可以建模為時間復(fù)雜的網(wǎng)絡(luò)，其中動態(tài)鏈路通過時間相鄰熱點之間的交通量加權(quán)。

時間t處的熱點i的PageRank指數(shù)被定義為式(1)。

(1)

其中N(t)是所有熱點的數(shù)量，NR(i)熱點i周圍的鄰近熱點，有流量將它們連接到熱點i，Pj(t)是熱點j的PageRank指數(shù)，Oji(t)表示t時刻從熱點j到熱點i的交通流量，∑Oj(t)在時間t時所有流出熱點j的流量，d=0.85是固定系數(shù)，以避免陷入沒有流出的區(qū)域。 當(dāng)兩個連續(xù)迭代之間的PageRank值之差小于0.000 001時，算法停止。

為了更好地觀察，Pi(t)量化到1到 10，如圖4(a)，在時間t的最大值和最小值之間有10個相等的間隔。

4 ARIMA人群流動性預(yù)測

ARIMA (Auto Regressive Integrated Moving Average) 被廣泛用于對時間序列進(jìn)行預(yù)測，常被用于需求預(yù)測和規(guī)劃中。不過，如果是從一個非平穩(wěn)的時間序列開始，首先需要做差分，直到得到一個平穩(wěn)的序列。模型的思想就是從歷史的數(shù)據(jù)中學(xué)習(xí)到隨時間變化的模式，學(xué)到的規(guī)律去預(yù)測未來。

ARIMA包含3個部分，即AR、I、MA。

AR：表示auto regression，即自回歸模型；

I表示integration，即單整階數(shù)，時間序列模型必須是平穩(wěn)性序列才能建立計量模型，ARIMA模型作為時間序列模型也不例外，因此首先要對時間序列進(jìn)行單位根檢驗，如果是非平穩(wěn)序列，就要通過差分來轉(zhuǎn)化為平穩(wěn)序列，經(jīng)過幾次差分轉(zhuǎn)化為平穩(wěn)序列，就稱為幾階單整。

MA：表示moving average，即移動平均模型?？梢姡珹RIMA模型實際上是AR模型和MA模型的組合。

本研究中，PUQ{PUQi,i=1,2,…,N}為給定熱點中上車事件時間序列，可將ARIMA模型的輸入設(shè)置為{PUQi,i=1,2,…,N-1}，輸出是PUQN，即乘客流量預(yù)測值。建立模型一共分為3部。分別介紹如下。

4.1 將非平穩(wěn)序列轉(zhuǎn)化為平穩(wěn)序列

一個時間序列的隨機(jī)變量是穩(wěn)定的，當(dāng)且僅當(dāng)它的所有統(tǒng)計特征都是獨立于時間的(是關(guān)于時間的常量)。穩(wěn)定的數(shù)據(jù)是沒有趨勢(trend)，沒有周期性(seasonality)的。如果一個時間序列是不穩(wěn)定的，那么預(yù)測前需要對改序列進(jìn)行求和操作，轉(zhuǎn)換成一個穩(wěn)定序列，如式(2)。

(2)

d是差分的階數(shù)，可以用單位根測試估計獲得。

4.2 自回歸(AR)

自回歸模型(Autoregressive Model)是用自身做回歸變量的過程，即利用前期若干時刻的隨機(jī)變量的線性組合來描述以后某時刻隨機(jī)變量的線性回歸模型，把時間序列PUQ的預(yù)測值表示為時間序列的歷史值和一個隨機(jī)白噪聲et的組合：

PUQN+1=φ0+φ1PUQN-1+φ2PUQN-2+…+φPPUQN-P+et

(3)

其中φ0是常數(shù)項，φ1,φ2,φP是參數(shù)模型，這些參數(shù)可以從PUQ中計算，et均值為0，方差為σ的白噪聲。

4.3 滑動平均(MA)

滑動平均法是一種簡單平滑預(yù)測技術(shù)，它的基本思想是：根據(jù)時間序列資料、逐項推移，依次計算包含一定項數(shù)的序時平均值，以反映長期趨勢的方法。本文中，可以將預(yù)測值表示為有限個歷史隨機(jī)白噪聲的線性組合為式(4)。

PUQN=αN-θ1αN-1-θ2αN-2-…-θqαN-q

(4)

因此在本文中ARIMA模型整合了上述三個過程，最后熱點i時間t處的預(yù)測值為式(5)。

PUQN+1=φ0+φ1PUQN-1+φ2PUQN-2+…+φPPUQN-P+et+αN-θ1αN-1-θ2αN-2-…-θqαN-q

(5)

由于一個熱點中上/下車的PUQ值是一個自然數(shù)，但預(yù)測值可能是小數(shù)，而且這里的預(yù)測值是偏移之后的時間序列得來的，所以最后的預(yù)測值為PUQN加上之前的均值E之后得到。

5 PageRank與ARIMA預(yù)測值的關(guān)系

如上所述，Pi(t)和PUQN都可以表示地區(qū)的出租車需求狀態(tài)。為了更直觀的了解兩者的關(guān)系，顯示了中國人民大學(xué)附近兩者一天內(nèi)的變化情況如圖4所示。

圖4 中國人民大學(xué)附近一天Pi(t)和PUQN的變化

可以看出，高Pi(t)伴隨著高PUQN，兩者變化極為類似，基于這樣的觀察我們進(jìn)一步探討Pi(t)和PUQN的關(guān)系(PUQN量化為1到10)。

為了進(jìn)一步確定Pi(t)和PUQN之間的相關(guān)程度，通過下面的等式計算Pi(t)和PUQN的Pearson相關(guān)系數(shù)(PCC)為式(6)。

(6)

其中N是相應(yīng)數(shù)據(jù)集中所有數(shù)據(jù)示例的數(shù)量。 列出了不同日期(假期，工作日和周末)和不同時間(早高峰時間，工作時間和晚高峰時間)的PCC如表1、表2所示。

表1 總時間段皮爾森系數(shù)

表2 一天中的皮爾森系數(shù)

從表1，表2可以看出，一天中Pi(t)和PUQN之間的平均Pearson相關(guān)系數(shù)為0.845 2。 除了周末的PCC小于0.8之外，其他情況下的PCC都大于0.8，這意味著Pi(t)和PUQN之間存在強(qiáng)的正線性相關(guān)性。因此，使用如下線性模型來擬合數(shù)據(jù)為式(7)。

PUQi(t)=a×Pi(t)+b

(7)

然后，使用最小二乘法進(jìn)行擬合，擬合曲線顯示如圖5所示。

圖5 擬合點分布圖

可以看出其中大多數(shù)分布在對角線附近。

6 總結(jié)

以上研究意味著可以直接利用(7)來快速的做。為了進(jìn)一步驗證這一點，我們用(7)將Pi(t)作為輸入，來對上下車乘客進(jìn)行預(yù)測，預(yù)測的準(zhǔn)確性被定義為式(8)。

(8)

表3 預(yù)測準(zhǔn)確率

本文介紹了使用出租車GPS軌跡數(shù)據(jù)來預(yù)測某地出租車需求。提出了基于復(fù)雜網(wǎng)絡(luò)中的PageRank流量建模，按照地區(qū)的上/下車乘客數(shù)量來劃分熱點，用ARIMA對熱點區(qū)域乘客量預(yù)測，通過實驗驗證，發(fā)現(xiàn)大部分地區(qū)的PageRank值與ARIMA預(yù)測值的皮爾森系數(shù)平均為0.817 4，兩者存在強(qiáng)正線性關(guān)系，并且對此進(jìn)行了準(zhǔn)確性驗證，平均準(zhǔn)確率為0.8446。因此PageRank值可以作為接下來熱點出租車需求的一項指標(biāo)。以上結(jié)果表明，以熱點區(qū)域作為節(jié)點PageRank建模是一種更為合理的交通預(yù)測手段。

事實上，出租車軌跡數(shù)據(jù)的分析不僅對出租車需求預(yù)測有幫助，對交通警察管理城市交通，提高效率，人力資源的分配有很大作用[13]。另外還可以引導(dǎo)乘客在更短的時間內(nèi)找到出租車，節(jié)省時間資源。還有對于司機(jī)，甚至城市規(guī)劃也很有幫助[14][15]。具體可以分為以下3個方面：

6.1 對乘客的服務(wù)

(1) 交通費用預(yù)測

出租車計價是行駛距離和等待時間的函數(shù)，但根據(jù)路況的不同，如紅綠燈的等待時間，以及緊急情況等會產(chǎn)生不同的費用。通過分析出租車在兩地之間的頻繁路線，綜合道路具體情況來預(yù)測交通費用。

(2) 交通時間分析

交通時間通常包括人們等到交通工具的時間。可以使用兩地的平均通行時間，也可以根據(jù)通行速度來進(jìn)行推斷。但是根據(jù)出租車計算時間有一定的局限性，出租車的等候時間靈活多變難以計算，等候的人群會因天氣，時間太長節(jié)假日等情況產(chǎn)生影響。

(3) 候車信息推薦

為解決難打車問題，向乘客推薦合適的乘車地點以及準(zhǔn)確的候車時間。

6.2 司機(jī)如何提高運行效率

(1) 道路路況檢測

通過整體的出租車軌跡數(shù)據(jù)，實時監(jiān)測路況，判斷道路通暢，交通堵塞以及交通速度等情況進(jìn)而分析最佳行車路線，最佳行車路線結(jié)合路況和學(xué)習(xí)出租車司機(jī)的只會，獲得更好的行車路線。

(2) 載客策略

幫助司機(jī)更快更好的找到乘客，提高收益，減低油耗。

6.3 政府如何改善交通

(1) 路網(wǎng)規(guī)劃

通過車輛軌跡，研究構(gòu)建城市道路，走向。復(fù)雜的單雙通行道路，高架等。但是存在一定的問題，出則車軌跡能否正確反應(yīng)交通情況，以及出租車行駛路線并不一定是兩地的最短距離。

(2) 交通供求分析

分析區(qū)域的交通客流量，建立公共交通體系，合理分配公共交通資源。

智慧城市作為一項新興的全球技術(shù)，旨在對資源進(jìn)行智能管理來促進(jìn)可持續(xù)發(fā)展，將給人們帶來高質(zhì)量的生活！