王藝霖,章志剛,金澈清

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

智能交通刷卡記錄中的公交站點(diǎn)恢復(fù)方法

王藝霖,章志剛,金澈清

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

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

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

0 引言

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

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

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

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

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

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

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

1 相關(guān)工作

本文工作主要與以下研究領(lǐng)域相關(guān).一個(gè)研究領(lǐng)域?yàn)槔枚喾N軌跡數(shù)據(jù)發(fā)現(xiàn)人群移動(dòng)模式及規(guī)律,進(jìn)行路線發(fā)現(xiàn)或推薦等;另一個(gè)研究領(lǐng)域?yàn)橹悄芙煌〝?shù)據(jù)的恢復(fù)與挖掘工作.

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

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

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

2 問題描述

在本節(jié)中,主要進(jìn)行數(shù)據(jù)準(zhǔn)備及問題定義.具體地,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號線,共計(jì)14條線,出租車指可以使用上海智能交通卡消費(fèi)的城市出租車.各種刷卡記錄類型及數(shù)量如表1所示.

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

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

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

2.2 問題定義

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

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

3 基于刷卡記錄時(shí)空鄰近性的站點(diǎn)推測

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

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

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

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

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

4 基于歷史出行記錄的站點(diǎn)推測

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

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

4.1 出行記錄劃分

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 實(shí)驗(yàn)

5.1 實(shí)驗(yàn)數(shù)據(jù)集

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

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

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

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

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

5.3 實(shí)驗(yàn)效果分析

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

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

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

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

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

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

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

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

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

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

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

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

5.4 算法運(yùn)行性能分析

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

圖3 HTB和STA運(yùn)行時(shí)間Fig.3 Running time of HTB and STA

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

圖4 HTB算法各步驟運(yùn)行時(shí)間Fig.4 Running time of each procedure in HTB

6 總結(jié)

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

[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ī)劃學(xué)刊,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卡乘客下車站點(diǎn)判斷概率模型[J].交通運(yùn)輸系統(tǒng)工程與信息,2014,14(2):62-67.

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

(責(zé)任編輯:林磊)

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

國家重點(diǎn)研發(fā)計(jì)劃重點(diǎn)專項(xiàng)(973)(2016YFB1000905);國家自然科學(xué)基金(61370101, 61532021,U1501252,U1401256,61402180)

王藝霖,女,碩士研究生,研究方向?yàn)榛谖恢玫姆?wù).E-mail:ylwang@stu.ecnu.edu.cn.

金澈清,男,教授,博士生導(dǎo)師,研究方向?yàn)榛谖恢玫姆?wù).E-mail:cqjin@sei.ecnu.edu.cn.