

首页  思维导图  详情



轨迹数据挖掘paper

2016-01-01 09:45:04   0  举报





仅支持查看

AI智能生成

paper整理

轨迹数据overview

模版推荐

作者其他创作

大纲/内容

轨迹数据

人的移动

主动记录

被动记录

移动数据（手机）

信用卡数据

车的移动（GPS 数据）

用途

资源分配

路况分析

提高运输网络

动物移动

用途

迁徙

行为

生活情况

自然移动

包含自然现象

气象

飓风

龙卷

环境

气候

海洋

预处理

噪声过滤

原因

数据存在不完美

sensor噪声

其他因素

数据类型

可接受

其他

主要方法

用估计值代换噪声测量

均值（中值）过滤

滑动窗口

适用于单个噪声点

卡尔曼 & 粒子过滤

模型

卡尔曼：线性模型 + 高斯噪声

粒子：更普通但效率略低

计算过程

初始化p个粒子

动态模型模拟

测量模型

选择

用异常值检测移走噪声点

基于速度

假设噪声点数少于normal

适用于

初始错误

数据稀少的情况

stay point 检测

适用于

单点位置

多点around

方法

时间戳空间点P 改变成有意义位置序列

应用

旅行推荐

目的地预测

taxi推荐

油价消费预测

预测path旅行时间

子主题

行驶方向建议

预测算法

立足点 & 后继距离？阈值

在距离阈值内，立足点与最远后继的时间跨度？阈值

轨迹压缩

压缩每秒记录时间戳的地理坐标

防止费电、大量通信、计算、数据存储

方法

offline压缩

用过之后压缩

online压缩

边运动边压缩

具体方法

距离度量

垂直欧几里得距离

时间异步欧几里得距离

压缩

离线压缩

用近似线段代替原轨迹

在线数据压缩

基于窗口的

基于移动物体的速度 or 方向

基于语义压缩

基于地理位置的社交网络

分段走路&不走路用轨迹分段算法

基于运输网络限制的压缩

key

删除同一路段的冗余点

基于 map-matching 算法

从时间中分开空间，结合Huffman Coding（越多越少）

轨迹分段

方法

时间间隔

连续两个采样点？阈值

轨迹形状

头部方向变化？阈值

Douglas-Peucker 算法，以Key Point 作为划分点

Minimal Description Language(MDL)

基于点的语义

Stay Point

travel速度估计

评估2个用户相似性

不同的运输模型

基于走路的分段模型

局限

当速度过快时，易认为是 non-work

当速度过慢时，易认为是 work

方法

Backward Segment

(un)Certain Segment

连续不确定段是否大于阈值

Map-Matching

用途

评估交通流量

车辆导航

预测车辆往哪去

探测原始地与目的地之间最频繁交通路段

方法

基于额外信息

地理

配对GPS到附近的roads

拓扑

frechet 距离

概率

其他先进方法

考虑采样点的范围

局部/递增

基于距离&方向的本地优化点

适用于在线应用

取决于轨迹的采样率

好处：高效

全局方法

适用于离线

更精准、但低效

算法

本地&全局信息（几何、拓扑、概率）去处理低采样率轨迹的匹配

方法

找出候选路段，其点在一个圆内

计算圆内每个候选点的概率

暗示着局部和几何信息

计算每两个连续轨迹点的候选点之间的转移概率

找到一条最大全局匹配概率的路径

轨迹数据管理

轨迹的索引 & 检索

KNN查询

分类

KNN点查询

考虑order

更关注是否有更好的连接到查询位置，而不是相似的查询形状

KNN轨迹查询

定义两个路径之间的距离/相似函数

有效的查询处理算法

检索经过指定路线的车辆轨迹

将road网络的path作为轨迹，用KNN轨迹查询去找出接近的path轨迹

用map-matching将轨迹转成路段，再建立indexing结构管理path与轨迹关系

范围查询

作用

获取旅行速度，流量等特征，为分类或者预测的数据挖掘任务

方法

时间+2D地理坐标构成3维，用3D Query Box在3D-RTree上找点

随时间增加。重叠增加

将时间周期分成时间间隔，像RTree为每段建立一个唯一的空间Index

随时间增加，结构不变，且结构可以由不同时间间隔共享

地理空间分成grids，为grids建立时间index

grid -> 用2D坐标表示(开始时间, 结束时间)

检索方式 -> hybrid B+ tree

轨迹距离/相似性

计算范围

轨迹与一些点之间的距离

两条轨迹之间的距离

轨迹中的不确定性

来源

2个连续采样点之间的不确定性

为了隐私增加的不确定性

减少轨迹数据的不确定性

原因：低采样率导致

2个连续采样点之间间隔时间太久了

taxi GPS坐标、用户check-in记录、鸟迁移

方法

为查询针对不确定轨迹建模

路径联想：构建k种最有可能的路径

针对于road网络

针对于自由空间

确定轨迹（与查询点相关的）

构建路径（近似于路径）

自由空间的方法

将地理空间划分成统一的grid

grids连接形成region

结束点所在的grid可以相连

起始点(p1, p2)在相邻的(g1, g2)

结束点(q1, q2)在同一个grid

travel时间相似

起始点所在的grid可以相连

起始点(p1, p2)在同一个grid

结束点(q1, q2)在同一个grid

travel时间相似

建立routable graph

基于routing算法找到最可能的route

轨迹数据的隐私

实时连续的基于位置的服务1km之内的交通路况

空间伪装

混淆区域

Path Confusion

基于短IDs的欧拉直方图

虚拟轨迹

历史轨迹的发布

收集一个人很可能被推断出home & 工作位置的轨迹，确定这个人是谁

方法

cluster-based

generalization-based

suppression-based

grid-based

轨迹模式挖掘

Moving Together Patterns

用处

研究物种迁徙

研究军事侦察

子主题

轨迹聚类

在轨迹中挖掘序列模式

从轨迹中挖掘周期模式

轨迹分类

异常点检测

将轨迹转变成其他形式

 Collect

Get Started

4-1数据挖掘的应用

 Collect

Get Started

paper2

 Collect

Get Started

testDemo_paper

 Collect

Get Started

paper





0 条评论

下一页