Python實現異常檢測LOF演演算法的範例程式碼

2022-03-16 19:00:53

背景

Local Outlier Factor（LOF）是基於密度的經典演演算法（Breuning et. al. 2000）, 文章發表於 SIGMOD 2000, 到目前已經有 3000+ 的參照。

在 LOF 之前的異常檢測演演算法大多是基於統計方法的，或者是借用了一些聚類演演算法用於異常點的識別（比如，DBSCAN，OPTICS）。這些方法都有一些不完美的地方：

基於統計的方法：通常需要假設資料服從特定的概率分佈，這個假設往往是不成立的。
聚類方法：通常只能給出 0/1 的判斷（即：是不是異常點），不能量化每個資料點的異常程度。

相比較而言，基於密度的LOF演演算法要更簡單、直觀。它不需要對資料的分佈做太多要求，還能量化每個資料點的異常程度（outlierness）。

下面開始正式介紹LOF演演算法。

LOF 演演算法

首先，基於密度的離群點檢測方法有一個基本假設：非離群點物件周圍的密度與其鄰域周圍的密度類似，而離群點物件周圍的密度顯著不同於其鄰域周圍的密度。

什麼意思呢？看下面圖片感受下。

叢集 C1 包含了 400 多個點，叢集 C2 包含 100 個點。C1 和 C2 都是一類叢集點，區別是 C1 位置比較集中，或者說密度比較大。而像 o1、o2點均為異常點，因為基於我們的假設，這兩個點周圍的密度顯著不同於周圍點的密度。

LOF 就是基於密度來判斷異常點的，通過給每個資料點都分配一個依賴於鄰域密度的離群因子 LOF，進而判斷該資料點是否為離群點。如果LOF＞=1 ，則該點為離群點，如果LOF≈1 ，則該點為正常資料點。

那什麼是LOF呢？

瞭解LOF前，必須先知道一下幾個基本概念，因為LOF是基於這幾個概念而來的。

1. k鄰近距離

在距離資料點P最近的幾個點中，第K個最近的點跟點P之間的距離稱為點P的 K-鄰近距離，記為 k-distance (p)，公式如下：

點O為距離點P最近的第k個點。

比如上圖中，距離點P最近的第4個點是點6。

這裡的距離計算可以採用歐式距離、漢明距離、馬氏距離等等。比如用歐式距離的計算公式如下：

這裡的重點是找到第k個最近的那個點，然後帶公式計算距離。

2. k距離領域

以點P為圓心，以k鄰近距離d_k(P)為半徑畫圓，這個圓以內的範圍就是k距離領域，公式如下：

還是上圖所示，假設k=4，那麼點 1-6 均是鄰域範圍內的點。

3. 可達距離

這個可達距離大家需要留意點，點P到點O的第k可達距離：

這裡計算P到點O的第k可達距離，但是要以點O為中心，取一個最大值，也就是在點P與O的距離、距離點O最近的第k個點距離中取較大的一個，如圖下所示。

p2距離o遠，那麼兩者之間的可達距離就是它們的實際距離。如果距離足夠近，如點p1，實際距離將被o的k距離代替。所有p接近o的統計波動d(p,o)可以顯著減少，這可以通過引數k來控制，k值越高，同一鄰域內的點的可達距離越相似。

4. 區域性可達密度

先給出公式。

資料點P的區域性可達密度就是基於P的最近鄰的平均可達距離的倒數。距離越大，密度越小。

5. 區域性異常因子

根據區域性可達密度的定義，如果一個資料點跟其他點比較疏遠的話，那麼顯然它的區域性可達密度就小。但LOF演演算法衡量一個資料點的異常程度，並不是看它的絕對區域性密度，而是看它跟周圍鄰近的資料點的相對密度。

這樣做的好處是可以允許資料分佈不均勻、密度不同的情況。區域性異常因子即是用區域性相對密度來定義的。資料點p的區域性相對密度（區域性異常因子）為點p鄰域內點的平均區域性可達密度跟資料點p的區域性可達密度的比值，即：

LOF演演算法流程

瞭解了 LOF 的定義以後，整個演演算法也就顯而易見了：

對於每個資料點，計算它與其它所有點的距離，並按從近到遠排序；
對於每個資料點，找到它的 k-nearest-neighbor，計算 LOF 得分;
如果LOF值越大，說明越異常，反之如果越小，說明越趨於正常。

LOF優缺點

優點

LOF 的一個優點是它同時考慮了資料集的區域性和全域性屬性。異常值不是按絕對值確定的，而是相對於它們的鄰域點密度確定的。當資料集中存在不同密度的不同叢集時，LOF表現良好，比較適用於中等高維的資料集。

缺點

LOF演演算法中關於區域性可達密度的定義其實暗含了一個假設，即：不存在大於等於 k 個重複的點。

當這樣的重複點存在的時候，這些點的平均可達距離為零，區域性可達密度就變為無窮大，會給計算帶來一些麻煩。在實際應用時，為了避免這樣的情況出現，可以把 k-distance 改為 k-distinct-distance，不考慮重複的情況。或者，還可以考慮給可達距離都加一個很小的值，避免可達距離等於零。

另外，LOF 演演算法需要計算資料點兩兩之間的距離，造成整個演演算法時間複雜度為O(n²)。為了提高演演算法效率，後續有演演算法嘗試改進。FastLOF （Goldstein，2012）先將整個資料隨機的分成多個子集，然後在每個子集裡計算 LOF 值。對於那些 LOF 異常得分小於等於 1 的，從資料集裡剔除，剩下的在下一輪尋找更合適的 nearest-neighbor，並更新 LOF 值。

Python 實現 LOF

有兩個庫可以計算LOF，分別是PyOD和Sklearn，下面分別介紹。

使用pyod自帶的方法生成200個訓練樣本和100個測試樣本的資料集。正態樣本由多元高斯分佈生成，異常樣本是使用均勻分佈生成的。

訓練和測試資料集都有 5 個特徵，10% 的行被標記為異常。並且在資料中新增了一些隨機噪聲，讓完美分離正常點和異常點變得稍微困難一些。

from pyod.utils.data import generate_data
import numpy as np
X_train, y_train, X_test, y_test = 
        generate_data(n_train=200,
                      n_test=100,
                      n_features=5,
                      contamination=0.1,
                      random_state=3) 
X_train = X_train * np.random.uniform(0, 1, size=X_train.shape)
X_test = X_test * np.random.uniform(0,1, size=X_test.shape)

PyOD

下面將訓練資料擬合了 LOF 模型並將其應用於合成測試資料。

在 PyOD 中，有兩個關鍵方法：decision_function 和 predict。

decision_function：返回每一行的異常分數
predict：返回一個由 0 和 1 組成的陣列，指示每一行被預測為正常 (0) 還是異常值 (1)

from pyod.models.lof import LOF
clf_name = 'LOF'
clf = LOF()
clf.fit(X_train)

test_scores = clf.decision_function(X_test)

roc = round(roc_auc_score(y_test, test_scores), ndigits=4)
prn = round(precision_n_scores(y_test, test_scores), ndigits=4)

print(f'{clf_name} ROC:{roc}, precision @ rank n:{prn}')
>> LOF ROC:0.9656, precision @ rank n:0.8

可以通過 LOF 模型方法檢視 LOF 分數的分佈。在下圖中看到正常資料（藍色）的分數聚集在 1.0 左右。離群資料點（橙色）的得分均大於 1.0，一般高於正常資料。

Sklearn

在scikit-learn中實現 LOF 進行異常檢測時，有兩種模式選擇：異常檢測模式 (novelty=False) 和 novelty檢測模式 (novelty=True)。

在異常檢測模式下，只有fit_predict生成離群點預測的方法可用。可以使用negative_outlier_factor_屬性檢索訓練資料的異常值分數，但無法為未見過的資料生成分數。模型會根據contamination引數（預設值為 0.1）自動選擇異常值的閾值。

import matplotlib.pyplot as plt

detector = LOF()
scores = detector.fit(X_train).decision_function(X_test)

sns.distplot(scores[y_test==0], label="inlier scores")
sns.distplot(scores[y_test==1], label="outlier scores").set_title("Distribution of Outlier Scores from LOF Detector")
plt.legend()
plt.xlabel("Outlier score")

在novelty檢測模式下，只有decision_function用於生成異常值可用。fit_predict方法不可用，但predict方法可用於生成異常值預測。

clf = LocalOutlierFactor(novelty=True)
clf = clf.fit(X_train)
test_scores = clf.decision_function(X_test)

test_scores = -1*test_scores

roc = round(roc_auc_score(y_test, test_scores), ndigits=4)
prn = round(precision_n_scores(y_test, test_scores), ndigits=4)

print(f'{clf_name} ROC:{roc}, precision @ rank n:{prn}')

該模式下模型的異常值分數被反轉，異常值的分數低於正常值。