DTW JS实现
DTW算法简介
动态时间规整（Dynamic Time Warping, DTW）是一种用于衡量两个时间序列相似性的算法，尤其适用于不同长度或局部速度不一致的序列比对。其核心思想是通过动态规划找到最小累积距离的路径。
DTW的JavaScript实现
以下是一个完整的DTW算法实现，包含距离计算和路径回溯功能：
function dtw(series1, series2, distanceFn = (a, b) => Math.abs(a - b)) {
const m = series1.length;
const n = series2.length;
// 初始化距离矩阵
const costMatrix = Array(m + 1).fill().map(() => Array(n + 1).fill(Infinity));
costMatrix[0][0] = 0;
// 填充距离矩阵
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
const cost = distanceFn(series1[i - 1], series2[j - 1]);
costMatrix[i][j] = cost + Math.min(
costMatrix[i - 1][j], // 插入
costMatrix[i][j - 1], // 删除
costMatrix[i - 1][j - 1] // 匹配
);
}
}
// 回溯最优路径
let i = m, j = n;
const path = [[i - 1, j - 1]];
while (i > 1 || j > 1) {
const minVal = Math.min(
costMatrix[i - 1][j] ?? Infinity,
costMatrix[i][j - 1] ?? Infinity,
costMatrix[i - 1][j - 1] ?? Infinity
);
if (minVal === costMatrix[i - 1][j - 1]) {
i--;
j--;
} else if (minVal === costMatrix[i - 1][j]) {
i--;
} else {
j--;
}
path.push([i - 1, j - 1]);
}
return {
distance: costMatrix[m][n],
path: path.reverse()
};
}使用示例
const seriesA = [1, 3, 4, 9, 8];
const seriesB = [1, 2, 3, 4, 5];
const result = dtw(seriesA, seriesB);
console.log("DTW距离:", result.distance);
console.log("对齐路径:", result.path);关键点说明
- 距离函数：默认使用欧氏距离（绝对值），可通过参数自定义（如余弦相似度）。
- 时间复杂度：O(mn)，适用于中小规模序列。
- 优化建议：
- 添加窗口约束（如Sakoe-Chiba Band）限制搜索范围。
- 对于长序列，考虑FastDTW等近似算法。
可视化扩展
结合库如D3.js可绘制对齐路径：
const pathPoints = result.path.map(([i, j]) => ({ x: i, y: j }));
// 使用D3绘制路径点连线此实现可直接用于时间序列分类、语音识别等场景。
