姜逸凡 葉青

摘 要：在時(shí)間序列分類(lèi)等數(shù)據(jù)挖掘工作中，不同數(shù)據(jù)集基于類(lèi)別的相似性表現(xiàn)有明顯不同，因此一個(gè)合理有效的相似性度量對(duì)數(shù)據(jù)挖掘非常關(guān)鍵。傳統(tǒng)的歐氏距離、余弦距離和動(dòng)態(tài)時(shí)間彎曲等方法僅針對(duì)數(shù)據(jù)自身進(jìn)行相似度公式計(jì)算，忽略了不同數(shù)據(jù)集所包含的知識(shí)標(biāo)注對(duì)于相似性度量的影響。為了解決這一問(wèn)題，提出基于孿生神經(jīng)網(wǎng)絡(luò)（SNN）的時(shí)間序列相似性度量學(xué)習(xí)方法。該方法從樣例標(biāo)簽的監(jiān)督信息中學(xué)習(xí)數(shù)據(jù)之間的鄰域關(guān)系，建立時(shí)間序列之間的高效距離度量。在UCR提供的時(shí)間序列數(shù)據(jù)集上進(jìn)行的相似性度量和驗(yàn)證性分類(lèi)實(shí)驗(yàn)的結(jié)果表明，與ED/DTW-1NN相比SNN在分類(lèi)質(zhì)量總體上有明顯的提升。雖然基于動(dòng)態(tài)時(shí)間彎曲（DTW）的1近鄰（1NN）分類(lèi)方法在部分?jǐn)?shù)據(jù)上表現(xiàn)優(yōu)于基于SNN的1NN分類(lèi)方法，但在分類(lèi)過(guò)程的相似度計(jì)算復(fù)雜度和速度上SNN優(yōu)于DTW?？梢?jiàn)所提方法能明顯提高分類(lèi)數(shù)據(jù)集相似性的度量效率，在高維、復(fù)雜的時(shí)間序列的數(shù)據(jù)分類(lèi)上有不錯(cuò)的表現(xiàn)。

關(guān)鍵詞：時(shí)間序列;相似性度量;神經(jīng)網(wǎng)絡(luò);孿生神經(jīng)網(wǎng)絡(luò)

中圖分類(lèi)號(hào)：TP391

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-9081（2019）04-1041-05

Abstract： In data mining such as time series classification， the similarity performance based on category of different datasets are significantly different from each other. Therefore， a reasonable and effective similarity measure is crucial to data mining. The traditional methods such as Euclidean Distance （ED）， cosine distance and Dynamic Time Warping （DTW） only focus on the similarity formula of the data themselves， but ignore the influence of the knowledge annotation contained in different datasets on the similarity measure. To solve this problem， a learning method of time series similarity measure based on Siamese Neural Network （SNN） was proposed. In the method， the neighborhood relationship between the data was learnt from the supervision information of sample tags， and ?an efficient distance measure between time series was established. The similarity measurement and confirmatory classification experiments were performed on UCR-provided time series datasets. Experimental results show that compared with ED/DTW-1NN（one Nearest Neighbors）， the overall classification quality of SNN is improved significantly. The Dynamic Time Warping （DTW）-based 1NN calssification method outperforms the SNN-based 1NN classification method on some data， but SNN outperforms DTW in complexity and speed of similarity calculation during the classification. The results show that the proposed method can significantly improve the measurement efficiency of the classification of dataset similarity， and has good performance for high-dimensional and complex time-series data classification.

Key words： time serie; similarity measure; neural network; Siamese Neural Network （SNN）

0?引言

時(shí)間序列是某一事件隨著時(shí)間的推移產(chǎn)生的一系列數(shù)據(jù)，由一定的時(shí)間間隔提取采集得到，對(duì)于時(shí)間序列的數(shù)據(jù)挖掘在工業(yè)、農(nóng)業(yè)、經(jīng)濟(jì)、醫(yī)療等領(lǐng)域時(shí)間序列都有廣泛的應(yīng)用，例如證券市場(chǎng)的基金、股票數(shù)據(jù)分析研究[1]、輔助心電圖疾病診斷[2]等。時(shí)間序列的分類(lèi)（Time Series Classification， TSC）等數(shù)據(jù)挖掘研究關(guān)鍵之一是時(shí)間序列之間的相似性度量，不同的相似性度量方法對(duì)時(shí)間序列的挖掘性能有很大的影響。目前主流的時(shí)間序列相似性度量使用L-P范數(shù)距離（如歐氏距離（European Distance， ED））和動(dòng)態(tài)時(shí)間彎曲（Dynamic Time Warping， DTW）[3-6]。這兩種距離度量方法都局限于時(shí)間序列之間特征向量的固定公式數(shù)值計(jì)算，不能有效利用標(biāo)注好的類(lèi)別標(biāo)簽。實(shí)際上，不同數(shù)據(jù)集的相似性描述并不能一概而論，數(shù)據(jù)樣本中包含的關(guān)于類(lèi)別的先驗(yàn)知識(shí)蘊(yùn)含了相似性的統(tǒng)計(jì)規(guī)律，這些統(tǒng)計(jì)規(guī)律可以從標(biāo)注好的訓(xùn)練集中進(jìn)行學(xué)習(xí)，進(jìn)而構(gòu)成更有效的數(shù)據(jù)相似性度量的表達(dá)方式。

近年來(lái)深度學(xué)習(xí)在很多領(lǐng)域得到了廣泛的應(yīng)用，一些學(xué)者結(jié)合距離度量學(xué)習(xí)[7]與孿生神經(jīng)網(wǎng)絡(luò)（Siamese Neural Network， SNN）進(jìn)行了各種應(yīng)用研究。SNN最早用于手寫(xiě)簽名驗(yàn)證[8]，驗(yàn)證平板電腦上書(shū)寫(xiě)的簽名真?zhèn)巍Ｎ墨I(xiàn)[9-11]將圖像識(shí)別中常用的卷積神經(jīng)網(wǎng)絡(luò)組成孿生卷積網(wǎng)絡(luò)（Siamese Convolutional Neural Network， SCNN）模型應(yīng)用于人臉識(shí)別（Face Verification）和行人重識(shí)別（Person Re-Identification）達(dá)到了不錯(cuò)的識(shí)別率。文獻(xiàn)[12]將SNN用于文本匹配，每個(gè)文本對(duì)象分別由子網(wǎng)絡(luò)單獨(dú)向量化，計(jì)算兩個(gè)向量的余弦相似度來(lái)衡量這兩段文本的相似程度。這些方法的共同目標(biāo)是學(xué)習(xí)一個(gè)好的距離度量，以便同類(lèi)數(shù)據(jù)對(duì)之間的距離縮小，而異類(lèi)數(shù)據(jù)對(duì)之間的距離盡可能地?cái)U(kuò)大。不同于一般基于特征向量的分類(lèi)問(wèn)題，時(shí)間序列數(shù)據(jù)往往具有高維度、屬性之間先后次序不可變等特點(diǎn)。

針對(duì)歐氏距離（ED）和DTW相似性度量方法的不足，借鑒SNN在模式識(shí)別等領(lǐng)域的良好表現(xiàn)，提出一種基于SNN的時(shí)間序列相似性度量學(xué)習(xí)方法，從標(biāo)簽信息和序列樣本中學(xué)習(xí)其數(shù)據(jù)之間相似性關(guān)系的知識(shí)并形成度量模型，時(shí)間序列的時(shí)間順序則在輸入變量的排序中體現(xiàn)，SNN網(wǎng)絡(luò)隱含層輸出每個(gè)時(shí)間序列新的矢量表示，計(jì)算新矢量之間的距離度量作為網(wǎng)絡(luò)的輸出，該輸出作為原時(shí)間序列之間的相似度S=SNN（Xi，Xj）。本文依據(jù)該相似度結(jié)合近鄰分類(lèi)器（K-Nearest Neighbor， KNN）[13]對(duì)時(shí)間序列進(jìn)行分類(lèi)，驗(yàn)證了該方法的優(yōu)勢(shì)。

1?相關(guān)理論基礎(chǔ)

區(qū)別于ED、DTW依賴(lài)于輸入空間中有意義且可計(jì)算的距離度量，SNN模型將度量學(xué)習(xí)的思想與神經(jīng)網(wǎng)絡(luò)的非線性表示嵌入結(jié)合起來(lái)，以監(jiān)督的方式從數(shù)據(jù)中學(xué)習(xí)數(shù)據(jù)之間的相似度的特定表達(dá)，經(jīng)過(guò)SNN子網(wǎng)絡(luò)映射到新的度量空間中。

1.1?SNN網(wǎng)絡(luò)一般結(jié)構(gòu)

輸出層作為輸入向量映射輸出的特征向量，用于度量模塊計(jì)算兩個(gè)子網(wǎng)絡(luò)輸出之間的相似度EW。EW的定義見(jiàn)式（12）。

在圖1中將一對(duì)同類(lèi)或異類(lèi)時(shí)間序列（Xi， Xj）分別輸入兩個(gè)權(quán)值共享結(jié)構(gòu)相同的子網(wǎng)絡(luò)，利用反向傳播算法調(diào)節(jié)網(wǎng)絡(luò)權(quán)值w，在訓(xùn)練階段如果一對(duì)時(shí)序數(shù)據(jù)（Xi， Xj）屬于同一類(lèi)別，則使得相似性度量EW數(shù)值小化，如果（Xi， Xj）屬于不同類(lèi)別，則EW數(shù)值大化。通過(guò)最小化損失函數(shù)值來(lái)學(xué)習(xí)優(yōu)化模型的所有參數(shù)。

1.3?度量函數(shù)

2?相似性度量實(shí)驗(yàn)及分析

圖2分別展示了Beef數(shù)據(jù)集中5類(lèi)時(shí)序數(shù)據(jù)的其中一個(gè)樣本。該數(shù)據(jù)集包含5個(gè)類(lèi)別共60條數(shù)據(jù)，劃分訓(xùn)練集和測(cè)試集各30條，每個(gè)類(lèi)別有6條時(shí)間序列數(shù)據(jù)。為了更直觀地了解SNN度量學(xué)習(xí)方法的優(yōu)勢(shì)，在Beef測(cè)試集上應(yīng)用基于t分布的隨機(jī)近鄰嵌入（t-distributed Stochastic Neighbor Embedding， t-SNE）算法[15]對(duì)SNN的中間層嵌入輸出Net（w， Xi）進(jìn)行了分析。

圖3中不同的數(shù)字代表相應(yīng)的序列類(lèi)別。t-SNE可視化表明SNN能夠很好地將相似的序列聚集在一起。為了比較，還使用相同數(shù)據(jù)原始序列的t-SNE圖。觀察圖2可以發(fā)現(xiàn)類(lèi)別為第2類(lèi)、第3類(lèi)、第4類(lèi)和第5類(lèi)的時(shí)間序列樣本在形態(tài)變化上非常相似，反映在圖3（a）中相應(yīng)的類(lèi)別數(shù)據(jù)點(diǎn)之間相互混淆，不同類(lèi)別序列的區(qū)分度不明顯。觀察圖3（b），通過(guò)學(xué)習(xí)有監(jiān)督的成對(duì)約束信息，原序列經(jīng)過(guò)子網(wǎng)絡(luò)映射到新的向量空間后，得到了一個(gè)能更有效地表達(dá)序列數(shù)據(jù)間鄰域關(guān)系的向量表示。這兩幅圖反映了SNN的潛在優(yōu)勢(shì)：SNN在衡量時(shí)間序列樣本相似度時(shí)能更好地描述序列間相似度。

3?分類(lèi)驗(yàn)證實(shí)驗(yàn)及比較

3.1?分類(lèi)實(shí)驗(yàn)流程

3.2?超參數(shù)選擇

本文采用一層隱含層的前饋神經(jīng)網(wǎng)絡(luò)構(gòu)建SNN模型子網(wǎng)絡(luò)。為了選擇合適的網(wǎng)絡(luò)結(jié)構(gòu)，從UCR數(shù)據(jù)集中隨機(jī)選取了兩個(gè)時(shí)序數(shù)據(jù)集進(jìn)行數(shù)值實(shí)驗(yàn)，通過(guò)分析實(shí)驗(yàn)結(jié)果探討SNN模型結(jié)構(gòu)參數(shù)對(duì)錯(cuò)誤率的影響，實(shí)驗(yàn)結(jié)果如圖4所示。實(shí)驗(yàn)中模型權(quán)值參數(shù)通過(guò)在區(qū)間[-0.05，0.05]內(nèi)的均勻分布采樣來(lái)初始化，選擇Adam優(yōu)化算法[16]訓(xùn)練模型，多次實(shí)驗(yàn)后選擇使用sigmoid函數(shù)作為神經(jīng)元激活函數(shù)，實(shí)驗(yàn)程序基于Python和Tensorflow平臺(tái)。

采用錯(cuò)誤率作為分類(lèi)質(zhì)量的評(píng)價(jià)標(biāo)準(zhǔn)，并對(duì)比以ED、DTW作為相似性度量的分類(lèi)錯(cuò)誤率。圖4展示了隨著神經(jīng)元數(shù)量增加時(shí)錯(cuò)誤率的變化。

錯(cuò)誤率的定義：分類(lèi)錯(cuò)誤的樣本數(shù)占樣本總數(shù)的比例。

在相同參數(shù)下進(jìn)行五次實(shí)驗(yàn)取平均值為實(shí)驗(yàn)結(jié)果。圖4的實(shí)驗(yàn)結(jié)果顯示，隨著隱層神經(jīng)元個(gè)數(shù)的增加分類(lèi)錯(cuò)誤率隨之明顯下降，較多的神經(jīng)元有利于學(xué)習(xí)數(shù)據(jù)的特征表示，但存在一定的飽和性。

3.3?數(shù)值實(shí)驗(yàn)

將SNN模型結(jié)合1-NN分類(lèi)器與主流的ED/DTW-1NN分類(lèi)器相比較，部分實(shí)驗(yàn)結(jié)果引用自文獻(xiàn)[17]。在UCR公共數(shù)據(jù)集上選取22個(gè)數(shù)據(jù)集完成對(duì)比實(shí)驗(yàn)，數(shù)據(jù)在獲取時(shí)已劃分好訓(xùn)練集與測(cè)試集，所有錯(cuò)誤率都在測(cè)試集上計(jì)算。表1展示了所對(duì)比的三種相似度度量方法在22個(gè)公共數(shù)據(jù)集上的分類(lèi)錯(cuò)誤率，加粗的數(shù)值表示所有對(duì)比方法中最優(yōu)的結(jié)果。其中SNN-1NN的結(jié)果是五次實(shí)驗(yàn)平均值。

從表1展示的實(shí)驗(yàn)結(jié)果來(lái)看，總體上分類(lèi)錯(cuò)誤率ED-1NN>DTW-1NN>SNN-1NN，三種分類(lèi)器在22個(gè)數(shù)據(jù)集上的平均分類(lèi)錯(cuò)誤率分別是0.251、0.236、0.191， SNN-1NN具有明顯的優(yōu)勢(shì)，其分類(lèi)錯(cuò)誤率在其中12個(gè)數(shù)據(jù)集上顯著低于主流的DTW-1NN分類(lèi)器，相對(duì)于ED-1NN在其中19個(gè)數(shù)據(jù)集上表現(xiàn)明顯占優(yōu)，在其余數(shù)據(jù)集上分類(lèi)錯(cuò)誤率相近。若對(duì)于不同數(shù)據(jù)集測(cè)試選擇更合適的調(diào)整網(wǎng)絡(luò)結(jié)構(gòu)則可進(jìn)一步降低SNN-1NN的分類(lèi)錯(cuò)誤率。

4?結(jié)語(yǔ)

本文針對(duì)目前時(shí)間序列相似性度量方法的優(yōu)點(diǎn)和不足，借鑒度量學(xué)習(xí)和神經(jīng)網(wǎng)絡(luò)模型相結(jié)合的思想，提出了一種基于SNN模型的度量學(xué)習(xí)方法，可提高對(duì)時(shí)間序列數(shù)據(jù)挖掘的性能。將該方法結(jié)合最近鄰算法在UCR公共數(shù)據(jù)集上進(jìn)行分類(lèi)實(shí)驗(yàn)，結(jié)果表明，與ED/DTW-1NN相比在分類(lèi)質(zhì)量總體上有明顯的提升。基于DTW-1NN的模型在部分?jǐn)?shù)據(jù)上表現(xiàn)仍然優(yōu)于SNN-1NN分類(lèi)方法，但在分類(lèi)過(guò)程的相似度計(jì)算復(fù)雜度和速度上，SNN優(yōu)于DTW。在之后的工作中，可對(duì)本文方法作進(jìn)一步的研究，針對(duì)數(shù)據(jù)集特點(diǎn)探討更加合理的網(wǎng)絡(luò)結(jié)構(gòu)，改進(jìn)模型的學(xué)習(xí)算法擴(kuò)展到時(shí)間序列數(shù)據(jù)挖掘聚類(lèi)等任務(wù)中的應(yīng)用。

參考文獻(xiàn)（References）

[1] 崔婧， 趙秀娟， 宋吟秋.中日股價(jià)序列相似性的比較分析[J]. 系統(tǒng)工程理論與實(shí)踐， 2009， 29（12）： 125-133. （CUI J， ZHAO X J， SONG Y Q. Similarity analysis on China's and Japan's security price series[J]. Systems Engineering — Theory and Practice， 2009， 29（12）： 125-133.）

[2] SIVARAKS H， RATANAMAHATANA C A. Robust and accurate anomaly detection in ECG artifacts using time series motif discovery[J]. Computational and Mathematical Methods in Medicine， 2015， 2015： 453214.

[3] 陳海燕， 劉晨暉， 孫博.時(shí)間序列數(shù)據(jù)挖掘的相似性度量綜述[J]. 控制與決策， 2017， 32（1）： 1-11. （CHEN H Y， LIU C H， SUN B. Survey on similarity measurement of time series data mining[J]. Control and Decision， 2017， 32（1）： 1-11.）

[4] BERNDT D J， CLIFFORD J. Using dynamic time warping to find patterns in time series[C]// AAAIWS 1994： Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining. Menlo Park， CA： AAAI Press， 1994， 10（16）： 359-370.

[5] FALOUTSOS C， RANGANATHAN M， MANOLOPOULOS Y. Fast subsequence matching in time-series databases[C]// SIGMOD 1994： Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data. New York： ACM， 1994： 419-429.

[6] 李海林， 梁葉， 王少春.時(shí)間序列數(shù)據(jù)挖掘中的動(dòng)態(tài)時(shí)間彎曲研究綜述[J]. 控制與決策， 2018， 33（8）： 1345-1353. （LI H L， LIANG Y， WANG S C. Review on dynamic time warping in time series data mining[J]. Control and Decision， 2018， 33（8）： 1345-1353.）

[7] 沈媛媛， 嚴(yán)嚴(yán)， 王菡子.有監(jiān)督的距離度量學(xué)習(xí)算法研究進(jìn)展[J]. 自動(dòng)化學(xué)報(bào)， 2014， 40（12）： 2673-2686. （SHEN Y Y， YAN Y， WANG H Z. Recent advances on supervised distance metric learning algorithms[J]. Acta Automatica Sinica， 2014， 40（12）： 2673-2686.）

[8] BROMLEY J， GUYON I， LECUN Y， et al. Signature verification using a “siamese” time delay neural network[C]// NIPS 1993： Proceedings of the 6th International Conference on Neural Information Processing Systems. San Francisco， CA： Morgan Kaufmann Publishers， 1994： 737-744.

[9] CHOPRA S， HADSELL R， LECUN Y. Learning a similarity metric discriminatively， with application to face verification[C]// CVPR 2005： Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. ??Washington， DC： IEEE Computer Society， 2005： 539-546.

[10] WANG F Q， ZUO W M， LIN L， et al. Joint learning of single-image and cross-image representations for person re-identification[C]// CVPR 2016： Proceedings of the 2016 IEEE Conference on Computer Vision and Pattern Recognition. ?Washington， DC： IEEE Computer Society， 2016： 1288-1296.

[11] DONG Y， ZHEN L， SHENG L， et al. Deep metric learning for person re-identification[C]// Proceedings of the 2014 22nd International Conference on Pattern Recognition. Piscataway， NJ： IEEE， 2014： 34-39.

[12] HUANG P S， HE X D， GAO J F， et al. Learning deep structured semantic models for Web search using clickthrough data[C]// Proceedings of the 22nd ACM International Conference on Conference on Information & Knowledge Management. New York： ACM， 2013： 2333-2338.

[13] COVER T， HART P. Nearest neighbor pattern classification[J]. IEEE Transactions on Information Theory， 1967， 13（1）： 21-27.

[14] BATISTA G E， WANG X， KEOGH E J. A complexity-invariant distance measure for time series[EB/OL]. [2018-05-10]. https：//epubs.siam.org/doi/pdf/10.1137/1.9781611972818.60.

[15] MAATEN L， HINTON G. Visualizing data using t-SNE[J]. Journal of Machine Learning Research， 2008， 9： 2579-2605.

[16] KINGMA D P， BA J. Adam： a method for stochastic optimization[EB/OL]. [2018-05-10]. https：//arxiv.org/pdf/1412.6980.

[17] CHEN Y， KEOGH E， HU B， et al. The UCR time series classification archive [DB/OL]. [2018-05-10]. http：//www.cs.ucr.edu/～eamonn/time_series_data/.