移动轨迹数据挖掘：一项综合概述

需积分: 9 154 浏览量更新于2024-07-17 收藏 1.87MB PDF 举报

"郑宇撰写的《Trajectory Data Mining》是一篇在ACM Transactions on Intelligent Systems and Technology, Vol. 6, No. 3, Article 1中发表的文章，出版日期为2015年9月。文章全面概述了在移动定位和移动计算技术进步背景下产生的大量空间轨迹数据及其挖掘技术。" 轨迹数据挖掘是近年来随着GPS、蓝牙、Wi-Fi等定位技术以及移动设备的普及而兴起的一个重要研究领域。这些技术使得我们能够收集到各种移动对象（如人、车辆、动物）的运动轨迹，形成了海量的时空轨迹数据。这些数据蕴含着丰富的行为模式、偏好信息以及潜在的规律性。文章首先从轨迹数据的生成入手，讨论了如何从原始位置信号中提取出有意义的轨迹数据。这一过程可能涉及到数据清洗、坐标标准化、时间同步等多个步骤，确保轨迹数据的质量和准确性。接下来，作者深入探讨了轨迹数据预处理的技术，这是数据挖掘的基础。预处理包括但不限于数据降噪、缺失值处理、轨迹分割和归一化等，这些方法有助于提高后续分析的效率和效果。在数据管理方面，文章介绍了针对轨迹数据的存储和索引策略。由于轨迹数据的特殊性（高维、动态、时序性强），传统的数据库系统往往难以有效处理，因此需要专门设计的空间数据库和索引结构，如R树、quadtree和kd-tree等，以支持高效的查询和分析。然后，文章详细阐述了多种轨迹数据挖掘任务，包括： 1. 轨迹模式挖掘：寻找频繁出现或具有代表性的轨迹模式，这有助于理解大规模移动对象的行为规律，如出行习惯、交通流模式等。 2. 异常检测：识别出与正常行为显著不同的轨迹，这些异常可能是由异常事件、设备故障或其他因素导致的，对于安全监控、欺诈检测等领域至关重要。 3. 轨迹分类：通过机器学习算法将轨迹分为不同的类别，例如根据驾驶风格、出行目的等进行分类，可应用于个性化推荐和服务。此外，文章还讨论了轨迹隐私保护、实时轨迹挖掘、多模态轨迹融合等前沿问题，以及这些技术在智能交通、环境监测、社交网络分析等领域的应用。《Trajectory Data Mining》这篇综述性文章为读者提供了一个全面了解轨迹数据挖掘领域的窗口，揭示了该领域的核心问题、关键技术以及未来的研究方向，对于从事相关研究和应用的人员具有很高的参考价值。

1: 8  ●  Y. Zheng 
 
 
ACM Trans. Intelligent systems and technologies, Vol. 6, No. 3, Article 1, Pub. date: Sept. 2015. 
 
Online Data Reduction: As many applications require to transmit trajectory data in a 
timely fashion, a series of online trajectory compression techniques have been proposed to 
determine whether a newly acquired spatial point should be retained in a trajectory. There 
are two major categories of online compression methods. One is the window-based algori-
thms, such as the Sliding Window algorithm [46] and Open Window algorithm [67]. The 
other is based on speed and direction of a moving object.  
     The idea of the Sliding Window algorithm is to fit the spatial points in a growing sliding 
window with a valid line segment and continue to grow the sliding window until the appro-
ximation error exceeds some error bound. As illustrated in Fig 5 B), 

 will be first reser-
ved as the error for 

 exceeds the threshold. Then, the algorithm starts from 

 and reserve 


. Other points are negligible. Different from the Sliding Window algorithm, the Open 
Window algorithm [67] applies the heuristic of the Douglas-Peucker algorithm to choose 
the point with the maximum error in the window (e.g. 

 in Figure 5 B) to approximate the 
trajectory  segment.  This  point  is  then  used  as  a  new  anchor  point  to  approximate  its 
successors. 
     Another category of algorithms consider speed and directions as key factors when doing 
online trajectory compression. For instance, Potamias et al. [84] use a safe area, derived 
from the last two locations and a given threshold, to determine whether a newly acquired 
point contains important information. If the new data point is located within the safe area, 
then this location point is considered as redundant and thus can be discarded; otherwise, it 
is included in the approximated trajectory. 
     Compression with Semantic Meaning: A series of research [87][17] aims to keep the 
semantic meanings of a trajectory, when compressing the trajectory. For instance, in a 
location-based social network [140], some special points where a user stayed, took photos, 
or changed direction greatly, would be more significant than other points in presenting 
semantic meanings of a trajectory. Chen et al.  [17] proposed a trajectory simplification 
algorithm (TS), which considers both the shape skeleton and the aforementioned special 
points. TS first divides a trajectory into walking and non-walking segments using a traject-
ory segmentation algorithm [147] (see Section 3.4). A point is weighted by its heading 
change degree and the distance to its neighbors.  
    Another branch of research [45][90] considers trajectory compression with the cons-
traints of transportation networks. For example, we can reduce the redundant points on the 
same road segment. We can even discard all the newly acquired points after an anchor 
point, as long as the moving object is traveling on the shortest path from the anchor point 
to its current location. This branch of work usually needs the support of map-matching 
algorithms (refer to Section 3.5). In 2014, PRESS [90] was proposed to separate the spatial 
representation of a trajectory from its temporal representation. PRESS consists of a hybrid 
spatial  compression  algorithm  and  an  error  bounded  temporal  compression  algorithm, 
compressing the spatial and temporal information of trajectories respectively. The spatial 
compression combines frequent sequential pattern mining techniques with Huffman Cod-
ing to reduce the size of a trajectory; i.e. a frequently traveled path can be represented by a 
shorter code, therefore saving storages.   
3.4 Trajectory Segmentation 
In many scenarios, such as trajectories clustering and classification, we need to divide a 
trajectory into segments for a further process. The segmentation does not only reduce the 
computational  complexity  but  also  enable  us  to  mine  richer  knowledge,  such  as  sub-
trajectory patterns, beyond what we can learn from an entire trajectory. In general, there 

Trajectory Data Mining: An Overview

ACM Trans. Intelligent Systems and Technology, Vol. 6, No. 3, Article 1, Pub. date: Sept. 2015.

are three types of segmentation methods.

The first category is based on time interval. For example, as illustrated in Figure 6 A),

if the time interval between two consecutive sampling points is larger than a given

threshold, a trajectory is divided into two parts at the two points, i.e. 







and 









. Sometimes, we can divid a trajectory into segments of the same time length.

The second category of methods is based on the shape of a trajectory. For example, as

demonstrated in Figure 6 B), we can partition a trajectory by the turning points with

heading direction changing over a threshold. Alternative, we can employ the line

simplification algorithms, such as Douglas-Peucker algorithm, to identify the key points

maintaining a trajectory’s shape, as depicted in Figure 6 C). The trajectory is then

partitioned into segments by these key points. Similarly, Lee et al [51] proposed to partition

a trajectory by using the concept of Minimal Description Language (MDL), which is

comprised of two components: 󰇛󰇜 and 󰇛󰇜 . 󰇛󰇜 is the length, in bits, of the

description of the hypothesis ; and 󰇛󰇜 is the length, in bits, of the description of the

data when encoded with the help of the hypothesis. The best hypothesis  to explain  is

the one that minimizes the sum of 󰇛󰇜 and 󰇛󰇜. More specifically, they use 󰇛󰇜 to

denote the total length of partitioned segments (like 









and 









), while let 󰇛󰇜 to

represent the total (perpendicular and angle) distance between the original trajectory and

the new partitioned segments. Using an approximation algorithm, they find a list of chara-

cteristic points that minimize 

󰇛



󰇜

 󰇛󰇜 from a trajectory. The trajectory is partit-

ioned into segments by these characteristic points.

Figure 6. Methods of trajectory segmentation

The third category of methods is based on the semantic meanings of points in a

trajectory. As illustrated in Figure 6 D), a trajectory can be divided into segments, i.e. 













and 







, based on the stay points it contains. Whether we should keep the

stay points in the divided results depends on applications. For example, in a task of travel

speed estimation, we should remove the stay points (from a taxi’s trajectory) where a taxi

was parked to wait for passengers [125]. On the contrary, to estimate the similarity between

two users [52], we can only focus on the sequences of stay points, while skipping other raw

trajectory points between two consecutive stay points.

Another semantic meaning-based trajectory segmentation is to divide a trajectory into

segments of different transportation modes, such as driving, taking a bus, and walking. For

example, Zheng et al. [144][146][149] proposed a walk-based segmentation method. The

key insight is that people have to walk through the transition between two different transpo-

rtation modes. Consequently, we can first distinguish Walk Points from non-Walk Points in

a trajectory, based on a point’s speed () and acceleration (). The trajectory can then

be divided into alternate Walk Segments and non-Walk Segments, as illustrated in Figure 7

A). In reality, however, as shown in Figure 7 B), a few points from non-Walk Segments

may be detected as possible Walk Points, e.g., when a bus moves slowly in traffic

A) Time interval-based

B) Turning point-based

C) Key shape point-based

D) Stay point-based

剩余40页未读，继续阅读

weixin_44175369

粉丝: 0
资源: 1

移动轨迹数据挖掘：一项综合概述

TrajectoryData

轨迹挖掘综述-微软研究院-郑宇

Trajectory Pattern mining

Trajectory Data Mining

Unveiling the complexity of human mobility by mining trajectory data

Classification on Trajectory data Using Extreme Learning Machine

Trajectory mining from anonymous binary motion sensors in Smart Environment

Mining frequent trajectory pattern based on vague space partition

中国新能源汽车&充电桩（2018-2022）数据-最新出炉.zip

JDK17 win64位版本下载

最新资源