指标计算方法论

计算货车轨迹点的道路路线变化度，可以考虑以下几种方法：

1. 轨迹相似度分析：

  • 动态时间规整（Dynamic Time Warping, DTW）：用于测量不同轨迹之间的相似度，可以处理速度和时间不一致的问题。
  • 编辑距离（Edit Distance on Real sequence, EDR）：计算两个轨迹之间最小编辑操作的数量，包括插入、删除和替换。

2. 离散弗雷歇距离（Discrete Fréchet Distance）：

  • 用于测量两条曲线之间的相似度，考虑曲线的形状和顺序。

3. 轨迹聚类：

  • 使用聚类算法（如K-means、DBSCAN）将轨迹分为不同的簇，然后分析每个簇的代表轨迹，以此来判断道路路线的变化。

4. 热力图分析：

  • 将轨迹点映射到地图上，生成热力图，直观地展示道路使用情况和变化情况。

5. 转折点检测：

  • 通过检测轨迹中的转折点，分析路径的变化情况。可以使用角度变化、速度变化等指标。

6. 路径匹配和比对：

  • 将轨迹点映射到道路网络上，使用地图匹配算法（Map Matching）将GPS轨迹与道路网络匹配，然后计算轨迹与标准路径的偏差。

具体选择哪种方法，可以根据数据的特点和分析的需求来确定。如果需要更详细的实现，可以结合具体的算法和代码示例进行深入分析。

你可以尝试以下步骤来实现这些方法：

  1. 预处理数据：清理和过滤GPS数据，去除噪音和异常点。
  2. 选择适当的相似度算法：根据数据特性选择合适的轨迹相似度计算方法。
  3. 实现轨迹相似度计算：编写代码实现轨迹相似度计算。
  4. 分析和评估结果：根据计算结果分析道路路线变化的情况。
  5. 动态时间规整（Dynamic Time Warping, DTW）

介绍

DTW 是一种用于测量两个时间序列相似度的算法。它允许对时间轴进行非线性变换，以便找出两个序列之间的最佳对齐路径。对于轨迹相似度分析，DTW 能很好地处理速度和时间的不一致性。

步骤

  1. 初始化：创建一个代价矩阵，矩阵的每个元素代表两个轨迹点之间的距离。
  2. 填充代价矩阵：通过动态规划填充代价矩阵，从左上角到右下角，每个元素的值等于当前点的距离加上前一步的最小累计代价。
  3. 回溯路径：从代价矩阵的右下角回溯到左上角，找到最小代价路径，这条路径代表两个轨迹的最佳对齐方式。

优点

  • 能处理时间和速度的不一致性。
  • 适用于不同长度的轨迹。

缺点

  • 计算复杂度较高，适用于小规模数据集。
  • 对噪声敏感。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import numpy as np

def dtw_distance(ts1, ts2):

	n, m = len(ts1), len(ts2)
	dtw_matrix = np.zeros((n+1, m+1))

	dtw_matrix[1:, 0] = np.inf
	dtw_matrix[0, 1:] = np.inf

	for i in range(1, n+1):
	    for j in range(1, m+1):
	        cost = np.linalg.norm(ts1[i-1] - ts2[j-1])
	        dtw_matrix[i, j] = cost + \
	        min(dtw_matrix[i-1, j],    # insertion
		          dtw_matrix[i, j-1],    # deletion
	            dtw_matrix[i-1, j-1])  # match

return dtw_matrix[n, m]

trajectory1 = np.array([[1, 2], [2, 3], [3, 4]])
trajectory2 = np.array([[1, 2], [2, 2], [3, 3]])
print("DTW Distance:", dtw_distance(trajectory1, trajectory2))
  1. 编辑距离（Edit Distance on Real sequence, EDR）

介绍

EDR 是一种用于计算两个轨迹之间最小编辑操作数量的算法，包括插入、删除和替换操作。与传统的编辑距离不同，EDR 适用于处理连续数值数据，如轨迹点。

步骤

  1. 定义阈值：设定一个阈值，用于判断两个轨迹点是否相似。
  2. 初始化矩阵：创建一个矩阵，用于记录每一步的编辑操作数量。
  3. 填充矩阵：通过动态规划填充矩阵，计算每一步的编辑操作数量。
  4. 获取编辑距离：矩阵右下角的值即为两个轨迹的编辑距离。

优点

  • 能处理轨迹点的插入、删除和替换操作。
  • 适用于处理噪声和异常点。

缺点

  • 需要设定阈值，阈值的选择可能影响结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def edr_distance(ts1, ts2, epsilon):

	n, m = len(ts1), len(ts2)

	edr_matrix = np.zeros((n+1, m+1))

	for i in range(1, n+1):
    edr_matrix[i, 0] = i
	for j in range(1, m+1):
    edr_matrix[0, j] = j

	for i in range(1, n+1):
    for j in range(1, m+1):
        if np.linalg.norm(ts1[i-1] - ts2[j-1]) < epsilon:
            cost = 0
        else:
            cost = 1
        edr_matrix[i, j] = min(edr_matrix[i-1, j] + 1,    # deletion
                               edr_matrix[i, j-1] + 1,    # insertion
                               edr_matrix[i-1, j-1] + cost)  # match/mismatch

		return edr_matrix[n, m]
		
epsilon = 1.0
print("EDR Distance:", edr_distance(trajectory1, trajectory2, epsilon))

总结

  • DTW 适用于需要考虑时间和速度变异的轨迹相似度计算，但计算复杂度较高。
  • EDR 适用于处理轨迹点的插入、删除和替换操作，对噪声具有一定的鲁棒性。

进行轨迹聚类是一种将相似的轨迹分组的技术。对于包含经纬度、时间和时速的轨迹数据，可以采用以下步骤进行轨迹聚类：

  1. 数据预处理

    1. 清洗数据：去除异常值和噪音数据。
    2. 时间同步：如果轨迹时间不同步，可以对轨迹进行插值，使其时间点一致。
    3. 规范化数据：将经纬度、时间和时速等特征进行规范化处理。

  2. 特征提取

    从轨迹数据中提取特征是关键步骤。常用的特征包括：

    1. 起点和终点：轨迹的起点和终点位置。
    2. 路径形状：使用轨迹的形状特征，如曲率、转角等。
    3. 时速分布：轨迹中的时速分布情况。可以将轨迹划分为等长的时间段或空间段，然后计算每段的特征。

  3. 距离计算

    选择适当的距离度量方法，如动态时间规整（DTW）或离散弗雷歇距离等，用于计算轨迹之间的相似度。

  4. 聚类算法

    常用的轨迹聚类算法包括：

    1. K-means聚类：需要预先指定聚类数。
    2. DBSCAN：不需要指定聚类数，适合处理噪音数据。
    3. 层次聚类：适合处理不同尺度的聚类。

示例代码

以下是一个简单的基于DTW距离和DBSCAN算法的轨迹聚类示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import numpy as np
from sklearn.cluster import DBSCAN
from fastdtw import fastdtw
from scipy.spatial.distance import euclidean

def compute_dtw_distance_matrix(trajectories):

	n = len(trajectories)
	distance_matrix = np.zeros((n, n))

	for i in range(n):
		for j in range(i+1, n):
			distance, _ = fastdtw(trajectories[i], trajectories[j], dist=euclidean)
			distance_matrix[i, j] = distance
			distance_matrix[j, i] = distance
	return distance_matrix

trajectories = [
np.array([[116.3, 39.9, 0, 50], [116.4, 39.8, 1, 60], [116.5, 39.7, 2, 55]]),
np.array([[116.3, 39.9, 0, 52], [116.4, 39.8, 1, 58], [116.5, 39.7, 2, 53]]),
np.array([[116.7, 40.0, 0, 40], [116.8, 40.1, 1, 45], [116.9, 40.2, 2, 50]])
]

trajectories_coords = [traj[:, :2] for traj in trajectories]
distance_matrix = compute_dtw_distance_matrix(trajectories_coords)
dbscan = DBSCAN(metric='precomputed', eps=10, min_samples=2)
labels = dbscan.fit_predict(distance_matrix)
print("聚类结果:", labels)

步骤解析

  1. 数据预处理：示例中省略了数据清洗和规范化步骤，请根据实际数据进行处理。
  2. 特征提取：这里只使用了经纬度进行DTW距离计算，可以根据需求添加其他特征。
  3. 距离计算：使用fastdtw库计算DTW距离矩阵。
  4. 聚类算法：使用DBSCAN算法进行轨迹聚类。

总结

  • 根据具体应用需求和数据特点，选择适当的特征提取方法和距离度量方式。
  • 使用合适的聚类算法，如DBSCAN适合处理噪音数据，K-means适合已知聚类数量的情况。
  • 对聚类结果进行评估和验证，以确保聚类的有效性和准确性。
学习
#DTW相似度 #文档
指标计算方法论
https://blogs.nover.fun/post/2024/07/指标计算方法论/
作者
Nover
发布于
2024年7月24日
许可协议