基于到達(dá)時(shí)間的行為模式挖掘?

李克華 劉志鋒 周從華

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

1 引言

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

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

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

2 相關(guān)工作

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

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

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

為了解決上述問(wèn)題，本文提出了一種基于到達(dá)時(shí)間的行為模式挖掘方法。

3 問(wèn)題定義

本節(jié)給出語(yǔ)義行為模式相關(guān)的定義

定義1語(yǔ)義點(diǎn)語(yǔ)義點(diǎn)S定義為

其中，s是用戶的停留點(diǎn)，tarrive是用戶在語(yǔ)義點(diǎn)S的到達(dá)時(shí)間。

定義2語(yǔ)義軌跡

語(yǔ)義軌跡是一個(gè)由n個(gè)語(yǔ)義點(diǎn)組成的序列。

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

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

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

4 語(yǔ)義軌跡頻繁模式挖掘

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

表1 語(yǔ)義軌跡集示例

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

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

其中，id軌跡在語(yǔ)義軌跡集中的標(biāo)識(shí)號(hào)，pos是α中最后的語(yǔ)義點(diǎn)在語(yǔ)義軌跡中的位置，t是最后一個(gè)語(yǔ)義點(diǎn)的到達(dá)時(shí)間，proj是pos以α為前綴的子序列。

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

輸入：語(yǔ)義軌跡集R，時(shí)間間隔δt，

最小支持度θ

輸出：頻繁語(yǔ)義模式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()計(jì)算到達(dá)時(shí)間差額在δt范圍內(nèi)的項(xiàng)目集，假設(shè)與p'等價(jià)的到達(dá)時(shí)間范圍G，的等價(jià)到達(dá)時(shí)間范圍G=[p'.t-δt，p'.t+δt]。

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

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

5 語(yǔ)義模式相似度

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

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

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

定義5最長(zhǎng)公共子序列給定兩個(gè)用戶語(yǔ)義行為模式P和Q，最長(zhǎng)公共子序列滿足條件：

為了突出到達(dá)時(shí)間對(duì)用戶語(yǔ)義行為模式的影響，給出了時(shí)間因子的定義。

定義6時(shí)間因子 給定用戶語(yǔ)義行為模式P，Q，當(dāng)其子序列元素一致時(shí)，元素對(duì)相似度的貢獻(xiàn)值通過(guò)時(shí)間因子來(lái)表達(dá)，定義如下：

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

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

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

6 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

6.3 語(yǔ)義軌跡頻繁模式挖掘?qū)嶒?yàn)

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

表3 基于到達(dá)時(shí)間的語(yǔ)義模式

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

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

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

圖2 展示了不同時(shí)間閾值、不同支持度得到的行為模式準(zhǔn)確度。當(dāng)頻繁模式支持度偏小時(shí)，得到的結(jié)果在不同時(shí)間閾值下沒(méi)有明顯的增加減小，因?yàn)橹С侄冗^(guò)小時(shí)，挖掘到的行為模式并非主流結(jié)果，不能有效代表一個(gè)用戶的行為模式。當(dāng)支持度在0.1以上時(shí)，挖掘到的語(yǔ)義模式更具代表性，隨著時(shí)間閾值的增加，準(zhǔn)確率也不斷提高。值得注意的是，當(dāng)時(shí)間閾值在40min～50min 以上時(shí)，準(zhǔn)確率沒(méi)有改善，還有下降趨勢(shì)，這是因?yàn)殡S著時(shí)間差增大，導(dǎo)致不同模式之間的區(qū)分度降低，從而影響了挖掘效果。

圖2 準(zhǔn)確性評(píng)估

6.4 相似度度量實(shí)驗(yàn)

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

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

圖3 基于學(xué)生相似度的聚類效果

7 結(jié)語(yǔ)

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