MOIR/HR:覆盖区域受限的热门区域挖掘

挖掘被移动对象频繁造访的封闭空间区域,即热门区域是从轨迹数据库中发现移动对象轨迹模式的关键前提.现有挖掘工作难以限制热门区域的大小.基于之前的移动对象管理平台MOIR[1],扩展实现了一个带有覆盖范围约束的热门区域挖掘模块,并引入3个新的度量指标:标准化密度、主导积分、差异度,用于精炼超出覆盖范围约束的区域.基于真实轨迹数据集得到的可视化及量化结果,给出了一个具有有说服力的概念证明原型来检验上述思想.     

基于轨迹结构的移动对象热点区域发现

针对现有热点区域发现算法难以从轨迹数据集中准确识别活动热点的问题,提出了基于轨迹结构的热点区域发现框架（TS_HS）。TS_HS由候选区域发现（CHSD）算法和热点区域过滤（HSF）算法组成。首先,使用基于网格相对密度的CHSD识别空间上的轨迹密集区域作为候选热点区域;然后,利用HSF根据候选区域中轨迹的活动特征和时间变化特征,筛选出移动对象活动频繁的热点区域。在Geolife数据集上进行的实验表明,与基于全局密度的热门区域发现算法（GD_HR）以及移动轨迹时空热点区域发现算法（SDHSRD）相比,TS_HS能更有效地解决多密度热点区域的识别问题。实验结果表明,TS_HS能够根据轨迹的活动特征准确发现移动对象的活动热点区域。     

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

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

基于过滤-精炼策略的用户特定时间段移动轨迹特征提取

发现移动用户在特定时间段的轨迹特征是实现用户个性化推荐服务的关键之一.采用过滤——精炼策略,研究了如何从单用户的大量轨迹数据中发现其在较长时间内的特定时间段的兴趣点.在过滤阶段,将用户连续若干天中同一特定时间段内的轨迹数据进行基于密度的聚类,从而得到用户在这些天中每天的该特定时间段的停留点.在精炼阶段,对所有的停留点再一次聚类,进而得到用户在这些天中该特定时间段的兴趣点.最后,通过实验验证了该方法的有效性.     

空间数据库平面曲线的点最近邻查询

基于线段最近邻查询,提出平面曲线的点最近邻查询(LPNN)概念,设计LPNN查询算法。通过R树索引空间对象,采用过滤和精炼两步法提高检索速度。过滤阶段利用平面曲线直接影响区域和筛选规则得到候选对象集,精炼阶段使用优先队列,避免相同点的重复计算,得到平面曲线的点最近邻查询结果。实验结果表明,该算法具有较好的查询性能。     

基于环境标记约束的不确定轨迹频繁路径挖掘

针对环境约束的不确定轨迹数据的频繁路径问题,设计了一种适应于严格时间约束条件下基于环境约束的位置不确定的移动概率序列挖掘算法（UETFP-PrefixSpan）,算法通过设置类标号把不同环境下的不确定轨迹数据区分开,利用概率支持度对频繁项集进行了重新定义,通过减少某些特定序列模式生成过程的扫描,来减少投影数据库的规模及扫描投影数据库的时间,提高算法效率。测试实验结果表明,改进后的UETFP-PrefixSpan算法挖掘结果更符合现实情况,算法执行效率更高。     

基于时间序列聚类的轨迹停留点检测算法

针对采样不规则轨迹的停留点检测准确性不高的问题,提出了一种基于时间序列聚类的停留点检测算法。首先基于数据场理论设计了一种综合考虑时空特性的混合特征密度测量方法,然后根据停留点中心密度比入口大的特性,采用过滤—精炼策略提取停留点。在过滤阶段,将时间连续且满足最小密度阈值的点作为候选停留点。在精炼阶段,通过最大阈值筛选出实际停留点。实验结果表明,该方法能够有效检测采样不规则轨迹中的停留点,相较于已有方法具有较高的准确性和较低的时间消耗。     

基于载客数据的出租车热门区域功能发现

根据出租车行驶载客数据中提取的乘客出行模式和上下客热门区域,提出一种出租车热门区域功能发现方法。采用基于交通数据时空特性的出租车行驶数据聚类算法,实现热门区域划分。建立基于潜在Dirichlet分配的热门区域乘客出行特征发现模型,对具有相似乘客出行模式的出租车热门区域进行聚类。通过总结各热门区域的具体功能,发现在不同客流时间段内的区域功能与乘客出行模式间的关系。实验结果表明,该方法能够有效发现热门区域的功能特点。     

发现含有第一类项目约束的频繁集的快速算法

与Apriori-like类型的算法相比,Zaki提出的基于垂直数据库结构及基于网络理论的算法将关联规则挖掘的运行速度提高了一个数量级,并且这些算法非常适合挖掘低支持度、长模式的关联规则。以Ecalt算法为原型,讨论了如何将项目约束引入关联规则挖掘过程的问题,从理论上证明了引入约束后的Eclat＋算法可以大大提高算法的效率和速度,并对相关的算法进行了比较。     

一种基于规则的离群挖掘算法

离群数据挖掘是指从大量数据中挖掘明显偏离、不满足一般行为模式的数据。现有的离群数据挖掘算法大多对密集的交易数据库缺乏有效的处理,文中提出了一种高效的基于规则的离群挖掘算法。该算法使用了多层最大离群支持度及最小离群兴趣度,计算1-离群条件集的幂集,并在数据结构中存储了交易标识符链表,使得扫描数据库的次数仅为一次,从而提高了挖掘的速度、效率且使得结果更具有决策意义。文中使用此算法对某一商场的部分销售数据库进行了实验,结果表明该算法能有效、迅速地发现密集数据库中的离群数据。     

Formation tracking of multi-vehicle systems in unknown environments using a multi-region control scheme

In this paper, a multi-region control scheme is proposed for a formation of nonholonomic vehicles to track a reference trajectory while avoiding collisions and preserving network connectivity in unknown environments. The proposed control scheme defines three regions, safe region, dangerous region and transition region. In different regions, priority is given to different control objectives. In safe region where trajectory tracking holds the priority, the proposed control scheme guarantees bounded tracking of the reference trajectory for each vehicle. In dangerous region where avoidance control is the main objective, a new bounded potential function is designed to characterise constraints of obstacle and inter-vehicle collision avoidance as well as connectivity maintenance. By introducing a series of transition functions, smooth switching between trajectory tracking and avoidance control is achieved in transition region. It has been proved that each vehicle can track its reference trajectory while satisfying the constraints simultaneously with a bounded controller which means that the proposed control scheme satisfies input constraints by properly tuning parameters. Simulation results demonstrate the effectiveness of the proposed method.     

Supervised coverage control of multi-agent systems

In this paper, we consider a dynamic coverage problem for multi-agent systems, where the main objective of a group of mobile agents is to explore a given compact region. We propose a novel control scheme, where we introduce a supervisor that assists a group of agents with the centralized coverage control law and the global trajectory tracking control law. The coverage control law ensures the coverage task is done until the agents end up in local minima, and when they do, the global trajectory tracking control law ensures that the agents are deployed to uncovered regions. Our control scheme is designed to be decoupled such that only one control law is active at a given time. In addition to the coverage objective, we design control laws for coverage agents to avoid collisions and maintain proximity to a supervisor. Moreover, we utilize feedback linearization to use the proposed control scheme for coverage control of kinematic unicycle agents. We validate our approach via numerical simulations.     

Hierarchically linked infinite hidden Markov model based trajectory analysis and semantic region retrieval in a trajectory dataset

With an increasing attempt of finding latent semantics in a video dataset, trajectories have become key components since they intrinsically include concise characteristics of object movements. An approach to analyze a trajectory dataset has concentrated on semantic region retrieval, which extracts some regions in which have their own patterns of object movements. Semantic region retrieval has become an important topic since the semantic regions are useful for various applications, such as activity analysis. The previous literatures, however, have just revealed semantically relevant points, rather than actual regions, and have less consideration of temporal dependency of observations in a trajectory. In this paper, we propose a novel model for trajectory analysis and semantic region retrieval. We first extend the meaning of semantic regions that can cover actual regions. We build a model for the extended semantic regions based on a hierarchically linked infinite hidden Markov model, which can capture the temporal dependency between adjacent observations, and retrieve the semantic regions from a trajectory dataset. In addition, we propose a sticky extension to diminish redundant semantic regions that occur in a non-sticky model. The experimental results demonstrate that our models well extract semantic regions from a real trajectory dataset.     

Sequential pattern mining of geo-tagged photos with an arbitrary regions-of-interest detection method

Geo-tagged photos leave trails of movement that form trajectories. Regions-of-interest detection identifies interesting hot spots where many trajectories visit and large geo-tagged photos are uploaded. Extraction of exact shapes of regions-of-interest is a key step to understanding these trajectories and mining sequential trajectory patterns. This article introduces an efficient and effective grid-based regions-of-interest detection method that is linear to the number of grid cells, and is able to detect arbitrary shapes of regions-of-interest. The proposed algorithm is combined with sequential pattern mining to reveal sequential trajectory patterns. Experimental results reveal quality regions-of-interest and promising sequential trajectory patterns that demonstrate the benefits of our algorithm.     

基于多尺度空间划分与路网建模的城市移动轨迹模式挖掘

针对城市移动轨迹模式挖掘问题展开研究, 提出移动全局模式与移动过程模式相结合的挖掘方法, 即通过移动轨迹的起始位置点--终点位置点 (Origin-destination, OD点) 与移动过程序列分别进行移动全局模式与过程模式的发现. 在移动全局模式发现中, 提出了弹性多尺度空间划分方法, 避免了硬性等尺度网格划分对密集区域边缘的破坏, 同时增强了密集区域与稀疏区域的区分能力.在移动过程模式发现中, 提出了基于移动轨迹的路网拓扑关系模型构建方法, 通过路网关键位置点的探测抽取拓扑关系模型.最后基于空间划分集合与路网拓扑模型对原始 移动轨迹数据进行序列数据转换与频繁模式挖掘. 通过深圳市出租车历史 GPS 轨迹数据的实验结果表明, 该方法与现有方法相比在区域划分、数据转换等方面具有更好的性能, 同时挖掘结果语义更为丰富, 可解释性更强.     

Effective and efficient trajectory outlier detection based on time-dependent popular route

With the rapid proliferation of GPS-equipped devices, a myriad of trajectory data representing the mobility of various moving objects in two-dimensional space have been generated. This paper aims to detect the anomalous trajectories with the help of the historical trajectory dataset and the popular routes. In this paper, both of spatial and temporal abnormalities are taken into consideration simultaneously to improve the accuracy of the detection. Previous work has developed a novel time-dependent popular routes based algorithm named TPRO. TPRO focuses on finding out all outliers in the historical trajectory dataset. But in most cases, people do not care about which trajectory in the dataset is abnormal. They only yearn for the detection result of a new trajectory that is not included in the dataset. So this paper develops the the upgrade version of TPRO, named TPRRO. TPRRO is a real-time outlier detection algorithm and it contains the off-line preprocess step and the on-line detection step. In the off-line preprocess step, TTI (short for time-dependent transfer index) and hot TTG (short for time-dependent transfer graph) cache are constructed according to the historical trajectory dataset. Then in the on-line detection step, TTI and hot TTG cache are used to speed up the detection progress. The experiment result shows that TPRRO has a better efficiency than TPRO in detecting outliers.     

Computing and visualizing popular places

Data analysis and knowledge discovery in trajectory databases is an emerging field with a growing number of applications such as managing traffic, planning tourism infrastructures, analyzing professional sport matches or better understanding wildlife. A well-known collection of patterns which can occur for a subset of trajectories of moving objects exists. In this paper, we study the popular places pattern, that is, locations that are visited by many moving objects. We consider two criteria, strong and weak, to establish either the exact number of times that an object has visited a place during its complete trajectory or whether it has visited the place, or not. To solve the problem of reporting popular places, we introduce the popularity map. The popularity of a point is a measure of how many times the moving objects of a set have visited that point. The popularity map is the subdivision, into regions, of a plane where all the points have the same popularity. We propose different algorithms to efficiently compute and visualize popular places, the so-called popular regions and their schematization, by taking advantage of the parallel computing capabilities of the graphics processing units. Finally, we provide and discuss the experimental results obtained with the implementation of our algorithms.     

A framework for regional association rule mining and scoping in spatial datasets

The motivation for regional association rule mining and scoping is driven by the facts that global statistics seldom provide useful insight and that most relationships in spatial datasets are geographically regional, rather than global. Furthermore, when using traditional association rule mining, regional patterns frequently fail to be discovered due to insufficient global confidence and/or support. In this paper, we systematically study this problem and address the unique challenges of regional association mining and scoping: (1) region discovery: how to identify interesting regions from which novel and useful regional association rules can be extracted; (2) regional association rule scoping: how to determine the scope of regional association rules. We investigate the duality between regional association rules and regions where the associations are valid: interesting regions are identified to seek novel regional patterns, and a regional pattern has a scope of a set of regions in which the pattern is valid. In particular, we present a reward-based region discovery framework that employs a divisive grid-based supervised clustering for region discovery. We evaluate our approach in a real-world case study to identify spatial risk patterns from arsenic in the Texas water supply. Our experimental results confirm and validate research results in the study of arsenic contamination, and our work leads to the discovery of novel findings to be further explored by domain scientists.     

A two step salient objects extraction framework based on image segmentation and saliency detection

Salient objects extraction from a still image is a very hot topic, as it owns a lot of useful applications (e.g., image compression, content-based image retrieval, digital watermarking). In this paper, targeted to improve the performance of the extraction approach, we propose a two step salient objects extraction framework based on image segmentation and saliency detection (TIS). Specially, during the first step, the image is segmented into several regions using image segmentation algorithm and the saliency map for the whole image is detected with saliency detection algorithm. In the second step, for each region, some features are extracted for the SVM algorithm to classify the region as a background region or a salient region twice. Experimental results show that our proposed framework can extract the salient objects more precisely and can achieve a good extraction results, compared with previous salient objects extraction methods.     

Iterative path-accurate trajectory generation for fast sensor-based motion of robot arms

Sensor-based trajectory generation of industrial robots can be seen as the task of, first, adaptation of a given robot program according to the actually sensed world, and second, its modification that complies with robot constraints regarding its velocity, acceleration, and jerk. The second task is investigated in this paper. Whenever the sensed trajectory violates a constraint, a transient trajectory is computed that, both, keeps the sensed path, and reaches the sensed trajectory as fast as possible while satisfying the constraints. This is done by an iteration of forward scaling and backtracking. In contrast to previous papers, a new backtracking algorithm and an adaptation of the prediction length are presented that are favorable for high-speed trajectories. Arc Length Interpolation is used in order to improve the path accuracy. This is completed by provisions against cutting short corners or omitting of loops in the given path. The refined trajectory is computed within a single sampling step of 4 ms using a standard KUKA industrial robot.