移动数据挖掘.html.pdf

丛书前言 当下大数据技术发展变化日新月异，大数据应用已经遍及工业和社会生活的方方面面，原有的数据管理理论体系与大数据产 业应用之间的差距日益加大，而工业界对于大数据人才的需求却急剧增加。大数据专业人才的培养是新一轮科技较量的基础，高 等院校承担着大数据人才培养的重任。因此大数据相关课程将逐渐成为国内高校计算机相关专业的重要课程。但纵观大数据人才 培养课程体系尚不尽如人意，多是已有课程的“冷拼盘”，顶多是加点“调料”，原材料没有新鲜感。现阶段无论多么新多么好 的人才培养计划，都只能在20世纪六七十年代编写的计算机知识体系上施教，无法把当下大数据带给我们的新思维、新知识传 导给学生。 为此我们意识到，缺少基础性工作和原始积累，就难以培养符合工业界需要的大数据复合型和交叉型人才。因此急需在思维 和理念方面进行转变，为现有的课程和知识体系按大数据应用需求进行延展和补充，加入新的可以因材施教的知识模块。我们肩 负着大数据时代知识更新的使命，每一位学者都有责任和义务去为此“增砖添瓦”。 在此背景下，我们策划和组织了这套大数据管理丛书，希望能够培养数据思维的理念，对原有数据管理知识体系进行完善和 补充，面向新的技术热点，提出新的知识体系/知识点，拉近教材体系与大数据应用的距离，为受教者应对现代技术带来的大数 据领域的新问题和挑战，扫除障碍。我们相信，假以时日，这些著作汇溪成河，必将对未来大数据人才培养起到“基石”的作 用。 丛书定位：面向新形势下的大数据技术发展对人才培养提出的挑战，旨在为学术研究和人才培养提供可供参考的“基石”。 虽然是一些不起眼的“砖头瓦块”，但可以为大数据人才培养积累可用的新模块（新素材），弥补原有知识体系与应用问题之前 的鸿沟，力图为现有的数据管理知识查漏补缺，聚少成多，最终形成适应大数据技术发展和人才培养的知识体系和教材基础。 丛书特点：丛书借鉴Morgan&Claypool Publishers出版的Synthesis Lectures on Data Management，特色在于选题新 颖，短小精湛。选题新颖即面向技术热点，弥补现有知识体系的漏洞和不足（或延伸或补充），内容涵盖大数据管理的理论、方 法、技术等诸多方面。短小精湛则不求系统性和完备性，但每本书要自成知识体系，重在阐述基本问题和方法，并辅以例题说 明，便于施教。 丛书组织：丛书采用国际学术出版通行的主编负责制，为此特邀中国人民大学孟小峰教授（email： xfmengruc.edu.cn）担任丛书主编，负责丛书的整体规划和选题。责任编辑为机械工业出版社华章分社姚蕾编辑（email： yaoleihzbook.com）。 在此期望有志于大数据人才培养并具有丰富理论和实践经验的学者和专业人员能够加入到这套书的编写工作中来，共同为中 国大数据研究和人才培养贡献自己的智慧和力量，共筑属于我们自己的“时代记忆”。欢迎读者对我们的出版工作提出宝贵意见 和建议。 丛书即将出版书目 大数据管理概论 孟小峰 主编 2017年5月 异构信息网络挖掘：原理和方法 美孙艺洲（Yizhou Sun） 韩家炜（Jiawei Han）著；段磊 朱敏唐常杰 译 2017年4月 大规模元搜索引擎技术 美孟卫一（Weiyi Meng） 於德（Clement T.Yu）著；朱亮 译 2017年4月 大数据集成 美董欣（Xin Luna Dong） 戴夫士·斯里瓦斯塔瓦（Divesh Sriva-stava）著 王秋月 杜治娟 王硕 译 2017年4月 短文本数据理解 王仲远 编著 2017年4月 个人数据管理 李玉坤 孟小峰 编著 2017年4月 位置大数据隐私管理 潘晓 霍峥 孟小峰 编著 2017年4月 移动数据挖掘 连德富 张富峥 王英子 袁晶 谢幸 编著 2017年4月 云数据管理：挑战与机遇 美迪卫艾肯特·阿格拉沃尔（Divyakant Agrawal） 苏迪皮托·达斯（Sudipto Das） 阿姆鲁·埃尔·阿巴迪（Amr El Abbadi）著；马友忠等译 2017年5月 前言 随着室内外定位、移动社交网络和物联网技术的发展与普及，移动数据的种类、规模和产生速度都在迅速增长。这些数据中 有很大一部分是由人产生的，也就是通过各种方式记录下来的人的活动历史。它们包含了大量的知识，对于众多实际应用有着重 要的价值。我们可以通过对这些数据进行挖掘，来发现人类出行的规律，并针对用户的属性和兴趣爱好生成画像，从而为用户提 供更加个性化的服务，包括交通出行规划、旅游线路和购物餐饮推荐等。这些知识还能用来研究疾病传播、城市发展及人类迁徙 等具有重大社会意义的科学问题。近年来，针对移动数据的挖掘已经成为学术界和工业界的热点之一。 本书作者所在的研究团队从十年前就开始在该领域开展研究，并在2006年进行的GeoLife项目中通过用户分享的移动数据研 究用户的出行模式，为旅游线路规划等应用提供支持，相关论文也被广泛引用。本书第一作者，即目前任教于电子科技大学的连 德富教授，长期针对基于移动数据的推荐系统进行研究，已经发表了大量有影响力的研究成果。 在实际应用中，移动数据的形式多种多样，既有来自移动社交网络的签到数据、来自运营商的日志数据，也有来自公交计费 系统的刷卡记录数据。本书从分析移动数据的特性出发，探讨和设计针对移动数据的数据挖掘算法，并指出在该领域展开研究将 要面临的挑战。 希望本书能够帮助有兴趣研究移动数据挖掘的读者缩短学习的过程，并共同推进该领域的研究进展。 第1章 引言 移动数据挖掘研究的是基于移动数据的数据挖掘算法。这些数据挖掘算法需要更多地利用移动数据的特性，挖掘与这些特性 有关系的模式。比如，研究发现，移动数据通常具有空间的聚集效应，即人们总是在少数的几个地点（家、工作场所等）附近活 动，因而如何在数据挖掘的过程中考虑这一特性，便是移动数据挖掘需要重点考虑的一个问题。那么，移动数据具体是什么、有 哪些特性、移动数据挖掘有什么任务、将要面对哪些挑战呢？ 1.1 移动数据及其价值 移动数据是移动轨迹的集合，而移动轨迹可以简单地认为是移动记录的有序序列，既可以是人的移动数据，也可以是任何其 他动物的移动数据。本书关注的是人类的移动历史。人类的移动历史具有更多的不确定性，他们并非总是愿意保持固定不变的生 活规律，因而人类的移动数据中具有更加丰富的移动模式。人们可以通过携带GPS设备直接收集移动数据，也可以将诸如出租 车、公交车、飞机、火车等移动对象作为载体来间接收集他们的移动数据。这种移动数据收集的普适性得力于移动通信和传感设 备等位置感知技术的发展和智能移动设备的普及，使得移动对象无论身处室内还是室外都可以更加容易地获取他们自身的地理位 置信息。目前最先进的定位系统不仅依赖于全球卫星定位系统的高精度定位，还依赖于Wi-Fi和基站的较为粗略但范围更广的定 位。出于业务本身或未来业务扩展及研究的需要，移动对象的很多定位数据都会被保留下来。由于与业务的强相关性，用户群的 大小及位置的采样频率也决定了这些存留的位置数据不仅数量巨大，而且数据产生的速率很高。比如，运营商出于高效通信的需 求会记录每个移动用户的服务位置，由于用户的规模巨大，因此每天产生的位置数据量也是非常巨大的。据我国三大运营商的运 营数据显示，截至2015年12月，中国电信、中国移动和中国联通的用户数分别高达1.979亿户、8.26亿户和2.866亿户。假如每 人每天平均通信一次，那么每天就会有约13亿条的位置数据。 然而，正如基站定位数据是存储在运营商手中的一样，位置数据一般不会保存在移动对象的手中，外加数据量巨大，使得移 动数据的开放受到了很大的约束。不过，随着移动互联网和在线社交网络的发展，诸如街旁网、Foursquare、Facebook Place 等位置社交网络应运而生。在位置社交网络中，人们可以便捷地跟踪和分享诸如他们在什么地方和什么时候做了什么事情的签到 （check-in）记录等位置访问信息。同样，源于与在线社交网络的结合，位置社交网络中的用户群也是巨大的，使得用户的移 动数据也得到了大量的积累。根据街旁网的官方数据，从2010年5月上线到2013年7月，街旁用户数已经突破了500万，累计签 到次数超过8000万次。根据Foursquare的统计数据，从2009年3月上线到2013年12月，用户数已经达到了4500万，累计签到 数高达50亿。 这些大规模移动数据的积累，为基于位置的智能服务提供了重要的基础条件。目前，这些基于位置的智能服务开辟了一个正 在快速增长的市场。一份来自MarketsandMarkets的研究报告预计，诸如导航、移动广告、移动社交网络等基于位置的智能服 务的市场份额将从2016年的113亿美元增长到2020年的549亿美元1。下面我们列举一些基于位置的智能服务的重要案例。通 过分析大量的历史活动轨迹数据或出行数据，为人们的日常出行和旅游给出合适的路线和兴趣点的推荐2345。基于位置社 交网络数据，挖掘本地人和外地人涉猎区域上的差异性，从而帮助人们学习到本地化的相关知识，比如利用北京本地人的生活经 验，给来北京旅游的外地人推荐性价比较高的餐馆和酒店6。东京大学联合微软亚洲研究院利用一百多万人三年的GPS轨迹、 日本的自然灾害资料及灾害的官方和新闻媒体报道，来分析建模灾后人们的移动行为规律，从而生成并模拟灾害发生后的最优移 动线路7。如AirSage公司一般每天通过处理来自上百万手机用户的150亿条位置信息，为美国的100多个城市提供实时交通信 息8。微软研究人员提出的T-Drive系统9可分析33000辆北京出租车的GPS轨迹，来帮助出行人员得出更优的驾车路线。测 试证明，推荐的驾车路线和Bing Maps或Google Maps内置的路线搜索相比，有60的路线更优，可节省16的时间。类似 地，他们还设计了T-Finder系统10，不仅可以为出租车司机推荐具有高密度客源的邻近区域，从而减少了出租车司机的空载时 间，还可以为乘客推荐有更高上车概率的邻近上车地点，从而减少了乘客的等待时间。无线数据科技公司（Jana）使用来自 100多个国家的、超过200个通信运营商提供的、覆盖了大约35亿人口的基站连接数据，将其转换为用户移动轨迹之后，来研究 疾病传播、城市发展、人类迁移等具有重大意义和价值的科学问题11。传统的车险业一般是通过评估群体的平均风险来为车 险定价，但是当保险公司分析了车辆出行时间、常见行驶地点和实际行驶过程等移动数据之后，便可以转变为对每个客户的个性 化风险评估和车险定价，从而改变了车险业的运营方式12。联合包裹运输公司（UPS公司）收集运输车辆的行驶轨迹信息， 并为它们提供最佳行车路线，从而减少燃油消耗、降低故障成本，在商业模式上取得了巨大的成功。据统计，仅2011年，UPS 公司旗下的车辆行驶路程就缩短了4828万公里，间接减少了1136万升的燃料和3万吨二氧化碳的排放13。从最后的两个案例可 以看到，移动数据的挖掘与分析甚至可以改变公司业务的运作方式，暗含了巨大的商业价值。 1 http:/bit.ly/1mda1Hv。 2 D Lian，C Zhao，et al.Geomf：joint geograph-ical modeling and matrix factorization for point-of-interest recommendationC.In Proceedings of KDD14，ACM，2014. 3 M Ye，P Yin，et al.Exploiting geographical influence for collaborative point-of-interest recommendationC.In Proceedings of SIGIR11，ACM，2011. 4 V Zheng，B Cao，et al.Collaborative filtering meets mobile recommendation：Auser-centered approachC.In Proceedings of AAAI10.AAAl Press，2010. 5 Y Zheng and X Xie.Learning travel recommendations from user-generated gps tracesJ.ACM Transaction Intelligent Systems Technology.（TIST），2011，2（1）：2. 6 Z Yang，N J Yuan，et al.Indigenization of urban mobilityC.arXiv preprint arXiv：1405.7769，2014. 7 X Song，Q Zhang，et al.A simulator of human emergency mobility following disasters：Knowledge transfer from big disaster dataC.In Proceedings of AAAI15，2015. 8 C W Smith，I Clayton Wilkinson，et al.System and method for providing traffic information using operational data of a wireless network： US Patent，6，842，620P.Jan.11，2005. 9 J Yuan，Y Zheng，et al.T-drive：driving directions based on taxi trajectoriesC.In Proceedings of GIS10，ACM，2010. 10 N J Yuan，Y Zheng，et al.T-finder：A recommender system for finding passengers and vacant taxisJ.Knowledge and Data Engineering，IEEE Transactions on，2013，25（10）：2390-2403. 11 S Hill，A Banser，et al.Reality mining africaC.In AAAI Spring Symposium：Artificial Intelligence for Development.Citeseer，2010. 12 T Litman.Distance-based vehicle insurance：feasibility，costs and benefitsEB/OL.www.vtpi.org/d-bvi_com.pdf. 13 H Zhong，D Zaret.Core area territory planning for optimizing driver famil-iarity and route flexibility，US Patent，7，363，126P.Apr.22，2008. 1.2 概念与定义 前面提到移动数据是移动轨迹的集合，而移动轨迹是移动记录的有序序列。移动记录是时间，位置对，可以记录诸如用 GPS设备等连续采样的数据，也可以记录诸如移动社交网络中签到等事件类型的数据。对于GPS设备采集的连续位置信息存在停 留点，用户需要在附近停留一定的时间。因而，停留点是带有位置、到达时间及停留时间信息的点。对于非停留点位置，用户可 能只是路过所以并不感兴趣，因而连续的GPS位置数据通常会被处理成停留点的序列。移动社交网络是移动位置服务和社交媒体 的结合体，是一种与朋友分享地点访问信息的社交平台，可用于帮助人们更加便利、快捷地探索周边环境和配套设施。其中分享 的地点访问信息就是移动社交网络中的签到。在签到时，一般是从兴趣点数据库中选择所访问的兴趣点，加上简短的话语分享感 受。如果有更深刻的感触，还可以分享更加丰富的攻略信息甚至有趣的照片等。兴趣点是带有名字、语义信息的地点，比如餐 馆、酒店、电影院等。诸如大众点评网和Yelp等本地服务平台纷纷兴起，大众点评网可以对地点进行打分和点评，来说明兴趣 地点的好和差。点评信息和攻略信息有些类似，只是攻略信息没有打分。 用户的移动历史信息除了可以表示为一个地点序列以外，还可以被处理为一个用户地点访问的二部图，在二部图中，图的顶 点被分为两个不相交的子集，一个为用户集，一个为地点集。二部图的边只存在于两个子集之间，表示用户访问了某个地点，边 的权重可以表示为访问次数。而子集内的顶点之间，即用户之间和地点之间，则无边相连。假设用户的集合为U=u1， ，uM，地点的集合为L=l1，lN，cu，i则表示用户集中的某一个用户u对地点集中的某一个地点i的访问次数，对应于二部 图中的边权。众所周知，图可以用矩阵来表示，二部图同样也不例外。假设用矩阵C表示这个二部图，每一行对应每一个用户， 每一列表示每一个地点，那么矩阵中的每一个元素cu，i便对应了二部图中的边权。随着城市的发展，可供人们访问的诸如餐馆、 酒店、商场等地点是越来越多了。由于每个用户只会访问很少一部分地点，因此这个矩阵便是稀疏的。 移动社交网络中的社交网络是由顶点和边组成的图结构，顶点是用户，边表示用户之间的关系，比如是否为朋友关系，或者 亲密程度等。如果边表示亲密程度，那么图就是加权网络。如果关系是有方向的，比如微博中的关注关系，那么图就称为有向 图。如果用户之间是双向关系，比如Facebook中的关系，那么图就为无向图。由于一个用户的朋友数有限，因此社交关系图就 是稀疏的。图可以用矩阵来表示，社交关系图就可以用稀疏方阵来表示。对于双向关系的无向图，对应的稀疏矩阵便是对称的； 而对于单向关系的有向图，对应的稀疏矩阵基本上就是非对称的。对于社交网络中的任意节点，其一度朋友是指该节点的直接邻 居（朋友），二度朋友则是指该节点的朋友的朋友。随着度的增加，与该节点关联的节点越来越多。针对在线社交网络的研究， 可以发现在线社交网络基本上都是小世界网络，满足“小世界理论”。“小世界理论”是指人们和任何一个陌生人之间所间隔的 人不会超过6个。因而，达到一定的度之后，每个节点所关联的节点可能就会覆盖整个网络1。 1 E David，K Jon.Networks，Crowds，and Markets：Reasoning About a Highly Connected WorldM.New York：Cambridge University Press，2010. 1.3 挑战 移动数据的形式多种多样，有来自移动社交网络中的签到数据、与基站通信时的日志数据，还有公交交通工具的刷卡数据、 美钞的交易数据，等等，它们的特点也各有不同，具体表现在采样频率、数据采集方式、定位精度等。不过针对这些数据的挖掘 所面临的挑战是类似的。 ·可扩展性 移动数据的规模巨大，不仅源于用户群的规模，而且源于数据的产生速率。如此大规模的移动数据要求移动数 据的挖掘算法需要具有较高的可扩展性。这种可扩展性应该尽可能地利用移动数据的诸如本地化、空间聚集等特性（将在第2章 介绍）。 ·稀疏性 尽管移动数据规模巨大，但是每个人所拥有的非冗余信息非常有限，因而面临稀疏性的挑战。若以移动社交网络 Foursquare中的签到数据为例，根据统计12，用户平均每天只分享25个位置访问记录。因而要从如此稀疏的数据中去学习人 们的日常生活模式和兴趣偏好就变得异常困难。在基站定位数据中，根据宋超明（音译）等人的分析3，我们发现人们探索新地 点的速率是随着时间增长而迅速减小的。即当人们熟悉了他们的周遭环境之后，便很少会继续探索新地点。因而，即使人们时刻 分享其位置访问记录，这些分享的记录也都是冗余的。冗余的信息虽然可以帮助了解人们的日常生活规律，但是要从中深入了解 人们的兴趣偏好也是一件挑战性很高的事情。 ·群体智慧 在移动社交网络中，人们趋于分享他们的感受和关注。通过评论、排名等方式可以很容易地获取群体的智慧。 与用户交互在一起的各类元信息对于移动数据挖掘的很多任务是有巨大价值的。另外，人们通过对地点的访问而相互关联在一 起，那么应该如何利用这些关联性来缓解稀疏性从而帮助了解人们的兴趣偏好呢？ ·异质性 移动数据挖掘的任务通常需要多个数据源共同支持。比如城市交通中事故的检测可能需要同时分析出租车的轨迹 和监控的视频。兴趣地点的发现可能需要借助人们诸如年龄、性别、教育情况、任职情况等的基本信息，还可能需要社交网络上 的社交关系，兴趣地点的物理位置信息、评论和攻略等文本内容，分享的图片信息，等等。城市功能区域的发现需要区域出入信 息、周遭兴趣点信息，等等。因此，移动数据的挖掘需要设计诸如多视图、多核学习或共同矩阵分解等相关算法来处理这些多源 异构的数据。 1 D Lian，X Xie，et al.Cepr：A collaborative exploration and periodically returning model for location predictionJ.ACM Transaction Intelligent Systems Technology，2015，6（1）：8：1-8：27. 2 H Gao，J Tang，X Hu，et al.Exploring temporal effects for location recommendation on location-based social networksC.In Proceedings of RecSys13，ACM，2013. 3 C Song，T Koren，et al.Modelling the scaling properties of human mobilityJ.Nature Physics，2010，6（10）：818-823. 1.4 本书简介 在这些挑战之下，本书将主要以人的轨迹数据，特别是移动社交网络的位置数据为中心，结合人的基本信息及社交网络等相 关信息来研究个人与群体的移动模式特性，具体包括用户移动建模、基于移动数据的用户画像及个性化兴趣地点推荐等。 ·在介绍移动数据的挖掘内容之前，我们先会介绍移动数据的预处理方法。数据预处理通常是数据挖掘的第一步，也是非常 重要的一步，它可能会影响到后续挖掘算法在移动数据中的准确性或可用性。在移动数据预处理的章节（第2章）中，我们会介 绍缺失数据的补全和噪声数据的清除，这些主要针对用户室内定位数据的丢失或漂移问题，以及由于业务本身造成的数据缺失问 题等等。那些连续收集的GPS轨迹数据通常存在大量冗余，因而需要利用聚类算法进行重要位置或事件的检测，比如路径轨迹中 停留时间较长的地点。但是这些被提取出来的重要位置一般没有语义信息，如何基于有监督学习的算法利用诸如兴趣点、可开展 活动的信息对这些重要位置进行标记或命名，也是预处理部分需要介绍的内容。 ·对人类移动模式的理解是自然科学的重要内容，它对于交通规划、疾病传播、城市规划等具有重要的作用。人类移动模式 的理解主要在于了解人类移动背后的规律，并在此基础上对人类的移动进行建模，从而预测人类的未来移动。第3章将从人类动 力学角度和数据挖掘两个角度来阐述对人类移动模式的理解。人类动力学角度是将每个个体当作物理学中的粒子，基于粒子的物 理移动模型（比如连续的随机游走模型）来建模研究人类的移动行为，具有很强的物理学意义和解释性。而基于数据挖掘的移动 模型则是从数据出发，利用如马尔可夫模型或时间规律性模型来分析用户的移动特性。此外，该章还会介绍移动模式中的时空聚 类特性，以及如何度量社交网络对于移动行为特性的影响。然而，根据宋超明等人1的分析，在数据较为完整的基站轨迹数据 中，用户行为的可预测性虽然高达93，但是仍然存在7的不规律行为（文中称为地点探索行为）。为此，该章也会阐述对这 类移动行为的分析和预测，同时介绍统一的算法框架来同时预测规律性行为和探索行为。 ·不同用户的移动模型均会有所差别，但也存在很多共性。这种共性可能是他们共同的属性或特质决定的，使得从用户的移 动模型去推导用户的基本属性或特质成为可能。因此，在第4章中，将介绍基于移动数据的用户画像，利用分类算法或回归算法 对用户的显性属性和隐性属性进行预测。其中的显性属性是指年龄、性别、教育背景等基本信息，而隐性属性则是指一些心理特 性，比如消费冲动心理、新颖性探索特性，等等。对这类问题的研究使得提出准确率更高的预测算法成为可能。另外，不管是隐 性属性还是显性属性，出于隐私的考虑，人们都不会轻易地将其分享出来，因而用户画像可以为精准的移动广告和精准营销提供 重要的依据。也就是说，系统可以根据移动行为的特性来投放相应的广告。 ·针对移动数据的挖掘，我们不仅可以刻画人们的时空规律性，而且还可以学习人们的兴趣偏好，进而推荐适合他们的未访 问过的兴趣地点。这种兴趣的挖掘一般是通过聚类等降维技术或协同过滤等学习方法来实现的。在第5章中，首先会根据兴趣地 点推荐问题重点介绍协同过滤方法在移动数据上的应用研究。由于地点是内嵌在地理空间中的，人们对地点的访问存在空间聚集 效应，即符合地理学第一定律“任何事物都相关，只是相近的事物关联得更紧密”，我们将重点考虑地理影响力的建模。如 果将地点的物理位置作为地点内容信息，地理建模就是一种基于内容的推荐方法。除了地理信息以外，被推荐的地点通常还有其 他很多的诸如评论等的文本信息，那么如何针对这些文本信息进行基于内容的推荐？最后，将介绍统一的兴趣地点的推荐模型， 来同时考虑这些重要的要素。主要包括介绍如何基于这些用户属性和地点的内容属性实现在移动数据不完整的情况下（冷启动） 的推荐问题，这一点与第4章从移动模型预测用户属性的出发点刚好相反。另外，地点的推荐应该是在一定的情境，比如说特定 时间之下完成的，因此情境感知的地点推荐方法也是该章的重要内容之一。 1 C Song，Z Qu，et al.Limits of predictability in human mobilityJ.Science，2010，327（5968）：1018-1021. 第2章 移动数据预处理 在本章中，首先对移动数据及其特性进行介绍，再介绍针对移动数据的预处理。因为移动数据的挖掘是从原始移动数据、语 义移动数据等多个层次进行的，在挖掘时总是会出现各种各样的数据缺失或数据异常。因此，本章的数据预处理包括缺失数据补 全、重要地点检测、语义信息标注三个方面，预处理的目的就在于更好地为后续移动数据的挖掘和分析做准备。 2.1 移动数据简介 移动数据的类型众多、范围较广，有来自于人类日常生活中使用手机等智能设备留下的印记，也有为研究人类和动物等的日 常行为规律而收集的轨迹数据。本书中，我们主要关注和人相关的移动数据，这些数据不仅包括GPS轨迹12、基站定位数 据34、公交卡轨迹5、Wi-Fi定位数据6、美钞交易地点轨迹7等，还包括移动社交网络中的签到轨迹89、带有GPS标记的 图片轨迹10等。 这些不同类型的数据的来源、特点各不相同，如表2.1所示，因而就有不同的分类方法。从收集的意愿性来考虑，有被动收 集和主动收集之分。比如基站定位数据便因用户使用手机打电话、发短信和上网时连接基站而记录，这种记录是源于手机通信过 程的需要，是一个被动过程；Wi-Fi定位数据和基站定位数据类似，是用户访问网络时连接Wi-Fi热点而记录的，也是一个被动过 程；再比如，公共交通工具的乘坐轨迹因计费需求来记录乘客的上车地点或下车地点而产生，也是一个被动过程。而诸如移动社 交网络中的签到轨迹、图片轨迹等均属于主动收集或主动上报的数据，因为签到数据是人们在访问地点之后出于趣味性希望与朋 友分享从而通过社交媒体记录的数据，图片轨迹是人们在看到适合场景拍摄照片时留下的地理印记而累计形成的。然而，GPS的 轨迹数据出于记录载体的不同，既有可能是被动记录的，比如出租车公司出于管理的目的在出租车上装备GPS设备而记录的轨迹 就是被动收集的数据，也有可能是主动记录的，比如发动志愿者携带GPS设备记录日程出行轨迹的过程便是主动收集的过程。 表2.1 移动数据对比 由于收集意愿的不同，可能会导致所收集的数据在时间和空间上均呈现不同的粒度，数据的缺失性也存在很大的差异性。大 部分被动记录的数据，由于较难受到人们意志的影响，因此位置数据较为连续，时间粒度较小，缺失性较低。比如，对于基站定 位数据，只要用户使用手机打电话或发短信就都会被记录的。不过若没有任何的通信需求，则用户的位置无法被记录，因此在位 置轨迹上存在一定的缺失性。而针对主动记录的数据，出于隐私的原因和趣味性程度的差异性，可能大部分的位置数据都是缺失 的，位置的连续性就很弱，时间的粒度也就更大。比如，大部分人都不愿意在家里签到；人们一般在景点附近才拍照来与朋友们 分享游玩的心情。 移动数据具有如下特性： ·本地化特性 本地化特性是指人们在不同城市中具有不同的移动行为模式，特别地，人们在本地城市和外地城市上的行为 具有本质性区别。在任何一个城市，人们都可被分为本地人和外地人。最简单的方法是为每个人确定居住城市，把居住城市作为 人们的本地城市。另外一种方法是通过判定移动数据的使用情况，检查人们在各个城市的停留时间和访问模式来判定是否为本地 人。根据这种区分，本地人和外地人在访问城市的兴趣地点时究竟有什么样的差异呢？先看看图2.1来感受一下北京本地人与外 地人的差异性及上海本地人与外地人的差异性。对于本地人来说，由于他们对本地城市的熟悉度较高，所以他们不仅会访问居住 地和工作地周边的兴趣地点，也会探索新的兴趣地点，因而，本地人的访问地点分布非常广；相反，外地人对城市不够熟悉，他 们更多地依赖于兴趣地点的热度，更多地去访问那些很流行的地点，因而他们的访问区域是较为集中的。而且这种直觉完全可以 利用统计量反映出来。比如说，外地人群体层面对地点的访问次数分布相比较于本地人群体，应该更加不均匀。为此，可分别统 计本地人和外地人对每个地点的访问频率，绘制出洛伦兹曲线，来看地点访问次数分布的均匀性，如图2.2所示。洛伦兹曲线原 本是为表示财富分布的不平等性而提出的。对角虚线代表的是财富完全平等时的曲线。洛伦兹曲线和对角线之间的面积代表不平 等的大小。在图2.2中，横坐标表示的是地点的百分比，而纵坐标表示的是相应地点的访问频率之和与在所有地点的访问频率之 和的比例。从图2.2可以看到，北京的外地人对地点访问频率的分布更加集中，更加不均匀，即只访问少数的几个非常流行的地 点。不过上海的外地人和本地人的差别则较小，不过这种本地化特性仍然是存在的。移动数据的本地化特性反映本地人和外地人 访问模式上的差异性，要求移动数据挖掘分别针对本地人和外地人进行考虑，甚至还要为本地人和外地人设计不同的挖掘算法。 比如在兴趣地点推荐中，有专门的算法11被设计来为外地人推荐地点，称为出城推荐。 图2.1 地点访问频率的密度图 图2.2 北京（a）和上海（b）的外地人和本地人对地点访问次数的洛伦兹曲线 ·地点访问次数的幂律分布 在本地化特性中，群体层面访问地点会表现出异质性，而个体层面访问地点时也会呈现这种异 质性。特别地，每个用户只会经常访问少数几个地点，而只会偶尔访问其他地点。将地点按照访问次数从高到低进行排序，那么 第k个访问地点的访问频率fk满足Zipf定律， 即 ·在不同数据集中的大小是不同的。在基站定位数据中12，1.2±0.1。求该函数的逆函数它表示的是访问频率为 fk的地点的排名，也就是它反映了有多少个地点的次数是大于fk的，即指示了访问频率的逆累计概率函数。形式上为 根据逆累计概率函数和概率密度之间的关系，可以得出访问频率的密度分布满足幂律分布p（f）f-（1+1/）。这种访 问次数满足幂律分布的移动数据，使得在设计移动模型和推荐算法时需要特别考虑。比如Pitman-Yor过程被用来做移动建模13， 因为它刚好能满足访问次数的幂律分布特性。Pitman-Yor过程曾被用于在语言模型之中建模单词之间的依赖关系，而根据Zipf等 人的研究，单词的使用频率也是满足幂律分布的，且刚好与移动数据中的移动建模相对应。 ·空间聚集效应 空间聚集效应是地理学第一定律14的一种表现形式，表示一个用户所访问的地点相互之间不是独立的， 而是受距离远近约束的。这种空间聚集效应可以通过两种方式进行解释。从物理学角度出发，通过随机游走进行建模，其关注的 一个统计量是相邻访问地点之间的距离。根据对美钞交易数据15、基站定位数据16、GPS轨迹17等的研究，可以发现连续访问 地点之间的距离满足幂律分布，表示人们移动时经常访问距离当前地点不远的地点，偶尔可能会访问远处的地点。图2.3a给出了 移动距离满足幂律分布的轨迹图，明显地展示出了聚集效应。虽然随机游走模型具有“漂亮”的表示公式，但是数据中很多实际 特性无法表示出来。因而，从数据中发现移动模式便成为一种更为实际的方法。空间聚集效应可以直接从数据中发现18，如图 2.3b所示。这种模式是通过聚类方法实现的。每个发现的类簇都可以认为是用户移动模式中的一个主要枢纽，比如家或工作场 所，人们在这些主要枢纽之间移动19。同时，人们会在某些时候在这些主要枢纽周围访问其他的地点，诸如购物中心、餐馆 等。这种空间的聚集效应对于移动建模具有重大的影响，使得在用户移动建模和兴趣地点推荐中必须考虑这种特性。比如在用户 移动建模中，时间依赖的地理空间混合模型被提出。在兴趣地点推荐中，空间聚集效应的建模，特别是与传统协同过滤方法的结 合，成为了重要的研究问题。 图2.3 空间聚集效应特性说明 ·规律性 规律性包括周期性和序列相关性。周期性是指事件间隔一定时间定期发生，包括日模式、周模式等。比如说，学 生早上8点30分去教学楼上课，12点去食堂吃饭，晚上8点去上自习等。这种周期性是可以测量的。给定任意一个地点，估计后续 访问时间与首次访问时间间隔的概率，称为返回概率。比如关于12点去食堂吃饭，假设首次是某天的12点，第二次是后一天的12 点，那么这个间隔即为24小时，第三次是后两天的12点，此时的间隔为36小时。虽然对于不同的地点，访问时间区间有所不同， 但是可通过计算和首次访问时间的差值将它们对齐。将多个地点的时间间隔放在一起，便可以估计每个人的规律性。这种规律性 已经在基站定位数据和移动社交网络中被度量出来，如图2.4所示。该图显示这些移动数据具有很强的日模式，而且在不同的移 动数据上周期性强度不同。基于这种时间的规律性，可以设计周期性的预测模型来预测移动模式。除了周期性是一种规律性以 外，序列相关性也是规律性的一种重要指标。序列相关性是指下一个访问的位置是与访问地点历史序列相关的。如果假设只与前 K个位置相关，那么这个序列相关性便是K+1阶的马尔可夫性。在不同的移动数据中，这种序列相关性的强度也是不同的。这种 序列相关性的强度直接对应了移动数据的冗余性和可预测性20，在序列相关性强的移动数据中，冗余性较高，可预测性也较 高，规律性就比较高。序列相关性可以通过序列熵（科尔莫洛夫熵）来度量，具体的细节可以参考3.2.1节。对于不同序列相关性 的移动数据，所设计的用户移动建模将采用不同复杂度的预测模型。对于序列相关性较高的移动数据，可以使用更高阶的马尔可 夫模型来为移动模式建模，比如在GPS轨迹中，二阶的马尔可夫模型被用于下一地点的预测21。而在移动社交网络中，带有回 退（fall-back）的一阶马尔可夫模型则被用作未来地点的预测，而且