異常檢測之SOS演算法

SOS演算法全稱stochastic outlier selection algorithm. 該演算法的作者是jeroen janssens. SOS演算法是一種無監督的異常檢測演算法.

演算法的輸入:

特徵矩陣(feature martrix)或者相異度矩陣（dissimilarity matrix）

演算法的輸出:

一個異常概率值向量（每個點對應一個）.

直覺上，當一個點和其它所有點的關聯度（affinity）都很小的時候，它就是一個異常點。

我們看下面這個數據集:

圖的左邊是6個二維空間上的點，這就是我們的原始輸入數據；而圖的右邊就是一個基於歐氏距離的相異度矩陣，當然根據輸入數據的不同，我們可以用其他的度量距離，比如hamming距離等。下面這張圖展示了SOS演算法的整個流程：

1. 計算相異度矩陣D
2. 計算關聯度矩陣A
3. 計算關聯概率矩陣B
4. 算出異常概率向量

作者使用關聯度的想法據說還是受了Geoffrey Hinton的一個思路的啟發。

SOS演算法中，每一個點都會對應一個方差值，這個方差值取決於點的密度，高密度的點對應較低的方差。

上圖中點 的密度最大，方差最小； 的密度最小，方差最大。事實上，方差如此設置，是為了使每一個點轉化後的鄰居數目相同，這裡的鄰居數目是SOS演算法唯一的一個參數，複雜度(Perplexity)。這裡的複雜度類似於KNN演算法中的K，只是在SOS中鄰居並非一個binary值，而是一個概率值，下圖展示了點 與其它幾個點的關聯概率

事實上，關聯概率矩陣(binding probability matrix)就是把關聯矩陣(affinity matrix)按行歸一化得到的。

得到了binding probability matrix，每個點的異常概率值就用如下的公式計算：

上面公式很好詮釋了我們上文說到的「直覺」：當一個點和其它所有點的關聯度（affinity）都很小的時候，它就是一個異常點

目前flink中已經有了SOS演算法的實現，感興趣的可以參考下Implement Stochastic Outlier Selection

參考文獻：

Stochastic Outlier Selection?

jeroenjanssens.comjeroenjanssens/phd-thesis?

github.com
推薦閱讀：