彭 艦，孫 海，陳 瑜，仝 博，黃飛虎

(四川大學(xué)計(jì)算機(jī)學(xué)院 成都 610065)

近年來(lái)，中國(guó)城市輕軌交通系統(tǒng)得到了快速發(fā)展。在城市輕軌交通系統(tǒng)中，自動(dòng)售票檢票系統(tǒng)(auto fare collection, AFC)采集和記錄了海量的乘客出行數(shù)據(jù)[1]。如何從這些數(shù)據(jù)中挖掘乘客的出行規(guī)律、出行軌跡模式等具有重要的研究?jī)r(jià)值。例如，通過(guò)對(duì)乘客出行軌跡的預(yù)測(cè)，運(yùn)營(yíng)商可以及時(shí)、快捷地制定針對(duì)緊急狀況的應(yīng)對(duì)措施、為乘客提供個(gè)性化服務(wù)、動(dòng)態(tài)調(diào)整輕軌的發(fā)車頻次；此外，還可以通過(guò)對(duì)乘客出行軌跡的精準(zhǔn)預(yù)測(cè)制定輕軌廣告投放策略，并可為新的交通網(wǎng)絡(luò)設(shè)計(jì)提供決策支持。大多數(shù)研究[2-4]集中于對(duì)乘客出行目的地的預(yù)測(cè)，很少對(duì)乘客的出行軌跡進(jìn)行預(yù)測(cè)。本文基于重慶市輕軌交通系統(tǒng)乘客的刷卡數(shù)據(jù)，提出一種基于馬爾科夫鏈的乘客軌跡預(yù)測(cè)算法(light rail passenger trajectory prediction based on markov chain, LRPTPMC)，用于預(yù)測(cè)乘客下次出行軌跡。實(shí)驗(yàn)表明，該算法具有較好的預(yù)測(cè)效果。

1 相關(guān)研究

文獻(xiàn)[5]基于公交IC卡數(shù)據(jù)，分別給出了由IC卡統(tǒng)計(jì)數(shù)據(jù)推算公交線路站點(diǎn)和區(qū)間出行站點(diǎn)的方法，并提出了基于GIS的公交IC卡數(shù)據(jù)分析處理系統(tǒng)框架，實(shí)現(xiàn)公交站點(diǎn)的推算；文獻(xiàn)[6]提出了一種利用公交調(diào)度信息和智能卡刷卡信息來(lái)推斷乘客上車站點(diǎn)的方法；文獻(xiàn)[7]通過(guò)對(duì)北京市市民乘坐公交及地鐵出行歷史數(shù)據(jù)的分析，研究了乘客的個(gè)人出行模式。這些研究都是基于智能IC卡的數(shù)據(jù)，其關(guān)注點(diǎn)集中于公交站點(diǎn)及乘客個(gè)人的出行模式，未針對(duì)乘客下次出行軌跡進(jìn)行預(yù)測(cè)。

在移動(dòng)對(duì)象的軌跡預(yù)測(cè)方面，文獻(xiàn)[2]基于地理和軌跡的語(yǔ)義特征預(yù)測(cè)移動(dòng)對(duì)象下一時(shí)刻位置點(diǎn)信息，通過(guò)挖掘同類用戶的常見(jiàn)行為特性來(lái)預(yù)測(cè)其未來(lái)位置；文獻(xiàn)[3]提出基于狀態(tài)的移動(dòng)對(duì)象運(yùn)動(dòng)模型，并采用馬爾科夫轉(zhuǎn)移概率解釋移動(dòng)對(duì)象在不同狀態(tài)間的轉(zhuǎn)換；文獻(xiàn)[4]采用混合馬爾科夫鏈模型預(yù)測(cè)行人運(yùn)動(dòng)。然而，在這些已有的預(yù)測(cè)模型中，極大可能存在答案丟失[7]和精度依賴問(wèn)題[8]。此外，這些研究均基于向量空間進(jìn)行預(yù)測(cè)，無(wú)法預(yù)測(cè)具體的移動(dòng)方向[9-10]。

因此，針對(duì)以上問(wèn)題，本文主要針對(duì)城市輕軌交通系統(tǒng)中乘客的下次出行軌跡預(yù)測(cè)進(jìn)行研究。

2 LRPTPMC：輕軌乘客軌跡預(yù)測(cè)算法

本節(jié)先給出相關(guān)參數(shù)定義和馬爾科夫鏈模型，然后介紹輕軌乘客軌跡的預(yù)測(cè)算法。

2.1 相關(guān)定義

定義 2 連續(xù)軌跡。若當(dāng)前的線路軌跡Gc的目的站點(diǎn)Sck與下次出行的軌跡Gn的出發(fā)站點(diǎn)Sn0相同，則稱Gc和Gn是兩條連續(xù)軌跡。

通過(guò)在真實(shí)輕軌交通數(shù)據(jù)集上的實(shí)驗(yàn)分析，乘客軌跡完整度取值大約為42.3%，由此可知，乘客的出行具有偏好返回特性。

表1 參數(shù)列表

定義 5 乘客常住地。乘客刷卡記錄中，出現(xiàn)次數(shù)最多的進(jìn)站站點(diǎn)。

算法中參數(shù)說(shuō)明如表1所示。

2.2 馬爾科夫鏈模型

馬爾科夫鏈模型認(rèn)為用戶下次出行的地點(diǎn)和之前去過(guò)的地點(diǎn)存在關(guān)聯(lián)。MC模型中，用戶的軌跡序列將構(gòu)成該用戶的n階馬爾科夫鏈，即用戶u第i次訪問(wèn)的地點(diǎn)與該用戶之前訪問(wèn)的n個(gè)地點(diǎn)存在關(guān)聯(lián)關(guān)系，式(1)給出了其計(jì)算方法：

2.3 LRPTPMC預(yù)測(cè)算法描述

算法預(yù)測(cè)輕軌乘客出行軌跡分兩個(gè)步驟：首先，利用貝葉斯分類器對(duì)乘客下次出行是探索新的軌跡，還是選擇歷史出行軌跡進(jìn)行分類；然后，根據(jù)乘客最近一次出行軌跡與其常住地的關(guān)系，預(yù)測(cè)下次出行軌跡。

2.3.1 軌跡分類

根據(jù)樸素貝葉斯分類器，乘客軌跡可根據(jù)式(3)進(jìn)行分類：

式中，x為特征向量，其中m為乘客歷史軌跡的次數(shù)，n為歷史不同軌跡的數(shù)量，p為歷史不同軌跡的數(shù)量和歷史軌跡的次數(shù)的比值，q為探索新線路的次數(shù)；Y為類別標(biāo)記，Y={01}，，0表示乘客下次出行會(huì)探索新的軌跡，1表示乘客下次出行會(huì)選擇歷史出行軌跡。

2.3.2 軌跡預(yù)測(cè)

確定乘客下一次出行軌跡的分類之后，即可對(duì)乘客下一次出行軌跡進(jìn)行預(yù)測(cè)。根據(jù)乘客最近一次出行軌跡與其常住地的關(guān)系，按以下4種情況預(yù)測(cè)其下次出行軌跡。

1)進(jìn)站站臺(tái)為常住地

算法首先判斷最近一次出行軌跡是否為新的軌跡。如果是新的軌跡，就判斷該乘客的值，當(dāng)即出行模式為“”時(shí)，下次出行軌跡即是最近一次出行軌跡；當(dāng)結(jié)合之前的數(shù)據(jù)分析，乘客的出行具有往返的特性，下次的出行則返回常住地。如果最近一次出行軌跡不是新的軌跡，即為歷史軌跡時(shí)，首先構(gòu)建該乘客出行軌跡的一階馬爾科夫狀態(tài)轉(zhuǎn)移矩陣，從狀態(tài)轉(zhuǎn)移矩陣中選取值最大的軌跡作為下次出行軌跡。

2)進(jìn)出站臺(tái)均不為常住地

當(dāng)乘客最近一次出行軌跡的進(jìn)站站臺(tái)和出站站臺(tái)均不為該乘客的常住地時(shí)，該乘客很可能處于中間狀態(tài)，很難對(duì)其描述。該情形下，本文引入了軌跡狀態(tài)轉(zhuǎn)移矩陣，同時(shí)結(jié)合了時(shí)間、距離、線路熱度等因素對(duì)其進(jìn)行預(yù)測(cè)。

通過(guò)對(duì)重慶市輕軌數(shù)據(jù)的分析，發(fā)現(xiàn)在“中間狀態(tài)”下，乘客下次出行軌跡的選擇依賴于最近一次出行軌跡，同時(shí)也和出發(fā)的時(shí)間密切相關(guān)。表1中已將連續(xù)的時(shí)間處理成離散的數(shù)據(jù)。在實(shí)際生活中，乘客下次的出行與最近幾次出行具有很強(qiáng)的相關(guān)性，為體現(xiàn)這種相關(guān)性，本文定義歷史軌跡中的軌跡與最近一次出行軌跡的距離Tshort為：

其中，

由式(6)和式(7)，式(5)可寫(xiě)為：

綜上所述，當(dāng)進(jìn)出站臺(tái)均不為常住地時(shí)，預(yù)測(cè)思路為：首先構(gòu)建關(guān)于時(shí)間狀態(tài)轉(zhuǎn)移的一階馬爾科夫矩陣以及計(jì)算歷史軌跡熱度值。然后判斷最近一次軌跡是否為新的軌跡，如果是，則下次的出行軌跡的進(jìn)站時(shí)間為時(shí)間轉(zhuǎn)移矩陣中最大的時(shí)間值，根據(jù)出行時(shí)間找到該出行時(shí)間段中熱度值最大的軌跡作為下次出行軌跡；如果最近一次軌跡是歷史軌跡中出現(xiàn)過(guò)的軌跡，則構(gòu)建關(guān)于軌跡狀態(tài)轉(zhuǎn)移的一階馬爾科夫矩陣。最后依據(jù)式(8)計(jì)算每條歷史軌跡的權(quán)值V，并選擇取值最大的軌跡作為下次出行軌跡。

3)出站站臺(tái)為常住地

當(dāng)乘客最近一次出行軌跡中出站站臺(tái)為常住地時(shí)，本文根據(jù)人類出行具有的最近相關(guān)性，引入了乘客的最近出行模式；同時(shí)，根據(jù)乘客出行的群集效應(yīng)，引入了站臺(tái)出度熱度Sin，入度熱度Sout以及軌跡熱度Lhot。出度熱度Sin和入度熱度Sout的計(jì)算方法分別如下：

4)探索新軌跡

由于馬爾科夫模型是基于歷史軌跡對(duì)下次出行軌跡進(jìn)行預(yù)測(cè)，不能有效解決乘客探索新軌跡的問(wèn)題。因此，當(dāng)預(yù)測(cè)到乘客下次的出行為探索新軌跡時(shí)，本文根據(jù)其他乘客的出行選擇解決乘客探索新軌跡的問(wèn)題。首先構(gòu)建該乘客出行時(shí)間的狀態(tài)轉(zhuǎn)移矩陣，根據(jù)該矩陣來(lái)預(yù)測(cè)其下次出行的時(shí)間。然后根據(jù)這個(gè)出行時(shí)間，計(jì)算該時(shí)間段內(nèi)所有乘客歷史軌跡的Lhot值(不包括該乘客的歷史軌跡)，預(yù)測(cè)的下次出行的軌跡即為L(zhǎng)hot值最大的軌跡。

3 實(shí)驗(yàn)及分析

3.1 實(shí)驗(yàn)環(huán)境和數(shù)據(jù)說(shuō)明

本文的實(shí)驗(yàn)基于Spark集群(1臺(tái)master，4臺(tái)slave主機(jī))。實(shí)驗(yàn)所用到的數(shù)據(jù)集是重慶市輕軌軌道交通系統(tǒng)中2014年12月1日—2015年5月31日的輕軌刷卡數(shù)據(jù)，表2給出了具體的數(shù)據(jù)描述。

原始數(shù)據(jù)集中包含444 743 582條刷卡記錄，7 473 709位輕軌乘客。本節(jié)數(shù)據(jù)只保留了在這6個(gè)月內(nèi)出行次數(shù)不少于100次的乘客的出行數(shù)據(jù)。

表2 數(shù)據(jù)集描述

3.2 數(shù)據(jù)預(yù)處理

3.2.1 數(shù)據(jù)格式介紹

本文所分析的數(shù)據(jù)是2014年12月—2015年5月共6個(gè)月的重慶市軌道交通的刷卡數(shù)據(jù)。該數(shù)據(jù)集包含了7 473 709個(gè)智能IC卡的共計(jì)444 743 582條的軌道交通刷卡記錄，每條記錄包含一次輕軌出行中乘客所搭乘輕軌的時(shí)間以及站臺(tái)信息。主要包含的字段有：卡ID(TICKET_ID)、刷卡日期(TXN_DATE)、刷卡時(shí)間(TXN_TIME)、刷卡站臺(tái)ID(TXN_STATION_ID)、卡類型(TICKET_TYPE)、進(jìn)出站標(biāo)志(TRANS_CODE)和換乘標(biāo)識(shí)(TXN_AMT)等。

3.2.2 軌跡提取

刷卡記錄是按照刷卡時(shí)間來(lái)記錄的，數(shù)據(jù)可能存在記錄錯(cuò)誤和數(shù)據(jù)缺失問(wèn)題。本文利用Spark框架對(duì)海量的數(shù)據(jù)進(jìn)行了軌跡提取，過(guò)程如下：

1)創(chuàng)建一個(gè)CardID標(biāo)識(shí)，初始值設(shè)為0，并將數(shù)據(jù)集按照日期和時(shí)間升序的原則進(jìn)行排序。

2)訪問(wèn)最開(kāi)始的記錄，將CardID設(shè)為該記錄的TICKET_ID的值，并檢查TRANS_CODE字段的值；如果值為21，則進(jìn)行步驟3)，如果值為22，則視此條記錄為“臟記錄”，并訪問(wèn)下一條TICKET_ID字段的值等于CardID的記錄，重復(fù)步驟2)的工作。

3)存儲(chǔ)記錄中的TICKET_ID、TXN_DATE、TXN_TIME、TXN_STATION_ID字段的值后刪除此條記錄，并訪問(wèn)下一條TICKET_ID字段的值等于CardID的記錄。

4)檢查該記錄中TRANS_CODE字段的值。如果值為22，則存儲(chǔ)記錄中的TICKET_ID，TXN_DATE，TXN_TIME，TXN_STATION_ID字段的值；如果值為21，則視此條記錄為“臟記錄”。最后刪除此條記錄，并訪問(wèn)下一條TICKET_ID字段的值等于CardId的記錄，并重復(fù)步驟4)。

5)上述步驟中兩次存儲(chǔ)的記錄就是卡ID為CardId值的乘客一次出行的完整軌跡，從步驟2)開(kāi)始重復(fù)，直到訪問(wèn)到最后一條TICKET_ID字段的值等于CardId的記錄，則可以得到卡ID為CardId值的乘客所有出行的完整軌跡。再將CardId的值設(shè)為0，重復(fù)步驟2)直到處理完全部記錄。

3.3 算法評(píng)價(jià)指標(biāo)

1)準(zhǔn)確率和召回率

在本文中，準(zhǔn)確率可以被視為預(yù)測(cè)精度，用于評(píng)價(jià)預(yù)測(cè)算法。公式如下：

式中，Ptotal表示預(yù)測(cè)的總次數(shù)；表示預(yù)測(cè)正確的次數(shù)。

召回率計(jì)算公式如下：

2)F1分?jǐn)?shù)

引入F1分?jǐn)?shù)可以評(píng)價(jià)模型的綜合性能，其計(jì)算公式如下：

3.4 實(shí)驗(yàn)結(jié)果對(duì)比與分析

本文所用到的3個(gè)對(duì)比算法分別為L(zhǎng)TMT、RNN及2-MC，其中LTMT為乘客歷史軌跡中出現(xiàn)次數(shù)最多的線路(line of travel most times)；RNN為循環(huán)神經(jīng)網(wǎng)絡(luò)[11]；2-MC為二階馬爾科夫鏈，常用于目的地預(yù)測(cè)[12]。圖1給出了預(yù)測(cè)精度測(cè)試對(duì)比結(jié)果。

由圖1可知，本文的預(yù)測(cè)算法的預(yù)測(cè)精度明顯優(yōu)于其他3種算法，而隨著乘客歷史軌跡不同線路的增加，其預(yù)測(cè)精度也隨之下降。其中RNN和2-MC的預(yù)測(cè)精度很相近，圖中的離散點(diǎn)大致重合。

圖1 預(yù)測(cè)精度對(duì)比圖

表3 算法對(duì)比

所有評(píng)價(jià)指標(biāo)的對(duì)比如表3所示。根據(jù)圖1和表3的結(jié)果可知，本文提出的LRPTPMC預(yù)測(cè)算法在精度、召回率和F1值等方面均優(yōu)于其他3種常見(jiàn)算法。對(duì)于單一的二階馬爾科夫模型來(lái)說(shuō)，其預(yù)測(cè)精度不及LRPTPMC算法的一半，說(shuō)明本文的預(yù)測(cè)算法在馬爾科夫模型基礎(chǔ)上的改進(jìn)有效。

圖2 運(yùn)行時(shí)間對(duì)比

本文的實(shí)驗(yàn)基于分布式處理框架Spark，對(duì)預(yù)測(cè)算法進(jìn)行了并行化處理。圖2對(duì)比了單機(jī)環(huán)境下的算法和并行化算法進(jìn)行運(yùn)行時(shí)間。采用了6組數(shù)據(jù)，根據(jù)預(yù)測(cè)乘客的數(shù)量不同來(lái)體現(xiàn)運(yùn)行時(shí)間的差異。如圖2所示，當(dāng)乘客數(shù)量規(guī)模大于1 000時(shí)，集群能有效利用其計(jì)算資源，能有效減少算法運(yùn)算時(shí)間。

4 結(jié)束語(yǔ)

城市輕軌交通系統(tǒng)中采集和積累了海量的乘客出行數(shù)據(jù)。本文基于對(duì)重慶市輕軌交通數(shù)據(jù)的研究，提出了一種基于馬爾科夫鏈的乘客軌跡預(yù)測(cè)(LRPTPMC)算法。實(shí)驗(yàn)結(jié)果表明，相比既有的預(yù)測(cè)算法，本文的LRPTPMC算法優(yōu)于其他3個(gè)對(duì)比算法。同時(shí)利用分布式處理平臺(tái)Spark來(lái)進(jìn)行實(shí)驗(yàn)，極大地減少了實(shí)驗(yàn)運(yùn)行時(shí)間。利用本文算法，可幫助輕軌運(yùn)營(yíng)管理者預(yù)測(cè)站臺(tái)和輕軌流量，合理安排輕軌班次，改善輕軌交通服務(wù)。事實(shí)上，天氣、影響力傳播等因素也會(huì)對(duì)乘客出行產(chǎn)生影響，將這些因素融入輕軌乘客出行軌跡預(yù)測(cè)是本文下一步研究方向。