1 绪论
1.1 研究背景
随着移动互联网、无线通信技术以及各种定位技术的快速发展，多种移动终端设备的普及使用，手机上网的人群占比正在逐年增加，为基于位置的服务（Location Based Service，LBS）提供了庞大的用户基础。位置服务指向大众或行业用户提供的与位置相关的诸如定位、导航、路径查询的各种服务，如微信提供的共享实时位置，百度地图提供的路线导航等，都是基于移动通信网络与定位技术提供的位置服务。因为移动终端设备所提供位置服务的便携性、移动性、实时性，越来越多的用户投身使用。在 2016 年 7 月来自于中国互联网络信息中心发布的第38 次中国互联网络发展状况统计报告[1]中指出，截至 2016 年 6 月，我国手机网民规模达 6.56 亿，占总体网民的 92.5%，手机在上网设备中占据主导地位。其中，有 61.0%的手机用户使用基于位置服务查找周围商场等购物场所，有 78.9%的手机用户使用基于位置服务接受当地热点新闻推送，有 78.7%的手机用户使用基于位置服务发布带实时坐标的微信朋友圈。各项数据表示，位置服务已经参与到人们生活的方方面面。在使用位置服务应用的过程中，会产生一系列移动对象的位置数据，包括地理位置坐标及其产生的时间。位置数据中蕴含着丰富的空间、时间结构信息，这些时空信息代表着移动对象在真实世界的活动轨迹，而这些活动轨迹的频繁度在一定程度上体现了移动对象的意图、生活习惯和行为模式。因此，通过分析与挖掘大量位置数据，从而得到对象的行为模式，对于对象相似度计算，人群分类，行为预测，推荐系统构建等领域都具有重大意义。但随着移动终端的广泛使用，位置服务应用的快速崛起，移动对象的位置数据量也呈指数级增长。因此原始位置数据存在着高维度的特点，给后续工作带来了巨大的困难。因此，如何降低原始位置数据的计算复杂度，同时保留数据中的重要信息，进而有效挖掘出移动对象的行为动机和行为模式，是眼下的急切需求。因此为了解决在位置数据急剧增加的时代，如何从高维数据中挖掘可解释性良好的移动对象特征，进而抽取移动对象的行为模式这一问题，降维算法成为研究此类问题的必要途径，移动对象行为模式抽取则是解决此类问题的关键。
.........
1.2 研究目标与意义
移动终端设备的普及，移动互联网、各种定位技术和位置服务应用的快速发展，使得移动对象的实时地理位置坐标更易被获取。而位置资源数量的飚升促使了对于快捷且准确的进行移动对象行为模式提取的急切需求，同时也给利用机器学习的人群分类方法提供了充足的数据来源。位置数据中含有大量移动对象的时空信息，研究者们难以从海量的位置数据中有效的规整并抽取出移动对象的行为模式。为解决这一难题，首先应对高维的位置数据进行降维操作。现有的降维算法主要有主成分分析法（Principal Component Analysis，PCA）、局部保持投影（Locality PreservingProjection，LPP）等。但这些降维算法都是基于位置数据本身，虽能降低数据维度，但却不能发掘其潜在语义。如上节所述，移动对象所产生的地理位置坐标都具有其隐含的意义——当前对象所处的功能区域。对象在不同的功能区域出现，代表着有不同的移动动机，如在居民区出现，代表着对象回家；在教育区出现，代表着上学或上班。移动对象在不同功能区域出现次数的多少，也从侧面体现了其兴趣爱好、生活习惯。例如，对象 A 的位置集中包含了大量功能特征为餐馆的 GPS坐标，可推断该对象喜欢在外就餐；甚至可进一步分析，得到对象时常光顾的餐厅类别，挖掘移动对象口味。在此认知的基础上，可将高维的位置数据转化为低维的地区功能特征，即位置语义，从而达到降维的目的；并以对象功能特征随时间变化的轨迹为基础，进而抽取出对象行为模式，对于计算对象相似度，进而判断对象类型具有重要意义。
.......
2 国内外研究现状
针对位置数据的高维稀疏特性，首先应对位置数据采用降维技术进行特征抽取，得到高维位置词汇下潜在的位置语义；其次，针对位置数据的时序特性，以位置语义为基础完成对象移动轨迹的规整与行为模式的抽取。最后，将对象的位置语义出现概率作为静态特征，将对象的行为模式作为动态特征，作为聚类属性应用于人群分类。基于以上，本章针对本文即将用到的技术分别阐述它们在国内外的研究现状。
2.1 降维技术研究现状
移动终端设备的普及、移动互联网、各种定位技术和位置服务应用的快速发展，使得人们的实时地理位置坐标更易被获取。但是，面对如此庞大并且数据规模急剧增长的位置数据集，研究者们很难直接对其进行处理与研究。关于降维技术的研究，最早开始于国外，并在数据可视化、特征抽取等领域有很长的应用历史，以 Jolliffe、Lee 等为代表的众多研究学者投入到降维技术的研究中，并取得了一系列很有成效的研究成果。早期的降维技术为主成分分析法（Principal Components Analysis，PCA），它是由英国生物统计学家 Perason 于 1901 年针对非随机变量提出的，后来由 Hotelling[2]于 1933年将其推广到随机变量。该算法的主要思想是通过求解原始矩阵 A 在最小二乘意义上的最佳 k 维近似，以此使用较少的数据维度，同时保留较多的原数据特性。后来基于 PCA 的思想，又引入了不同形式的损失函数和额外的约束映射，如 Sammon’s mapping[3]。至此，PCA 在数据分析领域被广泛使用。随后，在 1936 年，Fisher 等研究者提出了线性判别分析（LinearDiscriminant Analysis，LDA）[4]，也称为 Fisher 线性差别分析（Fisher LinearDiscriminant，FLD）。它是一种有监督的线性降维算法，利用分类信息将高维数据投影到一个最佳的低维线性判别子空间，使得类内聚合度高而且类间的耦合度低，使得降维后的数据尽可能容易地被区分。
.............
2.2 行为模式抽取研究现状
位置数据中均蕴含着丰富的空间信息和时间信息，体现着移动对象在真实世界的活动轨迹，而这些活动轨迹的频繁度通常体现了移动对象的意图、生活习惯和行为模式[18-20]。通过对这些信息的分析与挖掘，可以为移动对象提供多种多样的增值服务和工具[21-22]。如何有效地从位置数据中抽取移动对象行为模式，为对象行为预测，相似对象推荐，定点推送对象感兴趣的活动等都具有重要的意义。近年来，越来越多的研究者们投身于对象行为模式抽取，并取得了丰硕的研究成果。Blumm 等利用 100 万手机用户三个月的话单数据，通过度量每个对象轨迹熵值的方法，证明了对象移动轨迹的规律性和可预测性，为挖掘对象的行为模式奠定了理论基础[23]。从目前的研究现状来看，国外关于行为模式的研究方法主要分为两类：轨迹聚类，序列模式挖掘。研究学者基于轨迹聚类提出了很多优秀的行为模式抽取方法，这些方法利用不同的相似性度量算法对对象移动轨迹进行聚类，取得对象的行为模式。Han J W 等利用划分-聚类的思想提出了 TRACLUS 算法，将对象一次完整的移动轨迹划分为多个子轨迹序列，并使用基于密度的聚类方法将相似子轨迹进行合并，从而获得对象行为的“区域模式”[24]。Agrawal 等提出了对位置数据进行增量式聚类分析的算法框架 TCMM[25]，该框架包含微聚类和再聚类两个阶段，微聚类阶段根据特定的相似度度量方法和相似度阈值对新的轨迹数据和已存在的轨迹簇进行聚类，再聚类阶段对上一阶段产生的微簇进行重新合并聚类，从而得到对象行为模式。
.........
3 基于位置语义和概率的人群分类方法 ......... 16
3.1 引言......... 16
3.2 相关工作 ........ 16
3.3 基于位置语义和概率的人群分类方法 ..... 17
3.3.1 位置语义发现 .... 18
3.3.2 访问概率向量聚类 .... 20
3.4 实验......... 20
3.4.1 实验数据及数据预处理 .......... 20
3.4.2 评价指标 ..... 21
3.4.3 语义数目选择 .... 22
3.4.4 实验结果与分析........ 23
3.5 基于位置语义和概率的相似对象查询 ..... 28
3.5.1 相似对象查询页面 .... 28
3.6 本章小结 ........ 30
4 基于行为模式的人群分类方法 ...... 32
4.1 引言......... 32
4.2 相关工作 ........ 32
4.3 行为模式抽取研究 ....... 33
4.4 实验......... 36
4.4.1 实验设置及评估标准 ....... 36
4.4.2 时间片划分粒度选择 ....... 37
4.4.3 行为模式抽取结果 .... 37
4.4.4 人群分类实验结果 .... 38
4.5 本章小结 ........ 39
4 基于行为模式的人群分类方法
4.1 引言
随着移动设备的发展和定位技术的进步，以及位置服务应用的广泛使用（如社交网络、交通管理和军事侦察等），现已生成大量的位置数据，这些位置数据记录着人们的日常生活[79]，体现着移动对象在真实世界的活动轨迹，而这些活动轨迹体现了移动对象的意图、生活习惯和行为模式。上章从位置语义及其访问概率两方面同时考虑，以对象访问位置语义空间的概率大小作为相似用户的判断标准。但该工作却没有考虑对象访问位置语义空间的先后顺序。因此，本章在满足时间连续性的条件下，将位置语义发现方法得到的位置词汇的位置语义作为基点，构建对象时间序列轨迹，从而提取出对象频繁移动轨迹，即行为模式。将行为模式作为对象在时间维度上的动态特征向量，进行人群分类，从位置语义、时序性、频繁次数三个方面同时考虑，更能体现对象生活模式的相似性。因此，在上节位置语义发现方法的基础上，按照时间先后顺序，抽取移动对象在不同位置语义区域活动产生的轨迹，对于研究者理解移动对象行为动机，梳理对象的生活习惯、行为模式具有重要意义。针对这一实际需求，本章提出了一种基于移动对象行为模式的人群分类方法。首先通过上章提出的位置语义发现方法得到各个位置词汇的隐含位置语义，其次按照时间约束条件将其串联形成位置语义演化轨迹，然后利用最长公共子序列得到频繁移动轨迹，即移动对象行为模式，最后将其作为对象动态特征向量，并采用一系列聚类算法完成人群分类用以验证对象行为模式的正确性。与已有工作相比，本章的主要贡献在于：(1)建立了对象移动轨迹抽取规则(见第 4.3.2 节)，为不同时间段、不同地理位置距离、不同位置语义的坐标点建立合理的轨迹抽取规则；(2)提出了基于最长公共子序列(Longest Common Subsequence, LCS)算法的行为模式抽取方法(见第 4.4.3 节)。对于不同对象、不同长度的移动轨迹，建立了统一的行为模式抽取模型。在位置服务应用所产生的位置数据集上的实验表明，该算法抽取得到的行为模式符合移动对象的真实日常行为；在基于行为模式的人群分类实验中，能得到较好的实验性能(见第 4.5 节)。
..........
结论
随着移动设备、通信技术、GPS 定位技术等技术的迅速发展，移动对象使用位置应用服务产生的位置数据呈指数型增长，对研究者的处理和分析造成了巨大的障碍。位置数据的高维稀疏特性，使降维技术成为解决该问题的前提与基础。大量的位置数据中蕴含着丰富的时间、空间信息，通过研究移动对象随时间的空间变化规律，发现移动对象的行为模式，对于对象行为预测、个性化服务推荐等具有重要意义。因此，本文从两个方面解决了现有移动对象行为模式抽取的问题：高维稀疏性以及时序性。在本文的研究中，主要的创新性成果与贡献包括：
(1)针对位置数据的高维稀疏性，提出了一种基于位置语义的降维方法。该方法针对位置词汇隐含地区功能特征的特殊性，发掘位置词汇的位置语义，将高维位置数据映射到位置语义维度上，在位置语义空间下进行后续分析，有效降低了操作的数据维度。同时由于位置词汇的全球通用性，因此该方法具有一定的通用性和普适性；
(2)根据位置语义发现方法得到的位置语义空间，提出了一种基于位置语义和概率的人群分类方法。将对象在位置语义空间上的访问概率向量作为对象静态特征向量，并分别以划分聚类 K-means，凝聚聚类，层次聚类 HC，密度聚类 DBSCAN 为聚类方法，得到人群分类结果。实验表明以移动对象对位置语义的访问概率作为对象特征，可有效的进行人群分类；
(3)在位置语义发现与人群分类研究的前提下，以《移动终端定位系统》为平台，设计并实现了相似移动对象查询功能，表明本文研究具有一定的实际意义与应用价值；
(4)在位置语义挖掘基础上，根据位置词汇产生的时序性，建立了移动对象的位置语义演化轨迹抽取规则，为不同时间段、不同地理位置距离、不同位置语义的坐标点建立合理的轨迹抽取规则；
(5)提出了基于最长公共子序列(Longest Common Subsequence, LCS)算法的行为模式抽取方法。对于不同时间段、不同长度的移动轨迹，建立了统一的行为模式抽取方法。在位置服务应用所产生的位置数据集上的实验表明，该算法抽取得到的行为模式符合移动对象的真实日常行为；
(6)以移动对象的行为模式作为对象的动态特征向量，在动态时间规整（Dynamic Time Warping，DTW）算法基础上建立了行为模式相似度计算机制，在行为模式轨迹长度不一致的情况下，计算移动对象间的最大相似度，以此作为人群分类依据。实验结果表明以行为模式作为对象动态特征，较以对位置语义的访问概率作为的静态特征，F-measure 值更优。
..........
参考文献（略）