数据挖掘原理与算法06

2020年3月17日星期二1第六章时间序列和序列模式挖掘内容提要时间序列及其应用时间序列预测的常用方法基于ARMA模型的序列匹配方法基于离散傅立叶变换的时间序列相似性查找基于规范变换的查找方法序列挖掘及其基本方法AprioriAll算法AprioriSome算法GSP算法2020年3月17日星期二2时间序列及其应用时间序列（TimeSeries）挖掘是数据挖掘中的一个重要研究分支，有着广泛的应用价值。近年来，时间序列挖掘在宏观的经济预测、市场营销、客流量分析、太阳黑子数、月降水量、河流流量、股票价格变动等众多领域得到应用。事实上，社会、科学、经济、技术等领域中广泛存在着大量的时间序列数据有待进一步的分析和处理。时间序列数据挖掘通过研究信息的时间特性，深入洞悉事物进化的机制，是获得知识的有效途径。2020年3月17日星期二3时间序列有关概念从统计意义上来讲，所谓时间序列就是将某一指标在不同时间上的不同数值，按照时间先后顺序排列而成的数列。时间序列挖掘通过对过去历史行为的客观记录分析，揭示其内在规律，进而完成预测未来行为等决策性工作。简言之，时间序列数据挖掘就是要从大量的时间序列数据中提取人们事先不知道的、但又是潜在有用的与时间属性相关的信息和知识，并用于短期、中期或长期预测，指导人们的社会、经济、军事和生活等行为。从数学意义上来讲，如果我们对某一过程中的某一变量进行X(t)观察测量，在一系列时刻t1，t2，…，tn（t为自变量，且t1t2…，tn）得到的离散有序数集合Xt1，Xt2，…，Xtn称为离散数字时间序列。设X(t)是一个随机过程，Xti(i=1，2，…，n)称为一次样本实现，也就是一个时间序列。2020年3月17日星期二4时间序列有关概念时间序列的研究必须依据合适的理论和技术进行，时间序列的多样性表明其研究必须结合序列特点来找到合适的建模方法。一元时间序列：如某种商品的销售量数列等，可以通过单变量随即过程的观察获得规律性信息。多元时间序列。如包含气温、气压、雨量等在内的天气数据，通过多个变量描述变化规律。时间序列挖掘需要揭示各变量间相互依存关系的动态规律性。离散型时间序列：如果某一序列中的每一个序列值所对应的时间参数为间断点，则该序列就是一个离散时间序列。连续型时间序列：如果某一序列中的每个序列值所对应的时间参数为连续函数，则该序列就是一个连续时间序列。序列的分布规律：序列的统计特征可以表现平稳或者有规律的震荡，这样的序列是分析的基础点。此外如果序列按某类规律（如高斯型）的分布，那么序列的分析就有了理论根据。2020年3月17日星期二5第六章时间序列和序列模式挖掘内容提要时间序列及其应用时间序列预测的常用方法基于ARMA模型的序列匹配方法基于离散傅立叶变换的时间序列相似性查找基于规范变换的查找方法序列挖掘及其基本方法AprioriAll算法AprioriSome算法GSP算法2020年3月17日星期二6时间序列预测的常用方法时间序列分析的一个重要应用是预测，即根据已知时间序列中数据的变化特征和趋势，预测未来属性值。为了对时间序列预测方法有一个比较全面的了解，我们首先对时间序列预测的主要方法加以归纳。确定性时间序列预测方法随机时间序列预测方法其他方法2020年3月17日星期二7时间序列预测的常用方法(续)确定性时间序列预测方法对于平稳变化特征的时间序列来说，假设未来行为与现在的行为有关，利用属性现在的值预测将来的值是可行的。例如，要预测下周某种商品的销售额，可以用最近一段时间的实际销售量来建立预测模型。一种更科学的评价时间序列变动的方法是将变化在多维上加以综合考虑，把数据的变动看成是长期趋势、季节变动和随机型变动共同作用的结果。长期趋势：随时间变化的、按照某种规则稳步增长、下降或保持在某一水平上的规律。季节变动：在一定时间内（如一年）的周期性变化规律（如冬季羽绒服销售增加）。随机型变动：不可控的偶然因素等。设Tt表示长期趋势，St表示季节变动趋势项，Ct表示循环变动趋势项，Rt表示随机干扰项，yt是观测目标的观测记录。则常见的确定性时间序列模型有以下几种类型：加法模型：yt=Tt+St+Ct+Rt。乘法模型：yt=Tt·St·Ct·Rt。混合模型：yt=Tt·St+Rt或yt=St+Tt·Ct·Rt。2020年3月17日星期二8时间序列预测的常用方法(续)随机时间序列预测方法通过建立随机模型，对随机时间序列进行分析，可以预测未来值。若时间序列是平稳的，可以用自回归(AutoRegressive，简称AR)模型、移动回归模型(MovingAverage，简称MA)或自回归移动平均(AutoRegressiveMovingAverage，简称ARMA)模型进行分析预测。其他方法可用于时间序列预测的方法很多，其中比较成功的是神经网络。由于大量的时间序列是非平稳的，因此特征参数和数据分布随着时间的推移而变化。假如通过对某段历史数据的训练，通过数学统计模型估计神经网络的各层权重参数初值，就可能建立神经网络预测模型，用于时间序列的预测。2020年3月17日星期二9第六章时间序列和序列模式挖掘内容提要时间序列及其应用时间序列预测的常用方法基于ARMA模型的序列匹配方法基于离散傅立叶变换的时间序列相似性查找基于规范变换的查找方法序列挖掘及其基本方法AprioriAll算法AprioriSome算法GSP算法2020年3月17日星期二10基于ARMA模型的序列匹配方法ARMA模型（特别是其中的AR模型）是时序方法中最基本的、实际应用最广的时序模型。早在1927年，G.U.Yule就提出了AR模型，此后，AR模型逐步发展为ARMA模型、多维ARMA模型。ARMA通常被广泛用于预测。由于ARMA模型是一个信息的凝聚器，可将系统的特性与系统状态的所有信息凝聚在其中，因而它也可以用于时间序列的匹配。1．ARMA模型对于平稳、正态、零均值的时序，若X在t时刻的取值不仅与其前n步的各个值有关，而且还与前m步的各个干扰有关（n，m=1，2，…），则按多元线性回归的思想，可得到最一般的ARMA（n，m）模型：其中。}1...210{ntxXt，，，，ntttxxx...,,,21mttt...,,,21tjtjmjitinitxx11),0(~2atNID2020年3月17日星期二11基于ARMA模型的序列匹配方法(续)2．AR模型AR（n）模型是ARMA（n，m）模型的一个特例。在上面ARMA（n，m）模型表达中，当时，有其中。由于此时模型中没有滑动平均部分，所以称为n阶自回归模型，记为AR（n）。3．MA模型MA（m）模型是ARMA（n，m）模型的另一个特例。在上面ARMA（n，m）模型表达中，当时，有其中。由于模型中没有自回归部分，所以称为m阶滑动平均（MovingAverage）模型，记为MA（m）。0jtitinitxx1),0(~2atNID0ijtjmjttx1),0(~2atNID2020年3月17日星期二12建立AR模型建立AR模型的最常用方法是最小二乘法。具体方法如下：对于AR（n）模型，有，其中，即可以用以下线性方程组表示：，，……，。或者写成如下矩阵形式：，其中根据多元线性回归理论，参数矩阵的最小二乘估计为：。tntntttxxxx...2211),0(~2atNID111211...nnnnnxxxx，222112...nnnnnxxxxNnNnNNNxxxx...2211。xyTNnxxxy]...[2n1，Tn]...[21，Tnn]...[N21，nNNNnnnnxxxxxxxxxx...............212111yxxxTT1)(2020年3月17日星期二13构造判别函数根据上面的模型，我们可以获得待测序列的参数模型，同样我们也可以得到序列数据库中的其他序列Yi的参数模型。和都是n维向量，故均可视为n维空间上的点，从而序列的相似性问题就归结为n维空间Rn中的距离问题。因此，我们下面简单介绍几种基于距离的判别函数。1．Euclide2．残差偏移距离判别其中是待检序列的协方差矩阵，N表示待检序列的长度。3．Mahalanobis距离判别其中是参考序列的协方差矩阵。4．Mann距离判别其中，为待检序列的协方差矩阵，为待测时序的方差。，。，，}1...,,2,1,0{ntxXtXiYXY)()(),(2YXTYXYXED)()(),(2YXXTYXYXrND)()(),(22YXYTYXYYXMhrND)()(),(22XYXTXYXXYMnrNDXrYrXr2X2020年3月17日星期二14第六章时间序列和序列模式挖掘内容提要时间序列及其应用时间序列预测的常用方法基于ARMA模型的序列匹配方法基于离散傅立叶变换的时间序列相似性查找基于规范变换的查找方法序列挖掘及其基本方法AprioriAll算法AprioriSome算法GSP算法2020年3月17日星期二15基于离散傅立叶变换的时间序列相似性查找为了方便讨论，我们首先给出一些符号来表示序列及序列的相似性：表示一个序列；Len（X）表示序列X的长度；First（X）表示序列X的第一个元素；Last（X）表示序列X的最后一个元素；表示X在i时刻的取值，；序列上元素之间的“”关系，在序列X上，如果ij，那么X[i]X[j]；本文用表示X的子序列，如果序列X有k个子序列，则把这些子序列分别表示为。子序列间的关系，为X的子序列，如果，则称。子序列重叠（Overlap），假定XS1，XS2为X的两个子序列，如果或成立，则XS1与XS2重叠。}1...,,2,1,0{ntxXt][iXixiX][SXSkSSXXX,,...,21SjSiXX,)First(X)First(XSjSiSjSiXX)Last(X)First(X)First(XS1S2S1)Last(X)First(X)First(XS2S1S22020年3月17日星期二16基于离散傅立叶变换的时间序列相似性查找一般地，相似性匹配可分为两类：完全匹配（WholeMatching）。给定N个序列和一个查询序列X，这些序列有相同的长度，如果存在，那么我们称完全匹配。子序列匹配（SubsequenceMatching）。给定N个具有任意长度的序列和一个查询序列X以及参数。子序列匹配就是在上找到某个子序列，使这个子序列与X之间的距离小于等于。nYYY...,,,21),(iYXDiYX与nYYY...,,,21)1(NiYi2020年3月17日星期二17完全匹配所谓完全匹配必须保证被查找的序列与给出的序列有相同的长度。因此，与子序列匹配相比，工作就相对简单一些。1．特征提取给定一个时间序列，对X进行离散傅立叶变换，得到,这里，X与xt代表时域信息，而与代表频域信息，，为傅立叶系数。2．首次筛选根据Parseval的理论，时域能量谱函数与频域能量谱函数相同，得到}1...,,2,1,0{ntxXt)/2exp(/110nftixnXnttf1,...,1,0nfXfX}1,...,2,1,0{nfXXffX22YXYX2020年3月17日星期二18完全匹配(续)按照Parseval的理论，如下式子也应该成立：对大多数序列来说，能量集中在傅立叶变换后的前几个系数，也就是说一个信号的高频