基于K-Shape 的時間序列模糊分類方法

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

（1. 華僑大學信息管理與信息系統系 福建 泉州 362021；2. 華僑大學應用統計與大數據研究中心 福建 廈門 361021）

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

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

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

1 相關理論基礎

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

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

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

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

輸入：兩條Z-score 標準化后的時間序列x，y；

輸出：時間序列x，y的相似性度量dist 和y相對于x的對齊序列y′；

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

對x和y分別進行快速傅里葉變換，即Fx=FFT(x,len)，Fy=FFT(y,len)；

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

定義 2 SE 是從時間序列中提取最具有代表的形態特征，以此進行聚類。根據文獻[12]，k-shape利用SE 方法可以在每種類別的數據中產生一個聚類中心。

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

輸入：Z-score 標準化后的時間序列集合X=[x1,x2,···,xn] （其中每條時間序列的長度為p），與X對齊的參考序列向量R；

輸出：聚類中心矩陣C；

設立對齊序列矩陣M；

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

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

2 時間序列模糊分類

新分類方法首先通過基于k-shape 的聚類中心群方法構建每個類別的聚類中心群，然后結合基于FCM 的模糊分類方法實現對時間序列的分類。該方法具有良好的分類性能。

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

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

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

圖1 k-shape 算法優勢

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

輸入：同一類別的時間序列數據集X=[x1,x2,···,xn]、X的類別標簽A和聚類中心數k；

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

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

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

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

2.2 模糊分類

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

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

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

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

輸出：隸屬度矩陣D；

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

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

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

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

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

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

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

輸入：訓練集X、測試集Y、默認最大迭代次數iter_max 和聚類中心數k；

輸出：測試集Y的類標簽向量L；

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

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

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

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

3 數值實驗與結果分析

為了驗證本文提出算法的有效性，在30 個時間序列數據集上做分類實驗。通過實驗結果可以驗證分類精度的有效性，也可以驗證針對存在位移和扭曲特征的時間序列分類，新方法的適用性。

3.1 實驗設置

算法代碼使用Python 3.7 在Anaconda 科學計算環境中實現，運行所用計算機的CPU 型號為InterCore i5-8250U （1.60 GHz），RAM 為16 GB，操作系統是Windows10 64 位（DirectX 12）。

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

表1 時間序列數據集

在對訓練數據集進行k-shape 聚類時，訓練集的類別和類別數是已知的，需要用k-shape 單獨對訓練集每一個類別包含的時間序列進行聚類，進而確定各類別的聚類中心群。

3.2 參數設置

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

圖2 k值選取對SSE 的影響

3.3 數據分類

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

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

圖3 分類算法錯誤率的比較

圖4 k與錯誤率的關系

表2 各分類算法分類錯誤率

表3 各類算法評價指標

本文選取4 個時間序列數據集，來說明聚類中心數k對分類結果的影響，如圖4 所示。k值對各數據集的分類結果影響不同，對于BeetleFly 數據集，錯誤率最大值和最小值之間差距達到0.23；對于OliveOil 數據集，錯誤率最大值和最小值之間差距為0.06。

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

3.4 實驗分析

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

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

圖5 部分訓練集中label=1 的時序數據

圖6 部分數據集錯誤率比較

3.5 時間效率比較

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

由圖7 可知，KFCM 方法在4 個時間序列數據集上的時間效率比KMFCM、SVM 和Bayes 低，分類時間較長。但相比于EAIW 和TLCS，KFCM方法所花費的時間則相對較少。總體來講，KFCM的時間效率要高于EAIW 和TLCS，低于SVM、Bayes 和KMFCM。文獻[15]在大型電力負荷時間序列曲線聚類實驗中證明k-shape 的時間復雜度高于k-means。本文研究的時間序列分類方法主要是通過k-shape 提取聚類中心群，該階段的計算復雜度較高，導致整體算法在大數據環境下的時間效率較低，并不適用于大型數據集。但結合分類質量來看，KFCM 可以使用較高的時間效率來獲得較好的分類效果。

圖7 部分數據集時間效率比較

4 結 束 語

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