基于位置信息的用戶行為軌跡分析與應(yīng)用綜述*

陳 康，黃曉宇，王愛寶，陶彩霞，關(guān)迎暉，李 磊

（1.中國電信股份有限公司廣東研究院 廣州510630；2.華南理工大學(xué)經(jīng)濟與貿(mào)易學(xué)院 廣州510006；3.中山大學(xué)軟件研究所 廣州510275；4.中國電信集團公司 北京100032）

1 前言

近年來，隨著以GPS導(dǎo)航儀和智能手機為代表的智能終端的普及與應(yīng)用，人們已經(jīng)能夠以相對低廉的代價獲得大量的用戶實時位置數(shù)據(jù)，如在GPS導(dǎo)航系統(tǒng)的支持下，可以實時獲得汽車駕駛員當(dāng)前所在的經(jīng)、緯度位置信息和行駛方向信息；對于隨身攜帶移動電話的用戶，能以基站定位的方式，估計出該用戶所在的大概區(qū)域。特別地，對于給定的用戶，將其在一組連續(xù)時間點上的位置“串聯(lián)”起來后，就形成了他在這個時間段內(nèi)的行為軌跡數(shù)據(jù)。

在大量用戶位置和行為軌跡數(shù)據(jù)的背后，隱含了豐富的空間結(jié)構(gòu)信息和用戶行為規(guī)律信息，通過對這些信息進行深入的挖掘和利用，不僅有可能發(fā)現(xiàn)個體用戶的日常行為規(guī)律和群體用戶的共性行為特征，甚至還有可能掌握其社交關(guān)系信息，這對智能交通、廣告推薦等應(yīng)用具有非常重要的意義。早在2003年，Rao與Minakakis預(yù)測，如下4類基于用戶位置信息的服務(wù)應(yīng)用蘊藏著巨大的商機[1]：

·用戶空間定位及駕駛的路徑誘導(dǎo)服務(wù)；

·基于用戶位置分析的精準廣告投送服務(wù)；

·基于用戶行為的市場細分及應(yīng)用服務(wù)；

·面向企業(yè)的商業(yè)合作應(yīng)用服務(wù)。

目前，這些預(yù)測大多已成為現(xiàn)實，如美國的Inrix公司采集道路上的汽車行為軌跡信息，通過分析、挖掘為在途駕駛員提供交通信息發(fā)布和路徑誘導(dǎo)服務(wù)，其產(chǎn)品用戶已經(jīng)覆蓋了北美和歐洲的20多個國家；騰訊公司開發(fā)了帶位置服務(wù)功能的即時通信軟件——微信，在14個月內(nèi)即積累了超過2億名注冊用戶。這些應(yīng)用的成功吸引了廣泛的關(guān)注，越來越多的研究人員投入用戶行為軌跡分析的研究領(lǐng)域中。

對于用戶行為軌跡的分析，一般可以總結(jié)為“數(shù)據(jù)采集—位置匹配—分析應(yīng)用”3個步驟，具體技術(shù)架構(gòu)如圖1所示。

在圖1中，用于軌跡分析的數(shù)據(jù)主要來源于車載的GPS定位數(shù)據(jù)和以智能手機為代表的基站定位數(shù)據(jù)（部分智能手機也支持GPS定位，也有可能提供GPS定位數(shù)據(jù)），一般這些數(shù)據(jù)都可以使用四元組<數(shù)據(jù)源ID，時戳，經(jīng)度，緯度>表示；在使用這些數(shù)據(jù)之前，需要把它們匹配到地圖上[2]以關(guān)聯(lián)某些興趣點（point of interest，POI），但由于地圖匹配所需的電子地圖通常難以獲得，因此研究人員對這一步驟做了簡化處理，只是簡單地柵格化，將每個原始的數(shù)據(jù)點映射到柵格中，對用戶行為軌跡的分析和應(yīng)用在完成上述位置匹配過程之后的數(shù)據(jù)上進行[3～5]。

雖然對用戶日常行為軌跡的分析吸引了眾多的研究興趣，然而總結(jié)起來，相關(guān)的工作主要分為兩種類型：其一是傳統(tǒng)的智能交通服務(wù)應(yīng)用，研究所需的數(shù)據(jù)主要來源于由GPS終端和智能手機采集獲得的用戶空間位置信息；其二是對用戶的行為模式識別與社交關(guān)系的發(fā)現(xiàn)，這一工作的開展除了需要用戶的空間位置信息之外，還需要其他的數(shù)據(jù)信息，如用戶的網(wǎng)絡(luò)瀏覽信息、用戶在社交網(wǎng)站上的活動記錄信息等。

2 智能交通應(yīng)用

隨著位置數(shù)據(jù)采集設(shè)備的普及，近年來，在智能交通領(lǐng)域，研究手段也出現(xiàn)了革命性的變化：在早期的研究中，由于數(shù)據(jù)采集與處理的成本過高，數(shù)據(jù)的主要作用在于對已有模型進行檢驗和校正；在最近10年中，隨著采集成本的降低，已經(jīng)可以用非常低廉的價格獲得大量的動態(tài)交通數(shù)據(jù)，以此為基礎(chǔ)，相關(guān)研究者提出了以數(shù)據(jù)為驅(qū)動的智能交通系統(tǒng)[6]（data-driven intelligent transportation system，D2ITS），其核心在于通過數(shù)據(jù)挖掘、機器學(xué)習(xí)等手段，從數(shù)據(jù)中提取交通系統(tǒng)的運行模式，從而研究新的交通應(yīng)用。

2.1 電子地圖

在智能交通的各種研究中，電子地圖是最為底層的數(shù)據(jù)資源，為地圖匹配、用戶興趣點分析以及路徑誘導(dǎo)等各種應(yīng)用提供基礎(chǔ)性的支撐。然而，傳統(tǒng)電子地圖的編制代價非常高昂，需要投入大量的人力和物力進行精確的測量與校正。

為解決這一問題，Cao與Krumm[7]利用了如下事實：用戶駕車經(jīng)過的地方必然有道路的存在。由此提出了一種基于用戶出行軌跡的地圖編制算法，認為車輛在一條道路上行駛的GPS軌跡由該道路上各點的空間位置與一組相互獨立的以0為均值的誤差疊加而成，因此，當(dāng)多條這樣的軌跡合并時，得到的結(jié)果即該道路的實際位置。另一方面，在電子地圖中，車道標(biāo)識是一個很重要的組成部分，參考文獻[8]中研究了一種完全基于用戶假設(shè)軌跡數(shù)據(jù)的算法，他們注意到道路上不同車道的通行速度是有區(qū)別的，而道路上的通行速度可以視作所有車道速度的綜合，因而使用混合高斯分布對同一道路上的通行速度進行描述，進而利用采集到的速度數(shù)據(jù)對模型進行擬合分析，最后獲得的高斯成分個數(shù)即該道路上的車道數(shù)目。

2.2 路徑誘導(dǎo)

對行駛中的車輛進行路徑誘導(dǎo)是智能交通研究中的核心問題之一，其目標(biāo)是為駕駛員尋找“最合適”的道路。眾所周知，Dijkstra算法能在O(n2)的時間內(nèi)找到路網(wǎng)中兩點間的最短路徑，然而對駕駛員而言，除路徑的長短外，交通狀況、駕駛成本等也是影響其對路徑進行選擇的重要因素，所以“最短”的路徑并不等價于“最好”的路徑。

為解決上述問題，需要對所謂的“最合適”的路徑給出可操作的定義。當(dāng)前一個被廣泛接受的定義是：選擇走一條路的車輛越多，這條路的“合適程度”就應(yīng)該越高。以這一假設(shè)為基礎(chǔ)，越來越多的工作轉(zhuǎn)向基于駕駛軌跡的路徑誘導(dǎo)研究。

[9]中提出了一種有別于傳統(tǒng)的最短路徑算法的路徑誘導(dǎo)策略，駕駛員普遍傾向于選擇高等級的道路（等級越高，速度越快），而不同等級的道路又把路網(wǎng)劃分成大小不一的封閉區(qū)域（一般路網(wǎng)的等級越高，區(qū)域內(nèi)的面積越大，反之亦然），由此設(shè)計了一種基于A*搜索的最快路徑啟發(fā)式策略。在出發(fā)端，該策略引導(dǎo)用戶由低等級路網(wǎng)圍成的區(qū)域盡快進入通往目標(biāo)方向的高等級區(qū)域；在目標(biāo)端，則引導(dǎo)用戶盡快由高等級區(qū)域進入包含目標(biāo)地址的低等級區(qū)域。在該算法的設(shè)計中，Gonzalez等人還注意到，路網(wǎng)中存在部分路徑，雖然級別較低，但通行的車輛卻非常多，因此對道路等級的評定方式也做了修改，即道路的等級不僅與其靜態(tài)特性相關(guān)，還與其上通行車輛的數(shù)目和通行速度這些動態(tài)特征相關(guān)，這些特征的取值可以通過對用戶出行軌跡的分析獲得。

參考文獻[9]中的算法能很好地解決中長途旅行（如在兩個城市之間）的路徑誘導(dǎo)問題，然而對于城市內(nèi)的路徑選擇，其效果則差強人意。主要原因在于：在同一城市內(nèi)，各道路的通行與擁堵狀況在整體上已經(jīng)漸趨一致，難以給出明晰的等級劃分，因而該算法的應(yīng)用也受到了限制。對此，T-drive[10]提供了另一種解決方案：以城市內(nèi)出租車的駕駛軌跡數(shù)據(jù)為基礎(chǔ)進行路徑誘導(dǎo)，由于出租車的數(shù)量眾多，活動范圍廣泛，而且司機的經(jīng)驗也非常豐富，因此可以認為，對于城市內(nèi)的任意兩點，連接這兩點的出租車行駛軌跡接近最佳路線。

除了指導(dǎo)人們在駕車出行過程中選擇合適的路線外，對用戶出行軌跡的分析還有助于“綠色出行”的實現(xiàn)。這里的“綠色”指鼓勵人們盡可能使用公共交通工具，從而減少碳排放量，減輕道路的交通擁堵狀況。為減少用戶在使用公共交通工具出行過程中的不便，參考文獻[11]提出基于出租車的歷史行駛軌跡數(shù)據(jù)的公交線路規(guī)劃算法，該算法使用出租車的起止位置表示它的每一條行駛軌跡，并對這些軌跡進行層次聚類以生成若干軌跡簇，這些簇的中心軌跡即公交線路的規(guī)劃結(jié)果。與此相類似，參考文獻[5]中也研究了根據(jù)大規(guī)模的出租車駕駛軌跡進行夜間公交線路規(guī)劃的應(yīng)用。

2.3 行為模式識別

在城市居民的日常出行中，一條出行的行為軌跡可能包含多種不同的行為模式，如步行、公共汽車接駁以及地鐵換乘等，參考文獻[12]中提出了對用戶出行行為模式識別的研究，對比了條件隨機場、支持向量機、貝葉斯網(wǎng)絡(luò)與決策樹在這一問題上的表現(xiàn)，令人吃驚的是，在這些工具中，決策樹取得了最好的結(jié)果。然而，對于這一結(jié)果，還需結(jié)合數(shù)據(jù)的實際分布因素來考慮：對于大多數(shù)用戶，在他/她的一次出行行為中，絕大多數(shù)時間都是在交通工具上度過的，而步行、騎自行車接駁公共交通工具等行為在總體數(shù)據(jù)中僅占了非常小的比例，對分類算法而言，這是一個類別不平衡的問題[13]。在這種情況下，分類器僅需簡單地把所有結(jié)果都判別為優(yōu)勢類別，便能獲得很高的準確率，所以簡單地以分類結(jié)果的準確率來度量分類器的好壞是不合適的。

Stenneth等人對參考文獻[12]的結(jié)果做了改進，當(dāng)用戶使用不同的公交工具時，公交服務(wù)設(shè)施可以作為識別其行為模式的重要啟發(fā)信息，因此公交站、地鐵線路等的位置分布也可以用于輔助計算[14]，結(jié)果與參考文獻[12]類似，以決策樹為基礎(chǔ)的隨機森林（random forest）算法獲得了最好的表現(xiàn)。

此外，對用戶交通行為模式的研究還衍生了非常豐富的其他應(yīng)用，如Kjargaard等人[15]研究了群體用戶的聚集行為，他們的工作以智能手機采集的數(shù)據(jù)為基礎(chǔ)，匯集從智能手機獲得的用戶行為加速度數(shù)據(jù)、移動方向數(shù)據(jù)以及信號強度數(shù)據(jù)，通過層次聚類生成用戶的群體聚集與移動信息；Zhang和Li[3]、Ge和Xiong[4]等人則研究了基于出租車歷史行為軌跡的駕駛員異常行為探測算法，對于給定的兩點（起點和終點），多數(shù)人選擇的路徑就是“正?！钡穆窂?，因此若有某些駕駛軌跡明顯背離了這些正常路徑，則這些行為屬于異常行為。

3 用戶行為分析

除了智能交通應(yīng)用，基于位置信息的行為分析也已滲入用戶的日常生活中，從個人的活動模式到群體的社交關(guān)系，都有可能從用戶的歷史活動軌跡記錄中提取獲得，以此為依據(jù)，位置服務(wù)的提供者又能進一步改進他們的產(chǎn)品，為用戶提供更為個性化的服務(wù)。

3.1 用戶行為理解

對用戶行為的意圖分析是用戶軌跡分析的一個重要研究內(nèi)容，其目的在于從用戶的歷史行為軌跡中挖掘和解釋用戶的日常行為規(guī)律。在對這一問題的研究中，聚類分析是最為常用的技術(shù)手段，然而在另一方面，由于缺乏必要的驗證信息，對聚類結(jié)果的解讀通常需要結(jié)合特定的時空上下文進行。如Kirmse等人對用戶日常行為特點的研究[16]，使用meanshift聚類根據(jù)用戶的歷史行為軌跡數(shù)據(jù)生成了其日常駐留區(qū)域，并結(jié)合時間特點給出了結(jié)果的語義解釋（如用戶在白天駐留時間最長的地點是工作場所，晚上駐留時間最長的地點是家里）；而在Ying等人[17]的研究中，則充分利用空間信息輔助對結(jié)果的解讀：首先把聚類獲得的用戶日常駐留點與其周邊的興趣點（如公園、學(xué)校、銀行、酒店等）相關(guān)聯(lián)，進而根據(jù)用戶的出行軌跡把這些駐留點“串聯(lián)”起來，如“出門—學(xué)?！獑挝弧掳唷钡龋源藢崿F(xiàn)對用戶出行軌跡的語義解讀。

也有部分研究者嘗試直接根據(jù)用戶的行為軌跡數(shù)據(jù)建立其統(tǒng)計生成模型，主要做法是引入文本處理的相關(guān)技術(shù)。首先在軌跡數(shù)據(jù)與文本數(shù)據(jù)之間建立如下映射關(guān)系：

·軌跡數(shù)據(jù)中的一個區(qū)域（如一個POI或一條街道）對應(yīng)文章組成中的一個單詞，用戶經(jīng)過一個區(qū)域的次數(shù)相當(dāng)于單詞在文章中出現(xiàn)的次數(shù)；

·一條行為軌跡對應(yīng)一篇文章；

·一組軌跡構(gòu)成的集合對應(yīng)一個文本集合。

在以上對應(yīng)關(guān)系下，Zheng與Ni把對用戶出行行為的理解映射為文本處理中的主題抽取[18]，進而構(gòu)造了LDA模型[19]的一個變體，以解釋用戶出行軌跡的生成過程；與此相類似的還有Yuan等人的工作[20]，把LDA聚類的結(jié)果與城市中的服務(wù)設(shè)施位置相結(jié)合，從而實現(xiàn)基于用戶行為軌跡的城市實際功能的分區(qū)識別。

3.2 社交關(guān)系理解

眾所周知，在社交網(wǎng)絡(luò)中，存在著名的“六度分隔”理論，即任意兩個用戶之間的通信最多只需由6個順次認識的用戶進行信息交換即可實現(xiàn)，而這一理論的正確性也已被Jure與Horvitz使用微軟公司的3 000多萬名MSN用戶的歷史通信記錄所驗證[21]。此外，參考文獻[22]中對多個社交網(wǎng)絡(luò)數(shù)據(jù)集的分析結(jié)果還指出，在社交網(wǎng)絡(luò)中，隨著網(wǎng)絡(luò)半徑的擴大，人與人之間的交互距離反而縮小；另一方面，對于社交關(guān)系時空分布的特點，當(dāng)前還沒有定論。近年來，隨著社交網(wǎng)絡(luò)與位置服務(wù)的盛行，對用戶的物理位置與其社交聯(lián)系兩者之間的關(guān)聯(lián)性分析也激發(fā)起了廣泛的興趣。

在基于位置信息的用戶關(guān)系分析中，Crandalla[23]等人做了開創(chuàng)性的工作。以照片分享網(wǎng)站Flickr上的數(shù)據(jù)為研究對象，由于用戶在向Flickr上傳照片的同時也留下了時間信息，此外，在照片上載過程中有部分用戶提交了他所在的位置信息，根據(jù)這些記錄可以獲得用戶的時空位置信息；另一方面，F(xiàn)lickr還提供了社交網(wǎng)絡(luò)服務(wù)，由此，又可以確定用戶在網(wǎng)絡(luò)上的社交關(guān)系信息。以這些數(shù)據(jù)為依據(jù)，Crandalla等人研究了用戶在物理空間中的行為軌跡與其社交關(guān)系之間的聯(lián)系，在一定的簡化假設(shè)下，證明了如下結(jié)論：若兩位用戶在連續(xù)k天內(nèi)訪問了相同的區(qū)域，則他們在社交網(wǎng)絡(luò)中存在朋友關(guān)系的概率可以寫為，c1和c2是常數(shù)因子。

由這一結(jié)果可知，當(dāng)兩個人連續(xù)出現(xiàn)在相同的場合時，他們間彼此認識的概率將以共現(xiàn)的次數(shù)呈指數(shù)增長。這一發(fā)現(xiàn)為探索人群中的社會關(guān)系提供了新的手段：對所關(guān)心的目標(biāo)對象，只需簡單地比較他們的活動軌跡在一定時間周期內(nèi)的重合次數(shù)，即可斷言其是否存在朋友關(guān)系。

與參考文獻[23]相反，Cho及其合作者則研究了用戶間的社交關(guān)系對他們出行活動的影響[24]。分析了位置服務(wù)社交網(wǎng)站Gowalla與Brightkite的用戶數(shù)據(jù)以及由歐洲某電信運營商提供的用戶定位和聯(lián)系數(shù)據(jù)。結(jié)果顯示，一方面，兩個用戶成為朋友的概率隨物理距離的增加而降低；另一方面，當(dāng)用戶做旅行規(guī)劃時，他的社交關(guān)系對目標(biāo)地點的選擇存在一定的影響：對于短途旅游，用戶對目標(biāo)地點的選擇一般獨立于其社交關(guān)系；對于長途旅游，目標(biāo)地點一般會被優(yōu)先考慮在有朋友居住的地方。

與參考文獻[24]相類似的工作還有Ye、Yin和Lee的研究[25]，在這一工作中，他們分析了位置服務(wù)社交網(wǎng)站Foursquare的用戶數(shù)據(jù)，結(jié)果顯示，若兩個用戶間存在社交聯(lián)系，則在相同的地理位置共同出現(xiàn)的概率要遠遠高于他們間沒有社交關(guān)系時的概率，即對于用戶A和B，記他們?nèi)ミ^的地方集合分別為，則在A、B兩者是朋友時，r的取值遠大于兩者不是朋友時的取值。

容易看出，參考文獻[24,25]的發(fā)現(xiàn)對旅游行業(yè)的廣告推薦具有非常重要的意義，由于用戶在規(guī)劃長途旅游時會傾向于選擇有朋友或朋友去過的地方，因此基于用戶社交網(wǎng)絡(luò)聯(lián)系的目標(biāo)地點推薦有可能會獲得良好的效果。

3.3 服務(wù)推薦

推薦服務(wù)是在線社交系統(tǒng)與內(nèi)容服務(wù)系統(tǒng)的核心功能之一，常見的推薦內(nèi)容包括廣告、電影、音樂、朋友關(guān)系以及旅游線路等，為能向用戶提供個性化的推薦服務(wù)，近年來，有大量的工作投入對用戶行為特點與待推薦目標(biāo)兩者之間聯(lián)系的分析之中。

在社交網(wǎng)絡(luò)服務(wù)中，一個核心的應(yīng)用是朋友關(guān)系的發(fā)現(xiàn)和推薦，參考文獻[23]的結(jié)論為此提供了支持，如Ling等人的工作[26]可以視為對參考文獻[23]的直接應(yīng)用，在這一工作中，Ling等人設(shè)計了向量化的數(shù)據(jù)結(jié)構(gòu)來表示用戶在空間上的歷史訪問記錄和共同出現(xiàn)記錄，進而使用歐氏距離度量用戶間的熟悉程度，并在社交網(wǎng)絡(luò)中“相熟”用戶間進行朋友推薦。

另一方面，在參考文獻[23,26]等的工作中，用戶間“相似性”的計算依據(jù)是用戶與物理空間中特定參照物間的相對位置關(guān)系，這一計算方式雖然直觀而簡單，卻不能直接應(yīng)用于遠距離用戶間的相似度計算。事實上，當(dāng)兩個用戶間的物理距離充分大時，容易猜測，他們多次在同一區(qū)域中共同出現(xiàn)的概率將趨向于0，但在現(xiàn)實中，即使在這種極端的情況下，有很多用戶仍然在社交網(wǎng)絡(luò)中結(jié)為好友。為解決這一問題，Xiao等人[27]的做法是把原始的空間位置抽象為更高一級的概念，使用位置空間的語義代替具體的物理地址進行相似度計算，在這一計算模式下，可以認為，當(dāng)兩個用戶的行為軌跡語義相近時，則他們間有可能存在朋友關(guān)系。例如，若有兩位用戶的出行軌跡都是“購物中心—餐館—電影院”，則認為他們是相似的，因而可以在他們之間互相做朋友關(guān)系并推薦位置服務(wù)。

除了發(fā)現(xiàn)新的社交關(guān)系外，協(xié)助用戶強化現(xiàn)有的聯(lián)系也是社交網(wǎng)絡(luò)平臺所關(guān)注的焦點之一。Braga等研究人員提出了一種通過分析用戶的線下行為來促進其線上交互的策略[28]，以用戶的行為軌跡為研究對象，把最小有界矩形（minimum bounding rectangle）應(yīng)用于好友用戶的行為軌跡，從中提取這些用戶的日常公共活動區(qū)域，進而在社交網(wǎng)絡(luò)上為他們共享這些結(jié)果，以此促進彼此的線上互動。

旅游推薦是用戶行為軌跡分析的另一個重要應(yīng)用。由于社交關(guān)系對用戶旅游地點的選擇起著重要的影響，因此可以認為，這一結(jié)論從側(cè)面上證實了病毒營銷策略在旅游廣告推薦中的有效性，此外預(yù)期它還將深刻地影響未來旅游廣告的推薦行為，社交關(guān)系將成為廣告推薦的主要依據(jù)。事實上，在Ye等人[25]的研究中，已經(jīng)對此做了初步的嘗試。

4 結(jié)束語

對于基于用戶行為軌跡的分析應(yīng)用，一方面，在內(nèi)容上，智能交通領(lǐng)域的主要焦點仍然聚焦在對駕駛路徑誘導(dǎo)、交通狀態(tài)判斷等傳統(tǒng)問題的研究上；相對而言，基于互聯(lián)網(wǎng)的應(yīng)用研究則更為活躍，特別地，隨著社交網(wǎng)絡(luò)因素的引入，相關(guān)工作已經(jīng)展現(xiàn)了樂觀的前景。然而，需要指出的是，作為一個新興的研究方向，有眾多的問題有待進一步探討，其中最為核心的一個問題是如何針對特定的商業(yè)需求，從用戶的歷史軌跡中提取深層次的關(guān)聯(lián)行為，這也是支持和推動這一方向深入發(fā)展的動力。另一方面，在手段上，“大數(shù)據(jù)”已經(jīng)成為對用戶行為軌跡分析的主流方向。

對于智能交通系統(tǒng)的研究，近年來，隨著D2ITS的興起，“大數(shù)據(jù)”已經(jīng)成為這一領(lǐng)域研究中必不可少的組成部分。這是由于在動態(tài)交通數(shù)據(jù)采集系統(tǒng)中，隨著采集手段的完善，需要處理的數(shù)據(jù)規(guī)模隨之高速增長。這里僅以國內(nèi)某省級公路交通數(shù)據(jù)中心為例進行說明。

浮動車數(shù)據(jù)是該數(shù)據(jù)中心的主要數(shù)據(jù)資源之一，目前接入中心內(nèi)的浮動車數(shù)目已經(jīng)接近100 000輛，平均每車以15 s/次的頻率向數(shù)據(jù)中心發(fā)送實時交通狀態(tài)信息（每條信息包括記錄編號、車輛識別號、車輛位置的經(jīng)緯度、車行方向、瞬時速度以及時戳），據(jù)此估算，每天該數(shù)據(jù)中心將新增約17億條記錄，以每條記錄占30 byte計算，則每天該數(shù)據(jù)中心新增約48 GB的浮動車數(shù)據(jù)。

在其他各項應(yīng)用中，“大數(shù)據(jù)”依然占有十分顯著的位置。如Crandalla等人[23]為分析用戶的物理距離與社交關(guān)系的聯(lián)系，使用了Flickr上的3 800萬張照片記錄；Cho及其合作者[24]使用了位置服務(wù)社交網(wǎng)站Gowalla的640萬條用戶登錄數(shù)據(jù)和發(fā)生在196 591個用戶間的950 327對用戶關(guān)系數(shù)據(jù)、網(wǎng)站Brightkite的450萬條用戶登錄數(shù)據(jù)和發(fā)生在58 228個用戶間的950 327對用戶關(guān)系數(shù)據(jù)以及由歐洲電信運營商提供的發(fā)生在200萬用戶間的4.5億次通話聯(lián)系數(shù)據(jù)。

之所以需要如此規(guī)模龐大的數(shù)據(jù)，原因之一在于數(shù)據(jù)獲取的便利性，對于車輛的GPS軌跡數(shù)據(jù)，相關(guān)的運營商處有完整的記錄；對于用戶的社交網(wǎng)絡(luò)數(shù)據(jù)和其他定位數(shù)據(jù)，由于當(dāng)前主流的位置服務(wù)和社交應(yīng)用平臺 （如Facebook、Twitter以及Flickr等）已經(jīng)積累了大量的用戶數(shù)據(jù)，通過使用網(wǎng)絡(luò)爬蟲等工具，研究人員可以較為方便地抓取獲得這些數(shù)據(jù)。但根本的原因還是數(shù)據(jù)的稀疏性。以Cho[24]的工作為例進行說明：容易理解，雖然參考文獻[24]中所使用的3個數(shù)據(jù)集都包含了大規(guī)模的用戶活動記錄，然而在任一數(shù)據(jù)集中，相對于用戶總量的規(guī)模，發(fā)生在用戶間的關(guān)系（無論是社交關(guān)系，還是在物理空間上的接近關(guān)系）仍然是極為稀疏的，試圖在這兩種關(guān)系之間建立概率聯(lián)系，顯然會導(dǎo)致一個更為稀疏的結(jié)果，為了克服這一問題，研究者只能通過提升原始數(shù)據(jù)的規(guī)模以獲得更多的支持。

在“大數(shù)據(jù)”的背景下，對高效快速的數(shù)據(jù)分析處理算法的研究，已成為用戶行為軌跡的分析與應(yīng)用研究的核心內(nèi)容之一。參考文獻[29]中提出了一個著名的觀點：“更多的數(shù)據(jù)勝過更聰明的算法”，這一論斷在現(xiàn)有的工作中已經(jīng)得到了充分的證明。事實上，在現(xiàn)有的對用戶行為軌跡的研究工作中，大多強有力的結(jié)果都建立在高度簡化的假設(shè)以及對現(xiàn)有數(shù)據(jù)的統(tǒng)計、分析和擬合之上[23,24]；也有其他工作是對某些成熟高效的機器學(xué)習(xí)算法的應(yīng)用，如決 策 樹[12,14]、mean shift聚 類[16]等。由此，在這一研究領(lǐng)域中，對現(xiàn)有算法和模型的合理選擇與高效實現(xiàn)，也許比新型算法的設(shè)計更為重要。

參考文獻

1 Minakakis R.Evolution of mobile location-based services.Communication of the ACM,2003,46(12)

2 Quddus M A,Ochieng W Y,Noland R B.Current mapmatching algorithms for transport applications:state-of-the art and future research directions.Transportation Research Part C,2007(15):312～328

3 Ge Y,Xiong H,Liu C,et al.A taxi driving fraud detection system.Proceedings of the 11th IEEE International Conference on Data Mining(ICDM'11),Vancouver,Canada,2011:181～190

4 Zhang D Q,Li N,Zhou Z H,et al.iBAT:detecting anomalous taxi trajectories from GPS traces.Proceedings of the 13th ACM International Conference on Ubiquitous Computing(UbiComp’11),Beijing,China,2011:99～108

5 Chen C,Zhang D Q,Castro P S,et al.Real-time detection of anomalous taxi trajectories from GPS traces.Proceedings of the 8th Annual International ICST Conference on Mobile and Ubiquitous System(MobiQuitous’11),Copenhagen,Denmark,2011:63～74

6 Zhang J P,Wang F Y,Wang K F,et al.Data-driven intelligent transportation systems:a survey.IEEE Transations on Intelligent Transportation Systems,2011,12(4)

7 Cao L,Krumm J.From GPS traces to a routable road map.17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems(ACM SIGSPATIAL GIS 2009),Seattle,WA,2009:3～12

8 Chen Y H,Krumm J.Probabilistic modeling of traffic lanes from GPS traces.18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems(ACM SIGSPATIAL GIS 2010),San Jose,CA,USA,2010

9 Gonzalez H,Han J W,Li X L,et al.Adaptive fastest path computation on a road network:a traffic mining approach.VLDB 2007,Vienna,Austria,2007

10 Yuan J,Zheng Y,Zhang C Y,et al.T-drive:driving directions based on taxi trajectories.Proceedings of ACM SIGSPATIAL 2010,New York,USA,2010

11 Bastani F.A greener transportation mode:flexible routes discovery from GPS trajectory data.GIS 2011,San Jose,California,USA,2011

12 Zheng Y,Liu L,Wang L H,et al.Learning transportation mode from raw GPS data for geographic applications on the web.Proceedings of International Conference on World Wild Web(WWW 2008),Beijing,China,2008

13 He H B,Garcia E A.Learning from imbalanced data.IEEE Transactions on Knowledge and Data Engineering,2009,21(9)

14 Leon Stenneth,Ouri Wolfson,Philip S Yu,et al.Transportation mode detection using mobile phones and GIS information.GIS 2010,San Jose,CA,USA,2010

15 Mikkel Baun Kjargaard,Martin Wirz,Daniel Roggen,et al.Detecting pedestrian flocks by fusion of multi-modal sensors in mobile phones.UbiComp 2012,Pittsburgh,Pennsylvania,United States,2012

16 PabloBellver A K.Extracting patterns from location history.GIS 2011,San Jose,California,USA,2011

17 Ying J C,Lee W C,Weng T C,et al.Semantic trajectory mining for location prediction.GIS 2011,San Jose,California,USA,2011

18 Zheng J C,Lionel M Ni.An unsupervised framework for sensing individual and cluster behavior patterns from human mobile data.UbiComp 2012,Pittsburgh,Pennsylvania,United States,2012

19 David M,Andrew Y,Michael I.Latent dirichlet allocation.Journal of Machine Learning Research 3(4-5):993～1022

20 Yuan J,Zheng Y,Xie X.Discovering regions of different functions in a city using human mobility and POIs.KDD 2012,Beijing,China,2012

21 Leskovec J,Horvitz E.Planetary-scale views on a large instant-messaging network.Proceedings of the 17th International Conference on World Wide Web,New York,USA,2008

22 Leskovec J,Kleinberg J,Faloutsos C.Graphs over time:densification laws,shrinking diameters and possible explanations.KDD 2005,Chicago,IL,USA,2005

23 David J Crandalla,Backstromb L,Cosleyc D,et al.Inferring social ties from geographic coincidences.Proceedings of the National Academy of Sciences of the United States of America,2010

24 Cho E,Myers S A,Leskovec J.Friendship and mobility:user movement in location-based social networks.KDD 2011,San Diego,CA,USA,2011

25 Xiao X Y,Zheng Y,Luo Q,et al.Finding similar users using category-based location history.GIS 2010,San Jose,CA,2010

26 Huy Pham,Ling Hu,Cyrus Shahabi.Towards integrating real-world spatiotemporal data with social networks.GIS 2011,San Jose,California,USA,2011

27 Ye M,Yin P F,Wang-ChienLee.Location recommendation for location-based social networks.GIS 2010,San Jose,CA,USA,2010

28 Braga R B.A trajectory correlation algorithm based on users’daily routines.GIS 2011,San Jose,California,USA,2011

29 A few useful things to know about machine learning.Communications of the ACM,2012,55(10):78～87