李翔宇，李瑞興，曾燕清

(1.閩江師范高等?？茖W(xué)校 計(jì)算機(jī)系，福建 福州 350108；2.物聯(lián)網(wǎng)福建省高校應(yīng)用工程中心，福建 福州 350108；3.福建江夏學(xué)院 電子信息科學(xué)學(xué)院，福建 福州 350108)

時(shí)間序列數(shù)據(jù)正在以一種難以想象的規(guī)模和速度快速增長(zhǎng)，已經(jīng)在商業(yè)、醫(yī)藥和科學(xué)研究等領(lǐng)域占據(jù)了大量的存儲(chǔ)空間[1]。近年來(lái)，時(shí)間序列數(shù)據(jù)分類被廣泛應(yīng)用到很多的領(lǐng)域中，例如心電圖ECG的模式匹配、手寫(xiě)識(shí)別、網(wǎng)絡(luò)的入侵預(yù)測(cè)以及股市行情預(yù)測(cè)等。由于時(shí)間序列數(shù)據(jù)具有維度高、數(shù)據(jù)量大以及流數(shù)據(jù)等復(fù)雜特性，因此實(shí)際應(yīng)用中時(shí)間序列數(shù)據(jù)分類面臨了很多挑戰(zhàn)。

由于時(shí)間序列數(shù)據(jù)在相同位置的數(shù)值一般不可直接比較，一般的分類算法不能直接應(yīng)用于時(shí)間序列數(shù)據(jù)分類。為了解決這些問(wèn)題，國(guó)內(nèi)外的學(xué)者對(duì)時(shí)間序列數(shù)據(jù)分類進(jìn)行大量的研究，并取得了很多有效的成果。原繼東[2]等人通過(guò)計(jì)算原有時(shí)間序列與k個(gè)最好邏輯Shapelets的距離，將原有時(shí)間序列轉(zhuǎn)換成新的擁有k個(gè)屬性的數(shù)據(jù)，將時(shí)間序列分類問(wèn)題轉(zhuǎn)化成傳統(tǒng)的分類問(wèn)題。王志海[3]等人為每個(gè)待分類實(shí)例構(gòu)建各自的數(shù)據(jù)驅(qū)動(dòng)的懶惰式Shapelets分類模型，縮小了與其分類相關(guān)的時(shí)間序列搜索空間，并獲得能夠直接反映待分類實(shí)例的顯著局部特征的Shapelets。王子一[4]等人通過(guò)k-shape聚類算法對(duì)子序列聚類，尋找兩類時(shí)間序列數(shù)據(jù)中各自比較有區(qū)分性的片段，并以此來(lái)作為分類的依據(jù)。李海林[5]等人通過(guò)近鄰傳播算法對(duì)訓(xùn)練集數(shù)據(jù)進(jìn)行聚類并尋找各類別的代表點(diǎn)，構(gòu)建代表點(diǎn)的代表對(duì)象集，最后借助基于動(dòng)態(tài)時(shí)間彎曲的均值中心方法對(duì)各代表對(duì)象集實(shí)現(xiàn)中心群計(jì)算，結(jié)合改進(jìn)后的K近鄰算法實(shí)現(xiàn)時(shí)間序列數(shù)據(jù)的分類。

支持向量機(jī)(SVM)[6-7]是 Vapnik 等人提出的一種建立在統(tǒng)計(jì)學(xué)習(xí)理論基礎(chǔ)上的數(shù)據(jù)挖掘方法。在眾多的機(jī)器學(xué)習(xí)算法中，支持向量機(jī)作為一種分類效果和穩(wěn)定性較好的機(jī)器學(xué)習(xí)算法得到了廣泛應(yīng)用[8]。許多學(xué)者將SVM算法運(yùn)用時(shí)間序列數(shù)據(jù)的分類工作中[9-10]，張坤華[11]等人針對(duì)多變量時(shí)間序列定義了每個(gè)屬性的局部密度和判別距離，根據(jù)決策圖的分布來(lái)篩選屬性，最終通過(guò)SVM對(duì)數(shù)據(jù)進(jìn)行分類。張振國(guó)[12]等人以子序列為單位，構(gòu)建時(shí)序數(shù)據(jù)間的相似性向量，快速篩選出具有高分類能力的Shapelets集合，并使用SVM算法進(jìn)行分類。傳統(tǒng)的SVM算法一般應(yīng)用于時(shí)間序列數(shù)據(jù)分類的最后階段，即對(duì)降維或者轉(zhuǎn)化操作后的時(shí)間序列數(shù)據(jù)進(jìn)行分類。

針對(duì)時(shí)間序列數(shù)據(jù)的分類，傳統(tǒng)的SVM算法僅通過(guò)樣本在空間中的幾何距離判別樣本的類別，為此提出了一種基于改進(jìn)核函數(shù)的支持向量機(jī)算法。首先計(jì)算樣本與空間基數(shù)據(jù)的時(shí)間序列互相關(guān)距離，將樣本數(shù)據(jù)映射到新的特征空間中，其次根據(jù)新特征空間的訓(xùn)練樣本數(shù)據(jù)構(gòu)建線性核函數(shù)的核矩陣，計(jì)算得到SVM的分類模型，最終根據(jù)該分類模型對(duì)新特征空間的測(cè)試樣本數(shù)據(jù)進(jìn)行分類獲得分類結(jié)果。

1 SVM_IK算法

1.1 時(shí)間序列距離

1.1.1 時(shí)間序列

定義1(時(shí)間序列數(shù)據(jù))：時(shí)間序列數(shù)據(jù)是一個(gè)有序的信息集合。時(shí)間序列X={x1,x2,Λ,xn}是一個(gè)長(zhǎng)度為n的數(shù)據(jù)序列，其中數(shù)據(jù)序列的采樣間隔為Δt=t(xi)-t(xi-1)。

定義2(空間基數(shù)據(jù))：空間基數(shù)據(jù)是時(shí)間序列數(shù)據(jù)，主要應(yīng)用于時(shí)間序列數(shù)據(jù)的特征空間轉(zhuǎn)換。

定義3(類別時(shí)間序列數(shù)據(jù))：類別時(shí)間序列數(shù)據(jù)是由定義1的時(shí)間序列數(shù)據(jù)與該時(shí)間序列數(shù)據(jù)的類別構(gòu)成，D={(X1,y1),(X2,y2),Λ,(xn,yn)}，其中yi是時(shí)間序列Xi的類別。

1.1.2 時(shí)間序列互相關(guān)距離 在信號(hào)處理的流程中，常常用互相關(guān)函數(shù)來(lái)計(jì)算兩個(gè)不同的波的相似性[13],因此可以將其應(yīng)用于時(shí)間序列數(shù)據(jù)之間的相似性度量。讓一個(gè)時(shí)間序列保持靜止，另一個(gè)序列在靜止序列上滑動(dòng)，通過(guò)平移找到互相關(guān)的最大值，即為兩個(gè)時(shí)間序列的相似性。對(duì)于時(shí)間序列數(shù)據(jù)x=(x1,x2,…,xm)與時(shí)間序列數(shù)據(jù)y=(y1,y2,…,ym)，序列x位移w個(gè)位置后與靜止序列y的互相關(guān)函數(shù)如公式(1)所示：

(1)

其中w∈{-m,-m+1,Λ,0,Λ,m-1,m}，w≥0 時(shí)，表示x序列向右移動(dòng)w個(gè)位置，w<0時(shí)，表示x序列向左移動(dòng)w個(gè)位置，移動(dòng)后空余的位置由0替代。

找到一個(gè)最優(yōu)的位移w，使得C(x,y,w)的值最大，也就找到了x相對(duì)于y最好的位移。根據(jù)文獻(xiàn)[14]的時(shí)間序列形狀距離，時(shí)間序列互相關(guān)距離如定義4所示。

定義4(時(shí)間序列互相關(guān)距離)：衡量?jī)蓚€(gè)時(shí)間序列數(shù)據(jù)在形態(tài)上的一致性，時(shí)間序列x與序列y的互相關(guān)距離如公式(2)所示：

(2)

兩個(gè)時(shí)間序列之間的互相關(guān)數(shù)值范圍限定到[0,2]之間，即數(shù)值越大、越不相似，數(shù)值越小，越相似。

1.2 支持向量機(jī)(SVM)

支持向量機(jī)是基于統(tǒng)計(jì)學(xué)習(xí)理論( SLT) 的新型機(jī)器學(xué)習(xí)方法[12]。它是為了解決二分類識(shí)別問(wèn)題而提出了方法，通過(guò)尋找一個(gè)最優(yōu)的超平面，不僅能將訓(xùn)練樣本正確分開(kāi)，而且能使兩類樣本的分類間隔最大。

(3)

引入Lagrange函數(shù)來(lái)解決以上優(yōu)化問(wèn)題，如公式(4)：

(4)

其中λ≥0為拉格朗日乘子，通過(guò)對(duì)w和b求偏導(dǎo)，設(shè)置偏導(dǎo)為0，即可求解最優(yōu)權(quán)值向量w*和最優(yōu)偏置b*，分別如公式(5)和公式(6)所示：

(5)

b*=yi-∑yjλj(xj·xi)

(6)

由此可以獲得最優(yōu)的決策函數(shù)如公式(7)：

(7)

對(duì)于實(shí)際上難以線性分類的問(wèn)題，可以將待分類數(shù)據(jù)射到某個(gè)高維的特征空間，并在該特征空間中構(gòu)造最優(yōu)分類面，從而轉(zhuǎn)化成線性可分類問(wèn)題。以高維空間的樣本Φ(x)代替原樣本數(shù)據(jù)x,則可以得到最優(yōu)分類函數(shù)如公式(8)所示：

(8)

在高維特征空間構(gòu)造最優(yōu)超平面時(shí)，僅使用特征空間中的內(nèi)積實(shí)現(xiàn)?？梢酝ㄟ^(guò)一個(gè)核函數(shù)K(X,Xp)，如公式(9)所示：

(9)

則在特高維征空間建立超平面時(shí)無(wú)需考慮變換Φ的形式，簡(jiǎn)化映射空間中的內(nèi)積運(yùn)算。SVM的常用核函數(shù)有：Linear(線性)核函數(shù)、Polynomial(多項(xiàng)式)核函數(shù)、RBF(徑向基)核函數(shù)和Sigmoid型核函數(shù)。

1.3 SVM_IK算法的步驟

SVM引入核函數(shù)的目的是將高維特征空間中大量的內(nèi)積計(jì)算轉(zhuǎn)換成低維空間簡(jiǎn)單的運(yùn)算實(shí)現(xiàn)模型構(gòu)建。不同的核函數(shù)蘊(yùn)藏的幾何度量特征各異，選擇不同的核函數(shù)導(dǎo)致SVM泛化能力存在差異[15]。針對(duì)時(shí)間序列數(shù)據(jù)的分類，需要符合其特征的核函數(shù)對(duì)數(shù)據(jù)進(jìn)行空間轉(zhuǎn)換。

線性核函數(shù)作為SVM中的最簡(jiǎn)單的核函數(shù)，它并未對(duì)原始的數(shù)據(jù)元素進(jìn)行空間轉(zhuǎn)換。數(shù)據(jù)X=(x1,x2,…,xm)在線性核函數(shù)的公式中計(jì)算如公式(10)所示：

(10)

由于線性核函數(shù)中的幾何度量特征不能有效的衡量時(shí)間序列數(shù)據(jù)的關(guān)系。為此，引入時(shí)間序列互相關(guān)距離，將時(shí)間序列數(shù)據(jù)映射到新的特征空間中，消除原始特征空間中數(shù)據(jù)的時(shí)間序列特性。通過(guò)空間基數(shù)據(jù)T=(t1,t2,…,tm)，對(duì)原始時(shí)間序列數(shù)據(jù)進(jìn)行轉(zhuǎn)換，得到新的特征空間數(shù)據(jù)，如公式(11)所示：

(11)

新的特征空間的數(shù)據(jù)不再具有原始時(shí)間序列特性，因此可使用線性核函數(shù)獲得較好的SVM分類效果。將線性核函數(shù)與新的特征空間轉(zhuǎn)換結(jié)合，改進(jìn)的線性核函數(shù)如公式(12)：

k(X,X)=Dist(X,T)·Dist(X,T)

(12)

SVM_IK算法首先選用訓(xùn)練數(shù)據(jù)集作為空間基數(shù)據(jù)對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行空間轉(zhuǎn)換，將空間轉(zhuǎn)換映射后的結(jié)果進(jìn)行構(gòu)建相應(yīng)的分類模型。其次將待分類的時(shí)間序列數(shù)據(jù)進(jìn)行相應(yīng)的空間轉(zhuǎn)換，將空間轉(zhuǎn)換后的結(jié)果輸入到分類模型進(jìn)行分類獲得最終結(jié)果。SVM_IK算法的具體步驟如下：

步驟1：將時(shí)間序列數(shù)據(jù)集分為訓(xùn)練數(shù)據(jù)集Dtr(m×v)、訓(xùn)練標(biāo)簽集Ltr(m×1)、測(cè)試數(shù)據(jù)集Dte(n×v)、測(cè)試標(biāo)簽集Lte(n×1)，其中m為訓(xùn)練集樣本個(gè)數(shù)，n為測(cè)試集樣本個(gè)數(shù)，v為數(shù)據(jù)的維數(shù)；

步驟2：將訓(xùn)練集Dtr中的樣本與空間基數(shù)據(jù)Dtr兩兩計(jì)算樣本之間的時(shí)間序列互相關(guān)距離，構(gòu)建m×m的新特征空間中的訓(xùn)練樣本數(shù)據(jù)；

步驟3：將待分類數(shù)據(jù)集Dte中的樣本與空間基數(shù)據(jù)Dtr兩兩計(jì)算樣本之間的時(shí)間序列互相關(guān)距離，構(gòu)建n×m的新特征空間中的待分類樣本數(shù)據(jù)；

步驟4：使用線性核函數(shù)K(X,X)與訓(xùn)練標(biāo)簽集Ltr構(gòu)建SVM分類模型Model 。

步驟5：構(gòu)建n×m的新空間中的待分類樣本數(shù)據(jù)輸入到Model中進(jìn)行分類，最終獲得數(shù)據(jù)分類結(jié)果。

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

實(shí)驗(yàn)采用編程語(yǔ)言為Python3.7，實(shí)驗(yàn)程序代碼基于臺(tái)灣林智仁教授等開(kāi)發(fā)、設(shè)計(jì)的LibSVM[15]軟件包基礎(chǔ)上完成的。實(shí)驗(yàn)采用25組UCR數(shù)據(jù)集驗(yàn)證算法的有效性，UCR數(shù)據(jù)集是目前時(shí)間序列分類研究中普遍使用的數(shù)據(jù)集。

從表1可以看出，實(shí)驗(yàn)數(shù)據(jù)類型多樣。類別從2類到60類，數(shù)據(jù)維度也是大小不一，最小60維，最長(zhǎng)2000維；訓(xùn)練數(shù)據(jù)與測(cè)試數(shù)據(jù)的樣本數(shù)量的差異也較大，因此可以更全面的衡量算法的性能。為了便于測(cè)試，實(shí)驗(yàn)數(shù)據(jù)集采用默認(rèn)的訓(xùn)練數(shù)據(jù)和測(cè)試數(shù)據(jù)劃分，以準(zhǔn)確率作為分類結(jié)果評(píng)價(jià)指標(biāo)。準(zhǔn)確率定義如下:

準(zhǔn)確率 = 正確分類的樣本數(shù)/總樣本數(shù)

表1 25組UCR數(shù)據(jù)集

2.1 SVM_IK算法與傳統(tǒng)SVM算法比較

實(shí)驗(yàn)中的對(duì)比算法采用基于Linear核函數(shù)、Polynomial核函數(shù)、RBF核函數(shù)、 Sigmoid型核函數(shù)下的SVM算法，實(shí)驗(yàn)中它們的簡(jiǎn)寫(xiě)分別為SVM_L、SVM_P、SVM_R和SVM_S。以上4種核函數(shù)的參數(shù)設(shè)置均采用libsvm中的默認(rèn)參數(shù)，基于這些核函數(shù)的SVM算法分別對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行構(gòu)建分類模型，最后通過(guò)構(gòu)建的分類模型分別對(duì)測(cè)試數(shù)據(jù)分類，計(jì)算不同核函數(shù)下的準(zhǔn)確率。SVM_IK算法對(duì)訓(xùn)練數(shù)據(jù)集構(gòu)建分類模型，通過(guò)測(cè)試數(shù)據(jù)與訓(xùn)練數(shù)據(jù)的時(shí)間序列互相關(guān)距離構(gòu)建的測(cè)試數(shù)據(jù)進(jìn)行分類，計(jì)算最終的分類準(zhǔn)確率。SVM_IK算法與4種不同核函數(shù)下的傳統(tǒng)SVM算法實(shí)驗(yàn)對(duì)比圖1和表2所示。

表2 與4種核函數(shù)下的SVM算法平均準(zhǔn)確率對(duì)比

圖1可知，基于RBF核函數(shù)、 Sigmoid型核函數(shù)的傳統(tǒng)SVM算法對(duì)時(shí)間序列數(shù)據(jù)的分類效果較差，基于Linear核函數(shù)、Polynomial核函數(shù)的SVM算法則效果相當(dāng)。SVM_IK算法僅8組數(shù)據(jù)的分類效果略低于這四種算法，其他17組數(shù)據(jù)的分類效果持平或者高于4種核函數(shù)下的SVM算法。

從表1中可以發(fā)現(xiàn)，SVM_IK算法的平均準(zhǔn)確率均高于4種核函數(shù)下的SVM算法。由于傳統(tǒng)的SVM算法采用的幾何距離來(lái)衡量樣本與超平面之間的距離，SVM_IK算法考慮到時(shí)間序列的形狀上的相似度。

2.2 不同度量方式下的SVM_IK算法對(duì)比

SVM_IK算法采用時(shí)間序列互相關(guān)距離、DTW距離和歐氏距離下的改進(jìn)算法分類效果，實(shí)驗(yàn)中采用簡(jiǎn)寫(xiě)為SVM_IK(R)、SVM_IK(ED)和SVM_IK(DTW)，它們的分類結(jié)果圖2和表3所示。

表3 SVM_IK算法的三種度量下的平均準(zhǔn)確率

從圖2中可以發(fā)現(xiàn)，采用時(shí)間序列互相關(guān)距離時(shí)，18組數(shù)據(jù)的分類效果均好于其他兩種度量，7組數(shù)據(jù)的分類效果略低于或持平于其他兩種度量方式。同時(shí)表3中也可以發(fā)現(xiàn)采用時(shí)間序列互相關(guān)距離時(shí)，對(duì)于25組數(shù)據(jù)的平均分類準(zhǔn)確率優(yōu)于其他兩種度量方式。也說(shuō)明了 SVM_IK算法采用的時(shí)間序列互相關(guān)距離在分類過(guò)程中起到了積極的效果。

2.3 SVM_IK算法與1-NN算法對(duì)比

本實(shí)驗(yàn)對(duì)比SVM_IK算法與1-NN算法的分類結(jié)果，采用歐式距離度量的1-NN(ED)和采用DTW距離的1-NN(DTW)，對(duì)比結(jié)果如圖3和表4所示。

表4 與1-NN算法平均分類準(zhǔn)確率對(duì)比

圖3中可以發(fā)現(xiàn)，與兩種度量方式下的1-NN算法相比，SVM_IK算法有9組數(shù)據(jù)的分類效果略低于這他們兩者，有2組數(shù)據(jù)的分類效果與其中一者持平，有14組數(shù)據(jù)的分類效果都高于這兩者。通過(guò)表4可以發(fā)現(xiàn)本文算法的平均值均高于這兩種度量下的1-NN算法。因此，本文提出的SVM_IK算法對(duì)時(shí)間序列數(shù)據(jù)分類能夠有較好的分類準(zhǔn)確率。

3 結(jié)論

時(shí)間序列數(shù)據(jù)分類在被廣泛應(yīng)用于很多領(lǐng)域中，很多學(xué)者把支持向量機(jī)應(yīng)用于時(shí)間序列分類中。針對(duì)傳統(tǒng)的支持向量機(jī)分類僅依據(jù)樣本點(diǎn)在空間中的幾何距離作為分類評(píng)判的依據(jù)，而沒(méi)有考慮時(shí)間序列的數(shù)據(jù)形態(tài)特性，本文提出了SVM_IK算法引入了時(shí)間序列互相關(guān)距離，將時(shí)間序列的形態(tài)相似度引入到分類算法中，并對(duì)線性核函數(shù)進(jìn)行相應(yīng)的改進(jìn)，使得支持向量機(jī)能夠考慮樣本形態(tài)上的相似性，在UCR數(shù)據(jù)集上獲得較好的分類效果。