一般我們?cè)谧鰯?shù)據(jù)挖掘過程中地理位置算是一個(gè)特別重要的特征,，廣泛應(yīng)用于O2O的很多場(chǎng)景。但做的事情都相對(duì)來說比較簡(jiǎn)單，LBS的網(wǎng)格位置推相應(yīng)的內(nèi)容,。原來我們基于地理位置拿了不少數(shù)據(jù)，也做了一些模型,，主要是一些醫(yī)院位置,、商場(chǎng)位置、公交地鐵位置等來給附近的人推服務(wù),。

不同定位比較：

在當(dāng)前眾多的無線定位技術(shù)中,，GPS 以其覆蓋范圍廣、定位精度高,、定位時(shí)間短和定位依賴性小等優(yōu)勢(shì)逐漸在人們的日常生活中變得普及起來（見表 1）,。各種車載 GPS、手持GPS 和 GPS 智能手機(jī)的相繼問世也為人們提供了更加便捷的位置獲取和軌跡記錄方式,。作為用戶經(jīng)歷的載體,，這些軌跡數(shù)據(jù)在各種應(yīng)用中發(fā)揮著重要的作用，并幫助人們來理解個(gè)人行為和社會(huì)規(guī)律,。從數(shù)據(jù)源來看,，當(dāng)前的研究工作可分為基于個(gè)人軌跡數(shù)據(jù)的理解和基于多人軌跡數(shù)據(jù)的理解兩個(gè)方向。

場(chǎng)景：

用戶歷史軌跡中出現(xiàn)的頻繁模式反映了個(gè)人的生活習(xí)慣和行為規(guī)律,。如果可以很好的從軌跡中理解到這些知識(shí),，服務(wù)提供商將可以為用戶提供更深入、更個(gè)性化的位置服務(wù),。而要從軌跡中挖掘這些頻繁模式,，首先要面臨的困難就是如何對(duì)個(gè)人的歷史軌跡建模。

如圖 1 所示,，一條 GPS 軌跡通常由一系列帶有時(shí)間戳的坐標(biāo)點(diǎn)組成,。每個(gè)坐標(biāo)點(diǎn)包含了經(jīng)度、緯度和海拔高度等基本信息,。一個(gè)人在一段時(shí)間內(nèi)的活動(dòng)就可記錄為這樣一條連續(xù)的軌跡,。在這條軌跡中,，我們可以通過算法檢測(cè)出一些用戶停留過的地方。這個(gè)停留點(diǎn)并不是指速度為零的點(diǎn),，而是由一組實(shí)際的 GPS 點(diǎn)構(gòu)成,，如圖 1 中 p3, p4, p5 和 p6構(gòu)成了一個(gè)停留點(diǎn) s。它表示用戶在某個(gè)區(qū)域內(nèi)滯留的時(shí)間超過了一定的時(shí)間范圍,。與其他 GPS 點(diǎn)相比,，這些停留點(diǎn)含有更重要的語義信息，如用戶去過的餐館和電影院等,?；谶@些停留點(diǎn)，一個(gè)用戶的歷史軌跡就可以表達(dá)為一個(gè)停留點(diǎn)序列,，如

,。這個(gè)序列抓住了用戶行為的重點(diǎn)，同時(shí)也大大減輕了數(shù)據(jù)處理量,。

圖 1. 一條 GPS 軌跡樣例

——

由于用戶多次訪問同一地點(diǎn)所產(chǎn)生的停留點(diǎn)并不完全一致（坐標(biāo)會(huì)有偏差）,，直接對(duì)停留點(diǎn)進(jìn)行比較并不可行。因此,，我們需要對(duì)從軌跡中提取出來的停留點(diǎn)進(jìn)行聚類,。這樣相近的停留點(diǎn)就會(huì)被分配到同一個(gè)聚類中。此后,，我們?cè)儆酶鱾€(gè)停留點(diǎn)所歸屬的聚類來替換這個(gè)停留點(diǎn),，將停留點(diǎn)序列進(jìn)一步轉(zhuǎn)化為聚類的序列。這樣用戶在不同時(shí)間段的歷史軌跡就可比了,。

有了用戶歷史軌跡的模型,，我們可以用多種算法（如 FP-growth,、Closet+等）來挖掘這個(gè)數(shù)據(jù)中的頻繁項(xiàng)集,。如用戶 A 經(jīng)常在周末早上去中關(guān)村、用戶 A 經(jīng)常在周五晚上去超市等,。進(jìn)一步,，這些頻繁模式，可以相互組合和連接,，從而發(fā)現(xiàn)一些表征了用戶生活,、行為規(guī)律的順序模式（sequential pattern）。比如,，通常用戶 A 在周末早上會(huì)去中關(guān)村看電影,，然后下午去西單買東西。當(dāng)然,，這些學(xué)習(xí)到的模式將受到隱私保護(hù),，并只為用戶個(gè)人所用,。

在挖掘有意思的地點(diǎn)和經(jīng)典旅行線路時(shí)，首先就要對(duì)不同用戶的軌跡數(shù)據(jù)建模,。如圖2所示,，我們首先從每個(gè)用戶的每條線路中提取出停留點(diǎn)（在圖中表示為綠色小點(diǎn)），并把它們放在一個(gè)集合中,。然后,，利用一種基于密度的聚類算法，我們對(duì)這個(gè)停留點(diǎn)集合進(jìn)行層次化聚類,，在不同的地理尺度上,，將相近的停留點(diǎn)劃分到同一個(gè)聚類（圖中灰色節(jié)點(diǎn)，如 等）,。這樣我們可以得到一個(gè)如圖右半部分所示的一個(gè)層次樹,。樹中的節(jié)點(diǎn)代表不同的停留點(diǎn)聚類，而不同層次表示不同的地理空間尺度,。層次越深,，粒度越細(xì)，代表的地理空間也越小,。隨后,，將不同用戶的軌跡映射到這棵樹的各個(gè)層次，就可以將不同的聚類連接起來,，從而得到不同的圖模型（如圖 2左半部分所示）,。

圖 2. 基于層次圖模型的多用戶軌跡聚合

——

正如前面提到過的，軌跡隱含了人的行為和喜好,。因此,，人們?cè)诘乩砜臻g移動(dòng)的相似性，也在一定程度上反映了不同人之間品味和愛好的相似性,。這里,，我們首先按照如圖 3 所示的方式用不同的層次圖來建模每個(gè)用戶的歷史軌跡，然后成對(duì)地比較圖和圖之間的相似性,。

與之前提到過的大眾數(shù)據(jù)建模方法一致,，我們?nèi)匀焕脤哟位垲惖乃枷雽⑺杏脩舻耐Ａ酎c(diǎn)轉(zhuǎn)化為一個(gè)公共的層次樹（圖3 中間的部分），樹中的各個(gè)節(jié)點(diǎn)（停留點(diǎn)聚類）表示不同尺度和粒度的地點(diǎn),。此后,，將每個(gè)用戶的線路分別導(dǎo)入這個(gè)公共的框架，便可得到用戶各自的層次圖（圖3 的左右兩個(gè)部分分別表示用戶 1 和 2 的層次圖）,。

在通過匹配兩個(gè)層次圖來計(jì)算用戶相似性的時(shí)候,，我們考慮以下兩點(diǎn)因素：

1） 層次。兩個(gè)人的相似性,，可表示為兩個(gè)層次圖中各個(gè)對(duì)應(yīng)層次上的圖的相似性的加權(quán)和,。這里的權(quán)重就是由層次的深度來決定,。由于較深的層次具有較細(xì)的空間粒度和尺度，兩個(gè)用戶在越深的層次上的圖越相似,，則表明他們的活動(dòng)軌跡越相似,。因此，深層次的匹配結(jié)果應(yīng)被賦予較大的權(quán)重,。比如,，兩個(gè)人都在中國(guó)就不如兩個(gè)人都在北京市相似。如果能發(fā)現(xiàn)兩個(gè)人在代表學(xué)校和景點(diǎn)這種更細(xì)粒度的層次上仍有重疊,，則說明這兩個(gè)人更相似,。

2） 相似序列的長(zhǎng)度。同一圖層上兩幅圖的相似性,，可表示為這兩個(gè)圖共享序列的相似性的和,。而序列的相似性，又取決于序列的長(zhǎng)度,。因此,，用戶共享的序列越多，序列的長(zhǎng)度越長(zhǎng),，則這兩個(gè)圖的相似性越大,。如 A、B 和 C 三個(gè)用戶,，A 和 B 共同走過了一個(gè)長(zhǎng)度為 2 的序列 ,，而 A 和 C 兩個(gè)共同走過一個(gè)長(zhǎng)度為 3 的序列 。顯然,，與 B 相比,，用戶 C 更加跟 A 相似。

圖 3. 利用層次圖來比較用戶的相似性

前面介紹的利用大規(guī)模軌跡數(shù)據(jù)實(shí)現(xiàn)大眾化旅行推薦可找出一些公認(rèn)的熱門景點(diǎn)和經(jīng)典旅行線路,。但實(shí)際上不同的用戶有不同的喜好,，在每個(gè)人的心幕中各種景點(diǎn)的排名也不一樣。比如,，喜歡自然風(fēng)景的用戶可能對(duì)故宮這樣的歷史古跡并不是特別感興趣,；喜歡美食的游客也可能會(huì)更加關(guān)注哪些小吃聚集的街道。因此,，針對(duì)個(gè)人的喜好來做個(gè)性化的推薦才是更人性化、更有效的位置服務(wù),。

我們?cè)O(shè)計(jì)的基于軌跡的個(gè)性化朋友和地點(diǎn)推薦包含以下三步：

1） 利用用戶的歷史軌跡計(jì)算出用戶之間的相似性（參見上一節(jié)描述的方法）,，為某個(gè)用戶找出最相似的 n 個(gè)人作為潛在的朋友，完成個(gè)性化朋友推薦,。也許他們?cè)诂F(xiàn)實(shí)生活中多次插肩而過,，卻從來沒有認(rèn)識(shí)的機(jī)會(huì),。由于他們具有相同的興趣愛好，因此,，當(dāng)在論壇中發(fā)起一些活動(dòng)的時(shí)候（如自駕游和登山等）,，用戶能更加精準(zhǔn)地找到一些興趣相投的人。

2） 從這些潛在朋友的歷史軌跡中查找出一些該用戶沒有去過的地點(diǎn),，并利用協(xié)同過濾的方法來估計(jì)該用戶對(duì)這些地點(diǎn)的興趣度,。如圖 4 所示，如果把用戶和他們?nèi)ミ^的地點(diǎn)用一個(gè)矩陣來表示,，矩陣中的每個(gè)值表示用戶曾去過這個(gè)地方的次數(shù),。那么我們就可以像 Amazon 根據(jù)用戶的買書記錄來推薦圖書那樣使用協(xié)同過濾來計(jì)算用戶對(duì)未曾去過的地方的興趣度。這里有個(gè)很重要的思想,，即相似的人通常會(huì)做出類似的決定,，所以越相似的人的經(jīng)歷越具有參考價(jià)值。

3） 按估算的興趣度對(duì)用戶未曾去過的地點(diǎn)排名,，并把排名較高的 m 個(gè)地點(diǎn)推薦給用戶,。由于這個(gè)推薦是根據(jù)用戶過去的經(jīng)歷分析出來的，因此是個(gè)性化的地點(diǎn)推薦,。

圖 4. 用戶和訪問地點(diǎn)之間關(guān)系的矩陣表達(dá)方式

用途：

由于位置檢測(cè)技術(shù)的迅猛發(fā)展,，用戶可在不干擾生活的前提下輕松地記錄自己的旅行線路、運(yùn)動(dòng)經(jīng)歷,、以及日常生活和工作軌跡,。結(jié)合現(xiàn)有的地理信息數(shù)據(jù)庫(kù)和電子地圖，這些軌跡數(shù)據(jù)可為個(gè)人提供以下服務(wù),。

幫助用戶更有效的回憶過去：個(gè)人的軌跡數(shù)據(jù)可看作是一種自動(dòng)化的電子日記,，從中用戶可以清楚地了解自己過去的經(jīng)歷。比如,，從這些數(shù)據(jù)中用戶可以準(zhǔn)確的知道上星期五自己的上班時(shí)間,，午餐就餐地點(diǎn)以及在回家路上花費(fèi)的時(shí)間等信息。這種功能對(duì)于外出旅行和戶外運(yùn)動(dòng)更加有效,。

更便捷的與朋友分享生活經(jīng)歷：互聯(lián)網(wǎng)的普及催生了網(wǎng)絡(luò)博客的發(fā)展,。通過博客，朋友之間可以方便的分享近期的生活經(jīng)歷,。最近在互聯(lián)網(wǎng)上出現(xiàn)了一種以 GPS 軌跡數(shù)據(jù)為中心的新興應(yīng)用,。在這些互聯(lián)網(wǎng)的虛擬社區(qū)里，用戶可以通過發(fā)布自己的軌跡數(shù)據(jù)來展現(xiàn)自己的旅行經(jīng)歷或運(yùn)動(dòng)線路,。比如,，自行車愛好者可以將自己的騎行線路利用 GPS 設(shè)備記錄下來，然后通過互聯(lián)網(wǎng)上載到論壇來與其他愛好者交流和分享,。

理解自己的生活規(guī)律,，提供個(gè)性化服務(wù)：當(dāng)個(gè)人的數(shù)據(jù)積累到一定程度,，該用戶的生活規(guī)律已經(jīng)在數(shù)據(jù)中得到了體現(xiàn)。因此,，相當(dāng)一部分的研究工作從個(gè)人的長(zhǎng)期數(shù)據(jù)中分析出對(duì)用戶具有重要意義的地點(diǎn),，比如家、公司和常去的商場(chǎng)和餐廳,。進(jìn)一步,，根據(jù)用戶過去的經(jīng)歷得出用戶在這些地點(diǎn)的轉(zhuǎn)移概率，從而能夠?qū)τ脩艚窈蟮幕顒?dòng)作出較為準(zhǔn)確的預(yù)測(cè),。例如,，當(dāng)用戶被預(yù)測(cè)出將要前往某個(gè)商場(chǎng)，系統(tǒng)可將該商場(chǎng)的促銷信息提前發(fā)送到用戶的手機(jī)上,。

參考文獻(xiàn)

1． Mountain Bike. North York Moors and Yorkshire Wolds Mountain Bike (MTB) Routes

2． SportsDo. http:///Activity/ActivityBlog.aspx

3． Yu Zheng, Longhao Wang, Xing Xie, Wei-Ying Ma. GeoLife-Managing and understanding your past life over maps, In Proceedings of International conference on MobileData Management (MDM 2008), Beijing China.

4． Yu Zheng, Xing Xie, Wei-Ying Ma. Searching Your Life on Web Maps, SIGIR workshop on mobile information retrieval, 2008, Singapore.

5． Yu Zheng, Yukun Chen, Xing Xie, Wei-Ying Ma. GoLife2.0: A Location-Based Social Networking Service. In proceedings of International Conference on Mobile Data Management 2009 (MDM 2009).

6． Yukun Chen, Kai Jiang, Yu Zheng. Trajectory Simplification Method for Location-Based Social Networking Services. In Proceedings of ACM GIS workshop on Location-based social networking services. 2009.

7． 謝幸,，鄭宇, 基于地理信息的用戶行為理解, 計(jì)算機(jī)學(xué)會(huì)通訊, 10. 2008.

8． Yin Lou, Chengyang Zhang, Yu Zheng, Xing Xie. Map-Matching for Low-Sampling-Rate GPS Trajectories. In Proceedings of ACM SIGSPATIAL Conference on Geographical Information Systems (ACM GIS 2009).

9． Yang Ye, Yu Zheng, Yukun Chen, Xing Xie. Mining Individual Life Pattern Based on Location History. In proceedings of the International Conference on Mobile Data Management 2009 (MDM 2009).

10. Yu Zheng, Like Liu, Longhao Wang, Xing Xie. Learning Transportation Modes from Raw GPS Data for Geographic Application on the Web, In Proceedings of International conference on World Wild Web (WWW 2008), Beijing, China.

11. Yu Zheng, Quannan Li, Yukun Chen, Xing Xie. Understanding Mobility Based on GPS Data. In Proceedings of ACM conference on Ubiquitous Computing (UbiComp 2008), Seoul, Korea.

12. Yu Zheng, Yukun Chen, Quannan Li, Xing Xie, Wei-Ying Ma. Understanding transportation modes based on GPS data for Web applications. ACM Transaction on the Web. Volume 4, Issue 1, January, 2010. pp. 1-36.

13. Yu Zheng, Lizhu Zhang, Xing Xie, Wei-Ying Ma. Mining interesting locations and travel sequences from GPS trajectories. In Proceedings of International conference on World Wild Web (WWW 2009), Madrid Spain.

14. Quannan Li,Yu Zheng, Yukun Chen, Xing Xie. Mining user similarity based on location history. In Proceedings of ACM SIGSPATIAL conference on Geographical Information Systems (ACM GIS 2008), Irvine, CA, USA.

15. Yu Zheng, Lizhu Zhang, Xing Xie. Recommending friends and locations based on individual location history. To appear in ACM Transaction on the Web, 2009.

16. Yu Zheng, Lizhu Zhang, Xing Xie. Mining Correlation between Locations Using Human Location History. In Proceedings of ACM SIGSPATIAL Conference on Geographical Information Systems (ACM GIS 2009).