transdim

由陈新宇制作 • :globe_with_meridians: https://xinychen.github.io

Transportation data imputation（即 transdim，交通数据补全）。

机器学习模型在时空数据（spatiotemporal data）建模领域取得了重要进展——例如如何预测路网近期的交通状态。但是，当这些模型建立在从现实世界系统（如交通系统）中普遍收集的不完整数据之上时，会发生什么呢？

目录

• 关于本项目
• 任务与挑战
• 实现
• 快速开始
• 文档
• 出版物
• 贡献者

关于本项目

在 transdim 项目中，我们开发机器学习模型以帮助解决时空数据建模的一些最严峻挑战——从缺失数据补全（missing data imputation）到时间序列预测（time series prediction）。本项目的战略目标是为时空交通数据补全和预测任务创建准确且高效的解决方案。

赶时间吗？请查看以下内容。

任务与挑战

缺失数据就在那里，无论我们是否喜欢它们。真正有趣的问题是如何处理不完整的数据。

图 1: 时空设置下的两种经典缺失模式。

我们在真实世界数据上创建了三种缺失数据机制。

• 缺失数据补全 🔥

  • 随机缺失 (Random Missing, RM): 每个传感器完全随机地丢失观测值。(★★★)
  • 非随机缺失 (Non-random Missing, NM): 每个传感器在几天内丢失观测值。(★★★★)
  • 阻断缺失 (Blockout Missing, BM): 所有传感器在几个连续时间点丢失观测值。(★★★★)

图 2: 用于时空缺失交通数据补全的张量补全（Tensor Completion）框架。

• 时空预测 🔥
  • 无缺失值预测。(★★★)
  • 基于不完整观测值的预测。(★★★★★)

图 3: 我们提出的低秩自回归张量补全（Low-Rank Autoregressive Tensor Completion, LATC）补全器/预测器的示意图（绿色节点：观测值；白色节点：缺失值；红色节点/面板：预测；蓝色面板：用于构建张量的训练数据）。

实现

公开数据

在本项目中，我们将一些公开可用的数据集适配到了我们的实验中。这些数据的原始链接总结如下，

• 多元时间序列 (Multivariate time series)
  • 伯明翰停车数据集
  • 加州 PeMS 交通速度数据集 (大规模)
  • 广州城市交通速度数据集
  • 杭州地铁客流数据集
  • 伦敦城市移动速度数据集 (其他城市的数据也可在 Uber Movement 项目 获取)
  • 波特兰高速公路交通数据集 (包括交通流量/速度/占有率，参见 数据文档)
  • 西雅图高速公路交通速度数据集
• 多维时间序列 (Multidimensional time series)
  • 纽约市 (NYC) 出租车数据集
  • 太平洋表面温度数据集

例如，如果您想查看或使用这些数据集，请提前在 ../datasets/ 文件夹中下载它们，然后在您的 Python 控制台中运行以下代码：

import scipy.io

tensor = scipy.io.loadmat('../datasets/Guangzhou-data-set/tensor.mat')
tensor = tensor['tensor']

特别是，如果您对大规模交通数据感兴趣，我们推荐 PeMS-4W/8W/12W 和 UTD19。对于 PeMS 数据，您可以从 Zenodo 下载数据并将其放置在 datasets 文件夹中（数据路径示例：../datasets/California-data-set/pems-4w.csv）。然后您可以使用 Pandas 打开数据：

import pandas as pd

data = pd.read_csv('../datasets/California-data-set/pems-4w.csv', header = None)

对于模型评估，我们将“观测”数据中的某些条目掩码为缺失值，然后对这些“缺失”值执行补全操作。

模型实现

在我们的实验中，我们主要在 Numpy 上实现了一些机器学习模型，并使用 Jupyter Notebook 编写了这些 Python 代码。如果您想评估这些模型，请直接下载并运行这些笔记本（前提：提前下载数据集）。在下方的实现中，我们在可读性和效率方面改进了 Python 代码（在 Jupyter Notebook 中）。

我们提出的模型以粗体显示。

• imputer（插补模型）

Notebook	广州	伯明翰	杭州	西雅图	伦敦	纽约	太平洋
BPMF	✅	✅	✅	✅	✅	🔶	🔶
TRMF	✅	🔶	✅	✅	✅	🔶	🔶
BTRMF	✅	🔶	✅	✅	✅	🔶	🔶
BTMF	✅	✅	✅	✅	✅	🔶	🔶
BGCP	✅	✅	✅	✅	✅	✅	✅
BATF	✅	✅	✅	✅	✅	✅	✅
BTTF	🔶	🔶	🔶	🔶	🔶	✅	✅
HaLRTC	✅	🔶	✅	✅	✅	✅	✅
LRTC-TNN	✅	🔶	✅	✅	🔶	🔶	🔶

• predictor（预测模型）

Notebook	广州	伯明翰	杭州	西雅图	伦敦	纽约	太平洋
TRMF	✅	🔶	✅	✅	✅	🔶	🔶
BTRMF	✅	🔶	✅	✅	✅	🔶	🔶
BTRTF	🔶	🔶	🔶	🔶	🔶	✅	✅
BTMF	✅	🔶	✅	✅	✅	✅	✅
BTTF	🔶	🔶	🔶	🔶	🔶	✅	✅

• ✅ — 覆盖
• 🔶 — 未覆盖
• 🚧 — 开发中

对于这些模型的实现，我们同时使用 dense_mat（稠密矩阵）和 sparse_mat（稀疏矩阵）（或 dense_tensor（稠密张量）和 sparse_tensor（稀疏张量））作为输入。但是，如果您不希望看到迭代过程中的插补/预测性能，则无需如此操作，您可以从这些算法的输入中移除 dense_mat（或 dense_tensor）。

插补/预测性能

• 插补示例（基于广州数据）

(a) 8 月 1 日至 14 日两周内实际与估计速度的时间序列。

(b) 9 月 12 日至 25 日两周内实际与估计速度的时间序列。

BGCP 的插补性能（CP rank r=15 且缺失率α=30%），在三阶张量表示下的纤维缺失场景中，选取路段 #1 的估计结果作为示例。在这两个面板中，红色矩形代表纤维缺失（即全天速度观测值丢失）。

• 预测示例

快速开始

这是一个低秩张量补全与截断核范数最小化 (LRTC-TNN) 的插补示例。值得注意的是，与我们论文中的复杂公式不同，我们的 Python 实现非常容易使用。

• 首先，导入一些必要的包：

import numpy as np
from numpy.linalg import inv as inv

• 使用 Numpy 定义张量展开 (ten2mat) 和矩阵折叠 (mat2ten) 算子：

def ten2mat(tensor, mode):
    return np.reshape(np.moveaxis(tensor, mode, 0), (tensor.shape[mode], -1), order = 'F')

def mat2ten(mat, tensor_size, mode):
    index = list()
    index.append(mode)
    for i in range(tensor_size.shape[0]):
        if i != mode:
            index.append(i)
    return np.moveaxis(np.reshape(mat, list(tensor_size[index]), order = 'F'), 0, mode)

• 为截断核范数 (TNN) 最小化定义奇异值阈值处理 (SVT)：

def svt_tnn(mat, tau, theta):
    [m, n] = mat.shape
    if 2 * m < n:
        u, s, v = np.linalg.svd(mat @ mat.T, full_matrices = 0)
        s = np.sqrt(s)
        idx = np.sum(s > tau)
        mid = np.zeros(idx)
        mid[:theta] = 1
        mid[theta:idx] = (s[theta:idx] - tau) / s[theta:idx]
        return (u[:,:idx] @ np.diag(mid)) @ (u[:,:idx].T @ mat)
    elif m > 2 * n:
        return svt_tnn(mat.T, tau, theta).T
    u, s, v = np.linalg.svd(mat, full_matrices = 0)
    idx = np.sum(s > tau)
    vec = s[:idx].copy()
    vec[theta:] = s[theta:] - tau
    return u[:,:idx] @ np.diag(vec) @ v[:idx,:]

• 定义性能指标（即 RMSE, MAPE）：

def compute_rmse(var, var_hat):
    return np.sqrt(np.sum((var - var_hat) ** 2) / var.shape[0])

def compute_mape(var, var_hat):
    return np.sum(np.abs(var - var_hat) / var) / var.shape[0]

• 定义 LRTC-TNN：

def LRTC(dense_tensor, sparse_tensor, alpha, rho, theta, epsilon, maxiter):
    """Low-Rank Tensor Completion with Truncated Nuclear Norm, LRTC-TNN."""
    
    dim = np.array(sparse_tensor.shape)
    pos_missing = np.where(sparse_tensor == 0)
    pos_test = np.where((dense_tensor != 0) & (sparse_tensor == 0))
    dense_test = dense_tensor[pos_test]
    del dense_tensor
    
    X = np.zeros(np.insert(dim, 0, len(dim))) # \boldsymbol{\mathcal{X}}
    T = np.zeros(np.insert(dim, 0, len(dim))) # \boldsymbol{\mathcal{T}}
    Z = sparse_tensor.copy()
    last_tensor = sparse_tensor.copy()
    snorm = np.sqrt(np.sum(sparse_tensor ** 2))
    it = 0
    while True:
        rho = min(rho * 1.05, 1e5)
        for k in range(len(dim)):
            X[k] = mat2ten(svt_tnn(ten2mat(Z - T[k] / rho, k), alpha[k] / rho, int(np.ceil(theta * dim[k]))), dim, k)
        Z[pos_missing] = np.mean(X + T / rho, axis = 0)[pos_missing]
        T = T + rho * (X - np.broadcast_to(Z, np.insert(dim, 0, len(dim))))
        tensor_hat = np.einsum('k, kmnt -> mnt', alpha, X)
        tol = np.sqrt(np.sum((tensor_hat - last_tensor) ** 2)) / snorm
        last_tensor = tensor_hat.copy()
        it += 1
        if (it + 1) % 50 == 0:
            print('Iter: {}'.format(it + 1))
            print('MAPE: {:.6}'.format(compute_mape(dense_test, tensor_hat[pos_test])))
            print('RMSE: {:.6}'.format(compute_rmse(dense_test, tensor_hat[pos_test])))
            print()
        if (tol < epsilon) or (it >= maxiter):
            break

    print('Imputation MAPE: {:.6}'.format(compute_mape(dense_test, tensor_hat[pos_test])))
    print('Imputation RMSE: {:.6}'.format(compute_rmse(dense_test, tensor_hat[pos_test])))
    print()
    
    return tensor_hat

• 让我们尝试在广州城市交通速度数据集上运行：

import scipy.io

import scipy.io
import numpy as np
np.random.seed(1000)

dense_tensor = scipy.io.loadmat('../datasets/Guangzhou-data-set/tensor.mat')['tensor']
dim = dense_tensor.shape
missing_rate = 0.2 # Random missing (RM)
sparse_tensor = dense_tensor * np.round(np.random.rand(dim[0], dim[1], dim[2]) + 0.5 - missing_rate)

• 运行补全 (Imputation) 实验：

import time
start = time.time()
alpha = np.ones(3) / 3
rho = 1e-5
theta = 0.30
epsilon = 1e-4
maxiter = 200
tensor_hat = LRTC(dense_tensor, sparse_tensor, alpha, rho, theta, epsilon, maxiter)
end = time.time()
print('Running time: %d seconds'%(end - start))

此示例来自 ../imputer/LRTC-TNN.ipynb，您可以查看该 Jupyter Notebook 以获取详细信息。

Documentation

1. 随机奇异值分解的直观理解 (Intuitive Understanding of Randomized Singular Value Decomposition). 2020 年 7 月 1 日。
2. Matlab 和 Numpy 中生成随机数和数组 (Generating Random Numbers and Arrays in Matlab and Numpy). 2021 年 10 月 9 日。
3. 用于高维时间序列预测的低秩向量自回归模型 (Reduced-Rank Vector Autoregressive Model for High-Dimensional Time Series Forecasting). 2021 年 10 月 16 日。
4. 西雅图高速公路时空交通速度时间序列的动态模态分解 (Dynamic Mode Decomposition for Spatiotemporal Traffic Speed Time Series in Seattle Freeway). 2021 年 10 月 29 日。
5. 分析 Uber 移动速度数据中的缺失数据问题 (Analyzing Missing Data Problem in Uber Movement Speed Data). 2022 年 2 月 14 日。
6. 使用共轭梯度法求解矩阵方程 (Using Conjugate Gradient to Solve Matrix Equations). 2022 年 2 月 23 日。
7. 使用张量分解进行流体动力学修复 (NumPy) (Inpainting Fluid Dynamics with Tensor Decomposition (NumPy)). 2022 年 3 月 15 日。
8. 用于多元时间序列预测的时间矩阵分解 (Temporal Matrix Factorization for Multivariate Time Series Forecasting). 2022 年 3 月 20 日。
9. 使用非平稳时间矩阵分解预测多元时间序列 (Forecasting Multivariate Time Series with Nonstationary Temporal Matrix Factorization). 2022 年 4 月 25 日。
10. 使用 NumPy 实现克罗内克积分解 (Implementing Kronecker Product Decomposition with NumPy). 2022 年 6 月 20 日。
11. 张量自回归：一种多维时间序列模型 (Tensor Autoregression: A Multidimensional Time Series Model). 2022 年 9 月 3 日。
12. 在 Python 中复现流体流动数据的动态模态分解 (Reproducing Dynamic Mode Decomposition on Fluid Flow Data in Python). 2022 年 9 月 6 日。
13. 用于时间序列建模的卷积核范数最小化 (Convolution Nuclear Norm Minimization for Time Series Modeling). 2022 年 10 月 3 日。
14. 强化矩阵因子化用于时间序列建模：概率顺序矩阵因子化 (Reinforce Matrix Factorization for Time Series Modeling: Probabilistic Sequential Matrix Factorization). 2022 年 10 月 5 日。
15. 离散卷积和快速傅里叶变换逐步解释与实现 (Discrete Convolution and Fast Fourier Transform Explained and Implemented Step by Step). 2022 年 10 月 19 日。
16. Python 中用于图像修复的矩阵因子化 (Matrix Factorization for Image Inpainting in Python). 2022 年 12 月 8 日。
17. Python 中用于图像修复的循环矩阵核范数最小化 (Circulant Matrix Nuclear Norm Minimization for Image Inpainting in Python). 2022 年 12 月 9 日。
18. 用于时间序列补全和图像修复的低秩拉普拉斯卷积模型 (Low-Rank Laplacian Convolution Model for Time Series Imputation and Image Inpainting). 2022 年 12 月 10 日。
19. 用于彩色图像修复的低秩拉普拉斯卷积模型 (Low-Rank Laplacian Convolution Model for Color Image Inpainting). 2022 年 12 月 17 日。
20. 机器学习张量的直观理解 (Intuitive Understanding of Tensors in Machine Learning). 2023 年 1 月 20 日。
21. 用于速度场重建的低秩矩阵和张量因子化 (Low-Rank Matrix and Tensor Factorization for Speed Field Reconstruction). 2023 年 3 月 9 日。
22. 贝叶斯向量自回归预测 (Bayesian Vector Autoregression Forecasting)
23. 结构化低秩矩阵补全 (Structured Low-Rank Matrix Completion)

Publications

• Xinyu Chen, Zhanhong Cheng, HanQin Cai, Nicolas Saunier, Lijun Sun (2024). 用于交通时间序列补全的拉普拉斯卷积表示 (Laplacian Convolutional Representation for Traffic Time Series Imputation). IEEE Transactions on Knowledge and Data Engineering. 36 (11): 6490-6502. [DOI] [幻灯片] [数据与 Python 代码]

• Xinyu Chen, Lijun Sun (2022). 用于多维时间序列预测的贝叶斯时间因子分解。IEEE 模式分析与机器智能汇刊，44 (9): 4659-4673。[预印本] [DOI] [演示文稿] [数据与 Python 代码]

• Xinyu Chen, Mengying Lei, Nicolas Saunier, Lijun Sun (2022). 用于时空交通数据填补的低秩自回归张量补全。IEEE 智能交通系统汇刊，23 (8): 12301-12310。[预印本] [DOI] [数据与 Python 代码] (亦被 KDD 2021 的 MiLeTS 研讨会 部分接收，参见 研讨会论文)

• Xinyu Chen, Yixian Chen, Nicolas Saunier, Lijun Sun (2021). 用于时空交通数据填补的可扩展低秩张量学习。交通运输研究 C 辑：新兴技术，129: 103226。[预印本] [DOI] [数据] [Python 代码]

• Xinyu Chen, Jinming Yang, Lijun Sun (2020). 用于时空交通数据填补的非凸低秩张量补全模型。交通运输研究 C 辑：新兴技术，117: 102673。[预印本] [DOI] [数据与 Python 代码]

• Xinyu Chen, Zhaocheng He, Yixian Chen, Yuhuan Lu, Jiawei Wang (2019). 基于贝叶斯增强张量因子分解模型的缺失交通数据填补与模式发现。交通运输研究 C 辑：新兴技术，104: 66-77。[DOI] [演示文稿] [数据] [Matlab 代码] [Python 代码]

• Xinyu Chen, Zhaocheng He, Lijun Sun (2019). 一种用于时空交通数据填补的贝叶斯张量分解方法。交通运输研究 C 辑：新兴技术，98: 73-84。[预印本] [DOI] [数据] [Matlab 代码] [Python 代码]

• Xinyu Chen, Zhaocheng He, Jiawei Wang (2018). 通过 SVD 结合张量分解进行时空交通速度模式发现与不完整数据恢复。交通运输研究 C 辑：新兴技术，86: 59-77。[DOI] [数据]

  本项目源自上述论文，如果它们对您的研究有帮助，请引用这些论文。

合作者

Xinyu Chen 💻

Jinming Yang 💻

Yixian Chen 💻

Mengying Lei 💻

• 指导委员会

Lijun Sun 💻

Nicolas Saunier 💻

查看参与本项目的 贡献者 列表。

支持单位

许可证

本作品采用 MIT 许可证发布。

transdim 快速上手指南

Transdim (Transportation data imputation) 是一个专注于时空数据建模的机器学习项目，主要用于解决交通数据中的缺失值补全（Imputation）和时间序列预测（Prediction）任务。该项目基于 Numpy 实现，提供多种张量完成模型。

环境准备

• 操作系统: Linux / macOS / Windows
• Python 版本: >= 3.7
• 核心依赖:
  • numpy
  • scipy
  • pandas
  • jupyter (用于运行实验 Notebook)

💡 提示: 国内开发者建议使用清华源加速安装：

pip install -i https://pypi.tuna.tsinghua.edu.cn/simple numpy scipy pandas jupyter

安装步骤

1. 克隆仓库

   git clone https://github.com/xinychen/transdim.git
   cd transdim
   

2. 安装依赖 确保已安装上述核心依赖包。

3. 准备数据集 本项目需要手动下载公开数据集并放置到 datasets 文件夹中。例如：

   • 广州交通速度数据
   • Birmingham 停车数据
   • PeMS 交通流数据等

   下载后路径示例：../datasets/Guangzhou-data-set/tensor.mat

基本使用

方式一：运行 Jupyter Notebook（推荐）

项目提供了完整的模型评估 Notebook，适合直接查看结果和复现论文。

1. 启动 Jupyter Notebook：

   jupyter notebook
   

2. 打开对应模型的 Notebook 文件（位于 imputer/ 或 predictor/ 目录）。
3. 确保数据路径正确，点击运行单元格即可开始训练或补全。

方式二：核心算法快速演示

项目强调其 Python 实现比论文公式更简单。以下是核心的张量操作与奇异值阈值处理（SVT）代码片段，可直接在 Python 环境中运行：

import numpy as np
from numpy.linalg import inv as inv

# 定义张量展开算子
def ten2mat(tensor, mode):
    return np.reshape(np.moveaxis(tensor, mode, 0), (tensor.shape[mode], -1), order = 'F')

# 定义矩阵折叠算子
def mat2ten(mat, tensor_size, mode):
    index = list()
    index.append(mode)
    for i in range(tensor_size.shape[0]):
        if i != mode:
            index.append(i)
    return np.moveaxis(np.reshape(mat, list(tensor_size[index]), order = 'F'), 0, mode)

# 定义截断核范数最小化的奇异值阈值处理 (SVT)
def svt_tnn(mat, tau, theta):
    [m, n] = mat.shape
    if 2 * m < n:
        u, s, v = np.linalg.svd(mat @ mat.T, full_matric

注意: 上述代码为 README 中的核心逻辑片段。完整模型（如 BTMF, BGCP, LRTC-TNN 等）请通过 Jupyter Notebook 调用。

数据加载示例

import scipy.io

tensor = scipy.io.loadmat('../datasets/Guangzhou-data-set/tensor.mat')
tensor = tensor['tensor']