重叠SSA算法改进奇异谱分析框架

*SoftwareX 8（2018）26原始软件出版物奇异谱分析框架中的一种新算法：重叠SSA（ov-SSA）M.C.R. Lelesa，b，*，J.P.H.圣桑ab洛杉矶莫泽利，1988年，吉马良斯caCELTA -电子工程和自动化研究中心，UFSJ -罗德圣若昂德尔雷联邦大学。MG 443 km 7，36420-000，Ouro Branco，MG，巴西bPPGEE -电气工程研究生课程，UFMG -米纳斯吉拉斯联邦大学，Av. Antônio Carlos 6627，31270-901，Belo Horizonte，MG，巴西C 巴西UFMG电气工程系d巴西UFMG电子工程系ar t i cl e i nf o文章历史记录：2017年11月6日收到2017年11月6日接受保留字：奇异谱分析非平稳信号分割a b st ra ct奇异谱分析（SSA）是一种强有力的方法，它能够处理任意的统计过程，并且对底层数据具有自适应性。近年来，人们提出了许多标准方法的变体，以提高绩效，适应具体问题或目标，或解决某些缺点。当频谱随时间扩展和变化时，会出现这样的缺点之一，需要许多基本矩阵来重建原始序列的近似值，从而阻碍了方法的此外，当分析大型数据集时会出现另一个困难。有计算问题，也有问题的方法的能力，以保持令人满意的可分性。为了解决这些问题，提出了一种新的方法。原始时间序列被分成较小的连续段，它们之间有一些重叠然后，将标准SSA应用于每个段，并将结果正确连接。本文提供了该算法的实现和一些实验来说明所取得的改进。©2017作者。由爱思唯尔公司出版这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）中找到。代码元数据当前代码版本v1.0用于此代码版本的代码/存储库的永久链接https://github.com/ElsevierSoftwareX/SOFTX-D-17-00081Legal Code License 2-Clause BSD License使用的代码版本控制系统无使用MATLAB R2014a的编译要求，操作环境&MATLAB，Windows，Mac OS X，Linux如果可用链接到开发人员文档/手册问题支持电子邮件mleles@ufsj.edu.br原文DOI：http://dx.doi.org/10.1016/j.dsp.2017.10.025。通讯作者：CELTA-电子工程和自动化研究中心，UFSJ-圣若昂德尔雷伊联邦大学，罗德。MG 443 km 7，36420-000，Ouro Branco，MG，Brazil电子邮件地址：mleles@ufsj.edu.br（M.C.R. Leles），joao@ufsj.edu.br（J.P.H.Sansão），mozelli@cpdee.ufmg.br（L.A.Mozelli），hng@cpdee.ufmg.br（H.N.吉马良斯）。https://doi.org/10.1016/j.softx.2017.11.0011. 动机和意义奇异谱分析（SSA）是一种不断发展的时间序列分析方法，已成功应用于科学和工程的多个领域[1，2]。标准SSA算法包括嵌入、奇异值分解（SVD）、分组和对角平均四个阶段. 通过这种方式，SSA能够将时间序列分解为2352-7110/©2017作者。由爱思唯尔公司出版这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。可在ScienceDirect上获得目录列表SoftwareX期刊主页：www.elsevier.com/locate/softxM.C.R. Leles等人/SoftwareX 8（2018）2627=−=−主要成分：趋势、振荡和噪声。一个很大的优势是，该方法是非参数的，这意味着它可以适应底层数据集，排除先验模型的必要性由于这个原因，也被称为无模型方法。尽管最近取得了成功，但标准SSA算法仍有改进的空间。由于与SVD相关的高计算成本，其应用于大型数据集可能不适合。为了克服这个问题，Korobeynikov [3]提出了一种更有效的SVD阶段的实现Rekapalli和Tiwari [4]提出了另一种方法，该方法将原始数据集分割为非重叠段，称为窗口SSA（WSSA）。分段是非平稳时间序列信号处理中的一个循环过程[5]。除了降低计算成本外，分段还可以提供更多优势，例如改善所分析信号的时频特性[6]。为此，在Yiou等人中已经提出了SSA的本地版本，称为多尺度SSA（MS-SSA）[7]的文件。对于原始数据集的给定延伸，MS-SSA算法在具有重合中心的不同长度的几个段中运行标准SSA它寻求不同的时间尺度分辨率的信息，类似于小波变换。尽管在Rekapalli和Tiwari案中提出的方法[4]与标准SSA相比减少了计算工作量，但没有处理连续段合并时这个问题可能导致重构信号中的严重不连续性，从而引入不期望的伪影。另一方面，与标准SSA相比，Yiou等人[7]提出的方法改进了时间-频率表征和信号重建，但标准SSA的几次运行仅重建单个片段的影响最后，尽管Korobeynikov [3]提供的算法效率很高，但该方法是针对标准SSA算法开发的，没有受益于分割提供的其他优势为了在这方面做出贡献，这项工作详细介绍了一种新的SSA算法的实现，该算法在[6]中提出，这是该联合特刊的姊妹论文。该算法可以用于许多已经使用标准SSA的知识领域作为这种新算法的贡献，值得一提的是：改进了大型时间序列的重建;最小化（在某些情况下减轻）与分段分析相关的边界效应;更好地表征非平稳信号的时频特性[6]。在续集中，提供了关于算法和代码的详细解释。这些细节包括计算工作量的分析，揭示了所提出的算法比标准SSA实现更有效，并且与Korobeynikov [3]提出的高效实现非常具有2. 拟议方法Leles等人提出了一种新的算法[6]，允许标准SSA捕获非平稳时间序列中的变化结构和持久结构，提高重建和分析能力。该算法还使SSA能够用于大型数据集。SSA方法对于短时间序列更容易成功[8]，并且它适应于底层数据[9]，因此所提出的算法的思想是通过使用分割来利用这两工作[10]表明，在SSA中，第一个分量是表现出与光谱最大相似性的分量Fig. 1. 分段SSA。第一个组件存储原始信号，第二个组件添加更多信息，依此类推，直到最后一个组件存储的信息量最少理想情况下，分割的目的是将原始时间序列划分为保持不变特征的较小片段。如果一个结构在时间序列中持续时间很长，它会在连续的片段中重复出现。因此，对于一个平稳的时间序列，分割产生的好处相比，一个全球性的分析。然而，如果一个结构随着时间的推移而消失，就像发生在非平稳时间序列中一样，它可能被给定的片段捕获，而被其余的片段错过这是拟议方法的主要动机。长度为N的原始时间序列被分成固定长度为Z的更小的段。对于每个段，计算SSA算法并获得重建的时间序列。所提出的方法的关键创新在于从本地生成的片段中获得最终重建的时间序列。换句话说，就是如何把这个拼图拼在一起。3. 方法说明图1更好地说明了这种方法背后的思想。连续的片段不是不相交的，它们具有一定量的重叠，定义为百分比β。给定一个段，下一个段通过将初始值移位q个样本来获得。因此，重叠百分比由β100（Zq）/Z给出。考虑线段Z。此段内的所有样本都用于本地计算SSA。然而，由于SSA方法受到边界效应的影响，在左边缘和右边缘中的极值点被丢弃。丢弃的样品数量由下式给出：吕（Zq）/2。在Ly上，考虑样本q的内部子集有意义的是表示本地时间序列Z。在图1中针对三个连续段示出了该过程暗区域对应于被丢弃的重构样本浅灰色色调用于描绘保留的重构样本。最终的重建由不重叠的内部段q的级联给出原始时间序列的极端边缘需要特别注意，这将在下一节中解释。3.1. 算法描述该方法的伪代码在算法1中给出。这种方法是对保留时间方法的修改，保留时间方法是计算无限（和有限）持续时间序列的FFT（快速傅立叶变换）卷积的经典工具[11]。这种适应是必要的，因为标准SSA算法遭受28M.C.R. Leles等人/SoftwareX 8（2018）26--联系我们--˜=数据：原始时间序列，（x1，x2，. . . ，XN）。输入：标准SSA参数L（浸入尺寸）和 Im（分组大小）;分段版本参数Z（局部段长度）和q（移位的样本量）。输出：通过分段SSA算法重建的时间序列，x。初始化;L<$←（Z−q）/2;P= n（N-Z）/qn +1;s←（x1，x2，. . . ，x Z）T;intn（n，n，n）;x←（s1，s2，. . . ，s<$L<$+q）T;对p<$2到P−1做ρ<$（p−1）q+1;s←（xρ，xρ+1，. . . ，xρ+Z）T;intn（n，n，n）;x←（ . . ，s<$p+L<$+q）T;端p←p+1;ρ←（p−1）q+1;s←（xρ，xρ+1，. . . ，xρ+N）T;intn（n，n，n）;x←（x，sρL<$1，sρL<$2，. . . ，s<$N）T;算法1：ov-SSA：标准SSA的分段版本，本文提出的修改表1函数分段的输入参数。参数项目说明（x1，x2，. . . ，xN）原始时间序列L嵌入维数Im初等矩阵的集合Z局部段长度q移动的样本量SVD计算方法：两边的边界效应在过滤保存方法中，只有初始点必须被丢弃，因为边界效应只在过滤初始化时因此，新的方法被称为重叠SSA（ov-SSA）。3.2. 软件描述该软件非常简单，由Matlab编写的一些函数组成。有一个更高级别的语法函数y =分割（x、L、I、Z、q、方法）执行原始时间序列的分段，在算法1所示的循环内应用标准SSA，最后，执行连续段的组装，产生输出y：重构的时间序列。此函数的输入参数如表1所示。标准SSA的四个步骤作为函数实现请注意，有两种方法可以执行SVD步骤。一个是传统的实现，而另一个由svdecon提供，1是一个更有效的实现。这些方法在表1中分别表示为3.3. 计算工作量Rekapalli和Tiwari [4]中提出的加窗SSA（WSSA）算法可以被认为是Leles等人[6]中提出的方法的特殊情况。为了实现相同的结果，可以仅将重叠参数设置为β0%。这意味着没有重叠，并导致所提出的算法的最快版本通讯器-首先，Yiou等人[7]重建的序列与原始时间序列的长度不同。其次，作者自己也承认，该方法比标准SSA算法的计算成本据作者所3.3.1. 分析在本节中，将所提出的方法的计算工作量第一种情况是SSA的基本实现，用SSAbsc表示，导致worth-case复杂度由下式给出：时间复杂度为O（N3）其中N是样本的数量。另一种实现，由Korobeynikov [3]提出，用SSAkor表示，效率更高，最坏情况复杂度由下式给出：SSAkor=O（κNlogN+κ2N），其中κ是分组阶段中的特征向量的数量。对于所提出的方法，则存在两种可能性。如果所提出的算法以其基本形式实现，则可以获得以下复杂度：ov-SSA bsc= O（PZ 3）.[17][18][19][11https://www.mathworks.com/matlabcentral/fileexchange/47132-fast-svd-和pca。然而，如果使用有效的实现，则ov-SSA kor=O（P[κZlog Z+κ2Z]）。˜M.C.R. Leles等人/SoftwareX 8（2018）2629=====≤ −==(a) SSAbsc vs ov-SSAbsc。（b）SSAkor与ov-SSAkor，κ=10。（c）SSAkor（κ=N/4）与ov-SSAkor（κ=Z/4）。图二. 比较标准SSA和ov-SSA使用两种实现的SSA算法的计算工作量。 重叠百分比β85%。考虑不同的Z/N比。表2对于不同的Z和q值，通过ov-SSA重建的时间序列的MAE。SSA的MAE为82.3524。在[16]之后，使用的SSA参数是：L=24并且A{1，2，.，13}。Z=59Z= 61Z= 63Z= 60Z= 62Z= 64q=1 80.5816 78.6206 79.6910q=2 78.3102 79.3711 79.8009q=3 80.0970 79.3559 79.7011q=4 78.1780 80.4561 79.86333.3.2. 一个数字示例图2总结了计算工作量方面的一些相关结果这两种实现进行了比较。随着总样本数（N）的变化（x轴），计算运算数（y轴）.图形2（a），考虑标准SSA的基本实现和所提出的算法。正方形表示SSAbsc的结果。其他标记指示由ov-SSAbsc产生的结果，其具有不同的长度Z。通过采用较小的分段，即，通过减小Z/ N比，计算工作量显著减少。重叠百分比，由β85%给出。图2（b）和图2（c）分别考虑了标准SSA和ov-SSA的有效实现，即SSAkor它们的区别在于，在2（b）中，两种方法的分组大小都固定在κ10。然而，在2（c）中，分组大小根据局部段的长度而变化对于SSAkor，它被认为是κN/4，对于ov-SSAkor，它被认为是κZ/4。ov-SSA中的另一个变量是所述算法中的连续步骤之间的移位量，参数q。增加q会减少连续段之间的重叠量因此，随着重叠减少，操作的数量也减少，从而改善了所示的结果请注意，最大值偏移必须满足约束q Z2L，以避免下一节中讨论的边界4. 说明性实例在本节中，我们将介绍两个真实时间序列的例子。在第4.1节中，将所提出的方法与Rekapalli和Tiwari [4]的方法进行了比较，显示了所提出的方法的优点另一方面，在第4.2节中，选择了一些SSA研究[12-4.1. 大型数据集的重建这个例子说明了一个大型数据集的重建，该数据集包括三百万年来相互一致的记录，地面气温，每隔100年取样，共计30，000个数据点。关于这个时间序列的讨论见[15]。原始时间序列已被消除趋势，如图3（a）所示。在图3的左列中，示出了三个细节。右列显示相同的时间间隔。不同之处在于，左列示出了考虑Z512通过ov-SSA（蓝色）和WSSA（红色）重建的时间序列，而右列示出了考虑Z4096的重建。在这两列中，也以洋红色描绘了通过标准SSA重建的时间序列。点表示给定段的开始或结束，以突出显示段的连接。图图3（b）和3（c）揭示了当忽略段之间的重叠时发生的第一个问题。WSSA重建的时间序列随着段长度缩短，该伪影更加明显。然而，对于ov-SSA，细节3（f）和3（g）的分析表明，段长度在不连续性方面具有可忽略的影响，在某种程度上比WSSA更鲁棒另一个由脱节的片段引入的错误信息可以在图中看到。第3段（d）分段。尽管在重构的时间序列的极值样本中不存在突变，但是可以识别原始信号中不存在的重构的时间序列的拐点。考虑到通过ov-SSA重建的时间序列，不连续性被最小化，并且在某些情况下被完全miti- gated，例如。 图3（f）和3（g）。而且，连续段之间的过渡更平滑。作为最后一句话，在图的每一个细节。 3.可以检查通过所提出的方法重建的时间序列是更好地拟合原始时间序列的时间序列之一。 这方面是强调在定量的方式，如图。 四、对于几种长度的分段Z，计算了重建时间序列与原始时间序列之间的平方误差.正如预期的那样，标准SSA在所有方法中产生最大平方误差图4（a）显示了由标准SSA误差归一化的ov-SSA的平方误差，考虑了Z的几个长度。对于每个长度，不同的重叠百分比是一致的。也是并将这些结果与β=0%时等效于ov-SSA的WSSA进行了比较30M.C.R. Leles等人/SoftwareX 8（2018）264.1.1.原始时间序列。4.1.2.第一个细节Z=512（c）第一个细节，Z=4096。(d)第二个细节，Z=512。（e）第二个细节，Z=4096。(f)第三个细节，Z=512。（g）第三个细节，Z=4096。图三. 不考虑重叠时的边界效应问题（WSSA）以及在拟议方法中减少/缓解这一问题（OV-SSA）。(For对本图图例中所指颜色的解释，读者可参考本文的网络版。）该数值分析表明，该算法可以改善相对于标准SSA和WSSA的时间序列重建。在某些情况下，与标准SSA和WSSA相比，平方误差分别减少了近30%和20%。正如预期的那样，段增加，改进不太明显，并且渐近收敛于标准SSA，标准SSA是由包括整个时间序列的单个段组成的最终情况。M.C.R. Leles等人/SoftwareX 8（2018）2631(a)具有不同Z的归一化误差。（b）具有不同参数的ov-SSA的平方误差。见图4。关于时间序列重建可靠性的定量指标，用于算法比较。重叠对近似值可靠性的影响（a）。浸没尺寸和分组尺寸的分析（b）。图五. 1973年至1978年美国每月意外死亡人数。表3对于不同的Z和q值，通过ov-SSA重建的时间序列的MAE。SSA的MAE为164.1134。在[13]之后，使用的SSA参数是：L=24和A{1，2，3，5，6，7，8，10，14}。Z=59Z= 61Z= 63Z= 60Z= 62Z= 642019 - 06-2500：00：002019 - 06- 25 00：00：004.2. 短数据集的重建为了讨论ov-SSA的其他特征，使用了1973年至1978年美国每月意外死亡人数2 这一次series，描绘在图。 5，用于不同的SSA研究[13，14，16]。Hassani [16]将SSA技术应用于该时间序列，说明了SSA的一些细节和SSA参数选择的几种方法，值得强调的是，该时间序列仅由72个样本组成，并且段Z的最小大小可以等于50.尽管如此，通过分段方法可以注意到一些差异。表2和表3分别列出了使用不同Z和q值与Hassani [16]和Hassani等人[13]2这一时间序列可从以下网址免费下载：https://datamarket.com/data/set/22p0/accidental-deaths-in-usa-monthly-1973-1978。如通过表2和3的分析可以看出的，ov-SSA能够重建该（短）时间序列，对于Z和q的不同组合，提供比SSA更好的结果。应当强调的是，这些特别敏感协定参数是为基本特别敏感协定选定的。5. 影响大型数据集出现在许多应用和不同领域：经济和金融，生物信息学，电信，网络挖掘。因此，从大型数据集中提取相关信息的能力极为重要。在这种情况下，空间态势分析是一个强大的分析工具，其势头正在增强。该软件可以帮助在现有和新的应用程序中使用SSA，否则会遇到与数据集大小相关的此外，分段方法甚至对于短时间序列也是有用的，因为它提供了一种替代方案来捕获所观察到的时间序列中存在的时变特征。该软件可以帮助SSA方法本身的发展由于对数据集挖掘的兴趣越来越大32M.C.R. Leles等人/SoftwareX 8（2018）26=引起了人们对有意义的信息的高层次形式表示的兴趣。SSA算法的分段版本的使用可以有益于提取局部信息，其可以在标准方法中被隐藏进一步的讨论见[6]。此外，SSA社区现在有一个新的工具，可用于支持调查有关的最佳选择段长度。之所以选择MATLAB架构，是因为它是许多科学和工程领域的通用语言。因此，许多与SSA相关的内容已经开发，并可能被开发，允许用户轻松地和表面上适应他们的特定需求的拟议软件。该算法并不打算为每个应用提供标准SSA的改进。然而，用户具有灵活的工具，并且可以调整重叠和段大小参数，以从局部或分段方式逐步分析数据，直到全局方式。如果Zl标准SSA方法被恢复。有关可能影响和使用建议的进一步讨论，请参考[6]。6. 结论本文提出了一种新的算法--重叠SSA（ov-SSA）算法。相对于标准SSA方法，该方法可以改善时间序列的重构和主导结构它还有助于将SSA用于大型数据集。与现有算法相比，ov-SSA算法具有以下改进：减少了边界效应;一旦突变减少/减轻，分段连接更加平滑;重构的时间序列与原始时间序列具有相同的长度;与高效实现相比，局部分析对计算量的影响很小致谢我们感谢巴西各机构CAPES（Coordenação de Pessoal de NívelSuperior ） 、 CNPq （ Con- selho Nacional de DesenvolvimentoCientífico e Tecnológico ）和FAPEMIG （ Fundação de Amparo àPesquisa do Estado de Minas Gerais）对这项工作的部分支持。引用[1] Golyandina N，Zhigljavsky A.时间序列的奇 异谱分析。Springer Briefs inStatistics;2013.[2] LelesMCR，Mozelli LA，Guimartes HN. 新的趋势跟踪指标：使用SSA设计交易规则。Fluct Noise Lett2017;16：1750016.[3] 科罗别伊尼科夫SSA的计算和空间效率实现Stat Interface2010;3：357-68.[4] RekapalliR，Tiwari RK.加窗奇异谱分析在地球物理时间序列分析中的应用JGeol Resour Eng2014;3：167-73.[5] Azarbad M，Azami H，Sanei S，Ebrahimzadeh A.一种脑电信号分割的时频方法。J AI Data Min2014;2（1）：63-71.[6] Leles MCR，Guimaraes HN，Sansao JP，Mozelli LA.用奇异谱分析改进时间序 列 重 构 数 字 信 号 处 理 2016;1.https://doi.org/10.1016/j.dsp.2017.10.025 ， inpress.[7] 杨伟杰，陈晓梅.数据自适应小波与多尺度奇异谱分析。Physica D2000;142（3）：254-90.[8] 杨伟杰，李伟杰.奇异谱分析：一个工具包短，嘈杂的混沌信号。PhysicaD1992;58：95-126.[9] Jemwa GT，Aldrich C.应用蒙地卡罗奇异谱分析法进行过程动力学分类。计算机化学工程2006;30（5）：816-31.[10] 久米湾奇异谱分析解释为完全特征滤波器分解。Adv Adapt Data Anal2012;04（04）：1250023.[11] 布里格姆·E快速傅里叶变换及其应用。Prentice Hall;1988.[12] 吴晓松，李晓松，李晓用奇异谱分析预测欧洲工业生产。Int J Forecast2009;25：103-18.[13] Hassani H，Ghodsi Z，Silva ES，Heravi S.从自然到数学：使用遗传学殖民理论提高基于子空间的方法的预测性能。数字信号处理2016;51：101-9.[14] 王荣，马宏国，秦建强，冯晓文，刘宏民.应用ssa技术分析死亡序列。在：信息，通信和信号处理，2015年第10届IEEE国际会议;2015年。p. 1比5。[15] BintanjaR，van de Wal RSW. 北美冰盖动力学和10万年冰川循环的开始。Nature2008;454：869-72.[16] 哈桑尼·H奇异谱分析：方法论与比较。J DataSci2007;5（2）：259-67.