Code & Func

ST-MVL: Filling Missing Values in Geo-sensory Time Series Data

2020-11-09
Papers
Time Series
Machine Learning
最后更新：2024-09-19
13分钟
2417字

这篇文章发表在 IJCAI 2016 上。

解决的问题：如何在Geo-sensory Time Series上进行缺失值填充？

主要的idea：结合 IDW，SES，ICF 和 UCF 四种方法提出一种Multi-View learning based的方法来进行缺失值填充。

Introduction

为什么需要Filling Missing Values

  • 为了监测环境（如空气质量、天气），大量的传感器被部署在不同的地方，进而产生了大量的Geo-sensory Time Series数据。
  • 由于传感器故障和网络传输故障等原因，Geo-sensory Time Series数据往往存在大量的缺失：
    • Block missing包含
      • Spatial block missing：所有传感器的读数同时缺失。
      • temporal block missing：某个传感器的读数在一段时间（时间长度由$w$给定)内出现缺失
    • 2014/05/01 - 2015/04/30 Beijing default

Challenge

  • Readings （仪表读数） can be absent at arbitrary sensors and timestamps.

  • 同时可能会出现block missing（如下图 t2 时刻所有传感器都出现了缺失），这种情况某些方法是无法处理的（比如非负矩阵分解 non-negative matrix factorization NMF)

    default

  • Affected by multiple complex factors, sensor readings change over location and time significantly and non-linearly。

  • 对于某个传感器的读数来说，相隔比较的远的传感器的读数可能会比相隔比较近的传感器的读数对于当前传感器更加相近，如下图，相比于S3，S1和S2更近，但是S2和S3的AQI变化却更加相似。

    default

    default

Contribution

  • ST-MVL simultaneously considers 1) the spatial correlation between different time series and 2) the temporal correlation between readings at different timestamps in the same series, to generate a more accurate estimate.

  • ST-MVL integrates the advantages of global views, i.e. empirical models derived from the data over a long period, and those of local views, i.e. data-driven algorithms that are concerned with recent readings, to achieve better accuracy.

  • ST-MVL can handle the block missing problem, combining the four views in a multi-view learning

    framework.

  • We evaluate our method using Beijing air quality and meteorological data. The results demonstrate the advantages of our method compared with ten baselines.

Overview

Problem Definition

由于作者没有显式的提出Problem Definition，所以这里只是简单描述一下问题。

假设有m个传感器（记录的都是同一种数据，如PM2.5），其分别记录了长度为n的时间序列，我们可以将其表示成一个矩阵（如下图），第 i 行表示第 i 个传感器的所记录的时间序列，第 j 列表示 j 时刻所有传感器所记录的值，$v_{i,j}$表示第 i 个传感器第 j 时刻的读数。下图中$v_{2,j}$和$v_{1,j+1}$是缺失值，我们的问题就是利用已有的信息来填充缺失值，使其尽量与真实值接近。注意：这里不同的传感器只是在不同地方而已，它们记录的是同一种数据，例如都是记录PM2.5或都是记录空气湿度。

default

Multi View

对于相似度计算这个问题，我们可以通过不同的view/角度进行分析。view可以以下两种方式进行划分：

  • 利用同一空间维度还是同一时间维度上的信息：
    • spatial view：利用同一时刻空间上相邻的传感器的值去估计缺失值
    • temporal view：利用同一传感器相邻时刻的值去估计缺失值
  • 利用全部数据还是部分数据（这里特制是否只使用一段时间内的数据）
    • global view：考虑所有时刻的数据去估计缺失值
    • local view：考虑一个时间段内去估计缺失值

这一部分可以接合上面那张图来理解。

Framework

以下描述不是原文内容，但是将文中所使用的的方法统一到该框架下，有助于理解。

对于缺失值填充这个问题来说，我们可以把大部分方法（起码这篇文章所用到四个方法都可以）归结到同一个框架上去。

我们有$n$个已知值$v_1,v_2,v_3,…,v_n$和一个缺失值$u$，我们认为缺失值可以通过已知值的加权求和来进行预估，因此可以通过下面的公式对缺失值$u$进行估计：

$$ u=\sum_{i=1}^n{w_i*v_i} $$

那么现在问题的关键就是如何计算权重$w_i$了，如果我们能够计算出$v_i$和$u$之间的相似度$sim(v_i, u)$，那么我们就可以通过这样一个公式来计算权重$w_i$:

$$ w_i = \frac{sim(v_i,u)}{\sum_{i=1}^n sim(v_i,u)} $$

因此我们可以得到以下公式：

$$ u = \frac{ \sum_{i=1}^n sim(v_i,u)*vi}{\sum_{i=1}^n sim(v_i,u)} $$

那么接下来的问题就是如何去计算$v_i$和$u$之间的相似度$sim(v_i, u)$了。

ST-MLV

该文章的主要想法就是结合四个现有的缺失值填充方法，将他们得到的估计值进行综合得到预估值，四个方法分别为:

  • IDW (Inverse Distance Weighting)
  • SES (Simple Exponential Smoothing)
  • UCF (User-based Collaborative filtering)
  • ICF (Item-based Collaborative filtering)

四个方法分别代表不同的view（从下图中可以看出看出每种方法所代表的view），ST-MLV的主要想法就是先使用四种方法计算出缺失值的估计值，然后对这些估计值进行加权求和（Multi-View Learning)，这里权值通过训练得到。

default

接下来，我们分别介绍这个四种方法以及 Multi-View Learning。因为前面介绍过这四种方法都可以同一到一个框架下，将问题转化成相似度计算问题，因此在后面介绍着四种方法的时候，我们只分析它如何计算相似度。

为了方便，在下面的讨论中，假定要进行缺失值填充的值为$v_{2, j}$

Global Spatial View - IDW

IDW的想法是两个传感器在空间上越靠近，那么他们所记录的时间序列应该越相似，因此我们可以使用两个传感器之间距离的倒数来作为他们的相似度，同时，为了控制权值随着距离增加的衰减速度，增加一个恒为正的指数：

$$ IDW(v_{i,j}, v_{2,j})=distance(v_{i,j}, v_{2,j})^{-\alpha} $$

由于IDW是 Global View ，因此它会利用 $t$ 时刻的所有传感器（不含缺失值）进行预估（如下图所示，IDW利用的是红框内所有非缺失的值）。

default

Global Temporal View - SES

SES的想法是一个传感器/时间序列上，越相近的两个时刻越相似。它借鉴了指数平滑模型$\hat{v_{gt}}=\beta v_j + \beta (1-\beta)v_j-1 + \cdots + \beta(1-\beta)^{t_j-1}v_1$，将相似度表示为：

$$ SES(v_{2, i}, v_{2,j}) = \beta (1 - \beta)^{|j-i| - 1} $$

由于SES是Global View，因此它会利用第 $j$ 个传感器所有时刻（不含缺失值）的值来进行预估（如下图所示，SES利用的是红框内所有非缺失的值）。

default

Local View

在介绍 UCF 和ICF之前，由于他们都是local view和Collaborative filtering，所以这里先描述一下local view和Collaborative filtering。

首先，local view是计算相似度时只考虑一个时间窗内的数据，时间窗长度由 $w$ 给定，如果缺失值所在的时刻为$t$ ，则时间窗为$[j- \frac {w-1} {2}, j + \frac {w+1} {2}]$如下图，我们想要预测 $v_{2,j}$，而 $w=2$，所以我们在计算相似度的时候就只考虑 $t-2$ 到$t+2$的的数据。

default

Local Spatial View - UCF

UCF是一种常见的推荐算法，它主要的想法是，相似的用户对于同一个物品的评分是相近的。对于我们这个问题，一个传感器被当成一个用户。两个传感器的相似度的计算公式为：

$$ UCF(s_i, s) = 1 / {\sqrt{\frac {\sum_{k= j- \frac {w-1} {2}}^{ j + \frac {w+1} {2}} (v_{i,k}-v_{2,k})} {NT}}} $$ 其中 $NT$ 为时间窗内，两个传感器同时有读数的时刻数。

因为 UCF 计算的是两个传感器之间的相似度，按照之前提到的 framework，我们可以把这个相似度作为权值对同一时刻所有传感器的读数进行加权求和。

default

Local Temporal View - ICF

ICF 也是一种常见的推荐算法，它的主要想法是某个用户对相似的物品会做出相似的评分。对于我们这个问题**，一个时刻被当成一个物品**。则两个时刻的相似度的计算公式为：

$$ sim(t_i, t_2) = 1 / \sqrt {\frac {\sum_{k=i}^m(v_{k,i} - v_{k, 2})} {NS}} $$ 其中 $m$ 是传感器个数，$NS$ 是在 $t_i$ 和 $t_j$ 同时有读数的传感器的个数。

因为ICF计算的是两个时刻之间的相似度，按照之前提出的 framework，我们可以把这个相似度作为权值对这个传感器在时间窗内值进行加权求和。

default

Multi-View Learning

对于缺失值 $v_{2, j}$，我们可以使用上面提到的四种方法计算分别得到 $\hat {v_{gs}},\hat {v_{gt}},\hat {v_{ls}},\hat {v_{lt}}$，对这四个值进行一次线性回归得到最终的预测值 $\hat{v_{2,j}}$ :

$$ \hat{v_{2,j}} = w_1 * \hat {v_{gs}} + w_2 * \hat {v_{gt}} + w_3 * \hat {v_{ls}} + w_4 * \hat {v_{lt}} + b $$

其中 $w_k$ 是分别对每个传感器进行训练得到的。

同时，由于 UCF 和 ICF 不能很好的处理 block missing （因为如果时间窗内所有值都缺失，那么就无法计算出相似度了），所以遇到 block missing 的时候就先用 SES 或 IDW 进行一次填充先。ST-MVL的具体算法如下：

default

Experiment

Dataset

2014/05/01 - 2015/04/30 北京的空气质量和天气数据。

Metric

  • Mean Absolute Error (MAE):

    $$ MAE = \frac {\sum_i{|v_i - \hat{v_i}|}} n $$

  • Mean Relative Error (MRS): $$ MRE = \frac {\sum_i{|v_i - \hat{v_i}|}} {\sum_i v_i} $$

Result

default

default

Conclusion

这篇问题主要解决了时空数据上缺失值的问题，当时空数据集存在大量缺失值的问题时，可以考虑引入这篇文章的方法来解决这个问题，算法简洁有效，而且跑起来应该挺快的，算是一个比较好的 baseline。

Reference

6.S081 laba1 util
Docker Quick Start
本文标题：ST-MVL: Filling Missing Values in Geo-sensory Time Series Data
文章作者：wuxiaobai24
发布时间：2020-11-09
总访问量次
总访客数人次
Copyright 2024
站点地图