基于圖拉普拉斯變換和極限學習機的時間序列預測算法

鄒 小 云

(湖北職業技術學院公共課部 湖北 孝感 432000)

0 引 言

在許多領域內均存在多元的時間序列數據[1]，如互聯網中服務器的通信流量數據、虛擬現實技術的人體運動捕捉數據[2]和病人的腦電波實時監測數據等。多元時間序列一般伴隨著高維數據的屬性，導致多元時間序列的預測難度升高，且難以在合理的時間內取得理想的預測準確率[3]。

目前研究人員大多以時間為約束條件，以最大化預測準確率為研究目標，設計了不同的多元時間序列預測算法。文獻[4]提出了基于無核相關向量機的多元時間序列預測算法，利用無核相關向量機不受核函數約束的特性，構建了高維特征空間。但無核相關向量機的非線性擬合能力不足，導致多元時間序列的預測準確率較低。文獻[5]通過因子分析提取高維儲備池狀態矩陣的公因子，利用降維后的因子變量與期望輸出之間的線性回歸關系，求解神經網絡的未知參數。文獻[6]采用集群卷積神經網絡對多元時間序列進行預測，提出了訓練階段新的數據結構，通過協方差矩陣對時間序列進行快速分類。該網絡通過卷積運算和下采樣自動對時間域特征和空間域特征進行選擇，獲得了較好的預測效果。但該網絡模型需要實時更新卷積層參數、隱層單元數量和權重向量等超參數，訓練時間過長。文獻[7]通過遞歸神經網絡預測多元時間序列的類別，該算法的準確率較高，但是對每個新到達時間序列需要很多輪數才能達到收斂?？傮w而言，基于神經網絡的預測算法具有學習能力強的優勢，但存在網絡參數學習難度大的問題。當前的時間序列學習方法大多基于前饋神經網絡實現，并通過梯度下降法和后向傳播算法實現在線地學習和更新，但梯度下降法和后向傳播需要很長的訓練時間和復雜的參數調節。

為了解決上述問題，本文提出了基于圖拉普拉斯特征提取和極限學習機(Extreme Learning Machine,ELM)在線學習的多元時間序列預測算法。將標記觀察樣本和無標記觀察樣本分別構建圖拉普拉斯的散布矩陣，再利用圖拉普拉斯相關理論提取時間序列的特征子集。設計了新的時間序列在線極限學習機，該模型隨機初始化隱層單元數量，在線學習程序通過最小二乘法遞歸地逼近問題最優解，從而更新網絡的輸出權重。在線學習過程中僅需要學習和更新隱層和輸出層之間的權重即可完成訓練。本文的貢獻主要如下：(1) 提出基于圖拉普拉斯的稀疏特征選擇方法，利用凸l2-p范數(p=1)和非凸l2,p范數(0

1 多元時間序列的特征選擇

1.1 基于圖拉普拉斯的特征選擇問題模型

本文基于圖拉普拉斯建模特征學習問題[8]，計算特征選擇的稀疏變換向量，采用l2-p范數保證向量的稀疏性，使其符合特征選擇的問題模型。圖1是時間序列特征提取流程。設X=[x1,x2,…,xl,xl+1,…,xn]T∈Rd×n為訓練數據矩陣，X=[x1,x2,…,xl]T∈Rd×l為X的標記訓練數據，n為訓練數據的數量，l為標記訓練數據的數量。xi∈Rd(1≤i≤n)表示第i個訓練樣本，Y=[y1,y2,…,yl]T∈Rl表示訓練數據的標記向量，yi∈R(1≤i≤l)為第i個標記樣本的標記。定義W∈Rd為特征選擇問題的變換向量。

圖1 時間序列特征提取流程

1.2 時間序列的特征選擇模型

將l2-p范數引入圖拉普拉斯矩陣，以實現降維處理，目標函數定義為：

(1)

第1個散布矩陣定義為圖拉普拉斯的監督散布矩陣和無監督散布矩陣的結合，其計算式為：

(2)

(3)

式中：Lunsup∈Rn×n為訓練數據的無監督圖拉普拉斯矩陣?；谌繑祿⒔張DGunsup，每個節點對應一個觀察數據。如果xi屬于xj的k-近鄰，或者xj屬于xi的k-近鄰，則在兩個樣本間建立連接。圖Gunsup中邊權重的計算式為：

(4)

(5)

式中：Lsup∈Rl×l為標記數據的監督圖拉普拉斯矩陣。

基于標記數據建立監督近鄰圖Gsup，每個標記數據為一個節點，根據觀察樣本的標記信息在相似的樣本之間建立連接。圖Gsup的權重矩陣Ssup定義為：

(6)

第2個散布矩陣定義為：

M2=XLSemiXT

(7)

式中：Lsemi∈Rn×n為半監督圖拉普拉斯矩陣，表示標記數據的標記信息和局部結構信息。為了計算半監督圖拉普拉斯矩陣Lsemi，首先使用所有數據建立近鄰圖Gsemi，圖Gsemi的權重矩陣Ssemi定義為：

(8)

式中：dist為每對樣本的距離矩陣，其定義為：

(9)

1.3 多元時間序列的特征選擇

(10)

通過拉格朗日乘法求解式(10)的優化問題，式(10)轉化為：

(11)

式(11)對W求導，可得：

(12)

式(12)說明W為R=M+(2/p)λD的特征向量，“∧”為特征值。目標問題是最小化式(1)的問題，即選擇特征值最小的特征向量來最小化目標函數。

算法1是計算l2-p范數的迭代搜索求解算法，其中，第5行迭代地求解了l2,p范數的最小化問題。

算法1l2-p范數的迭代搜索求解算法

輸入：訓練數據X∈Rd×n,標記訓練數據X∈Rd×l,標記訓練數據的標記向量Y∈Rl,泛化參數λ。

輸出：選擇的特征。

//式(3)

//式(5)

3. 計算半監督散布矩陣M1和M2;

//式(2)和式(7)

4. 初始化:t=0,Wt∈Rd;

//隨機初始化Wt

5. while未達到收斂條件do

計算對角矩陣：

Rt=M+(2/p)λDt;

更新Wt+1=r1;

//r1為Rt的特征向量

t=t+1;

end while

計算無監督圖拉普拉斯矩陣的復雜度和半監督拉普拉斯矩陣的復雜度均為O(n2)，Rt特征分解的復雜度為O(d3)，特征排序的復雜度為O(dlogd)。因此特征選擇的總體復雜度為O(n2)+O(d3)+O(dlogd)。

2 時間序列的極限學習機

2.1 極限學習機

考慮一個單層前饋神經網絡的ELM模型：

(13)

式中：gi(·)對應第i個隱層單元的激活函數G(ai,bi,x)；x∈Rd，βi∈Rm，d為輸入層節點的數量，m為輸出層節點的數量；L為隱層節點的數量；ai為輸入層和隱層的連接權重；bi為輸入層偏差向量；βi為隱層和輸出層的連接權重。gi定義為：

gi=G(ai,bi,x)=g(ai·x+bi)

(14)

式中：ai∈Rd,bi∈R。采用徑向基激活函數(Radical Basis Function,RBF)，其計算式為：

(15)

式中：ai∈Rd,bi∈R。假設共有N個實例(xi,ti)∈Rd×m，網絡的輸出oj定義為：

(16)

式中：j=1,2,…,N。

(17)

式中：j=1,2,…,N。式(17)的廣義形式為：

Hβ=T

(18)

(19)

(20)

(21)

式(18)中：H為隱層輸出的矩陣，H的第i列對應第i個單元的輸出；x1,x2,…,xN為輸入。h(x)=G(a1,b1,x),G(a2,b2,x),…,G(aL,bL,x)為隱層的特征映射函數。

本文將隱層單元的數量設為隨機數，所以通過最小二乘解直接估計權重向量βi，訓練ELM網絡的目標等價于尋找線性系統Hβ=T的最小二乘解βms：

(22)

一般情況的隱層單元數量遠小于數據量，即L<

βms=H?T

(23)

式中：H?表示H的Moore-Penrose廣義逆矩陣。

在線ELM通過式(23)計算矩陣βms，Moore-Penrose廣義逆矩陣的計算式為：

H?=(HTH)-1HT

(24)

將式(24)代入式(23)，矩陣βms變為：

βms=(HTH)-1HTT

(25)

(26)

(27)

(28)

其中：Tk+1和Hk+1定義為：

(29)

(30)

3 在線ELM的學習算法

在線ELM的學習程序總結為以下5個步驟：

① 初始化階段。估計時間k的初始化矩陣βk，通過計算協方差直接估計Rk。

④ 在網絡中傳播狀態βk和誤差協方差矩陣。

⑤ 校準網絡的狀態βk和誤差協方差矩陣。

4 實 驗

4.1 實驗方法和參數設置

實驗環境為PC機，Windows 10操作系統，Intel Core i5處理器，主頻為3.10 GHz，內存為8 GB。編程環境為MATLAB R2014b。

選擇6個公開的多元時間序列數據集作為本文的benchmark數據集，如表1所示。將SinC之外的5個數據集屬性值均歸一化為[0,1]區間，SinC數據集的屬性值歸一化為[-1,1]區間。按照50%、25%和25%的比例將每個數據集分別劃分為訓練集、驗證集和測試集。

表1 數據集的基本屬性信息

網絡的訓練程序和測試程序均采用根均方誤差(RMSE)作為評價指標，其計算式為：

(31)

每組參數的實驗重復若干次，使實驗結果的置信度達到α=0.05。實驗將本文算法的參數t設為0.1，μ設為1(兩個散布矩陣重要性相同)，參數p設為0.5?；€學習機隱層節點數量等于數據集的維度。

4.2 多元時間序列的特征選擇實驗

采用3個維度較高的時間序列數據集Lorentz、Mackey-Glass和Rossler數據集驗證本文特征選擇算法的降維效果，選擇幾個支持時間序列特征選擇的算法作為對比方法。對比方法分別為：MODIS[9]、TSD[10]、RHFE[11]、CFAP[12]和FBDST[13]。其中：MODIS采用隨機森林估計每個特征的重要性得分，再利用Jeffries-Matusita距離度量每個時間序列的類分離性；TSD通過時間序列的特征判別能力將選擇判別能力強的特征子集；RHFE是一種基于直方圖統計的時間序列特征選擇算法；CFAP是一種支持海量數據的時間序列特征選擇算法；FBDST是一種基于標記符號檢測的時間序列特征選擇算法。

采用4個分類指標評價特征選擇的效果，包括：預測活動值R2、RMSE、平均絕對誤差(Mean Absolute Error,MAE)和一致性相關系數(Concordance Correlation Coefficient,CCC)。

R2的計算式為：

(32)

MAE的計算式為：

(33)

式中：n為測試集的樣本數量。

CCC的計算式為：

(34)

R2和CCC的值越大說明時間序列預測算法的性能越好，MAE和RMSE的值越小說明性能越好。

圖2所示為時間序列特征選擇算法提取的特征數量?？梢钥闯霰疚乃惴▽τ?個時間序列提取的特征數量均低于其他對比算法。因此，本文基于圖拉普拉斯的特征選擇算法具有較好的降維效果。圖3所示為不同算法對3個時間序列的分類準確率結果?？梢钥闯?，本文算法的MAE和RMSE值均低于其他5個對比算法，而R2和CCC值均高于其他5個對比算法，說明本文算法的分類性能優于其他5個特征選擇算法。綜合特征選擇的實驗結果可得出結論：本文算法對時間序列實現了較好的降維效果，并且有助于后續的分類處理和預測處理。

圖2 時間序列特征選擇算法提取的特征數量

(a) R2指標

4.3 時間序列的預測性能實驗

采用表1的6個時間序列數據集驗證本文時間序列預測算法的預測效果，選擇5個預測性能優秀的算法作為比較方法，分別為：FS-ELM[9]、OS-ELM[10]、MC-ELM[11]、FDS-ELM[12]和MMA-SLA[13]。FS-ELM將隨機森林和極限學習機結合。OS-ELM通過選擇判別能力強的特征，提高極限學習機的效率和泛化性能。MC-ELM引入直方圖建模時間序列的走勢，對噪聲具有較強的魯棒性。FDS-ELM也是一種將特征選擇和極限學習機結合的算法，增強了極限學習機的效率和泛化性能。對比方法的模型采用對應文獻內推薦的參數。

MMA-SLA對單層前饋神經網絡進行了進一步的簡化處理，其實驗結果表明該網絡對時間序列的預測效果優于許多經典的網絡模型。

為了觀察激活函數對極限學習機預測性能的影響，實驗中極限學習機和MMA-SLA分別在RBF和Sigmod兩種激活函數的網絡模型下完成了預測實驗。圖4所示為時間序列預測實驗的結果，本文算法對Istanbul、Lorentz、Mackey-Glass、Rossler和Wine共5種數據集的平均預測誤差均明顯低于其他5種算法，并且兩種激活函數獲得了相同的結論。本文算法對于SinC數據集的平均預測誤差和FS-ELM、OS-ELM、FDS-ELM較為接近，SinC數據集的維度較低(僅為2)，本文算法的特征選擇程序未能發揮作用。

(a) RBF激活函數

5 結 語

為了提高多元時間序列預測算法的預測準確率，提出基于圖拉普拉斯變換和極限學習機的時間序列預測算法。將標記觀察樣本和無標記觀察樣本分別構建圖拉普拉斯的散布矩陣，再利用圖拉普拉斯相關理論提取時間序列的特征子集。設計了新的時間序列在線極限學習機，在線學習程序通過最小二乘法遞歸地逼近問題最優解，從而更新網絡的輸出權重。

本文的特征選擇程序和后續的極限學習機程序是兩個分離的模塊，未來將研究把特征提取的迭代程序和極限學習機的迭代程序融合，從而提高總體的學習速度并降低迭代的次數。