基于改进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）。

王艳东，博士生导师，主要从事大数据时空分析计算、地理信息系统理论与工程应用等研究。