Local Outlier Factor ile Anormallik Tespiti
(1 votes, average: 5,00 out of 5)
Loading...Local Outlier Factor(LOF) bir noktanın (gözlemin) anormallik derecesini bize söyleyen bir algoritmadır[1]. Anormallik Tespiti (Outlier Detection) Yöntemleri yazımda anormallik tespit algoritmalarının genelde iki tür sonuç ürettiğinden ve bu sonuçların skor veya etiket olabileceğinden bahsetmiştim. LOF, skor üretenlerden.
LOF ne yapıyor? LOF aslında biraz k en yakın komşu (K Nearest Neighbor – KNN) sınıflandırma algoritmasına benziyor. Ortak noktaları hüküm verilirken komuşlara olan uzaklıkların baz alınmasıdır. Farklı olan noktaları ise ilgi duyduğumuz noktanın KNN’de kimlere benzediğini bulmaya çalışırken, LOF’da “kim komşularına daha çok benzemez” i bulmaya çalışırız. Buradaki k değeri kaç komşuya bakılarak hüküm verileceğini gösterir. Yani bir hiper parametredir. Eğer k değerini aşırı küçük belirlersek algoritma gürültülere duyarlı hale gelir. Büyük k değerleri için ise lokal anormallikleri ıskalayabilir.
1. K-Mesafesi (K-distance)
Peki bir k değeri var anladık. KNN olmadığını da anladık. O halde biz bu k değerini nasıl kullanacağız? Cevap: K-mesafesi (k-distance) hesaplamak için. Peki nedir bu k-mesafesi? Bir A noktasının (seçilen k sayısınca) komşularına olan mesafeleri hesaplanır, bu mesafeler küçükten büyüğe sıralanırsa k’ıncı sıradaki mesafe, bize k-mesafesini verir. Başka bir ifadeyle k’ıncı en yakın komşusuna olan mesafe. Tanım, Şekil-1 incelendiğinde daha iyi anlaşılacaktır. Burada k=3’tür. Eğer n tane nokta(gözlem) varsa tüm noktaların mesafeleri hesaplanacağından toplamda n(n-1)/2 adet mesafe hesaplanacaktır. Örneğin 150 gözlemlik bir veri seti için 11.175 adet mesafe hesaplaması yapmak gerekir.
2. Erişilebilirlik Mesafesi (Reachability distance)
Yukarıda tanımladığımız k-mesafesini (k-distance) şimdi erişilebilirlik mesafesini (reachability distance) hesaplamada kullanacağız. Mesafe, iki nokta arasındaki bir mesafedir. İki nokta arasında zaten bir mesafe (örneğin öklit) var. Bir de yukarıda k-mesafesinden bahsetmiştik o da iki nokta arasında. İşte erişilebilirlik mesafesi iki nokta arasındaki bu iki mesafeden uzak olanıdır. Basitçe formüle edecek olursak: erişilebilirlik_mesafesi = max(normal_mesafe, k-mesafesi) veya biraz daha matematiksel hali:
reach-dist(A,B) = max{k-distance(B), dist(A,B)}
Yukarıda Şekil-1’de çember içinde kalan noktalar ile A noktası arasındaki erişilebilirlik mesafesi A’nın k-mesafesi olacaktır. Çember dışında kalan noktalar ile olan erişilebilirlik mesafesi ise normal mesafe olacaktır.
3. Yerel erişilebilirlik yoğunluğu ( Local reachability density)
Şimdi gelelim başka bir kavrama: Yerel erişilebilirlik yoğunluğu (Local reachability density – LRD). Kavramları bindire bindire gidiyoruz çünkü her yeni kavramı açıklamak ve formüle etmek için bir öncekini kullanıyoruz. Burada da erişilebilirlik mesafesini kullanacağız. Şimdi A noktasının k sayısı kadar en yakın komşusu var. Bu komşulardan A noktasına olan erişilebilirlik mesafelerini topluyoruz ve komşu sayısına bölüyoruz ve ardından tersini alıyoruz.
LRD(A) = 1 / ( sum(reach-dist(A,n)) / k )
- A: LRD hesaplanacak noktayı
- n: 1’den k’ya kadar komşu noktaları
- k: Kaç komşuya göre yoğunluk tespiti yapılacağını gösteren tam sayıdır (analist/kullanıcı belirler).
Peki burada diyeceksinizki hepsi çemberin içinde kaldığı için aslında A’nın erişilebilirlik mesafesini komşu sayısı ile çarpıp yine komşu sayısına bölersek A’nın kendi erişilebilirlik mesafesini bulmuş oluyoruz. Hayır öyle değil. Burada diğer noktalardan A’ya doğru bir hesaplama yaptığımız için muhtemelen her nokta ile A arasındaki erişilebilirlik mesafesi farklı olacaktır.
4. Local Outlier Factor (LOF)
Şimdi elde edilen A noktasına ait bu LRD, k en yakın komşusuna ait LRD ile kıyaslanacaktır. Burada komşuların LRD’lerinin A noktası LRD’sine oranlarının toplamının ortalamasını alacağız.
LOF(a) = ( LRD(Komşu1) / LRD(A) + LRD(Komşu2) / LRD(A) + … ) / k
5. Local Outlier Factor (LOF) Sonuçların Yorumlanması
LOF her bir nokta için bir skor üretir. 1’in altındaki bir değer daha yoğun bir bölgeyi gösterirken, 1’den önemli ölçüde daha büyük değerler aykırı değerleri gösterir. Bu durumu Şekil-3’te rahatlıkla görebiliriz. Örneğin 7.6259 puan alan nokta diğer noktalardan çok uzakta kalmış. O yüzden LOF puanı 1’in çok üzerinde. Kırmızı yuvarlak içine alınmamış noktalar outlier olmayan (inlier) noktalar. Bunların LOF skorları 1’e çok yakın veya altında. Peki biz skor yerine noktaları etiketlemek istiyoruz, ne yapacağız? Yani bana algoritma aykırı mı, değil mi onu söylesin, beni puanlarla uğraştırmasın. Kolayı var, bir eşik belirlersiniz, örneğin 1,5, bu eşik üzerindeki LOF puanlarına sahip noktaları aykırı, diğerlerini normal olarak sınırlandırırsınız. Şayet eşiği bodoslama belirlemek istemiyor da bir şeylere dayanarak belirlemek istiyorsanız istatistik dünyası hizmetinizde 🙂
Local Outlier Factor – LOF’un ne olduğundan, ne işe yaradığından ve nasıl çalıştığından kısaca bahsettik. Başka bir yazıda görüşmek dileğiyle inlier veya outlier kalın, tercih sizin 🙂
Kaynakça:
- [1] Breunig, M. M.; Kriegel, H.-P.; Ng, R. T.; Sander, J. (2000). LOF: Identifying Density-based Local Outliers (PDF). Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. SIGMOD. pp. 93–104. doi:10.1145/335191.335388. ISBN1-58113-217-4.
- [2] https://en.wikipedia.org/wiki/Local_outlier_factor
- https://medium.com/@doedotdev/local-outlier-factor-example-by-hand-b57cedb10bd1
- https://towardsdatascience.com/local-outlier-factor-for-anomaly-detection-cc0c770d2ebe
- Kapak Görseli: https://thefederalist.com/2016/04/22/say-goodbye-to-choosing-your-neighbors-and-local-tax-rates/
![](https://www.veribilimiokulu.com/wp-content/uploads/2020/05/logo-e1590873495165.png"){kind=logo}