轨迹分析 2 轨迹相似性度量
2 轨迹相似性度量#
相似性度量方法
https://www.jianshu.com/p/8a5755c1831a
基于轨迹点的相似性度量方法：
全局匹配度量法
即两条轨迹要整体相似，每个点都要在另一条轨迹中找到对应点。常见的方法有：
- Euclid 欧式距离
- ERP 编辑距离
- DTW 动态时间扭曲方法。 对轨迹进行局部的拉伸或者缩放，从而可以对不同采样率和不同长度的轨迹进行比较，DWT距离就是所有最优匹配轨迹点间距离的累加和
局部匹配度量法
只要求两条轨迹部分相似，并且计算距离的时候只看匹配点之间的距离。常见的方法有
- EDR 编辑距离法。 将距离量化为0，1两个值来消除噪音。方法鲁棒性好，但是不满足距离的三角不等式
- LCSS 最长公共子序列 https://www.cnblogs.com/CheeseZH/p/8830482.html
zzz: 对于轨迹数据，可以将(x,y,t) 做一个映射，映射到一个格子标号。即将(x,y) 对应到一个位置范围。在这个位置范围内相同出现的次数可以认为是两个轨迹的相似度度量。
而且实际情况中，在商场的环境下。用户浏览路线的宽度其实是可以没有限制的可以进行适当的放松，这个必须得结合真实的商场布局图来设计。
这样(x, y, t) => x_y的字符id
python实现 https://www.jianshu.com/p/d7b8db280a01
Levenshtein实现
https://github.com/ztane/python-Levenshtein/#documentation
- Frechet 费累歇距离。人遛狗的狗绳距离
- KBCT：K-BCT是一个参数free的方法，结合了DTW和LCSS
- LCS,
- CATS
方法对比
| 方法 | 优缺点 | |
|---|---|---|
| 欧式距离 | x 采样率，轨迹点必须一致 | |
| DTW | 可以不同采样频率，不同长度； | |
| ERP | 可以不同采样频率，不同长度；不是所有的匹配点都计算距离，减少噪音 | |
code - DTW#
dtw实现
from fastdtw import fastdtw
euclidean_norm = lambda x, y: np.abs(x - y)
fastdtw(x, y, dist=euclidean_norm)
import numpy as np
from cdtw import pydtw
r = np.array([1,2,3,4])
q = np.array([2,3,4,5])
d = pydtw.dtw(r,q,pydtw.Settings(step = 'p0sym', #Sakoe-Chiba symmetric step with slope constraint p = 0
window = 'palival', #type of the window
param = 2.0, #window parameter
norm = False, #normalization
compute_path = True))
d.get_dist()
# 连接 https://pypi.org/project/cdtw/
dtw方法效率提高#
https://zhuanlan.zhihu.com/p/73292069
参考资料
- https://blog.csdn.net/songbinxu/article/details/86660136
- 成对数据计算效率问题: http://cn.voidcc.com/question/p-pvczjbyi-bmw.html
- 这里踩了一个坑：安装上fastdtw后速度仍然慢。在测试机上跑n=30条数据两两组队，耗时38s，mac上才3s。后来发现是mac上采用的是Cpython， 测试机上运行的是纯python版本。
- dtw加速计算的一些资料: https://jozeelin.github.io/2019/07/03/UCR-DTW%E5%92%8CUCR-ED%E6%A8%A1%E5%9E%8B%E8%AF%A6%E8%A7%A3/
效率问题#
假设有n个用户，如果采用计算相似矩阵/距离矩阵的方法，需要两两之间，即n^2的运算量。实际操作时候，如果n太大，可以先建立item-＞users的倒排，只针对有共同item的user进行计算。 将每个iterm下的user两两组成pair后再uniq即可。
facebook的一个开源工具 https://github.com/facebookresearch/faiss