An Algorithm for Mining Gradual Moving Object Clusters Pattern From Trajectory Streams

The discovery of gradual moving object clusters pattern from trajectory streams allows characterizing movement behavior in real time environment,which leverages new applications and services.Since the trajectory streams is rapidly evolving,continuously created and cannot be stored indefinitely in memory,the existing approaches designed on static trajectory datasets are not suitable for discovering gradual moving object clusters pattern from trajectory streams.This paper proposes a novel algorithm of gradual moving object clusters pattern discovery from trajectory streams using sliding window models.By processing the trajectory data in current window,the mining algorithm can capture the trend and evolution of moving object clusters pattern.Firstly,the density peaks clustering algorithm is exploited to identify clusters of different snapshots.The stable relationship between relatively few moving objects is used to improve the clustering efficiency.Then,by intersecting clusters from different snapshots,the gradual moving object clusters pattern is updated.The relationship of clusters between adjacent snapshots and the gradual property are utilized to accelerate updating process.Finally,experiment results on two real datasets demonstrate that our algorithm is effective and efficient.

Frequent Trajectory Patterns Mining for Intelligent Visual Surveillance System

A frequent trajectory patterns mining algorithm is proposed to learn the object activities and classify the trajectories in intelligent visual surveillance system.The distribution patterns of the trajectories were generated by an Apriori based frequent patterns mining algorithm and the trajectories were classified by the frequent trajectory patterns generated.In addition,a fuzzy c-means(FCM)based learning algorithm and a mean shift based clustering procedure were used to construct the representation of trajectories.The algorithm can be further used to describe activities and identify anomalies.The experiments on two real scenes show that the algorithm is effective.

CLEAN:Frequent Pattern-Based Trajectory Compression and Computation on Road Networks

The volume of trajectory data has become tremendously huge in recent years. How to effectively and efficiently maintain and compute such trajectory data has become a challenging task. In this paper, we propose a trajectory spatial and temporal compression framework, namely CLEAN. The key of spatial compression is to mine meaningful trajectory frequent patterns on road network. By treating the mined patterns as dictionary items, the long trajectories have the chance to be encoded by shorter paths, thus leading to smaller space cost. And an error-bounded temporal compression is carefully designed on top of the identified spatial patterns for much low space cost. Meanwhile, the patterns are also utilized to improve the performance of two trajectory applications, range query and clustering, without decompression overhead. Extensive experiments on real trajectory datasets validate that CLEAN significantly outperforms existing state-of-art approaches in terms of spatial-temporal compression and trajectory applications.

基于大数据的船舶活动轨迹规律挖掘方法

针对当前船舶轨迹聚类技术存在特征属性研究单一的问题,提出一种基于融合距离的多维度船舶轨迹聚类算法技术,该技术通过加入多个属性特征并采用新的距离度量算法,从时序性和复杂度两方面提出了新的解决思路。在聚类结果基础上,针对缺少轨迹规律特征刻画方法的问题,提出基于局部区域均值的典型轨迹算法技术,通过对各属性进行均值计算,实现同类轨迹集合中轨迹特征的具体描绘。

A parallel algorithm for detecting traffic patterns using stay point features and moving features

In order to detect the traffic pattern of moving objects in the city more accurately and quickly, a parallel algorithm for detecting traffic patterns using stay points and moving features is proposed. First, the features of the stay points in different traffic patterns are extracted, that is, the stay points of various traffic patterns are identified, respectively, and the clustering algorithm is used to mine the unique features of the stop points to different traffic patterns. Then, the moving features in different traffic patterns are extracted from a trajectory of a moving object, including the maximum speed, the average speed, and the stopping rate. A classifier is constructed to predict the traffic pattern of the trajectory using the stay points and moving features. Finally, a parallel algorithm based on Spark is proposed to detect traffic patterns. Experimental results show that the stay points and moving features can reflect the difference between different traffic modes to a greater extent, and the detection accuracy is higher than those of other methods. In addition, the parallel algorithm can increase the speed of identifying traffic patterns.

面向安防系统的高效用语义轨迹模式挖掘

在安防系统中,将大量目标轨迹先转化为语义轨迹后再进行频繁模式挖掘,有助于分析目标行为模式、识别危险源及增强安防系统内部防控。针对现有频繁模式挖掘方法未考虑目标停留点的效用差异问题,提出一种高效用语义轨迹模式挖掘算法。综合停留点兴趣度、目标停留时间以及目标语义轨迹支持度这3个参数定义语义轨迹效用值,采用蚁群算法挖掘高效用语义轨迹模式。利用精英蚂蚁策略改进蚂蚁种群的迭代方式,通过轮盘赌选择法优化蚂蚁对于下一个节点的选择策略,运用无效用编码向量剪枝策略提高算法执行效率。在Chess、Mushroom、Foodmart、Retail等4个公开数据集以及某安防系统的RFID定位数据集上的实验结果表明,相比于HUIM-ACS算法,该算法挖掘的高效用语义轨迹模式数量增加了10%~15%,运行时间减少了7%~12%。

Mining Semantic Trajectory Patterns from Geo-Tagged Data

User-generated social media data tagged with geographic information present messages of dynamic spatiotemporal trajectories. These increasing mobility data provide potential opportunities to enhance the understanding of human mobility behaviors. Several trajectory data mining approaches have been proposed to benefit from these rich datasets, but fail to incorporate aspatial semantics in mining. This study investigates mining frequent moving sequences of geographic entities with transit time from geo-tagged data. Different from previous analysis of geographic feature only trajectories, this work focuses on extracting patterns with rich context semantics. We extend raw geographic trajectories generated from geo-tagged data with rich context semantic annotations, use regions-of-interest as stops to represent interesting places, enrich them with multiple aspatial semantic annotations, and propose a semantic trajectory pattern mining algorithm that returns basic and multidimensional semantic trajectory patterns. Experimental results demonstrate that semantic trajectory patterns from our method present semantically meaningful patterns and display richer semantic knowledge.

Finding frequent trajectories by clustering and sequential pattern mining

Data mining is a powerful emerging technology that helps to extract hidden information from a huge volume of historical data. This paper is concerned with finding the frequent trajectories of moving objects in spatio-temporal data by a novel method adopting the concepts of clustering and sequential pattern mining. The algorithms used logically split the trajectory span area into clusters and then apply the k-means algorithm over this clusters until the squared error minimizes. The new method applies the threshold to obtain active clusters and arranges them in descending order based on number of trajectories passing through. From these active clusters, inter cluster patterns are found by a sequential pattern mining technique. The process is repeated until all the active clusters are linked. The clusters thus linked in sequence are the frequent trajectories. A set of experiments conducted using real datasets shows that the proposed method is relatively five times better than the existing ones. A comparison is made with the results of other algorithms and their variation is analyzed by statistical methods. Further, tests of significance are conducted with ANOVA to find the efficient threshold value for the optimum plot of frequent trajectories. The results are analyzed and found to be superior than the existing ones. This approach may be of relevance in finding alternate paths in busy networks （ congestion control）, finding the frequent paths of migratory birds, or even to predict the next level of pattern characteristics in case of time series data with minor alterations and finding the frequent path of balls in certain games.

Mining spatiotemporal patterns of urban dwellers from taxi trajectory data

With the widespread adoption of location- aware technology, obtaining long-sequence, massive and high-accuracy spatiotemporal trajectory data of individuals has become increasingly popular in various geographic studies. Trajectory data of taxis, one of the most widely used inner-city travel modes, contain rich information about both road network traffic and travel behavior of passengers. Such data can be used to study the microscopic activity patterns of individuals as well as the macro system of urban spatial structures. This paper focuses on trajectories obtained from GPS-enabled taxis and their applications for mining urban commuting patterns. A novel approach is proposed to discover spatiotemporal patterns of household travel from the taxi trajectory dataset with a large number of point locations. The approach involves three critical steps： spatial clustering of taxi origin-destination （OD） based on urban traffic grids to discover potentially meaningful places, identifying thresh- old values from statistics of the OD clusters to extract urban jobs-housing structures, and visualization of analytic results to understand the spatial distribution and temporal trends of the revealed urban structures and implied household commuting behavior. A case study with a taxi trajectory dataset in Shanghai, China is presented to demonstrate and evaluate the proposed method.

成品油运输车轨迹频繁模式挖掘

针对成品油运输车轨迹数据,提出一种结合轨迹聚类和地图匹配的频繁模式挖掘算法,该算法首先利用Fréchet距离进行相似性度量,再利用DBSCAN进行轨迹聚类,选取类簇中最长轨迹数据进行地图匹配,获取频繁货运路径。基于北京市部分运输车轨迹数据进行实验,获得实验结果进行分析,利用获得的频繁货运路径分析出成品油货运路径选择中安全便捷、低物流成本的特点。

位置大数据的价值提取与协同挖掘方法

随着位置服务和车联网应用的不断普及,由地理数据、车辆轨迹和应用记录等所构成的位置大数据已成为当前用来感知人类社群活动规律、分析地理国情和构建智慧城市的重要战略性资源,是大数据科学研究极其重要的一部分.与传统小样统计不同,大规模位置数据存在明显的混杂性、复杂性和稀疏性,需要对其进行价值提取和协同挖掘,才能获得更为准确的移动行为模式和区域局部特征,从而还原和生成满足关联应用分析的整体数据模型.因此,着重从以下3个方面系统综述了针对位置大数据的分析方法,包括:(1)针对数据混杂性,如何先从局部提取出移动对象的二阶行为模式和区域交通动力学特征;(2)针对数据复杂性,如何从时间和空间尺度上分别对位置复杂网络进行降维分析,从而建立有关社群整体移动性的学习和推测方法;(3)针对数据的稀疏性,如何通过协同过滤、概率图分析等方法构建位置大数据全局模型.最后,从软件工程角度提出了位置大数据分析的整体框架.在这一框架下,位置数据将不仅被用来进行交通问题的分析,还能够提升人们对更为广泛的人类社会经济活动和自然环境的认识,从而体现位置大数据的真正价值.

时空轨迹大数据模式挖掘研究进展

时空轨迹挖掘是数据挖掘领域的前沿研究课题,通过研究和开发时空轨迹挖掘技术,来发现隐藏在轨迹大数据中有价值的规律和知识以供决策支持。本文介绍了时空轨迹大数据模式挖掘与知识发现领域的研究进展;然后对时空轨迹模式挖掘技术产生的背景、应用领域和研究现状作了简介,并探讨了面向时空轨迹大数据模式挖掘的研究内容、系统架构以及关键技术,最后对时空轨迹频繁模式、伴随模式、聚集模式和异常模式的挖掘算法思想进行了阐述。

时空轨迹群体运动模式挖掘研究进展

群体运动模式是时空轨迹模式挖掘的重要内容,用于发现群体运动规律、群体运动趋势以及群体事件。本文首先对群体运动模式建模和群体运动模式挖掘两个层面存在的问题与挑战进行了阐述。接着,对群体运动模式进行了分类,将其分为有领导者运动模式、伴随模式、突变运动模式、流行运动模式、聚集运动模式和发散运动模式。最后,介绍了各种群体运动模式之间的区别与联系,对各种群体运动模式挖掘算法思想进行了综述。

基于FP-Tree模型的频繁轨迹模式挖掘方法

通过对经典频繁模式数据结构FP-tree的扩展与改进,提出了一种适用于处理轨迹数据的灵活高效的FP-tree轨迹挖掘方法(NFTM)。首先运用二维筛选和GPS格式过滤的方法对轨迹进行预处理,然后将有效数据经一次扫描后,生成按照真实轨迹顺序排列且具备时空属性的改进型FP-tree,使用动态数组存储模式挖掘过程中得到的候选集,根据用户的输入针对性输出相应时间和频率范围的频繁轨迹。最后通过与GSP算法、Prefixspan算法的对比测试表明,该算法具有更短执行时间和更优性能。

融合语义特征的移动对象轨迹预测方法

提出一种融合语义特征的移动对象轨迹预测方法．该方法首先将用户的地理位置轨迹转化成语义轨迹，挖掘出语义模式集，同时在语义轨迹中分析用户的移动行为和规律，将具有相似语义行为的用户进行聚类，并挖掘出每个聚类的地理模式集．然后，基于挖掘到的用户个体语义模式集和相似用户地理模式集，构造用来索引和局部匹配的模式树STP-Tree和SLP-Tree．通过对STP-Tree和SLP-Tree的索引和局部匹配，引入一个加权函数实现给定对象运动的语义位置预测．此方法在传统的地理模式预测方法的基础上融合语义特征，可以有效地提取用户的语义活动行为，克服地理位置点特征的局限．在大量真实和人工轨迹数据集上的实验结果表明：该方法的预测准确率较传统方法均有显著提高．

一种针对特定车辆潜在群体的行驶轨迹预测方法

城市智能交通信息系统所产生的原始交通数据中存在有大量的可供城市道路安全管理使用的未知模式信息,为了有效利用这些数据,提出一种针对特定车辆潜在群体的行驶轨迹预测方法(SVPG-TP)。该方法主要利用所提出的特定车辆潜在群体搜索算法及序列模式发现与贝叶斯网络互补预测的方式,有效地解决了目前城市道路安全中最为关注的潜在群体发现以及行驶轨迹预测这两大问题。通过实验测试验证所提出的算法在城市道路安全管理中的有效性及实用性,并实现软件系统,为保障城市道路安全提供可靠的技术手段。

基于轨迹的内河船舶行为模式挖掘

从内河海量的船舶AIS数据中提取出有用的交通知识,辅助水上安全监管,对于研究日益复杂的水上交通安全形势具有重要意义。基于内河船舶行为特征,构造由船舶位置、航速和航向4个维度组成的船舶航行状态空间来描述船舶行为。针对传统DBSCAN聚类算法提取状态空间中相似船舶轨迹存在计算复杂高的问题,提出增量式算法改进DBSCAN算法用以高效地计算不同船舶的行为模式;然后利用核密度估计等统计方法对不同模式的船舶行为特征进行数据挖掘,得到船舶航速、航向和位置的时空分布特征规律,进一步挖掘不同行为模式下的船舶微观特征。以武汉航段的汉江分叉航道水域作为研究案例,利用所提的方法对该水域分析研究,得到了6类不同行为模式,挖掘出不同模式下分叉航道内船舶静态属性信息(船舶类型、船舶尺寸)、空间分布特征(轨迹点分布、航速分布、航向分布)、船舶到达规律等信息。利用该模型所提取的知识有助于水上监管人员迅速获取水域交通态势,从而提高水上交通安全监管的水平和效率。

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

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

位置不确定移动时空轨迹频繁模式挖掘

针对不确定移动轨迹ε-邻域的空间分布特征,提出一种基于网格分割面积的不确定轨迹近邻网格概率匹配方法,将原始不确定移动轨迹数据转换为以网格单元表示的概率序列数据,通过对经典序列模式挖掘算法Prefix Span的相关改进,设计并实现了适应于严格时间间隔约束条件下的移动概率序列模式挖掘算法UTFP-Prefix Span.合成数据的测试实验仿真结果表明,本文所提出的方法较基于距离的概率转换方法在挖掘结果、可扩展性等方面具有更好的性能.