Regresi linier yang cepat kuat untuk pencilan

50

Saya berurusan dengan data linear dengan outlier, beberapa di antaranya berada pada 5 standar deviasi dari garis regresi yang diperkirakan. Saya mencari teknik regresi linier yang mengurangi pengaruh poin-poin ini.

Sejauh ini yang saya lakukan adalah memperkirakan garis regresi dengan semua data, kemudian membuang titik data dengan residu kuadrat yang sangat besar (katakanlah 10% teratas) dan ulangi regresi tanpa poin-poin tersebut.

Dalam literatur ada banyak pendekatan yang mungkin: kuadrat terkecil, regresi kuantil, m-estimator, dll. Saya benar-benar tidak tahu pendekatan mana yang harus saya coba, jadi saya mencari saran. Yang penting bagi saya adalah bahwa metode yang dipilih harus cepat karena regresi yang kuat akan dihitung pada setiap langkah rutin optimasi. Terima kasih banyak!

regression linear-model outliers robust fused-lasso Matteo Fasiolo
sumber

2

Sebuah metode yang Anda tidak menyebutkan adalah penggunaan murid-

t

$t$ kesalahan dengan derajat yang tidak diketahui kebebasan. Namun, ini mungkin tidak secepat yang Anda butuhkan.

@Procrastinator: (Sangat mudah untuk membayangkan konfigurasi outlier di mana) ini tidak akan berfungsi.

user603

@ user603 Itu benar untuk metode apa pun, tidak ada Panacea;). Saya hanya menunjukkan metode lain. +1 untuk jawaban Anda.

3

@Prastrastator: Saya setuju bahwa semua metode akan gagal untuk beberapa tingkat kontaminasi . Dan 'kegagalan' dalam konteks ini dapat didefinisikan secara kuantitatif dan empiris. Tetapi idenya adalah tetap mendukung metode-metode yang hanya akan gagal pada tingkat kontaminasi yang lebih tinggi.

user603

4

Karena ini dilakukan berulang kali selama rutinisasi optimasi, mungkin data dalam regresi (akhirnya) berubah perlahan. Ini menyarankan algoritma yang disesuaikan dengan situasi Anda: mulailah dengan beberapa bentuk regresi yang kuat, tetapi ketika mengambil langkah-langkah kecil selama optimasi, cukup asumsikan pada langkah berikutnya bahwa setiap outlier sebelumnya akan tetap menjadi outlier. Gunakan OLS pada data, lalu periksa apakah outlier dugaan masih outlying. Jika tidak, mulai ulang dengan prosedur yang kuat, tetapi jika demikian - yang mungkin sering terjadi - Anda akan menyimpan banyak perhitungan.

whuber

55

Jika data Anda mengandung outlier tunggal, maka itu dapat ditemukan dengan andal menggunakan pendekatan yang Anda sarankan (tanpa iterasi). Pendekatan formal untuk ini adalah

Cook, R. Dennis (1979). Pengamatan Berpengaruh dalam Regresi Linier . Jurnal Asosiasi Statistik Amerika (American Statistics Association) 74 (365): 169–174.

$M$ $M$ $M$ $\rho$

$\frac{1}{1+p}$ $p$
atau jika outlier tidak outlying dalam ruang desain (Ellis dan Morgenthaler (1992)).

$M$ $l_1$ robustbasequantregR

$\lfloor\frac{n}{p+1}\rfloor$ $M$ $\rho$

Dalam 20 tahun terakhir (dan khususnya 10 tahun terakhir) sejumlah besar algoritma pendeteksi outlier yang cepat dan andal telah dirancang untuk mengatasi masalah kombinatorial ini. Ini sekarang banyak diimplementasikan dalam paket statistik paling populer (R, Matlab, SAS, STATA, ...).

$O(2^p)$ $p$ $n$

$p$ $p<20$

Rousseeuw, PJ dan van Zomeren BC (1990). Unmasking Multivariate Outliers dan Leverage Points . Jurnal Asosiasi Statistik Amerika , Vol. 85, No. 411, hlm. 633-639.

Rousseeuw, PJ dan Van Driessen, K. (2006). Komputasi Regresi LTS untuk Kumpulan Data Besar . Penambangan Data dan arsip Penemuan Pengetahuan Volume 12 Edisi 1, Halaman 29 - 45.

Hubert, M., Rousseeuw, PJ dan Van Aelst, S. (2008). Metode Multivarian Kuat Tinggi . Ilmu Statistik , Vol. 23, No. 1, 92-119

Ellis SP dan Morgenthaler S. (1992). Leverage dan Breakdown di Regresi L1. Jurnal Asosiasi Statistik Amerika , Vol. 87, No. 417, hlm. 143-148

Buku referensi terbaru tentang masalah identifikasi outlier adalah:

Maronna RA, Martin RD dan Yohai VJ (2006). Statistik Kuat: Teori dan Metode . Wiley, New York.

Metode-metode ini (dan banyak variasi lainnya) diimplementasikan (antara lain) dalam paket.robustbase R

pengguna603
sumber

4

Nah, itu jawaban yang bagus!

Peter Flom - Kembalikan Monica

p < 10

$p < 10$

p

$p$

2

p < 10

$p<10$

M

$M$

1

"Sebuah keuntungan besar adalah bahwa sebagian besar dari algoritma ini memalukan paralel." Saya suka kata-katanya. ;)

Mateen Ulhaq

1

@Mateen, yah, itu adalah istilah seni . :)

JM bukan ahli statistik

19

Untuk regresi sederhana (x tunggal), ada sesuatu yang bisa dikatakan untuk garis Theil-Sen dalam hal ketahanan terhadap outlier y dan untuk poin-poin yang berpengaruh serta efisiensi yang umumnya baik (pada normal) dibandingkan dengan LS untuk lereng. Titik kerusakan untuk lereng hampir 30%; selama intersep (ada berbagai kemungkinan intersep yang digunakan orang) tidak memiliki rincian yang lebih rendah, seluruh prosedur mengatasi fraksi kontaminasi yang cukup baik.

Kecepatannya mungkin terdengar seperti buruk - median slope nampak sebagai bahkan dengan median - tetapi ingatan saya adalah bahwa hal itu dapat dilakukan lebih cepat jika kecepatan benar-benar masalah ( , saya percaya) $\binom{n}{2}$ $O(n^2)$ $O(n)$ $O(n \log n)$

Sunting: user603 meminta keuntungan dari regresi Theil daripada regresi L1. Jawabannya adalah hal lain yang saya sebutkan - poin berpengaruh:

Theil_vs_L1

Garis merah adalah kecocokan (dari fungsi dalam paket). Hijau cocok dengan kemiringan Theil. Yang diperlukan hanyalah salah ketik tunggal dalam nilai x - seperti mengetik 533 bukannya 53 - dan hal semacam ini bisa terjadi. Jadi kecocokan tidak kuat untuk satu kesalahan ketik di x-space. $L_1$ rqquantreg $L_1$

Glen_b
sumber

itu memang dapat dihitung dalam waktu . Bisakah Anda menguraikan keuntungan apa (dalam kasus x tunggal) yang oleh penaksir TS, misalnya, regresi ?

n \log n

$n\log n$

l_{1}

$l_1$

user603

1

@ user603 Lihat hasil edit.

Glen_b

(+1) terima kasih untuk hasil editnya. Penting untuk menunjukkan fitur ini.

user603

1

Dan apa kelebihan dibandingkan dengan perkiraan-MM, seperti lmrob () dari paket R robustbase atau bahkan {tidak perlu menginstal apa pun selain 'basis R'} rlm (*, ... method = "MM") dari paket MASS? Ini memiliki titik kerusakan penuh (~ 50%) dan mungkin bahkan lebih efisien pada normal.

Martin Mächler

1

@ MartinMächler Sepertinya Anda menentang klaim yang belum saya buat di sana. Jika Anda ingin memberikan jawaban yang juga berisi perbandingan dari penaksir kuat tingkat tinggi lainnya, terutama yang kira-kira mudah dimengerti bagi seseorang di tingkat OP, saya berharap untuk membacanya.

Glen_b

12

Sudahkah Anda melihat RANSAC (Wikipedia) ?

Ini harus baik dalam menghitung model linier yang masuk akal bahkan ketika ada banyak pencilan dan kebisingan, karena dibangun dengan asumsi bahwa hanya sebagian dari data yang benar-benar akan menjadi bagian dari mekanisme.

Anony-Mousse
sumber

ya tapi menambahkan sederhana langkah hasil re-bobot estimator (LTS) yang sama-sama kuat dan begitu jauh lebih stabil dan statistik efisien. Kenapa tidak?

user603

1

Saya menemukan regresi kesalahan dihukum paling baik. Anda juga dapat menggunakannya secara iteratif dan sampel ulang, yang tidak sangat konsisten dengan solusi. Ide dasarnya adalah untuk menambah model Anda dengan kesalahan: mana adalah vektor kesalahan yang tidak diketahui. Sekarang Anda melakukan regresi pada . Menariknya Anda tentu saja dapat menggunakan "laso leburan" untuk ini ketika Anda dapat memperkirakan kepastian pengukuran Anda di muka dan menempatkan ini sebagai bobot ke dan untuk menyelesaikan tugas baru yang sedikit berbeda $l_1$

y = A x + e

$y=Ax+e$

e

$e$

∥ y - A x - e ∥_{2}^{2} + λ ∥ e ∥_{1}

$\parallel y-Ax-e \parallel_2^2+ \lambda \parallel e \parallel_1$

W = d i a g (w_{i})

$W=diag(w_i)$

∥ y - A x - e ∥_{2}^{2} + λ ∥ W e ∥_{1}

$\parallel y-Ax-e \parallel_2^2 + \lambda \parallel W e \parallel_1$

Informasi lebih lanjut dapat ditemukan di sini: http://statweb.stanford.edu/~candes/papers/GrossErrorsSmallErrors.pdf

mojovski
sumber

Sudahkah Anda mencobanya pada contoh Glen_b (jika Anda menambahkan pencilan kedua di sebelah tempat ia meletakkannya) atau saya telah memposting?

user603

@ user603 tidak, saya hanya menerapkan ini pada kasus yang lebih praktis untuk pemodelan 3D dari gambar kamera. Itu sangat membantu. Namun, pelajaran yang dipetik adalah: Jika Anda memiliki banyak kemungkinan untuk menghilangkan outlier Anda, gunakanlah.

mojovski

Regresi linier yang cepat kuat untuk pencilan

Jawaban: