数据挖掘原理、-算法及应用第6章-时间序列数据挖掘-PPT课件

《数据挖掘原理、-算法及应用第6章-时间序列数据挖掘-PPT课件》由会员分享，可在线阅读，更多相关《数据挖掘原理、-算法及应用第6章-时间序列数据挖掘-PPT课件（90页珍藏版）》请在金锄头文库上搜索。

1、第第6章时间序列数据挖掘章时间序列数据挖掘第第6章时间序列数据挖掘章时间序列数据挖掘6.1概述6.2时间序列数据建模6.3时间序列预测6.4时间序列数据库相似搜索6.5从时间序列数据中发现感兴趣模式 第第6章时间序列数据挖掘章时间序列数据挖掘6.1概述概述 时间序列是一种重要的高维数据类型， 它是由客观对象的某个物理量在不同时间点的采样值按照时间先后次序排列而组成的序列， 在经济管理以及工程邻域具有广泛应用。 例如证券市场中股票的交易价格与交易量、 外汇市场上的汇率、 期货和黄金的交易价格以及各种类型的指数，这些数据都形成一个持续不断的时间序列。 利用时间序列数据挖掘， 可以获得数据中蕴含的与

2、时间有关的有用信息， 实现知识的提取。第第6章时间序列数据挖掘章时间序列数据挖掘时间序列数据本身具备有高维性、 复杂性、 动态性、 高噪声特性以及容易达到大规模的特性，因此时间序列数据挖掘是数据挖挖中最具有挑战性的十大研究方向之一。 目前的重点研究内容包括时间序列的模式表示、 时间序列的相似性度量和查询、 时间序列的聚类、 时间序列的异常检测、 时间序列的分类、 时间序列的预测等。第第6章时间序列数据挖掘章时间序列数据挖掘6.2时间序列数据建模时间序列数据建模 对于一个时间序列yt，t=1， 2， ，n，通常所建立的回归模型都假定yt在整个时间范围内具有相同的变化模式， 这在许多情况下是适宜的

3、。 但在实际中也确实存在着很多这样的时间序列，它在整个时间序列里明显地具有两种或两种以上的变化模式，对这样的时间序列如果仍在整个时间序列里建立回归模式(即假定它们在整个时间范围里服从同一变化模式)，就明显的不太适合，效果也就不会太好。 对这样的时间序列要采取非常规的建模方法，反映出它在不同时间范围里的不同变化。 第第6章时间序列数据挖掘章时间序列数据挖掘在实际中，具有不同变化规律的时间序列建立模型的方法有很多， 较常用的有虚拟变量法，段拟合法、 样条函数法和门限模型法四种， 下面我们就来介绍和讨论这四种方法。为简单起见，我们假定时间序列yt(t=1， 2， ，n)在整个时间范围里具有两种不同的

4、变化规律(具有多种变化规律时处理方法类似)，分界点或转折点是k，即当t=1， 2， ，k时，yt按某一模式变化，而当t=k+1， k+2， ，n时，yt按另一模式变化。 这里，分界点或转折点k常可通过观察分析y的散点图或曲线图来确定。 第第6章时间序列数据挖掘章时间序列数据挖掘1. 虚拟变量法虚拟变量法虚拟变量法就是设置一个在转折点前后具有不同特征的虚拟变量Dt，在对yt建立回归建模时引进Dt, 从而通过Dt来反映yt的不同变化规律。 虚拟变量Dt最常用的形式是： (6.1) 第第6章时间序列数据挖掘章时间序列数据挖掘这样以t和Dt为自变量和解释变量，yt为因变量和解释变量，即可建立起回归模型

5、。通常是建立起如下最常用的线性回归模型、 指数回归模型或自回归模型： (6.2) (6.3) (6.4) 第第6章时间序列数据挖掘章时间序列数据挖掘2. 分段拟合法分段拟合法既然yt在前后两个时间段里具有不同的变化规律， 那么一个很自然的做法就是在这两个时间段里对yt分别建立回归模型， 并且一般来说， 这两个在不同时间段里具有不同变化规律的数据所建立的回归模型是不同的， 因此可以反映出yt的转折性变化。 这种方法就是分段拟合法。第第6章时间序列数据挖掘章时间序列数据挖掘分段拟合时， 两个时间段的拟合模式或回归函数类型可以是一样的， 也可以是不一样的， 因此分段拟合结果为(6.5) 这里, f1

6、和f2一般可取为时间t的线性函数、多项式函数或指数函数，有时也可取为yt的滞后值yt-1、yt-2等的线性函数或这几种函数的混合函数。 第第6章时间序列数据挖掘章时间序列数据挖掘3. 样条函数法样条函数法上述两种方法对yt建立的回归模型在t=k处一般是不连续的，例如对模型(6.2)式， 在t=k处的左极限(即当t从小于k处或k的左边趋于k时的极限)为 (6.6) 而 在t=k处的右极限(即当t从大于k处或k的右边趋于k时的极限)为：(6.7) 第第6章时间序列数据挖掘章时间序列数据挖掘由于b0， 因此(6.6)式和(6.7)式不相等， 即在t=k处不连续。 这种不连续性一般是和实际相背的， 对

7、于社会经济现象中的数据更是如此。因此上述两种方法的拟合效果一般来说也不会很令人满意。而样条函数法正是对这一缺陷的一种补救方法，它是在多项式分段拟合(对其他函数形式也可如此处理，只是稍复杂而且也不常用)的基础上加上分段多项式在转折点t=k处的连续性和可微性的条件而形成的。下面我们给出实际中常用的几种样条函数拟合模型的形式，它们的具体推导就不在此详述了。一次、 二次、 三次样条函数拟合模型分别为第第6章时间序列数据挖掘章时间序列数据挖掘(6.8) (6.9) (6.10) 第第6章时间序列数据挖掘章时间序列数据挖掘如果引入(6.1)式中的虚拟变量Dt， 则上述三个模型可以简写为 (6.11) (6

8、.12) (6.13) 由此简写形式可以很容易地根据实际数据求出上述模型的系数， 因而也就能很容易地求出所需要的样条函数拟合模型。 第第6章时间序列数据挖掘章时间序列数据挖掘6.3时间序列预测时间序列预测 6.3.1局域线性化方法局域线性化方法局部线性化方法是时间序列建模以及预测的有效方法， 其基本思想是采用相空间重构的办法，将时间序列当前时刻点的领域线性化， 然后由所构造的线性模型做出预测。局部线性化方法的原理如下所述。第第6章时间序列数据挖掘章时间序列数据挖掘设观测到时间序列xt, t=1, 2, , N，其中是采样间隔数。根据下式从余震发生间隔时间序列重构相空间：x (i) =(xi,

9、xi+, , xi+(m-1) T, i=1, 2, , N (6.14) 其中，m为相空间维数， 为间隔时间。 (6.15) (6.16) (6.17) 第第6章时间序列数据挖掘章时间序列数据挖掘其中，XRkm，yRk1，且应使km。将按列零均值化，将也零均值化，那么在目标点的邻域内建立如下线性模型：y=Xw+e (6.18)其中，e是零均值白噪声，XRk1 ；w是参数向量， 。wRk1第第6章时间序列数据挖掘章时间序列数据挖掘w的最小二乘估计为 (6.19) 根据 并由下式求出由在t时刻对t+T时刻的预测值(6.20) 当X不是列满秩或者X的条件数过大时，矩阵XTX接近奇异，将导致(6.1

10、9)式得出的参数估计不可信。另外如何选择嵌入维数m也是令人困扰的问题。 第第6章时间序列数据挖掘章时间序列数据挖掘1. SVD最小二乘法最小二乘法引理1矩阵 的SVD分解可描述为：存在n1阶和n2阶正交矩阵U和V，使 A=UDVT (6.21)式中, ；，12r0是A的全部非零奇异值。 第第6章时间序列数据挖掘章时间序列数据挖掘因此， 可以得到如下SVD最小二乘法： 考虑（5）式的线性回归模型， 如果数据矩阵X是列满秩的， 即r=n2， 设X的条件数c=1/r不大于一个给定的正数M， 且X的SVD分解为X=UDVT， 则w的SVD最小二乘估计为 (6.22)第第6章时间序列数据挖掘章时间序列数

11、据挖掘式中， g=(g1, g2, , gr) T， 且(6.23)其中，ui, 1ir是U的第i个列向量；i, 1ir是X的第i个奇异值。证明证明： 根据引理， 得X的SVD分解为X=UDVT， 因为是正交矩阵， 得Dg=UTy， g=VTw注意到X列满秩，且V是正交矩阵， D具有引理给出的形式， 可得结论。 第第6章时间序列数据挖掘章时间序列数据挖掘2. 自适应确定嵌入维数自适应确定嵌入维数既然当X不是列满秩或者X的条件数过大时， 导致线性最小二乘估计法的参数不可信， 因此需要改良X， 以使其列满秩条件数不大于一个给定的正数M，从而保证参数估计的稳健性。 设想在当前时刻点，如果足够大的嵌入

12、维数是合理的， 那么数据矩阵X列满秩且其条件数不大于M；反之， X很可能是病态的。基于这个分析，我们可以在不损失估计精度的前提下达到此目的。做法是：先选一个初始嵌入维数m0， 然后在当前时刻点，如果X是病态的，就做降维处理，从而找到一个最大的使X列满秩且其条件数不大于M的嵌入维数m。 第第6章时间序列数据挖掘章时间序列数据挖掘算法流程如下： (1) 初选嵌入维数m0，选定邻近点数目k，并给定条件数阈值M0； (2) 在当前时刻t，构造X，并对X做SVD分解； (3) while (1/rM)(4) r=r-1；r=r-1(5) end while(6) m=r 第第6章时间序列数据挖掘章时间序

13、列数据挖掘3. 自适应局部线性化预测方法自适应局部线性化预测方法一般的局部线性化预测方法是取固定的嵌入维数， 按照相关的嵌入定理(Whitney定理和Taken定理)， 宜选择较大的嵌入维数。 但是鉴于样本数目有限， 在相空间上的某些数据点处，可能找不到k个彼此足够接近的数据点， 这是导致预测误差增加的主要原因。而如果是在较低维的相空间中， 就比较容易找到与当前数据点足够接近的k个数据点， 因此可以提高预测精度。故在当前时刻，自适应地选择合适的嵌入维数，可望获得比固定嵌入维数更好的预测结果。确定了合适的嵌入维数m后，就可以重构相空间，然后计算在当前时刻点的预测值。自适应局部线性化预测方法的步骤

14、如下： 第第6章时间序列数据挖掘章时间序列数据挖掘(1) 根据Taken定理初选嵌入维数m0； 选定临近点数目k， 并给定条件数阈值M0； (2) 在当前时刻， 调用自适应的算法确定合适的嵌入维数m； (3) 如果m=m0，则根据式(6.20)和式(6.22)计算出 ，做出预测;(4) 否则，根据m重构相空间，并用式(6.18)和式(6.20)做出预测； (5) 重复步骤(2)和步骤(3)直到结束。 上述算法中的条件阈值M一般根据实验结果合理选择， 根据经验， 对许多实际问题， 一般取M=100较合适。 第第6章时间序列数据挖掘章时间序列数据挖掘6.3.3神经网络方法神经网络方法神经网络是一组

15、连接的输入/输出单元， 其中每个连接都与一个权相关联。 在学习阶段，通过调整神经网络的权，使其能够预测输入样本的正确类标标号来学习。由于单元之间的连接，神经网络学习又称连接者学习。神经网络需要很长的训练时间， 因而对于有足够长训练时间的应用更合适。它需要大量的参数，这些参数通常主要靠经验确定，如网络拓扑或“结构”。神经网络的优点包括其对噪声数据的高承受能力，以及它对未经训练的数据分类模式的能力。 第第6章时间序列数据挖掘章时间序列数据挖掘对时间序列进行预测时，给定的预测原点为k， 预测步长为t，即给定Y(k)的值和若干k时刻之前的时间点，要求预测y(k+t)的值。如果在k时刻预测y(k+t)

16、，需要先建立预测原点k和预测k+t之间的定量关系。由Takens定理可知，在重构的相空间中存在一个映射F: RmRm， 使得：Y(k+t)=F(Y(k)式中，y(k+t)为当前状态Y(k)的t步演化状态。 因此只要能够逼近真实函数F(g)，就能够对y(k+t)的值作出预测。 第第6章时间序列数据挖掘章时间序列数据挖掘BP网络通过将网络输出误差反馈回传来对网络参数进行修正，从而实现网络的映射能力。已经证明，具有一个隐藏层的3层BP网络可以有效地逼近任意连续函数，这个3层网络包括输入层、隐藏层和输出层。考虑到实际应用当中对于网络预测泛化性能的要求，网络设计应坚持尽可能减小网络复杂性的原则。 第第6

17、章时间序列数据挖掘章时间序列数据挖掘对于一个给定的时间序列， 其具体的预测步骤如下： (1) 为了便于预测，首先对获得的时间序列进行归一化处理。归一化方法为(6.24) (2) 选择合适的m和重构系统的状态相空间， 依据预测步长要求构造训练数据。输入数据为： Y(k)=y(k), y(k-), , y(k-(m-1), k=1, 2, , N； 输出数据为：y(k+t), k=1, 2, , N。 第第6章时间序列数据挖掘章时间序列数据挖掘(3) 设计BP网络结构。网络的输入节点数目为重构相空间的维数m，根据具体情况选择合适的隐节点数目，因为每次只是预测出一个数据点，输出节点为单节点。用于实际

18、预测的神经网络结构如图6-1所示。图6-1神经网络结构图第第6章时间序列数据挖掘章时间序列数据挖掘(4) 多次输入训练数据Yk和对应的理想输出数据y(k+t)，对BP网络进行训练。训练结束以后就可以利用该网络进行预测了。 第第6章时间序列数据挖掘章时间序列数据挖掘6.4时间序列数据库相似搜索时间序列数据库相似搜索 6.4.1问题描述问题描述对象之间相似性的定义和度量研究在统计理论、机器学习以及数据挖掘等方面都具有重大的意义。 基于大量甚至海量时间序列数据库的数据挖掘技术，其研究目的是从大量时间序列数据中发现未知的模式和知识，因而主要研究时间序列数据之间的相互关系，即以某种度量来表征两个时间序列

19、之间的相似性，并以此为基础实现多个时间序列数据中的相似性搜索、聚类、 分类和模式发现。因此，相似性问题成为时间序列数据挖掘中的基础问题。第第6章时间序列数据挖掘章时间序列数据挖掘时间序列数据的相似性搜索问题最早由IBM公司的Agrawal等人于1993年提出，该问题被描述为“给定某个时间序列，要求从一个大型的时间序列数据库中找出与之最相似的序列”。第第6章时间序列数据挖掘章时间序列数据挖掘6.4.2时间序列相似性定义时间序列相似性定义时间序列相似搜索(又称为相似查询)的目的是在时间序列数据库中发现与给定序列模式相似的序列或查找库中相似的序列。时间序列相似查询可分为完全匹配和子序列匹配两种情况，

20、前者对应查询序列和被查询序列长度相等的情况， 而后者是在长时间序列中查询与查询序列相似的子序列。完全匹配查询和子序列匹配查询进一步又分为三种情况：第第6章时间序列数据挖掘章时间序列数据挖掘(1) 范围查询(Range Query)。给定查询序列q和时间序列数据集X，在X中搜索全部满足d(q，x)的序列x。这里d(q，x)是q与x之间的距离，阈值是大于0的常数。 (2) 全部配对查询 (All 2 Pairs Query)，也称为空间联合(Spatial Joint) 。在时间序列集合X中找出所有相互之间距离小于阈值的所有序列对。将范围查询的条件略加修改，可以得到k最近邻查询。 (3) k最近邻

21、查询(kNearest Neighbor Query)。给定查询序列q和时间序列数据集X，在X中搜索k个与q距离最近的序列。 第第6章时间序列数据挖掘章时间序列数据挖掘6.4.3高级数据表示与索引高级数据表示与索引1. 高级数据表示高级数据表示TSDM面对的时间序列数据通常是海量数据，直接用原始数据进行基于内容的查询以及时间序列聚类与分类分析等操作效率低下，甚至是不可行的。因此就需要研究合适的时间序列高级数据表示形式，在更高级的数据表示层次上进行数据挖掘处理。从数学的观点看，所谓时间序列高级数据表示，就是将原始时间序列映射到某个特征空间中，并用它在这个特征空间中的映像来描述原始的时间序列。 这

22、样处理有两个好处：实现了数据压缩，从而将显著减少后续处理的计算代价；在更抽象的层次上描述时间序列，有利于从中发现规律。 第第6章时间序列数据挖掘章时间序列数据挖掘目前已有的时间序列高级数据表示形式大致可以分为如下几类。1) 离散傅立叶变换(Discrete Fourier Transform， DFT) 离散傅立叶变换是最早被运用于时间序列的相似性降维方法。 在对时间序列数据的相似分析中， 大多数人采用欧氏几何距离作为相似性计算的依据，因此所选用的方法多采用保持欧氏距离的正交变换法。 离散傅立叶变换是一种十分常用的独立于数据的变换。 一方面由于在时间域中两个信号的距离与频率域中的欧氏距离相等；

23、第第6章时间序列数据挖掘章时间序列数据挖掘 另一方面因为DFT开头的几个系数表现十分突出，可以集中信号的极大部分的能量，因此可以通过保留DFT前几个系数来实现数据降维，成功地计算出实际距离的下界。自从DFT被Agrawal最早应用于时间序列数据相似性搜索后， 又有其他一些论文相继提出了DFT的许多扩展和改进方法，但核心思想并没有什么变化。DFT算法的时间复杂度(n lgn)，相比于点对点的比较的时间复杂度O(mn)，甚至是O(nm2)，已经有了很大的提高。离散傅立叶变换的基本算法如下。 第第6章时间序列数据挖掘章时间序列数据挖掘对于连续信号x(t)，它的Fourier变换定义为式中， 虚数，

24、f为频率，X(f)为频域函数。 设时间序列x(k)(k=0，1，L，N-1)是由连续信号x(t)采样得到的，采样间隔为t，则有 (6.25) 同时信号可以通过逆变换恢复为 (6.26) (6.27) 第第6章时间序列数据挖掘章时间序列数据挖掘DFT所保留的系数越多， 恢复特征也就越多；DFT在数据截取的过程中，舍弃了信号的高频成分，平滑了信号的局部极大值和极小值，因而造成了信息的遗漏。欧氏几何距离在经过DFT变换之后依然得到保持，所以可以用欧氏距离作为时间序列的相似性度量，即通过计算两序列差的平方和的平方根作为这两个时间序列的距离函数。如果计算的结果小于一个由用户所定义的阈值，则可以认为这两个

25、时间序列是相似的。 欧氏距离是一种较优越的估计距离的方法，尤其是在信号受到高斯噪声干扰的时候，由于DFT变换具有保持欧氏几何距离、计算简便且能够把信号大部分能量集中到很少的几个系数当中等优点，所以用它来表示时间序列数据可以达到一定的要求。第第6章时间序列数据挖掘章时间序列数据挖掘前几个系数集中的能量越多，方法也就越有效。但是DFT却平滑了原序列中局部极大值和局部极小值， 导致了许多重要信息的丢失。 此外，DFT还对序列的平稳性有较高要求，对非平稳序列并不适用。分段DFT可以用来缓和这一矛盾，但是分段的方法同样也引入了一些新的问题。例如，分段过大会导致判断力度的下降，分段过小又有低频建模的缺陷。

26、因此在实际应用中，DFT的方法尚存在较大的局限性。 第第6章时间序列数据挖掘章时间序列数据挖掘2) 离散小波变换 (Discrete Wavelet Transform， DWT) 离散小波变换和离散傅立叶变换一样是一种线性信号处理技术。 当用于数据向量D时，将它转换成数值上不同但长度相同的小波系数的向量D。小波变换数据降维的实现同样是由数据裁减实现的，即通过仅存放一小部分最强的小波系数来保留近似的压缩数据。DWT是一种较好的有损压缩，对于给定的数据向量，如果DWT和DFT保留相同数目的系数，则DWT能提供比原数据更精确的近似，更重要的是小波空间的局部性相当好，有助于保留局部细节。DWT在很多

27、场合的应用中要比DFT更加有效。例如， DWT拥有时频局部特性， 可以同时考虑时域和频域的局部特性，而不像DFT那样只考虑频域特性。DWT在很大程度上和DFT处理方法很类似， 其基本函数由递归函数定义。 第第6章时间序列数据挖掘章时间序列数据挖掘信号的连续小波变换定义如下：(6.28) 其中，是尺度因子；反映了位移。 由多尺度分析可知， 任意函数都可以分解为细节部分W1和大尺度逼近部分V1； 然后，V1又可进一步分解。如此重复进行，我们可以将其分解为任意尺度(分辨率)的逼近部分和细节部分。小波分解与重构的Mallat算法：设f(k)是一离散信号，f(k)=ck，则信号f(t)的正交小波变换分解

28、公式为 第第6章时间序列数据挖掘章时间序列数据挖掘(6.29) 其中，cj, k为尺度系数；dj, k为小波系数；j为分解的层数；N为离散采样点数。其重构过程为分解过程的逆运算，相应的重构公式为(6.30) 第第6章时间序列数据挖掘章时间序列数据挖掘在实际应用中，总是希望能够用尽量小的存储空间实现更快的计算速度，于是Harr小波变换最早被引入到时间序列的相似性研究中来。该方法得到了系数子集的良好近似，可以在保持欧氏几何距离的同时更加简便快捷地计算结果。小波变换在针对时间序列相似性研究中相比DFT并没有太大的优势。DWT并没有减少相对镜像误差，也没有在相似性查询中提高查询的准确性。在时间序列数据

29、库的相似性搜索中，基于DFT和基于DWT的不同技术相比并没有太大的差异，而且DWT无法处理任意长度的序列。而在实际应用中，始终分析一种长度的序列或是在索引中建立各种长度序列的架构显然也是不现实的，因此DWT在使用中还存在很大的缺陷。 第第6章时间序列数据挖掘章时间序列数据挖掘3) 动态时间弯曲(Dynamic Time Warping，DTW) 动态时间弯曲广泛用于语音识别领域，允许信号沿着时间轴对模式进行伸缩变换，以使查询模式Q和给定模式R相似。其基本思想是： 考虑时间序列X=x0, x2, , xn-1和Y=y0, y2, , yn-1， 允许通过重复元素扩展每个序列，欧氏距离在扩展的序列

30、X和Y之间计算。 设D(i, j)表示子序列x0, x2, , xn-1和y0, y2, , yn-1之间的动态弯曲距离，用公式表示为D(i, j)=|xi-yi|+min D(i-1, j-1), D(i-1, j-1), D(i, j-1) (6.31)第第6章时间序列数据挖掘章时间序列数据挖掘对弯曲路径作如下限制： (1) 单调性： 路径应该不能向下或向左； (2) 连续性： 在序列中没有间断点； (3) 边界条件： 弯曲路径要在矩阵的单元开始和结束位置。这种方法支持时间轴上的伸缩， 但需计算每个(i, j)的组合， 计算代价高。 第第6章时间序列数据挖掘章时间序列数据挖掘4) 分段多项

31、式表示(Piecewise PolynomialRepresentation，PPR)PPR有时也被称为正交多项式变换(Orthogonal Polynomial Transform，OPT)。PLR实际上是PPR的特例，不过PLR出现得更早，应用得也更普遍。 PPR是一类基于线性多项式回归的正交变换。xX, 其长度|x|=m，在最小均方误差意义下用如下多项式函数近似： f(t, w)=w0+w1t+w2t2+wp-1tp-1 (6.32)即将x映射到多项式基1, t, t2, , tp-1张成的p维特征空间中的点w=(w0, w1, , wp-1)T，称w是x的分段多项式表示(PPR)。 第

32、第6章时间序列数据挖掘章时间序列数据挖掘 w=F(x)=(QTQ)-1QTx (6.33)式中，Q=(1T, , iT, , mT)T，i=(i0, i1, ip-1) T, i=1, 2, , m，x的逆变换为 x=F-1(w)=Qw (6.34)x与x之间满足下式： x=x+e (6.35)其中，eN(0, 2)，e是残差序列。 PPR实现RmRp的映射，一般mp， 因此RmRp的映射实现了时间序列数据的降维。 除上述的高级数据表示形式外，还有其他非系统化方法，如界标法以及微分法，等等。 第第6章时间序列数据挖掘章时间序列数据挖掘2. 索引索引时间序列索引是海量时间序列数据库相似查询(有些

33、文献也称之为相似搜索、基于内容的查询、 特定模式搜索等)的关键技术之一。 在时间序列数据库相似查询处理中， 一般首先用某种高级数据表示将原始时间序列映射为特征空间中的点， 然后再用某种空间索引结构对这些点进行索引。有关空间数据索引的问题一直是数据库领域的研究热点之一，研究成果也较多。从大的方面， 空间数据索引技术可分为两类： 树结构和网格文件。第第6章时间序列数据挖掘章时间序列数据挖掘6.4.4相似搜索算法的性能评价相似搜索算法的性能评价相似搜索算法的性能评价基本可分为三种。 1. 信息损失量信息损失量 S=(x-x)(x-x) T (6.36) 其中，x为原始序列；x为高维表示后的近似序列。

34、 2. 相似查询效率相似查询效率定义定义6.1给定查询序列q，时间序列相似查询算法的查询效率为(6.37)因为|CI|CO|，Dim1， 故Ef(q)0, 1)。对于顺序扫描算法，上式中Dim=1；|CI|=|DB|。 第第6章时间序列数据挖掘章时间序列数据挖掘3. 计算复杂度计算复杂度例如，任给一实值时间序列X，其长度|x|=n，X的PPR变换W=F(X)由(6.33)式计算。 因为，其中的矩阵Q仅与n和p有关，故可以事先计算好Q以及(QTQ)-1QT。因为(QTQ)-1QT是pn维矩阵，故PPR变换需要进行pn次乘法运算和p(n-1)次加法运算。 一般p远远小于n，故PPR变换的时间复杂度

35、为O(n)。第第6章时间序列数据挖掘章时间序列数据挖掘6.5从时间序列数据中发现感兴趣模式从时间序列数据中发现感兴趣模式 6.5.1发现周期模式发现周期模式周期搜索问题可以描述为： 在一个规则时间间隔内找出发生模式的问题。这个概念强调了问题的两个方面， 即模式和间隔。因而，给出一个事件序列，我们可以找出随时间重复的模式及它们重复发生的时间间隔。例如，给出在一个十年阶段中某个公司的销售记录信息，要求我们找出在这十年中的一个基于每月的汇总数据的年度销售模式。第第6章时间序列数据挖掘章时间序列数据挖掘通过一些分析，我们也许发现某种产品在每年的七月达到它们的最大值，这是一个周期模式。然而，有时模式在一

36、个自然时间间隔，如每小时、每天、每月内等并不重复，电报码就是这种例子。又如一个人的心脏跳动通常在每分钟、 每小时间隔内并不规则跳动。因而，人们会被问到对于被给定的销售数据库的另外一种类型的问题是找出一个序列的重复模式以及同此模式阶段相对应的间隔。 第第6章时间序列数据挖掘章时间序列数据挖掘1. 周期模式发现周期模式发现在与时间序列中模式发现有关的人工智能领域已经做了很多的工作，所要考虑的问题是发现由事件(或对象)所标识的规律，每一个事件(或对象)由一个属性集标识， 以便预告一个连续序列。 另外一个热门的研究领域是寻找一个与给定规则表达式相匹配的文本子序列，或是寻找一个与给定字符串近似匹配的文本

37、子序列。然而，这种问题并不考虑一个序列的周期行为，而且，用在这个问题中的技术是面向一个模式的匹配。另一方面，在我们的问题中，没有给定的模式， 我们可以找到一种体现在一个序列中的周期模式来取代搜寻模式匹配问题的另外一种类型相似搜索。第第6章时间序列数据挖掘章时间序列数据挖掘我们比较两个序列以便看它们是否全体或局部相似，这个问题处理比较两个并行的序列以发现其中的共同之处，而在周期搜索的问题中，我们处理发现在所有相同阶段、连续的同一个序列内的共同之处。关于相似搜系的更详细的资料可在参考书中找到。我们的问题是同查找序列模式问题相联系的。 给定一个客户交互的数据库，序列模式挖掘的问题是查找在有一个用户指

38、定最小支持度的所有序列中找出最大序列。我们可以针对更普通的情况来考虑这个问题。 第第6章时间序列数据挖掘章时间序列数据挖掘例如， 一个如表6-1所示的序列关系，如果最小支持度设为20%， 则这个事件中两个序列1234和15符合这个支持度， 因为它们是在表6-1中客户序列的两个最少顺序发生， 因而这两个是所求的序列模式，我们称序列满足这个最小支持度。所以除这两个序列模式之外，1，2，3，4等都是大序列，即使它们不是最大的，而且，当这个问题既不考虑一个序列的周期行为也不考虑在一个单个序列中的模式时， 一个序列如果它的长度是n称为n序列。这个算法被称为AprioriAll，它由查找所有的大1序列开始

39、，在我们的例子中，这个大1序列是1， 2， 3，4和5， 然后这个算法通过迭代，首先从大n序列集中生成一个大(n+1)序列的候选集，这个(n+1)序列将要在原始序列中被重新检测以看它们是否是更大的，这个候选生成过程包括一个加入(join)过程和一个删整(prune)过程。 第第6章时间序列数据挖掘章时间序列数据挖掘表表6-1序列关系序列关系 第第6章时间序列数据挖掘章时间序列数据挖掘2. 周期模式分析周期模式分析同我们的研究最接近的是周期规律发现的问题。 规律的发现是周期关联规则， 每个序列的形成与一个关联规则相对应。例如，一个序列0011同一个关联规则A相关，表示A包含在t2和t3中。这里t

40、1指时间间隔it， (i+1)t。如果每个关联规则包含每个t时间单元(从tj开始)， 我们说这个关联规则有一些周期行为，这个关联规则的周期表示为(1，i)。在Ozden et.al. 的研究中，揭示了周期序列的一些特性，并且用这些特性发现与一个给定序列中有关的经过时间显示规则周期变化的规则，一些非常有用的属性如下： 第第6章时间序列数据挖掘章时间序列数据挖掘属性属性1如果一个项目集X有一个周期(1，i)，则X的任何子集有周期(1，i)在这个属性中，一个项目集指包含在一个给定序列中的项目集，假设在x中有两个项目x1，x2，如果X有一个周期(4，0)， 如果每4个时间单元重复从时间t0。开始，它暗

41、示x1和x2将也有这个周期。 第第6章时间序列数据挖掘章时间序列数据挖掘属性属性2对于任何周期(1，i)来说，它的倍数(1，i)，这里1/l(l被1除)而且i=iT mod 1也是一个周期，因而，仅仅只有那些不是其他周期的倍数的周期才是我们关注的。 这些属性被用做周期关联规则挖掘技术的基础， 这些技术包含周期删节、周期跳过和周期消除。这些操作技术的总的思想是不必检查每个项目集的周期，而是用周期序列的一些规则(或属性)来产生这个搜索空间，周期搜索问题因而被看做周期规则发现问题的一个超集。 第第6章时间序列数据挖掘章时间序列数据挖掘6.5.2发现例外模式发现例外模式数据挖掘的重要的任务之一是发现偏

42、离分布主体的少数对象所呈现的弱模式，即例外模式。 挖掘例外模式有助于人们发现电子商务和移动通信等领域中存在的欺诈模式，或者用于发现机电系统的故障与异常。 本节主要介绍时间序列数据的例外模式挖掘问题。 给出了时间序列例外模式的形式化定义，并提出一种基于这个定义的例外模式的挖掘算法。 第第6章时间序列数据挖掘章时间序列数据挖掘1. TSDM中的例外模式中的例外模式数据挖掘中的“例外(Outlier)”这个词是从时间序列分析理论中借用过来的, 因此时间序列数据挖掘中的例外模式的概念与时间序列分析理论中的例外的概念的区别必须搞清楚。第第6章时间序列数据挖掘章时间序列数据挖掘传统的时间序列分析理论中所讲

43、的“例外(Outlier)”是指一个孤立的异常观测值。 Hawkins给例外下的经典定义是： “例外是一个观测， 它与其他的观测偏离很大，以至于人们怀疑它是由一个不同的机制产生的。” 按照这个定义，1个时间序列中的例外会对模型辨识和参数估计带来不利的影响，因此是有害的。A.Justel等人还提出了“例外片”的概念， 即若干个连续的例外。在时间序列分析中，无论是例外还是例外片都是相对某一具体的数学模型而言的, 检测例外或例外片的任务就是发现一个时间序列中的例外或例外片，并尽可能准确地估计其真值。就这个意义上说，例外(片)等同于噪声，是需要消除的。 第第6章时间序列数据挖掘章时间序列数据挖掘时间序

44、列数据挖掘研究者认为例外模式中蕴含着有用的知识。 一个时间序列中的例外模式反映了产生这个时间序列的系统或现象的行为发生了某种改变。因此， 挖掘例外模式的任务就是辨识出一个时间序列中的全部例外模式并提供给用户。 可见，时间序列数据挖掘研究者们和时间序列分析研究者们对例外的价值认识是不同的。这种认识上的差异是由于双方对例外的定义不同而造成的。时间序列数据挖掘中关心更多的是时间序列的形态特征，而不是其动力学特征。时间序列数据挖掘中定义的模式是一个相似的时间序列集合。时间序列的例外模式定义为一个与其他模式显著不同且出现频率相对较低的模式。因此例外模式中很可能蕴含着系统的某种行为或者性质的改变，如系统故

45、障等。 第第6章时间序列数据挖掘章时间序列数据挖掘2. 已有的例外模式挖掘算法已有的例外模式挖掘算法近年来，传统的数据挖掘研究领域对例外模式挖掘的研究已经较深入了。例外模式发现方法可分为基于分布的方法、基于深度的方法、 基于距离的方法和其他方法。基于分布的方法采用标准分布(如正态分布、 泊松分布等)拟合数据集，根据数据分布情况定义偏差。其主要缺点是这些分布绝大多数适合于单变量情况，而且对于数据挖掘应用来说， 数据的分布情况事先并不知道， 需要通过很多次的测试才能找到合适的数据分布表示方式。用标准分布表示数据既费力， 又得不到满意的结果。在基于深度的方法中，数据集D每一个数据对象表示为K维空间中

46、的一个点，K即深度。人们提出了许多定义深度的方法。根据某种深度定义方法，在数据空间中以分层的方式表示数据对象。异常数据即那些具有较小深度的数据。这种方法避免了基于分布的方法中的数据分布拟合问题， 理论上也适合处理多维数据。 第第6章时间序列数据挖掘章时间序列数据挖掘Knorr等人首次对例外模式进行了形式化定义， 提出了基于距离的例外模式定义, 即DB(p, d)-Outlier的概念，并给出了相应的例外模式挖掘算法。Knorr和Ng将例外模式定义为：如果数据集D中至少有p%的对象到对象O(OD)的距离大于d，那么，对象O是一个DB(p, d) -Outlier。该定义的特点是对例外模式的定义具

47、有一定的灵活性，通过调节参数p和d可以获得不同强度的例外模式。后来的许多例外模式挖掘算法都或多或少受到了Knorr和Ng的这一工作的启发。 第第6章时间序列数据挖掘章时间序列数据挖掘有些研究者认为应当强调例外模式的局部性， 他们对例外模式的定义为：如果数据集D的对象O距离与它最近邻的对象较远，且O中包含的元素数目较少，则O是一个例外模式。然而，上述定义的着眼点主要是如何对数据进行分类，从而发现例外模式。这些成果并不能直接用于辨识时间序列数据中的例外模式，因为对时间序列如何分类本身就是一个复杂的问题。特别是面对海量时间序列数据，要求例外模式发现算法必须要能实现时间序列数据的降维(即压缩)，否则，

48、直接对原始时间序列数据进行操作将是没有效率的， 甚至是不可行的。本章采用的思路是用某种合适的高级数据表示将原始时间序列数据映射到正交多项式基张成的特征空间中， 不但实现了时间序列数据的降维， 而且可以在特征空间中方便地进行聚类操作。 第第6章时间序列数据挖掘章时间序列数据挖掘3. 时间序列的例外模式定义时间序列的例外模式定义考虑一个可数模式集合P=P1, P2, , PK， 这些模式的中心分别记为cen=cen1, cen2, , cenK。 假设： (1) ； (2)。 其中， 表示空集。定义定义6.2模式PiP(i=1, 2, , K）的频率为(6.38) 这里， 记号| |表示模式中的元

49、素数目。 第第6章时间序列数据挖掘章时间序列数据挖掘定义6.3模式PiP(i=1, 2, , K)的例外支持度为 其中，D(ceni, cenj)是模式Pi的中心ceni到模式Pj的中心cenj的距离；DMi和DMj分别是模式Pi和模式Pj中的元素到其中心的最大距离。 第第6章时间序列数据挖掘章时间序列数据挖掘定义定义6.4给定模式集合P，阈值01；对 ，如果os(Q)0，有QP，如果Q是模式集合P中的一个广义例外模式，且满足f(Q)(6.41) 则称模式Q是模式集合P中的一个狭义例外模式。 狭义例外模式定义是符合数据挖掘中经典的例外模式定义的。 狭义例外模式的定义强调例外模式与其他模式显著不

50、同且出现频率相对较低。 第第6章时间序列数据挖掘章时间序列数据挖掘【例6.1】如图6-2所示，假设将全部数据集分为A、B、 C和D等4个模式。那么按照广义例外模式的定义，A、B、C和D这4个模式互为广义例外模式；而按照狭义例外模式的定义，只有C和D这两个模式是潜在的狭义例外模式。 图6-2例外模式图示第第6章时间序列数据挖掘章时间序列数据挖掘4. 辨识时间序列中例外模式的算法辨识时间序列中例外模式的算法本节提出一种系统化的辨识时间序列中例外模式的算法。 该算法的一般框架如图6-3所示。该算法分为4步： (1) 将原始时间序列数据分割成子序列集合。 (2) 将这些子序列用某种高级数据表示映射成特

51、征空间的点。 可选的高级数据表示包括FFT、DWT、 PPR、 DTW等。 (3) 用聚类算法对特征空间中的点进行聚类， 得到一个模式集合P以及每一个模式的中心。(4) 用时间序列的例外模式的定义辨识P中的例外模式。可以根据不同应用的需要， 辨识广义例外模式， 或者狭义例外模式。 第第6章时间序列数据挖掘章时间序列数据挖掘图6-3 辨识时间序列中例外模式的步骤第第6章时间序列数据挖掘章时间序列数据挖掘考虑一个单变量实值时间序列xt(t=1，2，N)，具体的算法流程如下： (1) 给定一个时间序列xt, t=1，2，N。 ；阈值；。 (2) s1, s2, , sn=segmenting(xt)

52、 %分割时间序列 (3) For i=1:1:npfi=transform(si) %将子序列映射到特征空间 (4) P=cluster(pf) %对空间中的点集pf聚类形成模式集P (5) OP=Find_Outlier(P, , ) %辨识例外模式集合OP (6) End第第6章时间序列数据挖掘章时间序列数据挖掘无论是辨识广义例外模式还是辨识狭义例外模式，需要变的只有第(5)步。如果辨识狭义例外模式，则OP=Find_Outlier(P, , )函数的流程如下： (1) OP=Find_Outlier(P, , )(2) 计算模式集P中所有模式的中心距离， 形成一个2维的距离矩阵；(3)

53、计算模式集P中每个模式的半径；第第6章时间序列数据挖掘章时间序列数据挖掘(4) 计算模式集P中每个模式的例外支持度os， 所有满足os的模式均作为候选模式，即Candidate=Pi|PiP, os(Pi) ； (5) 计算候选集合中每个模式的频率，满足f，就是狭义例外模式，即OP= Pi|Picandidate, f(Pi)； (6) end如果辨识广义例外模式，则将OP=Find_Outlier (P, , )函数中的第(4)步删除，而将Candidata作为OP输出即可。 第第6章时间序列数据挖掘章时间序列数据挖掘5. 实验结果实验结果测试用例是1980.1.11992.10.8期间IB

54、M公司股票的每日收盘价数据(共3333个数据)。我们取最后的2333个数据作为测试用例。原始数据如图6-4所示。本章用时间序列分割算法(请参考文献24)对测试用例进行分割。为了便于比较，分别取多项式的阶次为1、 2和3(即p分别等于2、 3和4)。 本章利用在线分割算法把原始序列分割并映射到特征空间， 图6-5 (a)、 (b) 分别是特征空间维数p为2和3时的分割情况。第第6章时间序列数据挖掘章时间序列数据挖掘图64IBM公司每日股票收盘价格序列第第6章时间序列数据挖掘章时间序列数据挖掘将原始序列分割并映射到特征空间后， 就得到了特征空间中的点集，记为pf= pf1, pf2, , pfn

55、， 每一个点对应一个子序列。 为了对这些点集进行聚类， 计算每个点的模平方值，即qw=qw1, qw2, , qwn (6.42) 其中(6.43) 式中， wi是第i个点pfi的坐标向量。 第第6章时间序列数据挖掘章时间序列数据挖掘图6-5特征空间中的点第第6章时间序列数据挖掘章时间序列数据挖掘对qw取整，并画出其每个元素取值的直方图，如图6-6所示。根据这个直方图，可以确定在不同维特征空间中，模式类的数目。由图6-6可知，在2维或3维特征空间中，模式类的数目k=7，而在4维特征空间中，模式类的数目k=8较合适。第第6章时间序列数据挖掘章时间序列数据挖掘图6-6不同特征空间维数时qw的直方图

56、第第6章时间序列数据挖掘章时间序列数据挖掘一旦模式类的数目k确定后，就可以用k-平均(k-means)算法对点集pf进行聚类，得到模式集合P。聚类结果如表6-2和表6-3以及图6-6所示。表6-2是特征空间维数p分别为2、3和4时，每个模式包含的元素的数目；表6-3是特征空间维数p分别为2、3和4时，每个模式中心的模值；图6-7则显示了特征空间维数p分别为2、3和4时每个模式中心子序列的曲线。 从这些结果可以很明显地看出，其中包含了一个例外模式。 第第6章时间序列数据挖掘章时间序列数据挖掘表表6-2当当p分别为分别为2、3和和4时，每个模式包含的元素的数目时，每个模式包含的元素的数目 第第6章时间序列数据挖掘章时间序列数据挖掘表表6-3当当p分别为分别为2、3和和4时，每个模式中心的模平方值时，每个模式中心的模平方值 第第6章时间序列数据挖掘章时间序列数据挖掘图6-7每类模式的中心序列第第6章时间序列数据挖掘章时间序列数据挖掘最后，根据Find_Outlier函数辨识模式集合P中的例外模式。实验中我们选取阈值=1， =0.1。辨识结果如图6-8所示。无论特征空间维数p是2、3或者4时， 都准确地辨识出了1个相同的例外模式， 说明本章提出的例外模式辨识算法是有效的。第第6章时间序列数据挖掘章时间序列数据挖掘图6-8 辨识到的一个例外模式