R语言中如何实现sliding window与DTW完成多变量时序图匹配

下面是可直接复用的实现逻辑，覆盖从时序切分、DTW距离计算到图构建的全流程，适配多变量时序场景：

核心实现流程 #

• 滑动窗口切分：按设定的窗口长度、滑动步长把原始长时序切为固定长度的子序列窗口，常规场景推荐30%~50%的窗口重叠率，避免时序特征被切断
• 多变量DTW距离计算：逐对计算窗口间的DTW距离，点间度量可根据数据特性选欧氏距离、加权欧氏距离或马氏距离
• 图结构构建：将每个窗口作为图节点，节点间DTW距离低于预设阈值时连边，边权为对应的DTW距离值，后续可直接在该图结构上开展各类图匹配任务

可运行代码示例 #

import numpy as np
from typing import Tuple, List

def multivariate_dtw(s1: np.ndarray, s2: np.ndarray) -> float:
    """
    计算两个多变量时间序列窗口的DTW距离
    入参s1、s2形状均为(窗口长度, 变量数)
    """
    n, m = len(s1), len(s2)
    dtw_matrix = np.full((n + 1, m + 1), np.inf)
    dtw_matrix[0, 0] = 0

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            # 多变量点距默认用各变量欧氏距离和，可按需替换为其他度量
            point_dist = np.sqrt(np.sum((s1[i-1] - s2[j-1]) ** 2))
            dtw_matrix[i, j] = point_dist + np.min([
                dtw_matrix[i-1, j],
                dtw_matrix[i, j-1],
                dtw_matrix[i-1, j-1]
            ])
    return dtw_matrix[n, m]

def sliding_window_split(ts: np.ndarray, window_size: int, step: int) -> List[np.ndarray]:
    """
    滑动窗口切分多变量时序
    入参ts形状为(总时序长度, 变量数)
    """
    windows = []
    total_len = len(ts)
    for start in range(0, total_len - window_size + 1, step):
        windows.append(ts[start:start + window_size])
    return windows

def build_similarity_graph(windows: List[np.ndarray], dist_threshold: float) -> Tuple[List[int], List[Tuple[int, int, float]]]:
    """
    基于DTW距离构建相似度图
    返回节点列表、带权边列表（起点id, 终点id, 边权=DTW距离）
    """
    nodes = list(range(len(windows)))
    edges = []
    for i in range(len(windows)):
        for j in range(i + 1, len(windows)):
            dtw_dist = multivariate_dtw(windows[i], windows[j])
            if dtw_dist < dist_threshold:
                edges.append((i, j, dtw_dist))
    return nodes, edges

# 调用示例
if __name__ == "__main__":
    # 模拟3变量、长度1000的多变量时序
    mock_ts = np.random.randn(1000, 3)
    # 切分窗口：窗口长度50，步长25（50%重叠率）
    window_list = sliding_window_split(mock_ts, window_size=50, step=25)
    # 构建相似度图：距离阈值需提前采样部分窗口计算距离分布后确定，示例暂设为10
    nodes, edges = build_similarity_graph(window_list, dist_threshold=10)

落地注意事项 #

• 性能优化：原生DTW时间复杂度为O(n²)，窗口量级较大时可给计算逻辑加JIT编译加速，或引入LB_Keogh等DTW下界方法做剪枝，提前过滤距离必然超过阈值的窗口对，减少冗余计算
• 图匹配适配：如果是做跨时序的图匹配，可直接将DTW距离的倒数作为节点相似度输入常规图匹配算法；如果是做子图匹配，可先将查询模式按相同窗口规则切分计算特征，再到目标图中检索匹配子结构
• 度量调整：如果不同变量的重要性有差异，可在点距计算环节给各变量分配对应权重，不要默认所有变量权重一致

内容的提问来源于stack exchange，提问作者Rosita binti Husain Faculty o