智能交通刷卡記錄中的公交站點恢復方法

王藝霖,章志剛,金澈清

(華東師范大學數(shù)據(jù)科學與工程學院,上海200062)

智能交通刷卡記錄中的公交站點恢復方法

王藝霖,章志剛,金澈清

(華東師范大學數(shù)據(jù)科學與工程學院,上海200062)

隨著城市公共交通網(wǎng)絡(luò)的快速發(fā)展以及智能交通卡的普及,智能交通卡中隱藏著越來越豐富的個人及群體移動行為信息.但當前很多城市智能公交卡主要用于收費功能,并未包含乘客確切的上下車時間及站點信息,這給分析挖掘交通卡刷卡數(shù)據(jù)、提供基于精確位置的服務(wù)帶來了阻礙.本文針對上海市不含公交上下車站點的刷卡數(shù)據(jù)集,借助于確定的地鐵站點刷卡信息,分析個人的整體刷卡歷史記錄,提出一個基礎(chǔ)的基于時空鄰近性的恢復算法(STA, Space-Time Adjacency algorithm)和一個改進的基于歷史的恢復算法(HTB,Historical Trip Based algorithm).具體地,STA算法根據(jù)刷卡記錄線路的時空鄰近關(guān)系進行恢復,在此基礎(chǔ)上,HTB算法將刷卡記錄集合根據(jù)時間和空間屬性進行切分,獲得有明確出行意義的出行記錄,再利用歷史記錄集合,提取乘坐線路以及頻繁換乘線路,根據(jù)線路間的空間關(guān)系生成線路帶權(quán)候選站點列表,再次進行站點恢復.實驗證明本文算法可以較好地縮小線路的候選上下車站點范圍,且時間效率較高.

智能交通卡;缺失數(shù)據(jù);刷卡數(shù)據(jù)挖掘;站點推測

0 引言

隨著世界人口的增加和城市人口比例的不斷提高,設(shè)計、維持和促進可持續(xù)的城市公共交通模式變得非常重要.近年來,有越來越多的城市提供更加豐富的公共交通出行方式,促使更多乘客選擇公交、地鐵出行.與此同時,城市智能交通卡也在廣泛普及,便捷的付費方式以及優(yōu)惠的付費政策正吸引著越來越多的人采用智能交通卡出行.因此,每天都有數(shù)量巨大的智能交通刷卡數(shù)據(jù)在累積.大量的交易記錄隱含著豐富的信息,它不但記錄著一個人的公共交通出行基本信息,反映一個人的出行模式,也隱含著城市人群的移動模式和規(guī)律.目前有很多研究工作關(guān)注于利用智能交通卡數(shù)據(jù)分析挖掘乘客的移動模式[1-2].文獻[3]詳細分析了利用智能交通卡數(shù)據(jù)進行人群移動行為分析的可行性,文獻[4]從長期交通規(guī)劃、公共交通服務(wù)調(diào)整、日常乘客乘坐需求分析等三個層面描述智能交通卡數(shù)據(jù)的應(yīng)用.

盡管公共交通卡的廣泛使用使得其隱含著關(guān)于乘客出行的豐富信息,但在有些城市中,公共交通卡的設(shè)計只為完成收費功能,卡中并未記錄乘客出行的具體信息,如上下車站點、上下車時間[5].例如,上海市公共交通卡可以在公交、地鐵、出租車、輪渡等多種交通方式中使用,但只有地鐵乘坐的上下車時間信息和站點信息被完整記錄下來,出租車刷卡數(shù)據(jù)中只含刷卡時間而不含任何地理位置信息.由于上海的公交都采用一票制,在其交通卡信息存儲的設(shè)計中就沒有考慮存儲上下車站點信息以及下車時間,只有乘客上車的時間被記錄下來.數(shù)據(jù)集的不確定性和不完整性對分析和挖掘智能交通卡數(shù)據(jù)的研究工作產(chǎn)生了很大的阻礙.目前已有一些針對智能交通卡數(shù)據(jù)的恢復研究工作[6-7],這些工作大多都對至少包含上車站點或下車站點其中之一的刷卡數(shù)據(jù),利用“出行鏈”的思想進行數(shù)據(jù)恢復工作[8].文獻[5]針對部分公交線路中上下車站點信息均無的數(shù)據(jù)集,利用金錢、時間、空間維度的限制關(guān)系,以及占有一定比例的完整公交線路刷卡信息進行恢復,但其并沒有利用乘客整體歷史刷卡數(shù)據(jù)中的出行目的等隱藏含義以及乘客乘坐規(guī)律對站點進行恢復.以上研究工作均不適用于僅含有乘坐線路和上車時間的城市智能交通卡刷卡數(shù)據(jù)集的站點恢復工作.

為解決以上問題,本文提出基于歷史出行記錄的智能交通卡刷卡數(shù)據(jù)恢復方法.本文的主要貢獻如下.

1)考慮每條刷卡記錄對于乘客的出行意義,提出了基于時間和空間的出行記錄切分方法,以出行記錄的維度進行分析和站點恢復工作;

2)分析整張卡的所有歷史出行記錄,提取乘坐線路和頻繁換乘線路,利用線路出現(xiàn)頻次和線路間的空間位置關(guān)系,為線路站點設(shè)置權(quán)重,建立乘坐線路的候選站點列表,對刷卡記錄中的站點進行再恢復;

3)將所提出的方法應(yīng)用于真實數(shù)據(jù)集中進行刷卡記錄的恢復工作,分析證明了方法的合理性和有效性.

本文第1節(jié)介紹相關(guān)工作;第2節(jié)介紹數(shù)據(jù)集以及問題定義;第3節(jié)介紹基于時空鄰近性的刷卡數(shù)據(jù)恢復方法;第4節(jié)介紹基于出行記錄切分和歷史記錄的站點推測方法;第5節(jié)進行實驗結(jié)果展示與分析;第6節(jié)對工作進行總結(jié)和展望.

1 相關(guān)工作

本文工作主要與以下研究領(lǐng)域相關(guān).一個研究領(lǐng)域為利用多種軌跡數(shù)據(jù)發(fā)現(xiàn)人群移動模式及規(guī)律,進行路線發(fā)現(xiàn)或推薦等;另一個研究領(lǐng)域為智能交通卡數(shù)據(jù)的恢復與挖掘工作.

隨著各種軌跡數(shù)據(jù),如出租車GPS數(shù)據(jù)、手機基站連接數(shù)據(jù)、公交刷卡數(shù)據(jù)等的不斷積累,由歷史出行數(shù)據(jù)中發(fā)現(xiàn)個人移動模式或群體移動模式或推薦路徑引起了很多研究者的興趣.一些研究工作表明,人們的移動模式有很強的規(guī)律性以及可預測性[9].在城市中,人們常遵循一定的時空出行規(guī)律,且主要活動在有限的幾個固定地點附近,例如工作地和居住地,并在其中有規(guī)律地通行[10].文獻[11]嘗試發(fā)現(xiàn)目標的移動規(guī)律,包括在復雜的移動模式中找到移動周期,挖掘規(guī)律的移動行為等.在此基礎(chǔ)上,衍生了很多有關(guān)人群移動數(shù)據(jù)的應(yīng)用.文獻[12]考慮人群移動的規(guī)律性和一致性,利用興趣點簽到數(shù)據(jù)、車載GPS數(shù)據(jù)、公交刷卡數(shù)據(jù)等預測人的移動位置.文獻[13]利用出租車GPS數(shù)據(jù)構(gòu)建軌跡數(shù)據(jù)庫,記錄出發(fā)及到達的時間地點,根據(jù)歷史數(shù)據(jù)提供實時的路線費用及用時估計.文獻[14]利用手機連接基站產(chǎn)生的GPS數(shù)據(jù),發(fā)現(xiàn)停留區(qū)域,并獲取有效移動軌跡,由歷史軌跡數(shù)據(jù)發(fā)現(xiàn)熱門線路.文獻[15]利用海量出租車GPS歷史數(shù)據(jù),考慮時間、距離、油耗等因素,針對每位司機的出行偏好,篩選可參考的歷史軌跡數(shù)據(jù),提供實時路線推薦.海量歷史軌跡數(shù)據(jù)隱含著豐富的信息,可以考慮個性化因素進行軌跡挖掘,提高推薦路線的質(zhì)量.與GPS數(shù)據(jù)不同,公交刷卡數(shù)據(jù)記錄一個人每天搭乘公共交通出行的歷史軌跡,更能反映一些乘客常去的重要地點.通過對公交刷卡數(shù)據(jù)的分析,可以更好地了解城市公共交通的使用情況,提高服務(wù)質(zhì)量.

與此同時,一些研究工作專注于智能交通卡刷卡數(shù)據(jù)的分析挖掘及補充和恢復工作.文獻[16]總結(jié)了智能交通卡在城市研究中的應(yīng)用,包括數(shù)據(jù)處理與上下車站點推測、公共交通系統(tǒng)的管理、城市空間結(jié)構(gòu)的利用分析等幾個方面.文獻[17]利用北京市智能交通刷卡識別常用工作地、居住地以及頻繁利用的上下班線路,研究城市上下班通勤模型.文獻[18-19]分析公共交通乘坐行為,研究人們乘坐地鐵或公交的可接受步行距離范圍,發(fā)現(xiàn)影響步行距離最重要的因素是交通工具類型,而與出行目的、出行時間、乘客年齡等因素關(guān)系較小.

上述挖掘智能公交卡刷卡數(shù)據(jù)的工作常遇到公交刷卡數(shù)據(jù)信息不完整的問題.對于此問題,文獻[8]首先提出了兩條用于站點推測的重要假設(shè):①大部分乘客當天最后一次出行的終點和當天第一次出行的起點相同;②大部分乘客上一次出行的終點與下一次出行的起點距離較近.多數(shù)恢復工作都利用了上述“出行鏈”的思想,主要針對上車站點或下車站點之一缺失的情況進行站點恢復工作[6-8].文獻[20]對乘客刷卡時間進行聚類,與公交實時位置等其他數(shù)據(jù)來源進行匹配,輔助推測公交上下車站點;文獻[21]建立公交站點吸引權(quán)系數(shù)概率模型,依據(jù)每個站點上下車乘客的數(shù)目及概率,推算乘客上下車站點,但其上下車站點概率的設(shè)置主要與站點熱門程度相關(guān),缺失針對一個人的整體歷史記錄進行站點推算的工作.目前只有文獻[5]對上下車信息全無的公交刷卡記錄進行恢復,但其僅考慮相鄰刷卡記錄而沒有綜合一個人的所有歷史刷卡記錄信息及乘客出行目的進行站點恢復工作.本文研究工作與其有以下幾點不同:首先,文中提出了一種基于時空的刷卡記錄切分方法,將刷卡記錄組成有明確出行目的的出行記錄;然后充分考慮整體出行記錄中的隱含信息和線路間的空間關(guān)系,生成線路帶權(quán)候站點列表,幫助確定上下車候選站點.

2 問題描述

在本節(jié)中,主要進行數(shù)據(jù)準備及問題定義.具體地,2.1節(jié)描述上海市公共交通刷卡數(shù)據(jù)集基本情況和公共交通網(wǎng)絡(luò)的構(gòu)建工作,2.2節(jié)給出基于以上數(shù)據(jù)集的問題定義.

2.1 數(shù)據(jù)描述

智能交通卡刷卡數(shù)據(jù)含上海1 384萬張智能交通卡在2015年4月產(chǎn)生的4.13億次刷卡數(shù)據(jù),刷卡數(shù)據(jù)類型包含公交、地鐵、出租車、輪渡等.其中公交專指公共汽車,地鐵指上海軌道交通,含軌道交通1號線到13號線以及16號線,共計14條線,出租車指可以使用上海智能交通卡消費的城市出租車.各種刷卡記錄類型及數(shù)量如表1所示.

表1 各類型刷卡數(shù)據(jù)數(shù)目統(tǒng)計Tab.1 Statistics of various transaction data types

每條刷卡記錄包含以下屬性:卡號、日期、刷卡時間、交通工具類型以及線路名稱.其中地鐵乘坐在進站和出站時都需要刷卡,刷卡數(shù)據(jù)中包含了上下車站點及上下車時間;公交只有上車時需要刷卡,刷卡數(shù)據(jù)中僅包含線路名稱和上車時間;出租車刷卡數(shù)據(jù)中只包含下車時間;還有小部分輪渡等不含地理位置信息的刷卡記錄.刷卡記錄的具體格式如表2所示.

城市公共交通網(wǎng)絡(luò)由公交及地鐵線路站點組成.在刷卡數(shù)據(jù)集中,共出現(xiàn)1 344條公交線路,14條地鐵線路.利用公共地圖應(yīng)用接口高德API,查詢刷卡數(shù)據(jù)集中出現(xiàn)的所有公交及地鐵線路,以及各線路站點的具體位置信息.由于刷卡記錄中有些線路名稱有誤,以及少數(shù)公交線路運行調(diào)整,有89條公交線路在地圖應(yīng)用接口中查詢不到具體信息,視為“未知線路”,對應(yīng)刷卡記錄占總記錄的1.33%.為保證出行軌跡的完整性,保留“未知線路”的刷卡記錄.最終獲取公交線路1 255條,公交站點12 740個,地鐵線路14條,地鐵站點360個,以構(gòu)建公交和地鐵線路信息列表.

2.2 問題定義

從上述數(shù)據(jù)集的描述中可以看出,數(shù)據(jù)集中存儲的有關(guān)乘客上下車地理位置描述的信息缺失嚴重,公交線路的上下車站點全部都沒有被記錄.數(shù)據(jù)的不確定性和不完整性給進一步挖掘人群移動模式帶來了阻礙.為更好地挖掘數(shù)據(jù)集中隱含的豐富信息,提出公交站點恢復方法.具體定義如下.

定義1(站點恢復)給定一條公交刷卡記錄,考慮乘坐線路與鄰近刷卡記錄中乘坐線路交叉情況、線路間各站點間距、乘坐線路時間、乘客乘坐歷史上下文等信息,對該條刷卡記錄中的公交上/下車站點進行恢復.

3 基于刷卡記錄時空鄰近性的站點推測

一次公交刷卡記錄意味著乘客利用公共交通進行了一次地理位置的移動.相鄰刷卡記錄不但有著時間鄰近性,而且在乘客沒有采用其他卡中無記錄的交通工具出行的情況下,上一次乘車的下車站點和下一次乘車的上車站點之間很可能具有空間鄰近性,因而可以采用基于時空鄰近性的站點推測算法(STA,Space-Time Adjacency algorithm)進行站點推測.

刷卡數(shù)據(jù)中含有的刷卡類型有公交、地鐵、出租車等,有以下兩種情況可以利用空間關(guān)系進行簡單的站點推測.(1)對于地鐵-公交或公交-地鐵的連續(xù)乘坐,卡中可得知具體的地鐵站點,進而可以尋找公交線路中距離該地鐵站最近的公交站點.(2)對于公交-公交的連續(xù)乘坐,在卡中無法獲取到任何站點信息,僅知道乘坐線路及上車時間.這樣的連續(xù)兩次乘坐可能出現(xiàn)以下幾種情況:(a)因線路相同或出現(xiàn)“未知線路”,未找到站點;(b)線路距離較遠,未找到站點;(c)線路重合較多,可能的上下車站點較多;(d)線路重合站點或距離相近站點較少,可進行站點推測.

簡單來說該算法尋找時間上相鄰的兩條線路的重合站點或者距離相近的站點作為恢復結(jié)果,因而需要設(shè)置判定是否為鄰近站點的距離閾值.考慮到乘客步行速度限制、人群活動范圍的有限性、以及當前獲取換乘線路信息的便捷性,人們更可能在相同站點或距離更近的站點進行下一次乘坐.文獻[20]中對人們步行情況的研究表明,人們一天中的步行距離有限且大多小于2 km.文獻[21]顯示,在加拿大蒙特利爾人們可接受的到公交站和地鐵站的步行距離分別在400 m和800 m以內(nèi).此外我們計算出上海市公交站平均間隔距離約為700 m,因此對于地鐵-公交相鄰乘坐和公交-公交相鄰乘坐,分別設(shè)置距離閾值d1,d2,默認d1=1.5 km,d2=1 km.

具體過程如算法1所示.首先對刷卡數(shù)據(jù)按照卡號進行分組,使得同一張卡的記錄分到同一組當中(line 1),然后遍歷數(shù)據(jù)集對每一張卡的所有記錄按時間排序(line 3),接下來對排好序的刷卡記錄進行遍歷,考慮前后相鄰的記錄,利用距離閾值尋找候選站點(line 5).

對刷卡記錄數(shù)據(jù)集進行統(tǒng)計分析,其鄰近乘坐線路的空間鄰近性具體情況如表3所示.可以發(fā)現(xiàn)大多數(shù)的連續(xù)乘坐具有空間鄰近性.但同時發(fā)現(xiàn)公交-公交乘坐模式中,34.30%的連續(xù)乘坐是相同線路,另外20.50%的連續(xù)乘坐線路之間存在超過3個較近的站點,這給刷卡數(shù)據(jù)的推測和恢復工作帶來了挑戰(zhàn).

4 基于歷史出行記錄的站點推測

通過以上的分析和統(tǒng)計,可以看出僅考慮連續(xù)刷卡記錄的時空鄰近性的站點推測方法有很多局限性,對于連續(xù)乘坐同一條線路或連續(xù)乘坐相同站點較多的記錄不能得到很好的恢復,且沒有考慮每條刷卡記錄的潛在含義.本節(jié)介紹基于歷史出行記錄的站點推測算法(HTB,Historical Trip Based algorithm).結(jié)合文獻[8]中有關(guān)“出行鏈”的思想,該算法有兩個重要假設(shè):(1)使用智能交通卡的乘客大多數(shù)有固定的居住地,所以各天的第一次出行記錄大多由居住地附近出發(fā),各天的最后一次出行記錄也大多回到居住地.(2)前一天最后一次出行記錄若未回到居住地,可能與第二天的第一次出行記錄的起點有著空間鄰近性.

基于歷史出行記錄的站點推測算法除進行算法1的站點推測處理外,還進行以下三個處理操作:出行記錄劃分;提取乘坐線路及頻繁換乘線路;挖掘公交線路候選上下車站點,對數(shù)據(jù)進行再恢復.

4.1 出行記錄劃分

人們的一次出行,有具體的出行時間、出發(fā)地和目的地,對應(yīng)智能交通卡中的一條或多條刷卡記錄.刷卡記錄中的一條線路或者可以使乘客從出發(fā)地直達目的地,或者是乘客為到達目的地而乘坐的線路之一.為更好地利用刷卡記錄中的隱藏含義,提出一種基于時間和空間的記錄切分方法,將刷卡記錄組成出行記錄.出行記錄的具體定義如下.

定義2(出行記錄)一條出行記錄是由n(n≥1)條刷卡記錄按時間順序構(gòu)成的序列,且滿足以下三個約束:(1)相鄰刷卡記錄根據(jù)其交通工具類型的不同,刷卡時間間隔小于特定的時間閾值;(2)連續(xù)兩次地鐵刷卡記錄構(gòu)成一次完整的地鐵乘坐且包含在同一次出行記錄中;(3)同一條線路的連續(xù)兩次乘坐一定被包含在兩次不同的出行記錄中.

乘客在一次有明確目標的出行中會盡快完成乘坐及換乘,以抵達目的地.因而一張卡的刷卡記錄集合中,大于一定時間閾值的相鄰兩次刷卡記錄被認為屬于兩次不同的出行,應(yīng)該被劃分到兩次出行記錄中.一次出行中,乘客完成換乘和乘車兩種行為,設(shè)置換乘時間閾值T1和乘坐時間閾值T2.對于一次出行記錄內(nèi)的公交-公交/公交-地鐵的連續(xù)乘坐,閾值設(shè)為T1+T2;對于地鐵-公交/出租車的連續(xù)乘坐,由于地鐵刷卡發(fā)生在出站時,兩次刷卡時間間隔僅包含換乘時間T1.

出行記錄切分的具體方法如算法2所示.給定一張卡的所有刷卡記錄和時間閾值,遍歷刷卡記錄,根據(jù)切分規(guī)則進行切分.地鐵數(shù)據(jù)包括入站和出站信息,因而必定成對出現(xiàn),判斷當前記錄是否屬于出站記錄,決定是否對該記錄進行處理(Line 4).然后使用設(shè)定的時間閾值參數(shù),按照本節(jié)提出的閾值劃分規(guī)則進行劃分,將結(jié)果存入出行記錄集合L(Line 5-7).

此外,一條出行記錄在一天中所有出行記錄中的相對位置以及出發(fā)時間與出行目的地有著較強的關(guān)聯(lián).例如一張卡在某天有兩條出行記錄,且第一條出發(fā)時間為早上,該條出行記錄的起點更可能在居住地附近.若一張卡在某天僅有一條公交刷卡記錄,且乘坐時間為晚上10:00,該次乘坐的下車站點更可能靠近居住地.分析一張卡的出行記錄時間分布狀況,利用出行記錄的出發(fā)時間輔助判斷出行目的,有利于站點的推測工作.具體地,根據(jù)一天中的出行記錄次數(shù)及其在一天中的時間段,將出行記錄分為以下五種:START(一天中多條出行記錄中的第一條記錄)、END(一天中多條出行記錄中的最后一條記錄)、MID(一天中多條記錄中除去標簽為START和END的出行記錄)、ONESTART(一天中唯一的出行記錄且為由居住地附近出發(fā))和ONEEND(一天中唯一的出行記錄且為回到居住地附近).

4.2 乘坐線路及頻繁換乘線路發(fā)現(xiàn)

雖然乘客的出行路線多種多樣,但仍有相當比例的卡遵循著自己在時間和空間上的出行規(guī)律,其每天的出發(fā)地或到達地相對固定.因而可以利用乘坐線路間的站點位置關(guān)系,推測上下車站點.同時發(fā)現(xiàn)在一條出行記錄中,往往包含多條刷卡記錄,也就是乘客的一次出行需要多條公交線路的組合才能到達.而這種頻繁的換乘行為恰恰說明換乘的公交線路及換乘的地鐵線路沒有距離其出發(fā)地較近的站點,因而可以利用這種信息為后續(xù)處理提供幫助.

定義3(乘坐線路)乘坐線路包括標記為ONESTART或START的出行記錄中的第一條乘坐線路,和標記為ONEEND或END的出行記錄中的最后一條乘坐線路.

定義4(換乘線路)換乘線路是指標記為ONESTART或START的出行記錄中的第二條乘坐線路,和標記為ONEEND或END的出行記錄中的倒數(shù)第二條乘坐線路.

在HTB算法中,主要對標簽為START/ONESTART的出行記錄的上車站點及標簽為END/ONEEND的出行記錄的下車站點進行再推測,縮小乘客的候選站點的范圍.具體地,乘客乘坐線路及頻繁換乘線路提取方法如算法3所示.給定出行記錄集合和頻繁換乘線路閾值,遍歷出行記錄.首先判斷當前出行記錄的標簽類型,如果是ONESTART或START,將其第一條刷卡記錄對應(yīng)的線路加入到乘坐線路列表中,并更新其頻次(Line 3-4),同時如果第一條刷卡記錄為公交,則將第二條刷卡記錄中出現(xiàn)的地鐵站點或公交線路加入到換乘線路列表中,并更新其頻次(Line 5-6).相對應(yīng)地,對于標簽為ONEEND和END的出行記錄,處理過程相似,將出行記錄中的最后一條和倒數(shù)第二條刷卡記錄對應(yīng)的線路分別加入到乘坐線路列表和換乘線路列表中并更新頻次(Line 7-10).最后,使用設(shè)定的頻繁換乘線路閾值參數(shù)freq,對換乘線路列表進行過濾,刪除頻次過低的換乘線路(Line 11-13).

4.3 公交線路候選站點發(fā)現(xiàn)

算法3中提取的乘坐線路列表中可能含多條公交線路或多個地鐵站點,它們出現(xiàn)的頻次以及每兩條線路間的空間鄰近關(guān)系各不相同.這些線路之間擁有共同的公交站點或經(jīng)過相同的區(qū)域,而公交上下車站點很可能在這些線路共同經(jīng)過的區(qū)域內(nèi).同時,頻繁換乘線路列表中一些站點也會相交在一片共同區(qū)域中,顯然此類站點不是目標站點,根據(jù)這個輔助信息對候選站點進行篩選.

具體的候選站點挖掘過程如算法4所示.給定乘坐線路列表LineMap和頻繁換乘線路列表TransferMap,考慮線路出現(xiàn)的頻次以及線路間的站點鄰近關(guān)系,首先篩選LineMap中的線路,在LineMap中刪除頻繁換乘線路列表中的地鐵站點以及公交線路(Line 2-4).然后將LineMap中的線路組成公交-公交線路對和公交-地鐵線路對,線路對的權(quán)重取為兩線路在LineMap中的頻次之和.遍歷組成的線路對,找出線路間相同或滿足線路站點距離閾值d2的站點對,這些站點對將加入對應(yīng)線路的候選站點列表,兩線路對中產(chǎn)生的所有符合距離閾值的站點將平分該線路對的權(quán)重,更新線路中候選站點的權(quán)重(Line 5-9).接下來刪除結(jié)果列表中的頻繁換乘站點,對每一條線路,選擇權(quán)重最高的站點作為最可能的上下車站點,若有幾個權(quán)重最高且均相同的候選站點,將其一起保留(Line 10-11).

經(jīng)過以上處理過程,對于每一條非頻繁換乘線路的公交乘坐線路,都產(chǎn)生了一個候選站點列表,存儲著候選站點及其權(quán)重.利用這個結(jié)果可以對算法1的結(jié)果中標簽為START或ONESTART的出行記錄的出發(fā)站點以及標簽為END或ONEEND的出行記錄的到達站點進行再恢復,縮小線路的候選站點范圍.

5 實驗

5.1 實驗數(shù)據(jù)集

實驗采用上海市政府數(shù)據(jù)服務(wù)網(wǎng)公開的城市智能刷卡數(shù)據(jù)集[22],數(shù)據(jù)集描述如第2節(jié)所示.此外,本文選取了100位志愿者的卡進行人工標注.表4介紹了標注數(shù)據(jù)集中卡的出行記錄數(shù)目分布,表5介紹了卡的乘坐線路數(shù)目分布.

表4 人工標注數(shù)據(jù)出行記錄數(shù)目分布Tab.4 Distribution of cards’trip number

表5 人工標注數(shù)據(jù)乘坐線路數(shù)目分布Tab.5 Distribution of taken lines’number

5.2 實驗環(huán)境及相關(guān)設(shè)置

實驗在擁有24個節(jié)點的集群中完成,操作系統(tǒng)為Ubuntu 12.0.4.每個節(jié)點搭載6核Intel(R)Xeon(R)CPU E7-4809 v2@1.90 GHz的處理器,內(nèi)存共50 GB.所有實驗使用JAVA代碼實現(xiàn),JDK版本為1.8.0.算法2中換乘時間閾值T1設(shè)為30分鐘,乘坐時間閾值T2設(shè)為30分鐘,算法3中頻繁換乘線路閾值參數(shù)freq設(shè)為3.

5.3 實驗效果分析

整個數(shù)據(jù)集中,有20.53%的卡只有地鐵和出租車刷卡記錄,有18.22%的卡只含一條有效公交線路,對于這兩種卡進行過濾,不進行站點推測工作,以下實驗僅針對需要恢復的數(shù)據(jù)進行操作.本文實現(xiàn)了第3節(jié)提出的基于刷卡記錄時空鄰近性的站點推測方法,以及第4節(jié)提出的基于歷史出行記錄的站點推測方法.實驗效果分析HTB算法對整體數(shù)據(jù)集的處理效果,以及STA算法和HTB算法在標記數(shù)據(jù)集上的恢復結(jié)果.

(1)整體數(shù)據(jù)集算法效果分析

由算法2劃分所得的出行記錄內(nèi)部,相鄰記錄間不具有空間鄰近性的記錄占比1.71%(其中還包括與出租車的連續(xù)乘坐),與表3中所有鄰近刷卡記錄間的空間鄰近性統(tǒng)計情況相比,可以發(fā)現(xiàn)在所設(shè)時間閾值范圍內(nèi),同一出行記錄內(nèi)部確實具有更強的空間鄰近性關(guān)系,符合換乘的一般距離規(guī)律,這也證明了記錄切分方法的合理性.所有出行記錄的標簽分布結(jié)果如表6所示.標記為MID的出行記錄僅占總出行記錄的14%,START和ONESTART的出行記錄與END和ONEEND的出行記錄占主要部分且比例相近.這說明大多數(shù)情況下,一天中一張卡的出行記錄不超過兩條,即一天中乘客利用公共交通卡的出行不超過兩次.

表6 出行記錄的標簽占比統(tǒng)計Tab.6 Ratio of various labels on trips

圖1展示了經(jīng)算法3處理后得到的乘坐線路數(shù)目以及從乘坐線路中篩選掉頻繁換乘線路后的乘坐線路數(shù)目分布.可以看出,有很少的卡僅擁有一條乘坐線路(即在一個月內(nèi)每天第一條和最后一條乘坐線路全部相同),擁有2-8條乘坐線路的卡最為常見.豐富的乘坐線路給利用線路間的空間關(guān)系來獲取候選站點提供了可能.當從初步提取的乘坐線路中刪除掉頻繁換乘線路后,整體分布趨勢為卡的乘坐線路減少.被篩選掉的頻繁換乘線路可以防止換乘站點在算法4中權(quán)重設(shè)置過高,進而提高推測的準確性.

圖2展示了STA算法和HTB算法中標記為START/ONESTART的出行記錄的公交上車候選站點數(shù)目以及標記為END/ONEEND的出行記錄的公交下車候選站點數(shù)目累積分布對比.無任何公交候選站點的出行記錄的數(shù)目由46.42%降到5.24%.圖中可以看出,HTB算法明顯減少了候選上車站點的數(shù)目.HTB算法中,僅有一個候選站點的出行記錄數(shù)目達到STA算法的2.8倍.推測結(jié)果中,仍然會有一小部分出行記錄的候選站點數(shù)目較多,出現(xiàn)此種推測結(jié)果的原因可能是乘客刷卡數(shù)據(jù)集中乘坐線路有限,或這些線路的重合站點較多,1個月的刷卡數(shù)據(jù)集中提供信息較少,不利于充分推測線路站點.

圖1 乘客乘坐線路數(shù)目分布Fig.1 Distribution of taken lines

圖2 候選站點數(shù)目分布Fig.2 Distribution of candidate stations’number

(2)標注數(shù)據(jù)集算法性能分析

評價算法準確度具體從準確率(Precision)、召回率(Recall)、F1值(F1-measure)這三個方面進行考量.若算法推測的站點與人工標注的站點相差在兩站之內(nèi),則認為有效推測出了該條刷卡記錄的一個上/下車站點.假設(shè)算法找出的站點個數(shù)為P,其中正確找出的站點個數(shù)為Q,人工標注出的站點個數(shù)為R,于是有Precision=Q/P,Recall=Q/R,F1-measure=2×PR/(P+R).利用標注數(shù)據(jù)對STA算法和HTB算法進行性能分析,結(jié)果如表7所示.

表7 算法性能對比Tab.7 Performance of comparison

由表7可以看出,相比STA算法,HTB算法的準確率和召回率均較高,說明HTB算法的有效性.同時STA方法準確率比召回率高,而HTB算法的召回率比準確率高.這是因為STA算法僅考慮相鄰刷卡記錄進行站點推測,對于連續(xù)兩條相同公交線路乘坐的情況和相鄰刷卡記錄為出租車的情況,STA算法不做站點推測,導致P值較小,準確率相對召回率有所提升.而由于HTB算法的策略是利用歷史出行記錄盡可能對所有乘坐線路的站點進行恢復,這導致有更大的可能性使得每條線路都產(chǎn)生候選站點列表,進而使得P值較大,例如對那些擁有較多個候選站點的線路依然會進行恢復,而不是放棄恢復,造成召回率高于準確率.

5.4 算法運行性能分析

設(shè)置測試數(shù)據(jù)集大小依次為整個數(shù)據(jù)集的25%、50%、75%、100%,分別運行兩種推測算法.圖3展示了兩種站點推測方法在不同大小數(shù)據(jù)集下的運行時間,可以看出算法整體運行時間與數(shù)據(jù)集大小成線性關(guān)系.HTB算法運行時間約為STA算法的3.5倍,但是從之前的分析來看,HTB算法的準確度遠遠高于STA算法,因而時間開銷是可接受的.

圖3 HTB和STA運行時間Fig.3 Running time of HTB and STA

圖4則是HTB算法各個步驟的時間消耗狀況,可以發(fā)現(xiàn)算法1(STA)、算法2和算法3的時間消耗相對較小,算法4占用大部分的運行時間.這是因為HTB算法在出行記錄劃分算法中的時間與刷卡記錄數(shù)目n成線性關(guān)系,時間復雜度為O(n);在尋找乘坐線路及頻繁換乘線路中與出行記錄數(shù)目m成線性關(guān)系,時間復雜度為O(m);而最后的生成候選站點算法需要首先生成線路對,然后在線路對中尋找候選站點并計算權(quán)重,時間復雜度較高.

圖4 HTB算法各步驟運行時間Fig.4 Running time of each procedure in HTB

6 總結(jié)

本文針對公交上下車站點缺失的城市智能交通卡刷卡數(shù)據(jù),對公交站點進行推測,提出了基于時空鄰近性的站點推測方法(STA)以及基于歷史出行記錄的站點推測方法(HTB).STA算法只考慮用鄰近刷卡記錄的乘坐線路之間的空間關(guān)系進行恢復,而HTB還構(gòu)建了出行記錄,結(jié)合每張卡的歷史出行記錄對站點進行細粒度的恢復.實驗表明HTB算法比STA算法大大減少真實刷卡記錄中公交候選上下車站點的推測范圍,提高了推測站點的準確性.

[1]LATHIA N,CAPRA L.How smart is your smartcard?Measuring travel behaviours,perceptions,and incentives[C]//Proceedings of the 13th International Conference on Ubiquitous Computing.ACM,2011:291-300.

[2]LATHIA N,FROEHLICH J,CAPRA L.Mining public transport usage for personalised intelligent transport systems[C]//2010 IEEE 10th International Conference on Data Mining.IEEE,2010:887-892.

[3]BAGCHI M,WHITE P R.The potential of public transport smart card data[J].Transport Policy,2005,12(5): 464-474.

[4]PELLETIER M P,TR′EPANIER M,MORENCY C.Smart card data use in public transit:A literature review[J]. Transportation Research Part C Emerging Technologies,2011,19(4):557-568.

[5]ZHANG F,YUAN N J,WANG Y,et al.Reconstructing individual mobility from smart card transactions:A collaborative space alignment approach[J].Knowledge and Information Systems,2015,44(2):299-323.

[6]TR′EPANIER M,TRANCHANT N,CHAPLEAU R.Individual trip destination estimation in a transit smart card automated fare collection system[J].Journal of Intelligent Transportation Systems Technology Planning& Operations,2007,11(1):1-14.

[7]WANG W,ATTANUCCI J P,WILSON N H M.Bus passenger origin-destination estimation and related analyses using automated data collection systems[J].Journal of Public Transportation,2010,14(4):131-150.

[8]BARRY J,NEWHOUSER R,RAHBEE A,et al.Origin and destination estimation in New York City with automated fare system data[J].Transportation Research Record,2002,1817:183-187.

[9]SONG C,QU Z,BLUMM N,et al.Limits of predictability in human mobility[J].Science,2010,327:1018-1021.

[10]GIANNOTTI F,NANNI M,PEDRESCHI D,et al.Unveiling the complexity of human mobility by querying and mining massive trajectory data[J].The VLDB Journal,2011,20(5):695-719.

[11]LI Z,DING B,HAN J,et al.Mining periodic behaviors for moving objects[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2010:1099-1108.

[12]WANG Y,YUAN N J,LIAN D,et al.Regularity and conformity:Location prediction using heterogeneous mobility data[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM, 2015:1275-1284.

[13]BALAN R K,NGUYEN K X,JIANG L.Real-time trip information service for a large taxi f l eet[C]//Proceedings of the 9th International Conference on Mobile Systems,Applications,and Services.ACM,2011:99-112.

[14]DASH M,KOO K K,HOLLECZEK T,et al.From mobile phone data to transport network–gaining insight about human mobility[C]//IEEE International Conference on Mobile Data Management.IEEE,2015:243-250.

[15]DAI J,YANG B,GUO C,et al.Personalized route recommendation using big trajectory data[C]//IEEE 31st International Conference on Data Engineering.IEEE,2015:543-554.

[16]龍瀛,孫立君,陶遂.基于公共交通智能卡數(shù)據(jù)的城市研究綜述[J].城市規(guī)劃學刊,2015,3:70-77.

[17]LONG Y,THILL J C.Combining smart card data and household travel survey to analyze jobs-housing relationships in Beijing[J].Computers Environment&Urban Systems,2015,53:19-35.

[18]EL-GENEIDY A,GRIMSRUD M,WASFI R,et al.New evidence on walking distances to transit stops:Identifying redundancies and gaps using variable service areas[J].Transportation,2014,41(1):193-210.

[19]DANIELS R,MULLEY C.Explaining walking distance to public transport:The dominance of public transport supply[J].Journal of Transport&Land Use,2011,6(2):5-20.

[20]CUI A.Bus passenger origin-destination matrix estimation using automated data collection systems[D].Cambridge,MA:Massachusetts Institute of Technology,2006.

[21]胡繼華,鄧俊,黃澤.結(jié)合出行鏈的公交IC卡乘客下車站點判斷概率模型[J].交通運輸系統(tǒng)工程與信息,2014,14(2):62-67.

[22]上海市政府數(shù)據(jù)服務(wù)網(wǎng).[DB/OL].[2017-05-20].http://www.datashanghai.gov.cn.

(責任編輯:林磊)

Individual station estimation from smart card transactions

WANG Yi-lin,ZHANG Zhi-gang,JIN Che-qing
(School of Data Science and Engineering,East China Normal University,Shanghai 200062,China)

With the fast development of public transportation network and widespread use of smart card,more and more rich semantic information about human mobility behaviors are hidden in smart card transaction data.However,a great number of current smart cards are initially designed for charging and do not record any detailed information about where and when a passenger gets on or gets of f a bus,which brings out great diffi culties for analyzing,mining transaction data and providing more precise location-based services. This paper presents Space-Time Adjacency algorithm(STA)and Historical Trip Based algorithm(HTB)to estimate the bus station of each card’s transaction records with the aid of integral historical data including complete subway transaction data.Specif i cally, STA does the initial reconstruction work according to the space-time proximity of adjacenttransaction records.Then HTB f i rst cuts the collection of records to form trips that contain explicit trip purposes,then extracts taken lines and transfer lines using historical data,next generates candidate stations for each taken line,and f i nally uses them to recover the transaction records again.Experiments show that the proposed algorithms work well and narrow the range of candidate stations for bus lines,and have good time effi ciency.

smart card;incomplete data;card mining;station estimation

TP391

A

10.3969/j.issn.1000-5641.2017.05.018

1000-5641(2017)05-0201-12

2017-06-30

國家重點研發(fā)計劃重點專項(973)(2016YFB1000905);國家自然科學基金(61370101, 61532021,U1501252,U1401256,61402180)

王藝霖,女,碩士研究生,研究方向為基于位置的服務(wù).E-mail:ylwang@stu.ecnu.edu.cn.

金澈清,男,教授,博士生導師,研究方向為基于位置的服務(wù).E-mail:cqjin@sei.ecnu.edu.cn.