基于一種用于JumpStarter的抗離群的采樣算法

隨著在線服務(wù)系統(tǒng)的蓬勃發(fā)展，多元時(shí)間序列的異常檢測(cè)，例如CPU利用率的組合，平均響應(yīng)時(shí)間和每秒請(qǐng)求，對(duì)于系統(tǒng)可靠性很重要。盡管為此目的設(shè)計(jì)了一系列基于學(xué)習(xí)的方法，但實(shí)證研究表明，這些方法遭受了長(zhǎng)時(shí)間的初始化時(shí)間，以獲得足夠的培訓(xùn)數(shù)據(jù)。本文壓縮感測(cè)技術(shù)引入了多元時(shí)間序列異常檢測(cè)，以快速初始化。為了構(gòu)建跳躍異常檢測(cè)器，提出了一種名為Jumpstarter的方法?；谟蛱禺愋砸?jiàn)解，設(shè)計(jì)了一種基于形狀的聚類算法以及一種用于JumpStarter的抗離群的采樣算法。

背景及動(dòng)機(jī)

1、多元時(shí)間序列

在在線服務(wù)系統(tǒng)中，操作員不斷收集多個(gè)指標(biāo)的監(jiān)視數(shù)據(jù)，或從日志中提取數(shù)值。服務(wù)水平度量（例如，平均響應(yīng)時(shí)間）或機(jī)器級(jí)度量（例如CPU利用率，內(nèi)存利用率）通常是通過(guò)相等的間隔收集的，形成單變量時(shí)間序列。但是，任何單變量時(shí)間序列都無(wú)法捕獲系統(tǒng)的所有類型的性能問(wèn)題。由于系統(tǒng)通常具有監(jiān)視指標(biāo)的集合，因此可以表示為多變量時(shí)間序列，其中包括各種類型的單變量時(shí)間序列，從而跟蹤性能問(wèn)題的各個(gè)方面。隨著系統(tǒng)的規(guī)模和復(fù)雜性的增加，手動(dòng)檢查系統(tǒng)異常變得越來(lái)越困難。因此，多元時(shí)間序列異常檢測(cè)非常重要。

2、異常檢測(cè)

使用多元時(shí)間序列的異常檢測(cè)在線服務(wù)系統(tǒng)中很重要。在以前的異常檢測(cè)工作中，操作員在以下幾點(diǎn)上有一個(gè)粗略的共識(shí)：

1）多元時(shí)間序列異常是數(shù)據(jù)點(diǎn)或數(shù)據(jù)段，它顯著偏離了操作員對(duì)操作員的期望正常行為，可以在視覺(jué)上觀察到。

2）異常表明可能出現(xiàn)問(wèn)題，盡管仍需要進(jìn)一步調(diào)查進(jìn)行驗(yàn)證。

3）異常檢測(cè)通常用作失敗發(fā)現(xiàn)機(jī)制。

初始化時(shí)間的實(shí)證研究

1、異常檢測(cè)初始化時(shí)間

在部署或更新的新服務(wù)時(shí)，運(yùn)營(yíng)商通常為其啟動(dòng)一種異常檢測(cè)方法。如圖所示，異常檢測(cè)方法的初始化時(shí)間是啟動(dòng)何時(shí)（T1）到有效的時(shí)間（T2）。

許多先前方法使用基于學(xué)習(xí)的工作流來(lái)檢測(cè)異常。通常，它們是根據(jù)歷史數(shù)據(jù)進(jìn)行定期培訓(xùn)的。這些方法的初始化時(shí)間，例如數(shù)十天相對(duì)較長(zhǎng)，因?yàn)樗鼈兺ǔＰ枰峁┐罅康臍v史數(shù)據(jù)進(jìn)行培訓(xùn)。在表中，列出了不同數(shù)據(jù)集上五種基于學(xué)習(xí)的異常檢測(cè)方法的建議初始化時(shí)間。

2、增量再訓(xùn)練

考慮到基于學(xué)習(xí)的異常檢測(cè)方法的漫長(zhǎng)初始化時(shí)間，人們可能建議逐步保留，即逐漸（逐步）添加一個(gè)短期（例如一天）數(shù)據(jù)來(lái)訓(xùn)練這些方法。這樣，我們可以逐步提高這些方法的性能。每次添加一天的數(shù)據(jù)是因?yàn)檫@些基于學(xué)習(xí)的方法至少需要數(shù)千個(gè)數(shù)據(jù)點(diǎn)來(lái)收斂。然后，嘗試將增量再培訓(xùn)應(yīng)用于最新的多元時(shí)間序列檢測(cè)方法，即全曲率和mecred。

這聽(tīng)起來(lái)很理想，但是使用增量再培訓(xùn)的異常檢測(cè)不能確保令人滿意的性能。圖中顯示了隨著訓(xùn)練數(shù)據(jù)的增加（日復(fù)一日）的增加，F(xiàn)1的平均得分和訓(xùn)練時(shí)間。從圖中，可以看到，使用更多的訓(xùn)練數(shù)據(jù)，以及使用更多的訓(xùn)練數(shù)據(jù)，直到將10天的數(shù)據(jù)用于培訓(xùn)，它們才收斂。一個(gè)主要原因是，這些基于學(xué)習(xí)的方法必須從大量培訓(xùn)數(shù)據(jù)中明確學(xué)習(xí)多元時(shí)間序列的概率分布，以捕獲其正常行為。圖中表明，訓(xùn)練時(shí)間隨訓(xùn)練數(shù)據(jù)的規(guī)模線性增加。當(dāng)培訓(xùn)數(shù)據(jù)集包含10天的數(shù)據(jù)時(shí)，大約需要35分鐘才能訓(xùn)練。因此，這些方法由于其非舒適性和相當(dāng)大的培訓(xùn)成本而不適合新部署或更新的系統(tǒng)。

Jumpstarter方法

1、關(guān)鍵思想和挑戰(zhàn)

為了處理上述基于學(xué)習(xí)方法的局限性，將壓縮感測(cè)（CS）用于多變量時(shí)間序列異常檢測(cè)。CS是一種信號(hào)處理技術(shù)，用于從一系列采樣測(cè)量結(jié)果中重建信號(hào)。從這些樣品中重建的信號(hào)保留了原始信號(hào)的高能量成分，在某些輕度假設(shè)下概率很高。可以通過(guò)檢查重建信號(hào)是否與原始信號(hào)（多元時(shí)間序列）存在超過(guò)白噪聲的不同，來(lái)確認(rèn)檢測(cè)異常。由于CS不需要任何訓(xùn)練，因此基于CS的異常檢測(cè)的初始化時(shí)間是窗口大小W。

有兩個(gè)方式來(lái)進(jìn)行信號(hào)重建：

1、將多變量時(shí)間序列視為一個(gè)N×W的矩陣。

2、將多變量時(shí)間序列視為N個(gè)長(zhǎng)度為W的單變量序列。

結(jié)果如圖所示，第一種方式，對(duì)數(shù)據(jù)隨機(jī)采樣并進(jìn)行重建之后，出現(xiàn)前兩維數(shù)據(jù)在全時(shí)間跨度內(nèi)重建序列和原始序列都差異較大的情況。

第二種方式，原始和重建的單變量時(shí)間序列之間的差異表現(xiàn)為正常段中的白噪聲和異常的大波動(dòng)，可準(zhǔn)確捕獲每個(gè)單變量時(shí)間序列的異常。但是，它無(wú)法捕獲多元時(shí)間序列之間的復(fù)雜關(guān)系。此外，由于大量單變量時(shí)間序列的挑戰(zhàn)，單獨(dú)的重建在計(jì)算上更昂貴。

2、概述

1、采用一種基于形狀的聚類方法將多元時(shí)間序列的單變量時(shí)間序列分組為離線處理中的幾個(gè)組。

2、滑動(dòng)窗口技術(shù)應(yīng)用于在線異常檢測(cè)中的多元時(shí)間序列。

3、對(duì)于每組單變量時(shí)間序列，使用一種新型的抗異常值采樣算法來(lái)解決來(lái)自異常段采樣引入的挑戰(zhàn)，并應(yīng)用壓縮感測(cè)來(lái)重建它們。之后，比較原始時(shí)間序列和重建的多元時(shí)間序列，并使用EVT閾值對(duì)異常得分進(jìn)行異常確定。

3、Shape-Based Clustering

先前提到的兩種方式都存在自己的問(wèn)題。特別是第一種方式無(wú)法很好的在不同形狀的維度上進(jìn)行重建，因此一種方式就是按照形狀將多元分為幾個(gè)群集進(jìn)而重建每個(gè)群集。

采用基于形狀的距離（已有相關(guān)工作），是一種基于跨相關(guān)的方法，以測(cè)量?jī)蓚€(gè)單變量時(shí)間序列之間的距離。在處理高維度序列時(shí)，它可以實(shí)現(xiàn)高計(jì)算效率。表中說(shuō)明了聚類結(jié)果的示例。多元時(shí)間序列的九個(gè)單變量時(shí)間序列分為三個(gè)群集。在每個(gè)集群中，時(shí)間序列與其相應(yīng)監(jiān)視指標(biāo)的物理含義相關(guān)，表明這個(gè)方法是直觀有效的。

基于一日數(shù)據(jù)的每個(gè)多變量時(shí)間序列將單變量時(shí)間序列集成，因?yàn)榇蠖鄶?shù)單變量時(shí)間序列大致與24小時(shí)的周期大致相同，與客戶的企業(yè)使用模式相吻合。此外，在軟件更改后，單變量時(shí)間序列的形狀通常保持不變。因此，在軟件更改后，它無(wú)需重新群集。

4、Outlier-Resistant Sampling

異常通常是觀察窗口（滑動(dòng)）窗口中的異常值。如果異常的持續(xù)時(shí)間比窗口大小更長(zhǎng)，則可以從一開(kāi)始就捕獲，因?yàn)樗c正常模式顯著不同。因此，可以采用簡(jiǎn)單的離群檢測(cè)算法來(lái)獲得每個(gè)數(shù)據(jù)點(diǎn)的采樣置信度。數(shù)據(jù)點(diǎn)可能越高，其采樣置信度越低，選擇的可能性就越小?；谶@種見(jiàn)解，文章設(shè)計(jì)了一種抗離群的抽樣算法，即一維隨機(jī)高斯，它不僅可以保證撕裂，而且還可以抵抗異常值。

從圖中的result部分可以看出最后得到的兩個(gè)樣本點(diǎn)，盡管綠色的取樣點(diǎn)位于原始時(shí)間序列的異常段，但是得到的樣本點(diǎn)依舊穩(wěn)定。

4、Compressed Sensing Reconstruction

壓縮傳感理論首先將信號(hào)投影到一個(gè)低維的信號(hào)空間,然后通過(guò)解一個(gè)基于凸優(yōu)化的非線性恢復(fù)算法將信號(hào)恢復(fù),而僅僅需要很少的數(shù)據(jù)，文章使用了CVXPY這個(gè)凸優(yōu)化算法。

5、異常得分

使用歐幾里得距離計(jì)算兩個(gè)時(shí)間序列之間的差異得分。

6、選擇閾值

要正確生成異常警報(bào)，需要準(zhǔn)確選擇一個(gè)閾值，以確定異常得分是否足夠高以觸發(fā)警報(bào)。靜態(tài)閾值無(wú)法正常工作，因?yàn)閿?shù)據(jù)分布會(huì)隨時(shí)間變化。由于JumpStarter產(chǎn)生的異常得分的極值通常代表異常，因此采用廣泛使用的極值理論（EVT）自動(dòng)調(diào)整異常閾值。EVT是一種旨在找到極值定律的統(tǒng)計(jì)理論，并且不假定數(shù)據(jù)分布。已證明它可以準(zhǔn)確選擇異常檢測(cè)方法的閾值。

實(shí)驗(yàn)

實(shí)驗(yàn)部分主要解決以下研究問(wèn)題：RQ1：Jumpstarter在多元時(shí)間序列序列檢測(cè)中的表現(xiàn)如何？RQ2：每個(gè)組件是否有助于Jumpstarter？RQ3：Jumpstarter的主要參數(shù)如何影響其性能？數(shù)據(jù)集的情況如下圖所示。

RQ1: Performance of JumpStarter

可以看到，在在線實(shí)驗(yàn)中，JumpStarter的性能明顯優(yōu)于所有三個(gè)數(shù)據(jù)集中所有段的四個(gè)基線方法。

接下來(lái)是軟件更改后的異常檢測(cè)。

上圖顯示了軟件更改后五種方法的平均FPR，所有這些方法遇到的軟件更改都發(fā)生在圖中的第七分鐘。可以觀察到，在這些軟件更改后，所有五種方法都會(huì)產(chǎn)生誤報(bào)。但是，JumpStarter僅遭受大約五分鐘的高FPR，此后其FPR變得很低。

同時(shí)可以看到JumpStarter的準(zhǔn)備時(shí)間和運(yùn)行時(shí)間都比較少。

RQ2: Contributions of Components

通過(guò)去除各個(gè)步驟得到的F1-score來(lái)看，基于形狀的聚類和抗異常值的采樣的組合有助于準(zhǔn)確有效。

RQ3: Parameter Sensitivity

JumpStarter的初始化時(shí)間取決于檢測(cè)窗口大小w。我們從經(jīng)驗(yàn)上將窗戶尺寸從十分鐘增加到60分鐘。圖中顯示了隨著窗口尺寸的增加，Jumpstarter的平均最佳F1分?jǐn)?shù)和連桿檢測(cè)時(shí)間如何變化。在窗口大小達(dá)到20分鐘之前，Jumpstarter的準(zhǔn)確性會(huì)增加，之后它變得穩(wěn)定，而檢測(cè)時(shí)間逐漸增加。因此，窗口尺寸為二十分鐘，這使Jumpstarter既準(zhǔn)確又有效。請(qǐng)注意，對(duì)于那些持續(xù)超過(guò)20分鐘的異常，Jumpstarter仍然能夠檢測(cè)到它們，因?yàn)樗梢栽趩?dòng)時(shí)很容易捕獲這些異常。

JumpStarter的另一個(gè)重要參數(shù)是初始采樣率σ。圖中顯示了f1的平均最佳F1分?jǐn)?shù)和跳躍體的點(diǎn)檢測(cè)時(shí)間如何隨著σ的增加而變化。同樣，當(dāng)采樣率從0.1增加到0.2時(shí)，JumpStarter的F1得分會(huì)增加，此后變得穩(wěn)定。