Aplikasi wavelet untuk algoritma deteksi anomali berbasis seri waktu

25

Saya sudah mulai bekerja dengan cara saya melalui Tutorial Statistik Data Mining oleh Andrew Moore (sangat disarankan untuk orang lain yang pertama kali menjelajah ke bidang ini). Saya mulai dengan membaca PDF yang sangat menarik ini yang berjudul "Tinjauan Pengantar tentang algoritma pendeteksian anomali berbasis time-series" di mana Moore menelusuri banyak teknik yang digunakan dalam pembuatan algoritma untuk mendeteksi wabah penyakit. Di tengah-tengah slide, di halaman 27, ia mendaftar sejumlah "metode canggih" lainnya yang digunakan untuk mendeteksi wabah. Yang pertama terdaftar adalah wavelet . Wikipeida menggambarkan wavelet sebagai

osilasi seperti gelombang dengan amplitudo yang dimulai dari nol, meningkat, dan kemudian menurun kembali ke nol. Ini biasanya dapat divisualisasikan sebagai "osilasi singkat"

tetapi tidak menjelaskan aplikasi mereka ke statistik dan pencarian Google saya menghasilkan makalah yang sangat akademis yang mengasumsikan pengetahuan tentang bagaimana wavelet berhubungan dengan statistik atau buku lengkap tentang masalah ini.

Saya ingin pemahaman dasar tentang bagaimana wavelet diterapkan pada deteksi anomali time-series, seperti cara Moore menggambarkan teknik-teknik lain dalam tutorialnya. Dapatkah seseorang memberikan penjelasan tentang bagaimana metode deteksi menggunakan wavelet bekerja atau tautan ke artikel yang dapat dimengerti tentang masalah ini?

Oren Hizkiya
sumber

Jawaban:

19

Wavelet berguna untuk mendeteksi singularitas dalam suatu sinyal (lihat misalnya makalah di sini (lihat gambar 3 untuk ilustrasi) dan referensi yang disebutkan dalam makalah ini. Saya kira singularitas kadang-kadang bisa menjadi anomali?

Idenya di sini adalah bahwa Continuous wavelet transform (CWT) memiliki garis maksimum yang merambat sepanjang frekuensi, yaitu semakin panjang garis, semakin tinggi singularitas. Lihat Gambar 3 di kertas untuk melihat apa yang saya maksud! perhatikan bahwa ada kode Matlab gratis yang terkait dengan kertas itu, harus ada di sini .


Selain itu, saya dapat memberi Anda beberapa heuristik yang merinci mengapa DISCRETE (contoh sebelumnya adalah tentang yang berkelanjutan) transformasi wavelet ( DWT ) menarik bagi ahli statistik (alasan tidak melelahkan):

  • Ada kelas lebar (realistis (ruang Besov)) sinyal yang ditransformasikan menjadi urutan jarang oleh transformasi wavelet. ( properti kompresi )
  • Kelas luas (quasi-stationary) proses yang diubah menjadi urutan dengan fitur yang hampir tidak berkorelasi ( properti dekorasi )
  • Koefisien wavelet berisi informasi yang terlokalisasi dalam waktu dan frekuensi (pada skala yang berbeda). (properti multi-skala)
  • Koefisien wavelet dari sinyal berkonsentrasi pada singularitasnya .
robin girard
sumber
19

Daftar dalam presentasi yang Anda rujuk tampaknya cukup arbitrer bagi saya, dan teknik yang akan digunakan akan sangat tergantung pada masalah spesifik. Anda akan perhatikan bahwa itu juga termasuk filter Kalman , jadi saya curiga bahwa penggunaan yang dimaksud adalah sebagai teknik penyaringan. Transformasi wavelet umumnya jatuh di bawah subjek pemrosesan sinyal , dan akan sering digunakan sebagai langkah pra-pemrosesan dengan data yang sangat bising. Contohnya adalah kertas " Multi-scale anomaly detection " karya Chen dan Zhan (lihat di bawah). Pendekatannya adalah dengan menjalankan analisis pada spektrum yang berbeda daripada pada seri bising asli.

Wavelet sering dibandingkan dengan transformasi fourier waktu kontinu, meskipun mereka memiliki keuntungan terlokalisasi baik dalam waktu maupun frekuensi. Wavelet dapat digunakan baik untuk kompresi sinyal dan juga untuk menghaluskan (penyusutan wavelet). Pada akhirnya, masuk akal untuk menerapkan statistik lebih lanjut setelah transformasi wavelet telah diterapkan (dengan melihat pada fungsi auto-korelasi misalnya). Salah satu aspek lebih lanjut dari wavelet yang dapat berguna untuk deteksi anomali adalah efek lokalisasi: yaitu, diskontinuitas hanya akan mempengaruhi wavelet yang berada di dekatnya (tidak seperti transformasi fourier). Salah satu aplikasi dari ini adalah untuk menemukan deret waktu stasioner lokal (menggunakan LSW).

Guy Nason memiliki buku bagus yang akan saya rekomendasikan jika Anda ingin mempelajari lebih jauh ke dalam aplikasi statistik praktis: " Metode Wavelet dalam Statistik dengan R ". Ini secara khusus menargetkan penerapan wavelet untuk analisis statistik, dan ia memberikan banyak contoh dunia nyata bersama dengan semua kode (menggunakan paket wavethresh ). Buku Nason tidak membahas "deteksi anomali" secara khusus, meskipun ia melakukan tugas laksamana untuk memberikan gambaran umum.

Terakhir, artikel wikipedia memang menyediakan banyak referensi pengantar yang bagus, jadi ada baiknya memeriksanya secara rinci.

[Sebagai catatan tambahan: jika Anda mencari teknik modern yang bagus untuk deteksi titik perubahan, saya akan menyarankan mencoba HMM sebelum menghabiskan terlalu banyak waktu dengan metode wavelet, kecuali Anda memiliki alasan yang baik untuk menggunakan wavelet di bidang khusus Anda. Ini berdasarkan pengalaman pribadi saya. Tentu saja ada banyak model nonlinier lain yang dapat dipertimbangkan, jadi itu benar-benar tergantung pada masalah spesifik Anda.]

Shane
sumber
1
Tidak jelas bagi saya bagaimana Hidden Markov Model digunakan untuk deteksi anomali tapi saya sangat ingin tahu. Bagian yang sangat tidak jelas bagi saya adalah bagaimana membuat mesin negara yang mendasarinya benar dengan probabilitas transisi yang berarti (kecuali hanya dua negara seperti "anomali" dan "bukan anomali" dengan probabilitas transisi naif di antara mereka).
John Robertson
6

Fungsi-fungsi dasar wavelet diskrit yang paling umum digunakan (berbeda dari CWT yang dijelaskan dalam jawaban Robin) memiliki dua properti bagus yang membuatnya berguna untuk deteksi anomali:

  1. Mereka didukung secara kompak.
  2. Mereka bertindak sebagai band-pass filter dengan pass-band ditentukan oleh dukungan mereka.

Apa artinya ini secara praktis adalah bahwa dekomposisi wavelet diskrit Anda melihat perubahan lokal pada sinyal di berbagai skala dan pita frekuensi. Jika Anda memiliki (misalnya) noise berskala besar, frekuensi tinggi ditumpangkan melintasi fungsi yang menampilkan pergeseran magnitudo rendah dalam periode yang lebih lama, transformasi wavelet akan secara efisien memisahkan kedua skala ini dan memungkinkan Anda melihat perubahan garis dasar yang banyak teknik akan ketinggalan; perubahan dalam garis dasar ini dapat menyarankan wabah penyakit atau perubahan minat lainnya. Dalam banyak hal, Anda dapat memperlakukan dekomposisi itu sendiri sebagai lebih halus (dan ada cukup banyak pekerjaan yang dilakukan pada penyusutan yang efisien untuk koefisien wavelet dalam estimasi nonparametrik, lihat misalnya apa pun yang cukup banyak pada wavelet oleh Donoho). Tidak seperti metode berbasis frekuensi murni, dukungan yang ringkas berarti mereka mampu menangani data yang tidak stasioner. Tidak seperti metode murni berbasis waktu, metode ini memungkinkan penyaringan berbasis frekuensi.

Dalam istilah praktis, untuk mendeteksi anomali atau mengubah titik, Anda akan menerapkan transformasi wavelet diskrit (mungkin varian yang dikenal sebagai "DWT Tumpang tindih Maksimum" atau "shift DWT invarian", tergantung pada siapa yang Anda baca) ke data, dan lihat pada set koefisien frekuensi yang lebih rendah untuk melihat apakah Anda memiliki perubahan signifikan dalam baseline. Ini akan menunjukkan kepada Anda ketika perubahan jangka panjang terjadi di bawah kebisingan sehari-hari. Percival dan Walden (lihat referensi di bawah) mendapatkan beberapa tes untuk koefisien signifikan secara statistik yang dapat Anda gunakan untuk melihat apakah perubahan seperti ini signifikan atau tidak.

Sebuah karya referensi yang sangat baik untuk wavelet diskrit adalah Percival dan Walden, "Metode Wavelet untuk Analisis Rangkaian Waktu". Karya pengantar yang baik adalah "Pengantar wavelet dan transformasi wavelet, primer" oleh Burrus, Gopinath, dan Guo. Jika Anda berasal dari latar belakang teknik, maka "Elemen wavelet untuk insinyur dan ilmuwan" adalah pengantar yang bagus dari sudut pandang pemrosesan sinyal.

(Diedit untuk memasukkan komentar Robin)

Kaya
sumber
Poin pertama yang Anda sebutkan salah, secara umum saya sarankan Anda membaca kalimat pertama bab books.google.fr/… di buku Daubechie. Selain itu, Kalau kau membaca jawaban saya saya sudah mentionned properti bagus dari DWT di bagian 2 dari jawaban saya ...
robin girard
Untuk poin pertama, Anda benar. Saya seharusnya mengatakan "Fungsi dasar wavelet diskrit yang paling umum digunakan"; Saya akan mengedit untuk mencerminkan itu. Untuk poin kedua, Anda memberikan jawaban yang baik untuk bagaimana beberapa CWT (paling sering wavelet DOG atau wavelet Ricker terkait; sesuatu seperti misalnya wavelet Gabor tidak akan memberikan perilaku yang Anda gambarkan) dapat mendeteksi anomali dari jenis singularitas. Saya mencoba memberikan deskripsi analog tentang bagaimana DWT dapat digunakan untuk mendeteksi jenis anomali lainnya.
Rich
Poin kedua yang Anda sebutkan juga kemungkinan salah: dukungan wavelet (jika kompak) memberikan informasi tentang lokalisasi temporal wavelet bukan frekuensi lokalisasi.
robin girard
Wavelet diskrit - atau setidaknya sebagian besar yang diimplementasikan dan umum digunakan - biasanya dirancang untuk memiliki sifat berbasis frekuensi yang berguna di bawah kendala dukungan kompak. Kondisi saat menghilang dari Daubechies, misalnya, kurang lebih setara dengan kerataan dalam pass-band. Sifat-sifat lokalisasi frekuensi dari wavelet biasanya yang menyebabkan koefisien menjadi representasi yang jarang dan memungkinkan estimasi varians derau di bawah asumsi "sinyal + aditif noise nol-rata-rata".
Kaya