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

周豐

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

0 引言

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

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

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

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

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

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

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

2.1 數(shù)據(jù)

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

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

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

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

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

TAXI_ID：出租車(chē)的唯一ID;

GPS_TIME：采樣時(shí)間戳;

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

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

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

METER STATE：表示計(jì)程表是否正在運(yùn)行，即出租車(chē)是否有乘客：如果出租車(chē)被占用，則為1；如果是空閑，則為0。

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

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

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

3 PageRank流量建模

3.1 熱點(diǎn)提取

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

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

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

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

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

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

(a)

(b)

3.2 PageRank流量建模

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

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

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

(1)

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

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

4 ARIMA人群流動(dòng)性預(yù)測(cè)

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

ARIMA包含3個(gè)部分，即AR、I、MA。

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

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

MA：表示moving average，即移動(dòng)平均模型。可見(jiàn)，ARIMA模型實(shí)際上是AR模型和MA模型的組合。

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

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

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

(2)

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

4.2 自回歸(AR)

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

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

(3)

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

4.3 滑動(dòng)平均(MA)

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

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

(4)

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

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

(5)

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

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

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

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

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

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

(6)

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

表1 總時(shí)間段皮爾森系數(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)性。因此，使用如下線性模型來(lái)擬合數(shù)據(jù)為式(7)。

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

(7)

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

圖5 擬合點(diǎn)分布圖

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

6 總結(jié)

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

(8)

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

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

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

6.1 對(duì)乘客的服務(wù)

(1) 交通費(fèi)用預(yù)測(cè)

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

(2) 交通時(shí)間分析

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

(3) 候車(chē)信息推薦

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

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

(1) 道路路況檢測(cè)

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

(2) 載客策略

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

6.3 政府如何改善交通

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

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

(2) 交通供求分析

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

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