EVT 极值理论
EVT：Extreme Value Theory；預(yù)測小概率時間發(fā)生的可能，如大洪水，評估海事安全等。
EVT 中心思想是概率分布，可給出事件發(fā)生概率的數(shù)學(xué)公式。
例如常用的高斯分布，通常絕大多數(shù)數(shù)據(jù)不會偏離均值很多，但是對分布兩端的極端值很難預(yù)測；屬于小概率事件，事件越極端發(fā)生概率越低；此時計算發(fā)生概率可使用以往此類極端事件發(fā)生情況擬合曲線。
使用EVT流式檢測異常值：Anomaly Detectionin Streams with Extreme Value Theory
檢測流中的極端值問題可表述為，Xt是一段時間內(nèi)的觀測值，設(shè)置閾值zq，對任何>=0的時間 t，可觀測到Xt > zq 的概率小于q(q很小)
之前常用的方法需要假設(shè)：正常數(shù)據(jù)發(fā)生有很高概率而異常發(fā)生概率很低，需要假設(shè)數(shù)據(jù)分布；而極值理論不需要假設(shè)樣本數(shù)據(jù)的分布，通過理論結(jié)果推測低概率區(qū)域并找出異常點，這種單參數(shù)的方法適用于穩(wěn)定樣本和移動的樣本。
在數(shù)學(xué)上，X是隨機變量，F代表積累分布函數(shù)；F(X)=P(X<=x)；函數(shù)F的尾部分布為F(X)=1-F(X)=P(X>x)；用Xi代表隨機變量和結(jié)果，通過上下文可明確它們的意思。對一個隨機變量X和給定的概率q，記zq為它在1-q層的分位數(shù)，zq是最小值，P(X<=zq)>=1-q，P(X>zq)<q。
EVT的目的是找到極端事件的規(guī)律；極端事件有相同分布而不同于其原有分布。例如溫度和潮汐的最大值幾乎有相同分布而與潮汐和溫度的分布不相同，這種分布稱為極值分布EVD，形式如下：
所有正常標(biāo)準(zhǔn)分布的極值都符合EVD分布，極值系數(shù) γ 依賴于原始分布規(guī)則。
例如，X1...Xn 是n個變量，符合高斯正態(tài)分布，Mn為X中的極大值集合，Mn符合EVD分布，γ 由初始分布決定(這里是高斯分布，值為0)
對于多數(shù)概率分布，當(dāng)事件趨向于極值時其概率會下降，
例如當(dāng)X 大于某值是P(X > x)的概率，隨著x增大其概率P趨近于0。
F(x) = P(X>x) 代表 X 的分布的尾部，實際上只有三種尾部形狀和 Gγ 匹配對應(yīng)的函數(shù)。
?根據(jù)上述現(xiàn)象，可不受初始規(guī)則影響而準(zhǔn)確的計算概率。使初始分布正式化，中心極限定理表述了正態(tài)分布中 n 個變量的均值匯聚到分布中；極值理論對極值表述了同樣的結(jié)果。
極值理論可在原始數(shù)據(jù)分布非常復(fù)雜的情況下，仍可估計極端事件（異常等）。如下圖，藍(lán)色線段表示的是一個未知分布，但是紅色虛線則可以進(jìn)行擬合推動其分布。定義一個異常概率 q?(這是本算法中的唯一參數(shù))，存在一個可能的值 Zq?使 P(X > Zq) < q?，估計 Gγ 擬合紅虛線。
?對未知輸入分布的尾部訓(xùn)練EVD分布，就可以估算出潛在極端事件的概率；實際中，通過給定一個概率 q，可通過P(X > Zq) < q, 計算出zq，q 為概率，Zq為閾值，γ 值的估計是未解決的問題。
一種現(xiàn)存的訓(xùn)練尾部分布的方法是Peaks-Over_Threshold(POT)方法，也稱作第二極值理論。
?累積分布函數(shù)F，當(dāng)且僅當(dāng)下面函數(shù)的 σ 存在，x 屬于自然數(shù)，1 + x * γ > 0。
極值理論（EVT）認(rèn)為不同事物符合不同的數(shù)據(jù)分布，但不同事物的極端事件滿足相同的分布，這個分布稱為極值分布。而 SPOT 應(yīng)用 EVT 第二理論，即極值相對于一個閾值超出的部分滿足帕累托分布(GPD)：
?
這個結(jié)果顯示超過閾值 t 記作 X- t，符合 GPD分布，參數(shù)有γ，σ。GPD分布還需要第三個參數(shù) μ，這里設(shè)置為空。相比對X的極值訓(xùn)練EVD分布，POT是對超出閾值 t 的值 X-t 訓(xùn)練GPD分布(使用帕累托分布去擬合)。
使用極大似然估計計算 γ 和 σ 值，分位數(shù)閾值 Zq 使用下式計算(公式 （1）)：
最大似然估計式子：
?Yi = Xi - t，即所有大于 t 值得Xi 減去 t 的差值的集合。
在嚴(yán)格的GPD分布中，即 Yi 符合GPD分布，最大似然估計相比其他估計有更好的融合性質(zhì)。?
Grimshaw 策略是將兩個變量優(yōu)化問題轉(zhuǎn)為一個變量等式；l(γ, σ) = log(γ, σ)，要找 l 的極值，就是找?l(γ, σ) 的導(dǎo)數(shù)為 0 的解，根據(jù) Grimshaw 策略如果得到解，則變量 x =?γ / σ 是標(biāo)量等式 u(x) * v(x) = 1 的解，而 u(x)，v(x) 如下：
由等式可知 γ? = v(x) - 1，σ = γ / x，這個等式的解只能給出?l(γ, σ) 最大的可能解，所有要得到所有的根去計算對應(yīng)的似然值，用最好的(γ, σ) 作為最終的估計值。
搜索所有根的值，1 + x * Yi 必須是嚴(yán)格的正數(shù)，因為 Yi 為正，所有 x 的范圍 (-(1 / YM), +∞)，YM?是 Yi 中的最大值，通過下面的公式計算上邊界值 Xmax 以搜索根的值：
Ym = min(Yi)，為 Yi 均值，根的數(shù)量未知，要找到使似然值最大的解。
極值理論，通過POT方法估計 Zq，P(X > zq) < q，對X的分布不需要假設(shè)，不需要明確分布類型。
首先是初始化步驟，通過n個觀察值X1...Xn 計算閾值 Zq。之后細(xì)化兩個流式算法，通過輸入數(shù)據(jù)更新Zq，并作為決策邊界。本文提出SPOT用于穩(wěn)態(tài)數(shù)據(jù)，DSPOT用于流動部分。最后可使用一些理論和技術(shù)改進(jìn)，使更新邊界更快更好。
POT初始返回一個閾值 Zq，用 Zq 定義正常邊界；POT 初始化值更像是一個校準(zhǔn)的步驟。
流式異常檢測使用下一個觀察值檢測異常和定義異常閾值 zq。
首先是初始化步驟，通過 n 個觀察值 X1...Xn 計算閾值 Zq。細(xì)化兩個流式算法，通過輸入數(shù)據(jù)更新Zq值，并作為決策邊界。本文提出SPOT用于穩(wěn)態(tài)數(shù)據(jù)，DSPOT用于流動部分。最后可使用一些理論和技術(shù)改進(jìn)，使更新邊界更快更好。
?POT初始返回一個閾值 Zq，使用 Zq 定義正常邊界；
初始化更像是一個校準(zhǔn)的步驟，流式異常檢測使用下一個觀察值檢測，異常和定義異常閾值 Zq。
POT 不需要存儲所有時間序列，只要峰值即可。
在流中檢測異常事件，首先使用POT估計前 n 個值，獲得初始閾值 Zq；對于所有下一個觀測值就可以標(biāo)注事件或更新閾值。如果一個值超過了閾值 Zq， 就認(rèn)為其異常，不使用其更新模型。另一種情況，Xi 大于初始閾值還屬于正常值(峰值樣例)。在峰值樣例中，添加到峰值集合，更新Zq。SPOT假設(shè) Xi 分布不隨時間變化，但可能太嚴(yán)格了。
DSPOT 使 SPOT 不使用 Xi 絕對值而是相對值運行。
使用變量的差值，?Mi 是 i 時刻的均值，Mi 是移動平均，d 是當(dāng)前樣本的前 d 個正常觀測值，d 是一個窗口參數(shù)。假設(shè) Xi 來自相同的靜態(tài)分布。
數(shù)值優(yōu)化：減少參數(shù)選擇的搜索
u(x) * v(x) = 1 的可能的解在下面兩個區(qū)間內(nèi)：
如果 x 是公式的解，則滿足條件：
最大化似然函數(shù)優(yōu)化：使用 L-BFGS-B 解?
初始化 t 值，要確保 t 小于 Zq，t 的概率小于 1 - q，實際中設(shè) t 為一個高的經(jīng)驗分位數(shù) 98%
?SPOT的步驟可以分為兩步：
? ? ? ? （1）calibration，或者叫初始化。根據(jù)已有的數(shù)據(jù)計算t和閾值Zq。
? ? ? ? （2）流式更新閾值Zq，并把它當(dāng)做決策邊界判斷異常。大于Zq的為異常，報出去；
? ? ? ? ? ? ? ? ?在t和zq之間的為peaks，用于更新GPD模型和Zq；小于t的為正常數(shù)據(jù)，不處理;
DSPOT：用與局部平均M的相對值代替原先的絕對值進(jìn)行SPOT。該算法認(rèn)為這個相對值的分布不隨時間變化，即這個相對值滿足SPOT的前提條件。
DSPOT算法流程
? ? ? ? 先取前d個數(shù)計算M（初始化M）
? ? ? ? 再取n個數(shù)計算相對值X', 擬合模型得到初始閾值zq（初始化閾值zq）
? ? ? ? 流式更新模型：
????????如果新來的相對值大于zq，判斷為異常，不更新模型（特指極值分布模型），不更新M值。
????????如果新來的相對值是peak（大于t），更新模型，更新M；
????????否則，只更新M，不更新模型。
參考：
極值理論(Extreme Value Theory) (360doc.com)
基于極值理論的流數(shù)據(jù)實時異常檢測(SPOT/DSPOT, KDD'17) - 知乎
基于極值理論的單變量時間序列流式異常檢測算法SPOT/DSPOT_m0_37935211的博客-CSDN博客
總結(jié)
- 上一篇： js----与浏览列表有关的对象（浏览器
- 下一篇： RabbitMQ是如何运转的？