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

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

时空轨迹大数据分布式蜂群模式挖掘算法

针对时空轨迹大数据的蜂群模式挖掘需求,提出了一种高效的基于MapReduce的分布式蜂群模式挖掘算法。首先,提出了基于最大移动目标集的对象集闭合蜂群模式概念,并利用最小时间支集优化了串行挖掘算法;其次,提出了蜂群模式的并行化挖掘模型,利用蜂群模式时间域无关性,并行化了聚类与子时间域上的蜂群模式挖掘过程;第三,设计了一个基于MapReduce链式架构的分布式并行挖掘算法,通过四个阶段快速地实现了蜂群模式的并行挖掘;最后,在Hadoop平台上,使用真实交通轨迹大数据集对分布式算法的有效性和高效性进行了验证与分析。     

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

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

基于时空轨迹的移动对象汇聚模式挖掘算法

移动对象的聚集模式是时空轨迹模式挖掘中的重要课题,它研究移动对象群体在多个连续时刻中的空间聚集问题。现有的聚集模式基于共现模式进行定义,挖掘结果中夹杂大量非运动的聚集群体,严重影响模式挖掘的效果。为了解决此问题,本文提出了基于群体运动过程建模的汇聚模式。该模式定义从群体运动形态出发进行设计,准确识别向心运动的移动群体,有效排除非聚集类型运动群体的干扰。本文设计并实现了汇聚模式挖掘（Converging pattern mining,CPM）算法,该算法首先定位密度峰值点,确定候选的汇聚中心区域,然后依次识别每个时刻的汇聚群体,按照群体汇聚的持续性要求识别汇聚模式。基于真实轨迹数据进行实验,结果验证了本文提出的CPM算法在挖掘效果和算法效率的有效性。     

基于时空模式的轨迹数据聚类算法

针对轨迹聚类算法在相似性度量中多以空间特征为度量标准,缺少对时间特征的度量,提出了一种基于时空模式的轨迹数据聚类算法。该算法以划分再聚类框架为基础,首先利用曲线边缘检测方法提取轨迹特征点;然后根据轨迹特征点对轨迹进行子轨迹段划分;最后根据子轨迹段间时空相似性,采用基于密度的聚类算法进行聚类。实验结果表明,使用所提算法提取的轨迹特征点在保证特征点具有较好简约性的前提下较为准确地描述了轨迹结构,同时基于时空特征的相似性度量因同时兼顾了轨迹的空间与时间特征,得到了更好的聚类结果。     

基于二级时空分桶的伴随轨迹查询

随着移动传感器设备的普及,人们能够采集到的位置数据越来越多,轨迹数据的规模也越来越庞大.从大规模时空数据中查找与指定轨迹最相似的前k条轨迹一直是时空大数据挖掘的重要挑战之一.现有的相似轨迹查询方法大都包括三个阶段:(1)对海量的离线轨迹数据建立索引;(2)基于索引结构从已知轨迹集中查询与指定轨迹相似的候选轨迹;(3)计算指定轨迹与候选轨迹之间的精确相似度并返回相似度最大的前k条轨迹.但大多数现有方法对轨迹进行聚类索引时不能有效利用时间和空间信息,导致时间相似度不高的轨迹也会被划分到相同的索引项上,最终影响查询的准确性和效率.此外,现有的时空轨迹相似度计算方法存在大量的无效运算,使得相似轨迹的查询效率整体较低.针对当前伴随轨迹查询方法对时间与空间信息利用不充分的问题,本文提出一种新的二级时空分桶索引结构,首先将每条轨迹数据按照时间滑动窗口划分为若干带有时间槽信息的子轨迹,在时间上对轨迹进行一级索引聚类;在此基础上对在相同时间槽内的子轨迹进行二级空间索引聚类,利用哈希算法将具有连续相同位置点的子轨迹映射到同一时空分桶中.与已有索引方法相比,该方法对不同轨迹在索引时具有更好的区分度,查询时的...     

基于移动对象轨迹段分割的聚类算法研究

将对象的运动轨迹作为一个整体聚类,将丢失相似子轨迹段有用的信息.为了找出相似子轨迹段,提出针对某一个轨迹进行子轨迹的聚类算法,先把长轨迹在特征点分割为一组直子段,再用基于密度的聚类算法对子段进行聚类,得到子段的可达距离排序并生成可达性图,最后根据生成的可达性图识别聚类结构.实验结果表明该方法能有效准确地识别相似子轨迹段.     

面向位置预测的动态轨迹模式挖掘

针对海量的用户轨迹数据进行研究,提出一种动态分析移动对象轨迹模式、预测轨迹位置的方法（PRED）。首先使用改进的模式挖掘模型,提取轨迹频繁模式（简称T-模式）,然后提出DPTUpdate算法,设计蕴含时空信息的快捷数据结构--DPT（Dynamic Pattern Tree）,存储和查询移动物体的T-模式,并提出Prediction算法计算最佳匹配度,得到移动对象轨迹的预测位置。PRED方法可提供动态分析的能力,基于真实数据集进行对比实验,结果证明,平均准确率达到72%,平均覆盖率达到92.1%,与已有方法相比,其预测效果有显著提升。     

HMM-Cluster：面向交通量过载发现的轨迹聚类方法

随着经济的发展,城市交通拥堵问题亟待解决,交通量过载发现是解决交通拥堵问题的有效方法之一。提出一种基于HMM模型的轨迹聚类算法HMM-Cluster,可有效地发现交通量过载情况。该算法首先提取时空轨迹特征点,并采用维数约简技术减少轨迹数据量,根据参照轨迹拟合HMM模型,基于密度函数得到轨迹相似度矩阵,最后给出聚合的相似性轨迹。真实轨迹数据集上的对比实验结果表明,提出的HMM-Cluster可有效地挖掘移动对象运动模式,准确发现交通量过载情况,具有一定实用价值。     

手机信令的时空密度轨迹点识别算法

手机信令具有时空序列性以及数据量大、采样频率不均、定位精度低与基站振荡等特点,导致传统手机信令聚类方法数据密度分布不均、时空开销大且聚类效果差。提出一种用于手机信令的时空密度轨迹点识别算法。将手机信令数据网格化以统一评估尺度,根据振荡噪声特征对网格簇进行时空联结减少空间不确定性和计算量,结合网络轨迹的曲折性以及移动与停留时间重新定义网格簇内轨迹点时空移动能力,计算网格簇的时空密度以判断用户停留区域,并采集具有移动停留标签的轨迹数据以验证算法有效性和识别效率。实验结果表明,该算法识别精度较改进DBSCAN算法更高,适用于识别手机信令数据停留区域,对复杂轨迹停留区域的识别效果更好。     

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

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

DMFUCP:大规模轨迹数据通用伴随模式分布式挖掘框架

广泛应用的移动定位设备方便了用户位置数据的获取,轨迹数据量高速增长.通用伴随模式挖掘聚焦时空维度上的用户高相似度行为路径发现问题,基于大规模轨迹数据设计高效准确地伴随模式挖掘方法对发现用户偏好、构建新商业模式等具有重要意义,同时也极具挑战.一方面,海量且不断增长的轨迹数据要求伴随模式挖掘应具有良好的可扩展性,集中性挖掘策略并不适用.另一方面,现有的分布式挖掘框架在为高效模式挖掘提供高质量数据输入、轨迹数据中大量松散连接的有效处理等方面考虑不足,使得通用伴随模式发现存在改进空间.提出了一个分布式的2阶段通用伴随模式挖掘框架——DMFUCP,其通过嵌入数据预处理优化、松散连接分析优化等,让伴随模式挖掘方法呈现了更好的性能.其中,该框架为数据预处理阶段设了融合运动方向的密度聚类算法DBSCANCD和聚类平衡算法TCB,确保后续挖掘任务获得提供少噪音、高质量的轨迹数据输入;在模式挖掘阶段,该框架设计了G剪枝重划分算法GSPR和分段枚举算法SAE,GSPR使用参数G对长轨迹进行分割,并将分割后的所有分段重划分以改善松散连接的处理效果,SAE负责引入多线程和前向闭包保证挖掘算法的性能.实验证明,相比现有的通用伴随模式挖掘框架,DMFUCP具有更好的通用伴随模式发现能力的同时,将挖掘每组通用伴随模式的时间消耗降低了20%~40%.     

基于自适应分段粒度的时空模式挖掘方法*

针对轨迹数据采集手段日趋多样化,导致时空模式挖掘的预处理环节难以采用单一、固定的分段粒度来聚类挖掘的问题,提出了一种基于“极大稳定分段阈值”的时空模式挖掘方法。算法在预处理环节自适应调整多个分段阈值对轨迹进行分段,在模式挖掘阶段利用时空模式的空间连通特性来提升挖掘效率,并解决了多阈值分段导致的序列模式支持度重复计数问题。实验表明该方法提升了挖掘过程的鲁棒性,简化了参数调节过程,具有较强的实用性。     

一种高效的移动对象伴随模式挖掘算法

从时空维度中寻找轨迹相似、时间相近的对象集合,即挖掘移动对象的伴随模式,在基于地理位置的用户行为分析中被广泛使用.然而现有移动对象相似性挖掘算法难以处理时间连续、空间离散、时空相关并且数据量大的时空数据.针对此类数据,设计基于滑动窗口、Apriori性质和贪心选择策略的宽度优先搜索算法,对移动对象伴随模式挖掘问题进行求解.同时结合基于哈希的迭代剪枝算法和基于摘要信息的剪枝算法,设计两层剪枝算法以去除冗余的中间结果.在真实数据上的实验结果表明,与仅使用哈希迭代或摘要信息的剪枝算法相比,该算法的剪枝效率较高,并且能够稳定去除99%以上的冗余数据.     

A Framework for Mining Sequential Patterns from Spatio-Temporal Event Data Sets

Given a large spatio-temporal database of events, where each event consists of the fields event ID, time, location, and event type, mining spatio-temporal sequential patterns identifies significant event-type sequences. Such spatio-temporal sequential patterns are crucial to the investigation of spatial and temporal evolutions of phenomena in many application domains. Recent research literature has explored the sequential patterns on transaction data and trajectory analysis on moving objects. However, these methods cannot be directly applied to mining sequential patterns from a large number of spatio-temporal events. Two major research challenges still remain: 1) the definition of significance measures for spatio-temporal sequential patterns to avoid spurious ones and 2) the algorithmic design under the significance measures, which may not guarantee the downward closure property. In this paper, we propose a sequence index as the significance measure for spatio-temporal sequential patterns, which is meaningful due to its interpretability using spatial statistics. We propose a novel algorithm called Slicing-STS-miner to tackle the algorithmic design challenge using the spatial sequence index, which does not preserve the downward closure property. We compare the proposed algorithm with a simple algorithm called STS-miner that utilizes the weak monotone property of the sequence index. Performance evaluations using both synthetic and real-world data sets show that the slicing-STS-miner is an order of magnitude faster than STS-Miner for large data sets.     

基于大数据分析的移动对象轨迹预测方法

对移动对象的轨迹预测将在移动目标跟踪识别中具有较好的应用价值。移动对象轨迹预测的基础是移动目标运动参量的采集和估计,移动目标的运动参量信息特征规模较大,传统的单分量时间序列分析方法难以实现准确的参量估计和轨迹预测。提出一种基于大数据多传感信息融合跟踪的移动对象轨迹预测算法。首先进行移动目标对象进行轨迹跟踪的控制对象描述和约束参量分析,对轨迹预测的大规模运动参量信息进行信息融合和自正整定性控制,通过大数据分析方法实现对移动对象运动参量的准确估计和检测,由此指导移动对象轨迹的准确预测,提高预测精度。仿真结果表明,采用该算法进行移动对象的运动参量估计和轨迹预测的精度较高,自适应性能较强,稳健性较好,相关的指标性能优于传统方法。     

面向卫星在轨实时处理的遥感视频动目标提取算法

针对现有动目标检测算法应用于卫星视频存在较多伪运动误检且难以在轨实时运行,同时短程跟踪算法难以寻回丢失目标的问题,提出一种卫星在轨实时提取运动目标算法。面向运动区域设计图像分类算法以优化运动检测结果,准确筛选动目标;用短程跟踪代替逐帧检测,以降低整体算法复杂度,并设计多特征融合与时空约束的重识别机制关联短程轨迹,应对跟踪丢失;设计在轨智能实时处理系统。使用真实卫星视频数据在嵌入式仿真平台上实验,结果表明,该算法的准确性和实时性相比现有方法有明显提升。     

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

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