时间序列数据预处理的维度简约文献研究

钱国军

【摘 要】时间序列数据是现实数据库中最重要的数据类型之一，由于其具有数据量大、维度高和连续更新的特点，直接对时间序列数据进行数据挖掘非常困难，必须在数据预处理阶段对原时间序列进行维度简约，提高数据挖掘可操作性。文章对现有时间序列维度简约技术进行了汇总比较，为研究者进一步探索和挖掘时间序列数据提供参考。

【关键词】时间序列 数据挖掘 维度简约

【中图分类号】TP311.13【文献标识码】A【文章编号】1672-5158（2013）02-0067-01

现实中大量数据都是按时间顺序保存在数据库中，如金融市场的股票数据，数据量之大致使传统的时间序列分析效果甚微，大量包含有用信息的历史数据只能束之高阁。近几十年来，数据挖掘技术迅速发展，数据分析逐渐从单纯的统计分析向和计算机技术紧密联系的数据挖掘方向发展。数据挖掘通过各种算法让计算机在人的控制下探索海量数据，发现其中人所感兴趣的信息。时间序列数据是数据挖掘的重要方面，直接对原始进行数据处理是无法发现有用信息，一种可行的办法就是对原始数据进行特征提取，这一方面降低了数据维度，另一方面也消除了噪音。本文将着重介绍各种时间序列数据挖掘特征提取技术。

时间序列维度简约中最简单的方法可能是采样。然而，如果采样率很低，采样方法的缺点是扭曲了被采样时间序列的形状。一个提高的方法是使用每个分割的平均值带便相应的数据点集合。这种方法也称为分段聚集近似。Keogh提出一个扩展版本自适应分段常数近似，每个分割的长度不是固定的，而是是适用于序列的现状。Lee提出使用分割的总变异（SSV）表示时间序列的每个分割。

使用直线近似时间序列是一种重要方法，主要分为两类：线性插值和线性回归。第一类是线性插值。一个普遍的方法是使用分段线性表示PLR。PLR是一种自底向上的算法，此方法往往连接连续分割的末端，用衔接的直线来分段近似。反复合并代价最低的分割对，直到达到需要的分割数量。Ge把PLR扩展到分层结构。Keogh和Pazzani通过考虑分割的权重和来自使用者的信息反馈完善了PLR。第二种方法是线性回归，使用最优拟合直线代表子序列。

此外，保留显著点降低维度一种有效的方法。这些点称为感知重要点PIP。Chung首先引入了PIP识别过程，并适用于金融应用的技术模式的模式匹配。时间序列P有n个数据点， P中所有数据点在整个PIP识别过程中按其重要性排序，再按顺序识别，这种PIP定位过程直到达到要求的PIP数量。

这一思想和30年前Douglas and Peucker减少要求的数据点来代表直线的技术相似，他使用了路标模型识别时间序列中的重要点。Man和Wang提出晶格结构来表示时间序列中的识别的顶点和谷点。Pratt、Fink和Finketal定义了时间序列中如极大极小的极值，通过选择仅仅每个重要的极值点丢弃其他点压缩时间序列。这一算法也能处理新来的数据点，他根据时间序列分割的局部信息识别重要点，不需要储存原先的序列。目前，金融数据分析提出了关键点模型和基于关键点序列的高度表示方法。关键点表示时间序列适用于于奇异值识别。

另一类普遍的时间序列表示方法是把数值时间序列转化为符号形式。首先把时间序列离散化为分割片段，然后把每个分割转换为一个符号。Lin提出一种称为符号聚集近似的方法SAX，把PAA的结果转换为符号串。Jonsson 和Badal使用“形状描述字符SDA”。Qu采用梯度字母如向上、平坦和向下作为符号。Huang 和yu提出使用相邻数据点的变化量来把时间序列转换为符号串。

Megalooikonomou提出使用来自关键序列的码本的码字来表示每个划分。Megalooikononou考虑多路解决扩展了这一方法。Morchen和Ultsch提出了基于质量得分和持续状态的无监督离散处理。这一算法不是像很多其他方法忽略数据的时态顺序，而是包括了时态信息。

此外，子序列聚类是一种产生符号的普遍方法。Li提出是基于时间序列的符号形式多抽象层挖掘方法MALM。

目前为止介绍的大部分方法是在时间域内直接表示时间序列。在另一个域内表示时间序列是另一大类方法。一个流行的时间序列转换技术是傅里叶转换DFT，它首先由Agrawal在这一领域使用。Rafiei 和Mendelzon使用DFT开发了基于相似性查询。Janacek提出使用似然比统计量检验序列间不同的假设，而不是使用转换域的欧几里得距离。目前研究使用小波转换来表示时间序列。离散的小波转换DWT已认为是替代DFT的有效方法，哈尔变换最为流行。哈尔变换是一系列对时间序列的平均和差分操作。Shahabi提出多层次小波转换表示。Popivanov 和Miller表明大部分小波转换的可用于时间序列表示。Dasha比较了不同小波特征向量。Wu和Morchen对DFT和DWT之间优缺点的进行了比较。Kawagoe和Ueda提出了傅里叶和小波转换的联合使用。Keogh 和Vlachos提出的整合了两种和两种以上的表示方法整体索引。

主成分分析PCA是一种用于多元统计处理监督方法的流行多元技术，并应用于金融时间序列。在大部分相关研究中，PCA用于消除不显著的成分或传感器，减少数据表示只表示最为显著的数据点，把数据点画在两维空间。PCA定义了线性超平面，可以认为是PLR的多元扩展。PCA把多元数据映射到地位空间，在相关高位数据的分析和可视化中很有用。奇异值分解SVD是另一种基于转换的方法。

其他时间序列表示方法包括使用隐藏的马克鲁夫模型模拟时间序列. Deligiannakis提出了多元数据流的压缩技术，他是基于信号的，这信号给相关数据值的分段线性相关性编码。

以上介绍的许多表示方法和不同的索引方法想结合的。对于现存的多维索引结构的表示适用于普遍的表示方法方法。Agrawal提出了F-索引，他采用R*树索引第一少数DFT系数。Faloutsos进一步提出了ST-索引，这扩张了先前子序列处理的研究。Agrawal采用了R*和R+树作为索引结构。Vlachos提出多矩阵树，这是对欧几里得和间歇空间的混合索引结构。最小边界矩形MBR也是一种普遍的时间序列索引技术。Rafiei采用了MBR，发展了基于傅里叶转黄的MT-索引，Kahveci 和Singh 提出了基于小波转换的多路解决索引。Chen提出对PLR表示的索引机制。另一方面，Kim提出针对控制时间序列模式数据库的TIP-索引。EMDF Kim通过改善扩展的多维动态索引发展TIP-索引。iSAX是基于SAX的大量时间序列索引。Li提出多分辨率索引结构，适用于不同的表示。

总之，对于给定的索引结构，索引的有效性仅取决于维度简约空间的近似准确性。然而在选择维度简约技术时，我们不能简单选择任意一种压缩算法。需要能产生能索引的表示的技术。例如，很多时间序列可以通过delta编码有效的压缩，但之中表示不能使他自己能索引。相反，SVD、DFT、DWT和PAA傅里叶系数、小波系数或者聚集划分映射到索引树的一维中，能是容易得到索引。