基于改進Markov算法的人類活動信息挖掘

王艷東，高露妹，王 騰，姜 偉

（1.測繪遙感信息工程國家重點實驗室，湖北 武漢 430079；2.地球空間信息技術協同創新中心，湖北 武漢 430079）

基于改進Markov算法的人類活動信息挖掘

王艷東1,2，高露妹1，王 騰1，姜 偉1

（1.測繪遙感信息工程國家重點實驗室，湖北 武漢 430079；2.地球空間信息技術協同創新中心，湖北 武漢 430079）

近年來，基于位置的社交媒體飛速發展,為人類移動規律的挖掘與研究帶來新的數據源。基于擴展Markov模型，加入時間維度，提出一種利用社交媒體時空數據挖掘人類活動規律的方法，探索用戶的活動位置和活動位置的變化規律。應用該方法對北京市新浪微博用戶的個體和群體活動規律進行探索，可有效挖掘人類在以小時為單位細粒度時段的移動規律并由此反映區位人口的動態變化。

社交媒體；數據挖掘；人類活動模式；Markov模型

人類的移動規律是進行城市管理活動（如交通管理、災害預防和應急響應以及城市規劃等）的重要參考[1]。近年來，大量學者結合手機數據[2-3]、人口普查數據[4-5]、航班數據[6-7]、出租車數據[8-9]、交通卡數據[10-12]等不同類型數據，從各個領域探索了人類移動規律的挖掘方法[13-14]。

隨著智能手機的普及，基于位置的社交媒體應用得到空前發展。這些社交媒體可以在用戶進行在線社交活動時對用戶活動信息如位置信息、時間信息等進行記錄，從而產生了面向用戶個體的社交媒體數據。這些社交媒體數據獲取相對方便、對用戶位置記錄實時準確[15]，并且經常涵蓋大量用戶并保持相對較長的一段時間，這對基于龐大的數據量和較長時間跨度的研究是非常有意義的[16-20]。

為了量化人類在位置間的移動可能性，大量研究使用了計算模型，其中Markov模型作為一種預測方法被廣泛應用[21-28]。基于社交媒體數據，一些學者探索了使用該模型進行人類移動規律挖掘的方法[29-31]。本文基于擴展Markov模型，加入時間維度，提出一種利用社交媒體時空數據挖掘人類活動模式的方法。基于當前位置和當前位置的時間，使用擴展后的Markov模型預測用戶到達的下一個位置及概率。應用該方法對北京市新浪微博用戶的個體和群體活動規律進行探索，并分析了群體移動規律對城市區位人口流動的反映。實驗表明，該方法可有效挖掘人類在以小時為單位細粒度時段的移動規律并由此反映區位人口的動態變化。

1 數 據

社交媒體平臺和移動定位技術的發展使得人們的生活從現實擴展到網絡，人們熱衷于在社交媒體平臺中展示自己每天的活動并標注位置。新浪微博作為在中國流行較早、社會參與度較高的社交媒體平臺，涵蓋了用戶較長時間跨度的數據，為研究人類的活動規律提供了重要的數據源。本文使用網頁爬蟲采集了北京市范圍內所有的新浪微博用戶在2014年1～8月發布的所有的帶有位置信息的微博數據，一共1 800多萬條。每條微博數據包含微博發布位置的經緯度坐標、發布時間等信息。本文使用了2014年1～6月的數據對人類活動規律進行探測，并使用了2014年7～8月的數據對方法的有效性進行驗證。

2 方 法

本文提出了一個利用社交媒體時空數據挖掘人類活動模式的框架，如圖1所示，總共包含以下幾個部分：①數據預處理；②活動提取；③活動位置的探測；④ 活動位置轉換的探測。

圖1 基于社交媒體數據的人類移動規律挖掘

2.1 數據預處理

新浪微博是一種社交媒體數據，和其他社交媒體數據一樣，也存在一定的缺陷，因此，需要進行數據預處理，以保證數據質量。本文的數據預處理主要是去除噪音數據。噪音數據主要包含兩個方面：一是重復的數據；二是廣告等噪音。

重復數據主要指由于網絡原因或者用戶自身操作造成的對同一條微博連續發布多次的情況。重復微博的主要特征為發布時間相隔較短以及內容和發布位置相同等。重復數據的存在使得對同一個活動記錄多次，需要根據其發布的時間、位置以及文本內容將其去除。

廣告噪音主要是指非正常微博用戶（如各種app、淘寶賣家等）在新浪微博平臺上發布的各種廣告信息。這些廣告信息的特征是覆蓋微博量較大，發布位置單一等。廣告噪音的存在影響研究結果的準確性，需要根據其文本、位置信息將其去除。

2.2 活動提取

新浪微博是一種虛擬世界的社交活動，同時也反映了現實世界中的人類活動。因此，每一條新浪微博數據都是現實世界中一次人類活動的反映。本文以用戶為單位，提取每個用戶的活動數據。

1）活動的空間屬性。考慮到人類的活動有一定的活動半徑，本文使用400 m×400 m格網將研究區域進行格網劃分，并將一個格網所對應的范圍作為一個活動位置。對于同一個格網內的所有新浪微博，都認為處于同一個活動位置。

2）活動的時間屬性。人類的每個活動都占用了人的一段時間，在研究人類的移動時使用1 h作為時間窗口是常見的[16]。本文使用1 h作為時間窗口將人類的活動劃分到不同的時間段，每個時間段代表了一個活動時間。對于在同一時間段內發布的所有新浪微博，都認為處于相同的活動時間。

2.3 人類活動位置的探測

人類活動位置概率可以表示為在某個時間段，一個人出現在不同位置的概率。根據一個人在某個時間段內在不同位置活動的概率，可以估計這個人在這個時間段內可能出現的活動位置。本文設計的人類活動位置概率計算公式如下：

式中，P(j)ti表示在1 d中的第i個時間段內j位置出現的概率；F(j)ti表示在1 d中的第i個時間段內j位置出現的次數，N = a，…，n ，表示所有可能出現的位置。

人類在不同的時間段內經常出現的位置可能不同。例如，一個人在中午12時左右很可能會去一家餐館吃飯，而在20時左右很有可能在家休息。因此，獲取人類在某個時間段經常出現的位置是獲得其活動規律的一個重要方面。一個人在不同時段最有可能出現的位置可以表示為：

2.4 人類活動位置轉換的探測

人類活動位置轉換概率即兩個活動位置之間發生轉換的概率。每個人的活動都有一定的規律性，往往在進行完一個特定的活動后會進行另外一個特定的活動，通過計算人類活動位置轉換概率，可以根據當前的位置和時間對人類的下一個活動進行預測。

Markov模型是一種常用的預測模型，本文擴展了馬爾科夫模型，并加入時間維度。擴展后的模型如式（3）所示：

即在ti時間段內，在第n+1個位置出現的概率只與其上一個位置（第n個位置）相關，而與之前的位置無關。結合本文的應用場景和數據，具體計算如式（4）所示：

式中，T(Xn+1=k|Xn=j)ti表示在ti時間段內，j位置出現的前提下，從j位置到k位置的轉換次數，N位置表示j位置的所有可能的下一個活動位置。

人類的活動位置和活動位置的變化和時間緊密相關，即使對于同一個活動位置，在不同的時間段內，基于該活動位置的變化也會有所不同。如晚飯過后人們可能進行和娛樂相關的活動，但是午飯過后人們會去工作地點工作。對于“吃飯”這個活動而言，在不同的時間，基于此活動位置發生的變化也不相同。在考慮當前活動位置和時間的情況下，基于活動位置j的下一個最有可能的活動位置可以表示為：

人類在不同時段的活動位置和活動位置的轉換規律表明了人類在1 d中可能出現的位置和在位置之間的移動情況。通過探測個體活動位置和活動位置的轉換規律，可以探測個體在1 d中某時間段可能出現的位置和可能發生的移動，進而預測其在未來同一時間段的活動情況。同時，對多個個體的活動規律進行研究，有助于了解群體的活動情況，即群體在某時間段在某位置集聚或在幾個位置間流動的情況。本文將使用本方法對個體活動和群體活動進行探測并對結果進行分析。

3 實驗與分析

3.1 個體活動探測

本文以一個用戶為例來展示個體活動規律的挖掘，圖2為該用戶在不同時間段內的活動規律展示圖。圖2a為該用戶在研究期間的所有微博點分布情況，由微博點分布可知，該用戶主要在3個位置附近活動，使用A、B、C進行標識。相鄰微博點使用紅色連線連接，表示一次活動轉換。圖2b～h為1 d中不同時間段該用戶活動規律的展示。其中圓圈為在該時間段可能出現的一些活動位置，箭頭表示基于這些活動位置的活動轉換，箭頭方向表示活動轉換方向，圓圈和箭頭顏色表明位置和轉換出現的概率值。

從圖2中可以發現，用戶在休息時間如6 h、18 h、21 h、24 h活動在A位置的概率都很高，A位置可能為該用戶的家的位置。在工作時間如9 h、12 h、15 h在B、C位置活動，說明B、C可能為該用戶工作單位或者常去的地點。在不同的時間段，用戶可能有不同的活動轉換。例如，在上午6 h和9 h該用戶發生的主要活動變化為A→B，在中午12 h和下午15 h主要的活動變化為B→A，C→A。用戶在不同時間段活動規律差異明顯，說明在研究人類的活動規律時時間維度是至關重要的，不能僅僅依靠人類在空間位置間的移動頻率來判斷人類在所有時間段內的移動規律。

3.2 群體活動探測

同時研究多個個體的移動規律可以反映整個群體的移動規律，當人們于1 d的同一時間段在同一位置進行活動，他們的活動和活動轉換可以反映該時間段內人群聚集和移動情況。本文以北京市海淀區中關村附近的區域為例，展示本文方法對群體聚集和移動規律的挖掘。圖3展示了這個區域人群的活動規律，使用字母對主要研究區位進行標注（如A、B、C…），其中圖3a為本研究的目標位置的空間分布，圖3b～h為不同時間段內這些位置之間的人群移動情況，圖中標志和圖例的說明如圖2所示。

圖2 不同時間的個體活動規律

圖3 多個位置間群體活動規律

由圖3可知，在不同的時間點人們聚集于不同的位置，人群的移動路線和移動方向也有所不同。例如，在12 h（圖3d）人們在B位置、F位置、E位置出現聚集，主要的人群流動路線有F→B，B→E。而在21 h（圖3g）主要的人群聚集區為A位置、E位置、F位置，主要的人群流動路線為B→F。人們在1 d內不同時間段在城市間不同位置的集中程度、人群移動路線和方向均有所不同。這符合城市人口流動情況，對動態監測城市多個區位人口集中情況和流動情況是很有意義的。

3.3 驗 證

在實驗部分，本文使用了2014年1～6月的數據進行探測，此處使用2014年7～8月的數據對探測效果進行驗證，并且使用不考慮時間的Markov模型的實驗結果與本文提出的方法進行對比。

本文以一位用戶在12～13時段的活動規律為例展示探測與驗證的結果，如圖4、5所示。其中，傳統方法為不考慮時間的馬爾科夫模型方法得出的探測結果，實際值為用戶在驗證期間的實際概率。回歸分析是確定兩種或兩種以上變量間相互依賴的定量關系的一種統計分析方法，R2是其顯著性水平的檢驗指標。在比較兩種探測結果和實際值之間的關系時我們使用了該方法，并使用R2來檢驗其相互關系的顯著性水平。比較兩種方法所得結果和實際值之間的R2，相對于不考慮時間的馬爾科夫模型方法，本文提出的方法將該用戶出現概率的R2從0.71提高到0.94，將該用戶移動概率的R2從0.003提高到0.70。R2指標是對兩種概率值和實際值之間擬合效果評價的指標，R2的提高說明本方法所得概率值更貼近實際。由此可見，本方法在挖掘人類的動態移動規律方面有比較好的效果。

圖4 用戶位置轉換概率

圖5 用戶活動位置概率

4 結 語

了解人類的移動規律對于城市管理具有重要意義。人類的移動規律和時間緊密相關，因此提出了考慮時間的Markov模型，并且設計了基于社交媒體數據的人類移動規律挖掘框架。以新浪微博為例，應用該框架對北京市新浪微博用戶個體移動規律和群體移動規律進行探討，并分析了群體移動規律對于城市人口流動的反映。這對道路運輸安全與管理、災害預防和應急響應以及城市規劃等城市管理活動具有重要的參考價值。但是本框架在考慮時間因素時選取窗口尺寸方面仍需要斟酌，雖然1 h的時間窗口尺寸在研究人類移動時是常用的，但是對于新浪微博這種特殊的數據類型來說可能有更合適的時間窗口尺寸。基于此，在未來的工作中，將根據用戶個體發布微博頻率為切入點研究面向用戶個體的更準確的時間窗口尺寸。由于人類移動規律的復雜性，人們在一些位置移動的規律很難準確地反映出來。在將來的工作中，將探索不同格網大小對于人類移動規律的挖掘效果并使用其他類型的數據源測試框架的使用效果。

[1] LIU L, HOU A, BIDERMAN A, et al. Understanding Individual and Collective Mobility Patterns from Smart Card Records: A Case Study in Shenzhen[C].2009 12th International IEEE Conference on Intelligent Transportation Systems. IEEE, 2009

[2] HUANG Z, KUMAR U, BODNAR T, et al. Understanding Population Displacements on Location-Based Call Records Using road Data[C]. ACM Sigspatial International Workshop on Mobile Geographic Information Systems. 2013

[3] WILLIAMS N E, THOMAS T A, DUNBAR M, et al. Measures of Human Mobility Using Mobile Phone Records Enhanced with GISdata[J/OL]. http://dx.doi.org/10.1371/ journal.pone.0133630

[4] DALZIEL B D, POURBOHLOUL B, ELLNER S P. Human Mobility Patterns Predict Divergent Epidemic Dynamics Among Cities[J/OL]. http://dx.doi.org/10.1098/rspb.2013.0763

[5] PINDOLIA D K, GARCIA A J, HUANG Z, et al. The Demographics of Human and Malaria Movement and Migration Patterns in East Africa[J]. Malaria Journal, 2013, 12(1):1-12

[6] ORDANOVICH D, TATEM A. Risk Assessment of Malaria Importation to Europe and Other Non-Endemic Regions Via air-travel[J]. Malaria Journal, 2014, 13(1):1

[7] HUANG Z, TATEM A J. Global Malaria Connectivity Through Air Travel[J]. Malaria Journal, 2013, 12(1):1-11

[8] KUMAR D, WU H, LU Y, et al. Understanding Urban Mobility Via Taxi Trip Clustering[C]. IEEE International Conference on Mobile Data Management. IEEE, 2016

[9] TANG J, LIU F, WANG Y, et al. Uncovering Urban Human Mobility from Large Scale Taxi GPS Data[J]. Physica A Statistical Mechanics & Its Applications, 2015(438):140-153

[10] TERROSO S F, VALDES V M, SKAMETA G A F. Tram-Based Mobility Mining with Event Processing of Transit-Card Transactions[C]. IEEE, International Conference on Intelligent Transportation Systems. IEEE, 2015

[11] SONG J Y, JIN K E, KIM S I. Evaluation of Elderly Mobility Based on Transit Card Data in Seoul[J]. Promet-Traffic & Transportation, 2014, 26(4):281-290

[12] LIU L, HOU A, BIDERMAN A, et al. Understanding Individual and Collective Mobility Patterns from Smart Card Records: A Case Study in Shenzhen[C]. International IEEE Conference on Intelligent Transportation Systems, 2009

[13] LEI P R, SHEN T J, PENG W C, et al. Exploring Spatial-Temporal Trajectory Model for Location Prediction[C]. IEEE International Conference on Mobile Data Management, MDM 2011, Lulea, Sweden, June 6-9. 2011

[14] GONZALEZ M C, HIDALGO C A, BARABASI A L. Understanding Individual Human Mobility Patterns[J]. Nature, 2008, 453(7 196):779-82

[15] BLANFORD J I, HUANG Z, SAVELYEV A, et al. Geo-Located Tweets. Enhancing Mobility Maps and Capturing Cross-Border Movement.[J/OL]. http://dx.doi.org/10.1371/ Journal.Pone.0129202

[16] HUANG Q, WONG D W S. Modeling and Visualizing Regular Human Mobility Patterns with Uncertainty: An Example Using Twitter Data[J]. Annals of the Association of American Geographers, 2015, 105(6):1-19

[17] CHO E, MYERS S A, LESKOVEC J. Friendship and Mobility: User Movement in Location-Based Social Networks[C]. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, Ca, Usa, August. 2011

[18] HAI N T, NGUYEN H H, THAI N N. A Mobility Prediction Model for Location-Based Social Networks[M]. Intelligent Information and Database Systems. Springer Berlin Heidelberg, 2016

[19] BAPIERRE H, JESDABODI C, GROH G. Mobile Homophily and Social Location Prediction[J/OL]. https://Arxiv.org/ Abs/1506.07763

[20] BACKSTROM L, SUN E, MARLOW C. Find me if you can: Improving Geographical Prediction with Social and Spatial Proximity[C]. International Conference on World Wide Web, WWW 2010, Raleigh, North Carolina, Usa, April, 2010

[21] MATHEW W, RAPOSO R, MARTINS B. Predicting Future Locations With hidden Markov models[C]. ACM Conference on Ubiquitous Computing, 2012

[22] GAMBS S&#, BASTIEN, KJLLIJIAN M O, et al. Next Place Prediction Using Mobility Markov Chains[C]. EUROSYS 2012 Workshop on Measurement, Privacy, and Mobility, 2012

[23] ASAHARA A, MARUYAMA K, SATO A, et al. Pedestrian-Movement Prediction Based on Mixed Markov-Chain model[C]. ACM Sigspatial International Symposium on Advances in Geographic Information Systems, Acm-Gis 2011, November 1-4, 2011, Chicago, Il, Usa, Proceedings,2011

[24] ALVAREZ-GARCIA J A, ORTEGA J A, GONZALEZABRIL L, et al. Trip Destination Prediction Based on Past GPS Log Using a Hidden Markov Model[J]. Expert Systems with Applications, 2010, 37(12):8 166-8 171

[25] GAO W, CAO G. Fine-Grained Mobility Characterization: Steady and Transient State Behaviors[C]. Eleventh ACM International Symposium on Mobile Ad Hoc Networking and Computing. ACM, 2010

[26] HUANG W, LI S, LIU X, et al. Predicting Human Mobility with Activity Changes[J]. International Journal of Geographical Information Science, 2015, 29(9):1 569-1 587

[27] 宋路杰, 孟凡榮, 袁冠. 基于Markov模型與軌跡相似度的移動對象位置預測算法[J].計算機應用,2016, 36(1):39-43

[28] 呂明琪, 陳嶺, 陳根才. 基于自適應多階Markov模型的位置預測[J].計算機研究與發展,2010, 47(10):1 764-1 770

[29] YE J, ZHU Z, CHENG H. What's your Next Move: User Activity Prediction in Location-Based Social Networks[C]. Proceedings of the SIAM International Conference on Data Mining. SIAM,2013

[30] PREOTIUC-PIETRO D, COHN T. Mining userBehaviours: A Study of Check-in Patterns in Location Based Social Networks[C].Proceedings of The 5th Annual ACM Web Science Conference. ACM, 2013

[31] CHENG C, YANG H, LYU M R, et al. Where you Like to Go Next: Successive Point-of-Interest Recommendation[C]. International Joint Conference on Artificial Intelligence. AAAI Press, 2013

P208

B

1672-4623（2017）02-0001-05

10.3969/j.issn.1672-4623.2017.02.001

2016-10-18。

項目來源：國家自然科學基金資助項目（41271399）；國家重點研發計劃資助項目（2016YFB0501400）；測繪地理信息公益性行業科研專項經費資助項目（201512015）。

王艷東，博士生導師，主要從事大數據時空分析計算、地理信息系統理論與工程應用等研究。