本节书摘来自华章出版社《移动数据挖掘》一 书中的第2章，第2.1节，作者连德富 张富峥 王英子 袁晶 谢幸，更多章节内容可以访问云栖社区“华章计算机”公众号查看。
第2章 移动数据预处理
第2章 移动数据预处理在本章中，首先对移动数据及其特性进行介绍，再介绍针对移动数据的预处理。因为移动数据的挖掘是从原始移动数据、语义移动数据等多个层次进行的，在挖掘时总是会出现各种各样的数据缺失或数据异常。因此，本章的数据预处理包括缺失数据补全、重要地点检测、语义信息标注三个方面，预处理的目的就在于更好地为后续移动数据的挖掘和分析做准备。
2.1 移动数据简介
移动数据的类型众多、范围较广，有来自于人类日常生活中使用手机等智能设备留下的印记，也有为研究人类和动物等的日常行为规律而收集的轨迹数据。本书中，我们主要关注和人相关的移动数据，这些数据不仅包括GPS轨迹［5,158］、基站定位数据［35,114］、公交卡轨迹［144］、Wi-Fi定位数据［115］、美钞交易地点轨迹［14］等，还包括移动社交网络中的签到轨迹［61,63］、带有GPS标记的图片轨迹［4］等。这些不同类型的数据的来源、特点各不相同，如表2.1所示，因而就有不同的分类方法。从收集的意愿性来考虑，有被动收集和主动收集之分。比如基站定位数据便因用户使用手机打电话、发短信和上网时连接基站而记录，这种记录是源于手机通信过程的需要，是一个被动过程；Wi-Fi定位数据和基站定位数据类似，是用户访问网络时连接Wi-Fi热点而记录的，也是一个被动过程；再比如，公共交通工具的乘坐轨迹因计费需求来记录乘客的上车地点或下车地点而产生，也是一个被动过程。而诸如移动社交网络中的签到轨迹、图片轨迹等均属于主动收集或主动上报的数据，因为签到数据是人们在访问地点之后出于趣味性希望与朋友分享从而通过社交媒体记录的数据，图片轨迹是人们在看到适合场景拍摄照片时留下的地理印记而累计形成的。然而，GPS的轨迹数据出于记录载体的不同，既有可能是被动记录的，比如出租车公司出于管理的目的在出租车上装备GPS设备而记录的轨迹就是被动收集的数据，也有可能是主动记录的，比如发动志愿者携带GPS设备记录日程出行轨迹的过程便是主动收集的过程。
由于收集意愿的不同，可能会导致所收集的数据在时间和空间上均呈现不同的粒度，数据的缺失性也存在很大的差异性。大部分被动记录的数据，由于较难受到人们意志的影响，因此位置数据较为连续，时间粒度较小，缺失性较低。比如，对于基站定位数据，只要用户使用手机打电话或发短信就都会被记录的。不过若没有任何的通信需求，则用户的位置无法被记录，因此在位置轨迹上存在一定的缺失性。而针对主动记录的数据，出于隐私的原因和趣味性程度的差异性，可能大部分的位置数据都是缺失的，位置的连续性就很弱，时间的粒度也就更大。比如，大部分人都不愿意在家里签到；人们一般在景点附近才拍照来与朋友们分享游玩的心情。
移动数据具有如下特性：
● 本地化特性 本地化特性是指人们在不同城市中具有不同的移动行为模式，特别地，人们在本地城市和外地城市上的行为具有本质性区别。在任何一个城市，人们都可被分为本地人和外地人。最简单的方法是为每个人确定居住城市，把居住城市作为人们的本地城市。另外一种方法是通过判定移动数据的使用情况，检查人们在各个城市的停留时间和访问模式来判定是否为本地人。根据这种区分，本地人和外地人在访问城市的兴趣地点时究竟有什么样的差异呢？先看看图2.1来感受一下北京本地人与外地人的差异性及上海本地人与外地人的差异性。对于本地人来说，由于他们对本地城市的熟悉度较高，所以他们不仅会访问居住地和工作地周边的兴趣地点，也会探索新的兴趣地点，因而，本地人的访问地点分布非常广；相反，外地人对城市不够熟悉，他们更多地依赖于兴趣地点的热度，更多地去访问那些很流行的地点，因而他们的访问区域是较为集中的。而且这种直觉完全可以利用统计量反映出来。比如说，外地人群体层面对地点的访问次数分布相比较于本地人群体，应该更加不均匀。为此，可分别统计本地人和外地人对每个地点的访问频率，绘制出洛伦兹曲线，来看地点访问次数分布的均匀性，如图2.2所示。洛伦兹曲线原本是为表示财富分布的不平等性而提出的。对角虚线代表的是财富完全平等时的曲线。洛伦兹曲线和对角线之间的面积代表不平等的大小。在图2.2中，横坐标表示的是地点的百分比，而纵坐标表示的是相应地点的访问频率之和与在所有地点的访问频率之和的比例。从图2.2可以看到，北京的外地人对地点访问频率的分布更加集中，
更加不均匀，即只访问少数的几个非常流行的地点。不过上海的外地人和本地人的差别则较小，不过这种本地化特性仍然是存在的。移动数据的本地化特性反映本地人和外地人访问模式上的差异性，要求移动数据挖掘分别针对本地人和外地人进行考虑，甚至还要为本地人和外地人设计不同的挖掘算法。比如在兴趣地点推荐中，有专门的算法［9］被设计来为外地人推荐地点，称为出城推荐。
● 地点访问次数的幂律分布 在本地化特性中，群体层面访问地点会表现出异质性，而个体层面访问地点时也会呈现这种异质性。特别地，每个用户只会经常访问少数几个地点，而只会偶尔访问其他地点。将地点按照访问次数从高到低进行排序，那么第k个访问地点的访问频率fk满足Zipf定律，即fk～k-ζ（2.1）ζ在不同数据集中的大小是不同的。在基站定位数据中［113］，ζ≈1.2±0.1。求该函数的逆函数k～f-1/ζk，它表示的是访问频率为fk的地点的排名，也就是它反映了有多少个地点的次数是大于fk的，即指示了访问频率的逆累计概率函数。形式上为Pr(f>fk)～f-1/ζk。根据逆累计概率函数和概率密度之间的关系，可以得出访问频率的密度分布满足幂律分布p(f)～f-(1+1/ζ)。这种访问次数满足幂律分布的移动数据，使得在设计移动模型和推荐算法时需要特别考虑。比如Pitman-Yor过程被用来做移动建模［30］，因为它刚好能满足访问次数的幂律分布特性。Pitman-Yor过程曾被用于在语言模型之中建模单词之间的依赖关系，而根据Zipf等人的研究，单词的使用频率也是满足幂律分布的，且刚好与移动数据中的移动建模相对应。●空间聚集效应 空间聚集效应是地理学第一定律 任何事物都相关，只是相近的事物关联更紧密。的一种表现形式，表示一个用户所访问的地点相互之间不是独立的，而是受距离远近约束的。这种空间聚集效应可以通过两种方式进行解释。从物理学角度出发，通过随机游走进行建模，其关注的一个统计量是相邻访问地点之间的距离。根据对美钞交易数据［14］、基站定位数据［35］、GPS轨迹［101］等的研究，可以发现连续访问地点之间的距离满足幂律分布，表示人们移动时经常访问距离当前地点不远的地点，偶尔可能会访问远处的地点。图2.3a给出了移动距离满足幂律分布的轨迹图，明显地展示出了聚集效应。虽然随机游走模型具有“漂亮”的表示公式，但是数据中很多实际特性无法表示出来。因而，从数据中发现移动模式便成为一种更为实际的方法。空间聚集效应可以直接从数据中发现［21］，如图2.3b所示。这种模式是通过聚类方法实现的。每个发现的类簇都可以认为是用户移动模式中的一个主要枢纽，比如家或工作场所，人们在这些主要枢纽之间移动［131］。同时，人们会在某些时候在这些主要枢纽周围访问其他的地点，诸如购物中心、餐馆等。这种空间的聚集效应对于移动建模具有重大的影响，使得在用户移动建模和兴趣地点推荐中必须考虑这种特性。比如在用户移动建模中，时间依赖的地理空间混合模型被提出。在兴趣地点推荐中，空间聚集效应的建模，特别是与传统协同过滤方法的结合，成为了重要的研究问题。
● 规律性 规律性包括周期性和序列相关性。周期性是指事件间隔一定时间定期发生，包括日模式、周模式等。比如说，学生早上8点30分去教学楼上课，12点去食堂吃饭，晚上8点去上自习等。这种周期性是可以测量的。给定任意一个地点，估计后续访问时间与首次访问时间间隔的概率，称为返回概率。比如关于12点去食堂吃饭，假设首次是某天的12点，第二次是后一天的12点，那么这个间隔即为24小时，第三次是后两天的12点，此时的间隔为36小时。虽然对于不同的地点，访问时间区间有所不同，但是可通过计算和首次访问时间的差值将它们对齐。将多个地点的时间间隔放在一起，便可以估计每个人的规律性。这种规律性已经在基站定位数据和移动社交网络中被度量出来，如图2.4所示。该图显示这些移动数据具有很强的日模式，而且在不同的移动数据上周期性强度不同。基于这种时间的规律性，可以设计周期性的预测模型来预测移动模式。除了周期性是一种规律性以外，序列相关性也是规律性的一种重要指标。序列相关性是指下一个访问的位置是与访问地点历史序列相关的。如果假设只与前K个位置相关，那么这个序列相关性便是K+1阶的马尔可夫性。在不同的移动数据中，这种序列相关性的强度也是不同的。这种序列相关性的强度直接对应了移动数据的冗余性和可预测性［114］，在序列相关性强的移动数据中，冗余性较高，可预测性也较高，规律性就比较高。序列相关性可以通过序列熵（科尔莫洛夫熵）来度量，具体的细节可以参考3.2.1节。对于不同序列相关性的移动数据，所设计的用户移动建模将采用不同复杂度的预测模型。对于序列相关性较高的移动数据，可以使用更高阶的马尔可夫模型来为移动模式建模，比如在GPS轨迹中，二阶的马尔可夫模型被用于下一地点的预测［6］。而在移动社交网络中，带有回退（fall-back）的一阶马尔可夫模型则被用作未来地点的预测，而且一阶的马尔可夫性的强度很弱，能起到的作用很小。
● 新颖性探索 新颖性探索指人们不总是按照过往的惯例访问熟悉地点，偶尔也会去探索一些新颖地点。根据参考文献［114］，即使在规律性较高的基站定位数据中，也只有93％的可预测性。剩下7％的行为是无法基于个人历史行为进行预测的，它被认为是在探索性行为范畴之内的。新颖性探索说明人们访问的不同地点数目是随着时间而增长的，根据宋超明等人的研究发现［113］，假设S(t)表示在t时刻之前访问的不同地点数，满足S(t)～tμ（2.2）其中μ=0.6±0.02。这种规律背后的解释是随着时间的增长，人们对城市及周边环境的熟悉程度逐渐得到提升，减少了人们探索新地点的机会，或者使得人们需要花费更大的代价才能进行探索。有趣的是，这种新颖性探索趋势是可以被估计出来的。比如在参考文献［113］中所提到的，新颖性探索的概率和访问过的地点数有关，满足Pr(explore)=ρS-r（2.3）其中S就是人们访问的不同地点数。而在参考文献［61］中，新颖性探索被形式化为一个二分类问题，即判断下一访问的地点是否在移动数据的历史之中，具体可以细看3.2.6节的内容。这种新颖性探索特性在移动数据挖掘中需要特别考虑，这不仅是提升移动行为预测能力的一种重要保障，而且是基于降维技术进行用户画像的一种依据，其本身也是移动数据挖掘的一项重要内容。
