一种符号化的授时偏差预测方法

开篇：润墨网以专业的文秘视角，为您筛选了一篇一种符号化的授时偏差预测方法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要：提出了一种通过符号化方法对授时系统时间偏差进行预测的方法。该方法利用矢量拟合来表达时间序列的走势形态，采用聚类算法对形态进行聚类，然后根据聚类结果得到符号序列，并用不完全抽取方法来抽取序列模式。预测时，可根据学习得到的模式集来对新序列做出预测分析。通过对授时系统误差数据的实验表明，该方法可以对时间偏差进行较好预测，并可对预测的数值进行校准，从而进一步提高授时精度。

关键词：时间序列；符号化；聚类算法；模式抽取

中图分类号：TP301 文献标识码：A 文章编号：2095-1302(2012)04-0038-03

A time offset prediction method based on symbol sequence

Sun Jie

(CETC 20, Xi’an 710068, China)

Abstract: A new method for time offset forecast based on symbolic sequences is presented. The method uses vector fitting to represent the forms of the trends of time series and applies cluster method to classify these forms. Then the symbolic sequences are obtained and the patterns of sequences are extracted by using half-baked patterns extracting algorithm. This method can also forecast new sequences based on the sets of patterns just learned. Experiments show that it gives good results to forecast time offset series and can align the values just predicted .So it can afford higher accuracy by this method.

Key words: Time series, symbolic method; clustering algorithm; patterns extracting

0 引 言

通信系统中的授时精度是关键性的技术因素。随着对授时精度要求的提高，设备的维护难度也随之提高。而通过对历史偏差时间序列的学习，可对实时数据进行预判和校准，从而有效地提高精度，并降低对授时设备的要求。

时间序列预测是一个很复杂的问题。通常认为，时间序列预测要以两大假设为前提：曲线沿趋势移动；历史会重演。时间序列预测的算法众多，特别是各类神经网络算法，其非线性逼近能力使得其在时间序列分析上取得了相当好的效果。但是，由于神经网络泛化能力差、学习时间长、隐节点不好确定、受假突破和噪声影响大以及预测的时间范围小等自身缺点和局限性，其预测效果往往不稳定、复杂程度高等问题仍然很难克服。

符号化时间序列方法是从符号动力学理论、混沌时间序列分析和信息理论发展起来的一种分析方法。符号化的基本思想就是对时间序列离散化，把大量的数值数据序列变换为仅有若干值域的符号序列，也称为“粒化”过程，这一过程能够获得时间序列大尺度的特征，降低动力学噪声和测量噪声的影响。

本文使用符号化算法将偏差的时间序列拟合为矢量，利用矢量之间的相似度进行聚类，并为每一类分配符号，每组数据产生一条符号序列，然后对需要学习的序列进行模式分割并进行学习，再使用学习结果模式集合来对待测的序列进行匹配预测，从而达到预测的目的。

1 时间序列符号化

1.1线性化分段

与以往线性化分段工作不同的是，采用本文方法的主要目的是从时间序列中分割和抽取形态模式，这些模式之间具有相对独立的变化。模式线性化分段方法的优点之一是具有很好的形态表达与分割能力，经过处理，时间序列根据其变化形态被分割成形态各异的矢量，每一矢量都直观地表达了时间序列在该段时间内的变化特征，并且不同分段在形态上相对独立，因此，可以认为一个线性分段可以代表一个相对独立的变化模式。

线性化分段方法的第二个重要优点是当每段长度ni取不同值时还可以获得不同的表示精度。ni取得越小，段分得越细，

偏差就越小，就相当于提高了表示的精度或观察的分辨率；反之，ni取得越大，段就分得越粗，偏差就越大，就相当于降低了表示的精度或观察的分辨率。因此，通过对每段长度ni取不同值，线性化分段方法可以支持对同一时间序列在不同分辨率下的观察。线性化分段方法的这一特点非常重要，它可以帮助实现对时间序列进行多分辨率也称多粒度的数据挖掘分析，这也是时间序列数据挖掘的一个重要的研究课题。此外，该方法还具有较高的滤除噪声和数据抽象能力。在对时间序列进行线性化分段处理的同时，也相当于对它进行了平滑和数据缩减处理，变换后的数据量大幅度减少。

实现线性化分段的方法有很多，本文采用的是一种自下而上的分段近似算法。给定的时间序列T包含n个点，首先将它分为k个线性分段，每个分段包含3个点，最前面可以是4个或5个点，对每个分段利用最小二乘法对求出这些点集的最佳拟合线段。再定义每个点到所在直线的欧氏距离为残存误差，称为d1,d2,…,dj。定义每条线段的平均误差ei为：

该平均误差可被看作是第i个分段对其所包含数据点拟合的好坏度量。一般来说，不同矢量的平均误差会呈现出一定的不一致性，通过定义误差平衡系数Bk=std(e1,e2,…,ek)来衡量k个分段之间的不一致。然后，分段算法从已有的分段中选取两个相邻分段，并将它们合并为一个新的分段，这样，总的分段数就减少了一个。选择合并分段的依据是使下一步的误差平衡系数Bk最小，此后，再不断重复这步操作，直到分段数减至定值为止。

1.2聚类

使用聚类过程的目的就是将矢量集合中的数据分组成为多个类，使得在同一个类中的对象之间具有较高的相似度，而不同类中的对象差别很大。K-means算法属于聚类方法中的一种基本的划分方法，它采用误差平方和准则函数作为聚类准则函数。

本文的K-means算法提供了一种准确、简单高效的方法。假设矢量集合中有N个矢量样本{x1,x2,…,xN}，根据矢量特征计算欧氏距离时，可将矢量样本分为K类。第k类的样本数目为：

每类Ck的距离中心为(m1,m2,…,mK)，其中：

距离中心为最小化的目标函数为：

由于某些时间的序列中的大部分数据斜率变化程度都较小，且在矢量合并后，长矢量的个数在整个矢量集合中也比较少，特别是波动周期越小，合并的长矢量数量也就越小。这个也是显而易见的，因为波动周期越小，合并后产生的平均误差也就越大，合并的可能性也就小。在这种情况下，得到的结果具有明显的分布稠密度，而这将导致传统K-means聚类之后，各类的形状和大小差别非常大，之后的符号化后，其结果将出现符号出现频率不一致的、序列包含信息量少的情况。

为了解决这个问题，本文设计了再聚类后“折断”方法来对聚类后类中个数较少的类进行处理，这些类中包含的往往是模比较大的对象，计算这些类中的各个对象距各个中心点的距离，并将其归为各类。与上次聚类不同的是，这次聚类对每个对象作倍数标示，倍数q等于对象的模除以聚类中心点的模后取整，也就是说，新的聚类将原有较长的矢量变成了若干个短的矢量。

1.3 分配符号

聚类后，每个类都被赋予了一个类标识符。其原则是同一个类的标识符代表聚类中属于同一类别；被“折断”的对象用q个符号表示；对于较为关注的中心点的所在类，其标志为特殊字母。比如本文将较大涨跌的类分别标识为大写字母表示，其余的用小写字母表示。以这些类标识符形式替代所有属于该类的时间序列分段，即可得到所需的符号序列S。

2 模式抽取与识别

2.1 相关定义

下面先给出三个相关的参数定义。其中，表示序列S的模，即序列S中包含符号的个数；表示符号ai受关注的程度，即本文中矢量的斜率；N(Ti)代表模式Ti在模式表中出现的次数。

2.2抽取模式

本文采用的是基于定长序列的切割方法[1]。这种方法较为广泛的应用是在基于系统调用的入侵检测等方面。在训练时，可利用滑动窗口技术（窗口宽度为ω）从输入序列中进行模式抽取，并输出正常模式库。如ω=3，其训练序列为ACDBBDA，模式表示为：{ACD, CDB, DBB, BBD, BDA}。

在分析时，同样可采用滑动窗口技术进行模式匹配，窗口每移动一次，都与模式表中的模式相匹配。如果匹配成功，则得出结果；如果不成功，则继续向下滑动。抽取方法可使用如下两种：

（1）完全抽取

采用定长窗口来切割全部序列，切割经过实验测得的窗口ω大小取6较为理想，但是，完全抽取的缺点也很明显，对于一个序列S，抽取的模式有-1个，故其时间、空间复杂度都会增加，而且切割出来的模式繁冗、无用信息多、正确率低。

（2）不完全抽取

由于在符号序列中，期望得到的结果往往是斜率较大的信息，而且，由于时间序列波动中具有一定的随机性，因而其中的一些信息往往是不包含可用信息的，更加关注的是斜率较大的结果。所以，在切割序列的时候，每个窗口的最后一个符号为所关注的符号，即>ε；如果不是，则滑动窗跳过。这样切割出来的模式会大大减少，并且信息量少的模式也相应地大量减少。

采用本算法切出的短序列的窗口值ω越大，则复杂度越大，误报率越低，漏报率越高；ω越小，复杂度越小，误报率越高，漏报率较低。一般情况下，模式总是以一个或多个连续的斜率较大的符号结束的。

2.3精简及匹配

由上述方法可以得到一个原始的模式集合，其中，有些模式由于噪声影响，本身就极少可能出现，故其数量较少，对于这种出现次数小于θ模式的，即N(Ti)λ，则将其他删减掉；如果均未超过，则认为是无用模式，全部删减。例如一个模式cdedcA出现了6次，另一模式cdedcB出现了8次，出现频率为0.429和0.571，均未超过阈值λ=0.6，则这两种模式都应删减掉。删减后生成新的模式集合，它将作为训练结果对新的序列进行匹配预测。

将目标时间序列曲线进行符号化，并使用训练好的模式集合来对其进行匹配，如果出现了同样的条件符号模式，则可得出目标符号，从而得到所预测时间序列的未来趋势。

3 实验结果

3.1 实验过程

完全抽取方法可选取10组授时系统的偏差作为学习数据，同时利用另外5组作为测试数据。

不完全抽取实验可选取60组授时系统偏差作为实验数据，并用其中的50组进行学习，用另外的10组进行测试。

首先，要对每组数据作矢量化处理，之后，再利用矢量形态相似性度量方法和改进后的K-means聚类算法进行聚类。实验表明，所采用的再聚类后“折断”的方法，不但可以大大降低符号数量，同时可提高模式质量。再聚类后的类个数为12，也就是说，产生了12个符号。

3.2 实验结果

匹配作为测试的10组数据，并将条件模式一样的情况下的结果记为正确，反之记为错误。如果有关注的符号没有预测，则记为漏报。表1所列的是记录了使用完全抽取以及不完全抽取方法时的正确率及漏报率数据，表2所列是ω取5，6，7时的正确率和误报率。

通过测试结果可以看到，完全抽取方法虽然漏报率较低，但是，在计算时间、正确率方面的指标都比不完全抽取要差。ω的取值对精简后模式的个数和正确率、误报率影响很大，ω越大，模式越少，正确率越高，同时漏报率也越高。

采用不完全抽取的最好正确率超过了80％，在时间序列分析预测中，达到了比较好的效果，可以用来对授时系统的时间偏差趋势进行预测。

4 结 论

本文使用一种符号抽取方法对线性化分段并聚类过的时间序列进行了模式抽取，并对真实数据进行预测。预测结果较为理想，可以较好地对某授时系统的时间偏差进行预测分析，也可以提高授时系统精度，其结果还可以作为授时系统故障诊断以及故障预测的依据。该方法算法适用性强，对于其他应用领域，如定位精度的预测，可根据数据对象的特点设置参数以及使用不同的聚类算法和模式抽取算法，来进一步增强预测效果。

参 考 文 献

[1] FORREST S, HOFMEYR S A, SOMAYAJI A, et al. A sense of self for Unix processes[C]//Security and Privacy: Proceedings of 1996 IEEE Symposium on. 1996: 120 -128.

[2] GEORGE E P Box. 时间序列分析: 预测与控制［M］.北京：人民邮电出版社, 2005.

[3] 张雨. 时间序列的混沌和符号分析及实践［M］.长沙：国防科技大学出版社, 2007.

[4] 李克平. 混沌神经网络和非线性时间序列预测［D］. 天津：南开大学博士论文, 2002.

［5］ 刘佳,胡中豫,游苑，等.短波战术电台同步授时及时钟保持技术研究 [J].现代电子技术，2011，34（9）：10-12.