機器學習-異常檢測演算法（二）：Local Outlier Factor

01-29

Local Outlier Factor（LOF）是基於密度的經典演算法（Breuning et. al. 2000）, 文章發表於 SIGMOD 2000, 到目前已經有 3000+ 的引用。在 LOF 之前的異常檢測演算法大多是基於統計方法的，或者是借用了一些聚類演算法用於異常點的識別（比如，DBSCAN，OPTICS）。但是，基於統計的異常檢測演算法通常需要假設數據服從特定的概率分布，這個假設往往是不成立的。而聚類的方法通常只能給出 0/1 的判斷（即：是不是異常點），不能量化每個數據點的異常程度。相比較而言，基於密度的LOF演算法要更簡單、直觀。它不需要對數據的分布做太多要求，還能量化每個數據點的異常程度（outlierness）。

演算法介紹

LOF 是基於密度的演算法，其最核心的部分是關於數據點密度的刻畫。如果對 distanced-based 或者 density-based 的聚類演算法有些印象，你會發現 LOF 中用來定義密度的一些概念似曾相識。了解了這些核心概念，整個演算法也就顯而易見了。而整個演算法，最主要的是下面四個概念：

K-鄰近距離（k-distance）：在距離數據點 p 最近的幾個點中，第 k 個最近的點跟點 p 之間的距離稱為點 p 的 K-鄰近距離，記為 k-distance (p) 。

可達距離（rechability distance）：可達距離的定義跟K-鄰近距離是相關的，給定參數k時，數據點 p 到數據點 o 的可達距離 reach-dist（p, o）為數據點 o 的K-鄰近距離和數據點p與點o之間的直接距離的最大值。即：

$reach_dist_{k}(p,o)=max{ktext{-}distance(o),d(p,o)}$

局部可達密度（local rechability density）：局部可達密度的定義是基於可達距離的，對於數據點 p，那些跟點p的距離小於等於 k-distance（p）的數據點稱為它的 k-nearest-neighbor，記為 $N_k(p)$，數據點 p 的局部可達密度為它與鄰近的數據點的平均可達距離的倒數，即：

$lrd_{k}(p)=frac{1}{frac{sum_{oin{N_{k}(p)}}reach_dist_k(p,o)}{|N_k(p)|}}$

局部異常因子（local outlier factor）：根據局部可達密度的定義，如果一個數據點跟其他點比較疏遠的話，那麼顯然它的局部可達密度就小。但LOF演算法衡量一個數據點的異常程度，並不是看它的絕對局部密度，而是看它跟周圍鄰近的數據點的相對密度。這樣做的好處是可以允許數據分布不均勻、密度不同的情況。局部異常因子即是用局部相對密度來定義的。數據點 p 的局部相對密度（局部異常因子）為點p的鄰居們的平均局部可達密度跟數據點p的局部可達密度的比值，即：

$LOF_{k}(p)=frac{sum_{oin{N_k(p)}}frac{lrd(o)}{lrd(p)}}{|N_{k}(p)|}=frac{sum_{oin{N_{k}(p)}}lrd(o)}{|N_{k}(p)|}/lrd(p)$

根據局部異常因子的定義，如果數據點 p 的 LOF 得分在1附近，表明數據點p的局部密度跟它的鄰居們差不多；如果數據點 p 的 LOF 得分小於1，表明數據點p處在一個相對密集的區域，不像是一個異常點；如果數據點 p 的 LOF 得分遠大於1，表明數據點p跟其他點比較疏遠，很有可能是一個異常點。下面這個圖來自 Wikipedia 的 LOF 詞條，展示了一個二維的例子。上面的數字標明了相應點的LOF得分，可以讓人對LOF有一個直觀的印象。

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

1. 對於每個數據點，計算它與其它所有點的距離，並按從近到遠排序；

2. 對於每個數據點，找到它的 k-nearest-neighbor，計算 LOF 得分。

演算法應用

LOF演算法中關於局部可達密度的定義其實暗含了一個假設，即：不存在大於等於 k 個重複的點。當這樣的重複點存在的時候，這些點的平均可達距離為零，局部可達密度就變為無窮大，會給計算帶來一些麻煩。在實際應用時，為了避免這樣的情況出現，可以把 k-distance 改為 k-distinct-distance，不考慮重複的情況。或者，還可以考慮給可達距離都加一個很小的值，避免可達距離等於零。

LOF 演算法需要計算數據點兩兩之間的距離，造成整個演算法時間複雜度為 $O(n^2)$ 。為了提高演算法效率，後續有演算法嘗試改進。FastLOF （Goldstein，2012）先將整個數據隨機的分成多個子集，然後在每個子集里計算 LOF 值。對於那些 LOF 異常得分小於等於 1 的，從數據集里剔除，剩下的在下一輪尋找更合適的 nearest-neighbor，並更新 LOF 值。這種先將數據粗略分成多個部分，然後根據局部計算結果將數據過濾來減少計算量的想法，並不罕見。比如，為了改進 K-means 的計算效率， Canopy Clustering 演算法也採用過比較相似的做法。

參考文獻

1. M. M. Breunig, H. P. Kriegel, R. T. Ng, J. Sander. LOF: Identifying Density-based Local Outliers. SIGMOD, 2000.

2. M. Goldstein. FastLOF: An Expectation-Maximization based Local Outlier detection algorithm. ICPR, 2012