引言

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

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

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

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

1  時間序列符號化

1.1  線性化分段

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

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

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

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

1.2  聚類

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

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

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

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

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

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

1.3  分配符號

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

2  模式抽取與識別

2.1  相關(guān)定義

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

2.2  抽取模式

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

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

（1）完全抽取

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

（2）不完全抽取

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

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

2.3  精簡及匹配

由上述方法可以得到一個原始的模式集合，其中，有些模式由于噪聲影響，本身就極少可能出現(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)為是無用模式，全部刪減。例如一個模式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)時間序列曲線進(jìn)行符號化，并使用訓(xùn)練好的模式集合來對其進(jìn)行匹配，如果出現(xiàn)了同樣的條件符號模式，則可得出目標(biāo)符號，從而得到所預(yù)測時間序列的未來趨勢。

3  實驗結(jié)果

3.1  實驗過程

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

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

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

3.2  實驗結(jié)果

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

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

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

4  結(jié)論

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

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