基于自編碼器和隱馬爾可夫模型的時間序列異常檢測方法

霍緯綱，王慧芳

（中國民航大學計算機科學與技術學院，天津300300）

（?通信作者電子郵箱wghuo@cauc.edu.cn）

0 引言

時間序列異常檢測是時序數據挖掘的重要研究問題之一，已被廣泛地應用于航天［1］、金融［2］、醫療［3］等領域。隱馬爾可夫模型（Hidden Markov Model，HMM）作為一種動態時間序列統計分析模型，最早在20世紀60年代末引入和研究。由于其強大的數學基礎理論和完善的算法，HMM成為語音識別［4］、經濟分析、機械工程等領域的主流技術。Rabiner［4］驗證了HMM對具有時序性信息的識別能力較強。近年來，HMM方法已被成功引入到時間序列的故障診斷［5］和異常檢測領域［1-3，6］。

基于HMM的時間序列的異常檢測方法一般主要包含兩個重要步驟：1）符號化可觀測時間序列；2）參數學習與概率估計。符號化時間序列作為時間序列表示方法之一，旨在以字符串序列表示原始時間序列。符號化時間序列不但可以達到以低維數據表示高維數據的目的，而且符合HMM算法對觀測序列的要求。目前符號化時間序列的方法主要有分段符號化線性表示法［7］和聚類符號化表示方法［8-10］。分段符號化線性表示方法是將原始時間序列分段，并以時域和頻域信息表示為符號序列。文獻［7］將HMM應用在心電圖（ElectroCardioGram，ECG）醫療數據的阻塞性睡眠呼吸暫停（Obstructive Sleep Apnea，OSA）病情檢測中，該方法選取均值、方差和偏度等信息構成符號化序列，但是在轉化的過程中需要大量的先驗知識和豐富的實驗經驗，這不滿足現實對于時間序列異常檢測的需要。聚類符號化表示方法采用聚類的方法將時間序列的連續實數值映射到有限的符號表上，使得時間序列轉化為有限符號的有序集合［11］。文獻［8］將HMM應用在飛機著陸操作數據的異常檢測中，采用K-means聚類算法將原始時間序列轉化成由K個簇標記表示的符號序列；文獻［9］將聚類HMM應用在快速存取記錄器（Quick Access Recorder，QAR）數據分析的研究中，采用二次廣度優先鄰居搜索聚類算法將原始序列轉化成由聚類的符號表示的符號序列；文獻［10］將HMM應用在多維時間序列上的異常檢測中，分別采用模糊C均值（Fuzzy C-Means，FCM）聚類和模糊積分技術將多維時間序列轉換成單維的符號序列，且提高了HMM的異常檢測能力。

符號化序列分析的結果主要由符號化算法和時間序列的相空間軌跡決定。值得注意的是，如果使用原始時間序列中的所有數據進行分析，在符號化過程之前不進行特征提取，符號序列可能過長，噪聲的干擾對計算效率會造成影響［12］。上述文獻［7，8-10］在符號化步驟之前均無特征提取過程。文獻［12］結合感知重要點（Perceptually Important Point，PIP）［13］和HMM實現對液壓泵的故障診斷，該方法尋找對原始時間序列整體運動形狀影響較大的數據點，減少了時間序列壓縮過程中的信息損失，再根據重要點在符號空間位置劃分區域實現符號化。文獻［14］采用奇異值分解代替主成分分析中的特征分解對含有高維度的流量數據包進行降維，再應用K-means方法為HMM創建有意義的觀測序列。以上兩種方法都是在符號化序列之前，對分段后的原始序列進行特征提取和數據降維，并在故障分類和入侵檢測的準確度中取得了較好的效果。但是基于感知重要點技術的符號化方法需要計算每個點對于時間序列的影響力，復雜的計算過程降低了異常檢測的效率，而基于改進主成分分析的符號化方法在特征提取時會將數據方差較小的數據信息忽略，使得模型對非線性特征提取效果較差。

自編碼網絡是Hinton在2006年提出的一種由編碼器和解碼器構成的無監督學習算法，旨在從大量無標記的數據中學習數據的有效信息，并實現對輸入數據的非線性壓縮和重構［15］。為克服目前已有HMM建模時間序列符號化過程中特征提取方法的不足，本文通過自編碼器提取時間序列片段中的非線性特征。具體方法為：通過滑動窗口對時間序列樣本進行分段，據此生成若干時間序列分段樣本集，由正常時間序列上的不同位置上分段樣本集訓練自編碼器。利用訓練后的自編碼器得到每個分段時間序列樣本的低維特征表示。低維特征表示向量集采用K-means算法進行聚類處理，從而實現時間序列樣本集的符號化。正常時間序列的符號序列集構建HMM，并通過待測樣本在生成的HMM上的輸出概率值進行異常檢測。單變量和多變量時間序列數據集上的實驗表明了文中所提方法具有較好的異常檢測效果。

1 AHMM-AD方法

本文提出的基于自編碼器和HMM的時間序列異常檢測（Autoencoder and HMM-based Anomaly Detection，AHMM-AD）方法的具體流程如圖1所示。該方法首先把樣本集劃分為帶有正常時間序列樣本的訓練集、帶有正常和異常時間序列樣本的驗證集和測試集；其次采用滑動窗口將正常時間序列樣本集進行等長有重疊分段，由相同位置的正常時間序列片段樣本集訓練自編碼器，訓練集樣本通過訓練后的自編碼器進行特征表示，并得到低維特征表示向量集；然后采用K-means聚類算法對向量集進行聚類處理，并實現對訓練集樣本的符號化；最后采用Baum-Welch算法對樣本符號化序列集進行HMM建模，得到HMM的模型參數。驗證集和測試集的樣本經過與訓練集相同的符號化處理過程得到符號化序列。驗證集的每個樣本通過訓練完成的HMM計算輸出概率，并在輸出概率的最大值和最小值之間均勻劃分1 000個值，根據F1值最大原則來確定閾值。根據測試集樣本符號化序列的輸出概率和驗證集樣本計算所得閾值對測試集進行異常檢測。

圖1 本文時間序列異常檢測方法流程Fig.1 Flowchart of the time series anomaly detection method in thispaper

1.1 基于滑動窗口的時間序列分段

時間序列的分段方法通常有兩種：序列關鍵點（間斷點和突變點）分段［12，16］和等長有重疊時間窗口分段［11，17-18］。第一種方法通過序列中的間斷點和突變點來分段描述時間序列，然而當數據在連續上升或下降的幅度較小時，序列存在的轉折點或突變點無法識別［9］，這將會影響時間序列的分段表示。為此，大部分的方法研究采用第二種方法將原始時間序列創建為固定大小的段。這樣的方法不僅能夠保證將持續時間較長的數據模式被完整地分割出來［17］，還保持了原有時間序列數據在時序上的依賴性［11］。文獻［11］采用固定滑動窗口的方法分段并分析分段中存在的形態模式特征，較好地實現時間序列局部特征的符號化。文獻［17］采用有重疊滑動窗口分段視頻數據，并建立行為識別模型。本文采用等長有重疊時間窗口分段方法的具體實現為：設包含N個多維時間序列的樣本集記為其中單個長度為T的樣本可表示為表示第n個樣本t時刻m維的向量。樣本集中每個樣本X n應用滑動窗口以窗口大小w和步長s滑動截取，樣本的劃分表示如下：

其中：X sn表示第n個樣本片段集，表示分段后第n個樣本的第i個時間序列片段，f(x)表示滑動窗口函數，d為切片后的時間序列的片段總數，d=(T-w)s+1。

1.2 基于autoencoder的時間序列符號化

自編碼器能夠在壓縮高維數據的同時保留數據中重要特征，本文采用多個自編器提取不同時間序列片段中的特征。圖2為本文的自編碼器訓練過程示意圖。

3.2.4 性傳播疾病（sexually transmitted diseases，STD） STD患者生殖道黏膜常有破損和炎癥反應，HIV靶細胞--CD4+細胞常浸潤在此，為HIV入侵提供了有利條件［19］，而有生殖道感染的HIV患者，其生殖道分泌物中的HIV病毒含量也會顯著增加［26］，從而增加HIV感染風險。有研究發現陰性配偶最近一年有生殖道異常的HIV感染風險增加3.74倍（HR=3.74，95%CI：1.05～13.33）［25］。

圖2 自編碼器訓練過程示意圖Fig.2 Schematic diagram of training process of autoencoder

第n個樣本X sn經自編碼器特征表示后得到的特征序列

1.3 本文的時間序列異常檢測算法

本文時間序列異常檢測的算法具體為：HMM是由隱藏狀態序列和觀測序列構成的雙重隨機過程，序列的每一個位置對應一個時刻的隱藏狀態和觀測狀態。HMM由G，M，π，A，B來確定，其中，G表示HMM的隱藏狀態集合；M表示時間序列符號化后有限的觀測狀態集合，且M中的觀測狀態個數由肘部方法確定；π表示初始狀態概率向量，是由各個隱藏狀態的初始概率組成；A表示狀態轉移概率矩陣，是由隱藏狀態之間的轉換概率組成；B表示輸出概率矩陣，是由隱藏狀態下輸出觀測值的概率組成。

文中將樣本集按比例劃分為訓練集Xtrain、驗證集Xval和測試集Xtest。Xtrain用于訓練HMM，目的在于對訓練集的正常時序行為建模。由1.2節描述的基于autoencoder模型的符號化方法處理Xtrain，得到訓練集的樣本符號化序列Otrain。由于在HMM的訓練數據只包含觀測序列沒有對應的隱藏狀態序列，所以HMM的訓練過程運用非監督學習算法——Baum-Whelm算法，學習HMM的參數λ=(π，A，B)。驗證集Xval用來計算本文異常檢測方法的閾值τ，測試集Xtest用來測試本文方法的異常檢測效果。Xval和Xtest同樣經符號化處理后得到Oval和Otest，并依次輸入到訓練后的HMM中，計算每個樣本的輸出概率。在驗證集樣本的輸出概率的最大值與最小值之間均勻劃分1 000個值作為異常檢測的閾值候選值，F1值最高時所取的τ值即為本文方法的閾值，F1值的計算如式（4）～（6）所示。測試集的符號化樣本序列Otest計算的輸出概率表示為Ptest={ptest1，ptest2，…，ptestn，…，ptestN}，其中ptestn表示測試集的第n個樣本的輸出概率。結合閾值τ，當ptestn＜τ時，判定當前樣本為異常樣本；否則，判定其為正常樣本。由于本文是采用正常時間序列建模，所以ptestn的值越小表示發生異常的可能性越大。

其中：TP（True Positives）表示檢測為正常的正常樣本數；FP（False Positives）表示檢測為正常的異常樣本數；FN（False Negatives）表示檢測為異常的正常樣本數；TN（True Negatives）表示檢測為異常的異常樣本數。

算法描述如下所示：

輸 出 測 試 集 樣 本 的 輸 出 概 率Ptest=｛ptest1，ptest2，…，ptestn，…，ptestN｝。

將最大F1值對應的概率值Pvaln作為文中的閾值τ；在(min(Pval)，max(Pval))范圍內均勻劃分1000個值，將每個值作為異常檢測閾值，根據式（4）、（5）、（6）分別計算Xval上的F1值；將最大F1值對應的概率值Pvaln作為文中的閾值τ；

2 實驗與分析

2.1 實驗設置

為驗證本文方法的有效性，選用了6個數據集進行實驗。數據集描述如下：

1）雅虎（Yahoo）數據集是記錄Yahoo會員的登錄狀態的單維時間序列數據集。樣本數目300，每個樣本長1420，樣本異常率為33.33%（https：//webscope.sandbox.yahoo.com/）。

2）電力需求（Power Demand）數據集是記錄一個家庭一年的電力需求的單維時間序列。實驗中將長為35000的數據集等長截為100個樣本，每個樣本長350，樣本異常率為9%（https：//www.cs.ucr.edu/～eamonn/discords/）。

3）呼吸（Respiration）數據集是記錄病人醒來時胸腔擴張頻率的單維時間序列。實驗將長為42 000數據集等長截為140個樣本，每個樣本長300，樣本異常率為7.86%（https：//www.cs.ucr.edu/～eamonn/discords/）。

4）簡易電子傳輸協議（Simple Mail Transfer Protocol，SMTP）數據集是記錄網絡流量和攻擊手段的三維時間序列。實驗將長為95 040數據集等長截為264個樣本，每個樣本長360，異常樣本占有率7.86%（https：//www.openml.org/）。

5）基于多傳感器數據融合的活動識別系統（Activity Recognition system based on Multisensor data fusion，AReM）數據集記錄了一個人七種動作的六維時間序列數據集，樣本數目78，每個樣本長480，實驗使用動作類型作為標簽，其中將走路動作的15個樣本作為異常樣本，樣本異常率為19.23%（https：//archive.ics.uci.edu/ml/datasets/）。

6）美國國家航空航天局飛行（NASA Flight）數據集是美國宇航局在多核異常檢測（Multiple Kernel Anomaly Detection，MKAD）項目中記錄B_777飛機飛行過程的五維時間序列數據集。樣本數目300，每個樣本長1000，樣本異常率為4%（https：//c3.nasa.gov/dashlink/resources/136/）。

實驗的軟件環境為：tensorflow1.10.0，Python3.6.2，Windows10 64位操作系統；硬件環境為：Intel Core i7-3770處理器，4 GB內存。

2.2 參數選取

影響本文異常檢測方法的性能主要有兩個參數：一個是時間序列分段個數d；另一個是符號化序列所需符號的個數K。下面以Yahoo數據集的實驗為例，討論上述兩個參數的選擇過程。

實驗選擇10～50長度范圍的重構序列來測試計算效率、平均重構誤差和F1值，結果如表1。從表1中可看出，當樣本序列隨著時間序列分段個數的增多，訓練時間將會變長，但時間持續較短對模型整個訓練影響較小；平均重構誤差也相差較小；F1值在序列長度為23時最高為0.63，綜合分析Yahoo數據集的重構長度可設置在20～30范圍內較為合適。

表1 時間序列不同分段個數的實驗結果對比Tab.1 Experimental results comparison of different time series segmentation number

實驗使用K-means聚類方法對經過特征表示的樣本序列進行符號化，K值由肘部方法確定。圖3為Yahoo數據集在對比實驗基于HMM異常檢測方法中符號化的肘部曲線，當K=8時，平均畸變程度變化較高，即符號個數取為8。圖4是該數據集在本文異常檢測方法中符號化的肘部曲線，由圖4可看出K值被確定為40。

圖3 肘部方法確定基于HMM異常檢測方法的K值實驗圖Fig.3 Experimental diagram of K value of HMM-based anomaly detection method determined by elbow method

圖4 肘部方法確定本文方法的K值實驗圖FIG.4 Experimental diagram of K valueof themethod in this paper determined by elbow method

按此原理，所有數據集上的時間序列分段個數d和符號化序列所需符號個數K值設置如表2所示。

2.3 實驗結果與分析

實驗中對比方法有：基于HMM的時間序列異常檢測的方法 （Hidden Markov Model-based Anomaly Detection，HMM-AD）［8］，該方法中采用聚類方法對原始時間序列聚類處理并進行符號化；基于自編碼器模型的時間序列異常檢測方法（Autoencoder-based Anomaly Detection，AE-AD）［19］，該方法通過學習重構正常的時序行為，并利用重構誤差檢測異常。采用精確率（Precision）、召回率（Recall）和F1值作為異常檢測的評判標準。實驗結果如下：

1）在Yahoo、Power demand和Respiration三個單變量時間序列上的實驗結果如表3所示。從3個數據集的實驗結果可以看出，本文提出的AHMM-AD方法均取得了較好的結果。與HMM-AD模型相比，本文方法在3個數據集的檢測中，Precision、Recall和F1值均有所改進，對比實驗結果說明僅僅在原始數據進行符號化分析，不能避免噪聲的負面干擾，但是在符號化之前的特征表示有利于符號化過程對原始時間序列的表征。然而，與AE-AD方法相比，本文將autoencoder融合于HMM的方法在3個數據集的F1值平均提高0.339，表明先采用自編碼器對樣本片段分別進行局部提取表示，再用HMM對低維的樣本片段建模的方法在時間序列異常檢測中是有效的。

表2 實驗參數設置Tab.2 Settingof experimental parameters

2）在NASA Flight、SMTP和AReM三個多變量時間序列的實驗結果如表3所示。從表中可看出，AReM數據集的檢測效果在多變量時間序列中表現最好，其原因是該數據集的異常樣本是不同于正常樣本的行為動作，異常樣本模式突出。值得注意的是，AE-AD模型在多變量時間序列的檢測效果沒有和單變量時間序列的樣本的一樣優于HMM-AD，因此，HMM-AD模型在多變量時間序列的異常檢測中有一定的優越性。而本文所提出的模型與HMM-AD模型相比，在Recall值上具有較高的檢測得分，分別為0.916，0.700和0.890，且在F1值也有明顯的提高。實驗表明了文中的AHMM-AD能在HMM-AD的基礎上能進一步提高在多變量時間序列集上異常檢測效果。

表3 單變量和多變量時間序列實驗結果Tab.3 Experimental results of univariate and multivariate time series

3 結語

針對已有基于隱馬爾可夫模型的時間序列異常檢測模型的符號化方法不能很好地表征原始時間序列的問題，本文提出了基于自編碼器和HMM的時間序列異常檢測方法。該方法利用自編碼器對時間序列片段的特征表示優化符號化方法，進而提高了HMM表達正常時間序列的建模能力。在單變量和多變量時間序列上的實驗表明了文中方法的有效性。由

于本文方法在對時間序列片段的特征表示過程中沒有考慮片段內的時序關系，下一步將采用長短時間記憶網絡學習時間序列片段的特征表示，以進一步提高文中所提方法的異常檢測效果。