Algoritma sederhana untuk deteksi outlier online dari deret waktu umum

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.

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)
}

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.

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

R$x = (1,2,\ldots,n)$$n=1150$$y$

# 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:

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

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.

• Deteksi outlier online atas aliran data

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.

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.

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 .

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.

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;   
}

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.

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.

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.

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)
}

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