一種簡單的方法，可通過Python實(shí)現(xiàn)在數(shù)據(jù)流中查找異常值

在上一篇文章中，我解釋了流算法的概念，并給出了許多如何應(yīng)用流算法的示例。 其中之一是在不保存數(shù)據(jù)流元素的情況下計算數(shù)據(jù)流的滾動平均值。 現(xiàn)在，我想擴(kuò)展這個示例，并在異常值檢測的背景下向您展示另一種流算法的用例。

當(dāng)我們監(jiān)視機(jī)器的功耗以檢測任何異常行為時，可能會出現(xiàn)類似的問題。 如果我們發(fā)現(xiàn)異常值有所增加（異常觀察），則可能表明這臺機(jī)器的默認(rèn)值，可能值得檢查。

定義和示例

離群值可以通過多種方式定義。 在本文中，我們將使用以下定義：

如果數(shù)字?jǐn)?shù)據(jù)流中的元素與到目前為止所見元素的平均值不在3個標(biāo)準(zhǔn)偏差之內(nèi)，則該元素被視為離群值。

這需要一個小例子。 假設(shè)我們按順序獲得數(shù)據(jù)3、2、4、3、5、3、2、10、2、3、1。 讓我們進(jìn)一步假設(shè)，我們從零的均值和方差（以及因此的標(biāo)準(zhǔn)差）開始，即，如果不等于零，則始終將第一個元素視為離群值。

因此，將3視為離群值，因為3> 0 3 * 0。 現(xiàn)在，我們根據(jù)到目前為止看到的元素（僅是數(shù)字3）更新均值和方差。因此，新均值是3，方差是0。

然后我們看到2。我們有2> 3 3 * 0，所以2也被認(rèn)為是離群值。 這是有道理的，因為到目前為止我們只看到了3，所以其他任何數(shù)字都不適合該模式。 平均值更新為（3 2）/2=2.5，方差更新為（（3-2.5）2（2-2.5）2）/2=0.25，這意味著標(biāo)準(zhǔn)偏差為0.5。

現(xiàn)在我們看到4。由于2.5–3 *0.5≤4≤2.53 * 0.5，因此該數(shù)字不是異常值（即正常值）。 平均值更新為（3 2 4）/ 3 = 3，方差更新為（（3–3）2（2–3）2（4–3）2）/ 3 = 2/3，因此標(biāo)準(zhǔn)偏差為 約0.81。

以下數(shù)字3、5、3、2被認(rèn)為是正常的。 憑直覺，我們將下面的數(shù)字10視為離群值。 讓我們看看該算法的作用。 此時的平均值約為3.1，標(biāo)準(zhǔn)偏差約為1。由于10> 3.1 3 * 1，因此我們希望將10視為離群值。

如果繼續(xù)最后三個元素，您將看到它們都是正常的。

問題：要計算平均值和標(biāo)準(zhǔn)偏差，我們必須記住到目前為止看到的所有元素。 如果我們有一個每天輸出成千上萬個元素的系統(tǒng)，那么這不是一個選擇。

救援的流式算法

解決此問題的一種方法是使用流算法，該算法在從數(shù)據(jù)流中每個被掃描元素之后更新其內(nèi)部狀態(tài)。 內(nèi)部狀態(tài)由到目前為止在任何點(diǎn)看到的所有元素的均值和方差組成，從看到任何元素之前的均值和方差為零開始。 確切地說，在看到數(shù)據(jù)流的第n個元素之后，令m?為平均值，v?為方差，并附加定義m?=v?= 0。

計算均值

在我有關(guān)流算法的文章中，我們看到了如何僅使用舊的均值，正在掃描的最新元素以及到目前為止看到的元素數(shù)量來更新均值。 這意味著我們只需要隨時使用這種方法存儲兩個數(shù)字，而不是像幼稚的方法那樣存儲n。 讓我再次顯示它，將數(shù)據(jù)流的第i個傳入元素表示為a?：

這個公式不難開發(fā)，對吧？ 有了它，我們就有了我們期望的元素大小的基線。 現(xiàn)在，我們只需要可以用均值圍繞的標(biāo)準(zhǔn)偏差即可將輸入的示例分類為離群值和正常數(shù)據(jù)點(diǎn)。 我們通過計算方差來做到這一點(diǎn)，然后取其平方根即可達(dá)到標(biāo)準(zhǔn)偏差。

計算方差

在這種情況下，我們也可以輕松找到遞歸公式。 首先，看到n個元素后的方差為

讓我們嘗試再次根據(jù)n，v?和最新元素來寫。 由于方差取決于均值，因此我們也要包含m?。 在開始之前，讓我們重新安排這個公式，以使事情變得更容易：

現(xiàn)在，目標(biāo)是使v?進(jìn)入那里。 一種進(jìn)行方式是從以下簡單的重新排列開始，以隔離平方和直到索引n，它也以v?中的一項出現(xiàn)：

這相當(dāng)于

反過來導(dǎo)致

現(xiàn)在，我們有了公式，讓我們看看它在Python中是如何工作的！

用Python實(shí)現(xiàn)

我們可以通過以下方式實(shí)現(xiàn)上述解釋：

class StreamingMeanAndVariance:

def __init__(self):

self.mean = 0

self.variance = 0

self.n_elements = 0

def update(self, element):

self.variance = ((self.variance + self.mean ** 2) * self.n_elements + element ** 2) / (self.n_elements + 1)

self.mean = ((self.mean * self.n_elements) + element) / (self.n_elements + 1)

self.variance = self.variance - self.mean ** 2

self.n_elements += 1

關(guān)于此的注釋：update方法的第一行計算方差，但不減去當(dāng)前均方根。 在第二行中，計算當(dāng)前平均值。 在第三行中，然后將其從方差中減去，因為在第一行中仍然缺少此值。

要使用它，我們會

import numpy as np

m = StreamingMeanAndVariance()

n = 10000

for i, s in enumerate(np.random.randn(n)):

if not - 3 <= (s - m.mean) / np.sqrt(m.variance) <= 3:

print(i, s)

m.update(s)

這將掃描數(shù)據(jù)流，該數(shù)據(jù)流在此示例中由10000個正態(tài)分布的數(shù)字組成（我們將其表示為N（0,1）），并在出現(xiàn)異常時打印異常值。

如果將法線的間隔和平均值（以黃色表示）作圖，則會得到以下圖片：

以藍(lán)色顯示，您可以看到測量值。綠色區(qū)域包含法線點(diǎn)，其外部的測量值（紅色表示）被認(rèn)為是異常值。以黃色顯示您的期望值（平均值）。

討論區(qū)

該算法可以達(dá)到我們的期望！ 但是，到目前為止，我們還沒有看到它如何處理分配的變化，而是始終只有標(biāo)準(zhǔn)的正態(tài)分布數(shù)。

讓我們測試執(zhí)行以下操作時算法的行為：

結(jié)果看起來像這樣：

Everything adapts slowly to the new data.

優(yōu)點(diǎn)

這看起來很有希望！ 一切都會自動適應(yīng)新數(shù)據(jù)。 當(dāng)數(shù)據(jù)的平均值從0變?yōu)?時，我們可以看到很多離群值，這是有道理的。 新平均值2越多，觀測到的異常值就越少，因為2左右是新的常態(tài)。

當(dāng)將平均值從2更改為-2時，我們可以看到更多的離群值，因為這種變化要嚴(yán)重得多。 到目前為止，一切都很好。

缺點(diǎn)

如果查看圖的右半部分，可以看到對新數(shù)據(jù)的適應(yīng)非常慢。 如您所見，平均值和標(biāo)準(zhǔn)偏差將在一段時間后再次達(dá)到正確的水平，因為黃線（均值）下降并且綠色區(qū)域再次變窄。 但是直到穩(wěn)定為止，沒有發(fā)現(xiàn)異常值。

為了解決這個問題，我們只能使用最后k個樣本來計算均值和標(biāo)準(zhǔn)差，因為

這會破壞第一次測量的影響。 如果將k設(shè)置為無窮大，則可以從之前獲得算法。

我們將k設(shè)置得越低，算法就越快地適應(yīng)新數(shù)據(jù)。 但是，將k設(shè)置得太小可能會導(dǎo)致丟棄異常值，因為該算法認(rèn)為新數(shù)據(jù)就是這樣。 在設(shè)置k = 1的極端情況下，沒有元素被視為離群值，因為僅考慮了最新元素。

根據(jù)用例，可能幾百或幾千個就可以了。

結(jié)論

在本文中，我們已經(jīng)看到了如何為數(shù)據(jù)流建立一個非常簡單的異常檢測機(jī)制。 我們的算法不需要存儲所有測量值，因此非常容易應(yīng)用，也可以在極其受限制的硬件上使用，并且只需固定存儲即可。 該算法甚至可以適應(yīng)數(shù)據(jù)更改，因此無需手動更新。

唯一需要調(diào)整的是自適應(yīng)率，我們在本文中沒有介紹，但是很容易做到。