基于中国观鸟数据的移动对象周期模式发现

移动对象的轨迹数据中包含大量时空信息,挖掘时空信息背后隐藏的周期模式对掌握移动对象变化规律具有重要作用。为此,提出一种三阶段移动对象周期模式检测算法,通过研究轨迹点的时空特征识别并剔除重复数据,利用密度聚类算法发现轨迹点密集区域并找出密集区域中每一类移动对象的周期模式,解决移动对象轨迹周期模式挖掘中轨迹数据重复、采样数据不连续及潜在周期模式发现问题。基于2003年—2015年中国观鸟记录中心、中国观鸟年报等公开数据的实验结果表明,该算法可有效处理轨迹数据并准确挖掘出规律性移动对象的周期模式。     

多模式移动对象不确定性轨迹预测模型

以移动设备、车辆、飞机、飓风等移动对象不确定性轨迹预测问题为背景,将大规模移动对象数据作为研究对象,以频繁轨迹模式挖掘、高斯混合回归技术为主要研究手段,提出多模式移动对象轨迹预测模型,关键技术包括:1）针对单一运动模式,提出一种基于频繁轨迹模式树FTP-tree的轨迹预测方法,利用基于密度的热点区域挖掘算法将轨迹点划分成不同的聚簇,构建轨迹频繁模式树,挖掘频繁轨迹模式预测移动对象连续运动位置.不同数据集上实验结果表明基于FTP-tree的轨迹预测算法在保证时间效率的前提下预测准确性明显优于已有预测算法.2）针对复杂多模式运动行为,利用高斯混合回归方法建模,计算不同运动模式的概率分布,将轨迹数据划分为不同分量,利用高斯过程回归预测移动对象最可能运动轨迹.实验证明,相比于基于隐马尔科夫模型和卡尔曼滤波的预测方法,所提方法具有较高的预测准确性和较低的时间代价.     

时空轨迹序列模式挖掘方法综述

在全球定位、移动通信技术迅速发展的背景下涌现出了海量的时空轨迹数据,这些数据是对移动对象在时空环境下的移动模式和行为特征的真实写照,蕴含了丰富的信息,这些信息对于城市规划、交通管理、服务推荐、位置预测等领域具有重要的应用价值,而时空轨迹数据在这些领域的应用通常需要通过对时空轨迹数据进行序列模式挖掘才能得以实现。时空轨迹序列模式挖掘旨在从时空轨迹数据集中找出频繁出现的序列模式,例如： 位置模式（频繁轨迹、热点区域）、活动周期模式、语义行为模式,从而挖掘时空数据中隐藏的信息。总结近年来时空轨迹序列模式挖掘的研究进展,先介绍时空轨迹序列的数据特点及应用,再描述时空轨迹模式的挖掘过程：从基于时空轨迹序列来挖掘位置模式、周期模式、语义模式这三个方面来介绍该领域的研究情况,最后阐述现有时空轨迹序列模式挖掘方法存在的问题,并展望时空轨迹序列模式挖掘方法未来的发展趋势。     

基于后缀自动机的轨迹模式挖掘方法*

如何有效的从轨迹数据中挖掘轨迹模式和规律具有重要意义,本文基于交通路网研究移动对象轨迹预测,将序列分析方法和马尔科夫统计模型结合,提出了一种基于后缀自动机的变阶马尔科夫模型挖掘方法。该方法根据移动对象的历史轨迹数据进行学习训练,计算轨迹序列上下文的概率特征,建立序列的后缀自动机模型,结合当前实际轨迹数据,动态自适应预测将来的位置信息。实验结果表明：相比固定阶马尔科夫模型,随着阶数的增加（L>=2）,固定阶马尔科夫模型预测的精度逐步降低,而该方法能动态自适应,精度保持在81.3%左右,取得较好的预测效果;同时,该方法只需线性的时间和空间开销,大大降低了存储空间和时间,能实现大规模数据的在线学习。     

基于深度表示模型的移动模式挖掘

针对时空轨迹中位置顺序和时间对于理解用户移动模式的重要性,提出了一种新的用户轨迹深度表示模型。该模型考虑到时空轨迹的特点:1)不同的位置顺序表示不同的移动模式;2)轨迹有周期性并且在不同的时间段有变化。首先,将两个连续的位置点组合成位置序列;然后,将位置序列和对应的时间块组合成时间位置序列,作为描述轨迹特征的基本单位;最后,利用深度表示模型为每个序列训练特征向量。为了验证深度表示模型的有效性,设计实验将时间位置序列向量应用到用户移动模式发现中,并利用Gowalla签到数据集进行了实验评测。实验结果显示提出的模型能够发现"上班""购物"等明确的模式,而Word2Vec很难发现有意义的移动模式。     

基于前缀投影技术的大规模轨迹预测模型

智能手机、车载GPS终端、可穿戴设备产生了海量的轨迹数据,这些数据不仅描述了移动对象的历史轨迹,而且精确地反映出移动对象的运动特点.已有轨迹预测方法的不足在于：不能同时兼具预测的准确性和时效性,有效的轨迹预测受限于路网等局部空间范围,无法处理复杂、大规模位置数据.为了解决上述问题,针对海量移动对象轨迹数据,结合频繁序列模式发现的思想,提出了基于前缀投影技术的轨迹预测模型PPTP（prefix projection based trajectory prediction model）,包含两个关键步骤：（1）挖掘频繁轨迹模式,构造投影数据库并递归挖掘频繁前序轨迹模式;（2）轨迹匹配,以不同频繁序列模式作为前缀增量式扩展生成频繁后序轨迹,将大于最小支持度阈值的最长连续轨迹作为结果输出.算法的优势在于：可以通过较短的频繁序列模式,增量式生成长轨迹模式;不会产生无用的候选轨迹,弥补频繁模式挖掘计算代价较高的不足.利用真实大规模轨迹数据进行多角度实验,表明PPTP轨迹预测算法具有较高的预测准确性,相对于1阶马尔可夫链预测算法,其平均预测准确率可以提升39.8%.基于所提出的轨迹预测模型,开发了一个通用的轨迹预测系统,能够可视化输出完整的轨迹路线,为用户路径规划提供辅助决策支持.     

基于多源位置数据的居民出行频繁模式挖掘

随着城市化进程的不断深入,居民出行频繁模式挖掘成为一个研究热点.然而,现有的研究存在一些问题,如缺乏对频繁模式发生的目的和意义的描述,以及对挖掘结果分析不全面等.针对这些问题,文中提出了一种新颖的居民出行频繁模式挖掘方法(Mining Method of Residents'Frequent Travel Patterns,MMoRFTP).首先,采用形态学图像方式将地图划分为多个区域,利用融合后的多源位置数据来构建出行模式,并采用主题模型识别每个区域的功能;然后,将缺乏语义信息的出行轨迹转化为具有区域和功能区语义的出行轨迹,并以区域为节点、语义轨迹为边构建居民出行模式图和标签模式图,在图模型构建的基础上提出MulEdge算法来挖掘区域之间由居民出行所形成的频繁关联模式.文中以城市路网数据、POI数据、出租车GPS数据和签到数据作为对象进行实验,结果表明MMoRFTP方法具有良好的性能,其发现的出行频繁模式能为道路规划、交通管理、商业布局等应用提供决策依据.     

基于Adaboost-Markov模型的移动用户位置预测方法

针对Markov模型在位置预测中存在预测精度不高及匹配稀疏等问题,提出了一种基于Adaboost-Markov模型的移动用户位置预测方法。首先,通过基于转角偏移度与距离偏移量的轨迹划分方法对原始轨迹数据进行预处理,提取出特征点,并采用密度聚类算法将特征点聚类为用户的各个兴趣区域,把原始轨迹数据离散化为由兴趣区域组成的轨迹序列;然后,根据前缀轨迹序列与历史轨迹序列模式树的匹配程度来自适应地确定模型阶数k;最后,采用Adaboost算法根据1~k阶Markov模型的重要程度为其赋予相应的权重系数,组成多阶融合Markov模型,从而实现对移动用户未来兴趣区域的预测。在大规模真实用户轨迹数据集上的实验结果表明,与1阶Markov模型、2阶Markov模型、权重系数平均的多阶融合Markov模型相比,Adaboost-Markov模型的平均预测准确率分别提高了20.83%、11.3%以及5.38%,且具有良好的普适性与多步预测性能。     

基于轨迹和兴趣点数据的城市功能区动态识别与时变规律可视分析

目前,多数城市功能区识别方法仅依据路网和土地利用类型进行功能区的划分与识别,无法反映功能区范围及功能性随人类活动的动态变化.为此,提出基于轨迹数据挖掘与兴趣点语义分析的城市功能区识别与时空特征分析方法.通过考虑车辆行驶状况与区域功能的相关性,对特征轨迹点进行自适应密度聚类,并基于聚类中心利用Voronoi图合理划分功能区范围.为了有效地评价区域的复合功能性,利用潜在狄利克雷分布(latent Dirichlet allocation,LDA)模型对区域内兴趣点的类别信息挖掘主题词并计算相应的概率,在此基础上提出功能性强弱量化计算方法.基于轨迹数据的时变特性,构建交互式可视分析系统UFAVIS(urban functional areas visualization),进一步发掘人类活动对功能区时空模式的影响.利用结合时空特征分析的功能区识别方法对北京市真实数据进行了实验验证和具体案例分析,结果表明,UFAVIS能够准确识别区域的复合功能性,并发现功能区随人类活动的时空变化规律,为城市规划和政策制定提供依据.     

基于空间邻近搜索的移动轨迹相对时间模式挖掘方法

针对传统移动轨迹模式挖掘方法挖掘速度慢、占用最大内存大的问题,提出一种基于空间邻近搜索的移动轨迹相对时间模式挖掘方法。该方法包括5个阶段：1）对移动轨迹数据进行时空划分,并基于移动轨迹数据与时空格的匹配得到移动轨迹数据对应的时空格序列。2）扫描所有的时空格序列数据得到空间网格集合,并通过空间网格与时空格序列的包含运算得到所有的频繁空间网格。3）频繁空间网格转变为长度为1的频繁相对时间模式。4）基于空间邻近搜索的方式进行模式增长,得到以频繁空间网格为单元的候选相对时间模式,并通过相对时间模式与时空格序列的匹配运算,计算相对时间模式的支持度。5）基于设定的支持度阈值,得到所有频繁的相对时间模式。实验结果表明：所提方法由于采用了基于空间邻近搜索的方式进行模式扩展,大幅减小候选相对时间模式的搜索范围。与传统方法相比,所提方法具有挖掘速度快、占用最大内存少的优点。另外,方法在运行时间上具有更好的稳定性和可扩展性,而在占用最大内存上的稳定性与可扩展性与传统方法基本相近。该方法有助于移动轨迹模式挖掘方法提升挖掘速度、减少占用最大内存。     

Sequential Pattern Mining in Multi-Databases via Multiple Alignment

To efficiently find global patterns from a multi-database, information in each local database must first be mined and summarized at the local level. Then only the summarized information is forwarded to the global mining process. However, conventional sequential pattern mining methods based on support cannot summarize the local information and is ineffective for global pattern mining from multiple data sources. In this paper, we present an alternative local mining approach for finding sequential patterns in the local databases of a multi-database. We propose the theme of approximate sequential pattern mining roughly defined as identifying patterns approximately shared by many sequences. Approximate sequential patterns can effectively summerize and represent the local databases by identifying the underlying trends in the data. We present a novel algorithm, ApproxMAP, to mine approximate sequential patterns, called consensus patterns, from large sequence databases in two steps. First, sequences are clustered by similarity. Then, consensus patterns are mined directly from each cluster through multiple alignment. We conduct an extensive and systematic performance study over synthetic and real data. The results demonstrate that ApproxMAP is effective and scalable in mining large sequences databases with long patterns. Hence, ApproxMAP can efficiently summarize a local database and reduce the cost for global mining. Furthremore, we present an elegant and uniform model to identify both high vote sequential patterns and exceptional sequential patterns from the collection of these consensus patterns from each local databases.     

基于OPTICS聚类和关联分析的轨迹伴随模式分析

目前,主流的轨迹伴随模式挖掘方法大多是对连续短时间内轨迹的一次挖掘,忽略了前后非连续时间上的关联分析,因此对隐含伴随模式的挖掘不准确。本文对轨迹伴随模式进行了分析,并提出一种结合密度聚类和关联分析的伴随模式分析方法。该方法首先挖掘轨迹数据中的局部模式簇,通过非连续时间片局部模式簇的关联分析,优化挖掘结果。实验结果表明本文方法可以有效地挖掘轨迹中的伴随模式。     

移动对象轨迹时空相似性度量方法

在分析移动对象行为时,移动对象轨迹因包含大量的信息而具有重要的作用。在实际应用中移动对象常受限于空间网络而无法利用现有欧氏空间中轨迹及其距离处理技术。分析了道路网络空间轨迹相似性性质,提出一种移动对象轨迹建模的时空表示方法,能有效地将轨迹从道路网络空间转化到欧氏空间;同时提出了一种基于兴趣点POI（Points Of Interesting）距离的轨迹间相似性测量方法,有效地对轨迹进行化简并减少轨迹中节点的数目,从而降低算法时间复杂度。该方法不仅可以用于搜索相似轨迹,还可方便地应用到轨迹聚类的相关工作中。     

不确定性车辆路口的轨迹预测

在城市道路中,实时、准确、可靠地对移动车辆进行轨迹预测具有极高的应用价值,不仅可以提供准确的基于位置的服务,而且可以帮助过往车辆预知前方的交通状况。目前,移动车辆的轨迹预测方法主要基于历史轨迹的欧氏空间进行,并未考虑在受限路网中采用不确定性历史数据的车辆轨迹预测。针对这一问题,提出一种补全路径的基于马尔科夫链的轨迹预测方法,其优势在于:重新定义了补全路径算法,弥补了不确定性历史数据的不完整性,利用马尔科夫链低时间复杂度、高预测准确度的优势实现预测,避免了因频繁模式挖掘带来的查询时间过长而影响预测效率以及存在多余噪声影响轨迹预测准确率的问题。通过真实数据和实验分析表明:在参数设置相同的情况下,该方法比挖掘频繁轨迹模式算法的预测准确率平均提高了18.8%,预测时间平均缩减了80.4%。因此,该方法对于车辆路口的轨迹预测具有较高的预测准确率,并且能预测一系列的车辆未来轨迹。     

Spatiotemporal feature mining algorithm based on multiple minimum supports of pattern growth in Internet of Things

The temporal and spatial characteristics of users are involved in most Internet of Things (IoT) applications. The spatial and temporal movement patterns of users are the most direct manifestation of the temporal and spatial characteristics. The user’s interests, activities, experience and other characteristics are reflected by mobile mode. In view of the low clustering efficiency of moving objects in convergent pattern mining in the IoT, a spatiotemporal feature mining algorithm based on multiple minimum supports of pattern growth is proposed. Based on the temporal characteristics of user trajectories, frequent and asynchronous periodic spatiotemporal movement patterns are mined. Firstly, the location sequence is modeled, and the time information is added to the model. Then, a mining algorithm of asynchronous periodic sequential pattern is adopted. The algorithm is based on multiple minimum supports of pattern growth. According to multiple minimum supports, the sequential pattern of asynchronous period is mined deeply and recursively. Finally, the proposed method is validated and evaluated by Gowalla dataset, in which the user characteristics are truly reflected. It is shown by the experimental results that the average pointwise mutual information (PWI) of the proposed algorithm reaches 0.93. And the algorithm is proved to be effective and accurate.

     

基于多尺度的时序数据部分周期模式增量挖掘

针对动态时序数据部分周期模式挖掘过程存在的计算复杂度过高和扩展性差等问题,提出了一种结合多尺度理论的时间序列部分周期模式挖掘算法（MSI-PPPGrowth）,所提算法充分利用了时序数据客观存在的时间多尺度特性,将多尺度理论引入时序数据的部分周期模式挖掘过程。首先,将尺度划分后的原始数据以及增量时序数据作为更细粒度的基准尺度数据集进行独立挖掘;然后,利用不同尺度数据间的相关性实现尺度转换,以间接获取动态更新后的数据集对应的全局频繁模式,从而避免了原始数据集的重复扫描和树结构的不断调整。其中,基于克里金法并考虑时序周期性设计了一个新的频繁缺失计数估计模型（PJK-EstimateCount）,以有效估计在尺度转换过程中的缺失项支持度计数。实验结果表明,MSI-PPPGrowth具有良好的可扩展性和实时性,尤其是对于稠密数据集,其性能优势更为突出。     

An individual-based spatio-temporal travel demand mining method and its application in improving rebalancing for free-floating bike-sharing system

After the rapid expansion in the early stage, many enterprises have closed down or withdrawn from the Free-floating bike sharing (FFBS) market, the remaining few giants are also generally at a loss at present. One main reason causing these is the serious FFBS imbalance between supply and demand. As there is no fixed docking station, the individual-based identification method such as trip-chain, which is used for identifying travel demand and behaviour in traditional station-based bike sharing (SBBS) cannot be used in FFBS. Therefore, the lack of methods to obtain in-depth demand makes it unable to achieve reasonable rebalancing. This study constructs an individual-based spatio-temporal travel demand mining methodology, which is the first disaggregate travel demand mining model that suitable for FFBS. The proposed methodology consists of three steps. A spatio-temporal trajectory clustering algorithm is first developed to obtain an individual’s frequent trajectory clusters, and then a sequential pattern mining algorithm is applied to users who have multiple spatio-temporal trajectory clusters to extract travel patterns and trajectory sequential relations in patterns. A point clustering method is used finally to identify spatial relationships among different trajectory clusters. Besides, a zone aggregating method is proposed that aggregated granularity could be flexible adjusted for zone demand imbalance analysis. Based on these, how to utilize identified frequent pattern trajectories to improve rebalancing is studied. The proposed methodology is applied to Beijing Mobike dataset, six frequent travel patterns are mined out and analyzed in detail. On this basis, imbalance and rebalancing analysis are carried out with the case study at last. Consequently, this research contributes a powerful tool to achieve accurate FFBS demand analysis and rebalancing.     

基于浮动网格的路段检索方法

地图匹配是将车辆原始的GPS轨迹数据映射到实际道路网络上的过程, 其中为GPS轨迹点检索候选路段是地图匹配的首要环节, 然而不同的候选路段检索方式会直接影响地图匹配的准确性和效率. 本文针对城市路网环境下的低频采样GPS轨迹数据, 提出了一种基于浮动网格的路段检索方法. 该方法利用GeoHash网格编码, 采用浮动GeoHash网格的方式, 为轨迹点检索候选路段. 其次为了验证方法的可行性, 本文通过隐马尔可夫模型, 结合道路网络的拓扑结构以及轨迹的时空约束条件, 采用增量的方式, 利用维特比算法计算得到局部最优解. 最后使用贪心策略, 从已经得到的局部最优解中依次延伸得到全局最佳匹配路径.