郭茂祖，張 彬，趙玲玲，張 昱，4

（1.北京建筑大學電氣與信息工程學院，北京 100044；2.建筑大數(shù)據(jù)智能處理方法研究北京市重點實驗室（北京建筑大學），北京 100044；3.哈爾濱工業(yè)大學計算機科學與技術學院，哈爾濱 150001；4.深部巖土力學與地下工程國家重點實驗室（中國礦業(yè)大學），北京 100083）

（?通信作者zhaoll@hit.edu.cn）

0 引言

移動互聯(lián)網的迅速發(fā)展促進了基于位置的社交網絡的形成［1］。社交網絡融合了社交關系和位置信息，用戶能隨時隨地分享包括位置信息、活動信息、個體情感信息、空間環(huán)境信息等動態(tài)內容，這些由活動所產生的移動性時空數(shù)據(jù)對基于位置的服務研究提供了數(shù)據(jù)基礎，可用于挖掘用戶的移動特征、活動偏好和生活模式。

對人類移動性時空數(shù)據(jù)的建?？梢詮臅r間和空間兩個維度進行考慮。在時間維度上，人類的活動表現(xiàn)出一定的序列性［2-3］和周期性［4］，而在空間維度上人類的活動則表現(xiàn)出一定的區(qū)域聚集性［5-6］。在建模個體移動的序列相關性中基于馬爾可夫鏈的研究取得很好的成果，Cheng等［7］在原始馬爾可夫鏈的基礎上進行改進引入了一種因式分解個性化馬爾可夫鏈；Zhang 等［8］則提出了位置轉移概率圖；Cho 等［1］建立了一個基于社會網絡結構的人的移動模型，用于解釋人類移動的周期性行為；Wang 等［4］建模了一種高斯混合模型將人類移動的規(guī)律性和一致性進行整合。上述研究都是對時間維度上的序列特征以及周期特征進行探討，缺乏對空間信息的挖掘。而人類在活動選擇上偏好于訪問人數(shù)多的地方以及熟悉的地方，各種活動地點也有不同的屬性。顯然，這些特性的表達將對活動語義的識別提供更豐富的信息支持，但目前仍然缺少針對這些屬性的研究。

針對上述問題，本文提出了一種結合時間特征和空間特征的人類活動語義識別方法。空間特征中的空間熱點區(qū)域特征用于表示人類的熱點訪問區(qū)域，經緯度特征表示訪問位置，時間特征則是基礎特征，記錄人類活動的時間信息。本文通過具有噪聲的基于密度的聚類（Density-Based Spatial Clustering of Applications with Noise，DBSCAN）得到空間熱度特征；時間特征表達人的周期和序列活動模式。相比較于K均值聚類算法（K-means clustering algorithm，K-means），DBSCAN 不需要指定簇類的數(shù)量，能夠發(fā)現(xiàn)任意形狀的簇，對噪聲點也可以很好地識別?？臻g中的熱點區(qū)域的數(shù)量不定，分布不均勻，受地理與地形的影響。因此采用K-means 聚類算法不能有效挖掘出空間熱點區(qū)域。最后，利用極限梯度提升（eXtreme Gradient Boosting，XGBoost）算法來進行編碼，建立結合空間經緯度特征、區(qū)域熱度特征、時間周期特征的人類活動語義識別模型。XGBoost 是一種基于梯度提升理論的集成學習算法，有著良好的拓展性和高效性。與隨機森林、AdaBoost 集成學習算法相比，XGBoost 算法針對損失函數(shù)、正則化和并行運算等方面做了改進，同樣支持列抽樣，當訓練數(shù)據(jù)為稀疏值時還可以為缺失值或指定值設置分支的默認分裂方向，因此本文選擇XGBoost 對活動語義進行分類，提高算法的效率和識別精度。

1 相關研究

時空特征的周期性是人類活動建模中顯著的特征，工作、休息、飲食等活動具有很強的周期性。在許多對人類移動性建模的模型里都使用到了時空特征的周期性，如：Zarezade等［9］針對社交網絡中用戶的簽到行為的周期性以及其社交關系提出了一個基于周期衰減核的雙隨機點過程的概率模型；Li等［10］則提出了一種時空數(shù)據(jù)周期性檢驗和度量方法以挖掘活動行為的周期性；Rizwan 等［11-12］使用核密度估計的方法來觀察用戶的活動時空趨勢，并對空間進行回歸分析，發(fā)現(xiàn)相對于男性，女性更傾向使用社交媒體數(shù)據(jù)，而且在工作日與周末的活動上二者也表現(xiàn)出差異性。

序列特征是隱藏在人類行為當中的特征，人類的行為活動往往具有先后順序，而序列模式就是指這種從語義時空軌跡中挖掘出來的有規(guī)律的序列。Ying等［13］將活動內容標簽進行了連接，把各個活動語義串聯(lián)起來（家-工作-吃飯），然后使用頻繁模式語義挖掘來得到序列特征；Chen 等［14］將序列符號化之后，采用了一種基于序列的模式挖掘算法：STS-TPs（standing for Spatial-Temporal Semantic Trajectory Patterns）。

對于時空數(shù)據(jù)建模的無監(jiān)督方法主要是通過聚類的方法。例如對軌跡點進行聚類，各個聚類簇中的軌跡可看作具有相同的行為或進行著相同的活動。聚類的方法主要有兩種：基于距離的聚類和基于密度的聚類。為了得到用戶的行為規(guī)律，基于距離的聚類方法往往需要首先衡量軌跡的相似性，包 括CPD（Closet-Pair Distance）、SPD（Sum-of-Pairs Distanc）、DTW（Dynamic Time Warping）、LCSS（Longest Common SubSequence）、EDR（Edit Distance on Real sequence）等，其中LCSS 和EDR 對噪聲具有更好的魯棒性，而CPD 和SPD 計算開銷比較小。Redondo 等［15］將熵分析與聚類技術結合起來證實社交媒體活動中的意外行為是該城市活動意外變化所導致；Cao 等［16］提出了一種社交學習模型，根據(jù)用戶偏好和社會關系來評估興趣點，之后還將用戶地理信息整合到模型框架中，使用聚類的方法形成個性化的興趣點（Point of Interest，POI）推薦列表；Zhong 等［17］提出了一種多中心聚類算法來捕獲用戶的移動模式并開發(fā)一種用戶相似性度量的方法；Sakkari 等［18］通過使用無監(jiān)督競爭學習算法自組織圖和基于密度的聚類方法來識別和檢測人群，然后建立熵模型用于檢測城市中的異常事件；Coelho Da 等［19］提出了一種在線軌跡挖掘的框架，用于得到用戶的行為規(guī)律，其中采用了基于距離聚類的方式對軌跡段進行聚類。

在預測算法方面，近年來機器學習發(fā)展迅速，作為統(tǒng)計學和計算機科學的交叉領域、人工智能以及數(shù)據(jù)科學的核心方法，廣泛地應用于許多領域，解決了各種各樣的問題，在軌跡模式識別、活動預測等相關領域中也有著很好的效果。Liao等［20］采用了兩個基學習器和一個元學習器將時間特征和序列特征整合起來用于預測用戶的活動目的和活動位置；Lv 等［21］通過將原始的全球定位系統(tǒng)（Global Positioning System，GPS）軌跡分割從中提取出活動點，進而得出活動場所，并結合時間特征、空間特征和序列特征提出了一種增強型位置分類器用于活動預測；鄧堯等［22］則使用用戶簽到內容的短文本來進行地理定位，從短文本中提取實體，之后建立實體與位置間的概率模型，然后對候選區(qū)域進行排序選擇排名最高的位置作為結果；Fu 等［23］應用自然語言處理的方法從用戶發(fā)布Twitter 帖子中的文本內容挖掘用戶的活動類型，并根據(jù)時間和空間分布來評估得到的活動類型。

2 聯(lián)合特征和XGBoost理論

針對基于社交網絡簽到數(shù)據(jù)的人類活動語義識別問題，本文提出了基于聯(lián)合特征和XGBoost 的活動語義識別方法，該方法包括兩個主要模塊：聯(lián)合特征提取模塊和XGBoost 分類模型構建模塊。聯(lián)合特征指用戶在進行某活動時的空間特征和時間特征，空間特征指經緯度特征、區(qū)域熱度特征，其中區(qū)域熱度特征使用DBSCAN 提取出用戶活動的聚集區(qū)域（不同的簇），然后計算各個簇中包含元素的數(shù)量，將空間中的區(qū)域的熱度量化作為該空間區(qū)域的熱度特征；時間特征指時間信息中的季節(jié)、月份、星期、工作日、時間點；將以上特征組成特征向量用于XGBoost 的輸入通過訓練學習構建分類模型。圖1概述了本文方法的模型架構。

圖1 基于聯(lián)合特征和XGBoost的活動語義識別方法框架Fig.1 Framework of activity semantic recognition method based on joint features and XGBoost

2.1 特征提取

簽到數(shù)據(jù)信息中一般包含4 個主要信息(U，L，T，A)，U 表示User 用戶，L 表示Location 具體地點，T 表示Time，A 表示Activity 即進行的活動或者一些用戶在當前時間位置所記錄的文本、圖片、視頻等信息。

本文從空間、時間兩個維度進行特征提取，其中空間特征除了經緯度特征之外還針對人群的行為特點來提取，即個體進行特定活動時具有較大概率選擇訪問熱度高、訪問人數(shù)多的區(qū)域，因此采用基于密度的聚類方法DBSCAN 得到這些高熱度的訪問區(qū)域，并將其結果量化，從而得到空間特征。

時間序列特征是指人類不同活動行為之間的序列相關性，在移動軌跡問題中主要是從時間序列中獲得，但是對于簽到數(shù)據(jù)來說存在時間間隔不固定、簽到次數(shù)不固定等問題，不能夠有效地從時間序列中得到序列特征。時間周期特征主要指人類相同活動之間的周期相關性，包含時間數(shù)據(jù)中提取的季節(jié)、月份、工作日、小時等特征，對于時間特征是指在不同天、月、季節(jié)在同一時間進行活動的周期性。

2.1.1 基于DBSCAN聚類的空間特征提取

DBSCAN 是一種典型的基于密度的聚類算法，相比較于K-means這種只適用于凸樣本集的聚類，DBSCAN 還適用于非凸樣本集。DBSCAN 的顯著優(yōu)點就是聚類速度快且能夠有效處理噪聲點和發(fā)現(xiàn)任意形狀的空間聚類，該算法利用基于密度的聚類概念，要求聚類空間內所包含的對象數(shù)目不小于給定閾值，過濾低密度區(qū)域發(fā)現(xiàn)稠密樣本點，同一類別的樣本之間緊密連接。在空間上人類活動表現(xiàn)出一定的區(qū)域聚集性，而實際的地理位置上確實存在一些熱點區(qū)域，例如繁華的市中心、商業(yè)步行街、網紅餐廳、著名景點等。本文研究使用的數(shù)據(jù)集是FourSquare 的公共簽到數(shù)據(jù)集，其實際簽到位置圖如圖2 所示，其簽到位置熱力圖如圖3 所示，K-means、DBSCN聚類結果分別如圖4、圖5所示。

結合簽到位置以及熱力圖可以發(fā)現(xiàn)有一些地點，人們對于其的訪問次數(shù)要比其他地方多很多，本文基于這一空間中的熱點區(qū)域訪問量大的特點，考慮在識別人類的活動語義時人們對于此類地區(qū)的訪問可能性應大于其他地方。因此在識別的時候采取DBSCAN 聚類方法將這一空間特征提取量化，作為表達活動語義的特征之一。算法步驟如下。

算法1 DBSCAN聚類算法。

輸入 n 個樣本的數(shù)據(jù)集D，半徑參數(shù)ε，鄰域密度閾值MinPts；

輸出 樣本集合的聚類C。

1）標記所有對象為unvisitied；

2）Do

3） 隨機選擇一個unvisitied對象p；

4） 標記p為visited

5） If p的ε鄰域至少由Minpts個對象：

創(chuàng)建一個新簇C，并把p添加到C；

令N為p的ε鄰域中的對象集合

For N中的每個點p：

If p是unvisited：

標記p為visited；

If p 的ε 鄰域至少有MinPts 個對象，把這些對象添加到N；

If p還不是任何簇的成員，把p添加到C；

End For

輸出C

6） Else 標記p為噪聲

7）Until沒有標記為unvisited的對象

圖2 紐約市簽到數(shù)據(jù)地理投影Fig.2 Geographic projection of New York city check-in data

圖3 紐約市簽到位置熱力圖Fig.3 Heat map of New York city check-in locations

從K-means 和DBSCAN 聚類結果可以看出，K-means 聚類結果中各類別以區(qū)域劃分，而DBSCAN 則是以區(qū)域內訪問量即簽到點的密度劃分，因此可以更好地挖掘空間區(qū)域熱度特征。所以本文選取DBSCAN 聚類方法，并從聚類結果中提取了兩個特征：聚類的類別標簽、各個聚類結果簇中包含元素的數(shù)量。兩個特征均反映空間區(qū)域的熱度特征，對于那些訪問量大的熱點區(qū)域，其簇中的點多占比就大，人們再訪問其地點時的可能性就高。從空間中得到的區(qū)域熱度特征是基于對區(qū)域的訪問偏好所提取的。

2.1.2 時間特征提取

對于簽到數(shù)據(jù)來說，存在用戶簽到時間的不規(guī)律性、簽到間隔的不確定性，整個簽到行為具有很大的隨意性，這就導致了簽到數(shù)據(jù)集本身稀疏的問題。本文提取了季節(jié)特征season、月份特征month、日特征day、星期特征week、工作日特征workday、時刻特征hour1、時刻特征hour2，其中month、day、week、hour1 從協(xié)調世界時（Universal Time Coordinated，UTC）時間信息中獲得，hour1的精度為小時向上取整。

圖4 基于K-means聚類的熱度分類結果Fig.4 Heat classification results based on K-means clustering

圖5 基于DBSCAN聚類的熱度分類結果Fig.5 Heat classification results based on DBSCAN clustering

季節(jié)特征season 按紐約氣候特征，劃分3～5 月為春季、6～8月為夏季、9～11月秋季、12～2月為冬季。

工作日特征workday 周六日為休息時間，其余為工作時間。時刻特征精度為小時分為兩種特征hour1 和hour2，hour1為一天當中所屬小時24 小時制，hour2 為一周當中所屬小時7*24 小時制。其余的月份month、日day、星期week 直接從數(shù)據(jù)中提取。各特征計算方法見式（1）～（3）：

2.2 基于XGBoost的用戶活動語義識別

XGBoost是傳統(tǒng)Boosting方法的一種，Chen等［24］首次提出此算法。對于包含n 個樣本m 個特征的訓練集Data=｛（xi，yi）｝，i=1，2，…，N。XGBoost 預測值由多個分類回歸樹（Classification And Regression Tree，CART）構成的集成模型所得，表示為：

式中：K為決策樹數(shù)量；fk(xi)為第k棵CART對數(shù)據(jù)集中第i個樣本計算分值；F為所有CART函數(shù)所構成的函數(shù)空間。

XGBoost 算法中模型學習的目標函數(shù)考慮損失函數(shù)和正則項兩部分，正則項用于控制模型復雜度，避免過擬合，表達式見式（5）：

式中：T 是葉子節(jié)點總數(shù)，r 代表控制葉子數(shù)量權重的參數(shù)，wj為第j個葉子的權重，ft是樹的模型函數(shù)。

XGBoost 對損失函數(shù)采用了二階泰勒展開，同時用到了一階和二階導數(shù)，在代價函數(shù)中加入了正則項，用于控制模型的復雜度?？s減（Shrinkage）技術削弱了每棵樹的影響，列特征二次采樣，可以減少計算同時降低過擬合。對于高維稀疏性數(shù)據(jù)XGBoost 采用了一種稀疏感知的分割搜尋算法，對于樣本在某特征缺失無法劃分時，將樣本分別劃分到左節(jié)點和右節(jié)點，然后計算其增益最終劃分到增益大的那邊。XGBoost還具有高效性，在訓練開始時會進行一遍預處理來提高之后每次迭代的效率，多線程的并行計算也會減少計算時間的開銷。XGBoost算法步驟如下：

算法2 XGBoost算法。

輸入 訓練集樣本Data=｛（x1，y1），（x2，y2），…，（xm，ym）｝，最大迭代次數(shù)k，損失函數(shù)L；

輸出 XGBoost模型。

1）循環(huán)增加一棵CART ft(xi)

2）采用貪婪算法建樹，對迭代輪數(shù)t=1，2，…，k有：

①對樣本i=1，2，…，m，計算損失函數(shù)的一階和二階導數(shù)（取負值）：

②利用（xi，gti），（xi，hti），擬合CATR，得到第t 課樹，其對應的葉子節(jié)點區(qū)域為Rij(j=1，2，…，J)，其中J 為新添加樹的葉子節(jié)點數(shù)。

③對葉子區(qū)域j=1，2，…，J，計算最佳擬合值：

④計算節(jié)點分裂的最優(yōu)增益：

3）用構建好的樹迭代優(yōu)化函數(shù)空間：

4）重復1）直到生成第k棵樹。

3 實驗設計與結果展示

3.1 數(shù)據(jù)集描述

本文實驗采用的數(shù)據(jù)集［25］是從2012 年4 月12 日到2013年2 月16 日從Foursquare 上收集的公共簽到數(shù)據(jù)，數(shù)據(jù)集總共包含8列，分別是：1）用戶ID（user_id）；2）場地ID（Foursquare 編碼）；3）場地類別ID（Foursquare 編碼）；4）場地類別名稱（Foursquare 編碼）；5）緯度；6）經度；7）時區(qū)偏移量（分鐘）；8）UTC 時間。涉及227 428 條簽到信息、1 000 多位用戶的記錄。簽到數(shù)據(jù)示例如表1 所示，此示例數(shù)據(jù)未包含場地ID、場地類別ID、時區(qū)偏移量。

表1 用戶簽到數(shù)據(jù)示例Tab.1 Examples of user check-in data

3.2 實驗設置

在相同實驗條件下，從聯(lián)合特征的有效性和識別算法的性能兩個方面對本文方法的有效性進行了驗證。在聯(lián)合特征有效性方面，采用不同的特征組合進行實驗結果的比較和分析；在方法性能評估方面，將本文基于聯(lián)合特征和XGBoost 方法（Joint Feature and XGBoost algorithm，JF-XGBoost）與CAH（Context-Aware Hybrid）方 法［20］、STAP（Spatio Temporal Activity Preference）方法［25］，在相同數(shù)據(jù)集下，以前k 個分類準確率Acc@top-k來進行比較。

XGBoost 參數(shù)主要分為三大類：通用參數(shù)、Booster 參數(shù)和學習目標參數(shù)。調參調整的是Booster 參數(shù)，通過窮舉搜索所有候選參數(shù)，循環(huán)遍歷得到最優(yōu)的參數(shù)，利用的是GridsearchCV 網格搜索算法，參數(shù)優(yōu)劣的評價標準是測試集準確率的高低。候選參數(shù)主要考慮：生成最大樹的數(shù)目n_estimator，決定最大的迭代次數(shù)；學習率learning_rate，控制運行速度和準確率；樹的最大深度max_depth，用于控制模型對樣本的擬合程度。本文XGBoost 模型實驗參數(shù)設置為：

n_estimators=1 200，learning_rate=0.1，max_depth=7，objective='multi：softprob'。

3.3 實驗結果

時間特征和聯(lián)合特征的對比實驗結果如圖6 所示。實驗結果表明，基于聯(lián)合特征模型在進行活動語義識別時效果更好，在具體數(shù)值上基于時間特征的模型識別準確率為0.300 46，基于聯(lián)合特征的模型準確率為0.586 7，模型的識別準確率提高了28個百分點。

圖7是XGBoost識別模型的混淆矩陣，由于本文以簽到位置的簽到點名稱為標簽，類別眾多共247 類，其混淆矩陣太密集，因此本文對簽到點的名稱進行了歸類總結，將247 類歸為12 類用于展示說明。從混淆矩陣中發(fā)現(xiàn)Restaurant 活動的識別中出現(xiàn)了較多問題，許多錯例被識別為Restaurant 項，出現(xiàn)這一問題從數(shù)據(jù)上分析是因為各項活動數(shù)目不均衡，Restaurant 項在所有數(shù)據(jù)中最多。簽到數(shù)據(jù)在時間上，Restaurant項幾乎包含所有時間點，并且簽到數(shù)據(jù)集中只有簽到時間，沒有活動開始時間、持續(xù)時間和結束時間；空間上實際生活中存在一樓消費、二樓餐飲的設置，這樣不同活動會在空間位置上重疊，因此導致其在時間特征與空間特征上具有很大相似性，所以在識別中會出現(xiàn)較多的問題。人們在進行簽到時也偏向于簽到那些新奇的地方，對于日常的活動行為記錄相對較少，這也不利于活動行為的識別。

圖7 識別結果混淆矩陣Fig.7 Confusion matrix of recognition results

本文對比了CAH方法［20］、STAP方法［25］，結果見表2。

表2 識別算法對比結果Tab.2 Comparison results of recognition algorithms

通過算法對比和特征對比實驗，本文JF-XGBoost 方法在活動語義的識別方面具有更好的效果，而且時空聯(lián)合特征也在活動語義識別中也有重要作用。在空間地理位置訪問上形成熱點的空間區(qū)域，這是人類在現(xiàn)實社交生活中經過長時間的積累自然形成的聚集區(qū)域，具有十分客觀的現(xiàn)實意義，在時間上一些日常的飲食、運動、工作等行為也有著明顯的周期性特點，對于這些特征的深入挖掘將有利于活動行為語義的識別。

4 結語

本文主要研究了人類的活動語義識別，考慮了空間經緯度特征、區(qū)域熱點特征，并結合時間特征，利用聯(lián)合特征和XGBoost 集成學習方法從稀疏的社交媒體簽到數(shù)據(jù)中識別用戶的活動語義。相對于以往研究，增加了對空間熱點特征的挖掘，通過無監(jiān)督學習的DBSCAN 聚類方法從原始數(shù)據(jù)中獲得空間熱度特征并結合時間特征組成特征向量，采用XGBoost 算法學習數(shù)據(jù)中的信息，從而得到活動語義識別模型。在個人的活動建模方面，本文主要關注了空間特征和時間特征，以及地理空間、活動類型的整合等，但對于個體本身的偏好、屬性等個人特點未加考慮，個人的社交關系網絡也會對此有所影響，因此，將上述等問題考慮進活動語義建模中是今后提高識別效果的研究方向所在。