李海林，賈瑞穎，譚觀音,2

（1. 華僑大學(xué)信息管理與信息系統(tǒng)系 福建 泉州 362021；2. 華僑大學(xué)應(yīng)用統(tǒng)計(jì)與大數(shù)據(jù)研究中心 福建 廈門 361021）

時(shí)間序列是一種與時(shí)間相關(guān)的數(shù)值型數(shù)據(jù)，基于時(shí)間序列的數(shù)據(jù)挖掘與分析成為目前數(shù)據(jù)研究領(lǐng)域中最具有挑戰(zhàn)性的十大問題之一[1]。分類算法是時(shí)間序列數(shù)據(jù)挖掘中極為重要的任務(wù)和技術(shù)[2]，有大量關(guān)于時(shí)間序列分類和挖掘的研究[3]。分類問題依賴于時(shí)間序列間的相似性度量，而相似性度量是兩條時(shí)間序列相似程度的度量方法[4]。對(duì)于時(shí)間序列來說，同類時(shí)間序列間的相似性主要有時(shí)域相似性、形狀相似性和變化相似性3 種形式[5]。支持向量機(jī)（support vector machine, SVM）是由文獻(xiàn)[6]提出的通過核函數(shù)將時(shí)間序列向高維空間映射的方法，可用于時(shí)間序列分類。樸素貝葉斯分類器是目前公認(rèn)的一種簡單而有效的概率分類方法，作為經(jīng)典的機(jī)器學(xué)習(xí)算法之一，在信息檢索領(lǐng)域有著極為重要的地位[7]。文獻(xiàn)[8]提出了EAIW 分類算法，該算法為時(shí)間序列區(qū)間賦予權(quán)值，采用集成分類的算法，通過權(quán)值對(duì)時(shí)間序列進(jìn)行分類。文獻(xiàn)[9]提出了TLCS 算法，該算法提出一種新的基于時(shí)間序列的趨勢離散化方法，利用LCS 對(duì)其進(jìn)行相似性度量。

模糊聚類由于能夠描述樣本類屬的中介性，能更客觀地反映現(xiàn)實(shí)世界，目前已成為聚類分析的主流，成為非監(jiān)督模式識(shí)別的一個(gè)重要分支。模糊聚類分析已經(jīng)成功地應(yīng)用于遙感圖像處理、醫(yī)學(xué)圖像處理、基因數(shù)據(jù)處理、模糊決策分析等領(lǐng)域[10]。眾多的模糊聚類方法中，應(yīng)用最廣泛的是模糊C-均值（fuzzy C-means, FCM）算法。由于模糊C-均值算法在初始聚類中心的選擇上具有隨機(jī)性，對(duì)初始值比較敏感，難以取得全局最優(yōu)[11]。

本文提出一種新的時(shí)間序列分類方法，即基于k-shape 的時(shí)間序列模糊分類方法。該方法利用一種新的k-shape 聚類算法[12]對(duì)訓(xùn)練集中每個(gè)類的時(shí)間序列進(jìn)行聚類，得到聚類中心群，并將這些中心群作為模糊分類的初始聚類中心，使用模糊C 均值對(duì)時(shí)間序列測試集數(shù)據(jù)進(jìn)行分類。

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

k-shape 是一種應(yīng)用在時(shí)間序列數(shù)據(jù)中的聚類方法[12]，此算法提出基于時(shí)間序列形態(tài)相似性的距離量度方式SBD，并采用一種新的聚類中心計(jì)算方式SE 提取每類聚類中心的時(shí)間序列曲線形態(tài)，以此完成聚類。

定義1 SBD 是一種基于形狀的相似性度量方式，在一定程度上彌補(bǔ)了以歐式距離作為相似性評(píng)價(jià)指標(biāo)的不足，通過SBD 可得到兩條時(shí)間序列之間的相似度量。具體過程如下：

(dist,y′)=SBD(x,y)

基于形狀的相似性度量方法：

輸入：兩條Z-score 標(biāo)準(zhǔn)化后的時(shí)間序列x，y；

輸出：時(shí)間序列x，y的相似性度量dist 和y相對(duì)于x的對(duì)齊序列y′；

計(jì)算l en=22*length(x)-1；

對(duì)x和y分別進(jìn)行快速傅里葉變換，即Fx=FFT(x,len)，F(xiàn)y=FFT(y,len)；

進(jìn)行逆快速傅里葉變換，計(jì)算x和y之間的交相關(guān)序列CC，C C=IFFT{Fx*Fy}；

定義 2 SE 是從時(shí)間序列中提取最具有代表的形態(tài)特征，以此進(jìn)行聚類。根據(jù)文獻(xiàn)[12]，k-shape利用SE 方法可以在每種類別的數(shù)據(jù)中產(chǎn)生一個(gè)聚類中心。

基于代表性形態(tài)特征的聚類中心提取方法：C=SE(X,R)

輸入：Z-score 標(biāo)準(zhǔn)化后的時(shí)間序列集合X=[x1,x2,···,xn] （其中每條時(shí)間序列的長度為p），與X對(duì)齊的參考序列向量R；

輸出：聚類中心矩陣C；

設(shè)立對(duì)齊序列矩陣M；

定義 3k-shape 是一種基于時(shí)序形狀的時(shí)間序列聚類方法。該方法首先利用SBD 算法進(jìn)行時(shí)間序列之間的相似性度量，獲得相似序列。然后使用SE 算法從相似序列中提取第一特征向量，作為聚類中心，進(jìn)而完成聚類。

基于時(shí)間序列形態(tài)特征的聚類方法：(IDX,C)=k-shape(X,k)

2 時(shí)間序列模糊分類

新分類方法首先通過基于k-shape 的聚類中心群方法構(gòu)建每個(gè)類別的聚類中心群，然后結(jié)合基于FCM 的模糊分類方法實(shí)現(xiàn)對(duì)時(shí)間序列的分類。該方法具有良好的分類性能。

2.1 基于k-shape 的聚類中心群

絕大多數(shù)的時(shí)間序列都存在明顯的位移和扭曲，傳統(tǒng)的聚類算法不能有效解決這部分時(shí)間序列的聚類問題，而k-shape 對(duì)具有位移和扭曲的時(shí)間序列聚類有更好的適用性，可以在一定程度上彌補(bǔ)傳統(tǒng)聚類算法以歐氏距離作為相似性度量指標(biāo)的不足。本文提出一種新的基于k-shape 的聚類中心群方法KCG，該方法可得到單個(gè)類別的聚類中心群，且有較好的代表性。

如圖1 所示，通過對(duì)時(shí)間序列數(shù)據(jù)集X提取聚類中心，可以看出k-shape 提取的聚類中心相比于傳統(tǒng)聚類算法k-means 更符合數(shù)據(jù)集X的形態(tài)特征，更具有代表性。其算法過程如下。

圖1 k-shape 算法優(yōu)勢

基于k-shape 聚類的聚類中心群方法：Ca=KCG(X,k)

輸入：同一類別的時(shí)間序列數(shù)據(jù)集X=[x1,x2,···,xn]、X的類別標(biāo)簽A和聚類中心數(shù)k；

輸出：聚類中心矩陣Ca=[c1a,c2a,···,cka]，cia表示A類別的聚類中心群中的第i個(gè)中心代表對(duì)象；

1） 根據(jù)k-shape 聚類算法，將時(shí)間序列數(shù)據(jù)集X劃分成k類，得到k個(gè)聚類中心，即 (IDXa,Ca) =k-shape(X,k)， IDXa和Ca分別代表X中所有序列的聚類標(biāo)簽向量和聚類中心矩陣；

2） 將步驟1）中得到的聚類中心矩陣Ca標(biāo)記為Ca=[c1a,c2a,···,cka]， 代表A類別成員序列的聚類中心群。

通過基于k-shape 聚類的聚類中心群方法KCG可以得到同類別時(shí)間序列集的聚類中心群，該中心群可代表整個(gè)類別的時(shí)間序列數(shù)據(jù)形態(tài)特征分布情況。

2.2 模糊分類

模糊分類相比于傳統(tǒng)分類算法的硬劃分，更符合時(shí)間序列分類的不確定性。FCM 算法作為模糊分類的主流算法之一，能在一定程度上解決時(shí)間序列數(shù)據(jù)分類的不確定性問題，是傳統(tǒng)硬聚類算法的一種改進(jìn)。

FCM 算法的核心思想是通過極小化目標(biāo)函數(shù)求最優(yōu)聚類中心[13]，聚類結(jié)果是每一條時(shí)間序列對(duì)聚類中心的隸屬程度，該隸屬程度用一個(gè)數(shù)值來表示。本文提出一種基于FCM 的模糊分類方法，通過已知的初始聚類中心群，進(jìn)行模糊分類，降低初始值對(duì)最后分類結(jié)果的影響。為了便于理解和討論模糊分類方法，假設(shè)時(shí)間序列數(shù)據(jù)集共分為兩類，進(jìn)一步解釋該算法。其具體算法過程如下：

基于FCM 的模糊分類算法：D= FCM(Y,C,iter_max)

輸入：包含已知類別A和 類別B的聚類中心矩陣C、允許的最大迭代次數(shù) iter_max（默認(rèn)為100）和時(shí)間序列測試數(shù)據(jù)集Y=[y1,y2,···,ym]；

輸出：隸屬度矩陣D；

1） 將聚類中心矩陣C中A類別的聚類中心群標(biāo)記為Ca，B類 別的聚類中心群標(biāo)記為Cb；

2） 根據(jù)FCM 模糊聚類算法，將C作為初始聚類中心進(jìn)行聚類，得到模糊隸屬度矩陣D， 即D=FCM(Y,C,iter_max)。

通過基于模糊分類的FCM 算法得到模糊隸屬度矩陣D后，進(jìn)一步分別計(jì)算yi屬 于D中A類別聚類中心群Ca和B類 別聚類中心群Cb的隸屬度之和，并判斷大小。較大的隸屬度之和代表的類標(biāo)簽為yi所屬類別，即可完成分類。

基于FCM 的模糊分類算法以k-shape 聚類得到的聚類中心群作為初始聚類中心，經(jīng)過一定次數(shù)的迭代，得到模糊隸屬度矩陣，依次判斷測試時(shí)間序列屬于各類別標(biāo)簽的聚類中心群的隸屬度之和，根據(jù)最大隸屬度原則確定該測試時(shí)間序列屬于哪個(gè)類別，從而完成時(shí)序數(shù)據(jù)的分類。

2.3 基于k-shape 的時(shí)間序列模糊分類方法

考慮到k-shape 聚類算法和模糊分類算法的優(yōu)勢，本文將基于k-shape 的聚類中心群算法KCG和基于FCM 的模糊分類算法結(jié)合起來，提出了一種思路更為簡單的時(shí)間序列分類方法（k-shape and FCM based time series clustering, KFCM）。KFCM算法首先將時(shí)間序列訓(xùn)練集各類別的序列成員進(jìn)行k-shape 聚類，分別得到每個(gè)類別的聚類中心群，形成已知類標(biāo)簽的聚類中心群。然后，使用基于FCM 的模糊分類算法，將測試集序列與已知標(biāo)簽的聚類中心群進(jìn)行聚類，輸出模糊隸屬度矩陣。最后，根據(jù)隸屬度大小原則進(jìn)一步判斷測試集類別。具體算法如下：

基于k-shape 的時(shí)間序列模糊分類方法：L=KFCM(X,Y,k,iter_max)。

輸入：訓(xùn)練集X、測試集Y、默認(rèn)最大迭代次數(shù)iter_max 和聚類中心數(shù)k；

輸出：測試集Y的類標(biāo)簽向量L；

1）根據(jù)訓(xùn)練集X=[x1,x2,···,xn]的成員類標(biāo)簽[h1,h2,···,hw]， 依次利用KCG 對(duì)類別hi包含的每個(gè)成員進(jìn)行聚類，得到hi的 聚類中心群Ci。將w個(gè)聚類中心群合并得到總聚類中心群C，C包含w個(gè)類別，共kw個(gè)聚類中心；

2）對(duì)測試集Y=[y1,y2,···,ym]，使用基于FCM的模糊分類算法，即D=FCM(Y,C,iter_max)；

3）根據(jù)步驟2）得到的模糊隸屬度矩陣D，計(jì)算測試集對(duì)象yj屬 于D中各類聚類中心群的隸屬度之和，其較大者的類標(biāo)簽為yj所 屬類別lj；

4）重復(fù)步驟3），獲得Y中所有成員的類標(biāo)簽，即L=[l1,l2,···,lm]，其中m為測試集Y包含的時(shí)間序列數(shù)目。

3 數(shù)值實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證本文提出算法的有效性，在30 個(gè)時(shí)間序列數(shù)據(jù)集上做分類實(shí)驗(yàn)。通過實(shí)驗(yàn)結(jié)果可以驗(yàn)證分類精度的有效性，也可以驗(yàn)證針對(duì)存在位移和扭曲特征的時(shí)間序列分類，新方法的適用性。

3.1 實(shí)驗(yàn)設(shè)置

算法代碼使用Python 3.7 在Anaconda 科學(xué)計(jì)算環(huán)境中實(shí)現(xiàn)，運(yùn)行所用計(jì)算機(jī)的CPU 型號(hào)為InterCore i5-8250U （1.60 GHz），RAM 為16 GB，操作系統(tǒng)是Windows10 64 位（DirectX 12）。

本文采用的數(shù)據(jù)集是UCR TS Archive 2015，UCR[14]是時(shí)間序列數(shù)據(jù)集，每個(gè)數(shù)據(jù)集樣本都帶有樣本類別標(biāo)簽，它是目前時(shí)間序列挖掘領(lǐng)域重要的開源數(shù)據(jù)集資源。從UCR 數(shù)據(jù)集中選取了30 個(gè)訓(xùn)練集，為了驗(yàn)證新方法具有更高的分類質(zhì)量和性能，這30 個(gè)數(shù)據(jù)集在類別、長度和大小上具有明顯差異。具體數(shù)據(jù)集信息如表1 所示。

表1 時(shí)間序列數(shù)據(jù)集

在對(duì)訓(xùn)練數(shù)據(jù)集進(jìn)行k-shape 聚類時(shí)，訓(xùn)練集的類別和類別數(shù)是已知的，需要用k-shape 單獨(dú)對(duì)訓(xùn)練集每一個(gè)類別包含的時(shí)間序列進(jìn)行聚類，進(jìn)而確定各類別的聚類中心群。

3.2 參數(shù)設(shè)置

在進(jìn)行參數(shù)討論時(shí)，假定訓(xùn)練集共有w個(gè)類別，每個(gè)類別的聚類中心數(shù)都是k，因此共可得到wk個(gè)聚類中心，且每個(gè)聚類中心群都標(biāo)記著本類別的標(biāo)簽。本文以Cricket_X 數(shù)據(jù)集為例，說明利用手肘法選取最佳聚類數(shù)k的過程。k的取值為1～8 （本文設(shè)置上限為8）。如圖2 所示，隨著k增大，SSE 的下降幅度會(huì)驟減，在k=4 之后下降幅度趨于平緩。因此針對(duì)Cricket_X 數(shù)據(jù)集，最佳聚類中心數(shù)是4。

圖2 k值選取對(duì)SSE 的影響

3.3 數(shù)據(jù)分類

本節(jié)將提出的KFCM 算法與SVM[6]、Bayes[7]、EAIW[8]和TLCS[9]這4 種基準(zhǔn)分類算法進(jìn)行比較。為了進(jìn)一步驗(yàn)證k-shape 在提取聚類中心過程中的算法優(yōu)勢，本文利用k-means 算法提取各類別的聚類中心群來作為模糊分類的初始聚類中心，同時(shí)使用模糊分類方法對(duì)時(shí)間序列數(shù)據(jù)集進(jìn)行分類。該算法稱為KMFCM，作為KFCM 的對(duì)比算法之一。利用以上6 種方法對(duì)30 組UCR 數(shù)據(jù)集進(jìn)行分類實(shí)驗(yàn)，分類錯(cuò)誤率如表2 所示。利用平均分類錯(cuò)誤率、方差和勝出率3 個(gè)指標(biāo)評(píng)價(jià)分類效果，如表3所示。

從表2 可知，KFCM 算法的平均錯(cuò)誤率最低，錯(cuò)誤率的總體波動(dòng)幅度較小，在30 個(gè)數(shù)據(jù)集中有9 個(gè)數(shù)據(jù)集的錯(cuò)誤率最小，有最高的勝出率。為了更好地表現(xiàn)分類結(jié)果，本文通過對(duì)錯(cuò)誤率的兩兩比較，使用可視化分類比較結(jié)果展示，如圖3 所示。KFCM 的分類準(zhǔn)確率和勝出率都高于KMFCM，同時(shí)，在ShapeletSim、MoteStrain、InlineSkate 等數(shù)據(jù)集上也有較低的分類錯(cuò)誤率，這證明了k-shape相比于k-means 在聚類過程中有明顯優(yōu)勢。KFCM在時(shí)間序列測試集上的分類性能優(yōu)于SVM 和Bayes，平均準(zhǔn)確率有一定提升。最后，KFCM 分類準(zhǔn)確率相較于TLCS 和EAIW 也有一定提高，個(gè)別數(shù)據(jù)集提高效果較為明顯。

圖3 分類算法錯(cuò)誤率的比較

圖4 k與錯(cuò)誤率的關(guān)系

表2 各分類算法分類錯(cuò)誤率

表3 各類算法評(píng)價(jià)指標(biāo)

本文選取4 個(gè)時(shí)間序列數(shù)據(jù)集，來說明聚類中心數(shù)k對(duì)分類結(jié)果的影響，如圖4 所示。k值對(duì)各數(shù)據(jù)集的分類結(jié)果影響不同，對(duì)于BeetleFly 數(shù)據(jù)集，錯(cuò)誤率最大值和最小值之間差距達(dá)到0.23；對(duì)于OliveOil 數(shù)據(jù)集，錯(cuò)誤率最大值和最小值之間差距為0.06。

由此可知，對(duì)于不同的數(shù)據(jù)集，k對(duì)最后分類效果的影響也是不同的。有的數(shù)據(jù)集如BeetleFly受影響比較大，因此參數(shù)k需根據(jù)具體數(shù)據(jù)而設(shè)定。

3.4 實(shí)驗(yàn)分析

本文分析了30 個(gè)時(shí)間序列訓(xùn)練集中部分時(shí)間序列數(shù)據(jù)的特點(diǎn)，將時(shí)間序列訓(xùn)練集按照是否存在明顯位移和扭曲的特點(diǎn)分為兩大類，計(jì)算每一類的平均錯(cuò)誤率。橫向比較，新方法KFCM 在存在明顯位移和扭曲特點(diǎn)的時(shí)間序列平均錯(cuò)誤率要比趨勢較為一致的時(shí)間序列平均錯(cuò)誤率要低；縱向比較，對(duì)于存在明顯扭曲和位移的時(shí)間序列集，新方法KFCM 相比其他5 個(gè)方法的錯(cuò)誤率低，分類性能更好。

從 圖5 中 看 出，InlineSkate、MoteStrain 和ShapeletSim 這3 個(gè)時(shí)間序列數(shù)據(jù)集具有較明顯的位移和扭曲，故SVM、Bayes 和KMFCM 在處理此類的數(shù)據(jù)集分類時(shí)存在較大的不足，但KFCM算法表現(xiàn)良好。Symbols、TwoLeadECG 和Car 這3 個(gè)時(shí)間序列集中同一類時(shí)間序列數(shù)據(jù)上“幾乎”不存在位移或者扭曲，故SVM、Bayes 和KMFCM 在這3 個(gè)數(shù)據(jù)集上的分類效果比較理想。圖6 也表明新方法KFCM 在InlineSkate、MoteStrain 和ShapeletSim時(shí)間序列數(shù)據(jù)集上有更低的錯(cuò)誤率。

圖5 部分訓(xùn)練集中l(wèi)abel=1 的時(shí)序數(shù)據(jù)

圖6 部分?jǐn)?shù)據(jù)集錯(cuò)誤率比較

3.5 時(shí)間效率比較

時(shí)間序列分類的性能不僅體現(xiàn)在分類效果上，而且也包含了算法的整體時(shí)間消耗。為了更直觀的比較以上6 種分類方法的時(shí)間效率，本文隨機(jī)抽取了 WormsTwoClass、 Ham、 Beef 和 FaceFour 這4 個(gè)時(shí)間序列數(shù)據(jù)集，進(jìn)行方法運(yùn)行時(shí)間效率的對(duì)比實(shí)驗(yàn)。

由圖7 可知，KFCM 方法在4 個(gè)時(shí)間序列數(shù)據(jù)集上的時(shí)間效率比KMFCM、SVM 和Bayes 低，分類時(shí)間較長。但相比于EAIW 和TLCS，KFCM方法所花費(fèi)的時(shí)間則相對(duì)較少?？傮w來講，KFCM的時(shí)間效率要高于EAIW 和TLCS，低于SVM、Bayes 和KMFCM。文獻(xiàn)[15]在大型電力負(fù)荷時(shí)間序列曲線聚類實(shí)驗(yàn)中證明k-shape 的時(shí)間復(fù)雜度高于k-means。本文研究的時(shí)間序列分類方法主要是通過k-shape 提取聚類中心群，該階段的計(jì)算復(fù)雜度較高，導(dǎo)致整體算法在大數(shù)據(jù)環(huán)境下的時(shí)間效率較低，并不適用于大型數(shù)據(jù)集。但結(jié)合分類質(zhì)量來看，KFCM 可以使用較高的時(shí)間效率來獲得較好的分類效果。

圖7 部分?jǐn)?shù)據(jù)集時(shí)間效率比較

4 結(jié) 束 語

鑒于k-shape 在時(shí)間序列數(shù)據(jù)聚類領(lǐng)域的優(yōu)越性，本文提出了一種新的時(shí)間序列分類方法KFCM。該方法首先利用k-shape 對(duì)時(shí)間序列數(shù)據(jù)訓(xùn)練集中的各個(gè)類別包含的成員進(jìn)行聚類，得到聚類中心群。然后，將聚類中心群作為模糊分類的初始聚類中心，根據(jù)隸屬度最大原則確定測試時(shí)間序列數(shù)據(jù)的類別標(biāo)簽。通過實(shí)驗(yàn)驗(yàn)證，與傳統(tǒng)時(shí)間序列分類方法相比，新分類方法具有以下優(yōu)勢：1）通過使用k-shape 聚類算法，提高了對(duì)具有位移和扭曲特征的時(shí)間序列數(shù)據(jù)集分類的適用性，在一定程度上彌補(bǔ)了傳統(tǒng)聚類算法以歐氏距離作為相似性指標(biāo)的不足；2）新分類方法可以利用手肘法確定最佳聚類數(shù)，減小參數(shù)變化對(duì)最終分類結(jié)果的影響；3）與傳統(tǒng)分類方法相比，新分類方法能夠?qū)崿F(xiàn)更好的分類效果，具有一定的優(yōu)越性。然而，該方法相較于傳統(tǒng)分類方法SVM 和Bayes 有較高的時(shí)間復(fù)雜度，在大型數(shù)據(jù)集上應(yīng)用效果不佳，這是未來需要進(jìn)一步研究的工作。