周湛

（廣州杰賽科技股份有限公司，廣東 廣州 510310）

1 引言

移動用戶的出行軌跡反映了移動用戶的出行行為規(guī)律，移動用戶出現(xiàn)的每一個位置都會與之前出現(xiàn)的若干個位置存在一定的聯(lián)系。因此，可用概率后綴樹對移動用戶的出行位置序列進行建模，用于反映移動用戶軌跡的離群點或者異常點。目前的異常軌跡挖掘方法有：（1）通過提取軌跡的特征向量，采用基于距離的檢測方法來檢測異常的特征向量，從而達到軌跡異常點的提取[1]。（2）通過歷史軌跡數(shù)據(jù)提取出k個熱點軌跡，然后對比同一時間段的軌跡與熱點的距離，實現(xiàn)軌跡異常點檢測[2]。（3）先對分段后的軌跡形狀進行聚類，然后再對比整條軌跡的聚類單元進行對比，實現(xiàn)局部軌跡異常檢測功能[3]。（4）通過改進Hausdorff的距離實現(xiàn)軌跡聚類，通過聚類結果判斷軌跡異常檢測點[4]?？紤]到移動運營商具有海量用戶以及移動用戶自身的時空數(shù)據(jù)特點，本文提出基于概率后綴樹的移動用戶軌跡異常點檢測方法，該方法由于采用n叉樹思想檢測移動用戶的軌跡異常點，因此具有學習代價較低的特點。

2 相關研究

2.1 概率后綴樹

文獻[5]給出了概率后綴樹（Probabilistic Suffix Tree，PST）的詳細描述：概率后綴樹其實是一棵對節(jié)點進行有序排列的n叉樹。作為根節(jié)點Root給出了每一個字符或者符號的無條件概率，后面的每一節(jié)點給出了前面出現(xiàn)的一個或者多個字符或者符號的條件概率向量。深度為L的概率后綴樹一共有L階，葉節(jié)點保存了L個字符、符號的記錄以及對應的條件概率向量。概率后綴樹的示例圖如圖1所示。

2.2 概率后綴樹的構造方法

概率后綴樹的構造步驟分為兩步：

（1）根節(jié)點的初始化以及計算每一個字符、符號的無條件概率。設置子節(jié)點的閾值，如果字符、符號的無條件概率大于所設置的入樹概率閾值，則把對應的字符、符號作為候選的子節(jié)點。

（2）遞歸擴充每一個候選節(jié)點。

◆計算每一個候選節(jié)點的所有可能出現(xiàn)后續(xù)字符串的條件概率向量。

◆設候選節(jié)點的字符串為s，如果該字符串的后續(xù)字符串σ條件概率大于設定的候選節(jié)點閾值，那么候選節(jié)點的字符串為s添加到樹中。

◆如果該節(jié)點的深度小于概率后綴樹設定的深度閾值，如果候選節(jié)點的字符串為s，后續(xù)字符串為σ，如果sσ的相對概率大于入樹概率閾值，那么標記sσ節(jié)點作為該節(jié)點的候選節(jié)點。

3 基于后綴樹概率的移動用戶軌跡異常檢測

3.1 移動用戶軌跡預處理

從移動用戶發(fā)生業(yè)務時獲取的用戶軌跡數(shù)據(jù)較為連續(xù)，如果用戶在某個位置駐留時間較長，將會產生多次通話記錄。本文已經考慮了移動用戶的逗留時間，為了降低該算法的復雜度，將同一個位置的軌跡信息合并成一個。移動用戶軌跡處理如表1所示。

3.2 移動用戶軌跡序列化

在對移動用戶軌跡數(shù)據(jù)進行預處理后，按照時間依次排序移動用戶的軌跡集合，形成移動用戶的出行軌跡，時間序列Tri={(L1, t1), (L2, t2), …, (Li, ti), …, (Ln,tn)}。其中，(Li, ti)表示用戶在時間ti出現(xiàn)在Li位置。

3.3 構造PST概率模型

圖1 概率后綴樹的示例圖

表1 移動用戶軌跡處理

移動用戶軌跡數(shù)據(jù)可以看作一個按照時間規(guī)律排列的時間序列。定義一個時間發(fā)生的條件概率為前n-1個時間序列已經發(fā)生的條件下第n個時間序列。不同排列的n個時間序列對應不同的條件概率分布。為了描述移動用戶軌跡的規(guī)律性，以移動用戶的時間序列構造概率后綴樹模型，一個PST的節(jié)點對應著移動用戶的某一個時間序列，而一個時間序列對應著一個d維條件概率矢量，其中d是用戶時間序列的個數(shù)。圖2是追蹤某個移動用戶在一個月內的軌跡序列，按照一個時間序列發(fā)生后下一個時間序列的條件概率以逆序從頂向下PST得到的概率后綴樹，如果想知道用戶經過基站12321與基站10032后去往基站10536的概率，那么從PST可知，用戶去往基站10536的概率為0.25。同理，用戶經過基站12321與基站10032后去往基站12321的概率為0。

3.4 移動用戶軌跡的相似度分析

PST模型的一個重要作用就是計算用戶軌跡時間序列之間的相似度。由參考文獻[6]可知，移動用戶軌跡的相似度可以定義為用戶的軌跡時間序列與用戶的軌跡時間序列集合之間的相似度。

圖2 基于某移動用戶的軌跡數(shù)據(jù)構造概率后綴樹模型

先計算一個用戶的其中一個軌跡序列m在軌跡序列集合S中出現(xiàn)的概率：

其中，Ps(m)為用戶軌跡序列m在整個軌跡序列集合S的條件概率，可通過上述的PST得到。顯然，當Ps(m)很大時，這表明用戶軌跡序列m在用戶整個軌跡序列中出現(xiàn)的概率較大，那么越可能是用戶的常規(guī)路徑，越有可能代表用戶的出行規(guī)律。從聚類的角度來看，用戶軌跡序列與該軌跡的集合的相似度越大。因此，本文定義移動用戶出行軌跡序列與軌跡序列集合S的相似度為：

其中，Pr(m)表示移動用戶的軌跡si獨立隨機發(fā)生的概率。顯然，如果sims(m)大于1，那么表明該軌跡序列m很有可能發(fā)生；相反地，如果小于1，則表明該軌跡序列m發(fā)生的可能性不大。因此，本文把異常度的閾值設為1，如果該序列的相似度大于1則把用戶的軌跡序列視為正常；相反地，如果小于1，則把用戶的軌跡序列視為異常。

3.5 實驗分析

（1）實驗環(huán)境設置

實驗環(huán)境：Windows Server 2008 R2 64bit，Inter Xeon 2.50 GHz CPU，16.0 GB內存。仿真環(huán)境：Matlab R2015b。

（2）實驗數(shù)據(jù)及方法介紹

本文獲取保定市某運營商10 000用戶發(fā)生業(yè)務的位置以及發(fā)生的時間，然后根據(jù)上述的軌跡預處理以及軌跡序列化方法對軌跡數(shù)據(jù)進行處理，得到滿足在道路上運動的移動用戶數(shù)約為4 057，再通過剔除較長時間沒有運動的用戶，最后得到3.012×107名用戶。本文收集3 012名移動用戶3個月的軌跡數(shù)據(jù)，并通過頻度分析的方式找到3 012名移動用戶3個月正常軌跡數(shù)據(jù)并進行標注。隨機抽取50%已標注的軌跡數(shù)據(jù)作為訓練數(shù)據(jù)集并構建PST模型，然后對剩下的50%進行檢驗。得到的實驗結果如圖3所示：

圖3 移動用戶經過的軌跡點數(shù)量統(tǒng)計圖

從圖3可知，大部分移動用戶平均每天經過的基站數(shù)量區(qū)間為5~9，按照基站的平均部署的距離得出移動用戶的日均運動距離的區(qū)間為2.5 km~5 km。該數(shù)據(jù)結果符合一般用戶的出行路徑長度。

對上述滿足要求的移動用戶軌跡數(shù)據(jù)重復10次實驗，得到的移動用戶軌跡異常檢測準確率如表2所示：

表2 移動用戶軌跡異常檢測模型平均準確率 %

從表2可知，測試集的平均準確率達到86%，滿足工程應用的精度。由此說明，該算法能夠實現(xiàn)移動用戶軌跡異常檢測的應用。

4 結束語

本文以移動用戶軌跡序列數(shù)據(jù)為出發(fā)點，提出了一種移動用戶軌跡異常檢測的方法——基于后綴概率樹的算法。在對移動軌跡進行預處理和軌跡序列化的基礎上，構建移動用戶出行軌跡的PST模型，基于PST模型得到的條件概率計算移動用戶出行軌跡序列與軌跡序列集合的相似度，以此來實現(xiàn)移動用戶軌跡異常檢測。實驗證明，基于概率后綴樹的移動用戶軌跡異常檢測方法能夠滿足一定的工程應用要求。