解读ICDE'22论文：基于鲁棒和可解释自编码器的无监督时间序列离群点检测算法

---

0. 导读

---

本文（Robust and Explainable Autoencoders for Unsupervised Time Series Outlier Detection）是由华为云数据库创新Lab联合丹麦Aalborg University与电子科技大学发表在顶会ICDE’22的文章。该文章针对时间序列离群点检测问题，提出了基于自动编码器（AE）和鲁棒的主成分分析（RPCA）结合的兼具鲁棒性和可解释性的深度神经网络算法鲁棒自动编码器（RAE）和鲁棒双自动编码器（RDAE），并通过大量的实验证明RAE和RDAE算法能有效提高时间序列离群点检测的准确度，鲁棒性和可解释性。ICDE是CCF推荐的A类国际学术会议，是数据库和数据挖掘领域顶级学术会议之一。

1. 摘要

---

随着数据挖掘技术在制造业、众包和交通等领域的普及，大量的时序性数据被产生及应用。本文研究的是时间序列的离群点检测问题，旨在解决时间序列离群点检测难以兼具鲁棒性和可解释性的问题。

鲁棒性 在无监督的情况下，训练数据可能已经包括了离群值。由于编码器压缩了输入时间序列中的所有观测值，因此产生的潜在表征对离群值很敏感。特别是当它们的幅度很大时，少量的离群值仍然可能污染潜在的表征。训练数据中的离群值有可能污染潜在表征，使潜在表征也捕捉到离群值模式；因此一些离群值可能有小的重建误差（图1b中的红色曲线），很难从干净的数据中分离出来。这对准确性产生了不利的影响。例如，图1b中的蓝色曲线显示了从被污染的潜在表征中重建的时间序列。这就产生了一些重建误差较小的离群值，使得它们很难被发现（见图1b中的橙色区域）。为了避免这种情况，需要采用鲁棒的解决方案，使潜像表征受训练数据中离群值的影响较小。

可解释性 自动编码器将具有较大重建误差的观测值视为离群值，给定一个输入时间序列 $\mathcal{T}$，自动编码器将重建洁净的时间序列 $\hat{\mathcal{T}}$。如果输入时间序列中的观测值与重建时间序列中的相应观测值有很大的偏差，即相应的重建误差 $\mathcal{T}-\hat{\mathcal{T}}$很大，那么自动编码器就把这些观测值看作是离群值。然而现有的自动编码器产生的重建时间序列 $\mathcal{T}$往往比较复杂（例如，图1b中的蓝色曲线），致使用户难以理解哪些观测值应该出现在正常状态下。这就要求有更多的可解释的解决方案，例如重建的时间序列具有一个易于人类理解的模式（例如图1c中的蓝色曲线）。

图1. 鲁棒性和可解释性说明

本文针对以上挑战提出了相应的解决办法，主要贡献如下：

• 本文提出了两个用于无监督时间序列离群点检测的自动编码器框架RAE和RDAE，提供了更好的鲁棒性和可解释性。
• 本文提出了一种post-hoc可解释性分析技术。该方法能够对基于AE的离群点检测方法的可解释性进行量化分析。
• RAE和RDAE算法的准确率和可解释性在真实的时间序列数据集上击败了现有的方法。

2. 背景

---

时间序列离群点检测 给定一个长度为 $C$的时间序列 $\mathcal{T}=<s_1, s_2, ..., s_C>$，其中每个点被定义为 $s_i\in\mathbb{R}^D$， $D$是变量的维度。根据领域知识设定一个离群点分数 $\mathcal{OS}(s_t)$，离群点分数越大， $s_i$越有可能被认定为离群点。连续被发现的离群点被认定为群体离群点。

鲁棒主成分分析 给定一个矩阵 $M$，主成分分析（PCA）能够识别一个低等级矩阵来近似矩阵 $M$。由于PCA通常采用单值分解（SVD）来识别低等级矩阵，PCA也有和SVD一样的问题，即对离群值非常敏感。为了改善PCA在离群值存在时的性能，有人提出了鲁棒主成分分析（RPCA）。RPCA旨在将给定的矩阵 $M$分离成两个矩阵的总和，一个是代表洁净数据的低秩矩阵 $L$，另一个是由元素间离群值组成的矩阵 $S$。具体来说，RPCA对原始矩阵 $M$进行分解，使 $M=L+S$。RPCA的目标函数为：

$$\arg \min _{\mathbf{L,S}} rank(\mathbf{L})+\lambda||\mathbf{S}||_0\ s.t. \ \mathbf{X}=\mathbf{L}+\mathbf{S}.$$

其中 $rank(\mathbf{L})$是矩阵 $\mathbf{L}$的秩， $||\mathbf{S}||_0$是矩阵 $\mathbf{S}$中的非零元素数量， $\lambda$是控制 $\mathbf{S}$影响权重的因子。

自动编码器 自动编码器由一个编码器（Encoder） $E_{\theta_{AE}}(\cdot)$和解码器（Decoder） $D_{\theta_{AE}}(\cdot)$组成，其流程图如图2所示。给定输入 $\mathbf{M} = [x_1, x_2, ..., x_C]$，则相对应的自动编码器输出为 $\hat{\mathbf{M}} = [\hat{x}_1, \hat{x}_2, ..., \hat{x}_C]$，用于离群点检测的自动编码器目标函数为：

$$\arg \min _{\theta_{A E}} ||\mathbf{M}-\hat{\mathbf{M}}||_2=||\mathbf{M}-D_{\theta_{AE}}(E_{\theta_{AE}}(\mathbf{M}))||_2$$

其中 $\theta_{AE}$代表自动编码器的参数。

图2. 自编码器流程图

模型设计 首先，本文提出的模型支持时间序列问题。第二，本文提出的模型具有鲁棒性。第三，本文提出的模型具备可解释性。第四，本文提出的模型支持非线性关系。第五，本文支持多视角的学习机制。基于上述分析，本文提出两个兼具鲁棒性和可解释性的自动编码器框架RAE和RDAE，其差异性如图3所示：

图3. 模型差异性

3. RAE和RDAE算法设计

---

本文提出的RAE和RDAE算法结合了自编码器的支持时间序列，支持非线性拟合和RPCA具有良好鲁棒性和可解释性的优势。我们会先后介绍这两个模型。

RAE

RAE结合了自编码器和RPCA的优点，其流程图如图4所示：

图4. RAE流程图

其中 $\mathcal{T}$是输入的时间序列， $\mathcal{T}_\mathbf{L}$和 $\mathcal{T}_\mathbf{S}$分别为重建的洁净时间序列与离群时间序列，有 $\mathcal{T}_\mathbf{L}=\mathcal{T}-\mathcal{T}_\mathbf{S}$。输入时间序列 $\mathcal{T}$经过编码器编码和解码器解码被分解为洁净时间序列 $\mathcal{T}_\mathbf{L}$和离群时间序列 $\mathcal{T}_\mathbf{S}$，离群时间序列作为自编码器下一次迭代的输入，即 $\mathcal{T}-\mathcal{T}_\mathbf{S}$。

编码器和解码器的公式为：

$$E_{\theta_{AE}}(\mathcal{T}_{\mathbf{L}})\overset{def}{=}\phi(\mathbf{W}_e*\mathcal{T}_{\mathbf{L}}+\mathbf{b}_e)$$

$$D_{\theta_{AE}}(\mathcal{T}_{\mathbf{L}})\overset{def}{=}\phi(\mathbf{W}_d*E_{\theta_{AE}}(\mathcal{T}_{\mathbf{L}})+\mathbf{b}_d)$$

其中 $\phi(\cdot)$是非线性变化，例如 $sigmoid$或 $relu$， $\mathbf{W}$和 $b$分别是可学习的权重矩阵和偏置， $\theta_{AE}=\{\mathbf{W}_e,\mathbf{b}_e,\mathbf{W}_d,\mathbf{b}_d\}$。

RAE的目标函数为：

$$\arg \min _{\theta_{A E},\mathcal{T}_{\mathbf{S}}}||\mathcal{T}_{\mathbf{L}}-D_{\theta_{AE}}(E_{\theta_{AE}}(\mathbf{\mathcal{T}_{\mathbf{L}}}))||_2 + \lambda||\mathcal{T}_{\mathbf{S}}||_1 \ s.t. \ \mathcal{T}=\mathcal{T}_{\mathbf{L}}+\mathcal{T}_{\mathbf{S}}.$$

由于本文将时间序列 $\mathcal{T}$分解为洁净时间序列 $\mathcal{T}_\mathbf{L}$和离群时间序列 $\mathcal{T}_\mathbf{S}$，因此离群点分数 $\mathcal{OS}$对离群时间序列 $\mathcal{T}=<\mathcal{S}_{\mathcal{s}_1}, \mathcal{S}_{\mathcal{s}_2}, ..., \mathcal{S}_{\mathcal{s}_C}>$的表达式为：

$$\mathcal{OS}=<||\mathcal{S}_{\mathcal{s}_1}||_2^2, ||\mathcal{S}_{\mathcal{s}_2}||_2^2, ..., ||\mathcal{S}_{\mathcal{s}_C}||_2^2>$$

其中 $||\cdot||_2$为二阶矩。

RAE算法的具体细节如图5所示：

图5. RAE算法细节

RAE算法有两个超参数 $\lambda$和 $\epsilon$，分别为正则化参数和离群分数 $\mathcal{OS}$的阈值。首先随机化参数起始值，然后通过目标函数更新模型中的参数。通过迭代RAE的输入时间序列和离群时间序列的差值迭代更新模型。算法将目标函数的更新分为两个部分， $||\mathcal{T}_{\mathbf{L}}-D_{\theta_{AE}}(E_{\theta_{AE}}(\mathbf{\mathcal{T}_{\mathbf{L}}}))||_2$用于优化参数 $\theta_{AE}$， $\lambda||\mathcal{T}_{\mathbf{S}}||_1$用于优化 $\mathcal{T}_{\mathbf{S}}$。当表达式满足两个停止条件其中之一，即 $condition_1$或 $condition_2$时算法停止。 $condition_1$的满足条件是 $\mathcal{T}=\mathcal{T}_{\mathbf{L}}+{\mathcal{T}_{\mathbf{S}}}$。 $condition_2$的满足条件是 ${\mathcal{T}_\mathbf{L}}$和 ${\mathcal{T}_{\mathbf{S}}}$不再变化。

RDAE

多视图学习已经被证明能够通过向学习器提供补充信息来提高学习算法的鲁棒性，例如矩阵视图和时间序列视图。受此启发，基于RAE的多视图框架RDAE被提出。其流程图如图6所示：

图6. RDAE流程图

其中 $f_{1_{\theta_1}}(\cdot)$为一个2D CNN，因为此时的输入不再是时间序列，而是一个矩阵。NN的输出为 $\hat{\mathbf{M}}$，其公式为：

$$\hat{\mathbf{M}}=f_{1_{\theta_1}}(\mathbf{M})\overset{def}{=}\phi(\mathbf{W}_1*\mathbf{M}+\mathbf{b}_1)$$

一个时间序列经常包含一些小的变化（即噪音），这些变化不被看作是离群值，但仍会影响模型的准确性。变换的作用是通过去除这些噪声来平滑 $\mathbf{M}$。通过这样做，我们希望Inner RAE能实现更干净的分解，从而实现更好的重建，从而提高鲁棒性。我们仍然希望平滑后的矩阵 $\hat{\mathbf{M}}$与 $\mathbf{M}$相似。

因此，此处设计了一个目标函数，使 $\hat{\mathbf{M}}$与 $\mathbf{M}$两者之间的差异最小：

$$\arg \min _{\theta_1}||\mathbf{M} - \hat{\mathbf{M}}||_2 = \arg \min _{\theta_1}||\mathbf{M} - f_{1_{\theta_1}}(\mathbf{M})||_2$$

对于Inner RAE，其输入为 $\hat{\mathbf{M}}$，它的编码器和解码器的公式为：

$$E_{\theta_{AE}}({\mathbf{L}})\overset{def}{=}\phi(\mathbf{W}_e*\mathbf{L}+\mathbf{b}_e)$$

$$D_{\theta_{AE}}(\mathbf{L})\overset{def}{=}\phi(\mathbf{W}_d*E_{\theta_{AE}}(\mathbf{L})+\mathbf{b}_d)$$

其中编码器和解码器均为2D CNNs。

Inner RAE的目标函数为：

$$\arg \min _{\theta_{A E},\mathcal{T}_{\mathbf{S}}}||\mathbf{L}-D_{\theta_{AE}}(E_{\theta_{AE}}(\mathbf{\mathbf{L}}))||_2 + \lambda_1||\mathbf{S}||_1 \ s.t. \ \hat{\mathbf{M}}=\mathbf{L}+\mathbf{S}.$$

Decoder的输出是 $\mathbf{L}$和 $\mathbf{S}$，他们分别通过两个Hankelization操作，得到 $\tilde{\mathbf{L}}=\mathcal{H}(\mathbf{L})$和 $\tilde{\mathbf{S}}=\mathcal{H}(\mathbf{S})$。接着 $\tilde{\mathbf{L}}$和 $\tilde{\mathbf{S}}$被转变为时间序列 $\mathcal{T}_{\mathbf{L}}$和 $\mathcal{S}_{\mathbf{S}}$。

对于Outer RAE，输入的时间序列 $\mathcal{T}$被转变为洁净时间序列与离群时间序列 $\mathcal{T}_\mathbf{L}$和 $\mathcal{T}_\mathbf{S}$。

其中 $f_{2_{\theta_2}}(\cdot)$是一个1D CNN。其公式为：

$$\mathcal{T}_{\mathbf{L}}=f_{2_{\theta_2}}(\mathbf{\mathcal{T}_{\mathbf{L}}})\overset{def}{=}\phi(\mathbf{W}_2*\mathbf{\mathcal{T}_{\mathbf{L}}}+\mathbf{b}_2)$$

Outer RAE的目标函数为：

$$\arg \min _{\theta_{2},\mathcal{T}_{\mathbf{S}}}||\mathcal{T}_{\mathbf{L}} - f_{2_{\theta_2}}(\mathcal{T}_{\mathbf{L}}))||_2 + \lambda_2||\mathcal{T}_\mathbf{S}||_1 \ s.t. \ \mathcal{T}=\mathcal{T}_{\mathbf{L}}+\mathcal{T}_{\mathbf{S}}.$$

综上所述，RDAE模型的收敛过程需要共同优化以上三个子目标函数。

离群点分数 $\mathcal{OS}$计算过程与RAE算法相同，即：

$$\mathcal{OS}=<||\mathcal{S}_{\mathcal{s}_1}||_2^2, ||\mathcal{S}_{\mathcal{s}_2}||_2^2, ..., ||\mathcal{S}_{\mathcal{s}_C}||_2^2>$$

RDAE算法的细节如图7所示：

图7. RDAE算法细节

RDAE算法有四个超参数 $B$， $\lambda_1$， $\lambda_2$和 $\epsilon$，分别为滞后矩阵 $\mathbf{M}$的高度，两个正则化参数和离群分数 $\mathcal{OS}$的阈值。
首先随机化参数起始值，然后固定 $\theta_2$，和 $\theta_{AE}$，更新 $\theta_1$一次。然后固定 $\theta_1$， $\theta_2$，迭代更新 $\theta_{AE}$。待 $\theta_{AE}$收敛，停止条件是满足两个条件其中之一，其原理与RAE相同。 $condition_1$的满足条件是 $\hat{\mathbf{M}}=\mathbf{L}+\mathbf{S}$。 $condition_2$的满足条件是 ${\mathbf{L}}$和 $\mathbf{S}$不再变化。
最后固定 $\theta_1$和 $\theta_{AE}$，迭代更新 $\theta_2$，待 $\theta_2$收敛，停止条件需要满足两个条件的其中之一，其原理与RAE相同。 $condition_1$的满足条件是 $\mathcal{T}=\mathcal{T}_{\mathbf{L}}+{\mathcal{T}_{\mathbf{S}}}$。 $condition_2$的满足条件是 ${\mathcal{T}_\mathbf{L}}$和 ${\mathcal{T}_{\mathbf{S}}}$不再变化。

4. 可解释性

---

模型的可解释性指模型的输出是否易于人类理解并接受。图8介绍了何为可解释性：

图8. 可解释性介绍

图8a中的蓝色曲线为输入的时间序列，红色点为离群点。图8b的模型展示了同事具备高准确率和可解释性的模型。图8c展示了高准确率但是不具备可解释性的模型。图8d展示了具备可解释性但是低准确率的模型。可解释性高的模型输出的洁净时间序列具有比较简单的解析形式，即具备简单的且可以被人类理解的函数形式。

本文提出了两种post-hoc量化可解释性方法，PRM-based Explainability Scores和SSA-based Explainability Scores。提出的方法可以量化不同的基于自编码器的离群点检测算法的可解释性。我们会依次介绍这两种方法。

PRM-based Explainability Scores

该方法的思想是将拟合的洁净时间序列与N阶多项式求解平方根均方误差（RMSE），设定阈值 $\gamma$，若RMSE小于该阈值，则认为洁净时间序列觉有N阶多项式序列可解释性。求解模型输出可以满足要求的最小N。当N越小，则认为模型的输出更具有可解释性。其公式如下：

$$\varepsilon s_{PRM}=min\{N \in \mathbb{N}|RMSE(\mathcal{T}_{\mathbf{L}},\mathcal{T}_{\mathbf{PRM}}^{(N)})<\gamma\}$$

其中PRM代表多项式回归模型， $\varepsilon s_{PRM}$代表可解释性分数， $\mathcal{T}_{\mathbf{PRM}}^{(N)}$代表N阶多项式回归模型输出的时间序列。

SSA-based Explainability Scores

该方法的思想是将拟合的洁净时间序列与包含N个组件的SSA算法输出求解平方根均方误差（RMSE），SSA算法可将时间序列分解成N个具有趋势性和周期性的时间序列的线性组合。设定阈值 $\gamma$，若RMSE小于该阈值，则认为洁净时间序列觉有包含N个组件的SSA可解释性。求解模型输出可以满足要求的最小N。当N越小，则认为模型的输出更具有可解释性。其公式如下：

$$\varepsilon s_{SSA}=min\{N \in \mathbb{N}|RMSE(\mathcal{T}_{\mathbf{L}},\mathcal{T}_{\mathbf{SSA}}^{(N)})<\gamma\}$$

$\varepsilon s_{SSA}$代表可解释性分数， $\mathcal{T}_{\mathbf{SSA}}^{(N)}$代表包含N个组件的SSA输出时间序列。

5. 实验

---

本文选取了七个时间序列数据集GD，HSS，ECG，NAB，S5，2D，SYN，并选取了15个现有的离群点检测方法作为baseline。

实验结果 本文在七个数据集上分别做了对比实验，用ROC和PR作为比较手段，总体实验结果如图9所示：

图9. 实验结果

实验表明，RAE和RDAE在绝大多数情况下取得了最优表现。

此外，本文还完成了参数学习的研究，结果如图10所示：



图10. 参数学习

我们对模型的五个模块进行了消融实验，实验证明每个模块都发挥了作用，结果如图11所示：

图11. 消融实验

最后本文还测试了算法运行时间的对比，实验表明本文提出的方法在兼具鲁棒性和可解释性的同时运行时间也有一定的优势。结果如图12所示：

图12. 运行时间实验

6. 结论

---

本文提出了两个用于无监督的具备可解释性和鲁棒性时间序列离群点检测的自动编码器框架。这些框架首次尝试改善现有的基于神经网络的自动编码器的两个不足：低可解释性和对离群值的高脆弱性。RAE和RDAE将一个时间序列分解为一个洁净时间序列和一个离群时间序列，并使它们对离群值具有鲁棒性和可解释性。我们提供了一种post-hoc可解释性分析方法来量化模型的可解释性。实验研究表明本模型超过了最先进的方法。

华为云数据库创新lab官网：https://www.huaweicloud.com/lab/clouddb/home.html