轨迹数据挖掘paper
2016-01-01 09:45:04 0 举报AI智能生成
paper整理
作者其他创作
大纲/内容
轨迹数据
人的移动
主动记录
被动记录
移动数据（手机）
信用卡数据
车的移动（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
用处
研究物种迁徙
研究军事侦察
子主题
轨迹聚类
在轨迹中挖掘序列模式
从轨迹中挖掘周期模式
轨迹分类
异常点检测
将轨迹转变成其他形式
0 条评论
下一页
