Yerel Aykırı Değer Faktörü (LOF)
- Ortaya koyan
- Breunig, M. M.; Kriegel, H.-P.; Ng, R. T.; Sander, J.
- Yıl
- 2000
- Tür
- Density-based anomaly detection (unsupervised)
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Yerel Aykırı Değer Faktörü (LOF), Breunig, Kriegel, Ng ve Sander tarafından 2000 yılında tanıtılan, yoğunluk tabanlı, denetimsiz bir anomali tespit algoritmasıdır.
Her veri noktasına, o noktanın yerel komşuluğuna göre ne kadar izole olduğunu niceliksel olarak belirten sürekli bir aykırı değer skoru atar. Bu sayede, uzayın başka yerlerindeki yoğun kümelere karışarak küresel yöntemlerin gözden kaçırdığı anomalilerin tespitini mümkün kılar.
Yöntemin mantığı
Çoğu insanın yoğun kentsel bölgelerde yaşadığı bir şehir haritası düşünün. Kırsal alanda tek başına duran bir ev açıkça izoledir. Ancak LOF daha da ileri gider: tüm yakın komşuları daha da yoğun bir kümede toplanmışken, orta yoğunlukta bir banliyöde bulunan bir evi de işaretleyebilir. LOF, 'bu nokta her şeyden uzak mı?' diye sormak yerine, 'bu noktanın komşuluğu, kendi komşularının komşuluklarından çok daha seyrek mi?' diye sorar. Komşuları kendisinden daha sıkı bir şekilde bir arada yaşayan bir nokta yüksek bir LOF skoru alır; bu, küresel olarak boş bir bölgede olmasa bile yerel bir aykırı değer olduğunu gösterir.
Tarih
LOF, Markus Breunig, Hans-Peter Kriegel, Raymond Ng ve Jörg Sander tarafından ACM SIGMOD 2000 konferansında tanıtıldı. Mevcut aykırı değer yöntemlerinin bilinen bir sınırlamasını ele aldı — bu yöntemler küresel uzaklık eşiklerine dayanıyor ve bu nedenle yerel anomalileri daha az yoğun bölgelerdeki normal noktalarla karıştırıyordu. Makale, yerel erişilebilirlik yoğunluğu kavramını ve LOF skorunu tanıttı; bu, anomali tespitinde hızla temel bir referans haline geldi. O zamandan beri LoOP (yerel aykırı değer olasılıkları), LOCI ve COF dahil olmak üzere çok sayıda varyantla genişletildi ve büyük makine öğrenimi kütüphanelerine dahil edildi. ACM SIGMOD 2000 makalesi binlerce atıf almıştır ve yoğunluk tabanlı veri madenciliğinin temel çalışmalarından biri olarak kabul edilmektedir.
Ne zaman kullanılır?
LOF, anomalilerin değişen yoğunluktaki kümelerde ortaya çıkmasının beklendiği ve küresel bir uzaklık eşiğinin ya seyrek bölgelerde gizlenmiş aykırı değerleri kaçıracağı ya da meşru olarak seyrek ama tutarlı kümelerdeki noktaları yanlışlıkla işaretleyeceği durumlarda uygundur. Anlamlı bir uzaklık metriğine sahip herhangi bir sürekli özellik uzayında çalışır ve etiketlenmiş anomali örnekleri gerektirmez (tamamen denetimsizdir). Dolandırıcılık tespiti, ağa sızma tespiti, üretim kalite kontrolü ve tıbbi anomali taraması gibi uygulamalar için uygundur. Temel varsayımlar, iç değerlerin makul ölçüde tutarlı yerel komşuluklar oluşturması ve anlamlı ikili uzaklıkların hesaplanabilmesidir. LOF, n en az onlarca ila yüzlerce olduğunda en iyi performansı gösterir; çok yüksek boyutlu veriler için (boyutluluk laneti) uzaklıklar daha az ayırt edici hale gelir ve boyut indirgeme veya özellik seçimi önce tavsiye edilir.
Sınırlar ve dikkat edilmesi gerekenler
- Naif uygulamadaki karesel zaman karmaşıklığı, yaklaşık en yakın komşu indekslemesi olmadan büyük veri kümelerinde yavaş çalışmasına neden olur.
- k seçimine duyarlıdır: çok küçük bir k gürültülü skorlar üretirken; çok büyük bir k yerel yapıyı bulanıklaştırır.
- Boyutluluk laneti nedeniyle çok yüksek boyutlu uzaylarda performans düşer.
- Yeniden hesaplama yapılmadan akış veya çevrimiçi verilere doğal olarak ölçeklenmez.
- Eğitim setine erişim olmadan yeni noktaları doğrudan puanlamak için uygulanabilecek bir model sağlamaz.
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- Küresel yöntemlerin başarısız olduğu, değişen yoğunluktaki kümelere sahip veri kümelerinde yerel aykırı değerleri tespit eder.
- Kesin ikili bir etiket yerine sürekli, yorumlanabilir bir skor üreterek esnek eşik seçimine olanak tanır.
- Tamamen denetimsizdir: etiketlenmiş anomali verisi gerekmez.
- Öklid dışı uzaklıklar dahil olmak üzere, hesaplanabilir bir uzaklık metriğine sahip herhangi bir özellik uzayına uygulanabilir.
- Uzaklıklar standartlaştırılmış veriler üzerinde hesaplandığında, bireysel özelliklerin ölçeğine karşı sağlamdır.
Uygulama alanları
- Dolandırıcılık faaliyetinin yerel olarak seyrek modeller oluşturduğu finansal işlemlerde dolandırıcılık tespiti.
- Yerel komşuluğu çevresinden çok daha seyrek olan trafik kayıtlarını işaretleyerek ağa sızma tespiti.
- Sensör açısından zengin üretim verilerinde kusurlu öğeleri tanımlamak için üretim kalite kontrolü.
- Tıbbi anomali taraması — benzer hasta kohortlarına göre alışılmadık hasta profillerini tespit etme.
- Heterojen yoğunluğa sahip coğrafi ve çevresel verilerde uzamsal anomali tespiti.
Nasıl çalışır?
Nasıl çalışır?
Algoritma, her p noktası için önce k-uzaklığını hesaplar: p'nin k'ıncı en yakın komşusuna olan uzaklığı. Bu, p'nin yerel komşuluğunun erişimini tanımlar. Bu uzaklık içindeki tüm noktalar k-komşuluğu N_k(p) oluşturur. k seçimi, yerelliğin değerlendirildiği ölçeği kontrol eder; küçük k, ince taneli yerel yapıyı yakalarken, daha büyük k bunu yumuşatır.
Formül
k\text{-dist}(p) = \text{distance to the } k\text{-th nearest neighbor of } pp'den bir o komşusuna olan erişilebilirlik uzaklığı, o'nun k-uzaklığı ile p ve o arasındaki gerçek Öklid (veya başka bir metrik) uzaklığının maksimumu olarak tanımlanır. Bu yumuşatma, iki nokta aşırı derecede yakın olduğunda kararsızlığı önler: küçük uzaklıkları, o'nun kendi komşuluğunun daha geniş ayak iziyle değiştirerek yoğunluk tahminlerini daha sağlam hale getirir.
Formül
\text{reach-dist}_k(p, o) = \max\{k\text{-dist}(o),\, d(p, o)\}p'nin yerel erişilebilirlik yoğunluğu (lrd), p'den tüm k komşularına olan ortalama erişilebilirlik uzaklığının tersidir. Sıkıca paketlenmiş komşularla çevrili bir noktanın ortalama erişilebilirlik uzaklığı küçük, dolayısıyla lrd'si yüksektir. Seyrek bir bölgedeki bir noktanın ortalama erişilebilirlik uzaklığı büyük ve lrd'si düşüktür.
Formül
\text{lrd}_k(p) = \left(\frac{\sum_{o \in N_k(p)} \text{reach-dist}_k(p,o)}{|N_k(p)|}\right)^{-1}p'nin LOF skoru, komşularının lrd değerlerinin p'nin kendi lrd'sine oranının ortalamasıdır. Eğer p'nin komşularının hepsi p'nin kendisinden önemli ölçüde daha yüksek lrd'ye sahipse — yani daha yoğun alt bölgelerde yaşıyorlarsa — oran 1'i aşar, bu da p'nin yerel bir aykırı değer olduğunu gösterir. 1'e yakın bir skor, p'nin çevresiyle yaklaşık olarak aynı yoğunluğa sahip olduğunu gösterir. 1'den çok daha büyük skorlar, giderek daha anormal noktaları işaret eder. Bu yerellik-farkındalıklı karşılaştırma, LOF'u yalnızca uzaklık tabanlı yöntemlerden ayıran özelliktir.
Formül
\text{LOF}_k(p) = \frac{\sum_{o \in N_k(p)} \frac{\text{lrd}_k(o)}{\text{lrd}_k(p)}}{|N_k(p)|}Sık yapılan hatalar
- Uzaklıkları hesaplamadan önce özellikleri standartlaştırmayı veya normalleştirmeyi unutmak, yüksek varyanslı özelliklerin baskın olmasına neden olur.
- Duyarlılık analizi yapmadan tek bir k değeri kullanmak; en iyi uygulama, birkaç k değerini değerlendirmektir.
- LOF skorunu bir olasılık olarak ele almak — sabit bir olasılıksal yorumu olmayan göreceli bir ölçüdür.
- Yüksek boyutlu verilerde boyutluluk lanetini göz ardı etmek ve LOF'un önceden boyut indirgeme olmadan çalışmasını beklemek.
- Belirli veri kümesi için skor dağılımını incelemeden keyfi bir LOF eşiği belirlemek (örn. skor > 1.5).
Sık sorulan sorular
k'nin doğru değerini nasıl seçerim?
Evrensel olarak optimal bir k yoktur. Yaygın uygulama, bir dizi değeri — genellikle 5 ila 50 arası — değerlendirmek ve skor dağılımının ve işaretlenen aykırı değerlerin nasıl değiştiğini incelemektir. k değerleri arasındaki bir duyarlılık analizi, tespit edilen anomalilerin seçime karşı sağlam olduğuna dair güven verir. Minimum beklenen küme boyutu hakkındaki alan bilgisi de alt sınırı yönlendirebilir.
LOF skoru 1 ile 3 arasında ne anlama gelir?
1'e yakın bir skor, noktanın komşularıyla yaklaşık olarak aynı yerel yoğunluğa sahip olduğu ve bir iç değer olarak kabul edildiği anlamına gelir. 1'den önemli ölçüde büyük bir skor — veri kümesine bağlı olarak genellikle 1.5 veya 2'nin üzeri olarak yorumlanır — noktanın komşuluğunun, komşularının komşuluklarından çok daha seyrek olduğunu gösterir. Evrensel bir kesme noktası yoktur; eşik, belirli veri kümesi için LOF skorlarının dağılımı incelenerek seçilmelidir.
LOF, yeniden eğitim yapmadan yeni, görülmemiş noktaları puanlayabilir mi?
LOF, transdüktif bir yöntemdir: herhangi bir yeni nokta için komşulukları ve yoğunlukları hesaplamak için eğitim setinin mevcut olmasını gerektirir. Yeni gözlemleri puanlamak için eğitim seti saklanmalı ve her yeni nokta, depolanmış eğitim noktalarına karşı k-komşuluğunu yeniden hesaplamak üzere eklenmelidir. Bazı uygulamalar bu işlevselliği sunar, ancak bu, kompakt bir puanlama fonksiyonu öğrenen parametrik modellerden temelden farklıdır.
LOF, anomali tespiti için Isolation Forest ile nasıl karşılaştırılır?
LOF, yerel komşuluklara dayalı yoğunluk tahmini kullanır ve anomalilerin heterojen bir uzayın yerel olarak seyrek bölgelerinde kümelendiği durumlarda daha güçlüdür. Isolation Forest, rastgele bölümleme kullanır ve genellikle daha hızlı ve büyük veri kümelerine daha ölçeklenebilirdir. Yüksek boyutlu veya çok büyük veri kümeleri için genellikle Isolation Forest tercih edilir; yoğunluk varyasyonu olan orta boyutlu veriler için LOF sıklıkla daha ince ayrımcılık sunar.
İlgili yöntemler
Kaynaklar
Breunig, M. M., Kriegel, H.-P., Ng, R. T., & Sander, J. (2000). LOF: Identifying density-based local outliers. Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, 93–104.
DOI kaynağını açKopyalandı.Aggarwal, C. C. (2017). Outlier Analysis (2nd ed., Ch. 4). Springer.
ISBN: 978-3-319-47577-6Kopyalandı.Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed., Ch. 14). Springer.
ISBN: 978-0-387-84857-0Kopyalandı.