胡 珉，白 雪*，徐 偉，吳秉鍵

（1.上海大學悉尼工商學院，上海 201800；2.上海大學—上海城建建筑產業(yè)化研究中心，上海 200072）

（?通信作者電子郵箱18225515145@163.com）

0 引言

多維時間序列是指具有多個維度的有序數據集，相比單維時間序列，多維時間序列的時間復雜度和空間復雜度更高、無效和干擾信息更加嚴重，同時各維度之間也存在著更為復雜的關聯(lián)情況，使得對于多維時間序列的研究難度呈幾何級數增長。

對于時間序列的數據挖掘起始于20 世紀90 年代并且發(fā)展迅速，文獻［1］認為其挖掘內容涵蓋了時間序列的相似性查詢、時序模式挖掘、時間序列分類和聚類、時間序列異常檢測等領域。

本文研究的對象是多維時間序列異常檢測，它作為數據挖掘的重要研究領域，是各行各業(yè)尤其是大型工程項目密切關注的內容。例如，在互聯(lián)網領域，需要通過監(jiān)測和分析網絡數據的實時狀態(tài)發(fā)現異常情況，及時采取措施最終保障信息安全；在大型基礎設施的施工和運維過程中，需要通過分析各類傳感器的數據信息，及時發(fā)現風險隱患，實時報警并輔助管理人員采取有效措施，減少項目經濟損失，保障人員安全等。

然而，多維時間序列異常檢測算法異常困難：一是維數升高帶來的“維數災難”；二是隨著時間增長，數據量激增帶來的“信息膨脹”。這不僅增加了算法計算量，提高時間復雜度，加重處理數據的負擔，不利于實時檢測；而且復雜的關聯(lián)性容易干擾數據的真實結構，增加數據分析的難度，導致錯誤的分析處理結果［2］。為解決以上問題，學者們采用“維數約簡”和“時間序列模式表示”兩種思路處理原始數據，在保留原始數據的基本結構情況下，去除細節(jié)干擾，從橫向和縱向兩個角度對數據集規(guī)模進行壓縮，從而提高數據分析效率和數據挖掘的準確性。

下面分別對文中的關鍵名詞進行定義。

定義1異常。

關于異常的定義，目前還沒有統(tǒng)一標準，當前認可度較高的定義：異常指的是數據集合中明顯與眾不同的數據，這些數據是由不同的機制產生的，而非隨機偏差［3］。異?？梢苑譃辄c異常、模式異常和序列異常三種形式，本文中的異常發(fā)現主要指對點異常和序列異常的發(fā)現。

定義2維數約簡。

給定D維數據集X={x1，x2，…，xN|xi∈RD}，設d維數據集Y={y1，y2，…，yN|yi∈Rd}，D＞d。若存在函數F(xi)，1 ≤i≤N使得X→Y，構成映射RD→Rd，那么就稱Y為X維數約簡后的數據集。因此，維數約簡的實質就是求函數F(xi)。

定義3時間序列模式表示。

給定含m個樣本的多維時間序列數據集X={x1，x2，…，xm|xi∈RN}，m＞1，通過相關算法將原始的多維時間序列數據集壓縮為含n(m?n，n≥1)個樣本的多維時間序列數據集Y，其中Y={y1，y2，…，yn|yi∈RN}，時間序列模式表示，可理解為時間維度上的維數約簡。

目前國內外研究多維時間序列異常檢測有兩種思路：第一種思路是將多維時間序列進行橫向分割，轉換為多個單維時間序列，利用單維時間序列領域的算法發(fā)現異常模式；第二種思路是對多維時間序列進行縱向分段，通過相關算法研究發(fā)現異常點和異常序列。從整體邏輯順序來看，首先需要對原始數據集進行預處理，然后將預處理后的數據集按照這兩種不同的方法進行異常檢測，具體如圖1所示。

圖1 多維時間序列異常檢測算法技術路線Fig.1 Technical routes of multidimensional time series anomaly detection algorithm

本文主要圍繞多維時間序列異常檢測技術路線進行闡述，通過對維數約簡、時間序列模式表示和異常發(fā)現三大熱點領域進行分析整理，總結和分析目前多維時間序列異常檢測領域的研究現狀和研究趨勢。

1 維數約簡

避免“維數災難”最有效的方法是進行維數約簡，維度約簡分為選維和降維兩種類別［4］。選維指的是從原始的高維空間中根據異常檢測的目的直接選取相關維度，文獻［5］認為主要的選維方法包括：順序選維算法、遺傳算法、基于分形的選維算法和機器學習的選維方法等。相比選維方法，降維算法是指從一個維度空間映射到另一個維度空間的過程，降維后原始時間序列維度的含義和對應數值均會發(fā)生變化。

由于降維算法是目前維數約簡理論研究的主要方向，而且應用較為廣泛，因此本文主要介紹降維算法，無特別強調，后文中維數約簡方法指的是降維算法，其主流算法可以分為線性和非線性兩種類別，如圖2所示。

1.1 研究現狀

1.1.1 線性降維的主流算法

線性降維算法是維數約簡領域最早提出的一類算法，此類算法的核心是找到各維度之間存在的線性關系，然后對重復表達的信息進行刪除，從而達到降維的目的。目前其主流的算法包括主成分分析（Principal Component Analysis，PCA）、線性判別分析（Linear Discriminant Analysis，LDA）等。

圖2 維數約簡主流算法分類Fig.2 Classification of main algorithms for dimension reduction

線性降維領域中的經典算法是PCA，該算法是一種無監(jiān)督的統(tǒng)計分析方法，其計算簡單，應用廣泛。文獻［6-9］的結果顯示對多維數據集進行PCA 降維要明顯優(yōu)于不降維得到的結果。但是文獻［10-11］將PCA 算法應用于多維時間序列異常檢測時，發(fā)現其檢測效果不是很理想，它們認為PCA 算法在降維過程中只是反映了空間相關性卻沒有考慮時間的相關性，同時該算法對異常值、參數值和校正集比較敏感。

為此，文獻［10］提出了一種基于Galerkin 的KL 擴展算法（KL Expansion，KLE）計算方法，并將其應用于流量異常檢測中，實驗結果顯示該算法能夠考慮時間的相關性，其異常檢測結果有比較顯著的改善。文獻［12］提出基于小波變換的全網絡異常檢測算法MSPCA（Multiscale Principal Component Analysis），該算法考慮了多維時間序列的時空特性，經驗證其降維結果要優(yōu)于PCA 算法和KLE 算法。文獻［13］通過對比在工業(yè)加工和化學計量領域發(fā)展更為成熟的基于PCA 的多元統(tǒng)計過程控制（Multivariate Statistical Process Control，MSPC）與傳統(tǒng)PCA 的差異，提出多元統(tǒng)計網絡監(jiān)測（Multivariate Statistical Network Monitoring，MSNM），從而將MSPC 引入到網絡應用領域，實驗結果證明，利用MSNM 可以有效避免PCA 存在的缺陷。為降低PCA 的對異常值的敏感程度，文獻［14］將穩(wěn)健主成分分析（Robust Principal Component Analysis，RPCA）應用于網絡包捕獲數據的異常檢測，實驗發(fā)現該算法調整參數較少并且不需要很多的訓練數據就能達到較好的檢測效果。

1.1.2 非線性降維主流算法

隨著數據集規(guī)模的激增，學者們發(fā)現線性降維算法已經無法描述多維數據集各維度之間復雜的非線性關系，于是開始逐步研究非線性降維算法。

最初的非線性降維算法是基于已有線性降維算法的改進算法，即基于核的非線性降維算法，比較經典的算法是核主成分分析（Kernel Principal Component Analysis，KPCA），但是這類算法的難點在于難以選擇合適的核函數。

流形學習是近年來非線性降維算法領域的熱門研究方向，2000 年《Science》刊登了兩篇流形學習算法，分別是文獻［15］提出的局部線性嵌入（Locally Linear Embedding，LLE）算法和文獻［16］提出的等距離度量方法Isomap（Isometric Method），這兩篇論文從算法層面驗證了高維非線性數據空間內確實存在非線性流行結構，標志著學術界開始對流形學習的研究。該研究認為多維數據集主要呈現的是非線性關系，利用線性降維算法很難對其進行準確的描述，比如經典的瑞士卷數據集，如圖3所示。A點和B點的實際距離并非實線所對應的線性長度，而是虛線所對應的曲線距離，使用線性降維算法明顯不符合此類數據的真實結構。

圖3 瑞士卷數據集Fig.3 Swiss volume dataset

流形學習算法的關鍵在于從高維數據集中找到潛在的低維流形結構，從而實現降維的目的，其算法主要包括Isomap、LLE、多維尺度（Multidimensional Scaling，MDS）分析等。從文獻［16-19］整理中發(fā)現目前流形學習算法主要應用于圖像識別等領域；同時在多維時間序列的應用研究也有一定的成果［20-25］。目前，應用于時間序列的主流算法有Isomap、LLE 及其改進算法。

KPCA 算法是基于PCA 的改進算法，其算法的原理是通過核函數將非線性數據轉換為線性數據，然后利用PCA 算法從而實現非線性降維，該算法原理簡單，在矩陣比較稀疏的情況下其計算復雜度不高，是非線性降維的經典算法之一。文獻［24］通過對水文時間序列的預測模型算法對比，發(fā)現“KPCA+SVM”的預測結果要明顯優(yōu)于“PCA+SVM”的結果，說明了在該類數據集中，KPCA 降維效果要優(yōu)于PCA。但文獻［26］發(fā)現KPCA 算法雖然在性能上要優(yōu)于PCA，但是在實際應用中該算法對子集劃分和核函數的選取比較敏感。文獻［27］將KPCA 和其他基于機器學習分類器的方法應用于時間序列的異常檢測，通過實驗結果發(fā)現KPCA 的檢測結果要優(yōu)于獨立成分分析（Independent Component Analysis，ICA）、PCA等傳統(tǒng)的方法。文獻［28］提出基于部分核主成分分析（Partial Kernel Principal Component Analysis，PKPCA）算法研究故障檢測與隔離問題，然后應用于工業(yè)燃氣輪機傳感器實驗數據中，結果顯示該算法能夠有效地檢測和隔離故障。文獻［29］將KPCA 應用于無人機傳感器數據異常檢測領域，實驗結果發(fā)現，該算法的監(jiān)測效果良好。

Isomap 算法是一種非迭代的全局優(yōu)化算法，其核心思想是將MDS 算法中的歐氏距離轉換為測地距離。文獻［16］將該算法應用在圖像識別領域，實驗結果表明該算法的降維結果要優(yōu)于PCA 和MDS。但是，傳統(tǒng)的Isomap 算法計算復雜度很高，拓撲結構不夠穩(wěn)定，對于低維結構是非凸子集的高維數據集有效性不強［30］。為了降低算法的復雜度，文獻［31］提出地標-等距離度量方法L-Isomap（Landmark Isometric Method），該算法首先利用MDS 隨機選取若干地標映射到低維空間，之后通過距離計算確定非地標點在低維空間的相對位置，該算法能夠大大提高計算效率但是其降維結果對地表點十分敏感。為此，文獻［30］提出了兩種自適應的地標點選取機制，分別基于貪婪策略和圖論中的圖頂點染色思想，經實驗表明這兩種機制均能起到比較理想的降維結果。文獻［25］認為基于全局的降維算法（例如：PCA、Isomap 等）沒有充分考慮多維數據集的時間相關性，因此提出時空等值線圖STIsomap（Spatio-Temporal extension to Isometric method）改變局部鄰域圖中的原始權重，以強調時間相關點之間的相似性，作者將ST-Isomap算法應用于人體運動和機器人遙控操作數據，實驗結果證明了該算法的有效性。文獻［32］結合基因序列自身的特點，提出了基于Isomap 的一種變種即雙有界樹連接等值映射方法（double-bounded tree connected Isometric method，dbt-Isomap）［32］，在對基因時間序列進行維數約簡的實驗中結果良好。文獻［33］提出針對噪聲時間序列數據的Isomap 樣本外擴展方法，實驗結果表明，與其他時間感知嵌入算法相比，提出的樣本外擴展方法在存在各種噪聲和偽影的情況下，能夠提供更健壯、更準確的有序圖像數據嵌入。文獻［21］將Isomap 算法應用到股票的多維時間序列中，實驗結果驗證了Isomap算法的合理性和可行性。

LLE［15］假設數據在較小的局部范圍內是線性的，因此在局部范圍內采用歐氏距離代替測地距離，通過保證局部最優(yōu)來實現降維，因此該算法相較于Isomap 能夠有效地降低計算量。文獻［22］將LLE 算法應用到金融多維時間序列的聚類中，實驗結果表明利用LLE 算法進行降維得到的結果要優(yōu)于使用PCA 得到的效果，但是該算法較難確定嵌入維數和近鄰個數的參數。文獻［23］將LLE 算法進行改進，提出基于概率的有監(jiān)督局部線性嵌入（Supervised Locally Linear Embedding based on Probability，PSLLE）和基于概率的快速監(jiān)督局部線性嵌入（Quick Supervised Locally Linear Embedding based on Probability，PQSLLE），并應用于煤礦瓦斯?jié)舛葧r間序列異常監(jiān)測數據，取得較好的效果。文獻［34］為提高LLE 算法的準確度，提出了帶監(jiān)督的LLE（Supervised LLE，SLLE）算法并應用傳感器的故障識別中，實驗結果發(fā)現利用SLLE算法的降維效果要明顯優(yōu)于LLE、PCA 和MDS 算法。文獻［35］認為LLE算法只是對簡單的數據結構降維比較有效，而在噪聲、大曲率和稀疏采樣條件下，它并不能準確地處理鄰域的選擇。因此，作者提出了一種改進的加權局部線性嵌入算法（improved Weighted Local Linear Embedding Algorithm，WLE-LLE），該算法利用拉普拉斯特征映射重構降維目標函數，實現結果發(fā)現其能夠有效地表示非線性數據的流形結構，分類識別率要比LLE 算法提高2%～8%。文獻［36］將LLE 算法應用于非線性、非平穩(wěn)的腦電圖數據中，通過提取經離散小波變換得到的逼近分量的非線性特征，并結合神經網絡進行分類，實驗結果顯示該方法聚類分布明顯、分類效果好而且穩(wěn)定性強，證明了腦電信號處理中流形學習的可行性。

1.2 研究趨勢

隨著多維時間序列數據規(guī)模的激增，傳統(tǒng)的線性降維算法已經很難在準確、完整地保留其數據特征的前提下實現維數約簡，非線性降維算法尤其是流形學習將成為該領域未來重要的研究方向。

根據非線性降維算法已有的理論成果，本文將該領域的研究趨勢總結為以下幾個方面：

1）將已有理論成果與實際應用場景相結合，進一步確定算法的特點和適用范圍。目前文中涉及的諸多理論算法都只是在特定的實驗數據集或者人工數據集上進行測試，算法在解決具有實際背景的多維時間序列時的可行性還需要進一步的分析和驗證，這是將理論成果轉換為實際應用的重要環(huán)節(jié)。

2）算法優(yōu)化。整理發(fā)現，目前在該領域算法的缺陷主要表現在：時間相關性研究不夠深入、參數設置較多、計算復雜度較高、魯棒性不強等方面，在之后的算法研究中，可以從以上的一個或多個方面對算法進行優(yōu)化。

3）結合機器學習或深度學習實現維數約簡［37］。這些算法具有自學習能力，理論上非常適合于對海量時間序列的處理，因此可以將此類算法引入該領域解決時間序列的降維問題。

2 時間序列模式表示

時間序列模式表示是從時間角度對原始數據進行抽象和概括的特征表示方法，是對時間序列的重新描述。該方法能夠在保證原始數據基本形態(tài)和信息的基礎上實現數據壓縮。

目前在該領域的理論研究中，針對單維時間序列異常檢測的研究成果相對成熟，因此許多文獻會將多維時間序列轉換為多個單維時間序列，利用單維時間序列研究成果解決多維時間序列異常檢測問題。該領域的算法根據文獻［38］可以分為精確表示和近似表示，如圖4所示。

圖4 時間序列模式表示主流算法分類Fig.4 Mainstream algorithms of pattern representation of time series

2.1 研究現狀

在時間序列壓縮方式中，主流的方法有：抽樣表示法、分段線性表示法（Piecewise Linear Representation，PLR）、符號化表示法（Symbolic Aggregate Approximation，SAX）、離散傅里葉變換（Discrete Fourier Transform，DFT）等，下面分別對這幾類主流算法的研究現狀進行分析和介紹。

2.1.1 抽樣表示法

抽樣表示法［39］是時間序列最簡單的表示方法，該算法的原理簡單，即按比例抽取樣本點，同時易于實現，適用于實際工程中的多維時間序列的實時壓縮，但是其采樣步長很難確定，當該參數取值過大時，會使樣本變形導致表示不準確。

針對該問題，Keogh 等［40］提出分段聚合近似（Piecewise Aggregate Approximation，PAA），該方法在抽樣表示方法的基礎上使用平均值來表示每個分段對應的數據點集，減小了因抽樣導致的時序數據的變形程度，但是其準確度以及步長的確定仍然是需要進一步完善的問題。為防止該算法丟失時間序列的重要模式，同時保證其存在良好的下界約束，Hung等［41］提出了分段線性聚合近似（Piecewise Linear Aggregate Approximation，PLAA）算法，該算法結合均值和斜率兩個方面，能夠彌補PAA 算法的不足。文獻［42］針對PAA 步長問題提出基于混合層次聚類的PAA（hybrid Hierarchical Clustering-PAA，hybrid HC-PAA）算法，在基于振動特征的工業(yè)燃氣輪機故障檢測和基于超聲回波信號的生物特征識別兩個數據集的應用中具有良好的表現。為了解決PAA 算法數據特征丟失的問題，文獻［43］提出分段聚合模式表示（Piecewise Aggregate Pattern Representations，PAPR），并將其應用于心電圖數據和視頻監(jiān)控數據的異常檢測，實驗結果顯示，與基于PAA 的方法相比，基于該方法的異常檢測算法具有更高的魯棒性和更精確的異常檢測能力。文獻［44］針對PAA 存在的問題給出了兩種解決方式：第一種方法是根據平均值將每一段劃分為兩部分，并分別使用數值平均值來表示趨勢，該方法已被證明滿足下界約束，從而保證不會產生漏報；第二種方法使用二進制字符串來記錄時間序列的趨勢變化，實驗表明該方法要優(yōu)于之前提出的PAA算法。

2.1.2 分段線性表示法

Pavlidis 等［45］提出PLR，該算法是指采用首尾相鄰的一系列線段來近似表示時間序列，其難點在于如何進行樣本分段，確定分段數目和分段點。

針對此問題，文獻［46］提出基于PAA 的PLR 算法，將時間序列等寬分割，然后用均值代替該子時間段。該方法簡單直觀，能夠提高索引的效率，可以應用于多維時間序列壓縮。文獻［47］提出了基于重要點的分段方法，文中通過選取局部極值點來實現數據的壓縮。文獻［48］提出基于特征點的PLR算法，將影響時間序列形態(tài)的最大的點作為特征點進行線性分段，該算法雖然在選擇特征點的過程中對噪聲的處理結果較好，但無法及時捕獲單調序列中的變化轉折點，不能有效發(fā)現短暫變化的尖峰子序列。之后，文獻［1］提出基于時態(tài)邊緣算子的分段線性（piecewise linear representation based on Temporal Edge Operators，TEO）表示方法，算法考慮到時間序列的非平穩(wěn)性和相關性特點，選擇局部范圍內的邊緣幅度極值點作為邊緣點進行時間子序列的劃分，算法具有較強適應性，能夠應用于不同的數據特征環(huán)境。文獻［49］提出一種基于插值邊緣算子的時間序列分段線性表示（piecewise linear representation based on Interpolation Edge Operators，IEO）方法，可以有效壓縮數據，并且對噪聲和數據是否陡峭并不敏感，在異常檢測中能夠具有更好的表現效果。文獻［50］認為大部分的PLR 算法具有動態(tài)增量實時更新的優(yōu)點，于是提出基于信息熵的PLR_IE（Piecewise Linear Representation based on Information Entropy）算法，利用序列中熵的大小比例來確定序列中重要點的數量分布情況，從而線性擬合出初始曲線，實驗結果表明，與現有的距離計算分析查找特征點相比，該算法能夠更準確地提取序列重要特征，保留了序列整體性。文獻［51］為解決時間序列的分割問題，提出基于壓縮比的分段線性表示法。首先找出時間序列中的所有極值點，然后根據壓縮比例選取符合要求的極值點作為序列分割點，該算法原理簡單，同時不需要設置復雜的閾值參數，但是該算法的魯棒性不強，存在擬合誤差，只適用于單維時間序列的離線分割。為減小PLR 算法的擬合誤差，文獻［52］提出基于重要點的線性分段表示法（Piecewise Linear Representation based on Important Data Point，PLR-IDP），該重要點通過計算單點擬合誤差和分段擬合誤差來確定，結果顯示該算法能夠在保留數據主要特征的情況下，實現較低的單點、局部和全局擬合誤差。為減少參數設置，提高算法的擬合效果和魯棒性，文獻［53］提出基于時間序列重要點的分段（Piecewise Linear Representation based on the Important Point of the Time Series，PLR-TSIP）算法，該算法從整體擬合誤差角度確定每段的優(yōu)先級，然后在段內按照最大最小值點進行進一步劃分，實驗結果表明，該算法的擬合度較高，但是其計算效率還需要進一步提高。

2.1.3 符號化表示方法

時間序列的符號化表示方法中最常用的就是文獻［54］提出的SAX 算法，該算法是基于PAA 的擴展方法，被認為是該領域最簡單同時穩(wěn)健性最強的處理單維時間序列的算法［55］。由于目前字符串領域的匹配研究比較成熟，因此許多研究者會將時間序列離散化，然后映射到字符空間，利用字符串技術來對時間序列進行研究，但是該方法基于對時間序列的均值描述，其結果比較粗糙容易導致數據失真，同時難以描述時間序列的趨勢特征。

Wang等［56］結合SAX、卷積神經網絡和集成學習算法提出Pooling SAX-BoP （Pooling SAX Algorithms with BoP Representations），并應用于醫(yī)學領域并取得了較好的結果，證明了SAX 算法在該領域的可行性。為解決數據失真問題，文獻［57］結合SAX 距離與加權趨勢距離提出SAX-TD（SAX with the weighted Trend Distance）從而實現了對時間序列更加準確的分類。文獻［58］提出基于標準差的SAX（SAX based on Standard Deviation，SAX-SD）改進算法，通過在UCR 數據集的驗證，發(fā)現該算法與SAX、SAX-TD 算法相比具有更高的壓縮比率和更高的效率，同時能夠滿足下界約束和緊束縛距離，該算法在異常檢測中的應用有待進一步研究。文獻［59］提出基于滑動窗口的重要轉折點的SAX 改進算法FD-SAX（Featurebased Dividing SAX），該算法能夠實現在線流式時間序列符號表示，通過各種類型的實驗數據對比證明了該算法的優(yōu)越性。為解決SAX 算法難以描述時間序列趨勢特征的問題，文獻［60］提出基于趨勢的改進SAX 方法（Trend-based SAX，TSAX），通過UCR 時間序列數據集驗證了該算法的有效性，但是該算法難以更加精確地刻畫趨勢的程度，另外其距離值的測量方法不具有普遍性，同時其參數問題也沒有得到有效的解決。文獻［61］在SAX 方法的基礎上進行了改進，提出時間序列的多維符號化表示方法mSAX（multidimensional SAX），該改進算法是從多個維度來描述子序列片段并將其轉化特征向量，然后利用離散化方法對各子序列特征向量的各個維度進行符號化生成多維符號向量，結果顯示該方法對時間序列的描述和表示更加精準細致。

2.1.4 離散傅里葉變換法

DFT［62］基本思想是在全局范圍內將時間序列分解為有限個數的正弦函數和余弦函數的加權和。DFT能夠用極少的傅里葉系數來表示時間序列，能夠大幅度節(jié)省存儲空間并且能夠保持歐幾里得距離不變性，但是它很難刻畫時間序列的局部特征。為了克服該缺點，文獻［63］提出了短時傅里葉變換（Short-Time Fourier Transform，STFT），即在信號上加一段滑動窗口對信號進行分段取樣，將其化為若干個局部平穩(wěn)信號，但是STFT 的問題是很難確定滑動窗口的大小。離散小波變換（Discrete Wavelet Transform，DWT）可以解決上述問題，它具有多分辨率解析的特點同時包含時域信息和頻域信息，能更加有效地提取和分析局部信號，在原始信息的除噪過程中也經常使用該算法［64］，在時間序列模式領域已逐漸代替了DFT 和STFT。文獻［65］采用Harr 小波變換，實驗結果表明采用離散小波變換在相似性查詢時結果要優(yōu)于DFT 表示方法。文獻［66］提出將遺傳算法、聚類算法和DWT 進行結合，即利用K-means聚類將子序列分組，DWT保證子序列的相同長度，然后利用遺傳算法發(fā)現分割點，實驗結果表明，該方法能在時間序列中找到合適的分割模式。文獻［67］提出分別利用LLE和DWT 算法提取運動圖像腦電圖的特征，然后結合神經網絡算法實現更加穩(wěn)定和有效的分類效果。文獻［68］運用DWT算法提取擾動特征，同時提出基于人工蜂群的概率網絡（Probabilistic Neural Network based Artificial Bee Colony，PNNABC）算法優(yōu)化特征選擇，從而實現對電能質量擾動的有效分類。

2.2 研究趨勢

目前時間序列模式表示領域中對于單維時間序列的算法研究已經相對成熟，因此，對于單維時間序列，未來的研究趨勢主要側重于對已有算法的優(yōu)化，主要包含以下幾個方面：

1）實時性在線擴展能力。目前已有算法大部分只適于對離線數據進行時間維度的數據壓縮，對于動態(tài)數據的處理主要基于滑動窗口的設置。但是隨著數據量的增加和實際應用中對于實時異常檢測需求的提高，越來越多的時間序列需要滿足在線情況下、有限時間內完成對數據的實時檢測，因此，對于該算法的實時性研究具有很大的經濟價值。

2）可擴展性。目前已有的算法大部分需要設置較多的參數和閾值，由于不同數據集的特征迥異，對參數的調整和訓練將耗費大量的時間，導致算法的可擴展性不強。因此，在今后研究中可以對參數設置進行優(yōu)化和改進。

相對于單維時間序列模式表示，目前國內外對于多維時間序列模式表示方法理論成果較少［69］，處在初步研究階段。但是隨著當代各行各業(yè)尤其大型基礎設施對全生命周期海量數據實時處理要求的提高，對于該領域的理論研究需求愈加迫切。通過分析發(fā)現，目前研究瓶頸在于難以確定多維時間序列的分段規(guī)則。因此，在該領域的研究可以從以下幾個方向展開：

1）基于已有的單維時間序列模式表示方法提出改進算法使其能夠適用于多維時間序列。

2）研究多維時間序列模式表示算法，直接從多維時間序列的角度解決模式表示問題。同時，在算法的研究中要著重考慮算法的實時性、計算復雜度、可擴展性等一個或者多個方面，從而提高算法在實際應用中的可行性。

3 異常模式發(fā)現

異常模式發(fā)現是多維時間序列異常檢測最重要的研究領域之一，目前在該領域的主流算法主要分為以下五類，如圖5所示，本章將對這五類算法進行分析整理，并說明該領域的研究趨勢。

圖5 異常模式發(fā)現的主流算法Fig.5 Mainstream algorithm of anomaly pattern detection

3.1 基于預測的方法

基于預測的方法是通過預測值與實際值的誤差值大小來判斷異常位置，代表算法是差分整合移動平均自回歸模型（AutoRegressive Integrated Moving Average model，ARIMA）［70］，其適用于具有明顯季節(jié)性或周期性的單維時間序列的短期異常檢測。

國內最初將ARIMA 用于氣象數據和傳染病數據［71-73］，由于這些時間序列相對簡單，周期性很強并且具有明顯的規(guī)律，因此其預測值和實際值的誤差比較小，在具體的實驗數據中表現良好。

目前基于預測的方法逐漸從傳統(tǒng)的以ARIMA 模型為核心的線性預測算法發(fā)展到“ARIMA+”的組合預測算法。比如：文獻［74］提出ARIMA-LSSVM 的混合預測算法，分別對單維犯罪時間序列進行線性和非線性部分建模，實現對精準的犯罪預測，與傳統(tǒng)的ARIMA-BP 相比，該混合算法的準確性和穩(wěn)定性更高，但是此類算法參數設置較多同時其計算復雜度也偏高。文獻［75］結合ARIMA、DWT和功能鏈接人工神經網絡（Functional Link Artificial Neural Network，FLANN）對單維金融領域數據進行預測，通過DWT 將原始時間序列分解為線性和非線性部分，然后分別利用ARIMA 和FLANN 算法實現線性和非線性預測，實驗結果證明了該算法的有效性。文獻［76］將ARIMA 結合SVM 算法應用于單維網絡流量的趨勢預測，該算法需要對原始數據進行長期觀測提取相關特征，然后對各類特征分別建立ARIMA 模型，將實際值與預測值的差值作為偏離度向量，通過不斷更新偏離度并結合支持向量機（Support Vector Machine，SVM）算法實現對該網絡流量的實時在線預測，實驗驗證該算法能夠有效地預測異常情況。文獻［77］提出改進的ARIMA算法M-ARIMA（Modified ARIMA），將該算法應用于由光纖力熱參數儀中的壓力傳感器實時采集的數據集中，經驗證該算法具有較高檢測率的同時能夠自動、實時地實現異常預警。文獻［78］提出結合ARIMA、DWT 和RNN 實現對計算機網絡流量的預測，其原理與文獻［75］基本一致，作者認為該混合方法易于實現并且計算量相對較小，能夠顯著提高網絡服務質量、減少成本。文獻［79］基于ARIMABP 的混合算法預測氨氣的濃度，通過實驗對比，發(fā)現該算法在該領域的預測結果要優(yōu)于BP神經網絡或ARIMA模型。

3.2 基于頻率的方法

該方法的代表算法是隱馬爾可夫模型（Hidden Markov Model，HMM）［80］，該模型是關于時序的概率模型，異常檢測在HMM 中可以轉換為“在給定觀測序列O(t)，t=1，2，…，T和模型λ=(A，B，π)的前提下，求取P(O|λ)”的問題，該算法解決的是單維時間序列問題，其最顯著的特點是要求其觀測值是有限個數的離散值，能夠實現實時檢測。

圍繞HMM 有許多實際的應用，文獻［81］將HMM 應用到時間序列異常檢測中，實驗結果驗證了該算法的有效性，但是傳統(tǒng)的HMM算法在建模過程中時間復雜度過高、樣本需求量大并且對狀態(tài)參數比較敏感。

針對樣本需求量大的問題，文獻［82］提出基于半監(jiān)督學習的行為建模與異常檢測方法，即通過結合DTW、譜聚類和HMM，建立正常行為和異常行為的模型，從而得到異常行為判斷模型，對人的運動行為數據進行分析，實驗證明該算法適用于多類樣本的情況，能夠在較少樣本的情況下避免HMM欠學習的問題，具有較高的可靠性，但是該算法時間復雜度仍然較高，不能檢測到未知異常，同時對于小樣本類型的正常行為檢測效果也需要進一步完善。文獻［83］提出了一種增量的HMM 學習算法，將訓練集切割為若干個規(guī)模較小的子集分別進行訓練，最后將訓練得到的子模型合并為最終的模型，實驗顯示該方法能夠大幅度減少計算時間。孫美鳳等［84］提出了基于特征模式的馬爾可夫鏈異常檢測模型，該算法能夠避免重復性檢測，實驗顯示，該算法簡單、實時性強、檢測率高、誤報率低，但是其對參數設置比較敏感，能夠直接影響算法的檢測效果。

針對時間復雜度過高同時狀態(tài)參數敏感的問題，王瓊等［85］提出改進的隱馬爾可夫模型（Improved HMM，IHMM），為降低算法對閾值參數的敏感性，該算法將訓練數據集中發(fā)生頻率極低的特征序列刪除，利用發(fā)生頻率較高的特征序列建立正常行為輪廓，經實驗對比發(fā)現，該算法在訓練時間、適應性等方面都明顯優(yōu)于HMM模型。

近幾年HMM算法開始和機器學習結合來改進預測效果，比如文獻［86］提出的將HMM 算法結合自組織神經網絡等。同時，該算法已逐步運用到其他領域，比如信用卡欺詐檢測［87］、行為識別［88-89］、器械故障檢測［90］等。

3.3 基于免疫的算法

負選擇算法（Negative Selection Algorithm，NSA）［91］基于生物學中免疫系統(tǒng)的自我-非我識別原理，該算法的基本原理是通過正樣本獲得能夠盡可能覆蓋非我空間的檢測器集，然后利用檢測器對系統(tǒng)的運行狀態(tài)進行甄別。負選擇算法基于大量的正樣本進行學習，不需要先驗知識，非常適合于異常樣本匱乏或者未知故障的檢測問題，但是該算法中檢測器數目和檢測器對非我空間的覆蓋兩者之間是相互矛盾的，這也成為目前眾多學者研究的熱點方向。

針對檢測器數目和檢測器對非我空間的覆蓋之間的矛盾，文獻［92］提出基于模擬退火算法的負選擇算法，以此增加檢測器對非我空間的覆蓋區(qū)域。文獻［93］提出基于歐氏距離的實數域負向選擇算法，并應用于周期性時間序列和轉子振動時間序列，結果表明，該算法可以有效地檢測出異常值。文獻［94］提出采用粒子群算法的優(yōu)化檢測器的分布來提高檢測效率，作者將該算法應用于正弦時間序列和軸承振動信號序列驗證了該算法的有效性和實用性。文獻［95］提出改進的進步訓練負選擇算法（Further training NSA，FtNSA），通過生成覆蓋自區(qū)域的自檢測器引入到訓練階段以減小“漏洞”，作者將該算法應用于多個實驗數據集，結果顯示其在整體上要明顯優(yōu)于NSA，同時表示會將優(yōu)化生成的檢測器分布和減少檢測器重疊作為今后的研究方向。文獻［96］提出基于網格文件的特征空間負選擇算法（Real NSA based on the Grid File of feature space，GF-RNSA），將特征空間劃分為若干網格單元，然后在每個網格單元中分別生成檢測器。由于候選檢測器只需要與位于同一細胞內的自身抗原進行比較，而不需要與整個自身集進行比較，因此檢測器訓練結果更加有效。文獻［97］提出基于粒子群優(yōu)化的負選擇算法（NSA based on Particle Swarm Optimization，NSA-PSO），即利用粒子群優(yōu)化算法改進隨機檢測器的生成，將該改進算法應用于垃圾郵件檢測網絡，結果表明該算法的結果優(yōu)于傳統(tǒng)的NSA算法。

文獻［98］認為上述算法雖然都能夠在一定程度上減少“漏洞”，但是幾乎沒有考慮到檢測器在小樣本情況下的在線自適應能力，因此作者提出在小樣本情況下的在線自適應學習的邊界固定負選擇算法（Boundary-fixed Negative Selection Algorithm with Online Adaptive Learning，OALFB-NSA），實驗結果表明，該方法能夠適應測試階段自身空間的實時變化，具有較高的檢測率和較低的誤報率。

3.4 基于聚類的算法

聚類是一種非監(jiān)督的算法，符合實際工程數據標簽不完整、不準確的情況，因此在異常檢測領域有比較廣泛的應用，目前已有的聚類算法主要包括K-means、基于密度的聚類方法DBSCAN（Density-Based Spatial Clustering of Applications with Noise）、高斯混合模型（Gaussian Mixture Model，GMM）等。文獻整理發(fā)現，時間序列的異常發(fā)現主要結合的算法是K-means［99］，該算法是一種基于劃分的聚類方法，該算法簡單高效，適用于對大規(guī)模數據集的處理。

但是傳統(tǒng)的K-means 算法的聚類結果易受初始聚類中心和離群值的影響。為解決該問題，文獻［100］提出最近最遠K均值算法（minimum maximumK-means，minmaxK-means），該算法能夠保證各距離中心保持一定的間隔，但是不能消除離群點對算法的影響；文獻［101］提出通過計算各個數據點的密集性，利用密集性最大的前K點作為初始聚類中心的思想，但單純利用密集性選取的初始中心并不能保證均勻分布，不太符合聚類的真實位置和本質屬性。之后，文獻［102］提出了改進的K-means 算法，該算法結合前文改進算法的特點，首先剔除離群點區(qū)域，然后在數據緊密區(qū)，對算法的初始聚類中心按照最近最遠距離的原理選擇初始聚類中心。實驗證明，改進后的K-means 算法在異常檢測率、誤報率等方面均優(yōu)于傳統(tǒng)的K-means 算法和minmaxK-means 算法。文獻［103］提出一種基于高斯函數加權距離測度的改進的粗糙K均值算法（RoughK-means，RKM），與傳統(tǒng)算法相比，該算法能夠在同樣的時間復雜度下，為數據集提供更為合理的上下界，其聚類效果更加精確。另外，文獻［104］將K-means 算法結合計算多維時間子序列之間距離的擴展范式距離（the Distance of Extended frobenius norm，DEros），將聚類從發(fā)現異常點擴展到能夠發(fā)現多維時間子序列，但是該算法的復雜度較高，同時不能進行在線異常檢測。文獻［105］將K-means 算法和基于距離的算法結合，提出兩階段的多維時間序列異常檢測算法，首先利用K-means 進行初始聚類，并用一個啟發(fā)式規(guī)則估計每個簇包含異常點的可能性，按從大到小的可能性進行排序；然后在聚類基礎上，利用循環(huán)嵌套算法實現異常檢測。該過程增加了兩個剪枝規(guī)則，從而降低了時間復雜度，但是該方法對由不同密度子集混合而成的時間序列數據集的檢測效果不好［106］。

3.5 基于分類的算法

分類算法是有監(jiān)督的方法，例如支持向量機（SVM）、K近鄰（K-Nearest Neighbor，KNN）算法、決策樹算法。文獻整理發(fā)現，目前分類算法中用于解決時間序列異常檢測問題的主流算法是SVM算法和其改進算法1-SVM。

SVM 的優(yōu)點是泛化能力強、沒有局部極小點和解具有稀疏表示，因此被經常應用于入侵檢測系統(tǒng)的異常檢測中［107］。另外，SVM 在異常檢測領域結合其他算法能夠得到很好的檢測效果，文獻［76］將ARIMA結合SVM算法實現多維時間序列的在線異常檢測，結果顯示該算法的有效性。文獻［108］提出改進的SVM 算法，結合神經網絡解決植物病害檢測問題。文獻［109］提出局部增量算法LISVM（Local Incremental SVM），結合徑向基函數改進SVM，能夠實現在線分類，在實驗驗證中該算法具有良好的表現，同時其計算復雜度不高，可以從擴大實驗數據規(guī)模和調整參數兩個方面進一步優(yōu)化該算法。

文獻［110］認為異常值檢測實際上可視為特殊的一類分類問題，即1-SVM，其將1-SVM 從回歸和相空間重構分類兩個角度對時間序列進行異常檢測，分別提出根據求最小超球體的二次規(guī)劃方法和基于線性規(guī)劃的優(yōu)化方法，實驗結果表明以上兩種方式均能較好地辨別出時間序列中的異常值。文獻［111］PCA 結合1-SVM 的算法，首先利用PCA 進行維數約簡，利用滑動窗口對降維后的數據集進行區(qū)域劃分，然后對時間窗內的數據進行特征提取并轉換為無序變量，最后將其代入1-SVM 進行訓練，實現對待測數據的異常檢測，該算法簡單，在實際的工程應用中起到較好的效果。

3.6 研究趨勢

異常發(fā)現主要分為兩種思路：第一種思路是將預處理后的多維時間序列轉換為多個單維時間序列分別進行分析，同時結合聚類算法、分類算法實現對多維時間序列的異常檢測；第二種思路是直接將多維時間序列切割成若干個多維時間子序列后通過聚類算法等方式進行異常發(fā)現。

目前該領域的實現方式主要基于第一種思路，該思路的理論研究相對成熟，但是對應算法基本不能滿足實時異常檢測，同時其對數據預處理的方式比較敏感，另外隨著數據集規(guī)模的增長，該算法時間復雜度會大幅增加，不能滿足今后的數據發(fā)展需求。

第二種思路目前處在初步研究階段，但是由于該方法能夠在同一時刻保留各個維度之間的相互關系，并且不需要通過訓練多個模型來實現異常檢測，能夠滿足大規(guī)模數據類型的需求，因此對于該算法的研究對于大規(guī)模數據更具有價值。從文獻整理來看，目前該領域存在的研究難點在于難以衡量多維時間子序列之間的相似程度。總結該思路算法的研究重點主要為以下幾個方面：

1）多維時間子序列相似性度量算法研究。據了解，目前該領域相對常用的算法是基于擴展范式距離的度量方法，但是該方法不滿足實時異常檢測，仍需要學者進行算法改進或者提出新的算法。

2）基于單維時間序列異常發(fā)現的算法改進。目前對于單維時間序列進行分析的算法主要是基于預測的算法和基于概率的算法，這兩種方法目前已經比較成熟，可以通過相應的算法改進來研究多維時間序列的問題。

3）改進傳統(tǒng)的聚類和分類算法，使其滿足時間特性。傳統(tǒng)的聚類和分類算法的對象是無序變量，但是時間序列是有序數據集。為避免丟失時間序列的時間維度信息，在研究時間序列問題時，需要對傳統(tǒng)的聚類和分類算法進行相應的算法改進。

4 結語

隨著信息技術和硬件制造水平的提高，各類數據均能夠通過前端設備實時采集，形成規(guī)模愈加龐大的海量時間序列，為多維時間序列異常檢測的發(fā)展提供了契機和挑戰(zhàn)。

近年來，國內外在該領域的理論研究已有一定的成果。通過文獻整理，本文歸納為兩種主流思路：第一種是將原始多維時間序列經過數據預處理之后轉換為單維的時間序列，然后利用單維時間序列異常檢測的相關理論發(fā)現異常；第二種是通過研究新的算法或者改進算法直接對預處理后的多維時間子序列進行異常檢測。

目前對于第一種思路的理論研究相對成熟，但是該思路比較適合對于小型數據的異常檢測。第二種思路目前雖處在初步研究階段，但是該思路理論上能夠滿足更大規(guī)模時間序列的異常檢測，因此本文認為今后的發(fā)展研究方向將側重于第二種思路的理論研究。

下面從“維數約簡”“時間序列模式表示”和“異常模式發(fā)現”三個方面對第二種思路的重點研究內容進行總結。

1）維數約簡：算法在時間相關性方面的優(yōu)化研究。維數約簡過程中如何保留原始數據的時間規(guī)律是目前已有算法難以解決的問題，雖然學者已有初步成果，但是目前在該領域仍然沒有普遍認可的方法。

2）時間序列模式表示：多維時間序列模式表示的方法研究。該方法的難點主要在兩個方面：第一，難以確定統(tǒng)一的規(guī)則，使其能夠在較高數據壓縮率的情況下，對各個維度具有比較精確的表示；第二，該方法是否能夠適用于實時更新的多維時間序列。

3）異常模式發(fā)現：該領域主要研究方向可以分為兩個部分：第一，多維時間子序列相似性度量算法研究；第二，聚類和分類算法在時間相關性方面的優(yōu)化研究。目前已有許多經典的單維時間序列相似性度量方法，例如歐氏距離、動態(tài)時間扭曲、垂直距離等，但是對于多維時間序列的相似性度量方法還處在初步研究階段，目前還沒有成熟的算法理論。另外，傳統(tǒng)的聚類、分類算法只是針對無序變量，如直接應用于時間序列會丟失原始數據信息，降低異常檢測的準確性，因此有必要聚類和分類算法進行改進和優(yōu)化。

除此之外，在對多維時間序列異常檢測的算法研究中，要注意以下問題：第一，要盡量降低算法的復雜度。過度復雜的算法不僅要消耗較多的時間和存儲代價，同時也不利于參數的調整，難以達到預期的效果。第二，算法要注重對實時檢測的研究，在實際的應用中，多維時間序列大部分均需要進行實時異常檢測，因此要求算法能夠在較短的時間內有效判斷出最新數據的狀態(tài)，這對算法的實時性提出了更高的要求。第三，注重算法的魯棒性和泛化能力，保證算法能夠在不同的實際工程背景下盡量得到穩(wěn)定和精確的結果。

總的來說，多維時間序列異常檢測領域的理論研究并不成熟，建議今后的理論研究要更多地結合實際應用背景，以實際、動態(tài)、大規(guī)模的工程數據集為檢驗算法可行性的主要依據，從而進一步地提高和完善理論研究成果。