數據挖掘系列篇(25):基於地理位置的數據挖掘
一般我們在做數據挖掘過程中地理位置算是一個特別重要的特徵，廣泛應用於O2O的很多場景。但做的事情都相對來說比較簡單，LBS的網格位置推相應的內容。原來我們基於地理位置拿了不少數據，也做了一些模型，主要是一些醫院位置、商場位置、公交地鐵位置等來給附近的人推服務。
——————————————————禁止轉載———————————————————
不同定位比較：
在當前眾多的無線定位技術中，GPS 以其覆蓋範圍廣、定位精度高、定位時間短和定位依賴性小等優勢逐漸在人們的日常生活中變得普及起來（見表 1）。各種車載 GPS、手持GPS 和 GPS 智能手機的相繼問世也為人們提供了更加便捷的位置獲取和軌跡記錄方式。作為用戶經歷的載體，這些軌跡數據在各種應用中發揮著重要的作用，並幫助人們來理解個人行為和社會規律。從數據源來看，當前的研究工作可分為基於個人軌跡數據的理解和基於多人軌跡數據的理解兩個方向。
場景：
用戶歷史軌跡中出現的頻繁模式反映了個人的生活習慣和行為規律。如果可以很好的從軌跡中理解到這些知識，服務提供商將可以為用戶提供更深入、更個性化的位置服務。而要從軌跡中挖掘這些頻繁模式，首先要面臨的困難就是如何對個人的歷史軌跡建模。
如圖 1 所示，一條 GPS 軌跡通常由一系列帶有時間戳的坐標點組成。每個坐標點包含了經度、緯度和海拔高度等基本信息。一個人在一段時間內的活動就可記錄為這樣一條連續的軌跡。在這條軌跡中，我們可以通過演算法檢測出一些用戶停留過的地方。這個停留點並不是指速度為零的點，而是由一組實際的 GPS 點構成，如圖 1 中 p3, p4, p5 和 p6構成了一個停留點 s。它表示用戶在某個區域內滯留的時間超過了一定的時間範圍。與其他 GPS 點相比，這些停留點含有更重要的語義信息，如用戶去過的餐館和電影院等。基於這些停留點，一個用戶的歷史軌跡就可以表達為一個停留點序列，如
。這個序列抓住了用戶行為的重點，同時也大大減輕了數據處理量。
圖 1. 一條 GPS 軌跡樣例
——
由於用戶多次訪問同一地點所產生的停留點並不完全一致（坐標會有偏差），直接對停留點進行比較並不可行。因此，我們需要對從軌跡中提取出來的停留點進行聚類。這樣相近的停留點就會被分配到同一個聚類中。此後，我們再用各個停留點所歸屬的聚類來替換這個停留點，將停留點序列進一步轉化為聚類的序列。這樣用戶在不同時間段的歷史軌跡就可比了。
有了用戶歷史軌跡的模型，我們可以用多種演算法（如 FP-growth、Closet+等）來挖掘這個數據中的頻繁項集。如用戶 A 經常在周末早上去中關村、用戶 A 經常在周五晚上去超市等。進一步，這些頻繁模式，可以相互組合和連接，從而發現一些表徵了用戶生活、行為規律的順序模式（sequential pattern）。比如，通常用戶 A 在周末早上會去中關村看電影，然後下午去西單買東西。當然，這些學習到的模式將受到隱私保護，並只為用戶個人所用。
在挖掘有意思的地點和經典旅行線路時，首先就要對不同用戶的軌跡數據建模。如圖2所示，我們首先從每個用戶的每條線路中提取出停留點（在圖中表示為綠色小點），並把它們放在一個集合中。然後，利用一種基於密度的聚類演算法，我們對這個停留點集合進行層次化聚類，在不同的地理尺度上，將相近的停留點劃分到同一個聚類（圖中灰色節點，如 等）。這樣我們可以得到一個如圖右半部分所示的一個層次樹。樹中的節點代表不同的停留點聚類，而不同層次表示不同的地理空間尺度。層次越深，粒度越細，代表的地理空間也越小。隨後，將不同用戶的軌跡映射到這棵樹的各個層次，就可以將不同的聚類連接起來，從而得到不同的圖模型（如圖 2左半部分所示）。
圖 2. 基於層次圖模型的多用戶軌跡聚合
——
正如前面提到過的，軌跡隱含了人的行為和喜好。因此，人們在地理空間移動的相似性，也在一定程度上反映了不同人之間品味和愛好的相似性。這裡，我們首先按照如圖 3 所示的方式用不同的層次圖來建模每個用戶的歷史軌跡，然後成對地比較圖和圖之間的相似性。
與之前提到過的大眾數據建模方法一致，我們仍然利用層次化聚類的思想將所有用戶的停留點轉化為一個公共的層次樹（圖3 中間的部分），樹中的各個節點（停留點聚類）表示不同尺度和粒度的地點。此後，將每個用戶的線路分別導入這個公共的框架，便可得到用戶各自的層次圖（圖3 的左右兩個部分分別表示用戶 1 和 2 的層次圖）。
在通過匹配兩個層次圖來計算用戶相似性的時候，我們考慮以下兩點因素：
1） 層次。兩個人的相似性，可表示為兩個層次圖中各個對應層次上的圖的相似性的加權和。這裡的權重就是由層次的深度來決定。由於較深的層次具有較細的空間粒度和尺度，兩個用戶在越深的層次上的圖越相似，則表明他們的活動軌跡越相似。因此，深層次的匹配結果應被賦予較大的權重。比如，兩個人都在中國就不如兩個人都在北京市相似。如果能發現兩個人在代表學校和景點這種更細粒度的層次上仍有重疊，則說明這兩個人更相似。
2） 相似序列的長度。同一圖層上兩幅圖的相似性，可表示為這兩個圖共享序列的相似性的和。而序列的相似性，又取決於序列的長度。因此，用戶共享的序列越多，序列的長度越長，則這兩個圖的相似性越大。如 A、B 和 C 三個用戶，A 和 B 共同走過了一個長度為 2 的序列 ，而 A 和 C 兩個共同走過一個長度為 3 的序列 。顯然，與 B 相比，用戶 C 更加跟 A 相似。
圖 3. 利用層次圖來比較用戶的相似性
前面介紹的利用大規模軌跡數據實現大眾化旅行推薦可找出一些公認的熱門景點和經典旅行線路。但實際上不同的用戶有不同的喜好，在每個人的心幕中各種景點的排名也不一樣。比如，喜歡自然風景的用戶可能對故宮這樣的歷史古迹並不是特別感興趣；喜歡美食的遊客也可能會更加關注哪些小吃聚集的街道。因此，針對個人的喜好來做個性化的推薦才是更人性化、更有效的位置服務。
我們設計的基於軌跡的個性化朋友和地點推薦包含以下三步：
1） 利用用戶的歷史軌跡計算出用戶之間的相似性（參見上一節描述的方法），為某個用戶找出最相似的 n 個人作為潛在的朋友，完成個性化朋友推薦。也許他們在現實生活中多次插肩而過，卻從來沒有認識的機會。由於他們具有相同的興趣愛好，因此，當在論壇中發起一些活動的時候（如自駕游和登山等），用戶能更加精準地找到一些興趣相投的人。
2） 從這些潛在朋友的歷史軌跡中查找出一些該用戶沒有去過的地點，並利用協同過濾的方法來估計該用戶對這些地點的興趣度。如圖 4 所示，如果把用戶和他們去過的地點用一個矩陣來表示，矩陣中的每個值表示用戶曾去過這個地方的次數。那麼我們就可以像 Amazon 根據用戶的買書記錄來推薦圖書那樣使用協同過濾來計算用戶對未曾去過的地方的興趣度。這裡有個很重要的思想，即相似的人通常會做出類似的決定，所以越相似的人的經歷越具有參考價值。
3） 按估算的興趣度對用戶未曾去過的地點排名，並把排名較高的 m 個地點推薦給用戶。由於這個推薦是根據用戶過去的經歷分析出來的，因此是個性化的地點推薦。
圖 4. 用戶和訪問地點之間關係的矩陣表達方式
——————————————————禁止轉載———————————————————
用途：
由於位置檢測技術的迅猛發展，用戶可在不干擾生活的前提下輕鬆地記錄自己的旅行線路、運動經歷、以及日常生活和工作軌跡。結合現有的地理信息資料庫和電子地圖，這些軌跡數據可為個人提供以下服務。
? 幫助用戶更有效的回憶過去：個人的軌跡數據可看作是一種自動化的電子日記，從中用戶可以清楚地了解自己過去的經歷。比如，從這些數據中用戶可以準確的知道上星期五自己的上班時間，午餐就餐地點以及在回家路上花費的時間等信息。這種功能對於外出旅行和戶外運動更加有效。
? 更便捷的與朋友分享生活經歷：互聯網的普及催生了網路博客的發展。通過博客，朋友之間可以方便的分享近期的生活經歷。最近在互聯網上出現了一種以 GPS 軌跡數據為中心的新興應用。在這些互聯網的虛擬社區里，用戶可以通過發布自己的軌跡數據來展現自己的旅行經歷或運動線路。比如，自行車愛好者可以將自己的騎行線路利用 GPS 設備記錄下來，然後通過互聯網上載到論壇來與其他愛好者交流和分享。
? 理解自己的生活規律，提供個性化服務：當個人的數據積累到一定程度，該用戶的生活規律已經在數據中得到了體現。因此，相當一部分的研究工作從個人的長期數據中分析出對用戶具有重要意義的地點，比如家、公司和常去的商場和餐廳。進一步，根據用戶過去的經歷得出用戶在這些地點的轉移概率，從而能夠對用戶今後的活動作出較為準確的預測。例如，當用戶被預測出將要前往某個商場，系統可將該商場的促銷信息提前發送到用戶的手機上。
參考文獻
1． Mountain Bike. North York Moors and Yorkshire Wolds Mountain Bike (MTB) Routes
2． SportsDo. http://sportsdo.net/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． 謝幸，鄭宇, 基於地理信息的用戶行為理解, 計算機學會通訊, 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).
微信公眾號：datafa（數據分析聯盟）
微信群：加V 784414374
QQ群：252805327
新書鏈接：
【數據分析俠 《人人都會數據分析》20萬字書籍】http://m.tb.cn/h.AJEkoq 點擊鏈接，再選擇瀏覽器打開；或複製這條信息￥fSnh09F0Vpy￥後打開 手淘
推薦閱讀：