基于改進LCSS的移動用戶軌跡相似性查詢算法研究
2017-05-02 15:36:24陳少權
移動通信 2017年6期
陳少權
【摘 要】為了解決由于移動用戶軌跡數據具有隨機性和繁雜性導致算法效率和精度低的問題，首先抽取用戶軌跡時間位置序列，然后基于用戶的逗留時長采用加權FP樹挖掘移動用戶的常駐區域以解決用戶軌跡的隨機性，最后提出結合用戶出行的時間和地理因素的LCSS算法衡量用戶軌跡相似性。實驗證明，該算法具有一定的有效性和擴展性。
【關鍵詞】軌跡相似性 FP樹 最長公共子序列 時間相似性系數
1 引言
隨著移動通信和移動應用的快速發展，用戶對手機的使用率及依賴性不斷提高，移動運營商積累了大量移動用戶實時記錄的定位數據。分析移動用戶位置的相似性，提取移動用戶的相似路徑在出行路徑預測、興趣區域發現、軌跡聚類、個性化路徑推薦等領域具有廣泛的應用。如何利用豐富的移動用戶定位數據找到合適軌跡的表示方法，如何高效計算移動用戶軌跡間的相似性已經成為工業界和學術界的研究熱點[1]。賈振美針對移動對象的稀疏數據處理的問題，提出了稀疏數據處理的具體方法，并結合時間因素挖掘用戶的頻繁軌跡模式，利用相似用戶聚類方法實現同類用戶位置的預測[2]。張用川通過對手機用戶移動軌跡數據的語義環境信息進行研究，創新性提出地理位置語義化的方法，挖掘用戶出行模[3]。羅家順通過預先對用戶位置進行定義建立用戶-位置信息模型，然后結合時間效應利用協同過濾的算法找到區域性相似的用戶，實現實時的多維動態用戶興趣推薦[4]。肖嘯騏針對移動對象軌跡在時間維度分布不均勻的特點，提出了一種基于關鍵點和時間分段的稀疏軌跡相似性的方法，提升軌跡相似性度量的運行效率和準確度[5]。呂瑞鵬提出一種基于移動概括的相似度方法來衡量用戶移動軌跡的相似度[6]。本文在現有研究者的研究成果基礎上，從移動用戶的原始軌跡數據抽取位置序列，同時將位置序列映射為具有時間和地理位置信息的序列，解決由于移動用戶軌跡數據的稀疏性導致相似度算法效率低下的問題。再結合用戶逗留的時長，通過FP-tree（Frequent Pattern-tree，頻繁模式樹）的加權頻繁模式挖掘移動用戶軌跡的頻繁序列，解決由于用戶軌跡隨機性和繁雜性而導致算法效率低下的問題。最后通過改進LCSS（Longest Common Subsequence，最長公共子序列）的方法，結合時間和地理因素衡量用戶軌跡的相似性。
2 移動用戶軌跡表示及相似度的研究
2.1 移動用戶軌跡表示
原始的移動用戶軌跡數據一般由離散的數據組成，由于信號或者用戶發生業務的原因，這些用戶的軌跡數據會出現分布不均勻、不連續的特點。為了有效挖掘移動用戶的行為，不少學者通過對原始的移動用戶數據做了相關的處理，得到有效的用戶軌跡數據。常見的移動用戶軌跡表現方法有：基于FP-Growth算法對用戶的常駐地模式進行挖掘，得到若干個有效的用戶軌跡數據；基于位置序列的抽取，將不同用戶的位置映射為不同的字符串；利用最小包圍盒技術描述移動用戶的停留區域的基于停留區軌跡表示方法；利用手機軌跡數據的出行目的為目標，采用語義技術來提取用戶出行的地理位置。
2.2 相似度衡量的方法
衡量相似度的方法有很多，常見的有歐式距離、動態時間規整（Dynamic Time Warping，DTW）、編輯距離（Edit Distance on Real Sequence，EDR）、最長公共子序列（Longest Common Subsequence，LCSS）、最大時間出現法（Maximum Co-occurrence Time，MCT）、余弦相似性（Cosine Similarity）、Hausdorff距離等，這些方法的適用數據類型和應用場景不盡相同，因此在選擇時需要充分考慮應用情況[7-9]。基于本文軌跡數據的特點，以下重點介紹歐式距離、DTW、LCSS三種衡量相似度的算法。
（1）歐式距離
歐式距離是通過計算每個時間點上軌跡所對應的兩個點的歐式距離，然后再對所有點的歐式距離進行綜合處理，總和處理包括平均值、求和、取中值等方式。
其中，EU表示歐式距離，dist（pAk， pBk）表示用戶A和B在某段時間段內的距離；pAk、pBk表示A和B在k時刻的位置；pAk， x、pBk， x表示用戶A和用戶B在x維度的位置，同理，pAk， y、pBk， y表示用戶A和用戶B在y維度的位置。
歐式距離的缺點是容易受到噪音的影響，特別是現實中兩個移動用戶的軌跡在時間和個數上都存在很大差異，因此采用該方法的時候必須對移動用戶的軌跡數據進行預處理。
（2）動態時間規劃
動態規劃方法解決了歐式距離對采樣過于苛刻的要求，采用重復點之前的記錄點填補對應空缺的方式，以求出的最小距離作為軌跡的相似性度量[11]。
假設有兩個用戶軌跡空間域的離散采樣P=
（3）最長公共子序列（LCSS）
DTW和歐式距離對軌跡的個別點差異性非常敏感，如果兩個時間序列在大多數時間段具有相似的形態，僅僅在很短的時間具有一定的差異，那么歐式距離和DTW無法準確衡量這兩個時間序列的相似度。LCSS很好地解決了這些問題。
假設有兩條長度分別為n和m的時間序列數據A和B，那么最長公共子序列的長度為[13]：
3 基于改進LCSS的移動用戶軌跡相似性思路分析
基于改進LCSS的移動用戶軌跡相似性查詢算法的研究包括幾個重要的步驟：
（1）抽取位置序列，將位置序列映射為具有時間和地理位置信息的序列，以發生時間的序列表示移動用戶的軌跡。
（2）采用FP-Growth算法挖掘移動用戶軌跡的頻繁序列。
（3）結合時間和地理因素，采用改進LCSS的方法衡量用戶軌跡的相似性。
3.1 移動用戶軌跡的表示
移動用戶的軌跡一般由一系列按照時間依次排序的位置組成[10]，Tri={（L1， t1）， （L2， t2）， …， （Li， ti）， …， （Ln， tn）}。（Li， ti）表示用戶出現在某個基站的位置Li對應的時間ti。
移動用戶軌跡是按照時間序列形成有序的集合，因此，在考慮時間因素的情況下，可通過移動用戶的軌跡抽取移動用戶的時間位置序列。上述的移動用戶軌跡可表示為Tri={（L1， L2， t1， t2）， （L2， L3， t2， t3）， …， （Li， ti， Li+1， ti+1）， …， （Ln-1， tn-1， Ln， tn）}。序列中（L1， L2， t1， t2）表示移動用戶在時刻t1出現在基站L1，然后在時刻t2離開基站L1前往基站L2。
3.2 移動用戶軌跡頻繁序列的挖掘
對于移動用戶軌跡數據的頻繁模式定義為如下形式：
Li→Lj （7）
公式（7）的定義是一個移動用戶從位置Li向位置Lj移動的規律。移動用戶頻繁軌跡提取是從移動用戶移動軌跡數據集中提取支持度大于最小支持度閾值的集合。因此，移動用戶頻繁模式反映了移動用戶群體在移動行為上具有相同特征或是相同規律[15]。但由于頻繁項集在運算過程中需要付出更大的代價，因此本文引入閉合頻繁項集來保證挖掘得到的移動用戶行為信息量最全面且數據規模最小。Pasquier于1999年提出頻繁閉合項集的概念，定義了頻繁閉合移動模式。假設頻繁移動模式Tpi屬于頻繁閉合移動模式，其必須滿足：在頻繁模式集中不存在任一個模式Tpj，滿足Tpj?Tpi，且support（Tpj）≥Tpi。由于考慮到移動用戶在基站的逗留時間，本文以頻繁閉合序列模式挖掘經典算法，以基站平均逗留時間作為項目權重，以各項目count值降序依次為頭節點和其他節點，生成條件模式基，然后采用條件模式基構造對應的加權條件FP樹，最后并按照設定加權支持度的閾值判斷相應的頻繁模式。
3.3 基于改進LCSS的移動用戶軌跡相似性查詢算法
為了提高移動用戶軌跡識別的準確性，在通過TP樹獲得用戶常駐區域模式的基礎上，結合時間因素，以時間系數反映所有用戶在鄰近時間在相同的地理位置的比例。時間相似性系數的公式為：
其中，△T為精度（一般設為1個小時），Ti（u）表示移動用戶u在某一個時間精度內達到某一個基站Li（u）的時刻，Tj（v）表示移動用戶v在某一個時間精度內達到某一個基站Lj（v）的時刻，δ（Li（u）， Lj（v））是一個重合性公式，當兩個用戶的基站重合時，值為1，否則值為0。
結合時間因素，改進的LCSS的相似度算法為：
公式的第一部分表示用戶u和用戶v一天的最長公共子序列，第二部分表示在每一個時間精度下，兩位用戶在鄰近時間在相同的地理位置的比例。
4 實驗分析
4.1 用戶移動軌跡數據的提取和預處理
本次實驗隨機抽取某運營商的10 000名移動用戶兩周的軌跡數據，包括用戶的發生業務的起始時間、起始基站名稱、切換基站時間、切換基站名稱、在每一個基站的逗留時長、主叫號碼、被叫號碼、用戶發生的業務類型等。在對數據進行挖掘之前，先對數據進行預處理，剔除與求解軌跡相似度無關的字段，然后抽取用戶的時間位置序列，最后按照發生業務的起始時間的順序排列每一個用戶的時間位置數據。具體如表1所示。
從表1可以看出，經過對移動用戶原始的軌跡進行預處理之后，得到每一個移動用戶的時間位置信息，為下一步數據挖掘做準備。
4.2 采用FP樹挖掘移動用戶軌跡頻繁序列
（1）對用戶移動軌跡的項目以及項集的數據處理
在獲取用戶時間位置信息的基礎上，計算移動用戶在每一個基站的平均逗留時間，以此作為項目權重。項目名稱及權重如表2所示：
從用戶移動軌跡處理結果提取用戶的項集X={2353-672-6582-42487-31271-57522}。根據用戶在每一個基站的逗留時間設置每一個項目（基站）的權重，當項目（基站）具有一個權重后，用戶發生軌跡的項目項集（基站組合）的權重定義為各項目權重的平均值[17]。例如表3中，X={2353-42487-672-6582}，用戶的移動軌跡項集權重為WT（t）=（286+67+30+45）/4=107，經過歸一化操作之后，該項集的歸一化權重為0.1488。
（2）建立加權FP樹
由表3可得到各項目{2353，672，6582，42487，31271，57522}的count為{5，4，3，4，2，1}。結合用戶在每一個基站的逗留時長，根據FP樹構造的思想，得到某用戶移動軌跡的加權FP樹。基于用戶在基站逗留時長的加權FP樹如圖1所示。
根據加權FP樹導出用戶逗留基站的權重分別是：2353：0.6558；42487：0.6558；6582：0.5487；672：0.3394；31271：0.2616；57522：0.2767。
設最小支持度Wminsup=0.45，那么根據上述的加權條件樹得出的頻繁模式如表4所示。
4.3 基于LCSS算法評價移動用戶軌跡相似性的結果
基于加權FP樹提取移動用戶的常駐地點，再結合移動用戶在常駐地點的時間因素，采用公式（9）計算的10 000名移動用戶工作日的軌跡相似度的結果如表5所示：
5 結束語
隨著移動互聯網的快速發展，大數據洪流已經全方位深入到移動用戶的生活中。如何有效利用移動用戶的海量數據為電信運營商、移動運營商或者其他商家提供有效的營銷數據支撐已經成為研究的熱點。本文首先按照一定的規則對移動用戶軌跡數據進行時間和位置序列預處理，然后采用FP樹挖掘用戶的常駐地點，最后通過改進的LCSS算法來判斷移動用戶軌跡的相似性。實驗證明，該算法具有較高的準確率和擴展性。下一步的工作是設計分布式算法，以支持大規模的移動用戶軌跡相似性的計算，提升計算的速度。
參考文獻：
[1] 裴劍，彭敦陸. 一種基于LCSS的相似車輛軌跡查找方法[J]. 小型微型計算機系統， 2016（6）： 1197-1202.
[2] 賈振美. 面向稀疏軌跡數據的位置預測方法研究[D]. 沈陽： 東北大學， 2014.
[3] 張用川. 基于手機定位數據的用戶出行規律分析[D]. 昆明： 昆明理工大學， 2013.
[4] 羅家順. 面向移動用戶的協同過濾推薦算法研究[D]. 長春： 吉林大學， 2016.
[5] 肖嘯騏. 一個有效的稀疏軌跡數據相似性度量[J]. 微型電腦應用， 2014（4）： 25-30.
[6] 呂瑞鵬. 基于移動概括的新用戶相似度衡量方法[D]. 濟南： 山東大學， 2014.
[7] Chen L， Ozsu M T， Ora V. Robust and fast similarity search for moving object trajectories[A]. Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data[C]. ACM， 2005： 491-501.
[8] Lee J G， Han J， Whang K Y. Trajectory clustering： a partition and group framework[A]. Proceeding of 2007 ACM SIGMOD International Conference on Management of Data[C]. ACM， 2007： 593-604.
[9] Lee S L， Chun S J， Kim D H， et al. Similarity search for multidimensional data sequences[A]. Data Engineering， Proceedings 16th International Conference on IEEE[C]. 2000： 599-608.
[10] 肖艷麗. 基于位置序列的廣義后綴樹用戶相似性計算方法[J]. 計算機應用， 2015，35（6）： 1654-1658.
[11] 郭巖，羅珞珈，汪洋，等. 一種基于DTW改進的軌跡相似度算法[J]. 研究與開發， 2016，35（9）： 66-71.
[12] SAKURAI Y，YOSHIKAWA M，FALOUTSOS C. FTW： fast similarity search under the time warping distance[A]. Symposium on Principles of Database System[C]. 2005： 491-502.
[13] Marascu A， Khan S A， Palpanas T. Scalable similarity matching in streaming time series[A]. PAKDD'12 Proceedings of the 16th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining[C]. 2012： 218-230.
[14] Vlachos M， Kollios G， Gunopulos D. Discovering similar multidimensional trajectories[A]. International Conference on Data Engineering[C]. 2002： 673-684.
[15] 王亮，汪梅，郭鑫穎，等. 面向移動時空軌跡數據的頻繁閉合模式挖掘[J]. 西安科技大學學報， 2016，36（4）： 573-576.
[16] Pasquier N， Bastide Y， Taouil R， et al. Discovering frequent closed itemsets for association rules[A]. ICDT' 99 Proceedings of the 7th International Conference on Database Theory[C]. 1999： 398-416.
[17] 陳文. 基于FP樹的加權頻繁模式挖掘算法[J]. 計算機工程， 2012，38（6）： 63-65.
