陳典全

（廈門雅迅網(wǎng)絡(luò)股份有限公司，福建 廈門361008）

0 引 言

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

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

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

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

所有研究內(nèi)容以用戶授權(quán)采集軌跡數(shù)據(jù)、不觸犯用戶隱私為前提。

1 用戶軌跡簡化

在LBS應(yīng)用中，部分用戶為了與好友分享自己的經(jīng)歷，或者為了記錄自己有紀(jì)念意義的行動過程，會樂于將自己的行動軌跡上傳并保存到LBS服務(wù)提供商系統(tǒng)中?；镜牧鞒淌怯脩敉ㄟ^有衛(wèi)星定位（北斗、GPS等）的手持或車載設(shè)備（典型設(shè)備是具備衛(wèi)星定位的手機）采集到位置信息，通過公用無線網(wǎng)絡(luò)上傳到LBS運營商的服務(wù)器，經(jīng)過處理后保存在數(shù)據(jù)庫中，供用戶自己或者授權(quán)的其他用戶查看。

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

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

圖1 DP算法基本原理

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

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

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

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

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

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

圖2 用戶原始軌跡圖

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

根據(jù)實際應(yīng)用需求，并參考文獻［2]，對DP算法進行以下改進：

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

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

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

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

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

2 用戶軌跡時空融合

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

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

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

圖4 Voronoi圖

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

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

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

表1 PAM示例

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

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

3 用戶行為特征分析

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

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

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

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

3.1 數(shù)據(jù)預(yù)處理

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

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

3.2 算法原理

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

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

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

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

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

重復(fù)下面過程直到收斂：

｛

對于每一個樣例i，計算其應(yīng)該屬于的類：

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

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

3.3 結(jié)果分析

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

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

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

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

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

4 結(jié) 論

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

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

［1]LBS應(yīng)用用戶行動軌跡設(shè)計雜思［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]陳典全，黃朝陽.基于位置的社會網(wǎng)絡(luò)（LBSN）研究及其產(chǎn)業(yè)化［C]／／第二屆中國衛(wèi)星導(dǎo)航學(xué)術(shù)年會論文集（上），上海，2011：144－147.

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