LBS中基于軌跡的用戶行為特征分析①

陳典全

（廈門雅迅網絡股份有限公司，福建 廈門361008）

0 引 言

基于位置的服務（LBS）是整個移動互聯網的基礎應用之一，日、韓、北美、歐洲等都推出了眾多基于位置的服務，國內也有不少企業推出位置相關的產品和服務并獲得成功。國外比較流行的應用有Foursquare、Color、Kuipp等，國內新浪微博、玩轉四方、大眾點評等也融合了與位置相關的信息。

在LBS應用中，針對用戶行動軌跡的產品設計是一個值得深入探討、有很大想象空間的話題，對用戶的行動軌跡數據進行挖掘，可以衍生出眾多有趣的應用［1]。2011年初爆出iPhone、Android可記錄用戶行蹤軌跡，證明了Apple、Google也對用戶行動軌跡深感興趣。

一旦記錄了用戶的行動軌跡，就可以對軌跡數據進行分析、挖掘，掌握用戶的行為特征，從而為用戶提供具有直接針對性、個性化、智能化的基于位置的服務，改變目前LBS服務單純依賴于簽到、彈性社交、問答等幾個簡單模式，從而極大改善用戶的使用體驗。

將以用戶原始記錄的軌跡數據為基礎，進行軌跡簡化、時空融合、行為特征分析等幾方面的研究，為推出個性化LBS服務產品奠定技術基礎。

所有研究內容以用戶授權采集軌跡數據、不觸犯用戶隱私為前提。

1 用戶軌跡簡化

在LBS應用中，部分用戶為了與好友分享自己的經歷，或者為了記錄自己有紀念意義的行動過程，會樂于將自己的行動軌跡上傳并保存到LBS服務提供商系統中。基本的流程是用戶通過有衛星定位（北斗、GPS等）的手持或車載設備（典型設備是具備衛星定位的手機）采集到位置信息，通過公用無線網絡上傳到LBS運營商的服務器，經過處理后保存在數據庫中，供用戶自己或者授權的其他用戶查看。

但是，大多數用戶設備對位置上傳的功能設置比較簡單，最常見的是設置取樣時間間隔，即每隔一定時間采集位置數據并上傳。這種模式將導致上傳到LBS運營商服務器的軌跡數據有大量的無效的冗余信息，不但占用數據庫存儲空間，還不利于用戶軌跡的再次分享傳輸。

軌跡簡化的算法有很多種，最常用的是DP算法（Douglas和Peuker提出），該算法至今仍然廣泛應用于制圖學領域。其基本原理如圖1所示。

圖1 DP算法基本原理

假定如圖軌跡需要簡化，事先設定一個可以容忍的垂直距離td，a作為固定點，b作為浮動點。先找出所有軌跡中到線ab垂直距離最大的c點，判斷fc是否大于td，如果大于，則c作為新的浮動點；再找出a、c兩點間到線ac的垂直距離最大的d點，判斷de是否大于td，如果de＞td，d成為新的浮動點，c作為保留點存儲，否則，d成為新的固定點，而ad之間所有的其它點將丟棄。

DP算法實現起來比較簡單，但用在軌跡簡化中存在兩個問題：

用戶以不同方式運動（駕駛或步行）單位時間內運動距離差別很大，用單一的可容忍垂直距離判斷有可能使得步行軌跡大量丟棄，而往往步行軌跡對用戶來說更有意義。

沒有考慮停留時間。用戶在某點停留往往表示附近有其感興趣的內容，這對于用戶行為特征分析尤為重要。

文獻［2]提出了一種改進的軌跡簡化算法，采用步行和駕駛分段處理、考慮相鄰軌跡點角度變化等優化手段，能夠使得軌跡的簡化更為合理。

圖2示出了某一用戶軌跡圖，用戶駕車從城市快速道成功大道行駛到輪渡，坐渡船到達鼓浪嶼碼頭，步行游覽一周，其中在皓月園景點入內參觀停留。

圖2 用戶原始軌跡圖

如果采用DP算法簡化，如圖3所示，駕車段軌跡損失不大，但步行段則與實際差別很大，而用戶重點參觀的皓月園景點軌跡則全部丟棄。

根據實際應用需求，并參考文獻［2]，對DP算法進行以下改進：

圖3 使用DP算法簡化的軌跡圖

將軌跡點中速度為0或者接近于0的點去除（駕駛停車或步行停留），按照前后軌跡點距離和速度的變化并考慮用戶軌跡的語義（一般不會短時間駕駛與步行交替），將軌跡劃分為駕駛段和步行段。針對駕駛段和步行段使用不同的可容忍垂直距離值進行簡化

考慮相鄰軌跡點用戶方向角度變化以及相鄰點之間的距離。有速度、相鄰點有一定距離、急轉彎（角度變化大）的軌跡點有更大的保留價值

考慮POI匹配、停留時間等因素。將軌跡點與POI進行匹配，并計算與同一個POI匹配的多個軌跡點之間的時間間隔，從而判斷用戶在該POI停留的時間。與某一POI匹配的軌跡點越多、停留時間越長，那么這些軌跡點中與該POI最近的軌跡點保留價值更高

按照以上優化方法進行軌跡簡化，簡化后的軌跡損失駕車段與步行段比較均衡，特別是用戶重點停留的皓月園保留比較完整，簡化后的視覺效果與圖2差別不大，但數據量減少80%以上（5s取樣，駕駛段容忍距離200m，步行段容忍距離40m，考慮相鄰軌跡點角度變化和POI停留時間）。

2 用戶軌跡時空融合

在用戶軌跡簡化的基礎上，就可以進行用戶軌跡的時空融合，即把用戶的軌跡與地圖上的POI點進行匹配，并考慮其停留時間，從而推斷出用戶的行為。可以看出，在軌跡簡化階段考慮用戶停留時間因素十分重要。

用戶軌跡與POI匹配及其停留時間計算采用Voronoi圖算法［3]，如圖4所示。

利用Voronoi圖對平面上n個離散POI點Pi，按照最鄰近原則劃分區域；每個點Pi與它的最近鄰區域相關聯。通過計算軌跡Tj（vj，tj）與各關聯區域的交點Xk，可以進一步推算出最匹配的POI點及軌跡受該POI點影響的持續時間。

圖4 Voronoi圖

研究的重點放在“軌跡與POI匹配并且停留了一定的時間”所代表的語義。要比較準確的分析軌跡所代表的語義需要建立POI－活動映射表（PAM），對每種細分POI所對應的可能活動的時間進行定義。

PAM與POI分類有密切關系，每家地圖數據商其分類有所不同，但一般采用兩級（最多不超過3級）分類法，大類一般不超過20種，小類數百種。PAM必須建立在LBS運營商所采用的地圖數據POI分類基礎上。

表1示出了PAM示例，以此表為參考，可以推斷圖5中的用戶軌跡所代表的語義可能是：“在建文樓上課（工作）3h25min”，“在建設銀行ATM取款20min”，“在大方素食館吃飯1h15 min”。

表1 PAM示例

應該說，基于軌跡及PAM來分析用戶行為還無法做到語義的完全準確推斷，例如“用戶在銀行停留30min”有可能是“ATM取款”，也有可能是“柜臺業務”，甚至有可能兩種活動都有發生。

圖5 用戶軌跡所代表的語義

3 用戶行為特征分析

人的行為特征具有規律性、持續性等特征，一個人經常從事的行為可以反映出其偏好、性格特點甚至氣質修養。經過用戶軌跡簡化和時空融合，LBS運營商可以得到大量的用戶行為信息［4]，這些信息包含時間、地點、活動、持續時間等內容。

經過一定時間的積累，LBS運營商可以從海量數據中挖掘出大量的用戶行為特征信息，并針對用戶行為特征推出相應的個性化LBS服務［5]，例如和商家聯合推出優惠折扣服務。

從海量用戶數據中進行數據挖掘是分析用戶行為特征的主要手段。數據挖掘的很多算法都可以應用在行為特征分析中，如應用分類分析法提取用戶偏好、時間序列法分析用戶行為規律、聚類分析法分析用戶群體特征等。

以“體育運動”為例，我們采用聚類分析中的K－means算法對喜愛體育運動的用戶年齡、體重分布特征進行分析。

3.1 數據預處理

本階段所使用的數據雖然經過了軌跡簡化和時空融合，仍然存在雜亂性、重復性、不完整性等特征，需要對數據進行集成、清洗、簡化等預處理，并構建針對“體育運動”特征進行數據挖掘所需要的數據倉庫。

選取某一年度的用戶軌跡數據，首先進行簡化處理，只選取與POI大類“體育”相關的軌跡數據，然后再對噪聲數據、臟數據等進行清洗，根據用戶群體行為特征分析的需求構建如圖6所示的數據倉庫維度表和事實表。

3.2 算法原理

數據挖掘的目的是要找出從事體育鍛煉的用戶群體分布規律，適合于使用聚類算法，采用聚類算法中最典型的 K－means算法［6]。

圖6 用于特征分析的事實表和維度表

設定要處理的數據集為Rn，樣本是 ｛x（1），…，x（m）｝，每個x（i）∈Rn.

K－means算法是將樣本聚類成k個簇，算法步驟如下：

隨機選取k個聚類質心，u1，u2，…，uk∈Rn

重復下面過程直到收斂：

｛

對于每一個樣例i，計算其應該屬于的類：

對于每一個類j，重新計算該類的質心：

k是事先給定的聚類數，ci代表樣例i與k個類中距離最近的那個類，ci的值是1到k中的一個。質心μj代表對屬于同一個類的樣本中心點的猜測，隨機選取k個點作為初始質心，第一步對于每一個樣本計算其到k個質心中每一個的距離，選取距離最近的那個簇作為ci，經過第一步每一個樣本都有了所屬的簇；第二步對于每一個簇，重新計算它的質心μi（對年齡和體重值求平均）。重復迭代第一步和第二步直到質心不變或者變化很小。

3.3 結果分析

針對3.2中的K－means算法，依據經驗，選取k＝3，亦即找出3類從事體育鍛煉的典型人群。經過計算，3個聚類簇中心是：

｛（23.1，59.3），（39.4，67.6），（56.2，66.9）｝

二維值中分別代表的是年齡和體重。3個簇中心分別代表學生或剛參加工作的年輕人、事業家庭穩定后的中年人以及接近退休的老年人。

根據需要，可以繼續采用數據挖掘的多種算法（如C4.5、Apriori、CART 等）對與“體育運動”相關的行為特征進行進一步分析，例如不同年齡、性別、職業、學歷用戶的體育運動頻度、持續時間、運動類型等。

根據個體或群體用戶的行為特征，LBS運營商就可以推出智能化、個性化的服務，從而極大提升用戶的使用體驗并獲得可持續發展的商業模式。

4 結 論

基于用戶的行為特征提供個性化的服務必將是LBS服務的發展趨勢，而對用戶特性的充分了解是提供個性化服務的基礎。

提供了基于軌跡的用戶行為特征分析的基本研究方法和主要手段，基于這些研究開發出了初步的產品，但商業化的應用仍有許多細節需要進一步的深入研究。

［1]LBS應用用戶行動軌跡設計雜思［EB／OL]［2011－06－28].http：∥www.yeeach.com.

［2]CHEN Yu－kun，JIANG Kai，ZHENG Yu，et al.Trajectory simplification method for location－based social networking services.［C]∥ LBSN＇09Proceedings of the 2009International Workshop on Location Based Social Networks，ACM New York，NY，USA，2009.

［3]XIE Ke－xin，DENG Ke，ZHOU Xiao－fang.From trajectories to activities：a spatio－temporal join approach［C]／／LBSN＇09Proceedings of the 2009International Workshop on Location Based Social Networks，ACM New York，NY，USA，2009.

［4]JAEWAN L，ROMEO M A，M，BOBBY D，et al.Location－aware agent using Data Mining for the Distributed Location－Based Services［C]∥Computational Science and Its Applications Iccsa，2006：867－876 .

［5]陳典全，黃朝陽.基于位置的社會網絡（LBSN）研究及其產業化［C]／／第二屆中國衛星導航學術年會論文集（上），上海，2011：144－147.

［6]JERRYLEAD.k－means聚類算法［EB／OL].［2001－04－06]http：／／www.cnblogs.com