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

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

1 前言

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

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

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

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

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

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

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

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

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

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

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

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

2.1 電子地圖

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

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

2.2 路徑誘導(dǎo)

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

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

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

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

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

2.3 行為模式識(shí)別

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

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

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

3 用戶行為分析

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

3.1 用戶行為理解

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 服務(wù)推薦

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

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

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

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

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

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

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

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

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

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

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

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

參考文獻(xiàn)

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