局部異常因子算法-Local Outlier Factor(LOF)

        在數(shù)據(jù)挖掘方面，經(jīng)常需要在做特征工程和模型訓(xùn)練之前對(duì)數(shù)據(jù)進(jìn)行清洗，剔除無(wú)效數(shù)據(jù)和異常數(shù)據(jù)。異常檢測(cè)也是數(shù)據(jù)挖掘的一個(gè)方向，用于反作弊、偽基站、金融詐騙等領(lǐng)域。
異常檢測(cè)方法，針對(duì)不同的數(shù)據(jù)形式，有不同的實(shí)現(xiàn)方法。常用的有基于分布的方法，在上、下α分位點(diǎn)之外的值認(rèn)為是異常值（例如圖1），對(duì)于屬性值常用此類方法?；诰嚯x的方法，適用于二維或高維坐標(biāo)體系內(nèi)異常點(diǎn)的判別，例如二維平面坐標(biāo)或經(jīng)緯度空間坐標(biāo)下異常點(diǎn)識(shí)別，可用此類方法。

        這次要介紹一下一種基于距離的異常檢測(cè)算法，局部異常因子LOF算法（Local Outlier Factor）。
用視覺直觀的感受一下，如圖2，對(duì)于C1集合的點(diǎn)，整體間距，密度，分散情況較為均勻一致，可以認(rèn)為是同一簇；對(duì)于C2集合的點(diǎn)，同樣可認(rèn)為是一簇。o1、o2點(diǎn)相對(duì)孤立，可以認(rèn)為是異常點(diǎn)或離散點(diǎn)。現(xiàn)在的問題是，如何實(shí)現(xiàn)算法的通用性，可以滿足C1和C2這種密度分散情況迥異的集合的異常點(diǎn)識(shí)別。LOF可以實(shí)現(xiàn)我們的目標(biāo)。

下面介紹LOF算法的相關(guān)定義：
        1) d(p,o) ：兩點(diǎn)p和o之間的距離；
2) k-distance：第k距離
               對(duì)于點(diǎn)p的第k距離 dk(p) 定義如下： 
               dk(p)=d(p,o) ，并且滿足：
                      a) 在集合中至少有不包括p在內(nèi)的 k 個(gè)點(diǎn)o,∈C{x≠p}， 滿足 d(p,o,)≤d(p,o) ； 
                      b) 在集合中最多有不包括p在內(nèi)的 k−1 個(gè)點(diǎn) o,∈C{x≠p} ，滿足 d(p,o,)<d(p,o) ；

        p的第k距離，也就是距離p第k遠(yuǎn)的點(diǎn)的距離，不包括p，如圖3。

        3) k-distance neighborhood of p：第k距離鄰域
點(diǎn)p的第k距離鄰域 Nk(p) ，就是p的第k距離即以內(nèi)的所有點(diǎn)，包括第k距離。
因此p的第k鄰域點(diǎn)的個(gè)數(shù) |Nk(p)|≥k 。
4) reach-distance：可達(dá)距離
點(diǎn)o到點(diǎn)p的第k可達(dá)距離定義為：
reach−distancek(p,o)=max{k−distance(o),d(p,o)}
也就是，點(diǎn)o到點(diǎn)p的第k可達(dá)距離，至少是o的第k距離，或者為o、p間的真實(shí)距離。
這也意味著，離點(diǎn)o最近的k個(gè)點(diǎn)，o到它們的可達(dá)距離被認(rèn)為相等，且都等于 dk(o) 。
如圖4， o1 到p的第5可達(dá)距離為 d(p,o1) ， o2 到p的第5可達(dá)距離為 d5(o2) 。

        5) local reachability density：局部可達(dá)密度
點(diǎn)ｐ的局部可達(dá)密度表示為：

                表示點(diǎn)p的第k鄰域內(nèi)點(diǎn)到p的平均可達(dá)距離的倒數(shù)。
注意，是p的鄰域點(diǎn) Nk(p) 到p的可達(dá)距離，不是p到 Nk(p) 的可達(dá)距離，一定要弄清楚關(guān)系。并且，如果有重復(fù)點(diǎn)，那么分母的可達(dá)距離之和有可能為0，則會(huì)導(dǎo)致lrd變?yōu)闊o(wú)限大，下面還會(huì)繼續(xù)提到這一點(diǎn)。
這個(gè)值的含義可以這樣理解，首先這代表一個(gè)密度，密度越高，我們認(rèn)為越可能屬于同一簇，密度越低，越可能是離群點(diǎn)。如果p和周圍鄰域點(diǎn)是同一簇，那么可達(dá)距離越可能為較小的 dk(o) ，導(dǎo)致可達(dá)距離之和較小，密度值較高；如果p和周圍鄰居點(diǎn)較遠(yuǎn)，那么可達(dá)距離可能都會(huì)取較大值 d(p,o) ，導(dǎo)致密度較小，越可能是離群點(diǎn)。

        6) local outlier factor：局部離群因子
點(diǎn)p的局部離群因子表示為：

                表示點(diǎn)p的鄰域點(diǎn) Nk(p) 的局部可達(dá)密度與點(diǎn)p的局部可達(dá)密度之比的平均數(shù)。
如果這個(gè)比值越接近1，說明p的其鄰域點(diǎn)密度差不多，p可能和鄰域同屬一簇；如果這個(gè)比值越小于1，說明p的密度高于其鄰域點(diǎn)密度，p為密集點(diǎn)；如果這個(gè)比值越大于1，說明p的密度小于其鄰域點(diǎn)密度，p越可能是異常點(diǎn)。
現(xiàn)在概念定義已經(jīng)介紹完了，現(xiàn)在再回過頭來看一下lof的思想，主要是通過比較每個(gè)點(diǎn)p和其鄰域點(diǎn)的密度來判斷該點(diǎn)是否為異常點(diǎn)，如果點(diǎn)p的密度越低，越可能被認(rèn)定是異常點(diǎn)。至于密度，是通過點(diǎn)之間的距離來計(jì)算的，點(diǎn)之間距離越遠(yuǎn)，密度越低，距離越近，密度越高，完全符合我們的理解。而且，因?yàn)閘of對(duì)密度的是通過點(diǎn)的第k鄰域來計(jì)算，而不是全局計(jì)算，因此得名為“局部”異常因子，這樣，對(duì)于圖1的兩種數(shù)據(jù)集C1和C2，lof完全可以正確處理，而不會(huì)因?yàn)閿?shù)據(jù)密度分散情況不同而錯(cuò)誤的將正常點(diǎn)判定為異常點(diǎn)。
算法思想已經(jīng)講完了，現(xiàn)在進(jìn)入干貨環(huán)節(jié)，亮代碼。
給一個(gè)python實(shí)現(xiàn)的lof算法：
https://github.com/damjankuznar/pylof
再給一下我fork之后的代碼：
https://github.com/wangyibo360/pylof
有區(qū)別：
上面提到了，對(duì)于重復(fù)點(diǎn)局部可達(dá)密度可能會(huì)變?yōu)闊o(wú)限大的問題，我改的代碼對(duì)這個(gè)問題做了處理，如果有重復(fù)點(diǎn)方面的場(chǎng)景，可以用我的代碼，源代碼這塊有bug沒有fix，而且好像代碼主人無(wú)蹤影了，提的pull也沒人管。。。

到此這篇關(guān)于異常點(diǎn)/離群點(diǎn)檢測(cè)算法——LOF解析的文章就介紹到這了,更多相關(guān)異常點(diǎn)/離群點(diǎn)檢測(cè)算法——LOF內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論