Ma trận chi phí căn chỉnh chuỗi thời gian Dynamic Time Warping (DTW)

Mục tiêu kiến thức

• Hiểu giải thuật Dynamic Time Warping (DTW) để so sánh độ tương đồng giữa 2 chuỗi thời gian có độ dài hoặc tốc độ biến thiên khác nhau.
• Tính toán ma trận khoảng cách cục bộ bằng broadcasting 2D thuần vector hóa (s1[:, None] - s2[None, :]) ** 2.
• Xây dựng bảng quy hoạch động tích lũy chi phí tối ưu (Accumulated Cost Matrix).

Mô tả bài toán

Viết hàm dynamic_time_warping_distance(s1: np.ndarray, s2: np.ndarray) -> tuple[float, np.ndarray]:

• s1: Mảng 1D chuỗi thời gian thứ nhất độ dài N.
• s2: Mảng 1D chuỗi thời gian thứ hai độ dài M.
• Kiểm tra tính hợp lệ:
• Nếu len(s1) == 0 hoặc len(s2) == 0, raise ValueError("Chuoi thoi gian khong duoc rong").
• Tính ma trận chi phí cục bộ:

D = (s1[:, np.newaxis] - s2[np.newaxis, :])² có kích thước (N, M).

• Bảng chi phí tích lũy cost kích thước (N, M):
• cost[0, 0] = D[0, 0].
• Cột đầu tiên: cost[i, 0] = cost[i - 1, 0] + D[i, 0] với i = 1, …, N-1.
• Hàng đầu tiên: cost[0, j] = cost[0, j - 1] + D[0, j] với j = 1, …, M-1.
• Các ô còn lại (i ≥ 1, j ≥ 1):

cost[i, j] = D[i, j] + min(cost[i - 1, j], cost[i, j - 1], cost[i - 1, j - 1]).

• Trả về tuple (dtw_dist, cost):
• dtw_dist = float(cost[N - 1, M - 1]).
• cost: ma trận tích lũy (N, M).

Ràng buộc

• Thời gian chạy tối đa: 1000ms.
• Giới hạn bộ nhớ: 256MB.
• Dữ liệu đầu vào tuân thủ đúng kiểu dữ liệu và miền giá trị được mô tả.