2. 山西农业大学文理学院 山西 太谷 030801;
3. 杭州师范大学信息经济研究所和阿里巴巴商学院 杭州 310036
2. College of Arts and Sciences, Shanxi Agricultural University Taigu Shanxi 030801;
3. Institute of Information Economy and Alibaba Business College, Hangzhou Normal University Hangzhou 310036
对人类行为规律的探索长久以来一直是自然、经济、社会等各个学科领域的学者关注的研究方向。近年来,随着越来越多的人类行为的数据资料被精确记录,学者得以从定量角度分析人类行为的时空规律及其动力学机制,并由此改变了很多对人类行为的传统认识。如在时间规律上,过去人们假设人类行为的产生是具有均匀特性的泊松过程,而近年来大量实证结果显示人类行为在很多方面具有明显的阵发和重尾特征[1-5],即表现为长时间静默和短时间爆发交织,且时间间隔服从重尾分布。
研究人类行为的空间规律在疾病传播[6-8]、交通流控制[9-11]、异常行为监测[12]、人口迁移[13]等方面具有重大的理论和应用价值。过去,人们假设人类的出行行为可以用随机游走或者列维飞行刻画,但近年来的一系列研究却证实人类出行的时间间隔分布和位移距离分布都服从重尾分布,表现为阵发性、有界性、周期性和规律性综合的特征[14-20]。为此,学者相继从不同角度提出了统计模型来解释上述特征产生的原因[14, 16-17]。在实证和建模的基础上,更具有理论和商业价值的位置预测[21-29]也是人类出行行为研究的重点之一。文献[21]用熵的方法得到人类出行的理论可预测性最高可达93%,该结果受到了广泛关注。
过去对人类出行规律的研究所采用的数据多来源于钞票或者手机通信,这些数据都可视为被动签到行为的结果,并非用户主动上传。随着GPS设备的微型化,更能反映用户的主观愿望的即时通讯(instant messaging, IM)和基于位置的服务(location based services, LBS)工具变得更加普及,从而为研究人们的出行行为提供了更好的媒介。
本文通过两组由手机收集的地点签到数据(包括基于IM的QQ和基于LBS的Gowalla)研究人们在日常生活中的签到行为,总结了签到行为的基本特征,利用熵和Fano不等式计算了用户的平均最大可预测性,重点分析了影响可预测性的因素,包括访问地点数、平均跳转距离、回转半径和最常访问地点。发现人们的签到行为具有明显的非均匀特征和一定的记忆效应,可预测性和规律性受用户访问的地点数的影响明显,而与用户的活动范围和平均跳转距离关系不大,更进一步,可预测性会随着用户最常访问地点的删除而呈现先减小后增大的趋势。同时还发现,与被动签到行为相比,主动签到行为具有更大的熵值,因而也更难预测。相比于地点分享行为,日常出行行为的记忆性、规律性和可预测性都更强一些。
1 数据描述本文研究所采用的数据集来源于两组由手机收集到的经过匿名化处理的地点签到信息:数据集D1来自LBS社交网站Gowalla,全球范围内的用户可通过移动端的应用程序或者浏览器进行主动签到,从而与好友分享新的地点、活动和旅行线路;数据集D2来自国内某沿海城市的手机QQ用户使用涉及地图服务的应用时被动记录下的地点信息。因此,两组数据都是用户发生空间移动行为时记录的位置信息,包括了用户ID、地点经纬度、时间等属性,且相比于D2,D1由于是用户主动上传分享的,故其主动性更强一些。为了保证用户轨迹信息量具有统计意义,本文在计算可预测性时去掉了地点签到量不足100条的用户,在去掉不活跃的用户之后,D1、D2的用户数量分别为全部用户的8.35%和28.92%,但轨迹量却能分别达到65.59%和79.33%,地点数目分别达到全量数据的76.56%和81.00%。两组数据的概述如表 1所示。
这两组数据都源于手机用户上网、签到或查询地图等行为,文中将用户在某个地点产生一条轨迹信息记录的行为统称为“签到”,若相邻两次签到的地点发生变化,则称为一次“跳转”,若地点没有发生变化,则称之为“停留”。由于数据集中存在短时间内产生多条签到记录的现象,使得数据在时间上会显得非常频繁,但在空间地点信息上又显得不够丰富。为了更好地分析用户的空间移动行为特征,将极短时间内在同一地点的多条签到记录合并为一条,最后保留的数据集中仍然存在一定时间间隔下的有意义的地点停留。从而获得每个用户i的签到轨迹集合
统计结果显示,本文所研究的签到行为的时间间隔分布和跳转距离分布都表现出幂律特征,与文献[13-15]的结果类似。那么,在人们的日常生活中,每个人会访问多少个不同的地点?每个地点又会有多少不同的人来访问呢?为了回答这两个问题,定义用户的活跃度为用户去过的地点集的大小N,定义地点的活跃度为去过该地点的用户集的大小U。统计两个数据集中全部用户和地点的活跃度分布,结果如图 1所示。
用户活跃度N的累积分布如图 1a所示,两个数据集中用户比例均在大约30个地点处开始明显下降,这说明在人们的日常生活中,大多数人经常访问的地点数是有限的,对这些有限数量地点的访问是较为均匀的。如图 1a插图所示,曲线在双对数坐标下近似为直线,即
而由图 1b知地点的活跃度分布则为幂律分布。这说明在特定地点签到的人数具有较强的异质性,即日常生活中大部分地点的访问人数较少,同时存在少数热门地点具有大量的访问人数。这样的现象与购物、点评等典型二部图网络的度分布研究结果类似[32],说明在真实系统中,行为的主动发出者所覆盖的受众是有限而较为均匀的,而行为的被动接收者却可以接受大量而异质的访问。由于Gowalla数据的地点精确度非常高,故大部分地点的访问量非常少,因而其U曲线的衰减速度比QQ的U曲线要快得多,后者的异质性更强。
2.2 签到行为的统计特征根据签到记录中的经纬度信息,计算用户i在签到过程中的跳转距离,并进一步得到每个用户的平均跳转距离为:
$ {\bar l^i} = \frac{1}{{|{L^i}|}}\sum\limits_{k = 1}^{|{L^i}|} {l_k^i} $ |
式中,
为了考察用户日常活动范围的大小,定义回转半径[15]为:
$ {\rm{R}}{{\rm{g}}^i} = \sqrt {\frac{1}{{|{L^i}|}}\sum\limits_{k = 1}^{|{L^i}|} {|l_k^i-{{\bar m}^i}{|^2}} } $ |
式中,
用户相邻的两次跳转之间是否存在内在联系,是否一次长距离的跳转也预示着下一步也是长距离的跳转?为了研究这个问题,本文采用文献[33]中定义的记忆性指标,研究所有个体用户跳转距离的相关性。
若某用户i的跳转距离序列共有
$ M' = \frac{1}{{n_\tau ^i-1}}\sum\limits_{k = 1}^{n_\tau ^i-1} {\frac{{({\tau _k}-{m_1})({\tau _{k + 1}} - {m_2})}}{{{\sigma _1}{\sigma _2}}}} $ |
式中,m1和m2、σ1和σ2分别是两个子序列的均值和标准差。该值在-1~1之间,M'>0意味着记忆效应,M' < 0意味着反记忆性。
本文计算每一个用户的跳转距离序列的M'值。结果显示,所有用户M'值的平均值〈M'〉在Gowalla和QQ中分别为0.134±0.163和0.249±0.186。从该结果可以看出,对于大多数用户来说,长距离的跳转之后仍然倾向于长距离的跳转,反之亦然,即跳转距离具有一定的弱记忆性和正相关性。考虑在日常生活中,人们大部分的出行是在以家和公司为焦点的椭圆范围之内活动[34],连续出行距离都比较短;但一旦有出差、旅行或探亲活动,则很容易伴随一系列的长短距离交替的跳转活动。相比于数据集D1,D2更多是日常生活中城内和城际范围内的活动,因而后者的签到行为更集中,〈M'〉更大,即日常生活中签到行为的记忆性更强。
3 签到行为可预测性分析 3.1 签到行为的可预测性度量本文采用文献[21]中的方法定义签到行为的熵和可预测性,包括三种熵的度量指标。
随机熵:
香农熵:
真实熵:
根据Fano不等式可得到每个用户的可预测性:
$ {{\mathit{\Pi }} _i} \le {\mathit{\Pi }} _{\max }^i({S^i}, {N^i}) $ |
式中,
同时定义用户地点访问的规律性。将一周的时间分成24小时*7天=168个时段,用
根据上述指标计算了两个数据集中活跃用户的3种熵
如图 3a所示,对于数据集D1,从用户的随机熵
如图 3b所示,熵值的减少导致了最大可预测性的增长,
图 3c揭示了用户的地点访问的规律性分布,在用户的签到行为中,约28.9%的时间里都是位于该时段最常签到的地点。故对于某个特定时段,只要猜测用户位于在其最常访问的地点,就至少能够获得28.9%左右的准确度。
对于数据集D2,熵、可预测性和规律性等指标表现为与D1类似的情况。二者的差别表现在:D2的3种类别的熵值都比D1低,可预测性则要高。这是由于D2数据中地点的经纬度精度要低于D1,且D2的数据中地点的范围相对较小(D1中的签到地点遍布全世界,而D2大部分局限在该城市及周边),使得D2中的地点重合度高达97.6%,而D1中只有80.5%。对于数据集D1,在每个用户的签到序列中新地点的比例更大,总地点个数更多,每个地点访问的概率更小,因此熵值也必然更大。
如图 3a所示,D2的真实熵值
从前文的统计结果可以看出,人类的日常签到行为具有复杂性和规律性交织的特征。那么,规律性越强的用户是否更容易预测?访问过更多地点的用户、活动半径更大的用户是否更难预测?计算每个用户的可预测性
统计用户去过的地点数和去过该地点数的全部用户的平均可预测性值,考察二者之间的关系,结果如图 4a所示。访问地点数与可预测性的关系在两个数据集中表现出了相同的规律,即先在一段小范围内减小,然后迅速变得平缓,在波动中缓慢下降。由于Gowalla数据的观测期更长,故其用户访问的地点数也更多。这说明在一定范围内,确实存在用户访问过的地点数越多,其行为就更难预测的现象。但是随着地点数持续增多其真实可预测性开始趋于平缓,即地点数的影响作用变小。总体上看,用户去过的地点数与用户的可预测性存在一定的负相关性。
根据2.2节得到的每个用户的平均跳转距离和回转半径分析二者和可预测性的关系,如图 4b和4c所示,不论是回转半径还是平均跳转距离对于可预测性的影响都表现出了相似的规律,即随着用户活动范围和出行距离的增大,
规律性反映了用户在特定时段出现在最常访问地点的概率,那么上述三个统计量对用户签到行为的规律性是否有影响呢?计算结果显示,随着用户访问地点数的增大,
在人们的日常生活中,不论是个体还是群体用户对某个特定地点的访问量都具有显著的异质性,少数地点具有极高的访问量,而大多数地点极少被光顾。那么这些访问量大的地点是否对可预测性产生影响呢?为了回答这个问题,逐步删除用户移动轨迹中访问量最大的K个地点,查看用户最大真实熵和可预测性的变化情况。在实验前首先挑选访问过的唯一地点数大于最大删除量(在数据集D1和D2中分别是50和20)的用户,以保证在删除访问量大的地点时用户仍然访问过多于1个不同的地点。
实验结果如图 6所示,平均最大真实可预测性
可以从以下方面理解这种非平凡现象:一般情况下,对地点访问信息丰富的用户来说,随着最常访问地点的删除,用户的地点签到序列会慢慢变得随机化,此时熵值将慢慢增大,最大可预测性也随之降低。但当轨迹点被删除到一定程度时,用户访问序列中的轨迹点都逐渐趋近于被访问极少的次数,几乎成为一个完全随机的地点访问序列,可预测性下降趋势逐渐变缓。当全部的轨迹点的访问次数都为1的时候,熵值达到最大,此时可预测性曲线也慢慢趋向最小值。当继续删除轨迹点时,熵值随着N的增大而逐渐变小,此时最大可预测性则因为随机序列中地点数的减少而缓慢增长。由此说明,用户经常访问的地点是带来签到行为高可预测性的一个重要因素。而可预测性曲线的最值点比熵曲线滞后则是Fano不等式中二者的非线性关系造成的。
4 结语和讨论本文通过两组手机用户的签到数据研究人类日常的出行行为,总结了签到行为的一般规律,用熵的方法分析了签到行为的可预测性,并重点分析了影响可预测性的几个因素。发现人们的签到行为具有一定的记忆效应,对地点的访问具有明显的异质性。总体来看,用户访问的地点数和对最常访问地点的访问规律对可预测性和规律性有明显影响。具体而言,用户访问过的地点的数量与可预测性和规律性都具有一定的反相关关系,而回转半径和平均跳转距离对二者的影响则微弱的多。用户经常访问的地点对可预测性具有显著影响,随着这些地点被逐个删除,可预测性表现为先下降再略微上升的形态。进一步研究还发现,可预测性和规律性是人们日常生活的普遍规律,与性别、年龄等属性无关[21],因而该性质是人类空间运动的普遍规律,在人口统计学属性上无个体差异。
研究表明,当用户访问的地点数逐步增大时,以及当用户最常访问的地点被逐步删除时,其可预测性都会下降,说明用户对地点的访问次数和访问模式对可预测性有重要影响。一方面,当用户访问的地点逐渐增多时,其访问序列会变得混乱,因而熵值增大,可预测性下降;另一方面,当用户经常访问的地点被删掉时,可预测性曲线的非线性的下降速率说明不同地点对可预测性的影响程度是不同的,访问量大的地点的影响程度也更大。这些结果都说明用户对不同地点的访问量是非均匀的。因此,用户对地点访问的异质性是影响其可预测性的重要因素。
从研究结果可以看到,数据集D2得到的可预测性数值要高于D1,这样的差别反应了两组数据集的不同。如前文介绍所说,Gowalla是一个鼓励用户主动上报地理位置的LBS网站,其行为更多源自旅游、美食、娱乐等活动的分享;而QQ数据是在用户日常生活中使用地图服务时记录的位置信息,日常生活中出行的记忆性和规律性更强,地点重合度也更高,因而其可整体可预测性也更高。
人类行为动力学研究的是人类行为的宏观统计规律,而熵的方法分析可预测性得到的则是预测准确度的理论上限,并不是真正意义上的预测算法。由于人类行为的高度复杂性,对于个体出行行为的精确预测并不是一件容易的事情,预测的准确度也受到多种客观条件和数据本身的质量等因素制约。社会学、物理学、计算机科学等领域的学者都在从多方面关注影响人们出行的因素并探索提高预测算法的准确度的方式。本文有助于理解人类的出行规律,为寻找制约预测准确度的因素、改进利用熵和Fano不等式计算可预测性的方法提供一定的参考和借鉴。
本文的研究工作得到了山西农业大学科技创新基金(201208)的资助,在此表示感谢![1] |
BARABÁSI A L. The origin of bursts and heavy tails in human dynamics[J].
Nature, 2005, 435(207): 211.
|
[2] |
ZHOU T, KIET H A T, KIM B J, et al. Role of activity in human dynamics[J].
Europhys Lett, 2008, 82(2): 28002.
DOI:10.1209/0295-5075/82/28002 |
[3] |
周涛, 韩筱璞, 闫小勇, 等. 人类行为时空特性的统计力学[J].
电子科技大学学报, 2013, 42(4): 481–540.
ZHOU Tao, HAN Xiao-pu, YAN Xiao-yong, et al. Statistical mechanics on temporal and spatial activities of human[J]. Journal of University of Electronic Science and Technology of China, 2013, 42(4): 481–540. |
[4] |
樊超, 郭进利, 韩筱璞, 等. 人类行为动力学研究综述[J].
复杂系统与复杂性科学, 2011, 8(2): 1–17.
FAN Chao, GUO Jin-li, HAN Xiao-pu, et al. A review of research on human dynamics[J]. Complex Systems and Complexity Science, 2011, 8(2): 1–17. |
[5] |
ZHAO Z D, CAI S M, HUANG J, et al. Scaling behavior of online human activity[J].
Europhys Lett, 2012, 100(4): 48004.
DOI:10.1209/0295-5075/100/48004 |
[6] |
HUFNAGEL L, BROCKMANN D, GEISEL T. Forecast and control of epidemics in a globalized world[J].
Proc Natl Acad Sci, 2004(101): 15124–15129.
|
[7] |
EUBANK S, GUCLU H, KUMAR V S A, et al. Modelling disease outbreaks in realistic urban social networks[J].
Nature, 2004, 429(6988): 180–184.
DOI:10.1038/nature02541 |
[8] |
HAN X P, WANG B H, ZHOU C S, et al. Scaling in the global spreading patterns of pandemic Influenza A (H1N1) and the role of control: empirical statistics and modeling [EB/OL]. [2014-09-23]. http://arxiv.org/pdf/0912.1390.
|
[9] |
MEYER M D, MILLER E J.
Urban transportation planning: a decision-oriented approach[M]. New York: McGraw-Hill, 2001.
|
[10] |
MOKHTARIAN P L, SALOMON I.
In perpetual motion: Travel behavior research opportunities and application challenges[M]. Amsterdam: Elsevier Science Press, 2002.
|
[11] |
CHON Y, LANE N D, KIM Y, et al. Understanding the coverage and scalability of place-centric crowdsensing[C]// Proceedings of the 2013 ACM international joint conference on Pervasive and ubiquitous computing. [S. l]: ACM, 2013: 3-12.
|
[12] |
BARABASI A L.
Bursts: the hidden patterns behind Everything we do, from your E-mail to bloody crusades[M]. New York: Plume Books, 2010.
|
[13] |
YANG Z, YUAN N J, XIE X, et al. Indigenization of Urban Mobility[EB/OL]. [2014-10-12]. http://arxiv.org/pdf/1405.7769.
|
[14] |
BROCKMANN D, HUFNAGEL L, GEISEL T. The scaling laws of human travel[J].
Nature, 2006(439): 462–465.
|
[15] |
GONZÁLEZ M C, HIDALGO C A, BARABÁSI A L. Understanding individual human mobility patterns[J].
Nature, 2008, 453(7196): 779–782.
DOI:10.1038/nature06958 |
[16] |
SONG C, KOREN T, WANG P, et al. Modelling the scaling properties of human mobility[J].
Nat Phys, 2010(6): 818–823.
|
[17] |
CHO E, MYERS S A, LESKOVEC J. Friendship and mobility: user movement in location-based social networks [C]//Proceedings of the 17th ACM SIGKDD international conference on knowledge discovery and data mining. [S. l]: ACM, 2011: 1082-1090.
|
[18] |
HAN Xiao-pu, HAO Qiang, WANG Bing-hong, et al. Origin of the scaling law in human mobility: Hierarchy of traffic systems[J].
Phys Rev E, 2011, 83(3): 036117.
DOI:10.1103/PhysRevE.83.036117 |
[19] |
YAN X Y, HAN X P, WANG B H, et al. Diversity of individual mobility patterns and emergence of aggregated scaling laws[J].
Scientific Reports, 2013, 3: 2678.
DOI:10.1038/srep02678 |
[20] |
SCHNEIDER C M, BELIK V, COURONNE T, et al. Unravelling daily human mobility motifs[J].
Journal of The Royal Society Interface, 2013, 10(84): 20130246.
DOI:10.1098/rsif.2013.0246 |
[21] |
SONG C, QU Z, BLUMM N, et al. Limits of predictability in human mobility[J].
Science, 2010, 327(5968): 1018–1021.
DOI:10.1126/science.1177170 |
[22] |
MONREALE A, PINELLI F, TRASARTI R, et al. WhereNext: a location predictor on trajectory pattern mining[C]//Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining. [S. l]: ACM, 2009: 637-646.
|
[23] |
朱寅, 杨强. 诺基亚移动数据挖掘竞赛[J].
中国计算机学会通讯, 2012, 8(8): 67–70.
ZHU Yin, YANG Qiang. Nokia mobile data challenge[J]. Communications of the Chinese Computer Federation, 2012, 8(8): 67–70. |
[24] |
GAMBS S, KILLIJIAN M O, DEL PRADO CORTEZ M N. Next place prediction using mobility markov chains[C] //Proceedings of the First Workshop on Measurement, Privacy, and Mobility. [S. l]: ACM, 2012: 3.
|
[25] |
NOULAS A, SCELLATO S, LATHIA N, et al. Mining user mobility features for next place prediction in location-based services[C]//ICDM. [S. l. ]: [s. n. ], 2012, 12: 1038-1043.
|
[26] |
LU Xin, BENGTSSON L, HOLME P. Predictability of population displacement after the 2010 Haiti earthquake[J].
Proc Natl Acad Sci, 2012, 109(29): 11576–11581.
DOI:10.1073/pnas.1203882109 |
[27] |
GALLOTTI R, BAZZANI A, ESPOSTI M D, et al. Entropic measures of individual mobility patterns[J].
Journal of Statistical Mechanics: Theory and Experiment, 2013(10): P10022.
|
[28] |
BAUMANN P, KLEIMINGER W, SANTINI S. The influence of temporal and spatial features on the performance of next-place prediction algorithms[C] //Proceedings of the 2013 ACM International Joint Conference on Pervasive and Ubiquitous Computing. [S. l]: ACM, 2013: 449-458.
|
[29] |
LU Xin, WETTER E, BHARTI N, et al. Approaching the limit of predictability in human mobility[J].
Scientific Report, 2013(3): 2923.
|
[30] |
LAHERRERE L, SORNETTE D. Stretched exponential distributions in nature and economy: "fat tails" with characteristic scales[J].
Euro Phys J B, 1998, 2: 525.
DOI:10.1007/s100510050276 |
[31] |
ZHOU T, WANG B H, JIN Y D, et al. Modelling collaboration networks based on nonlinear preferential attachment[J].
Int J Mod Phys C, 2007, 18: 297–314.
DOI:10.1142/S0129183107010437 |
[32] |
SHANG Ming-sheng, LÜ Lin-yuan, ZHANG Yi-cheng, et al. Empirical analysis of web-based user-object bipartite networks[J].
Europhys Lett, 2010(90): 48006.
|
[33] |
GOH K I, BARABASI A L. Burstiness and memory in complex systems[J].
Europhys Lett, 2008(81): 48002.
|
[34] |
YAN Xiao-yong, HAN Xiao-pu, ZHOU Tao, et al. Exact solution of the gyration radius of an individual's trajectory for a simplified human regular mobility model[J].
Chin Phys Lett, 2011, 28(12): 120506.
DOI:10.1088/0256-307X/28/12/120506 |