基于集成回聲狀態網絡Fisher核的時間序列分類算法

王 勁 松

(中國科學技術大學計算機科學與技術學院中國科大-伯明翰大學智能計算與應用聯合研究所 安徽 合肥 230027)

0 引 言

在許多實際應用領域都會產生大量的時序數據，比如股票交易[1]、電力系統[2]和工業觀測[3]等。時序數據是一種結構化的數據，具有高維、變長、數值之間存在時序依賴關系等特點。研究人員提出了很多有效的時間序列分類算法。早期基于歐氏距離和動態時間規整距離的最近鄰算法采用歐氏距離或動態時間規整距離來度量兩個時序樣本之間的距離[4-6]，雖然歐氏距離計算在某些情況下比較高效，以及動態時間規整距離算法可以解決時序變長問題，但當前基于距離的方法本質上還是基于點與點的比較，難以捕捉到隱藏在序列中動態的時序依賴信息?；谔卣鞯姆椒ǖ暮诵乃枷胧遣捎酶鞣N技術從原始時序數據中提取出具有鑒別力的特征[7-8]。盡管相關實驗表明基于特征的方法可以很好地提取序列中的局部信息，但是巨大的特征搜索空間和繁重的數據預處理使得此類方法時間開銷大。

另一類基于模型的方法先是用一個特定的生成模型對時序數據的分布進行擬合，為每條時序樣本學習一個函數模型，然后基于函數模型之間的差異來度量原始時序樣本之間的距離，例如：基于隱馬爾可夫模型的概率積核[9]、Fisher核[10]以及基于高斯混合模型的散度核[11]等。相關研究工作[12]討論并分析了此類方法度量結構化時序數據的優勢。由于數據背后指定的生成模型的假設有時過于嚴格，限制了模型對時序樣本的近似能力。近幾年，一類高效的非線性儲蓄池模型被用來處理時間序列，其中回聲狀態網絡(Echo State Network，ESN)模型[13]受到較多關注。動態狀態規整算法[14]將原始的時序數據映射到儲蓄池的隱狀態空間中，然后基于經典的動態時間規整距離來度量轉換的隱狀態序列，提高了模型的分類性能。文獻[15]利用ESN的讀出權重對噪音數據進行分類，驗證了回聲狀態網絡具有一定的魯棒性。Ma等[16]用時變輸出函數替換ESN的輸出權重，并將時間聚合運算引入輸出層，將時間信號投影到離散類標簽中。

盡管基于回聲狀態網絡模型的時序分類算法利用非線性的儲蓄池來擬合時序動態的生成機制，然而對于這種非歐的模型空間，傳統的歐氏距離度量方法已經不能滿足要求。文獻[17-18]表明學習出有鑒別力的距離度量方式有助于提高模型的分類能力。此外，文獻[19]證明了在單個數據表示的情況下，采用集成方法可以提高時序算法的分類性能。目前基于ESN的時間序列算法分類準確度還有待提高，究其原因，基于單個回聲狀態網絡模型的時間序列分類算法不能很好地擬合數據復雜的分布結構，因此，本文嘗試引入AdaBoost集成方法[20]訓練出多個模型來緩解這一問題。

本文提出一種基于集成回聲狀態網絡和Fisher核的時間序列分類算法(Fisher Kernel based on Integration of ESNs，FKIESN)。該模型先用回聲狀態網絡模型對時間序列進行建模，捕捉序列中隱藏的動態信息，然后在模型的參數空間中采用Fisher核來度量函數模型之間的差異。由于回聲狀態網絡是一個預測模型而非分類模型，傳統的AdaBoost分類算法不能直接應用，本文引入了AdaBoost回歸框架訓練出多個模型，在特征層面上完成加權集成，提高了模型的分類能力。

1 回聲狀態網絡與Fisher核

1.1 回聲狀態網絡

如圖1所示,回聲狀態網絡是循環神經網絡的一種改進版本，主要由輸入層、水庫層和輸出層組成。三層的神經元數量分別為D、N和O。圖中，實線箭頭表示固定和隨機連接，虛線箭頭表示可訓練的連接。

圖1 標準回聲狀態網絡結構圖

不考慮輸出層到水庫層連接的簡化回聲狀態網絡可以通過下式進行訓練：

x(t+1)=f(Wx(t)+Winu(t))

y(t+1)=Woutz(x(t+1))

(1)

式中：Win∈RN×D代表輸入神經元到水庫神經元的連接權值;W∈RN×N表示水庫內部神經元之間的連接權值；Wout∈RO×(N+D)代表水庫神經元到輸出神經元的連接權值(讀出映射)；u(t)∈RD是網絡當前時刻的輸入；x(t)∈RN表示當前時刻水庫的狀態；z(t)=[x(t);u(t)]表示考慮輸入時的當前系統狀態；f(·)表示水庫神經元的激活函數，一般是tanh函數。防止初始瞬態的影響，從tmin+1時刻開始保存系統狀態Z=[z(tmin+1),z(tmin+2),…,z(tmin+l)]，其中l代表訓練樣本的長度。假設期望輸出矩陣為Y=[y(tmin+1),y(tmin+2),…,y(tmin+l)]，則通過最小二乘法可學習到讀出映射：

Wout=(ZTZ)-1ZTY

(2)

為了防止過擬合，通常引入正則化參數，則讀出映射為：

Wout=(ZTZ+λI)-1ZTY

(3)

式中：λ是正則化系數，I是單位矩陣。

回聲狀態網絡兩個典型的特點是擁有一個不需要訓練的高維非線性動態水庫和一個可以高效訓練的讀出映射，其中輸入權值矩陣和水庫權值矩陣都是隨機化產生，而讀出映射通過線性回歸訓練得到。通過考慮當前輸入和先前的歷史信息，回聲狀態網絡模型可以捕捉到隱藏在時序數據中的動態信息。回聲狀態網絡是一個預測模型而非分類器，盡管研究學者已經提出了一些基于回聲狀態網絡的高效分類模型，該領域還有很多值得研究的問題。

1.2 Fisher核

生成方法擬合類條件概率密度函數，而判別方法專注于直接分類。Fisher核[21]能夠結合生成方式和判別方式的優勢，假定P(u|θ)為一個概率生成模型，其中θ是模型參數，則Fisher核可將時序樣本u編碼成一個費希爾分數向量：

Uu=▽θlog(P(u|θ))

(4)

給定兩條時間序列樣本a和b，其對應的費希爾分數分別為Ua和Ub，則Fisher核測量的距離為：

(5)

式中：F=Es{▽θlog(P(S|θ))▽θlog(P(S|θ))T}為費希爾信息矩陣；S為訓練樣本集；Es是期望。似然函數通常比較復雜，很難計算對應的期望，通常采用訓練集進行經驗期望估計，則：

(6)

2 算法設計

2.1 基于回聲狀態網絡的Fisher核

根據以上關于回聲狀態網絡和Fisher核的介紹，本文利用回聲狀態網絡來建模時間序列樣本，在回聲狀態網絡模型的參數空間中利用Fisher核來度量函數模型之間的差異，并給出相應的公式推導。

引入噪音假設的基于回聲狀態網絡的概率生成模型如下：

x(t+1)=f(Wx(t)+Winu(t))

y(t+1)=Woutz(x(t+1))+b+ε(t)

(7)

式中：b為截距。

假設獨立同分布，噪音模型ε(t)服從高斯分布:

ε(t)=N(0,σ2I)

(8)

則u(t+1)的條件概率為：

P(u(t+1)|u(1),u(2),…,u(t))=P(u(t+1)|x(t))=

(9)

給定一條長度為l的時間序列，用p(u(1,2,…,l))來簡化表示模型的似然函數p(u(1),u(2),…,u(l))，則似然函數為：

(10)

因此，對數似然p(u(1,2,…,l))的偏導數為：

(11)

式中：偏導數U是一個O×N的矩陣，噪音方差σ2可以從原始序列和模型預測輸出中估計得出。給定兩個時間序列ui和uj，計算出序列對應的生成函數模型的偏導數Uui和Uuj，Fisher核度量可以通過式(5)獲得。Fisher核認為同類樣本若能夠以相同的方式“拉伸”生成模型的參數，表明這兩個樣本在給定的參數模型上具有某種相似性，用這種相似性來度量原始時序樣本的距離。

2.2 基于Fisher核的時間序列集成算法

假設給定包含M個時間序列樣本的訓練集S={u1,u2,…,uM}，圖2描繪了模型的結構。

圖2 算法的集成訓練過程

對于第i個ESN基模型BMi而言，為每條時間序列學習出一個函數模型，得到對應的訓練誤差以及模型的讀出映射，Di表示樣本的權重，Wi是第i個基模型在全部訓練樣本上獲得的讀出映射矩陣，根據訓練每個樣本所產生的誤差，我們可以計算出第i個基模型在本輪訓練的回歸誤差ei，根據回歸誤差和樣本的權重，可以計算出第i個基模型的權重mi以及更新樣本下一輪的權重Di+1。Ui表示第i個基模型為全部訓練樣本學習出的費希爾分數矩陣，矩陣的每一行表示一個樣本所對應的費希爾分數向量。依次進行，最終獲得B個基模型。在訓練過程中，上一輪被錯分的樣本的權重將會增加，被正確分類的樣本的權重將會降低，更新權重后的樣本將會被用于下一輪的訓練，下一輪的基模型將會更加關注那些錯分的時序樣本。獲得每個基模型學習到的費希爾分數矩陣之后，本文重新計算了一個新的費希爾分數矩陣，此矩陣的每一行是每個基模型學習到的費希爾分數矩陣對應行的加權和，即：

(12)

式中：Vj表示針對時序樣本uj所訓練出的集成費希爾分數向量。得到最終的費希爾分數向量之后，可以根據式(5)計算出對應的Fisher核矩陣，采用SVM核方法來完成分類任務。算法1描述了整個訓練過程的細節。

算法1基于集成回聲狀態網絡的Fisher核學習

1. 輸入：時間序列數據集S，儲蓄池尺寸N，嶺回歸參數λ，基模型個數B

2. 輸出：Fisher核矩陣

3. 初始化時序樣本權重

4.D1={sw11,sw12,…,sw1M},sw1k=1/M

5. fori=1 toBdo

6. 生成一個弱的分類器BMi，從帶權重的時序樣本集中學習出讀出映射Wi

7. 統計出訓練樣本上的最大誤差Ek=max(NMSEk)，NMSEk是擬合第k個樣本所產生的歸一化的均值平方誤差

8. 計算每個樣本的相對誤差

9.eik=NMSEk/Ek,k=1,2,…,M

10. 計算基模型的回歸誤差

12. 獲得基模型的權重

14. 更新樣本權重分布

16. 通過式(11)計算出費希爾分數矩陣

17. end for

18. 獲得每個樣本的加權和的費希爾分數表示

20. 計算出Fisher核矩陣，矩陣中的每個元素通過式(5)得出

3 實 驗

本節首先在人工合成數據集上驗證了FKIESN具有一定的魯棒性，其次在時間序列基準數據上與其他基線模型進行了性能對比實驗，相關的參數分析實驗在本節的最后給出。

3.1 實驗設置

本節采用的對比算法有：基于歐氏距離的最近鄰算法(ED)[14]、最大間隔最近鄰(LMNN)[4]、基于動態時間規整的最近鄰算法(DTW)[6]、詞袋模型(TSBF)[7]、基于shapelet轉型算法(ST)[8]、基于儲蓄池的核方法(RV)[15]和基于費希爾儲蓄池的核方法(FisherRV)[18]。在RV和FisherRV中，核寬度γ通過5折交叉驗證選擇，搜索范圍為{10-5,10-4,…,101}，嶺回歸超參數λ的搜索范圍為{10-5,10-4,…,101}。為防止過擬合，FKIESN中基模型水庫大小最優設置為5，基模型個數設置為10。本文采用LIBSVM工具包中的SVM算法來進行分類任務，一對一策略用來解決多分類任務，通過交叉驗證在{10-3,10-2,…,103}范圍內選擇出最優的正則化參數C。在訓練集上使用交叉驗證選擇模型后，將所選模型在整個訓練集上重新訓練一次，并在測試集上進行評估。

3.2 魯棒性分析

首先利用非線性自回歸滑動平均(Nonlinear Autoregressive Moving Average,NARMA)系統[22]生成10、20和30階的時間序列，產生公式如下：

1.5u(t-9)u(t)+0.1

(13)

1.5u(t-19)u(t)+0.01)+0.2

(14)

1.5u(t-29)u(t)+0.201

(15)

式中：y(t)和u(t)分別是當前時刻的輸出和輸入。這三種序列從相同的輸入u中產生，u是從[0,0.5]區間上均勻隨機產生，三類序列的產生長度都是80 000，圖3描繪了三類不同的NARMA序列。每條序列被分割成100條長度為800的子序列，每種類別的50條子序列分到訓練集，剩下的50條分到測試集，最終獲得大小都是150條子序列的訓練集和測試集。向這些數據集中添加高斯白噪聲，噪聲的均值為零，方差分別為0.1、0.2、0.3、0.4、0.5}。這樣設置的目的是可以清楚地顯示模型的性能變化趨勢。實驗中，對于每個噪音級別，生成合成序列5次，每次在合成數據集上重復10次實驗，將平均分類準確度作為最終的評估結果。圖4展示了實驗的最終結果。

圖3 三種類別的NARMA時間序列(10、20和30)

圖4 模型在不同噪音級別下的分類錯誤率

可以看出，與對比算法相比，FKIESN對噪音更具魯棒性。DTW對噪音比較敏感的原因是它本質上還是基于點與點的比較，這將導致它對序列的形狀有很強的依賴，然而，高斯噪音的加入改變了原始序列的變化幅度，使得DTW的分類性能受到較大的影響。RV將原始序列從數據空間映射到模型空間中，適當地降低了噪音帶來的影響，在噪音數據集上獲得了僅次于FKIESN的分類性能。FKIESN不僅采用Fisher核在模型空間中合適地度量函數模型之間的距離，還引入AdaBoost訓練出多個基模型來擬合數據復雜的分布結構，進一步降低了噪音的影響。

3.3 分類性能比較

本文在12個來自UCR[23]的時間序列基準數據集上比較FKIESN和其他基線模型的分類性能，數據集都被分割成訓練集和測試集，詳細信息如表1所示。

表1 12個UCR時間序列基準數據集的詳細信息

實驗結果如表2所示，在每個數據集上，可以看出FKIESN在大部分數據集上優于其他基線模型。具體而言，FKIESN在9個數據集上比基于距離的方法和基于模型的方法表現出色，同時在大部分數據集上優于基于特征的方法。隱藏在長序列中的模式信息通常很難捕捉，值得一提的是，對于長序列數據集，比如RefDevices、SmlKitApp和WormsTC，本文算法與其他對比算法相比仍舊有比較低的分類錯誤率，原因可能在于本文使用多個模型捕捉長序列中的復雜模式。對于每個數據集，本文將8個算法進行排序，具有最小分類錯誤率的算法獲得名次1，以此類推，具有最大分類錯誤率的算法則獲得名次8，具有相同分類錯誤率的算法獲得相同的名次，然后統計各個算法在12個數據集上的平均排名，如表2倒數第二行所示，可以看出FKIESN在平均排名上明顯地優于其他算法，ED則獲得了最差的平均排名?？紤]到平均排名評價準則是一種無偏的度量方法，對模型池的選擇和大小很敏感，本文采用一種更加魯棒的評價準則[24]：

(16)

(17)

式中：ek和ck分別代表模型i在數據集k上的分類錯誤率以及數據集包含的類別數量，數據集上每種類別的誤差用PCEk表示，MPCEk表示模型在所有數據集上的平均每種類別的誤差。表2的最后一行給出了最終的計算結果?？梢钥闯?，FKIESN在MPCE上表現優異，基于模型的方法RV和FisherRV次之，基于距離的兩個算法(DTW和LMNN)與基于特征的兩個算法在MPCE上性能相當，ED算法還是表現最差。

表2 FKIESN與對比算法在12個基準數據集上的分類錯誤率

3.4 相關參數分析

當儲蓄池神經元數量設置太大時，經典的ESN模型會出現過度擬合的現象，本節將探究儲蓄池大小對FKIESN分類性能的影響。實驗中，保持其他參數不變，改變儲蓄池規模的大小，改變范圍為N∈{5,10,20,30,40,50,60,70,80,90,100}。對于特定的儲蓄池規模，在每個數據集上重復做20次實驗，取20次實驗結果的平均值作為最終的結果。圖5展示了模型在Beef和BeetleFly兩個時間序列基準數據集上的表現。

圖5 不同儲蓄池規模對模型分類準確度的影響

可以看出，儲蓄池大小對模型產生很大的影響，隨著儲蓄池神經元的增多，模型在數據集上的分類性能總體呈現下降趨勢。儲蓄池神經元的增多，導致基模型的擬合能力增強，這與AdaBoost集成學習要求基模型是一個弱分類器的事實相違背，多個過強的基模型提取過多的冗余信息，反而導致模型的分類性能下降。

4 結 語

本文基于回聲狀態網絡和Fisher核，提出了一種時間序列集成模型FKIESN?；诨芈暊顟B網絡的Fisher核在模型空間中度量函數模型之間的差異，同時在特征層面上引入AdaBoost集成，利用多個模型來擬合數據復雜的分布結構，提高了算法的分類性能。除此之外，FKIESN是基于回聲狀態網絡生成模型，它很自然地解決了時間序列變長問題以及能捕捉序列中的動態信息，不僅在大多數時間序列基準數據集上優于對比的基線模型，也在人工合成數據集上表現出較好的魯棒性。

本文提出的框架具有開放性，未來將在模型空間中繼續探索其他有效的距離度量方式，提高模型的分類性能，同時針對海量序列樣本且序列比較長的分類問題，在保證分類性能的同時，加快模型的分類速度。