顶会VLDB‘22论文解读：CAE-ENSEMBLE算法

顶会VLDB‘22论文解读：CAE-ENSEMBLE算法 - 华为云开发者社区的个人空间 - OSCHINA - 中文开源技术交流社区

摘要：针对时间序列离群点检测问题，提出了基于CNN-AutoEncoder和集成学习的CAE-ENSEMBLE深度神经网络算法，并通过大量的实验证明CAE-ENSEMBLE算法能有效提高时间序列离群点检测的准确度与效率。

本文分享自华为云社区《VLDB'22 CAE-ENSEMBLE论文解读》，作者：云数据库创新Lab。

本文（Unsupervised Time Series Outlier Detection with Diversity-Driven Convolutional Ensembles）是由华为云数据库创新Lab联合丹麦Aalborg University与电子科技大学发表在顶会VLDB’22的文章。该文章针对时间序列离群点检测问题，提出了基于CNN-AutoEncoder和集成学习的CAE-ENSEMBLE深度神经网络算法，并通过大量的实验证明CAE-ENSEMBLE算法能有效提高时间序列离群点检测的准确度与效率。VLDB是CCF推荐的A类国际学术会议，是数据库和数据挖掘领域顶级学术会议之一。

随着交通、医疗和金融等方面的全面数字化，大量的传感器被布置在我们生活的环境中，产生了各种各样的时间序列数据，随即催生出大量新的应用。本文研究时间序列的离群点检测问题，尽管过去有很多相关的研究，现有的离群点检测方法在算法的准确性与效率方面还是存在不足。本文针对这些问题提出了相应的解决方法，主要贡献如下：

提出了CAE-ENSEMBLE算法，本算法包括基于CNN的自编码器和多样性驱动的集成学习方法，其中基于CNN的自编码器用于对时间序列的时间依赖进行高效建模，多样性驱动的集成学习方法进一步提升了算法的准确性。
本文提出了一种无监督的超参数选择方法，减少了对昂贵标签数据的依赖。
CAE-ENSEMBLE算法的表现在真实的时间序列数据集上击败了现有的方法。

时间序列离群点检测 给定一个长度为CC的时间序列\mathcal{T}=<s_1, s_2, ..., s_C>T=<s1,s2,...,sC>，即在第tt时刻的观测值为s_tst。离群点检测的目标在于给每个观测值s_tst计算一个离群点分数\mathcal{OS}(s_t)OS(st)，这个离群点分数越大，这个观测值越可能是离群点。比如可以根据领域知识预先设定一个阈值\epsilonϵ，那么如果\mathcal{OS}(s_t)>\epsilonOS(st)>ϵ, s_tst就被认为是离群点。

由于自动编码器属于无监督模型，且对时间序列数据具有强大的学习能力，本文采用自动编码器作为基本模型，用于时间序列离群点检测。具体来说，我们首先将原始时间序列\mathcal{T}T输入到编码器中进行表示学习，然后将学习到的表示输入到解码器中进行复原，得到重建的时间序列\hat{\mathcal{T}}T^，最后计算重建差异（reconstruction error），即\mathcal{T}T与\hat{\mathcal{T}}T^之间的差异，作为离群点分数。

如下图中时刻3的观测值的重建差异很大，它就很有可能是一个离群点。

自动编码器 自动编码器由一个编码器（Encoder）和解码器（Decoder）组成，给定输入X = [x_1, x_2, ..., x_C]X=[x1,x2,...,xC]，则相对应的自动编码器输出为\hat{X} = [\hat{x}_1, \hat{x}_2, ..., \hat{x}_C]X^=[x^1,x^2,...,x^C]，用于离群点检测的自动编码器目标函数为：

其中\theta_{AE}θAE代表自动编码器的参数。我们将重建损失RE定义为||x_i - \hat{x}_i||^2∣∣xi−x^i∣∣2，若重建损失RE超过设定好的阈值\epsilonϵ，则代表这个点为离群点。

本文提及了6种编码器：普通自动编码器AE（由全连接层组成）、基于RNN的自动编码器RAE、基于CNN的自动编码器、集成的普通自动编码器AE-Ensemble、集成的基于RNN的自动编码器RAE-Ensemble、集成的基于CNN的自动编码器CAE-Ensemble。这六种编码器在建模时间依赖、效率和多样性方面的区别如下图所示。

3. CAE-ENSEMBLE算法设计

CAE-ENSEMBLE算法设计如下图所示，包含数据预处理、集成的CAE模型和无监督超参选择三部分，我们将从这三部分分别介绍本模型。

A. 数据预处理

数据预处理的目的在于将原始的时间序列数据处理为时间序列窗口数据，并用于模型训练和测试。防止减少不同特征对最后重构损失RE的影响，我们首先将原始数据进行标准化，公式如下：

其中\muμ与\sigmaσ分别是训练集中观测值xx的均值和标准差。

将数据标准化后，设定滑动窗口大小为ww，然后对当前的时间序列观测数据进行滑动窗口，若原始时间序列为\mathcal{T}=<s_1, s_2, ..., s_C>T=<s1,s2,...,sC>，则第一个窗口为<s_1, s_2, ..., s_w><s1,s2,...,sw>，第二个窗口为<s_2, s_3, ..., s_{w+1}><s2,s3,...,sw+1>。

B. 集成的CAE模型CAE-ENSEMBLE

在本节中，首先，我们将介绍如何用基于CNN的自动编码器对时间序列数据进行建模，然后介绍多样性驱动的集成方法构建CAE-ENSEMBLE模型。

(1). 基于CNN的自动编码器（Convolutional Sequence-to-Sequence Autoencoder CAE）

本文采用基于CNN的自动编码器CAE作为集成学习的基础模型，并对时间序列进行建模，CAE结合了卷积神经网络CNN与Seq2Seq模型，结构如下图所示。首先，我们将一个滑动窗口的时间序列数据输入到由一维卷积组成的编码器中学习数据的时间依赖，然后将同样的数据和编码器学到的隐藏表示一起输入到由一维卷积组成的解码器中进行特征学习，最后利用注意力机制组合编码器和解码器学习到的特征，并用于重构时间序列。

在数据输入阶段，我们首先对原始滑动窗口数据进行特征嵌入，包含位置与观测嵌入两种方法，具体实现如下图所示。

在编码阶段，编码器采用堆叠的卷积层学习时间序列的时序特征，下图给出了一个由三层卷积网络组成的编码器示例。

解码器与编码器类似，但存在轻微的不同，我们利用padding的方式确保在tt时刻的输入不晚于tt，下图给出了一个由三层卷积网络组成的解码器示例。

然后，利用注意力机制学习局部的时间依赖，注意力机制公式如下。

最终，对解码器最后一层网络生成的隐藏特征，利用全连接层进行重构，公式如下：

其中，D^{(L+1)}D(L+1)代表解码器最后一层学习到的隐藏特征。

(2). 多样性驱动的集成方法（Diversity-driven Ensembles）

为了解决现有方法准确度低和训练成本高的问题，我们将CAE作为基础模型，提出了一个新颖的多样性驱动的集成方法CAE-ENSEMBLE，如下图所示。与传统方法不同的是，我们一个一个的生成基础模型，而不是采取分别生成的方式。同时，我们还设计了一个用于保证模型多样性的目标函数，防止模型过于相似，以提高准确度。同时，我们在训练模型时，将一部分前一个模型的参数迁移到当前训练的基本模型中，这个操作可以显著地减少训练时间，提升效率。

目标函数 CAE-ENSEMBLE目标函数包含两部分：重构损失\mathcal{J}_{f_m}Jfm和模型的多样度损失\mathcal{K}_{f_m}Kfm，公式如下。

离群点分数计算 为了防止过拟合，我们采用多个模型计算出来的离群点分数\mathcal{OS}(x_t)OS(xt)的中位数作为最终的离群点分数。

其中MM代表基础模型的个数。

C. 无监督超参选择

本文有三个重要的超参：滑动窗口大小ww，参数转移比例\betaβ，平衡参数\lambdaλ，由于我们的方法是无监督的，首先，我们将划分无标签的训练集和验证集，然后我们为这三个参数设定一个范围，然后利用随机搜索，通过最小化重构损失确定一个最优的超参组合，，其中利用重构损失可以使得我们的算法不需要标签，达到无监督的作用。同时，在寻找某个参数的最优值的过程中，我们会将另外两个参数固定在默认值。具体算法如下图所示。