基于到達時間的行為模式挖掘?

李克華 劉志鋒 周從華

（江蘇大學計算機科學與通信工程學院 鎮(zhèn)江 212013）

1 引言

隨著GPS 定位技術的不斷發(fā)展與智能移動設備的普及，軌跡數(shù)據(jù)的獲取不再困難。比如通過開啟智能收集中的定位服務，可以記錄用戶的位置，所有這些位置記錄組成了該用戶的原始軌跡，從這些軌跡中推斷出用戶的日常行為習慣。針對這一相關應用的需求逐漸增多，在個性化服務中，幫助服務供應商了解用戶的生活規(guī)律，預測用戶的行駛路徑，實現(xiàn)商品或路徑推薦；或者在推薦系統(tǒng)中，通過用戶分享的軌跡數(shù)據(jù)，發(fā)現(xiàn)用戶的生活方式、興趣愛好等，推薦趣味相投的朋友；因此，近年來不少學者開始關注移動用戶軌跡模式的研究。

移動用戶軌跡模式的挖掘分為兩類：基于地理位置的軌跡模式挖掘和基于語義信息的軌跡模式挖掘。前者主要關注的是位置特征，即GPS類型的移動數(shù)據(jù)，后者主要關注的是語義信息，這類數(shù)據(jù)有些需要從GPS軌跡中計算得到語義信息，有些則是已經(jīng)標注好語義的數(shù)據(jù)；同傳統(tǒng)的軌跡挖掘算法相比，語義軌跡行為模式挖掘計算量大大減小，并且能更好地反映用戶平常的行為模式與生活習慣。

在語義軌跡模式挖掘技術方面，目前缺乏一種能夠處理用戶在基于語義點到達時間下的高準確性的軌跡模式挖掘方法。為了解決這一問題，本文提出了一種基于到達時間的語義行為模式挖掘方法。將原始的語義軌跡轉化成具有代表性的語義軌跡模式，并根據(jù)語義軌跡模式進行用戶相似度的度量。該方法的優(yōu)勢在于1）能夠提高不同語義行為模式之間的區(qū)分度；2）能夠發(fā)現(xiàn)具有相似生活方式或行為習慣的移動對象群體。

2 相關工作

本節(jié)首先介紹了語義軌跡頻繁模式挖掘方法，然后概括了現(xiàn)有的語義軌跡相似度度量方法。

Zheng Yu 等提出了將地理軌跡轉化為語義軌跡的方法，基于移動對象在某個區(qū)域范圍內停留的時間來判定停留點，一系列的停留點便形成了語義軌跡［1］。Furtado 等將原始的軌跡序列轉換成一系列的子序列片段，然后按照網(wǎng)格軌跡序列的形狀相似程度和空間上的遠近程度對分段后的子軌跡進行重組，進而通過應用子樹結構和技術來找出頻繁的路徑模式［9］。Huang 等通過定義距離公式，將軌跡進行聚類，軌跡在不同聚類轉移的模式即為軌跡的頻繁模式，但該方法不適用于語義軌跡［2］。Liu等提出了基于地理位置的語義軌跡頻繁模式挖掘方法。該方法采用STP-tree 對語義軌跡的模式按照地點的先后順序進行索引，每條路徑代表一個模式，遍歷STP-tree找到所有符合給定頻繁閾值的模式即可得到語義軌跡頻繁模式［3］。Ying 等將軌跡經(jīng)過的地點作為軌跡的語義點，并基于這些語義點建立T-pattern Tree，其結構類似STP-Tree，只是T-pattern Tree 的每一條邊記錄了語義軌跡從一個地點轉移到另一個地點所需要的時間，同樣的，遍歷T-pattern Tree 找到所有符合給定閾值的模式即可得到語義軌跡頻繁模式挖掘［4］。上述方法中，只有文獻［4］考慮了語義軌跡中的時間因素，但只考慮了語義點之間的轉移時間，沒有考慮到達時間。

文獻［1，5，7］討論并研究了語義軌跡的相似性。文獻將軌跡轉換成語義軌跡，然后通過移動對象之間的相似性進行用戶推薦，文獻［1］依據(jù)用戶之間軌跡模式的相似性定義用戶之間的相似性，文獻［5］通過層次樹狀結構計算相似性。基于地理特征信息的相似性度量方法只能處理軌跡的位置信息，而基于語義信息的相似性度量方法沒有考慮到達時間的影響，因此現(xiàn)有的相似性度量方法不能解決基于到達時間的語義軌跡相似性問題。

為了解決上述問題，本文提出了一種基于到達時間的行為模式挖掘方法。

3 問題定義

本節(jié)給出語義行為模式相關的定義

定義1語義點語義點S定義為

其中，s是用戶的停留點，tarrive是用戶在語義點S的到達時間。

定義2語義軌跡

語義軌跡是一個由n個語義點組成的序列。

對任意的si和si+1，有ti≤ti+1。語義軌跡長度即為所包含的語義點的數(shù)量，記為|ST|=n。所有語義軌跡組成的集合稱為語義軌跡集，記為R，軌跡的數(shù)量為 |R|。

定義3用戶語義行為模式 給定用戶語義軌跡集合R和最小支持度sup，用戶行為語義模式即從軌跡中挖掘出頻繁語義行為模式P=，滿足條件：

最后，給出本文問題描述：基于到達時間的語義行為模式挖掘是指給定用戶語義軌跡集合R，最小支持度sup 和時間閾值δt，依據(jù)sup 和δt，從語義軌跡集合中進行用戶語義軌跡頻繁模式的提取，得到可以反映用戶生活習慣的語義行為模式。

4 語義軌跡頻繁模式挖掘

本節(jié)介紹了用戶的語義行為模式挖掘方法。在行為模式挖掘之前，先對原始數(shù)據(jù)進行語義軌跡的轉換，關于地理數(shù)據(jù)轉換為語義軌跡數(shù)據(jù)的研究較為豐富［8］，本節(jié)不再詳細描述，然后針對每一個用戶，挖掘出他的頻繁語義模式。這里以在校大學生的數(shù)據(jù)集為例進行說明。整合大學生的智能卡使用信息以及校園內各個地點的門禁日志可以得到學生的語義軌跡。對每個學生，以天為單位從其個人記錄中提取出若干條包含時間的語義軌跡，如表格1所示。

表1 語義軌跡集示例

語義軌跡代表了學生在某一天的時空行為，語義軌跡頻繁模式挖掘是從許多語義軌跡中找出行為模式。每個用戶的語義軌跡隨著用戶移動地點及時間的不同呈現(xiàn)多樣化形式，但是可以通過行為模式挖掘分析出不同用戶的行為習慣。我們基于prefix-span算法的思想來構建頻繁模式挖掘算法。

定義4投影數(shù)據(jù)庫 給定語義軌跡集合R，α的投影數(shù)據(jù)庫R(α)=，tuple定義為

其中，id軌跡在語義軌跡集中的標識號，pos是α中最后的語義點在語義軌跡中的位置，t是最后一個語義點的到達時間，proj是pos以α為前綴的子序列。

算法1：行為模式挖掘算法

輸入：語義軌跡集R，時間間隔δt，

最小支持度θ

輸出：頻繁語義模式FP

1.S1←frequent(R(P))

2.for β in S1do

3. P'←P⊕β

4. R(P)←?

5. for p in R(P)do

6. S ←R(p.id)

7. for i:i ＞p.pos Si=β do

8. R(P')←R(P')∪＜p.id，i，Si.t，p.proj⊕β ＞

9. end for

10. end for

11. for p'in R(P')do

12. T ←SET(R(P')，p'，δt)

13. if |T |≥θ× |R |th en

14. Pnew←getPattern(P'，T)

15. P ←P ∪Pnew

16. end if

17. end for

18.end for

19.return P

算法中函數(shù)SET()計算到達時間差額在δt范圍內的項目集，假設與p'等價的到達時間范圍G，的等價到達時間范圍G=[p'.t-δt，p'.t+δt]。

函數(shù)getPattern()根據(jù)集合T中的平均到達時間構建β的到達時間，最終返回頻繁語義行為模式P'=P(β，tβ) 。

在行為模式挖掘算法中，首先找出語義軌跡集中長度為1 的語義符號項集S1，將P與S1中的語義點β進行拓展，并在語義軌跡集合R中構造投影數(shù)據(jù)庫（行1-10），然后遞歸構建頻繁語義行為模式。對每一個項集p'，調用函數(shù)SET()返回行為模式中與其等價的語義集軌跡合T，經(jīng)判斷，若為頻繁模式，調用函數(shù)getPattern()構建頻繁語義行為模式。

5 語義模式相似度

本節(jié)介紹了語義行為模式相似度的度量。研究表明，語義行為模式之間的相似度取決于兩個模式之間的公共子序列。當兩種行為模式之間的公共子序列越長，我們認為兩種行為模式越相似。

MSTP-similarity算法計算的是每個用戶最長的語義軌跡模式之間的相似度。語義軌跡的長度越長，它所產(chǎn)生的子序列數(shù)目越多。模式的所有子序列都會參與到用戶的相似度計算中，為了避免重復計算帶來的誤差問題該方法只使用最長語義軌跡模式表示用戶的頻繁行為習慣。計算方式如下：

在上一節(jié)中我們已經(jīng)對用戶語義軌跡進行了頻繁語義軌跡模式的提取，得到的結果代表了用戶的行為模式，無需另選最長語義軌跡。但是原算法在計算行為模式相似度的時候存在一個問題：只基于兩個序列的符號的等同性來進行相似性的計算。由于本文的語義行為模式序列中還具有時間信息，這些信息對于計算兩個行為模式的相似度具有重要的作用。所以，本節(jié)基于原來的MSTP-simi?larity 做了改進，使其可以將用戶對語義點的到達時間考慮到相似度計算中。首先，給出基于到達時間的最長公共子序列定義：

定義5最長公共子序列給定兩個用戶語義行為模式P和Q，最長公共子序列滿足條件：

為了突出到達時間對用戶語義行為模式的影響，給出了時間因子的定義。

定義6時間因子 給定用戶語義行為模式P，Q，當其子序列元素一致時，元素對相似度的貢獻值通過時間因子來表達，定義如下：

定義7用戶行為模式相似度 給定用戶語義行為模式P，Q及公共子串，P，Q之間的相似度定義為

給定語義軌跡模式，當公共子序列越多、時間因子越大時，兩個模式越相似。由于尋找公共子序列的過程十分耗時，本文采用動態(tài)規(guī)劃法來尋找。動態(tài)規(guī)劃方法采用二維數(shù)組標識中間計算結果，避免了重復計算而提高了效率。相似度計算算法如下。

算法中，我們采用動態(tài)規(guī)劃算法逐步計算了P，Q之間的相似度，矩陣分別存儲了P_ratio，Q_ratio以及公共子序列的長度count。首先對矩陣初始化，第一行第一列皆為0；然后依據(jù)count變化逐步計算P_ratio，Q_ratio。比如，矩陣的第一個元素count加1，然后P_ratio增加，Q_ratio增加(1/| {dor，lib}|)*T13，通過這種方式，逐步處理得到矩陣中的值。最后，根據(jù)定義計算兩個用戶的相似度。

6 實驗結果與分析

6.1 數(shù)據(jù)集及實驗環(huán)境

實驗數(shù)據(jù)：某大學經(jīng)過脫敏處理過后的9475名學生的校園語義軌跡。原始數(shù)據(jù)集示例如圖1。

圖1 數(shù)據(jù)集概覽

實驗環(huán)境：編譯軟件/python 3.6.0，操作系統(tǒng)/Windows10/CPU/Intel（R）CORE（TM）i5-2450M，主頻2.50GHz，內存8G。

6.2 數(shù)據(jù)預處理

我們以天為單位將學生的“數(shù)字足跡”轉化為語義軌跡軌跡，處理后的數(shù)據(jù)詳情如表2所示。

表2 預處理后數(shù)據(jù)

6.3 語義軌跡頻繁模式挖掘實驗

首先對實驗的有效性進行驗證，即考慮到達時間后挖掘出的語義軌跡模式是否比沒有考慮到達時間時更具有代表性，更能表現(xiàn)用戶行為習慣，部分用戶語義行為模式挖掘結果如下。

表3 基于到達時間的語義模式

由于考慮了用戶在每個語義點的時間因素，挖掘出的行為模式更能體現(xiàn)每個學生的行為習慣，比如學生8和學生37，若不考慮時間約束下的行為模式挖掘，二者的校園語義軌跡近似相同，容易造成二人的生活習慣也類似的錯覺，從而不利于后續(xù)相似度的計算。但是引入了到達時間之后發(fā)現(xiàn)，學生8 的生活習慣傾向于早起去食堂吃早飯并喜歡去圖書館，白天的大部分時間不會在宿舍；而學生37則是基本不吃早飯而且經(jīng)常到中午才會離開宿舍，二者呈現(xiàn)出的行為模式完全不同。

本節(jié)模擬了100 個用戶，依據(jù)每個用戶的行為模式生成了1000 條語義軌跡，20%條隨機生成，80%條語義軌跡依據(jù)4 中用戶行為習慣生成，為了更精確的評估挖掘算法的準確率，定義如下：

其中，ηcorrect是正確的語義行為模式個數(shù)，ηall是語義行為模式的個數(shù)。參數(shù)設置如下：num=100，trj=1000，Lpat=6，Npc=20 。

圖2 展示了不同時間閾值、不同支持度得到的行為模式準確度。當頻繁模式支持度偏小時，得到的結果在不同時間閾值下沒有明顯的增加減小，因為支持度過小時，挖掘到的行為模式并非主流結果，不能有效代表一個用戶的行為模式。當支持度在0.1以上時，挖掘到的語義模式更具代表性，隨著時間閾值的增加，準確率也不斷提高。值得注意的是，當時間閾值在40min～50min 以上時，準確率沒有改善，還有下降趨勢，這是因為隨著時間差增大，導致不同模式之間的區(qū)分度降低，從而影響了挖掘效果。

圖2 準確性評估

6.4 相似度度量實驗

行為模式可以展現(xiàn)用戶的生活習慣和行為規(guī)律，經(jīng)濟能力相似的用戶通常具有類似的行為模式，為了驗證這一假設，對基于行為模式的用戶相似度度量方法辨別不同背景（經(jīng)濟能力）的用戶的效果進行探索。

實驗中，首先基于行為模式計算每個學生對的相似度，然后基于學生間相似度矩陣采用k-means算法對所有學生進行聚類。對于每一類學生，在4個聚類中尋找其主導聚類。采用兩個指標評價該聚類效果：主導內聚度（Iadr）和主導外聚度（Io?dr）。主導內聚度指主導聚類中具有指定助學金人數(shù)和主導聚類中總人數(shù)的比例，主導外聚度指主導聚類中含有指定助學金的人數(shù)和該助學金獲得的總人數(shù)的比例。另外，為了考察引入到達時間后在本節(jié)方法中的效果，基于上述相同的實驗設置，在不考慮時間因素的情況下提取行為模式并計算相似度，然后重新進行用戶聚類。主導內聚度和主導外聚度相較于未考慮時間因素下得到的結果均顯著增大，這說明了基于時間對用戶行為模式進行挖掘得到的結果更能反映用戶生活習慣相似性。

圖3 基于學生相似度的聚類效果

7 結語

針對語義軌跡模式挖掘中沒有考慮到達時間的問題，本文提出了基于到達時間的行為模式挖掘方法，首先對包含時間信息的語義軌跡進行頻繁模式提取，然后基于挖掘到的頻繁模式對用戶計算相似度，并在真實數(shù)據(jù)集上驗證了該方法的有效性和正確性。本文提出的方法在路徑預測、朋友推薦以及不同用戶群體區(qū)分等方面具有廣泛的應用前景。未來可將其與地理軌跡特征結合起來處理，以達到更好的實用效果。