基于PageRank算法的出租車需求預測

周豐

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

0 引言

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

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

本文研究貢獻在于：

1.利用PageRank建模[10]時，把城市熱點區域作為節點，以此解決數據分區和網格分辨率對模型帶來的影響。

2.不僅利用ARIMA模型[11-12]預測熱點區域的乘客數量，而且還發現動態特征PageRank值與預測乘客量間的確定性關系。

3.根據北京市10000輛出租車軌跡數據實驗驗證結果的準確性。

2 數據處理

2.1 數據

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

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

圖1 北京城區部分出租車軌跡圖

計算熱點區域交通狀態時，我們以15分鐘作為時間間隔，每天有96個時間間隔，熱點提取時使用前10天的數據，后五天的數據被用來對模型進行預測準確率的驗證。

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

TAXI_ID：出租車的唯一ID;

GPS_TIME：采樣時間戳;

GPS_LONGITUDE：出租車當前經度；

GPS_LATITUDE：出租車當前緯度;

GPS_STATUS：GPS設備的當前狀態，有效或無效，表示來自GPS設備的消息是否成功。

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

2.2 數據處理

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

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

3 PageRank流量建模

3.1 熱點提取

熱點是頻繁出現上下車事件的區域，如圖2所示。

圖2 規定閾值后熱點圖

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

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

(2) 從軌跡數據提取轉換事件，記錄事件數量。

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

(a)

(b)

3.2 PageRank流量建模

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

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

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

(1)

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

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

4 ARIMA人群流動性預測

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

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

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

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

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

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

4.1 將非平穩序列轉化為平穩序列

一個時間序列的隨機變量是穩定的，當且僅當它的所有統計特征都是獨立于時間的(是關于時間的常量)。穩定的數據是沒有趨勢(trend)，沒有周期性(seasonality)的。如果一個時間序列是不穩定的，那么預測前需要對改序列進行求和操作，轉換成一個穩定序列，如式(2)。

(2)

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

4.2 自回歸(AR)

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

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

(3)

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

4.3 滑動平均(MA)

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

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

(4)

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

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

(5)

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

5 PageRank與ARIMA預測值的關系

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

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

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

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

(6)

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

表1 總時間段皮爾森系數

表2 一天中的皮爾森系數

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

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

(7)

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

圖5 擬合點分布圖

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

6 總結

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

(8)

表3 預測準確率

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

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

6.1 對乘客的服務

(1) 交通費用預測

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

(2) 交通時間分析

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

(3) 候車信息推薦

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

6.2 司機如何提高運行效率

(1) 道路路況檢測

通過整體的出租車軌跡數據，實時監測路況，判斷道路通暢，交通堵塞以及交通速度等情況進而分析最佳行車路線，最佳行車路線結合路況和學習出租車司機的只會，獲得更好的行車路線。

(2) 載客策略

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

6.3 政府如何改善交通

(1) 路網規劃

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

(2) 交通供求分析

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

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