基于子序列相似性的時(shí)間序列語義挖掘算法

陸怡，王鵬，汪衛(wèi)

（1.復(fù)旦大學(xué) 軟件學(xué)院，上海 201203；2.復(fù)旦大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，上海 201203）

0 概述

時(shí)間序列數(shù)據(jù)是在一段時(shí)間內(nèi)以固定的時(shí)間間隔采集的數(shù)據(jù)點(diǎn)序列，用于描述現(xiàn)象隨時(shí)間變化的情況，已成為日常生活中重要的信息記錄形式。隨著大數(shù)據(jù)時(shí)代的到來以及大規(guī)模計(jì)算能力的提升，時(shí)間序列數(shù)據(jù)分析與挖掘已成為研究熱點(diǎn)，廣泛應(yīng)用于醫(yī)療、交通、金融等領(lǐng)域。在現(xiàn)實(shí)場景中，時(shí)序數(shù)據(jù)雖然存在不同的演化規(guī)律，例如記錄服務(wù)器CPU 使用情況的監(jiān)控?cái)?shù)據(jù)、反映患者健康狀況的心電數(shù)據(jù)以及表征市場行情的商品銷售數(shù)據(jù)，但這些領(lǐng)域各異的數(shù)據(jù)的內(nèi)核通常是一致的，會根據(jù)觀測對象或系統(tǒng)的實(shí)際物理狀態(tài)，呈現(xiàn)出不同的波動形式。因此，挖掘時(shí)間序列中潛在的語義信息，實(shí)際上是識別被監(jiān)測系統(tǒng)的物理狀態(tài)，通過將時(shí)間序列轉(zhuǎn)換為狀態(tài)序列，實(shí)現(xiàn)數(shù)據(jù)壓縮或者異常檢測。

時(shí)間序列具有數(shù)據(jù)量大、復(fù)雜度高、干擾信息多等特性，一般采用特征提取手段對時(shí)間序列進(jìn)行加工處理。針對時(shí)間序列的語義挖掘，主要分為基于領(lǐng)域特征、基于全局特征、基于子序列相似性三類。基于領(lǐng)域特征的時(shí)間序列語義挖掘算法除了時(shí)間序列數(shù)據(jù)之外，還引入了領(lǐng)域知識或者帶標(biāo)簽的數(shù)據(jù)。文獻(xiàn)［1］針對金融時(shí)間序列的自相關(guān)特征，提出一種基于ARMA 模型［2］的時(shí)間序列分割算法。文獻(xiàn)［3］根據(jù)心電時(shí)間序列的特點(diǎn)，提出一種基于殘差平衡及邊界約束的分段線性回歸方法以得到時(shí)間序列的分段表示。文獻(xiàn)［4］通過從訓(xùn)練集中構(gòu)建特征的高斯概率分布模型，實(shí)現(xiàn)有監(jiān)督的狀態(tài)挖掘。基于全局特征的時(shí)間序列語義挖掘算法使用全局特征對時(shí)間序列進(jìn)行概括。全局特征又可細(xì)分為斜率和均值兩種類型。一種以pHMM［5］為代表，從斜率的角度將時(shí)間序列簡化成線段序列，并利用隱馬爾科夫模型（Hidden Markov Model，HMM）［6］指導(dǎo)線段的聚類，最終獲得狀態(tài)信息。另一種以AutoPlait［7］和StreamScope［8］為代表，從均值的角度描述不同的狀態(tài)，得到多層的隱馬爾科夫模型，并通過最小描述長度（Minimum Description Length，MDL）［9］對可選的模型進(jìn)行評估，從而得到時(shí)間序列的最優(yōu)表示。基于均值的算法還可進(jìn)一步應(yīng)用于多維或高階時(shí)間序列，例如DBSE［10］以及在AutoPlait 基礎(chǔ)上提出的CUBEMARKER［11］。在基于子序列相似性的時(shí)間序列語義挖掘算法中，具有代表性的子序列會頻繁出現(xiàn)。實(shí)際上，大量對于時(shí)間序列的分析是從子序列入手的，例如文獻(xiàn)［12-13］實(shí)現(xiàn)的基序列挖掘，文獻(xiàn)［14］提出的基于子序列的時(shí)間序列分類方法。但是，基于子序列相似性的語義挖掘算法仍在初步研究階段。FLUSS［15-16］和ESPRESSO［17］作為典型代表，僅能識別出狀態(tài)的轉(zhuǎn)變點(diǎn)。

目前，多數(shù)時(shí)間序列語義挖掘算法對于時(shí)序數(shù)據(jù)特征有一定的約束條件，因此難以處理海量且形式各異的時(shí)序數(shù)據(jù)。本文提出一種基于子序列相似性的時(shí)間序列語義挖掘算法SEDIS，通過計(jì)算子序列的相似性，將時(shí)間序列分割成片段序列進(jìn)行兩級聚類，識別出時(shí)間序列中潛在的物理狀態(tài)，使其具備在不同應(yīng)用場景下的通用處理能力。

1 問題描述

定義1（時(shí)間序列）時(shí)間序列是對某個(gè)事物或系統(tǒng)進(jìn)行連續(xù)同間隔的測量得到的數(shù)值序列，可表示為T=(t1，t2，…，tL)，其中，L為時(shí)間序列長度。

定義2（子序列）子序列是由時(shí)間序列中一段連續(xù)的值組成的數(shù)值序列。Ti，l=(ti，ti+1，…，ti+l-1)表示從第i個(gè)時(shí)間點(diǎn)開始，長度為l的子序列。

時(shí)間序列作為事物或系統(tǒng)某個(gè)剖面的觀測結(jié)果，按照時(shí)間序列反映的物理意義將其片段組成若干分段，并根據(jù)分段的內(nèi)在聯(lián)系形成狀態(tài)序列，稱為分段表示與狀態(tài)表示。

定義3（分段表示）時(shí)間序列T的分段表示可定義為SEG(T)={s1，s2，…，sn}，其中si(1 ≤i≤n)是T的一個(gè)子序列。

定義4（狀態(tài)表示）時(shí)間序列T的狀態(tài)表示在分段表示的基礎(chǔ)上，引入了分段的物理狀態(tài)，可定義為STATE(T)={＜s1，c1＞，＜s2，c2＞，…，＜sn，cn＞}，其中ci表示分段si的狀態(tài)。假設(shè)m表示物理狀態(tài)個(gè)數(shù)，則ci是一個(gè)介于1和m之間的正整數(shù)，且1 ≤m≤n。

根據(jù)上文描述，SEDIS 的目標(biāo)任務(wù)是尋找一個(gè)符合用戶期望的狀態(tài)表示STATE(T)以描述或壓縮原時(shí)間序列T，其中包含的物理狀態(tài)個(gè)數(shù)m由用戶定義。實(shí)際上，如果將時(shí)間序列中的每個(gè)時(shí)間點(diǎn)視作一個(gè)對象，該任務(wù)也可理解為聚類任務(wù)，目標(biāo)是將反映同一狀態(tài)的觀測值聚集在同一類簇中。

2 時(shí)間序列語義挖掘算法

SEDIS 基于以下基本假設(shè)：在同一狀態(tài)下，由于具有代表性的子序列會頻繁出現(xiàn)，因此屬于同一狀態(tài)的分段之間必然存在多個(gè)相似的子序列。SEDIS分為兩個(gè)階段：1）基于子序列相似性結(jié)合基于密度的聚類方法構(gòu)建組成分段的片段；2）采用貪心策略對片段進(jìn)行預(yù)聚類，再通過k-means 聚類識別出片段對應(yīng)的物理狀態(tài)。

2.1 片段分割

為避免兩兩計(jì)算子序列相似性帶來的巨大計(jì)算開銷，SEDIS 采用基于概率的抽樣方法，每輪選取一個(gè)子序列作為參考子序列。如果兩個(gè)子序列相似，則它們與參考子序列的距離相近。

2.1.1 子序列相似性的優(yōu)化計(jì)算

子序列相似性通過標(biāo)準(zhǔn)化歐式距離進(jìn)行度量。在歐式距離的基礎(chǔ)上，預(yù)先對每個(gè)子序列進(jìn)行標(biāo)準(zhǔn)化操作，使得子序列各個(gè)時(shí)間點(diǎn)對應(yīng)的數(shù)值的均值等于0、標(biāo)準(zhǔn)差等于1，從而消除了幅度縮放、基線漂移等對波形相似性的影響。具體而言，兩個(gè)長度等于l的子序列X=(x1，x2，…，xl)和Y=(y1，y2，…，yl)的標(biāo)準(zhǔn)化歐式距離可通過式（1）計(jì)算：

其中：μ表示均值；σ表示標(biāo)準(zhǔn)差。

假設(shè)時(shí)間序列的長度是L，參考子序列的長度是l，需要計(jì)算參考子序列與其余L-l+1 個(gè)長度同樣等于l的子序列的標(biāo)準(zhǔn)化歐式距離。由于時(shí)間序列的數(shù)據(jù)量通常較大，因此SEDIS 采用文獻(xiàn)［18］提出的基于快速傅里葉變換［19］的算法，加速子序列的相似性計(jì)算。首先對時(shí)間序列和參考子序列使用快速傅里葉變換等操作得到兩者的滑動點(diǎn)積，然后以滑窗的形式增量地記錄子序列的平均值和標(biāo)準(zhǔn)差，從而基于O（LlogaL）的時(shí)間復(fù)雜度求出L-l+1 個(gè)子序列對的標(biāo)準(zhǔn)化歐式距離。

由于相似是一個(gè)主觀的評判標(biāo)準(zhǔn)，難以通過量化后的數(shù)值完成二分類，因此為得到多個(gè)相似子序列以支持分段，通過最大堆篩選出與參考子序列距離最近的k個(gè)子序列完成初過濾。

2.1.2 基于密度的優(yōu)化聚類

由于參數(shù)k的取值將極大影響k個(gè)子序列的相似情況，但時(shí)間序列的平滑特性以及全自動的應(yīng)用要求，難以通過類似手肘法的方案提供一個(gè)k的建議值，因此SEDIS 采用基于密度的聚類方法［20］對k個(gè)子序列進(jìn)行再過濾，其核心思想為屬于同一分段的子序列在時(shí)間軸上會緊密地聚集在一起。基于密度的聚類方法能夠自動地將鄰近的子序列分到一個(gè)類中，進(jìn)而識別出潛在噪聲。具體地，聚類對象是k個(gè)子序列，聚類相似性標(biāo)準(zhǔn)取決于子序列的起始時(shí)間點(diǎn)。子序列對Ti，l和Tj，l的距離可簡單表示為|i-j|，即兩個(gè)子序列在時(shí)間軸上越接近，越有可能聚成一類。

針對該距離度量，本文提出一種基于密度的優(yōu)化聚類方法。在確定每個(gè)子序列Ti，l是否為核心點(diǎn)時(shí)，需要檢索其EEps鄰域內(nèi)存在的子序列數(shù)量。由于相似性僅考慮起始時(shí)間點(diǎn)，因此問題可簡化成找到滿足{Tj，l|i-EEps≤j≤i+EEps}的子序列集合。假設(shè)子序列已經(jīng)按照起始時(shí)間點(diǎn)升序排序，則可以通過兩次二分搜索快速定位第一個(gè)滿足j≥i-EEps的子序列和最后一個(gè)滿足j≤i+EEps的子序列。兩者之間包含的子序列數(shù)量即Ti，l的EEps鄰域內(nèi)存在的子序列數(shù)量。通過二分搜索，該步驟的時(shí)間復(fù)雜度可降至對數(shù)級。

經(jīng)過基于密度的聚類方法過濾掉一部分的噪聲子序列后，剩余的子序列間可能存在重疊。為便于后續(xù)處理，在每一個(gè)形成的類簇中，找出其中起始時(shí)間點(diǎn)最小的子序列Ti，l和起始時(shí)間點(diǎn)最大的子序列Tj，l，以此構(gòu)建一個(gè)新的子序列Ti，j+l-i，該子序列即為一個(gè)候選分段。

2.1.3 基于概率的迭代模式

由單個(gè)參考子序列得到的候選分段僅能表征一個(gè)狀態(tài)，因此需要引入多個(gè)不同的參考子序列使其涵蓋所有的物理狀態(tài)。本文提出一種基于概率的迭代模式，根據(jù)候選分段的情況動態(tài)地調(diào)整子序列被選為參考子序列的概率，設(shè)計(jì)思想為對于沒有被包含在候選分段中的子序列給予更多的機(jī)會。具體地，對于所有的子序列，賦予相同的初始概率，以模擬均勻分布。在每一輪完成后，將包含在候選分段中的子序列的概率減半，從而直接影響下一輪參考子序列的選取情況。

至此，SEDIS 產(chǎn)生若干候選分段，一組候選分段對應(yīng)一個(gè)參考子序列，多組候選分段間可能存在重疊。候選分段的起始點(diǎn)和終止點(diǎn)表示候選的狀態(tài)轉(zhuǎn)變點(diǎn)。根據(jù)這些候選點(diǎn)對所有候選分段進(jìn)行分割，產(chǎn)生的子序列稱為片段。一個(gè)分段至少產(chǎn)生一個(gè)片段。值得注意的是，片段不一定足以覆蓋整個(gè)時(shí)間序列，對于漏檢片段的處理，將在下文進(jìn)行具體介紹。

2.2 狀態(tài)識別

狀態(tài)識別是根據(jù)片段反映的物理狀態(tài)對其進(jìn)行聚類，同一類簇的片段對應(yīng)同一狀態(tài)。因此，狀態(tài)識別的核心為片段在物理狀態(tài)層面上的相似性定義。

2.2.1 基于貪心策略的預(yù)聚類

在聚類前，時(shí)間序列通常是平滑演進(jìn)的。排除監(jiān)測設(shè)備的突發(fā)故障，時(shí)間序列在狀態(tài)轉(zhuǎn)變點(diǎn)附近的波動通常較小，因此會導(dǎo)致附近的子序列被分割成多個(gè)片段。為提高效率，本文對所有生成的片段采用貪心策略進(jìn)行預(yù)聚類，使用棧模擬貪心策略的執(zhí)行，具體步驟如下：

1）將所有片段按照起始點(diǎn)的降序依次推入棧中。

2）從棧中推出棧頂片段Ti，p，找出所有包含該片段的候選分段C={Tj，q|j≤i＜i+p≤j+q}。

3）計(jì)算集合C中所有候選分段的終止點(diǎn)的平均值A(chǔ)=，其中|C|表示集合C的元素個(gè)數(shù)。

4）從C中選擇終止點(diǎn)最接近A的候選分段。將Ti，p的起始點(diǎn)i和選中的候選分段的終止點(diǎn)j+q-1 組合形成新的片段Ti，j+q-i。

5）從棧中推出新的棧頂片段，如果被Ti，j+q-i包含，則略過；否則，重復(fù)步驟2～步驟5 直到棧中無剩余元素。

基于上述步驟，在保留片段原有語義信息的同時(shí)，通過片段間的合并減少了片段數(shù)量，提高了算法運(yùn)行效率。

2.2.2 基于k-means 的再聚類

根據(jù)聚類的任務(wù)描述：將沒有分類標(biāo)簽的數(shù)據(jù)集分為若干個(gè)簇［21］，再結(jié)合狀態(tài)識別目標(biāo)，假設(shè)給定一個(gè)在物理狀態(tài)層面上的相似性度量，通過聚類可將片段組織成多個(gè)類簇，每個(gè)類簇對應(yīng)一個(gè)狀態(tài)。

SEDIS 的基本假設(shè)為屬于同一狀態(tài)的片段之間存在多個(gè)相似的子序列，因此基于片段分割的過程，提出一種新的相似性度量函數(shù)。為便于描述，給定一個(gè)片段Pi，輔助向量Oi是一個(gè)r維的向量，其中r是參考子序列的總個(gè)數(shù)。Oi的每一維是0 或者1，表示Pi是否被由該參考子序列生成的候選分段包含，進(jìn)而定義兩個(gè)片段Pi和Pj的相似性，如式（2）所示：

其中：&表示按位與；sum 表示求和；min 表示求最小值。

式（2）計(jì)算的是兩個(gè)片段在同一候選分段中的共現(xiàn)頻率，在一定程度上反映了兩個(gè)片段包含的相似子序列的數(shù)量。該值越大，表明兩者屬于同一狀態(tài)的可信度越大。

基于相似性定義，采用k-means 聚類［22］算法得到片段的隱含結(jié)構(gòu)，即片段的物理狀態(tài)，具體步驟如下：

1）隨機(jī)選取m個(gè)片段作為初始的聚類中心，其中m是用戶指定的物理狀態(tài)個(gè)數(shù)。

2）將每個(gè)片段分配到相似性最高的聚類中心所在的類簇中。

3）對于每個(gè)類簇，選取其中與所有其他片段相似性之和最大的片段作為新的聚類中心。

4）重復(fù)步驟2 和步驟3，直到聚類中心不再變化。

至此，每個(gè)類簇對應(yīng)一個(gè)物理狀態(tài)。

2.2.3 基于k 最近鄰的漏檢片段分類

需要指出的是，雖然SEDIS 在片段分割階段通過基于概率的迭代模式盡可能地保證參考子序列涵蓋全部的物理狀態(tài)，但是片段的漏檢現(xiàn)象仍可能存在，即在時(shí)間序列中，有部分子序列并未包含在任何候選分段中。對于這部分子序列，或稱為漏檢片段，SEDIS 采用k 最近鄰（k Nearest Neighbor，kNN）算法進(jìn)行分類處理。在實(shí)際應(yīng)用中，將每個(gè)漏檢片段作為參考子序列，考察在標(biāo)準(zhǔn)化歐式距離度量下與其最相似的k個(gè)子序列的物理狀態(tài)，取頻次最高的作為分類標(biāo)簽。

2.3 時(shí)間復(fù)雜度分析

SEDIS 主要包括片段分割和狀態(tài)識別兩個(gè)階段。理論上，第一階段的時(shí)間復(fù)雜度與時(shí)間序列的長度強(qiáng)相關(guān)，第二階段的時(shí)間復(fù)雜度與片段的數(shù)量強(qiáng)相關(guān)，后者遠(yuǎn)小于前者，同時(shí)在實(shí)際應(yīng)用中證明，第一階段的時(shí)間開銷在總時(shí)間開銷中占比較大，因此本節(jié)將主要圍繞該階段展開分析。

片段分割包括對每個(gè)參考子序列執(zhí)行相似性計(jì)算、相似子序列篩選、聚類3 個(gè)步驟。假設(shè)時(shí)間序列的長度等于n，參考子序列的個(gè)數(shù)等于r，每次只保留k個(gè)與參考子序列最相似的子序列，則該階段的時(shí)間復(fù)雜度為O（r×（nlogan+nlogak+klogak））。但需要指出的是，由執(zhí)行快速傅里葉變換引入的O（nlogan）的時(shí)間復(fù)雜度在實(shí)際應(yīng)用中是近似線性的，文獻(xiàn)［18］認(rèn)為這可能是由于該算法已在工程領(lǐng)域中得到高度優(yōu)化。此外，r和k作為輸入?yún)?shù)，與n不存在線性增長關(guān)系，這意味著對于長時(shí)間序列，r和k也可視作常量。因此，SEDIS 的總時(shí)間復(fù)雜度是近似線性的。

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

實(shí)驗(yàn)主要分為3 個(gè)部分：1）驗(yàn)證SEDIS 所得的物理狀態(tài)的可解釋性；2）將SEDIS 在時(shí)間序列分割和狀態(tài)識別兩階段的準(zhǔn)確率和運(yùn)行效率與其他算法進(jìn)行對比；3）驗(yàn)證SEDIS 對于相關(guān)參數(shù)的魯棒性。

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

SEDIS 使用Matlab 實(shí)現(xiàn)。實(shí)驗(yàn)運(yùn)行于配置Intel Core i5 處理器、1.4 GHz主頻、帶 有8 GB 內(nèi)存的MAC 筆記本電腦上。

實(shí)驗(yàn)數(shù)據(jù)集主要細(xì)分為以下2 類：1）Barbet、Fetal、SP02 和ECG 數(shù)據(jù)集，這類數(shù)據(jù)集包括狀態(tài)變化更少且長度更短的時(shí)間序列，選自文獻(xiàn)［18］中的32 個(gè)數(shù)據(jù)集，其中涵蓋醫(yī)療、生物、工業(yè)等領(lǐng)域相關(guān)數(shù)據(jù)，以證明SEDIS 的通用性；2）PAMAP 數(shù)據(jù)集，這類數(shù)據(jù)集包括狀態(tài)更多且長度更長的時(shí)間序列，選自PAMAP 運(yùn)動數(shù)據(jù)集［23-24］，是傳感器采集的監(jiān)測數(shù)據(jù)，反映傳感器佩戴者進(jìn)行的有氧運(yùn)動種類，如慢走、跑步、踢足球等。5 個(gè)數(shù)據(jù)集的具體信息如表1所示。

表1 數(shù)據(jù)集信息統(tǒng)計(jì)Table 1 Data set information statistics

SEDIS 主要涉及參考子序列長度l、參考子序列個(gè)數(shù)r以及與參考子序列最相似的子序列個(gè)數(shù)k這3 個(gè)參數(shù)。由于SEDIS 基于子序列相似性，因此l的推薦值是代表性子序列的長度。例如，對于心電圖（Electrocardiogram，ECG）序列，l可設(shè)置成一次心跳的時(shí)長。借助該推論提出一種自動化設(shè)置參考子序列長度的方法。具體地，利用快速傅里葉變換將時(shí)間序列從時(shí)域映射到頻域，此時(shí)能量最大的頻率f即主導(dǎo)頻率，頻率的倒數(shù)為代表性子序列的周期l=。根據(jù)此規(guī)則，對于5 個(gè)數(shù)據(jù)集，l分別取81、20、24、58、13，r統(tǒng)一取100，k分別取n/600、n/100、n/200、n/100、n/100，其中n表示時(shí)間序列長度。

實(shí)驗(yàn)選取基于子序列相似性的FLUSS 算法［15］（僅支持時(shí)間序列的分割問題）、基于斜率的pHMM算法［5］、基于均值和標(biāo)準(zhǔn)差的AutoPlait算法［7］與SEDIS 進(jìn)行性能對比。FLUSS 基于子序列相似性，需要輸入子序列長度，為保證一致性將其設(shè)置成SEDIS 使用的參考子序列的長度l。pHMM 通過εr和εc兩個(gè)參數(shù)限制使用線段擬合原始序列以及構(gòu)建線段聚類結(jié)果產(chǎn)生的誤差，在實(shí)驗(yàn)中通過調(diào)整這兩個(gè)參數(shù)來獲得最佳識別結(jié)果。AutoPlait 是全自動算法，不涉及參數(shù)設(shè)置。

3.2 算法可解釋性驗(yàn)證

在SP02 數(shù)據(jù)集上對SEDIS 所得的物理狀態(tài)進(jìn)行可解釋性驗(yàn)證。SP02 數(shù)據(jù)集由傳感器采集的人體血氧飽和度數(shù)據(jù)組成，血壓在一定程度上會對該數(shù)據(jù)產(chǎn)生影響。為便于展示，對該時(shí)間序列進(jìn)行降采樣處理，將長度縮減至350。由圖1（a）可以看出，時(shí)間序列中存在2 種不同的狀態(tài)，兩者對應(yīng)的代表性子序列的長度和波形均不一致，2 種狀態(tài)分別表示傳感器佩戴者的血壓維持正常和血壓突然驟降。對比圖1（b）的原始標(biāo)簽以及圖1（c）由SEDIS 得到的識別結(jié)果可知，SEDIS 識別出的物理狀態(tài)與真實(shí)狀態(tài)基本吻合，證明了通過子序列相似性區(qū)分狀態(tài)是可行的。pHMM 和AutoPlait的識別結(jié)果如圖1（d）和圖1（e）所示。由于FLUSS 僅支持序列分割，因此不在此進(jìn)行展示。從選擇的特征進(jìn)行分析，pHMM 基于斜率，將上升段和下降段分為2 種狀態(tài)，最終識別出3 種狀態(tài)，但無法從更宏觀的角度描述狀態(tài)，而AutoPlait基于均值和標(biāo)準(zhǔn)差，由于該案例中的2 種狀態(tài)在均值和標(biāo)準(zhǔn)差方面不具備區(qū)分性，因此AutoPlait 將整個(gè)時(shí)間序列視為同一狀態(tài)，識別效果不理想。

圖1 算法可解釋性驗(yàn)證結(jié)果Fig.1 Verification results of algorithm interpretability

3.3 算法準(zhǔn)確率分析

由于語義挖掘算法在識別出狀態(tài)的同時(shí)也監(jiān)測出不同狀態(tài)間的轉(zhuǎn)變點(diǎn)，因此本節(jié)將從序列分割和狀態(tài)識別兩個(gè)維度對算法準(zhǔn)確率進(jìn)行量化評估。

3.3.1 序列分割準(zhǔn)確率

FLUSS 僅能進(jìn)行序列分割，而其他對比算法忽略了每個(gè)分段的狀態(tài)標(biāo)識，僅考慮分割點(diǎn)的準(zhǔn)確率。本文提出一種新的分割誤差指標(biāo)sse，包括精確率指標(biāo)和召回率指標(biāo)，其中為所有預(yù)測分割點(diǎn)與其最接近的真值點(diǎn)的距離和，為所有不包含預(yù)測分割點(diǎn)的區(qū)域的長度和。將整個(gè)時(shí)間序列劃分成多個(gè)區(qū)域，區(qū)域的分界點(diǎn)由兩個(gè)相鄰真值點(diǎn)的中值決 定，越接近于0，表示分割點(diǎn)越準(zhǔn)確。

表2 給出了4 種算法在5 個(gè)數(shù)據(jù)集上的分割誤差，其中，×表示該算法未識別出任何有效分割點(diǎn)，意味著將整個(gè)時(shí)間序列視作同一狀態(tài)。由表2可以看出，SEDIS在5 個(gè)數(shù)據(jù)集上均具有優(yōu)異表現(xiàn)。FLUSS 同樣基于子序列相似性，較優(yōu)于pHMM 和AutoPlait。但由于其難以處理狀態(tài)多次出現(xiàn)的情況，因此在部分?jǐn)?shù)據(jù)集上表現(xiàn)不佳。pHMM 更適合區(qū)分斜率不同的波段而非復(fù)雜波形，因此在結(jié)果中出現(xiàn)了大量的分段碎片，導(dǎo)致召回率指標(biāo)分值較低。AutoPlait難以區(qū)分均值和標(biāo)準(zhǔn)差較為一致的狀態(tài)，僅在兩個(gè)數(shù)據(jù)集上找到有效的分割點(diǎn)。由此可見，SEDIS 具備更強(qiáng)的通用性。但是，SEDIS 未能完全命中真值點(diǎn)的原因在于：時(shí)間序列是平滑演進(jìn)的，分割點(diǎn)附近的子序列相對接近，導(dǎo)致分割點(diǎn)難以精準(zhǔn)定位，然而相比于分割點(diǎn)的誤判和漏判，準(zhǔn)確率方面的誤差是可接受的。

表2 4 種算法的分割誤差比較Table 2 Comparison of segmentation errors of four algorithms

3.3.2 狀態(tài)識別準(zhǔn)確率

狀態(tài)識別問題實(shí)際上是一個(gè)特殊形式的聚類問題，假如將時(shí)間序列中的每個(gè)時(shí)間點(diǎn)視作一個(gè)聚類對象，那么目標(biāo)就是將所有時(shí)間點(diǎn)劃分成多個(gè)不同的類簇，每個(gè)類簇反映一個(gè)物理狀態(tài)。本文引入調(diào)整蘭德系數(shù)（Adjusted Rnd Index，ARI）［25］作為狀態(tài)識別準(zhǔn)確率的衡量標(biāo)準(zhǔn)。ARI的取值范圍在-1 到1 之間。ARI越大，表明聚類結(jié)果與實(shí)際分類情況越吻合。

表3給出了3種算法的狀態(tài)準(zhǔn)確率比較結(jié)果，其中×表示該算法未在該數(shù)據(jù)集上進(jìn)行狀態(tài)識別，即將整個(gè)時(shí)間序列視作一個(gè)狀態(tài)。由表3可以看出，SEDIS在5個(gè)數(shù)據(jù)集上均達(dá)到了90%以上的準(zhǔn)確率，而pHMM 和AutoPlait 則表現(xiàn)一般，符合上文的理論分析。

表3 3 種算法的狀態(tài)識別準(zhǔn)確率比較Table 3 Comparison of state recognition accuracy of three algorithms %

3.4 算法效率分析

基于PAMAP 數(shù)據(jù)集進(jìn)行算法效率實(shí)驗(yàn)，比較不同算法在不同時(shí)間序列長度下的運(yùn)行時(shí)間，如圖2 所示。由圖2 可以看出，SEDIS 的運(yùn)行效率是近似線性的，優(yōu)于其他算法。當(dāng)時(shí)間序列長度n等于694 380時(shí)，SEDIS的運(yùn)行時(shí)間僅為112.73 s。

圖2 4 種算法的運(yùn)行時(shí)間比較Fig.2 Comparison of the running time of four algorithms

3.5 算法參數(shù)設(shè)置對狀態(tài)識別結(jié)果的影響

通過實(shí)驗(yàn)分析參考子序列長度l、參考子序列個(gè)數(shù)r以及與參考子序列最相似的子序列個(gè)數(shù)k這3 個(gè)參數(shù)在ECG 數(shù)據(jù)集上對于SEDIS 狀態(tài)識別結(jié)果的影響程度。假設(shè)將子序列長度表示為l′，實(shí)驗(yàn)中固定其他參數(shù)，將子序列長度從0.5×l′增長至4×l′。圖3（a）給出了不同子序列長度對于狀態(tài)識別準(zhǔn)確率的影響，可以看出SEDIS 對于子序列長度的依賴性較弱。圖3（b）給出了不同參考子序列個(gè)數(shù)對于狀態(tài)識別準(zhǔn)確率的影響，可以看出由于SEDIS 中基于概率的迭代模式在參考子序列有限的情況下，仍舊具有較為穩(wěn)定的識別能力。圖3（c）給出了與參考子序列最相似的子序列個(gè)數(shù)，實(shí)驗(yàn)從50 個(gè)子序列增長至400 個(gè)子序列，可以看出盡管最相似的子序列個(gè)數(shù)相比其他兩個(gè)參數(shù)對于結(jié)果造成的影響更大，但是SEDIS 在根據(jù)這個(gè)指標(biāo)篩選最相似子序列之后，還會通過基于密度的聚類算法對結(jié)果進(jìn)行再過濾，因此子序列個(gè)數(shù)的決定性作用被弱化了，使得整體準(zhǔn)確率仍保持在98%以上。

圖3 參數(shù)設(shè)置對狀態(tài)識別結(jié)果的影響Fig.3 Influence of parameter settings on state recognition results

4 結(jié)束語

針對現(xiàn)有時(shí)間序列語義挖掘算法缺乏通用性的問題，本文提出一種基于子序列相似性的時(shí)間序列語義挖掘算法。通過定義在物理狀態(tài)層面上的子序列相似性，并結(jié)合兩級聚類識別時(shí)間序列中的潛在狀態(tài)。引入基于概率的迭代模式，提高算法的識別準(zhǔn)確率和運(yùn)行效率。在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果證明了該算法的有效性和可解釋性，并且表明其具有較強(qiáng)的魯棒性。下一步將針對多維時(shí)間序列和流式數(shù)據(jù)進(jìn)行擴(kuò)展，以解決海量數(shù)據(jù)的實(shí)時(shí)分析問題，并從語義挖掘的角度出發(fā)，將所得狀態(tài)作為有監(jiān)督學(xué)習(xí)樣本，進(jìn)一步執(zhí)行時(shí)間序列的異常檢測、預(yù)測和分類等流程，實(shí)現(xiàn)數(shù)據(jù)的高效利用。