1004
機器學習-異常檢測算法（二）：Local Outlier Factor
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\{k\text{-}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_{o\in{N_{k}(p)}}reach_dist_k(p,o)}{|N_k(p)|}}
$$
局部異常因子（local outlier factor）：根據局部可達密度的定義，如果一個數據點跟其他點比較疏遠的話，那麼顯然它的局部可達密度就小。但LOF算法衡量一個數據點的異常程度，並不是看它的絕對局部密度，而是看它跟周圍鄰近的數據點的相對密度。這樣做的好處是可以允許數據分布不均勻、密度不同的情況。局部異常因子即是用局部相對密度來定義的。數據點 p 的局部相對密度（局部異常因子）為點p的鄰居們的平均局部可達密度跟數據點p的局部可達密度的比值，即：
$$
LOF_{k}(p)=\frac{\sum_{o\in{N_k(p)}}\frac{lrd(o)}{lrd(p)}}{|N_{k}(p)|}=\frac{\sum_{o\in{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 的定義，整個算法也就顯而易見了：
- 對於每個數據點，計算它與其它所有點的距離，並按從近到遠排序；
- 對於每個數據點，找到它的 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 算法也采用過比較相似的做法。
參考文獻
- M. M. Breunig, H. P. Kriegel, R. T. Ng, J. Sander. LOF: Identifying Density-based Local Outliers. SIGMOD, 2000.
- M. Goldstein. FastLOF: An Expectation-Maximization based Local Outlier detection algorithm. ICPR, 2012
最後更新：2017-08-13 22:46:17