概率后綴樹在移動用戶軌跡異常檢測中的應(yīng)用

周湛

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

1 引言

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

2 相關(guān)研究

2.1 概率后綴樹

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

2.2 概率后綴樹的構(gòu)造方法

概率后綴樹的構(gòu)造步驟分為兩步：

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

（2）遞歸擴(kuò)充每一個候選節(jié)點(diǎn)。

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

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

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

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

3.1 移動用戶軌跡預(yù)處理

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

3.2 移動用戶軌跡序列化

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

3.3 構(gòu)造PST概率模型

圖1 概率后綴樹的示例圖

表1 移動用戶軌跡處理

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

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

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

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

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

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

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

3.5 實(shí)驗(yàn)分析

（1）實(shí)驗(yàn)環(huán)境設(shè)置

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

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

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

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

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

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

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

從表2可知，測試集的平均準(zhǔn)確率達(dá)到86%，滿足工程應(yīng)用的精度。由此說明，該算法能夠?qū)崿F(xiàn)移動用戶軌跡異常檢測的應(yīng)用。

4 結(jié)束語

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