一文讲透时序和序列数据的存储、搜索、分析及挖掘

在算法实践中，快速掌握时序数据的特征，估算出长期趋势、重复变化和循环变化的规律，将具有非常重要的意义。原因是它有助于选择合适的方法去做分析，并且有助于全面理解数据。通过对趋势、循环、季节和非规则成分的运动的系统分析，使人们可以在较合理的情况下，制定出长期或短期的预测（即预报时序）。

如何进行趋势分析

用于特化时序数据的四种主要变化成分：

01 长期或趋势变化

trend movement，它用于反映一般变化方向，其时序图是在较长时间间隔上的数据变化。这种变化反映为一种趋势曲线，或趋势线。确定趋势曲线或趋势线的典型方法包括加权移动平均方法和最小二乘法，详见下面的讨论。

02 循环运动或循环变化

cyclic movement or cyclic variations，主要指循环性，即趋势线或曲线在长期时间内呈摆动迹象，它可以是也可以不是周期性的。即在等时间间隔之间，循环不需要沿着同样的模式演进。

03 季节性运动或季节性变化

seasonal movements or seasonal variations，它反映的是每年都重复出现的事件，如情人节前巧克力和鲜花会的销量突然上升，或在圣诞节节前储藏商品的销售会突然增加。换句话说，季节性运动是指同一或近似同一的模式，在连续几年的有关月份期间重复出现。

04 非规则或随机变化

irregular or random movements，它反映的是随机或偶然事件零星时序变化，如劳工需求，洪水，或企业内发生的人事变动等。

以上有关趋势的，循环的，重复的，和非规则的运动，可以分别用变量 T，C，S，I 表示。时序分析也可以指将时序分解为以上四个基本运动的分析。时序变量丫可以表示为四个变量的积(即Y=T%C%S%I)，或四变量之和。其选择通常是凭经验的。“对Y给定一组值(即，1,2,3....，如何确定数据的趋势?”确定趋势的常见方法是按算术平均式序列，计算 n 阶的移动平均值 (a moving average of order n)。

趋势分析的方法

01 趋势分析常见方法：移动平均

采用适当的阶数的加权移动平均，可以消除数据中的循环，重复和非规则的模式，而只保留趋势变化。移动平均可以降低数据集中的变化总量。

因此用移动平均替代时序，可以减少不希望出现的波动，故它也称为平滑的时序(smoothing of time series)。移动平均会丢失系列中的头尾数据，由此有时会生成在原始数据中不会出现的循环或其它变化趋势，并且它可能受一些极端数据的影响。对极端数据的影响，可通过采用适当权重的加权移动平均的方法降低其负面影响。

02 其他计算趋势的方法

其中之一是所谓的徒手法(free-hand method),它是基于用户的判断画一根近似曲线或直线去吻合一组数据。这一方法代价很大，且只对大规模数据挖掘可靠。另一种是最小二乘法,其中以最吻合的曲线 C 作为最小二乘曲线,即曲线具有最小值，其中 d;的偏差或误差是指点 (x,y) 的值y: 与对应曲线 C 的值之间的差值。

03 对循环运动及季节性波动的调整方法

在许多商业交易中，存在预期的季节性波动，如圣诞节期间的旺销。因此，对趋势和循环数据分析，很重要的一点是识别此类重复性变化，并对数据“反季节化 (deseasonalize)”。

为此，引入季节指数 (seasonal index)的概念，用一组数字表示·年中某些月份某变量的相关值。例如，如十月，一一月，十二月的销售分别是全年平均月销量的80%，120%，140%，那么 80，120，140 就是本年度的季节指数。若原始的每月数据由对应的季节指数去除，其结果数据被称为是反季节化的，或者是对季节变量调整过的。反季节化数据可以针对趋势做进一步的调整，即按对应的趋势值去除这些数据。而且，合适的移动平均可以平滑掉的非规则的变化，而只剩下循环变化做进一步的分析。

如果循环呈现周期或近似周期，则可以按引入季节性指数的同样方法引入循环指数 (cyclic index)。

04 其他

最后，非规则或随机变化可以通过针对趋势，季节和循环变化的数据调整，加以估计。一般地,小偏差出现的频率高，大偏差出现的频率低，遵从正态分布。推荐关注@公众号：数据STUDIO 更多优质好文~

时序分析的技术基础

01 什么是时序数据库？

什么是序列 (sequence) 数据库?时序数据库是指有随时间变化的值或时间组成的数据库。值通常是在等时间间隔测得的数据。很多应用中时序数据库很普遍，如股票市场的每日波动，动态产品加工过程，科学实验，医学治疗，等等。

时序数据库也是种序列数据库。然而序列数据库是指中有序事件序列组成的数据库，它可以有时间标记，也可以没有。例如，Web 页面遍历序列是一种序列数据，但可能不是时序数据。本节将介绍时序数据库和序列数据库的挖掘的几种重要内容，包括趋势分析，相似搜索，序列模式挖掘和与时间有关数据的周期模式挖掘。

02 什么是相似搜索？

通常数据库查询是要找出符合查询的精确数据，相似搜索与之不同，它是找出与给定查询序列最接近的数据序列。子序列匹配(subsequence matching.是找出与给定序列相似的所有数据序列，而整体序列匹配 (whole sequence matching)是找出彼此间相似的序列。对金融市场的分析(如股票数据分析)，医疗诊断(如心电图分析)，和科学与工程数据库(如能量消耗分析) 等，时序分析中的相似搜索大有用武之地。

03 数据变换：从时间域到频率域

疑问一：为什么需要变换数据?

许多信号分析的技术需要数据来自频率域。因此，有关距离的正交变换经常用于从时间域到频率域的数据变换。通常，使用独立于数据的变换，其变换矩阵是预先确定的，与输入数据无关。两个常见的独立于数据的变换是离散傅立叶变换 (DFT) 和离散小波变换(DWT)29。由于在时间域中两个信号的距离与频率域中欧氏距离类似，所以 DTF 可以出色发挥，在头系数 (first few coeficients) 表现突出。通过仅保持 DFT 的头几个 (即,“最强的”) 系数,我们可以计算出实际距离的下限。

疑问二：一旦数据经过变换，比如 DFT，如何进行相似搜索?

为提高访问效率，可以用头几个傅立叶系数构造一个多维索引。当相似查询提交给系统，可以利用索引检索出与查询序列保持一定最小距离的序列。通过计算时间域序列和未满足查询的序列间的实际距离，可以进行必要的后处理postprocessing)。

疑问三：子序列匹配如何进行?

对子序列匹配，每一序列首先被分割为长度为的窗口“片段”每个序列影射为特征空间的中一个“线索 (trail)”。对子序列分析，把每个序列的线索划分为“子线索(subtrail)”，每一个由最小边界矩形表示。利用多片组装算法 (multipiece assembly algorithm)可以搜索更长的匹配序列。

04 增强相似搜索方法，处理偏移和振幅中的间隙和差异

大部分实际应用并不一定要求匹配的子序列在时间轴上完全一致。换句话说，若子序列对具有同样的形状，但在序列内存在间隙或在偏移或振幅 (offsets or amplitudes) 中存在差异，我们也可以认为它们是匹配的。这在许多相似序列分析中尤为有用，如股票市场的分析和心电图分析。

疑问一：如何改进相似搜索，使其能够在存在这种差异的情况下仍能判断其相似性?

一种改进的相似模型，是允许用户或专家说明一些参数，如滑动窗口(sliding window)尺寸，相似范围的宽度，最大间隙，匹配片段(matching ffaction)，等等。如图 9.7，给出了两人时间序列，其中的间隙被移去，结果序列按偏移转移和振幅调整加以规范处理，使得振幅和偏移量不同的序列得以匹配。

当一个子字列与另一个子序列处于某一宽度e的范围内(其中e是一个小的数字，可由用户或专家指定)，这两人子序列是相似和可匹配。两序列是相似的，当它们之间存在足够多的非重叠的符合时间次序的相似子序列对。

疑问二：处理存在间隙和偏移与振幅差异的相似搜索的执行步骤？

原子匹配(atomic matching): 找出所有无间隙的较小相同窗口对。
窗口结合(window stitching): 把相同窗口结合，形成大的相似子序列对，其中允许在原子几配间有间隙。
子序列排序(subsequence ordering): 线性排列子序列匹配，以判定是否存在足够大的相似片段。通过以上的处理步骤，可以求得形状相似但有间隙或在偏移或振幅中有差异的相似序列。

05 相似搜索的索引方法

“是否存在高效的实现方法?”为在大型数据库中改进相似搜索的效率，人们提出了各种了索引的方法。例如，R-树，R*-树用于存储最小边界矩形以加速相似搜索。另外，提出了ekdB 树用于在高维点上提高空间相似连接的速度，还提出了后缀树 ( suix tree) 等。

序列模式挖掘

序列模式挖掘 (seuence pattern mining) 是指挖掘相对时间或其它模式出现频率高的模式。一个序列模式的例子是“九个月以前购买奔腾 PC 的客户很可能在一个月内订购新的 CPU 芯片”。由于很多商业交易，电传记录，天气数据，和产品处理都是时间序列数据.在针对目标市场，客户吸引，气象预报等的数据分析中，序列模式挖掘是很有用途的。推荐关注@公众号：数据STUDIO 更多优质好文~

01 序列模式挖掘的情形和参数

许多有关序列模式挖掘的研究主要针对符号模式(svmbolic pattern)，因为数字曲线模式通常属于统计时序分析中的趋势分析和预测范畴。

对序列模式挖掘，存在一些参数，其取值如何，将严重影响挖掘结果。第一个参数是时间序列的持续时间 (duration)T。

第二个参数是事件重叠窗口 (event folding window)w。

第三个参数是被发现的模式中时间之间的时间间隔 (interval) int。此参数可取如下的值：int-0：表示没有时间间隔。

02 序列模式挖掘的方法

关联规则挖掘中采用的 Apriori 特性可以用于序列模式的挖掘，因为若长度为 k 的序列模式是非频繁的,其超集(长度为 k+1)不可能是频繁的。因此,序列模式挖掘的大部分方法都采用了类 Apriori算法的变种，虽然所考虑的参数设置和约束都有所不同。另一种挖掘此类模式的方法是基于数据库投影的序列模式生长(database project based sequential pattern growth)技术，类似无候选的频繁模式挖掘(frequent patter)方法，频繁模式增长法 (FP-growth)。

周期分析

是指对周期模式的挖掘，即在时序数据库中找出重复出现的模式。周期模式可以应用于许多重要的领域。例如季节，潮汐，行星轨道，每日能源消耗，每日交通模式，和每周特定时间的所有 TV 节目。如前一节所指出的，周期模式挖掘可视为以一组分片序列为持续时间的序列模式挖掘，如每年某事件出现前后的每一位置等等。

01 周期模式挖掘的问题可分为三类

挖掘全周期模式(full periodic pattern)：这里每一时间点都影响着(精确或近似)时序上的循环行为。如一年中的每一天都对一年中的季节循环起着作用。

挖掘部分周期模式(partial periodic pattern)：它描述在部分时间点的时序周期。例如，Sand在平日的早晨 7: 00 至7:30 阅读纽约时报，但在其它时间则没有什么规律。部分周期是一种比全周期较为松散的形式，在现实世界也更为常见一些。

挖掘循环或周期关联规则(cyclic or periodic association rule)：这种规则是周期出现的事件的关联规则。周期关联规则的一个例子是“基于每天的营业记录，若周末下午茶在 3:00-5: 00pm,则晚餐最佳营业时闻为 7: 00-9: 00。

全周期分析的技术已在信号分析和统计中得到研究。如 FFT(快速傅立叶变换) 方法已广泛用于时间域到频率域的数据转换，以便于此类分析。

02 全周期模式挖掘方法可否用于部分周期模式挖掘？

高效的部分周期模式挖掘已在最近的数据挖掘中研究中得到重视。全周期模式挖掘的大部分方法相对于部分周期模式挖掘或者不适用，或者代价太大，原因是部分周期模式在同一周期内混杂有周期事件和非周期事件。

例如，FFT 不能用于部分周期挖掘，因为它把时序看作不可分离的数据流。一些周期探测方法不能覆盖部分周期模式,除非部分模式的的周期，长度，和选时 (timing)是明确说明的。以新闻阅读为例，我们需要明确说明诸如“以24 小时为一周期，找出 Sandv 在 7: 00 以后半小时内的有规律的活动”。把此类方法简单适用于部分周期模式的挖掘问题是不足取的，因为它需要处理的是周期，长度，和选时的大量组合。

有关部分周期模式和循环关联规则挖掘的大部分研究都应用了 Apriori 特性启发式和采用了变通的Apriori挖掘方法。在序列模式和周期模式挖掘中可以引入约束。Apriori特性,各种改进的 Apriori算法，以及约束挖掘(mining constraint) 的使用。

END

来源：数据STUDIO；