基于時空周期模式挖掘的活動語義識別方法

郭茂祖，邵首飛，趙玲玲，李陽

（1. 北京建筑大學(xué) 電氣與信息工程學(xué)院，北京 100044; 2. 北京建筑大學(xué) 建筑大數(shù)據(jù)智能處理方法研究北京市重點實驗室，北京 100044; 3. 哈爾濱工業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001）

活動語義識別是指從人類的時空軌跡數(shù)據(jù)或離散的位置序列中挖掘出人類的活動信息[1]。智能移動終端的廣泛應(yīng)用提供了海量的個體位置相關(guān)的時空數(shù)據(jù)，如社交媒體簽到數(shù)據(jù)、GPS(global positioning system)軌跡數(shù)據(jù)和手機(jī)信令數(shù)據(jù)等[2]。這些數(shù)據(jù)為精細(xì)粒度下個體的活動識別提供了有力支撐。相比原始的時空軌跡數(shù)據(jù)或位置序列信息，帶有語義的活動軌跡數(shù)據(jù)更能直觀地反應(yīng)人類的具體活動，這有助于深入了解每個個體的生活模式，發(fā)現(xiàn)個體的個性需求，為個體提供定制化服務(wù)，也可以發(fā)現(xiàn)與個體活動模式相同或相似的群體，進(jìn)而識別群體的共性特征和需求[3]。這些信息的挖掘可以用于配置交通資源和資源規(guī)劃[4]，如公交車的班次和地點的設(shè)定、共享單車的投放量和投放地點、商場的選址等，從而達(dá)到優(yōu)化社會資源配置、精細(xì)化滿足各種群體的不同需求的目的[1,5-6]。

人類的活動軌跡在空間上是多重交叉的[7]，在時間上表現(xiàn)出序列性和一定的周期性[8-10]。已有的大部分方法都是在GPS軌跡數(shù)據(jù)的空間特征—活動地點的POI(point of interest)數(shù)據(jù)和運動特征(速度、加速度)之上構(gòu)建分類模型，進(jìn)而識別用戶的活動語義[11-15]。該類方法忽略了活動軌跡的時間特性，導(dǎo)致該類方法的識別結(jié)果過度依賴于POI獲取的準(zhǔn)確性，而忽視了用戶某些活動，難以準(zhǔn)確獲取相應(yīng)POI的實際問題，而且容易混淆用戶在不同時間訪問相近的地方發(fā)生的不同活動，本文在文獻(xiàn)[16-17]提取用戶活動軌跡周期模式的方法上使用LombScargle[18-19]方法挖掘用戶軌跡數(shù)據(jù)的周期作為用戶活動特征中的周期特征，再結(jié)合用戶活動的持續(xù)時間、活動中心點附近POI，及活動發(fā)生的年份、月份、季節(jié)、日期、是否是節(jié)假日和是否是周末等時間特征[15]，使用隨機(jī)森林分類器挖掘用戶活動語義。

1 相關(guān)研究

現(xiàn)有的活動語義識別方法可以分為：基于空間特征的識別方法和基于運動特征的識別方法。文獻(xiàn)[11]從用戶活動的空間角度，采用活動地點的POI數(shù)據(jù)挖掘語義信息。并且考慮到POI數(shù)據(jù)不均勻以及POI在不同地區(qū)主題下對用戶活動的影響度不同等因素，引入隱含狄利克雷分布 (latent dirichlet allocation，LDA)主題模型提取活動地點POI的主題特征。通過地區(qū)內(nèi)POI與主題的相關(guān)程度來確定在該主題下POI對用戶活動的影響度，從而確定用戶在活動地點產(chǎn)生的活動模式。文獻(xiàn)[12]使用移動基站提供的數(shù)據(jù)集結(jié)合Open-StreetMap上的POI信息對用戶的行為進(jìn)行識別和預(yù)測。文獻(xiàn)[13]設(shè)計自助數(shù)據(jù)采集系統(tǒng)，以志愿者的方式采集數(shù)據(jù)，并利用用戶的軌跡、年齡、收入、居住等特征和支持向量機(jī)(support vector machine, SVM)模型來識別用戶的活動語義。文獻(xiàn)[14]利用社交簽到數(shù)據(jù)，融合簽到地點頻次等信息識別活動語義。文獻(xiàn)[15]采用聚類方法獲取空間熱度特征并利用極限梯度提升 (eXtreme gradient boosting，XGBoost)建模識別用戶活動模式。文獻(xiàn)[20]逐步提取用戶的實時位置，將運動過程中訪問的地點與人類的活動相關(guān)聯(lián)起來，進(jìn)而推斷用戶進(jìn)行的活動。上述方法的核心思想是從活動軌跡點的空間信息提取特征來建模，但是用戶的軌跡信息在空間和時間上是緊密相連的，因此該類方法忽略了時間特性，導(dǎo)致該類方法的識別結(jié)果過度依賴于POI獲取的準(zhǔn)確性而忽視了用戶某些活動難以準(zhǔn)確獲取相應(yīng)POI的實際問題，而且容易混淆用戶在不同時間訪問相近的地方發(fā)生的不同活動。

人類活動具有顯著的周期性特征[9]，已有的研究就軌跡的周期性進(jìn)行挖掘，如文獻(xiàn)[16]中就移動對象頻繁訪問某一地方的核心點(reference spot)提取用戶空間信息，并融合傅里葉變換(fourier transform)獲取用戶的時間信息。通過提取核心點提取用戶的空間信息，再通過傅里葉變換檢測活動發(fā)生的周期，提取用戶的時間信息。使用傅里葉變換挖掘用戶活動周期時必須獲取軌跡數(shù)據(jù)的均值采樣，但是由于天氣的原因無法獲取均值采樣的軌跡數(shù)據(jù)。此時必須通過線性插值的方法使不規(guī)則的樣本變成均值的軌跡。但是由于軌跡數(shù)據(jù)量龐大的原因，這種插值會帶來巨大的計算量。文獻(xiàn)[17]在此基礎(chǔ)上，先將單個用戶軌跡數(shù)據(jù)運用基于密度的帶噪聲應(yīng)用空間聚類(density based spatial clustering of application with noise，DBSCAN)，聚類后獲取用戶的活動軌跡點，再結(jié)合OpenStreetMap中的POI信息進(jìn)行地點匹配得到帶有地點特征的軌跡數(shù)據(jù)，最后使用LombScargle[18,21]算法挖掘用戶活動的周期。該算法可以直接從非規(guī)則采樣的軌跡中挖掘出用戶的活動周期。但是文獻(xiàn)[16-17]均是挖掘用戶軌跡的周期模式，并沒有結(jié)合用戶活動產(chǎn)生的軌跡點的空間信息挖掘用戶的活動語義。

2 周期模式挖掘

針對個體的部分活動存在周期性這一特征，本文從訪問位置的周期性挖掘出發(fā)，將周期性活動的周期提取、停留時間、周期性活動的相關(guān)POI進(jìn)行提取，構(gòu)成以時空周期性為核心的特征表示。

單個用戶產(chǎn)生的活動軌跡表示為一個三維的時空序列，則用戶一天的活動序列S可以表示為

式中： l ng 、 l at、t表示軌跡點的經(jīng)度、緯度、時間，i1、in表示用戶進(jìn)行第i個活動的第一和最后一個軌跡點。需要說明的是，活動軌跡并不總是連續(xù)的，它只表示用戶在某地發(fā)生某個活動時產(chǎn)生的軌跡。

2.1 活動地點匹配

活動地點匹配是將原始的軌跡序列S依據(jù)空間距離和時間距離使用DBSCAN算法進(jìn)行聚類，進(jìn)而將聚類后每個軌跡點所在的軌跡簇ID標(biāo)記為該軌跡點的place-id[22]。空間上的距離使用經(jīng)緯度之間的歐幾里得距離，時間距離使用軌跡點的時間戳差值，最后將空間距離和時間距離的算術(shù)平均值作為聚類距離，如式(1)。聚類后為每個聚類簇分配一個ID作為分類簇中所有對應(yīng)軌跡點的place-id，聚類的同時能夠舍棄一些離群點，聚類后得四維向量：(lngi,lati,ti,place_idi)

算法1 DBSCAN算法。

輸入樣本集D=(x1,x2,···,xn),領(lǐng)域參數(shù)(ε,MinPts)，樣本距離度量方式。

1) 初始化核心對象集合 ? =?，聚類簇個數(shù)k=0 ，未訪問的樣本集合 Γ =D，簇劃分C=?

2) forjin 1 ,2,···,ndo

3)通過距離度量方式，找到xj的 ε 鄰域子樣

6) end for

7) while ? ≠? do

8) 隨機(jī)選取 ? 中的一個核心對象o，?cur={o}，

9) if?cur=?

10)C={C1,C2,···,Ck},?=??Ck

continue

11) else

12)?=??Ck

13) end if

14)在 ?cur中取出一個核心對象o′通過鄰域距離閾值 ε 找出所有的 ε ? 鄰域Nε(o′)， ? =Nε(o′)∩Γ，Ck=Ck∪?，Γ=Γ??，?cur=?cur∪(?∩?)?o′

15) end while

輸出簇劃分C={C1,C2,···,Ck}。

2.2 周期模式挖掘

對于GPS軌跡數(shù)據(jù)，一個連續(xù)采樣的軌跡滿足在某個軌跡簇pi中對任意連續(xù)的i,j使得成立。一個不連續(xù)采樣的軌跡滿足存在連續(xù)的i,j使得成立。以往挖掘序列周期模式使用的方法為傅里葉變換(fourier transform)和自相關(guān)(autocorrelation)[8,16]。使用傅里葉變換有一個重要的前提條件，要求輸入的樣本必須是均值采樣。然而，由于天氣和采樣設(shè)備故障原因，自然采集的軌跡基本上都是不規(guī)則的。因此使用傅里葉變換之前需要進(jìn)行線性插值，將不規(guī)則樣本補全。對于大量的軌跡數(shù)據(jù)來說，線性插值的計算量相當(dāng)大。LombScargle算法由文獻(xiàn)[18]提出用于檢測不規(guī)則采樣時間序列周期，并由文獻(xiàn)[21]用LombScargle功率-頻率圖檢測出不規(guī)則間隔的時間序列周期。該算法能夠省去計算量大的線性插值，并且能夠識別出序列中所有的周期[23]。

對于時間序列來說，xj是采樣tj時刻對應(yīng)的樣本值j=1,2,···,N。LombScargle圖能夠反應(yīng)出序列的周期，LombScargle周期圖通過式(1)計算得出：

式中 τ 是每個f特定的值，以保證對于不規(guī)則樣本的時移不變性，其中 τ 和f的關(guān)系為

對于LombScargle圖，圖中每個峰值表示一個周期。LombScargle圖是通過錯誤預(yù)警概率(false alarm probability)來表示該峰值的顯著性，其計算為

從式(2)的分布得出，一個有效的功率峰值z，在給定一個誤差 α 時必須要超過統(tǒng)計顯著性的值，可由式(3)計算得出：

算法2周期模式挖掘算法。

輸入其中

1) forpiinPdo

2) forpjinPdo

3) if p lace?idj≠place?idi

4)將pj加入P′

5) end for

6)P′代入式(1)求出PSL的峰值pmax,對應(yīng)頻率fi, 取倒數(shù)表示周期Ti

7)按照式(2)求出pmax的錯誤預(yù)警概率Pri

8)qi=ti,place?idi,Ti,Pri將qi加入Q中

9) end for

輸出帶有周期的GPS軌跡序列Q=

3 活動語義識別

基于周期模式挖掘的語義識別流程如圖1。首先，將用戶的活動軌跡聚類成若干個軌跡簇，然后為不同軌跡簇中的每個軌跡點分配一個獨特的ID作為識別周期模式的地點標(biāo)識。之后使用這些地點標(biāo)識識別出每個活動發(fā)生的周期模式，計算活動軌跡中心點，利用軌跡中心點獲取活動地點附近的POI信息，最后將這些特征作為隨機(jī)森林分類器的輸入識別用戶的活動義。

圖1 本文提出的方法總體流程Fig. 1 Overall procedure of our proposed method

3.1 特征提取

時空軌跡具有序列性、時空緊密性、不規(guī)矩的時間間隔、空間層次性和包含背景語義信息等特征。序列性指前后2個相鄰的軌跡點在時間上有先后順序。緊密性指軌跡的空間特征和時間特征緊密相連，不能分割。不規(guī)則的時間間隔指現(xiàn)實生活中由設(shè)備采集到的數(shù)據(jù)是非均值采樣。空間層次性指人的時空軌跡是區(qū)域聚集性和在不同板塊下有不同的層次表示。背景語義能一定程度上反映活動者在這個地方進(jìn)行的活動類型。針對這些特性，本文加入了用戶活動參考點的經(jīng)緯度作為空間特征。通過地圖API (application programming interface)獲得的POI信息，作為背景語義特征。進(jìn)行活動的起始時間、活動的時長、活動的日期(活動發(fā)生的年份、月份、日期、是否周末)作為時間特征，以及活動的周期特征(包含識別周期過程中每個周期對應(yīng)的錯誤預(yù)警概率)。

3.2 模型選擇

隨機(jī)森林是采用有放回抽樣的方式從訓(xùn)練集中選取一定比例的樣本和一定個數(shù)的特征作為子訓(xùn)練集，使用多個決策樹在不同的子訓(xùn)練集中進(jìn)行分類，并且將最后多數(shù)分類器得到的分類結(jié)果作為最終分類結(jié)果的分類器。該分類器有較好的抗噪性，并且在高維和大數(shù)據(jù)的數(shù)據(jù)集下有很好的分類性能，本文采用隨機(jī)森林算法識別活動語義。

3.2.1 決策樹

決策樹模型呈樹形結(jié)構(gòu)，在分類問題中，表示基于特征對實例進(jìn)行分類的過程。決策樹學(xué)習(xí)過程包含3個步驟：特征選擇、決策樹的生成和決策樹的剪枝。

1)特征選擇。

通過計算并比較特征的信息熵或者基尼系數(shù)進(jìn)行特征選擇。在分類問題中，設(shè)有K個類別，樣本屬于第k個類別的概率為pk,則概率分布的基尼系數(shù)由式(4)得到：

樣本集合D的基尼指數(shù)為

式中Ck為數(shù)據(jù)集D中屬于k類的樣本子集。如果數(shù)據(jù)集D根據(jù)特征A在某個取值a上進(jìn)行分割，得到D1、D22個部分后，那么在特征A下集合D的基尼系數(shù)表示為

2)決策樹生成。

決策樹生成有ID3、C4.5和分類回歸樹 (classification and regression tree，CART)。

本文用到的是CART算法構(gòu)建分類樹。CART算法采用基尼系數(shù)作為評判準(zhǔn)則，通過式(6)選取使得基尼系數(shù)最小的特征和對應(yīng)特征取值遞歸構(gòu)建二叉樹分類樹進(jìn)行分類。

3)決策樹的剪枝。

決策樹生成算法遞歸地產(chǎn)生決策樹，直到不能進(jìn)行下去為止。這樣的算法產(chǎn)生的樹對訓(xùn)練數(shù)據(jù)分類很準(zhǔn)確，但對未知數(shù)據(jù)集的分類往往沒有那么準(zhǔn)確—過擬合。解決過擬合的方式是考慮生成樹的復(fù)雜度，對已經(jīng)生成的決策樹進(jìn)行簡化—剪枝。

3.2.2 基于隨機(jī)森林的活動語義分類

隨機(jī)森林是由很多獨立的決策樹組成的一個森林，每棵樹之間相互獨立，在最終模型組合時，通過投票的方式?jīng)Q定最終的分類結(jié)果。

算法3 活動語義識別算法。

輸入提取完的活動軌跡特征矩陣M。

1)將特征矩陣分成訓(xùn)練集M1和測試集M2。

2)從訓(xùn)練集M1中隨機(jī)有放回選取一定比例的樣本M1i(i表示第i棵決策樹)作為一棵決策樹的輸入樣本。

3)通過CART方法構(gòu)建n個決策樹，將所有決策樹的分類結(jié)果概率最高的作為隨機(jī)森立分類器的結(jié)果。

4)n從1～200變化，得到分類器最好精度時對應(yīng)的決策樹的個數(shù)。

5)將訓(xùn)練完成的分類器放在測試集上測試。輸出模型的訓(xùn)練和測試精度。

輸出模型的精度。

4 實驗結(jié)果與分析

4.1 實驗設(shè)置

本文采用的數(shù)據(jù)是來自Yang等[24]通過Foursquare提供的開發(fā)者API收集的來自紐約和東京2個城市用戶的簽到數(shù)據(jù)，數(shù)據(jù)有8個特征：用戶ID、活動地點ID、場地類別ID、場地類別名稱、經(jīng)度、緯度、UTC時間、時間偏移量。東京數(shù)據(jù)集TKY包含57萬條數(shù)據(jù)，紐約數(shù)據(jù)集NYC包含22萬條數(shù)據(jù)，這2個城市的簽到數(shù)據(jù)集時間跨度超過10個月，從2012年4月12日—到2013年2月16日紐約1 083個用戶和東京2 293個用戶的簽到數(shù)據(jù)記錄。在有無周期對比實驗中本文根據(jù)簽到地點名稱采用多專家決策的方法最終標(biāo)記為12類(Shopping, Restaurant, Work,Travel, Entertainment, Service, Meeting, Education,Sports, Rest, Medical, Art)。實驗中，為了能識別用戶的周期，設(shè)定少于5次訪問次數(shù)的地點為用戶不常去的地點，沒有周期性,實驗中去除了這些數(shù)據(jù)。TKY簽到數(shù)據(jù)中標(biāo)簽分布如圖2，標(biāo)記完的簽到數(shù)據(jù)如圖3。

圖2 簽到數(shù)據(jù)種類分布Fig. 2 Distribution of check-ins categories

圖3 簽到數(shù)據(jù)樣式Fig. 3 Examples of check-ins data

4.2 實驗結(jié)果

4.2.1 周期模式的識別

識別周期模式中，識別的周期通常指最小正周期，因此需要傳入周期的取值范圍限制識別出周期的大小。去除10個月少于5次簽到的數(shù)據(jù)周期為(0, 1 440)小時(1個月按30 d計算)，某個用戶的某個活動周期—頻率圖如圖4所示，通過圖5中周期—頻率圖得到最大峰值對應(yīng)的周期為24.15 h。這表明用戶在這個地方的活動每隔24.15 h會發(fā)生一次。

4.2.2 活動語義識別結(jié)果

為了驗證周期特征對活動語義識別的有效性，本文在相同的實驗條件下，對比了加入和不加入周期模式特征進(jìn)行活動語義的識別的性能。分別使用準(zhǔn)確度、精準(zhǔn)率、召回率、F1值對分類結(jié)果進(jìn)行的評價，其計算為

式中：TP、 FP、 TN、FN表示將正類分正確、將正類分錯誤、將負(fù)類分正確、負(fù)類分錯誤的個數(shù)。

圖4 某個特定活動對應(yīng)的LombScargle功率—頻率Fig. 4 LombScargle power-frequency diagram corresponding to a specific activity

圖5 有無周期的分類結(jié)果Fig. 5 The histogram without or with period

在周期模式特征中加入錯誤預(yù)警概率作為聯(lián)合周期特征，隨機(jī)森林最后參數(shù)設(shè)置為n-estimator=84，在TKY數(shù)據(jù)集上得到的實驗結(jié)果如圖5所示。加入周期特征后準(zhǔn)確率從0.871提升到0.968，精準(zhǔn)率從0.874提升到0.973，召回率從0.826提升到0.951，F(xiàn)1值從0.848提升到0.962。由數(shù)值結(jié)果可以看出加入周期特征后在各個分類結(jié)果中都取得了10%以上的提升。

分別繪制每個分類的結(jié)果，得到加入周期特征前后的混淆矩陣如圖6、圖7，矩陣橫軸表示預(yù)測的類別，縱軸表示真實的類別。方格對角線的值表示識別正確的類別占總類別的比值，其中空白表示值為0，即在預(yù)測樣本中完成分類正確。從圖6中可以看出，沒有加入周期前模型對Edu(Education)、 Spo(Sport)、 Res(Restaurant)這幾種活動的識別精度較低(0.726，0.689，0.707），加入周期模式特征后這些活動的識別效果得到了20%左右的提升，識別精度均超過0.9。從圖6可以看出，Edu和Sho、 Spo和Sho、 Res和Ser(Service)混淆得最為嚴(yán)重，其原因在于人類在學(xué)習(xí)、運動的活動中，進(jìn)行活動的時間和場所受個人偏好影響比較大，這些活動的持續(xù)時間較長，在特征方面容易與購物、飲食和社會服務(wù)（銀行，派出所，居委會，政府等社會公共設(shè)施內(nèi)進(jìn)行的活動）等行為混淆。由于人類的這些行為周期性比較明顯，加上周期模式特征后，這些行為會被更加準(zhǔn)確地識別出來。

圖6 不加入周期特征的混淆矩陣Fig. 6 The confusion matrix without period

圖7 加入周期特征的混淆矩陣Fig. 7 The confusion matrix with period

為了驗證本文方法有更好的識別精度，本文和文獻(xiàn)[24-25]在相同的數(shù)據(jù)集下(東京市簽到數(shù)據(jù)集、紐約市數(shù)據(jù)集)進(jìn)行實驗。本文和文獻(xiàn)[24-25]都采簽到地點名稱作為用戶的活動語義標(biāo)簽，TKY數(shù)據(jù)集包含的標(biāo)簽個數(shù)為247個，NYC包含的標(biāo)簽個數(shù)為251個。實驗結(jié)果如表1，LIAO等[25]采用2個基學(xué)習(xí)器和一個元學(xué)習(xí)器將時間特征和序列特征整合用于預(yù)測用戶的活動目的和活動位置，YANG等[24]提出一種上下文感知框架對用戶活動偏好進(jìn)行推理，從而識別用戶的活動語義。實驗結(jié)果如表1所示，在NYC數(shù)據(jù)集上本文的識別方法相對于LIAO提升精度35.9%，相對于YANG提升了10.8%。在TKY數(shù)據(jù)集上分別提升了37.8%和23.7%。實驗結(jié)果表明周期模式挖掘算法具有更好的識別精度，也驗證了用戶在長時間活動軌跡中周期性的重要作用。

5 結(jié)束語

本文通過對比是否加入周期特征的方法，驗證了加入周期模式能有效提高活動語義的識別性能；同時，在與LIAO、YANG方法的對比中可以發(fā)現(xiàn)本文的方法具有更好的識別精度，驗證了本文方法的有效性。本文充分利用了人的部分活動帶有顯著的周期性這一特點，挖掘了歷史活動的周期模式，來提高對當(dāng)前活動的識別的準(zhǔn)確性。因此本文方法更適合個體活動記錄的時間跨度較大的數(shù)據(jù)場景，以便更好地捕捉活動的周期特征。本文的活動語義識別方法是基于周期模式特征為主要特征，因此對于人的部分不頻繁的活動模式識別效果不佳，這也是未來要研究的方向之一。