一種符號化的授時(shí)偏差預(yù)測方法

引言

通信系統(tǒng)中的授時(shí)精度是關(guān)鍵性的技術(shù)因素。隨著對授時(shí)精度要求的提高，設(shè)備的維護(hù)難度也隨之提高。而通過對歷史偏差時(shí)間序列的學(xué)習(xí)，可對實(shí)時(shí)數(shù)據(jù)進(jìn)行預(yù)判和校準(zhǔn),從而有效地提高精度，并降低對授時(shí)設(shè)備的要求。

時(shí)間序列預(yù)測是一個(gè)很復(fù)雜的問題。通常認(rèn)為，時(shí)間序列預(yù)測要以兩大假設(shè)為前提：曲線沿趨勢移動(dòng)；歷史會(huì)重演。時(shí)間序列預(yù)測的算法眾多，特別是各類神經(jīng)網(wǎng)絡(luò)算法，其非線性逼近能力使得其在時(shí)間序列分析上取得了相當(dāng)好的效果。但是，由于神經(jīng)網(wǎng)絡(luò)泛化能力差、學(xué)習(xí)時(shí)間長、隱節(jié)點(diǎn)不好確定、受假突破和噪聲影響大以及預(yù)測的時(shí)間范圍小等自身缺點(diǎn)和局限性，其預(yù)測效果往往不穩(wěn)定、復(fù)雜程度高等問題仍然很難克服。

符號化時(shí)間序列方法是從符號動(dòng)力學(xué)理論、混沌時(shí)間序列分析和信息理論發(fā)展起來的一種分析方法。符號化的基本思想就是對時(shí)間序列離散化，把大量的數(shù)值數(shù)據(jù)序列變換為僅有若干值域的符號序列，也稱為“?；边^程，這一過程能夠獲得時(shí)間序列大尺度的特征，降低動(dòng)力學(xué)噪聲和測量噪聲的影響。

本文使用符號化算法將偏差的時(shí)間序列擬合為矢量，利用矢量之間的相似度進(jìn)行聚類，并為每一類分配符號，每組數(shù)據(jù)產(chǎn)生一條符號序列，然后對需要學(xué)習(xí)的序列進(jìn)行模式分割并進(jìn)行學(xué)習(xí)，再使用學(xué)習(xí)結(jié)果模式集合來對待測的序列進(jìn)行匹配預(yù)測，從而達(dá)到預(yù)測的目的。

1  時(shí)間序列符號化

1.1  線性化分段

與以往線性化分段工作不同的是，采用本文方法的主要目的是從時(shí)間序列中分割和抽取形態(tài)模式，這些模式之間具有相對獨(dú)立的變化。模式線性化分段方法的優(yōu)點(diǎn)之一是具有很好的形態(tài)表達(dá)與分割能力，經(jīng)過處理，時(shí)間序列根據(jù)其變化形態(tài)被分割成形態(tài)各異的矢量，每一矢量都直觀地表達(dá)了時(shí)間序列在該段時(shí)間內(nèi)的變化特征，并且不同分段在形態(tài)上相對獨(dú)立，因此，可以認(rèn)為一個(gè)線性分段可以代表一個(gè)相對獨(dú)立的變化模式。

線性化分段方法的第二個(gè)重要優(yōu)點(diǎn)是當(dāng)每段長度n取不同值時(shí)還可以獲得不同的表示精度。n取得越小，段分得越細(xì),偏差就越小，就相當(dāng)于提高了表示的精度或觀察的分辨率:反之，n取得越大，段就分得越粗，偏差就越大，就相當(dāng)于降低了表示的精度或觀察的分辨率。因此，通過對每段長度n取不同值，線性化分段方法可以支持對同一時(shí)間序列在不同分辨率下的觀察。線性化分段方法的這一特點(diǎn)非常重要，它可以幫助實(shí)現(xiàn)對時(shí)間序列進(jìn)行多分辨率也稱多粒度的數(shù)據(jù)挖掘分析，這也是時(shí)間序列數(shù)據(jù)挖掘的一個(gè)重要的研究課題。此外,該方法還具有較高的濾除噪聲和數(shù)據(jù)抽象能力。在對時(shí)間序列進(jìn)行線性化分段處理的同時(shí)，也相當(dāng)于對它進(jìn)行了平滑和數(shù)據(jù)縮減處理，變換后的數(shù)據(jù)量大幅度減少。

實(shí)現(xiàn)線性化分段的方法有很多，本文采用的是一種自下而上的分段近似算法。給定的時(shí)間序列T包含n個(gè)點(diǎn)，首先將它分為k個(gè)線性分段，每個(gè)分段包含3個(gè)點(diǎn)，最前面可以是4個(gè)或5個(gè)點(diǎn)，對每個(gè)分段利用最小二乘法對求出這些點(diǎn)集的最佳擬合線段。再定義每個(gè)點(diǎn)到所在直線的歐氏距離為殘存誤差，稱為 d1,d2,…,dj。定義每條線段的平均誤差e,為：

該平均誤差可被看作是第i個(gè)分段對其所包含數(shù)據(jù)點(diǎn)擬合的好壞度量。一般來說，不同矢量的平均誤差會(huì)呈現(xiàn)出一定的不一致性，通過定義誤差平衡系數(shù)Bk=std(e1,e2,…,ek)來衡量k個(gè)分段之間的不一致。然后，分段算法從已有的分段中選取兩個(gè)相鄰分段，并將它們合并為一個(gè)新的分段，這樣，總的分段數(shù)就減少了一個(gè)。選擇合并分段的依據(jù)是使下一步的誤差平衡系數(shù)Bk最小，此后，再不斷重復(fù)這步操作，直到分段數(shù)減至定值為止。

1.2  聚類

使用聚類過程的目的就是將矢量集合中的數(shù)據(jù)分組成為多個(gè)類，使得在同一個(gè)類中的對象之間具有較高的相似度,而不同類中的對象差別很大。K-means算法屬于聚類方法中的一種基本的劃分方法，它采用誤差平方和準(zhǔn)則函數(shù)作為聚類準(zhǔn)則函數(shù)。

本文的K-means算法提供了一種準(zhǔn)確、簡單高效的方法。假設(shè)矢量集合中有N個(gè)矢量樣本 {x1,x2,…,xN}，根據(jù)矢量特征計(jì)算歐氏距離時(shí)，可將矢量樣本分為K類。第k類的樣本數(shù)目為：

每類Ck的距離中心為為 (m1,m2,…,mK)，其中：

距離中心為最小化的目標(biāo)函數(shù)為：

由于某些時(shí)間的序列中的大部分?jǐn)?shù)據(jù)斜率變化程度都較小，且在矢量合并后，長矢量的個(gè)數(shù)在整個(gè)矢量集合中也比較少，特別是波動(dòng)周期越小，合并的長矢量數(shù)量也就越小。這個(gè)也是顯而易見的，因?yàn)椴▌?dòng)周期越小，合并后產(chǎn)生的平均誤差也就越大，合并的可能性也就小。在這種情況下，得到的結(jié)果具有明顯的分布稠密度，而這將導(dǎo)致傳統(tǒng)K-means聚類之后，各類的形狀和大小差別非常大，之后的符號化后，其結(jié)果將出現(xiàn)符號出現(xiàn)頻率不一致的、序列包含信息量少的情況。

為了解決這個(gè)問題，本文設(shè)計(jì)了再聚類后“折斷”方法來對聚類后類中個(gè)數(shù)較少的類進(jìn)行處理，這些類中包含的往往是模比較大的對象，計(jì)算這些類中的各個(gè)對象距各個(gè)中心點(diǎn)的距離，并將其歸為各類。與上次聚類不同的是，這次聚類對每個(gè)對象作倍數(shù)標(biāo)示，倍數(shù)q等于對象的模除以聚類中心點(diǎn)的模后取整，也就是說，新的聚類將原有較長的矢量變成了若干個(gè)短的矢量。

1.3  分配符號

聚類后，每個(gè)類都被賦予了一個(gè)類標(biāo)識(shí)符。其原則是同一個(gè)類的標(biāo)識(shí)符代表聚類中屬于同一類別；被“折斷”的對象用q個(gè)符號表示；對于較為關(guān)注的中心點(diǎn)的所在類，其標(biāo)志為特殊字母。比如本文將較大漲跌的類分別標(biāo)識(shí)為大寫字母表示，其余的用小寫字母表示。以這些類標(biāo)識(shí)符形式替代所有屬于該類的時(shí)間序列分段，即可得到所需的符號序列S。

2  模式抽取與識(shí)別

2.1  相關(guān)定義

下面先給出三個(gè)相關(guān)的參數(shù)定義。其中，|S|表示序列S的模，即序列S中包含符號的個(gè)數(shù)；Ia|表示符號a,受關(guān)注的程度，即本文中矢量的斜率IT代表模式T,在模式表中出現(xiàn)的次數(shù)。

2.2  抽取模式

本文采用的是基于定長序列的切割方法虬這種方法較為廣泛的應(yīng)用是在基于系統(tǒng)調(diào)用的入侵檢測等方面。在訓(xùn)練時(shí)，可利用滑動(dòng)窗口技術(shù)(窗口寬度為從輸入序列中進(jìn)行模式抽取，并輸出正常模式庫。如?=3,其訓(xùn)練序列為ACDBBDA，模式表示為：｛ACD,CDB,DBB,BBD,BDA｝。

在分析時(shí)，同樣可采用滑動(dòng)窗口技術(shù)進(jìn)行模式匹配，窗口每移動(dòng)一次，都與模式表中的模式相匹配。如果匹配成功,則得出結(jié)果；如果不成功，則繼續(xù)向下滑動(dòng)。抽取方法可使用如下兩種：

（1）完全抽取

采用定長窗口來切割全部序列，切割經(jīng)過實(shí)驗(yàn)測得的窗口刃大小取6較為理想，但是，完全抽取的缺點(diǎn)也很明顯,對于一個(gè)序列S,抽取的模式有|S|-1個(gè)，故其時(shí)間、空間復(fù)雜度都會(huì)增加，而且切割出來的模式繁冗、無用信息多、正確率低。

（2）不完全抽取

由于在符號序列中，期望得到的結(jié)果往往是斜率較大的信息，而且，由于時(shí)間序列波動(dòng)中具有一定的隨機(jī)性，因而其中的一些信息往往是不包含可用信息的，更加關(guān)注的是斜率較大的結(jié)果。所以，在切割序列的時(shí)候，每個(gè)窗口的最后一個(gè)符號為所關(guān)注的符號，即a|>e；如果不是，貝慵動(dòng)窗跳過。這樣切割出來的模式會(huì)大大減少，并且信息量少的模式也相應(yīng)地大量減少。

采用本算法切出的短序列的窗口值m越大，則復(fù)雜度越大，誤報(bào)率越低，漏報(bào)率越高@越小，復(fù)雜度越小，誤報(bào)率越高，漏報(bào)率較低。一般情況下，模式總是以一個(gè)或多個(gè)連續(xù)的斜率較大的符號結(jié)束的。

2.3  精簡及匹配

由上述方法可以得到一個(gè)原始的模式集合，其中，有些模式由于噪聲影響，本身就極少可能出現(xiàn)，故其數(shù)量較少，對于這種出現(xiàn)次數(shù)小于0模式的，即N(T)<6,可進(jìn)行刪減。另外，刪減掉以后，可能還有一些同樣的條件符號可以出現(xiàn)不同的結(jié)果，判斷哪一種出現(xiàn)的頻率較高，即設(shè)定閾值兀如果任何一種模式出現(xiàn)比例N(T)/￡N(T)潁，則將其他刪減掉；如果均未超過，則認(rèn)為是無用模式，全部刪減。例如一個(gè)模式cdedc一A出現(xiàn)了6次，另一模式cdedc一B出現(xiàn)了8次，出現(xiàn)頻率為0.429和0.571，均未超過閾值2=0.6,則這兩種模式都應(yīng)刪減掉。刪減后生成新的模式集合，它將作為訓(xùn)練結(jié)果對新的序列進(jìn)行匹配預(yù)測。

將目標(biāo)時(shí)間序列曲線進(jìn)行符號化，并使用訓(xùn)練好的模式集合來對其進(jìn)行匹配，如果出現(xiàn)了同樣的條件符號模式，則可得出目標(biāo)符號，從而得到所預(yù)測時(shí)間序列的未來趨勢。

3  實(shí)驗(yàn)結(jié)果

3.1  實(shí)驗(yàn)過程

完全抽取方法可選取10組授時(shí)系統(tǒng)的偏差作為學(xué)習(xí)數(shù)據(jù)，同時(shí)利用另外5組作為測試數(shù)據(jù)。

不完全抽取實(shí)驗(yàn)可選取60組授時(shí)系統(tǒng)偏差作為實(shí)驗(yàn)數(shù)據(jù)，并用其中的50組進(jìn)行學(xué)習(xí)，用另外的10組進(jìn)行測試。

首先，要對每組數(shù)據(jù)作矢量化處理，之后，再利用矢量形態(tài)相似性度量方法和改進(jìn)后的K-means聚類算法進(jìn)行聚類。實(shí)驗(yàn)表明，所采用的再聚類后“折斷”的方法，不但可以大大降低符號數(shù)量，同時(shí)可提高模式質(zhì)量。再聚類后的類個(gè)數(shù)為12,也就是說，產(chǎn)生了12個(gè)符號。

3.2  實(shí)驗(yàn)結(jié)果

匹配作為測試的10組數(shù)據(jù)，并將條件模式一樣的情況下的結(jié)果記為正確，反之記為錯(cuò)誤。如果有關(guān)注的符號沒有預(yù)測,則記為漏報(bào)。表1所列的是記錄了使用完全抽取以及不完全抽取方法時(shí)的正確率及漏報(bào)率數(shù)據(jù)，表2所列是ω取5,6,7時(shí)的正確率和誤報(bào)率。

通過測試結(jié)果可以看到，完全抽取方法雖然漏報(bào)率較低,但是，在計(jì)算時(shí)間、正確率方面的指標(biāo)都比不完全抽取要差。a的取值對精簡后模式的個(gè)數(shù)和正確率、誤報(bào)率影響很大，a越大，模式越少，正確率越高，同時(shí)漏報(bào)率也越高。

采用不完全抽取的最好正確率超過了80%,在時(shí)間序列分析預(yù)測中，達(dá)到了比較好的效果，可以用來對授時(shí)系統(tǒng)的時(shí)間偏差趨勢進(jìn)行預(yù)測。

4  結(jié)論

本文使用一種符號抽取方法對線性化分段并聚類過的時(shí)間序列進(jìn)行了模式抽取，并對真實(shí)數(shù)據(jù)進(jìn)行預(yù)測。預(yù)測結(jié)果較為理想，可以較好地對某授時(shí)系統(tǒng)的時(shí)間偏差進(jìn)行預(yù)測分析，也可以提高授時(shí)系統(tǒng)精度，其結(jié)果還可以作為授時(shí)系統(tǒng)故障診斷以及故障預(yù)測的依據(jù)。該方法算法適用性強(qiáng)，對于其他應(yīng)用領(lǐng)域，如定位精度的預(yù)測，可根據(jù)數(shù)據(jù)對象的特點(diǎn)設(shè)置參數(shù)以及使用不同的聚類算法和模式抽取算法，來進(jìn)一步增強(qiáng)預(yù)測效果。

20210904_61324aa9ea88c__一種符號化的授時(shí)偏差預(yù)測方法