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

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

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

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

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

1 相關研究

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

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

2 周期模式挖掘

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

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

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

2.1 活動地點匹配

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

算法1 DBSCAN算法。

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

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

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

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

6) end for

7) while ? ≠? do

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

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

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

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

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

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

輸入其中

1) forpiinPdo

2) forpjinPdo

3) if p lace?idj≠place?idi

4)將pj加入P′

5) end for

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

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

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

9) end for

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

3 活動語義識別

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

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

3.1 特征提取

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

3.2 模型選擇

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

3.2.1 決策樹

決策樹模型呈樹形結構，在分類問題中，表示基于特征對實例進行分類的過程。決策樹學習過程包含3個步驟：特征選擇、決策樹的生成和決策樹的剪枝。

1)特征選擇。

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

樣本集合D的基尼指數為

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

2)決策樹生成。

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

本文用到的是CART算法構建分類樹。CART算法采用基尼系數作為評判準則，通過式(6)選取使得基尼系數最小的特征和對應特征取值遞歸構建二叉樹分類樹進行分類。

3)決策樹的剪枝。

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

3.2.2 基于隨機森林的活動語義分類

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

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

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

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

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

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

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

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

輸出模型的精度。

4 實驗結果與分析

4.1 實驗設置

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

圖2 簽到數據種類分布Fig. 2 Distribution of check-ins categories

圖3 簽到數據樣式Fig. 3 Examples of check-ins data

4.2 實驗結果

4.2.1 周期模式的識別

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

4.2.2 活動語義識別結果

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

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

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

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

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

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

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

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

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

5 結束語

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