基于分數(shù)微分的時間序列相似性度量及其應用

閆汶朋 汪志濤 袁曉

摘 要 ???：時間序列的相似性度量是時間序列聚類、分類以及其他相關時間序列分析的基礎.傳統(tǒng)基于距離的相似性度量方法，忽視了時間序列可能存在的時間上的聯(lián)系，而將時間序列看作一系列孤立點的集合.對于序列間可能存在的前后聯(lián)系，基于分數(shù)階微分的遺傳特性和記憶特性，提出一種新的時間序列聚類的相似性度量.根據(jù)時間序列的分數(shù)階微分計算新序列間的點距離，將其作為聚類算法的輸入對時間序列進行聚類.仿真實驗結果表明，與基于原始序列矢量距離的聚類結果相比，新的分數(shù)階相似性度量方法表現(xiàn)更好.

關鍵詞 ：時間序列； 聚類； 相似性度量； 分數(shù)階微分

中圖分類號 ：TP391 文獻標識碼 ：A DOI ： ?10.19907/j.0490-6756.2023.043004

Time series similarity measurement based on ?fractional differential and its application

YAN Wen-Peng， WANG Zhi-Tao， YUAN Xiao

（College of Electronics and Information Engineering， Sichuan University， Chengdu 610065， China）

Similarity measures of time series are the basis for time series clustering， classification and other related time series analysis. The traditional distance-based similarity measure ignores the possible temporal connections of time series and treats time series as a series of isolated point sets. For the possible backward and forward connections between sequences， a new similarity measure for time series clustering is proposed based on the genetic and memory properties of fractional order differentiation. The point distances between the new sequences are calculated based on the fractional order differentiation of the time series， and then are used as the input of the clustering algorithm to cluster the time series. The simulation experimental results show that the new fractional-order similarity measure performs better compared with the clustering results based on the original distances.

Time series； Cluster； Similarity measure； Fractional differential

1 引 言

時間序列作為一種隨時間順序變化的數(shù)據(jù)序列，通常具有數(shù)據(jù)量大、維度高、無限遞增、結構復雜等特點.近年來，面對日益龐大的時間序列數(shù)據(jù)集，人工標記的成本日益增加，屬于無監(jiān)督、半監(jiān)督學習的時間序列聚類引起了越來越多研究者的興趣，并被廣泛應用于金融學 ?［1］、醫(yī)療診斷 ?［2，3］、工業(yè)生產控制 ?［4］和生物學 ?［5］等.聚類通過將相似的數(shù)據(jù)放入相關或同質的組中，將具有最小相似性的對象放入其他組中，已成為一種有用的數(shù)據(jù)分析方法.

對于時間序列的相似性研究，很多采用了歐幾里德距離或其演變，但基于矢量的歐式距離及其演變單純的將時間序列看做孤立點的集合，忽視了時間序列可能存在的時間上的聯(lián)系和關鍵點信息，對于序列在時間軸上的偏移也非常敏感，不具備形態(tài)識別能力.針對這些問題，國內外學者們相繼提出了眾多的解決方法：廣泛應用于語音識別領域的DTW ?［6］距離，通過把兩個時間序列進行延伸和縮短，找到距離最短的扭曲距離；隱馬爾可夫模型，利用時間序列隱含的屬性（馬爾可夫性）提高聚類精度.近年來，王瑞等 ?［7］根據(jù)分段序列的斜率變化，劃分形態(tài)模式，把時間序列轉換成字符串序列.李海林等 ?［8］提出動態(tài)時間彎曲與符號距離結合的時間序列距離度量方法，反映了時間序列數(shù)值分布和形態(tài)特征.Soleimani等 ?［9］定義了兩個相似性閾值并確定它們的值，提出了發(fā)展的最長公共子序列（Developed Longest Common Subsequence，DLCSS），解決了LCSS很難確定正確的相似度閾值，導致結果較差的問題.甄遠婷等 ?［10］基于中心Couple函數(shù)捕獲時間序列的動態(tài)相依結構，采用Cramer-von Mises統(tǒng)計量構造了一種新的相似性度量.

本文提出一種基于分數(shù)階微分的時間序列相似性度量，利用分數(shù)階微分的遺傳效應和記憶特性 ?［11］，對原始時間序列數(shù)據(jù)進行分數(shù)階微分計算，再根據(jù)傳統(tǒng)的點與點距離公式計算得到相似度，最后將其作為聚類算法的輸入完成時間序列的聚類.

2 分數(shù)階微分理論基礎

分數(shù)階微積分作為一個重要的數(shù)學分支，近年來，已不斷在科學、工程等領域得到了廣泛的應用，并被引入控制論、流體力學、信號處理及圖像處理等領域 ?［12-18］.對于某些特定的應用，整數(shù)階微分并不能進行很好的描述，需要借助分數(shù)階微分以達到更精確的描述，如：流變本構方程、分數(shù)階控制系統(tǒng)等.相對于整數(shù)階微分，分數(shù)階微分可以提供比整數(shù)階微分更豐富的信息 ?［19］.

2.1 G-L分數(shù)階導數(shù)的定義

分數(shù)階微分有多種不同的定義形式，適合于數(shù)值計算 ?［20］的Grünwald-Letnikov（G-L）分數(shù)階導數(shù)定義為

GL ??a D ?α tf（t）= ?lim ??η→0 ?A ??（α） ηf（t），t∈ a，b ??（1）

A ???（α） ηf（t）=η ??-α∑ ∞ ?j=0 g ??（α） jf（t-jη） ?（2）

g α 0=1，g α j= 1- α+1 j ?g α ?j-1，j=1，2，… ?（3）

式（1）和式（2）中，D為分數(shù)階微分算子； α （可取分數(shù)）為運算階數(shù)； t 表示時間序列當前時刻； η 是采樣步長； ?g ?（α） ?j 為二項式系數(shù)，可通過式（3）遞推求出.

可以看出，在計算分數(shù)微分時，要用到時刻 t 之前所有的歷史數(shù)據(jù)，被加項數(shù)目變得非常大.對于時間序列，隨著數(shù)據(jù)量的增大，考慮所有歷史數(shù)據(jù)，分數(shù)階微分的計算速度會隨之受到影響，因此，在實際計算中，根據(jù)分數(shù)微分加權系數(shù)具有的較快衰減特性，使用短時記憶法則，只考慮時間序列當前時刻近來的過去，即在區(qū)間 ?t-L， ?t ?的行為.

GL ??a D ??α tf（t）≈ ?t-L D ??α tf（t），t>a+L ?（4）

式（4）中， L 是記憶長度.根據(jù)公式，具有下限 a 的分數(shù)導數(shù)可用具有移動下限 t-L 的分數(shù)導數(shù)來逼近.但是，這樣的簡化，在計算精度上會受到某些懲罰，對于 a≤t≤b ，若存在函數(shù) f（t）≤M ，則可利用式（4），由短時記憶原理所引起的誤差，建立估計.

Δ ?= ???GL ??a D ??α tf（t）- ?t-L D ??α tf（t） ≤ ML ?-α ??Γ ?1-α ??，

a+L≤t≤b ??（5）

該不等式可以用來確定給定精度 ε 情況下的記憶長度 L ，有

L≥ ??M ε ?Γ ?1-α ??????1 α ???（6）

A - ????（α） ηf（t）≈η ??-α∑ J ?j=0 g ??（α） jf t-jη ???（7）

式（7）中， J t-Jη≥0 ?表示計算 t 時刻序列點分數(shù)階導數(shù)使用的非局域記憶點數(shù)，使用短時記憶原理，不考慮全部歷史數(shù)據(jù).

G-L定義適用于 α>0 和 α<0 的微分與積分，且當 α=0 時，有 D ??0 ?if i =f i ?，在時間序列處理中，可將初始時刻 a 看為0.

2.2 G-L分數(shù)階微分的數(shù)值計算

式（1）也可寫為： ???GL ??a D ??α tf（t）=A ?（α） ηf（t）+ o ?η ?，當選擇的采樣步長 η 足夠小時，式（1）中的求極限操作可以忽略，G-L定義的分數(shù)階導數(shù)便可以由 ????GL ??a D ??α tf（t）≈ A ??（α） ηf（t） 直接計算，再結合短時記憶原理，減少計算過程.

與傳統(tǒng)的整數(shù)階微分只使用當前和前幾個有限步長內的函數(shù)值相比，分數(shù)階微分具有遺傳特性和記憶特性，涉及到 t 時刻序列點的前 J 個非局域記憶點序列值，可以捕捉時間序列的前后關系，與其他未將時間序列做相應計算，把各序列點看作孤立存在的方法相比，分數(shù)階微分（如圖1）考慮了時間序列的時間順序，使時間序列相似性的刻畫具有非局域的記憶特性.

對于精度損失的問題，對比了通過分數(shù)導數(shù)逼近式（1）與運用短時記憶原理計算式（7）計算結果的區(qū)別（CBF訓練集， α ?設置為0.01），如圖2所示.可以看出，利用短時記憶原理，在不同記憶點數(shù) J 的情況下，分數(shù)階導數(shù)計算結果與逼近式計算結果接近完全重合，誤差可忽略不計.

3 ?基于分數(shù)階微分的時間序列相似性度量

給定兩個長度為 n 的時間序列 x、y ，傳統(tǒng)的歐式距離 d ?E（ x，y ）= ?∑ ?n ?i=1（x ?i-y ?i） ??1/2 是時間序列聚類中最常用的相似度量.有研究表明，在時間序列分類精度上，歐式距離具有驚人的競爭力 ?［21］，在諸多算法中都有廣泛的應用.

時間序列由于具有先后順序，把時間序列各點看做孤立的存在并不合理，因此，需要考慮時間序列中可能存在的時間上的聯(lián)系，以達到更好的聚類效果.基于分數(shù)階微分的時間序列相似度，對原始時間序列的每一點求其分數(shù)階微分，可以看做計算一段序列的加權累計值.由于分數(shù)階微分計算結果中某些數(shù)值較大，對其進行標準化處理，通過將所有數(shù)據(jù)與數(shù)據(jù)最小值的絕對值相加來轉換數(shù)據(jù)，使數(shù)據(jù)的最小值變?yōu)?，其他所有數(shù)據(jù)變?yōu)檎龜?shù)，再使用Z-Score標準化處理數(shù)據(jù).

D ?～ ?αx i= ?D ?αx i-μ σ ??（8）

式（8）， ?x ?i 表示時間序列的第 i 點數(shù)據(jù)；D ?～ ?αx i 表示時間序列各時間點的 ?α ?階分數(shù)微分； μ 表示分數(shù)階微分時間序列的均值； σ 表示標準差；D ?～ ?αx i 表示分數(shù)階微分時間序列各點標準化后的值.

算法1描述了具體過程.輸入為時間序列各個時刻的函數(shù)值構造的向量，第（1）行設定初始化步長，（2）（3）行遞推計算二項式系數(shù)，（4）～（8）根據(jù)相應的非局域記憶點數(shù) J 計算給定時間序列的分數(shù)階微分值，最后，標準化返回結果.

算法1 ??偽代碼：分數(shù)階微分

輸入： ?原始時間序列 ?T ?i= t ?1， t ?2，…， t ?n

輸出： ??標準化的分數(shù)微分時間序列

（1） 初始化 η

（2） for ??j =2; ?j ??≤ len （t）; j ++ do

（3） ???ω← CalculateWeights（ ω ， α ）

end

（4） for ?i ?= 1; ?i ?≤ ?len（ t ）; ?i ++ do

（5） ?if ?i ??≥J ?then

（6） ???y ←CalFraDiff（ ω 1 ， f ??1， h ， α ）

（7） else

（8） ???y ←CalFraDiff（ ω 2 ， f ??2， h ， α ）

end

（9） return Standardization（ y ）

再通過處理后的序列計算歐式距離得到相似度，定義如下.

d ?α F（ x，y ）=（∑ n i=0 （ D ?～ ??ax ?i- D ?～ ??ay ?i） 2） ?1/2=

（∑ n i=0 （A ～ ??α ηx ?i-A ～ ??α ηy ?i） 2） ?1/2 ?（9）

式（9）， A α ηx i 和 A α ηy i 為時間序列各時間點的 α 階分數(shù)微分計算表 達式（式2）； A ～ ?α ηx i 和 A ～ ?α ηx i 表示對其進行標準化； d α F（ x，y ）為最終計算得到的相似度.

4 實 驗

編譯工具Python3.9.8，操作系統(tǒng)Window11，CPU/AMD Ryzen 7 5800H with Radeon Graphics，主頻3.20 GHz，內存16 GB，固態(tài)硬盤容量512 G.

4.1 實驗數(shù)據(jù)與實驗方法

本文實驗中用到的時間序列數(shù)據(jù)集為UCR時間序列數(shù)據(jù)庫 ?［22］中收集的標準時間序列數(shù)據(jù)集，每個數(shù)據(jù)集包含一個訓練集和一個測試集，具體信息如表1.

表1中， K 為聚類的數(shù)目; L 為時間序列的長度; N 為數(shù)據(jù)集的訓練集數(shù)目; M 為數(shù)據(jù)集的測試集數(shù)目.

對于分數(shù)微分計算后的序列，在訓練集上比較計算序列間歐式距離與改進的DTW距離LB_Keogh作為聚類輸入的聚類準確度與時間消耗，如圖3所示.

可以看出，計算兩個序列間的歐式距離作為K-Means聚類的輸入到完成聚類過程所需的時間遠遠小于LB_Keogh距離作為聚類輸入所需的時間，且隨著時間序列數(shù)據(jù)量的增大，時間差異更加明顯.在聚類準確度方面，兩種距離互有優(yōu)劣，因此，綜合考量時間與準確度因素，選擇歐氏距離作為計算處理后序列間相似度的距離公式.

實驗總體采用不同的距離度量，并通過K-Means聚類算法實現(xiàn)對時間序列的聚類，同時也采用了層次聚類與基于u-shapelets的時間序列聚類算法 ?［23］進行相關實驗，最后對所得結果進行對比分析.分數(shù)微分歐式（Fractional Differentiation Euclidean， FDE）距離首先對數(shù)據(jù)集中的時間序列進行 α 階分數(shù)微分運算，將其標準化后，再根據(jù)運算后序列的歐式距離計算得到兩個時間序列的相似度，以此作為聚類算法的輸入完成聚類，并使用 R （Rand Index）評價聚類質量.

R= a+d a+b+c+d ??（12）

式（12）中， a 為在實際類別中為同一類且在聚類結果中也為同一類的數(shù)據(jù)點對數(shù); d 為在實際類別中不為同一類且在聚類結果中也不屬于同一類的數(shù)據(jù)點對數(shù); b 為在實際類別中為同一類但在聚類結果中不屬于同一類的數(shù)據(jù)點對數(shù); c 為在實際類別中不為同一類但在聚類結果中屬于同一類的數(shù)據(jù)點對數(shù).

計算相似度時，記憶點數(shù) J 和階數(shù) α 的不同將會影響距離度量，并最終影響聚類質量.圖4給出了單獨的不同 J 、 ?α 分別對于聚類質量評價的影響.通過將式（6）計算得到的距離作為聚類算法 ?［24］的輸入，獲得了兩個變量 J、 ?α 對聚類質量的影響（如圖5）.

為了確定最佳 J 、 α 值，本文通過在訓練集中，觀察不同 J 和 α 對于聚類質量評價 R 的影響，再在測試集中，利用訓練集得到的最佳 J ?、α 進行多次實驗取均值得到最終結果.

4.2 實驗結果分析

4.2.1 準確度對比 ?對基于LB_Keogh距離、歐式距離、余弦距離、Pearson相關系數(shù)的K均值聚類、層次聚類 ?［25］、基于u-shapelets的時間序列聚類結果比較如表2所示，其中， J 、 α 分別為獲得的最佳記憶點數(shù)與分數(shù)階導數(shù)的階數(shù)，Win一行標明了采用5種不同的距離度量和聚類算法在21個數(shù)據(jù)集上取得最佳效果的數(shù)量.

從表2可知，在21個時間序列數(shù)據(jù)集中，本文提出的FDE距離分別在14個數(shù)據(jù)集、14個數(shù)據(jù)集、15個數(shù)據(jù)集、16個數(shù)據(jù)集上優(yōu)于基于余弦距離、LB_Keogh距離、歐氏距離、Pearson相關系數(shù)的K-Means聚類，在16個數(shù)據(jù)集上優(yōu)于層次聚類的結果，14個數(shù)據(jù)集上優(yōu)于基于u-shapelets的時間序列聚類.實驗表明，雖然在不同的數(shù)據(jù)集上，基于各種距離的K-Means聚類、層次聚類和基于u-shapelets的時間序列聚類算法都能或多或少取得最佳的聚類效果，但是本文所提出的方法整體效果最佳.

4.2.2 運行時間對比 ?歐式距離、DTW距離是常用的基于距離來衡量相似性的指標.FDE在歐氏距離的基礎上，增加了分數(shù)微分的計算過程，對比FDE與此兩種距離作為K-Means聚類算法的輸入，并比較了層次聚類與基于u-shapelets的時間序列聚類算法在10個時間序列數(shù)據(jù)集上完成聚類操作所需的時間.結果如表3所示，可以看出，F(xiàn)DE在運行時間上遜于基于歐幾里得距離的K-means聚類與層次聚類，大幅優(yōu)于基于LB_Keogh距離的k-means聚類和基于u-shapelets的時間序列聚類，具有更高的時間效率.

5 結 論

為了解決傳統(tǒng)的基于距離的相似性度量方法將時間序列矢量看作孤立點存在的問題，本文提出利用時間序列的分數(shù)階微分構造新的時間序列，用構造的新序列間的歐式距離計算相似度作為K-Means聚類算法的輸入完成聚類過程.

通過與基于傳統(tǒng)距離度量的K-Means聚類、層次聚類以及基于u-shapelets的聚類結果進行比較，可以得出，本文方法相對于歐式距離簡單快速的實現(xiàn)方式，犧牲了一些計算速度，在一定程度上提高了聚類準確度.

后續(xù)研究中，我們可考慮以下兩個方面：（1） 對于時間序列先計算分數(shù)階微分，再計算點距離計算時間較長的問題，可考慮第二次計算過程使用符號聚合近似、主成分分析等數(shù)據(jù)降維和特征表示方式來計算相似度，減少計算過程，以加快計算速度；（2） 利用深度學習，對獲得的新序列進行特征提取、距離矩陣計算的自適應權重等方式，以得到的更好的聚類結果.

參考文獻：

［1］ ??Ruiz E J， Hristidis V， Castillo C， ?et al . Correlating financial time series with micro-blogging activity ?［C］∥Proceeding of the fifth ACM International Conference on Web Search and Data Mining. New York： ACM， 2012： 513．

［2］ ?Li G， Braeysy O， Jiang L， ?et al . Finding time series discord based on bit representation clustering［J］. Knowl-Based Syst， 2013， 54： 243.

［3］ ?Tavenard R， Malinowski S. Cost-aware early classification of time series ［C］//Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Cham： Springer， 2016.

［4］ ?Zalewski W， Silva F， Maletzke A G， ?et al . Exploring shapelet transformation for time series classification in decision trees ［J］. Knowl-Based Syst， 2016， 112： 80.

［5］ ?Jiang D， Pei J， Ramanathan M， ?et al. ?Mining gene-sample-time microarray data： a coherent gene cluster discovery approach ［J］. Knowl Inf Syst， 2007， 13： 305.

［6］ ?Salvador S， Chan P. Toward accurate dynamic time warping in linear time and space ［J］. Intell Data Anal， 2007， 11： 561.

［7］ ?王瑞， 賈瑞玉. 基于形態(tài)模式的時間序列相似性度量算法［J］.計算機應用與軟件， 2017， 34： 253.

［8］ ?李海林， 梁葉.基于數(shù)值符號和形態(tài)特征的時間序列相似性度量方法［J］.控制與決策， 2017， 32： 451.

［9］ ?Soleimani G， Abessi M. DLCSS： a new similarity measure for time series data mining［J］.Eng Appl Artif Intel， 2020， 92： 103664.

［10］ ?甄遠婷， 冶繼民， 李國榮.基于中心Copula函數(shù)相似性度量的時間序列聚類方法［J］.陜西師范大學學報： 自然科學版， 2021， 49： 29.

［11］ 袁曉.分數(shù)微積分—理論基礎與應用導論［M］.北京： 電子工業(yè)出版社， 2021.

［12］ Huang J， Li H， Chen Y Q， ?et al . Robust position control of PMSM using fractional-order sliding mode controller ［C］//Abstract and Applied Analysis. Hindawi： ［s.n.］， 2012.

［13］ 伍小二.一類無界變差函數(shù)的分數(shù)階微積分及其分形維數(shù)［D］.南京： 南京理工大學， 2018.

［14］ 徐明瑜， 譚文長．中間過程、臨界現(xiàn)象—分數(shù)階算子理論、方法、進展及其在現(xiàn)代力學中的應用［J］．中國科學Ｇ輯： 物理學 力學 天文學， 2006， ?36： 225.

［15］ 蒲亦非， 袁曉， 廖科， 等．現(xiàn)代信號分析與處理中分數(shù)階微積分的五種數(shù)值實現(xiàn)算法［J］．四川大學學報： 工程科學版， 2005， 37： 118.

［16］ 楊柱中， 周激流， 晏祥玉， 等.基于分數(shù)階微分的圖像增強［J］.計算機輔助設計與圖形學學報， 2008， 20： 343.

［17］ 陳衛(wèi)衛(wèi)， 王衛(wèi)星， 閆迪. 基于分數(shù)階微分Frangi的夜間車道線檢測［J］.四川大學學報：自然科學版，2021， 58： 022001.

［18］ 彭朝霞， 蒲亦非. 基于分數(shù)階微分的卷積神經網絡的人臉識別［J］.四川大學學報：自然科學版， 2022， 59： 012001.

［19］ 薛定宇.分數(shù)階微積分學與分數(shù)階控制［M］.北京：科學出版社， 2018.

［20］ 周宇， 袁曉， 張月榮. 基于IFFT的Lubich數(shù)字分數(shù)微分器系數(shù)的快速算法［J］.太赫茲科學與電子信息學報， 2022， 20： 608.

［21］ Lkhagva B， Yu S， Kawagoe K. New time series data representation ESAX for financial applications［C］// International Conference on Data Engineering Workshops. Atlanta： IEEE Computer Society， ?2006.

［22］ Dau H A， Keogh E， Kamgar K， ?et al . The ucr time series classification archive ［EB/OL］. ［2022-05-22］. https：//www.cs.ucr.edu/eamonn/time series data 2018.

［23］ 余思琴， 閆秋艷， 閆欣鳴. 基于最佳u-shapelets的時間序列聚類算法［J］.計算機應用， 2017， 37： 2349.

［24］ 李海林， 張麗萍.時間序列數(shù)據(jù)挖掘中的聚類研究綜述［J］.電子科技大學學報， 2022， 51： 416.

［25］ 陳美云.時間序列聚類分析中幾種算法的研究及應用［D］. 徐州： 中國礦業(yè)大學， 2019.