Skip to content
Kembali ke hasil pencarian

Local Outlier Factor (LOF)

Diperkenalkan oleh
Breunig, M. M.; Kriegel, H.-P.; Ng, R. T.; Sander, J.
Tahun
2000
Jenis
Density-based anomaly detection (unsupervised)

Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris

Ukuran huruf

Apa fungsinya?

Local Outlier Factor (LOF) adalah algoritma deteksi anomali tanpa pengawasan berbasis kepadatan yang diperkenalkan oleh Breunig, Kriegel, Ng, dan Sander pada tahun 2000.

Algoritma ini menetapkan skor outlier kontinu untuk setiap titik data yang mengukur seberapa terisolasi titik tersebut relatif terhadap lingkungan lokalnya, memungkinkan deteksi anomali yang terlewatkan oleh metode global karena menyatu ke dalam kluster padat di tempat lain dalam ruang.

Intuisi di balik metode

Bayangkan peta kota di mana kebanyakan orang tinggal di distrik perkotaan yang padat. Sebuah rumah yang berdiri sendiri di pedesaan jelas terisolasi. Namun LOF melangkah lebih jauh: ia juga dapat menandai sebuah rumah yang terletak di pinggiran kota yang cukup padat ketika semua tetangga terdekatnya berkumpul dalam kluster yang lebih padat lagi. Alih-alih bertanya 'apakah titik ini jauh dari segalanya?', LOF bertanya 'apakah lingkungan titik ini jauh lebih jarang daripada lingkungan tetangga-tetangganya sendiri?' Sebuah titik yang tetangga-tetangganya semua hidup lebih rapat daripada titik itu sendiri akan mendapatkan skor LOF yang tinggi — menandakan bahwa itu adalah outlier lokal meskipun secara global tidak berada di wilayah kosong.

Sejarah

LOF diperkenalkan oleh Markus Breunig, Hans-Peter Kriegel, Raymond Ng, dan Jörg Sander pada konferensi ACM SIGMOD 2000. Algoritma ini mengatasi keterbatasan yang diakui dari metode outlier yang ada — bahwa metode tersebut bergantung pada ambang batas jarak global dan oleh karena itu mengacaukan anomali lokal dengan titik normal di wilayah yang kurang padat. Makalah tersebut memperkenalkan konsep kepadatan keterjangkauan lokal dan skor LOF, yang dengan cepat menjadi referensi utama dalam deteksi anomali. Sejak itu telah diperluas oleh banyak varian, termasuk LoOP (probabilitas outlier lokal), LOCI, dan COF, dan disertakan dalam pustaka pembelajaran mesin utama. Makalah ACM SIGMOD 2000 telah mengumpulkan ribuan kutipan dan dianggap sebagai salah satu karya fundamental dalam penambangan data berbasis kepadatan.

Kapan digunakan

LOF sesuai ketika anomali diharapkan terjadi dalam kluster dengan kepadatan bervariasi dan ketika ambang batas jarak global akan melewatkan outlier yang tersembunyi di wilayah jarang atau salah menandai titik-titik di kluster yang sah jarang tetapi konsisten. Algoritma ini bekerja pada ruang fitur kontinu apa pun dengan metrik jarak yang bermakna dan tidak memerlukan contoh anomali berlabel (sepenuhnya tanpa pengawasan). Algoritma ini cocok untuk aplikasi seperti deteksi penipuan, deteksi intrusi jaringan, kontrol kualitas manufaktur, dan penyaringan anomali medis. Asumsi utama adalah bahwa inlier membentuk lingkungan lokal yang cukup kohesif dan jarak berpasangan yang bermakna dapat dihitung. LOF berkinerja terbaik ketika n setidaknya puluhan hingga ratusan awal; untuk data berdimensi sangat tinggi (kutukan dimensionalitas) jarak menjadi kurang diskriminatif dan pengurangan dimensi atau pemilihan fitur disarankan terlebih dahulu.

Batasan dan pertimbangan

  • Kompleksitas waktu kuadratik dalam implementasi naif membuatnya lambat pada kumpulan data besar tanpa pengindeksan tetangga terdekat perkiraan.
  • Sensitif terhadap pilihan k: k terlalu kecil menghasilkan skor yang berisik; k terlalu besar mengaburkan struktur lokal.
  • Kinerja menurun di ruang berdimensi sangat tinggi karena kutukan dimensionalitas.
  • Tidak secara alami diskalakan ke data streaming atau online tanpa penghitungan ulang.
  • Tidak menyediakan model yang dapat langsung diterapkan untuk menilai titik-titik baru tanpa akses ke set pelatihan.

Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.

Kelebihan

  • Mendeteksi outlier lokal dalam kumpulan data dengan kluster berkepadatan bervariasi, di mana metode global gagal.
  • Menghasilkan skor kontinu yang dapat diinterpretasikan daripada label biner yang kaku, memungkinkan pilihan ambang batas yang fleksibel.
  • Sepenuhnya tanpa pengawasan: tidak diperlukan data anomali berlabel.
  • Dapat diterapkan pada ruang fitur apa pun dengan metrik jarak yang dapat dihitung, termasuk jarak non-Euclidean.
  • Tahan terhadap skala fitur individual ketika jarak dihitung pada data yang distandardisasi.

Penerapan

  • Deteksi penipuan dalam transaksi keuangan di mana aktivitas penipuan menciptakan pola lokal yang jarang.
  • Deteksi intrusi jaringan dengan menandai catatan lalu lintas yang lingkungan lokalnya jauh lebih jarang daripada sekitarnya.
  • Kontrol kualitas manufaktur untuk mengidentifikasi item cacat dalam data produksi yang kaya sensor.
  • Penyaringan anomali medis — mendeteksi profil pasien yang tidak biasa relatif terhadap kohort pasien yang serupa.
  • Deteksi anomali spasial dalam data geografis dan lingkungan dengan kepadatan heterogen.

Cara kerjanya

Cara kerjanya

1

Untuk setiap titik p, algoritma pertama-tama menghitung k-jarak: jarak ke tetangga terdekat ke-k dari p. Ini mendefinisikan jangkauan lingkungan lokal p. Semua titik dalam jarak tersebut membentuk k-lingkungan N_k(p). Pilihan k mengontrol skala di mana lokalitas dinilai — k kecil menangkap struktur lokal yang halus, k yang lebih besar menghaluskannya.

Rumus
k\text{-dist}(p) = \text{distance to the } k\text{-th nearest neighbor of } p
2

Jarak keterjangkauan dari p ke tetangga o didefinisikan sebagai maksimum dari k-jarak o dan jarak Euclidean (atau metrik lain) aktual antara p dan o. Penghalusan ini mencegah ketidakstabilan ketika dua titik sangat berdekatan: ia mengganti jarak yang sangat kecil dengan jejak yang lebih luas dari lingkungan o sendiri, membuat estimasi kepadatan lebih kuat.

Rumus
\text{reach-dist}_k(p, o) = \max\{k\text{-dist}(o),\, d(p, o)\}
3

Kepadatan keterjangkauan lokal p (lrd) adalah kebalikan dari rata-rata jarak keterjangkauan dari p ke semua k tetangganya. Sebuah titik yang dikelilingi oleh tetangga yang rapat memiliki jarak keterjangkauan rata-rata yang kecil, dan oleh karena itu lrd yang tinggi. Sebuah titik di wilayah yang jarang memiliki jarak keterjangkauan rata-rata yang besar dan lrd yang rendah.

Rumus
\text{lrd}_k(p) = \left(\frac{\sum_{o \in N_k(p)} \text{reach-dist}_k(p,o)}{|N_k(p)|}\right)^{-1}
4

Skor LOF dari p adalah rata-rata rasio nilai lrd tetangganya terhadap lrd p sendiri. Jika tetangga p semuanya memiliki lrd yang jauh lebih tinggi daripada p sendiri — yang berarti mereka tinggal di sub-wilayah yang lebih padat — rasio tersebut melebihi 1, menunjukkan bahwa p adalah outlier lokal. Skor mendekati 1 menunjukkan bahwa p memiliki kepadatan yang sama dengan lingkungannya. Skor yang jauh lebih besar dari 1 menandai titik-titik yang semakin anomali. Perbandingan yang sadar lokalitas inilah yang membedakan LOF dari metode yang hanya berbasis jarak.

Rumus
\text{LOF}_k(p) = \frac{\sum_{o \in N_k(p)} \frac{\text{lrd}_k(o)}{\text{lrd}_k(p)}}{|N_k(p)|}

Kesalahan umum

  • Lupa untuk menstandarisasi atau menormalisasi fitur sebelum menghitung jarak, menyebabkan fitur dengan varians tinggi mendominasi.
  • Menggunakan satu nilai k tanpa analisis sensitivitas; praktik terbaik adalah mengevaluasi beberapa nilai k.
  • Memperlakukan skor LOF sebagai probabilitas — ini adalah ukuran relatif tanpa interpretasi probabilistik tetap.
  • Mengabaikan kutukan dimensionalitas dalam data berdimensi tinggi dan mengharapkan LOF bekerja tanpa pengurangan dimensi sebelumnya.
  • Menetapkan ambang batas LOF arbitrer (misalnya, skor > 1,5) tanpa memeriksa distribusi skor untuk kumpulan data tertentu.

Pertanyaan yang sering diajukan

Bagaimana cara memilih nilai k yang tepat?

Tidak ada k yang optimal secara universal. Praktik umum adalah mengevaluasi rentang nilai — biasanya 5 hingga 50 — dan memeriksa bagaimana distribusi skor dan outlier yang ditandai berubah. Analisis sensitivitas di berbagai nilai k memberikan keyakinan bahwa anomali yang terdeteksi kuat terhadap pilihan tersebut. Pengetahuan domain tentang ukuran kluster minimum yang diharapkan juga dapat memandu batas bawah.

Apa arti skor LOF 1 versus 3?

Skor yang mendekati 1 berarti titik tersebut memiliki kepadatan lokal yang sama dengan tetangganya dan dianggap sebagai inlier. Skor yang secara signifikan lebih besar dari 1 — sering diinterpretasikan sebagai di atas 1,5 atau 2 tergantung pada kumpulan data — menunjukkan bahwa lingkungan titik tersebut jauh lebih jarang daripada lingkungan tetangganya. Tidak ada batas pemotongan universal; ambang batas harus dipilih dengan memeriksa distribusi skor LOF untuk kumpulan data tertentu.

Bisakah LOF menilai titik-titik baru yang belum pernah dilihat tanpa melatih ulang?

LOF adalah metode transduktif: ia memerlukan set pelatihan untuk hadir guna menghitung lingkungan dan kepadatan untuk titik baru mana pun. Untuk menilai observasi baru, set pelatihan harus disimpan dan setiap titik baru harus dimasukkan untuk menghitung ulang k-lingkungannya terhadap titik pelatihan yang disimpan. Beberapa implementasi menawarkan fungsionalitas ini, tetapi secara fundamental berbeda dari model parametrik yang mempelajari fungsi penilaian yang ringkas.

Bagaimana perbandingan LOF dengan Isolation Forest untuk deteksi anomali?

LOF menggunakan estimasi kepadatan berdasarkan lingkungan lokal dan lebih kuat ketika anomali mengelompok di wilayah lokal yang jarang dari ruang yang heterogen. Isolation Forest menggunakan partisi acak dan cenderung lebih cepat dan lebih skalabel untuk kumpulan data besar. Untuk kumpulan data berdimensi tinggi atau sangat besar, Isolation Forest sering lebih disukai; untuk data berdimensi sedang dengan variasi kepadatan, LOF sering menawarkan diskriminasi yang lebih halus.

Metode terkait

Sumber

  1. 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.

    Buka referensi DOI
    Disalin.
  2. Aggarwal, C. C. (2017). Outlier Analysis (2nd ed., Ch. 4). Springer.

    ISBN: 978-3-319-47577-6
    Disalin.
  3. Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed., Ch. 14). Springer.

    ISBN: 978-0-387-84857-0
    Disalin.