Algoritma sederhana untuk deteksi outlier online dari deret waktu umum

88

Saya bekerja dengan sejumlah besar deret waktu. Rangkaian waktu ini pada dasarnya adalah pengukuran jaringan yang datang setiap 10 menit, dan beberapa di antaranya periodik (yaitu bandwidth), sementara beberapa lainnya tidak (yaitu jumlah lalu lintas perutean).

Saya ingin algoritma sederhana untuk melakukan "deteksi outlier" online. Pada dasarnya, saya ingin menyimpan dalam memori (atau pada disk) seluruh data historis untuk setiap seri waktu, dan saya ingin mendeteksi setiap pencilan dalam skenario langsung (setiap kali sampel baru diambil). Apa cara terbaik untuk mencapai hasil ini?

Saat ini saya menggunakan moving average untuk menghilangkan beberapa noise, tapi lalu bagaimana selanjutnya? Hal-hal sederhana seperti standar deviasi, mad, ... terhadap seluruh kumpulan data tidak berfungsi dengan baik (saya tidak dapat menganggap deret waktu stasioner), dan saya ingin sesuatu yang lebih "akurat", idealnya kotak hitam seperti:

double outlier_detection (double * vector, double value);

di mana vektor adalah array ganda yang berisi data historis, dan nilai kembali adalah skor anomali untuk "nilai" sampel baru.

gianluca
sumber
1
Hanya untuk kejelasan, inilah pertanyaan asli pada SO: stackoverflow.com/questions/3390458/…
Matt Parker
1
Saya pikir kita harus mendorong poster untuk mengirim tautan sebagai bagian dari pertanyaan jika mereka memposting pertanyaan yang sama di situs SE lain.
ya, Anda sepenuhnya benar. Lain kali saya akan menyebutkan bahwa pesan tersebut crossposted.
gianluca
Saya juga menyarankan Anda memeriksa tautan Terkait lainnya di sisi kanan halaman. Ini adalah pertanyaan populer dan telah muncul dalam berbagai pertanyaan sebelumnya. Jika mereka tidak memuaskan, yang terbaik adalah memperbarui pertanyaan Anda tentang spesifik situasi Anda.
Andy W
Tangkapan yang bagus, @Andy! Mari kita gabungkan pertanyaan ini dengan yang lain.
Whuber

Jawaban:

75

Berikut adalah fungsi R sederhana yang akan menemukan outlier deret waktu (dan secara opsional menunjukkannya dalam plot). Ini akan menangani seri waktu musiman dan non-musiman. Ide dasarnya adalah untuk menemukan perkiraan yang kuat dari tren dan komponen musiman dan kurangi. Kemudian cari outlier di residu. Tes untuk outlier residual adalah sama seperti untuk boxplot standar - poin lebih besar dari 1,5IQR di atas atau di bawah kuartil atas dan bawah diasumsikan outlier. Jumlah IQR di atas / di bawah ambang ini dikembalikan sebagai "skor" outlier. Jadi skornya bisa berupa angka positif, dan akan menjadi nol untuk yang bukan pencilan.

Saya menyadari Anda tidak menerapkan ini dalam R, tetapi saya sering menemukan fungsi R tempat yang baik untuk memulai. Maka tugasnya adalah menerjemahkan ini ke bahasa apa pun yang diperlukan.

tsoutliers <- function(x,plot=FALSE)
{
    x <- as.ts(x)
    if(frequency(x)>1)
        resid <- stl(x,s.window="periodic",robust=TRUE)$time.series[,3]
    else
    {
        tt <- 1:length(x)
        resid <- residuals(loess(x ~ tt))
    }
    resid.q <- quantile(resid,prob=c(0.25,0.75))
    iqr <- diff(resid.q)
    limits <- resid.q + 1.5*iqr*c(-1,1)
    score <- abs(pmin((resid-limits[1])/iqr,0) + pmax((resid - limits[2])/iqr,0))
    if(plot)
    {
        plot(x)
        x2 <- ts(rep(NA,length(x)))
        x2[score>0] <- x[score>0]
        tsp(x2) <- tsp(x)
        points(x2,pch=19,col="red")
        return(invisible(score))
    }
    else
        return(score)
}
Rob Hyndman
sumber
+1 dari saya, bagus sekali. Jadi,> 1,5 X kisaran antar-kuartil adalah definisi konsensus dari pencilan untuk seri yang tergantung waktu? Itu akan menyenangkan untuk memiliki referensi skala independen.
doug
Tes outlier ada pada residu, jadi semoga ketergantungan waktunya kecil. Saya tidak tahu tentang konsensus, tetapi boxplots sering digunakan untuk deteksi outlier dan tampaknya bekerja dengan cukup baik. Ada metode yang lebih baik jika seseorang ingin membuat fungsinya sedikit lebih keren.
Rob Hyndman
Terima kasih banyak atas bantuannya, saya sangat menghargai. Saya cukup sibuk di tempat kerja sekarang, tetapi saya akan menguji pendekatan seperti Anda secepat mungkin, dan saya akan kembali dengan pertimbangan akhir saya tentang masalah ini. Satu-satunya pemikiran: dalam fungsi Anda, dari apa yang saya lihat, saya harus secara manual menentukan frekuensi deret waktu (ketika membangunnya), dan komponen musiman hanya dipertimbangkan ketika frekuensi lebih besar dari 1. Apakah ada cara yang kuat untuk menangani ini secara otomatis?
gianluca
1
Ya, saya menganggap frekuensi diketahui dan ditentukan. Ada metode untuk memperkirakan frekuensi secara otomatis, tetapi itu akan sangat menyulitkan fungsi. Jika Anda perlu memperkirakan frekuensinya, coba ajukan pertanyaan terpisah tentang hal itu - dan saya mungkin akan memberikan jawaban! Tetapi membutuhkan lebih banyak ruang daripada yang saya miliki dalam komentar.
Rob Hyndman
2
@Marcin, saya sarankan menusuk sendiri. Mungkin menempelkan solusi Anda di gist.github.com dan memposting pertanyaan SO setelah selesai, untuk meminta orang lain memeriksa pekerjaan Anda?
Ken Williams
27

Solusi yang baik akan memiliki beberapa bahan, termasuk:

  • Gunakan jendela bergerak yang halus dan tahan untuk menghilangkan ketidakstabilan.

  • Nyatakan kembali data asli sehingga residu berkenaan dengan kelancaran kira-kira terdistribusi secara simetris. Mengingat sifat data Anda, kemungkinan akar kuadrat atau logaritma mereka akan memberikan residu simetris.

  • Menerapkan metode bagan kendali, atau setidaknya pemikiran bagan kendali, untuk residu.

Sejauh yang terakhir berjalan, pemikiran diagram kontrol menunjukkan bahwa ambang "konvensional" seperti 2 SD atau 1,5 kali IQR di luar kuartil bekerja buruk karena mereka memicu terlalu banyak sinyal palsu di luar kendali. Orang biasanya menggunakan 3 SD dalam pekerjaan diagram kontrol, di mana 2,5 (atau bahkan 3) kali IQR di luar kuartil akan menjadi titik awal yang baik.

Saya kurang lebih telah menguraikan sifat dari solusi Rob Hyndman sambil menambahkan dua poin utama: potensi kebutuhan untuk mengekspresikan kembali data dan kebijaksanaan untuk menjadi lebih konservatif dalam memberi sinyal outlier. Saya tidak yakin bahwa Loess baik untuk detektor online, karena itu tidak berfungsi dengan baik di titik akhir. Sebagai gantinya, Anda mungkin menggunakan sesuatu yang sederhana seperti filter median bergerak (seperti pada smoothing tahan Tukey). Jika outlier tidak muncul secara berurutan, Anda dapat menggunakan jendela sempit (5 titik data, mungkin, yang akan terurai hanya dengan ledakan 3 atau lebih outlier dalam grup 5).

Setelah Anda melakukan analisis untuk menentukan ekspresi ulang data yang baik, Anda tidak perlu mengubah ekspresi ulang. Oleh karena itu, detektor online Anda benar-benar hanya perlu merujuk nilai terbaru (jendela terbaru) karena tidak akan menggunakan data sebelumnya sama sekali. Jika Anda memiliki rangkaian waktu yang sangat lama, Anda dapat melangkah lebih jauh untuk menganalisis autokorelasi dan musiman (seperti fluktuasi harian atau mingguan) untuk meningkatkan prosedur.

whuber
sumber
3
Ini adalah jawaban yang luar biasa untuk analisis praktis. Tidak pernah terpikir perlu untuk mencoba 3 IQR di luar kuartil.
John Robertson
3
@ John, 1,5 IQR adalah rekomendasi asli Tukey untuk kumis terpanjang di boxplot dan 3 IQR adalah rekomendasinya untuk menandai poin sebagai "far outliers" (riff pada frasa populer 60-an). Ini dibangun ke banyak algoritma boxplot. Rekomendasi tersebut dianalisis secara teoritis di Hoaglin, Mosteller, & Tukey, Understanding Robust dan Exploratory Data Analysis.
whuber
Ini mengkonfirmasi data deret waktu yang saya coba analisis. Rata-rata jendela dan juga standar deviasi jendela. ((x - rata-rata) / sd)> 3 tampaknya menjadi poin yang ingin saya tandai sebagai outlier. Yah setidaknya memperingatkan sebagai outlier, saya menandai sesuatu yang lebih tinggi dari 10 sd sebagai outlier kesalahan ekstrim. Masalah yang saya temui adalah berapa panjang jendela yang ideal? Saya bermain dengan apa saja antara 4-8 poin data.
Josh Peak
1
@Neo Taruhan terbaik Anda mungkin untuk bereksperimen dengan subset dari data Anda dan mengonfirmasi kesimpulan Anda dengan tes pada sisanya. Anda juga dapat melakukan validasi silang yang lebih formal (tetapi perhatian khusus diperlukan dengan data deret waktu karena saling ketergantungan semua nilai).
whuber
17

(Jawaban ini menanggapi pertanyaan rangkap (sekarang ditutup) di Mendeteksi peristiwa luar biasa , yang menyajikan beberapa data dalam bentuk grafis.)


Deteksi outlier tergantung pada sifat data dan pada apa yang Anda anggap tentang mereka. Metode tujuan umum mengandalkan statistik yang kuat. Semangat dari pendekatan ini adalah untuk mengkarakterisasi sebagian besar data dengan cara yang tidak dipengaruhi oleh outlier dan kemudian menunjuk pada nilai-nilai individual yang tidak sesuai dengan karakterisasi tersebut.

Karena ini adalah deret waktu, ini menambah komplikasi karena perlu (kembali) mendeteksi pencilan secara berkelanjutan. Jika ini harus dilakukan saat seri dibuka, maka kami hanya diizinkan menggunakan data yang lebih lama untuk pendeteksian, bukan data mendatang! Selain itu, sebagai perlindungan terhadap banyak pengujian berulang, kami ingin menggunakan metode yang memiliki tingkat positif palsu yang sangat rendah.

Pertimbangan ini menyarankan menjalankan tes outlier jendela sederhana, kuat bergerak atas data . Ada banyak kemungkinan, tetapi yang sederhana, mudah dipahami dan diimplementasikan dengan mudah didasarkan pada MAD yang sedang berjalan: median deviasi absolut dari median. Ini adalah ukuran variasi yang sangat kuat dalam data, mirip dengan standar deviasi. Puncak terpencil akan menjadi beberapa MAD atau lebih besar dari median.

Rx=(1,2,...,n)n=1150y

# Parameters to tune to the circumstances:
window <- 30
threshold <- 5

# An upper threshold ("ut") calculation based on the MAD:
library(zoo) # rollapply()
ut <- function(x) {m = median(x); median(x) + threshold * median(abs(x - m))}
z <- rollapply(zoo(y), window, ut, align="right")
z <- c(rep(z[1], window-1), z) # Use z[1] throughout the initial period
outliers <- y > z

# Graph the data, show the ut() cutoffs, and mark the outliers:
plot(x, y, type="l", lwd=2, col="#E00000", ylim=c(0, 20000))
lines(x, z, col="Gray")
points(x[outliers], y[outliers], pch=19)

Diterapkan ke dataset seperti kurva merah yang diilustrasikan dalam pertanyaan, ini menghasilkan hasil ini:

Merencanakan

Data ditampilkan dalam warna merah, jendela 30 hari dari median + 5 * ambang batas MAD berwarna abu-abu, dan outlier - yang hanya berupa nilai data di atas kurva abu-abu - berwarna hitam.

(Ambang hanya dapat dihitung mulai dari akhir jendela awal. Untuk semua data di dalam jendela awal ini, ambang pertama digunakan: itu sebabnya kurva abu-abu datar antara x = 0 dan x = 30.)

Efek dari mengubah parameter adalah (a) meningkatkan nilai windowakan cenderung memuluskan kurva abu-abu dan (b) meningkatkan thresholdakan meningkatkan kurva abu-abu. Mengetahui hal ini, seseorang dapat mengambil segmen awal dari data dan dengan cepat mengidentifikasi nilai-nilai parameter yang paling baik memisahkan puncak-puncak terpencil dari sisa data. Terapkan nilai parameter ini untuk memeriksa sisa data. Jika plot menunjukkan metode semakin memburuk dari waktu ke waktu, itu berarti sifat data berubah dan parameter mungkin perlu disetel ulang.

Perhatikan betapa sedikitnya metode ini mengasumsikan tentang data: mereka tidak harus didistribusikan secara normal; mereka tidak perlu menunjukkan periodisitas apa pun; mereka bahkan tidak harus non-negatif. Semua itu mengasumsikan bahwa data berperilaku dengan cara yang hampir sama dari waktu ke waktu dan bahwa puncak terpencil tampak lebih tinggi daripada sisa data.


Jika ada yang ingin bereksperimen (atau membandingkan beberapa solusi lain dengan yang ditawarkan di sini), berikut adalah kode yang saya gunakan untuk menghasilkan data seperti yang ditunjukkan dalam pertanyaan.

n.length <- 1150
cycle.a <- 11
cycle.b <- 365/12
amp.a <- 800
amp.b <- 8000

set.seed(17)
x <- 1:n.length
baseline <- (1/2) * amp.a * (1 + sin(x * 2*pi / cycle.a)) * rgamma(n.length, 40, scale=1/40)
peaks <- rbinom(n.length, 1,  exp(2*(-1 + sin(((1 + x/2)^(1/5) / (1 + n.length/2)^(1/5))*x * 2*pi / cycle.b))*cycle.b))
y <- peaks * rgamma(n.length, 20, scale=amp.b/20) + baseline
whuber
sumber
Ini adalah solusi yang sangat menarik dan saya menghargai bahwa saya dapat mengimplementasikannya tanpa menggunakan R (hanya menggunakan JavaScript biasa dalam aplikasi web). Terima kasih!
hgoebl
15

Jika Anda khawatir tentang asumsi dengan pendekatan tertentu, satu pendekatan adalah melatih sejumlah peserta didik pada sinyal yang berbeda, kemudian gunakan metode ensemble dan agregat atas "suara" dari peserta didik Anda untuk membuat klasifikasi outlier.

BTW, ini mungkin layak dibaca atau membaca sekilas karena referensi beberapa pendekatan untuk masalah ini.

ars
sumber
5

Saya menduga model deret waktu yang canggih tidak akan bekerja untuk Anda karena waktu yang dibutuhkan untuk mendeteksi pencilan menggunakan metodologi ini. Oleh karena itu, berikut ini solusinya:

  1. Pertama-tama tentukan pola lalu lintas 'normal' untuk satu tahun berdasarkan analisis manual dari data historis yang mencakup waktu, hari kerja vs akhir pekan, bulan tahun dll.

  2. Gunakan baseline ini bersama dengan beberapa mekanisme sederhana (mis. Moving average yang disarankan oleh Carlos) untuk mendeteksi outlier.

Anda mungkin juga ingin meninjau literatur kontrol proses statistik untuk beberapa ide.


sumber
1
Ya, inilah yang saya lakukan: sampai sekarang saya secara manual membagi sinyal menjadi beberapa periode, sehingga untuk masing-masing saya dapat menentukan interval kepercayaan di mana sinyal seharusnya diam, dan karena itu saya dapat menggunakan metode standar seperti sebagai standar deviasi, ... Masalah sebenarnya adalah bahwa saya tidak dapat memutuskan pola yang diharapkan untuk semua sinyal yang harus saya analisis, dan itulah mengapa saya mencari sesuatu yang lebih cerdas.
gianluca
Berikut ini satu ide: Langkah 1: Terapkan dan perkirakan model deret waktu umum berdasarkan satu waktu berdasarkan data historis. Ini dapat dilakukan secara offline. Langkah 2: Gunakan model yang dihasilkan untuk mendeteksi outlier. Langkah 3: Pada frekuensi tertentu (mungkin setiap bulan?), Kalibrasi ulang model deret waktu (ini dapat dilakukan secara offline) sehingga deteksi langkah 2 outlier Anda tidak berjalan terlalu jauh dengan pola lalu lintas saat ini. Apakah itu akan berhasil untuk konteks Anda?
Ya, ini mungkin berhasil. Saya sedang memikirkan pendekatan yang sama (menghitung ulang baseline setiap minggu, yang bisa menjadi CPU intensif jika Anda memiliki ratusan deret waktu univariat untuk dianalisis). BTW pertanyaan yang sulit sebenarnya adalah "apa algoritma gaya kotak hitam terbaik untuk pemodelan sinyal yang sepenuhnya generik, mempertimbangkan kebisingan, estimasi tren dan musiman?". AFAIK, setiap pendekatan dalam literatur membutuhkan fase "parameter tuning" yang sangat sulit, dan satu-satunya metode otomatis yang saya temukan adalah model ARIMA oleh Hyndman ( robjhyndman.com/software/forecast ). Apakah saya melewatkan sesuatu?
gianluca
Harap diingat bahwa saya tidak terlalu malas untuk menyelidiki parameter ini, intinya adalah bahwa nilai-nilai ini perlu ditetapkan sesuai dengan pola sinyal yang diharapkan, dan dalam skenario saya, saya tidak dapat membuat asumsi.
gianluca
Model ARIMA adalah model deret waktu klasik yang dapat digunakan agar sesuai dengan data deret waktu. Saya akan mendorong Anda untuk menjelajahi aplikasi model ARIMA. Anda bisa menunggu Rob untuk online dan mungkin dia akan berpadu dengan beberapa ide.
5

Menyesuaikan data secara musiman sehingga hari biasa terlihat lebih dekat dengan rata. Anda bisa mengambil sampel 17:00 hari ini dan mengurangi atau membagi rata-rata 30 hari sebelumnya pada pukul 17:00. Kemudian lihat melewati standar deviasi N (diukur dengan menggunakan data pra-sesuaikan) untuk pencilan. Ini bisa dilakukan secara terpisah untuk "musim" mingguan dan harian.

James Roth
sumber
Sekali lagi, ini bekerja dengan cukup baik jika sinyal seharusnya memiliki musiman seperti itu, tetapi jika saya menggunakan rangkaian waktu yang sama sekali berbeda (yaitu rata-rata waktu perjalanan pulang pergi TCP rata-rata), metode ini tidak akan berfungsi (karena akan lebih baik untuk mengatasinya dengan rata-rata global sederhana dan standar deviasi menggunakan jendela geser yang berisi data historis).
gianluca
1
Kecuali jika Anda bersedia menerapkan model deret waktu umum (yang membawa kontra dalam hal latensi dll) Saya pesimis bahwa Anda akan menemukan implementasi umum yang pada saat yang sama cukup sederhana untuk bekerja untuk semua jenis deret waktu.
Komentar lain: Saya tahu jawaban yang baik mungkin "sehingga Anda dapat memperkirakan periodisitas sinyal, dan memutuskan algoritma untuk digunakan sesuai dengan itu", tapi saya tidak menemukan solusi yang sangat baik untuk masalah lain ini (saya memainkan sedikit dengan analisis spektral menggunakan DFT dan analisis waktu menggunakan fungsi autokorelasi, tetapi deret waktu saya mengandung banyak noise dan metode semacam itu memberikan hasil yang gila hampir sepanjang waktu)
gianluca
Komentar untuk komentar terakhir Anda: itulah sebabnya saya mencari pendekatan yang lebih umum, tetapi saya memerlukan semacam "kotak hitam" karena saya tidak dapat membuat asumsi tentang sinyal yang dianalisis, dan karena itu saya tidak dapat membuat + msgstr "set parameter terbaik untuk algoritma pembelajaran".
gianluca
@ gianluca Seperti yang telah Anda ketahui, struktur ARIMA yang mendasarinya dapat menutupi anomali. Formulasi yang salah jika variabel penyebab yang mungkin seperti jam dalam sehari, hari dalam seminggu, efek liburan dll juga dapat menutupi anomali. Jawabannya cukup jelas Anda harus memiliki eqaution yang baik untuk mendeteksi anomali secara efektif. Mengutip Bacon, "Karena siapa pun yang tahu cara-cara Alam akan lebih mudah melihat penyimpangannya dan, di sisi lain, siapa pun yang tahu penyimpangannya akan lebih akurat menggambarkan cara-caranya."
IrishStat
3

Alternatif untuk pendekatan yang digariskan oleh Rob Hyndman adalah menggunakan Holt-Winters Forecasting . Pita kepercayaan yang diturunkan dari Holt-Winters dapat digunakan untuk mendeteksi pencilan. Berikut adalah makalah yang menjelaskan cara menggunakan Holt-Winters untuk "Deteksi Perilaku Aberrant dalam Rangkaian Waktu untuk Pemantauan Jaringan". Implementasi untuk RRDTool dapat ditemukan di sini .

Peter Prettenhofer
sumber
2

Analisis spektral mendeteksi periodisitas dalam deret waktu stasioner. Pendekatan domain frekuensi berdasarkan estimasi kepadatan spektral adalah pendekatan yang saya sarankan sebagai langkah pertama Anda.

Jika untuk periode-periode tertentu, ketidakteraturan berarti puncak yang jauh lebih tinggi daripada tipikal untuk periode itu maka deret dengan penyimpangan seperti itu tidak akan stasioner dan analisis spektral tidak akan sesuai. Tetapi dengan asumsi Anda telah mengidentifikasi periode yang memiliki penyimpangan Anda harus dapat menentukan kira-kira berapa tinggi puncak normal akan dan kemudian dapat menetapkan ambang batas pada tingkat di atas rata-rata untuk menunjuk kasus tidak teratur.

Michael Chernick
sumber
2
Bisakah Anda menjelaskan bagaimana solusi ini akan mendeteksi "penyimpangan lokal"? Memberikan contoh yang berhasil akan sangat membantu. (Sejujurnya, saya sarankan Anda melakukan ini karena dalam melakukan latihan seperti itu saya percaya Anda akan menemukan bahwa saran Anda tidak efektif untuk deteksi outlier. Tapi saya bisa salah ...)
whuber
1
@whuber Analisis spektral hanya akan mengidentifikasi di mana semua puncak berada. Langkah selanjutnya adalah mencocokkan model seri yime menggunakan istilah sinus dan kosinus dengan frekuensi yang ditentukan dari analisis spektral dan amplitudo yang diperkirakan dari data. Jika penyimpangan berarti puncak dengan amplitudo yang sangat tinggi maka saya pikir ambang batas pada amplitudo akan sesuai. Jika penyimpangan lokal berarti bahwa untuk suatu periode amplitudo kadang-kadang secara signifikan lebih besar dari yang lain maka seri tidak stasioner dan analisis spektral tidak akan sesuai.
Michael Chernick
1
Saya tidak mengikuti kesimpulan tentang kurangnya stasioneritas. Misalnya, jumlah dari bentuk gelombang sinusoidal reguler dan proses titik Poisson yang ditandai akan tetap, tetapi tidak akan menunjukkan periodisitas yang Anda cari. Namun Anda akan menemukan beberapa puncak yang kuat dalam periodogram, tetapi mereka akan memberi tahu Anda tidak ada yang relevan dengan puncak data tidak teratur yang diperkenalkan oleh komponen proses Poisson.
Whuber
1
Rangkaian waktu stasioner memiliki rata-rata yang konstan. Jika puncak untuk komponen periodik dapat berubah dari waktu ke waktu, hal itu dapat menyebabkan rata-rata untuk berubah dari waktu ke waktu dan karenanya seires akan nonstasioner.
Michael Chernick
2

Karena ini adalah data deret waktu, filter eksponensial sederhana http://en.wikipedia.org/wiki/Exponential_smoothing akan memperlancar data. Ini adalah filter yang sangat baik karena Anda tidak perlu mengumpulkan poin data lama. Bandingkan setiap nilai data yang baru dihaluskan dengan yang tidak terhapuskan . Setelah penyimpangan melebihi ambang batas yang telah ditentukan sebelumnya (tergantung pada apa yang Anda yakini sebagai pencilan dalam data Anda), maka pencilan Anda dapat dengan mudah dideteksi.

Dalam CI akan melakukan hal berikut untuk sampel 16 bit real-time (saya percaya ini ditemukan di suatu tempat di sini <Penjelasan - https://dsp.stackexchange.com/questions/378/what-is-the-best-first-order) -iir-aproksimasi-ke-a-moving-average-filter >)

#define BITS2 2     //< This is roughly = log2( 1 / alpha ), depending on how smooth you want your data to be

short Simple_Exp_Filter(int new_sample) 
{static int filtered_sample = 0;
long local_sample = sample << 16; /*We assume it is a 16 bit sample */
filtered_sample += (local_sample - filtered_sample) >> BITS2;   
return (short) ((filtered_sample+0x8000) >> 16); //< Round by adding .5 and truncating.   
}


int main()
{
newly_arrived = function_receive_new_sample();
filtered_sample = Simple_Exp_Filter(newly_arrived);
if (abs(newly_arrived - filtered_sample)/newly_arrived > THRESHOLD)
    {
    //AN OUTLIER HAS BEEN FOUND
    }
 return 0;   
}
AyodeleO
sumber
1

Anda bisa menggunakan standar deviasi dari pengukuran N terakhir (Anda harus memilih N yang sesuai). Skor anomali yang baik adalah berapa banyak standar deviasi yang diukur dari moving average.

Carlos Accioly
sumber
Terima kasih atas tanggapan Anda, tetapi bagaimana jika sinyal menunjukkan musiman tinggi (yaitu banyak pengukuran jaringan ditandai dengan pola harian dan mingguan pada waktu yang sama, misalnya malam vs hari atau akhir pekan vs hari kerja)? Suatu pendekatan yang didasarkan pada standar deviasi tidak akan berfungsi dalam kasus itu.
gianluca
Sebagai contoh, jika saya mendapatkan sampel baru setiap 10 menit, dan saya sedang melakukan deteksi outlier penggunaan bandwidth jaringan suatu perusahaan, pada dasarnya pada jam 6 sore ukuran ini akan turun (ini adalah pola totaly normal yang diharapkan), dan standar deviasi yang dihitung pada jendela geser akan gagal (karena pasti akan memicu peringatan). Pada saat yang sama, jika ukurannya turun pada jam 4 sore (menyimpang dari baseline biasa), ini adalah pencilan nyata.
gianluca
1

Apa yang saya lakukan adalah mengelompokkan pengukuran dengan jam dan hari dalam seminggu dan membandingkan standar deviasi itu. Masih tidak benar untuk hal-hal seperti liburan dan musim panas / musim dingin tetapi sebagian besar benar.

The downside adalah bahwa Anda benar-benar perlu mengumpulkan satu tahun atau lebih data untuk memiliki cukup sehingga stddev mulai masuk akal.

Aleksandar Ivanisevic
sumber
Terima kasih, itulah tepatnya yang saya coba hindari (memiliki banyak sampel sebagai baseline), karena saya ingin pendekatan yang sangat reaktif (mis. Deteksi online, mungkin "kotor", setelah 1-2 minggu baseline)
gianluca
0

Saya menyarankan skema di bawah ini, yang seharusnya dapat diimplementasikan dalam satu hari atau lebih:

Latihan

  • Kumpulkan sebanyak mungkin sampel yang bisa Anda simpan dalam memori
  • Hapus outlier yang jelas menggunakan deviasi standar untuk setiap atribut
  • Hitung dan simpan matriks korelasi dan juga rata-rata dari setiap atribut
  • Hitung dan simpan jarak Mahalanobis dari semua sampel Anda

Menghitung "outlierness":

Untuk satu sampel yang ingin Anda ketahui "outlierness" -nya:

  • Ambil sarana, matriks kovarians, dan jarak Mahalanobis dari pelatihan
  • Hitung jarak Mahalanobis "d" untuk sampel Anda
  • Kembalikan persentil di mana "d" jatuh (menggunakan jarak Mahalanobis dari pelatihan)

Itu akan menjadi skor outlier Anda: 100% adalah outlier ekstrem.


PS. Dalam menghitung jarak Mahalanobis , gunakan matriks korelasi, bukan matriks kovarians. Ini lebih kuat jika ukuran sampel bervariasi dalam satuan dan jumlah.

Ytsen de Boer
sumber
0

Untuk kasus di mana seseorang harus menghitung outlier dengan cepat, seseorang dapat menggunakan ide Rob Hyndman dan Mahito Sugiyama ( https://github.com/BorgwardtLab/sampling-outlier-detection , library (spoutlier), fungsi qsp) untuk menghitung pencilan sebagai berikut:

library(spoutlier)
rapidtsoutliers <- function(x,plot=FALSE,seed=123)
{
    set.seed(seed)
    x <- as.numeric(x)
    tt <- 1:length(x)
    qspscore <- qsp(x)
    limit <- quantile(qspscore,prob=c(0.95))
    score <- pmax((qspscore - limit),0)
    if(plot)
    {
        plot(x,type="l")
        x2 <- ts(rep(NA,length(x)))
        x2[score>0] <- x[score>0]
        tsp(x2) <- tsp(x)
        points(x2,pch=19,col="red")
        return(invisible(score))
    }
    else
        return(score)
}
orgesleka
sumber
0

Deteksi anomali membutuhkan konstruksi persamaan yang menggambarkan ekspektasi. Deteksi Intervensi tersedia dalam pengaturan non-kausal dan kausal. Jika seseorang memiliki seri prediktor seperti harga maka hal-hal bisa menjadi sedikit rumit. Respons lain di sini tampaknya tidak memperhitungkan penyebab yang dapat dialihkan ke akun yang disebabkan oleh seri prediktor yang ditentukan pengguna seperti harga dan karenanya mungkin cacat. Kuantitas yang dijual mungkin tergantung pada harga, mungkin harga sebelumnya dan mungkin kuantitas yang dijual di masa lalu. Dasar untuk deteksi anomali (pulsa, pulsa musiman, pergeseran level, dan tren waktu lokal) ditemukan di https://pdfs.semanticscholar.org/09c4/ba8dd3cc88289caf18d71e8985bdd11ad21c.pdf

IrishStat
sumber
Tautan tidak berfungsi, bisakah Anda memperbaikinya. Terima kasih
Pankaj Joshi
selesai ..................
IrishStat