Algoritma untuk secara dinamis memonitor kuantil

Saya ingin memperkirakan jumlah beberapa data. Data tersebut sangat besar sehingga tidak dapat ditampung dalam memori. Dan data tidak statis, data baru terus berdatangan. Adakah yang tahu algoritma untuk memonitor kuantil data yang diamati sejauh ini dengan memori dan komputasi yang sangat terbatas? Saya menemukan algoritma P2 berguna, tetapi tidak berfungsi dengan baik untuk data saya, yang didistribusikan dengan sangat berat.

Algoritma P2 adalah temuan yang bagus. Ia bekerja dengan membuat beberapa perkiraan kuantil, memperbaruinya secara berkala, dan menggunakan interpolasi kuadrat (bukan linier, bukan kubik) untuk memperkirakan kuantil. Para penulis mengklaim interpolasi kuadrat bekerja lebih baik di ekor daripada interpolasi linier dan kubik akan menjadi terlalu rewel dan sulit.

Anda tidak menyatakan dengan tepat bagaimana pendekatan ini gagal untuk data "ekor berat" Anda, tetapi mudah ditebak: perkiraan kuantil ekstrem untuk distribusi berekor berat akan tidak stabil hingga sejumlah besar data dikumpulkan. Tapi ini akan menjadi masalah (pada tingkat lebih rendah) bahkan jika Anda menyimpan semua data, jadi jangan berharap keajaiban!

Bagaimanapun juga, mengapa tidak menetapkan marker bantu - sebut saja mereka dan --dengan mana Anda sangat yakin quantile akan berbohong, dan simpan semua data yang terletak di antara dan ? Saat buffer Anda terisi, Anda harus memperbarui marker ini, selalu simpan . Algoritma sederhana untuk melakukan ini dapat dibuat dari kombinasi (a) estimasi P2 saat ini dari kuantil dan (b) jumlah jumlah data yang disimpan kurang dari dan jumlah data lebih besar dari . Dengan cara ini Anda dapat, dengan kepastian tinggi, memperkirakan kuantil sama baiknya jika Anda memiliki seluruh dataset yang selalu tersedia, tetapi Anda hanya membutuhkan buffer yang relatif kecil.x 6 x 0 x 6 x 0 ≤ x 6 x 0 x $x_0$$x_6$$x_0$$x_6$$x_0 \le x_6$$x_0$$x_6$

Secara khusus, saya mengusulkan struktur data untuk mempertahankan informasi parsial tentang urutan nilai data . Di sini, adalah daftar tertautn x 1 , x 2 , … , x n $(k, \mathbf{y}, n)$$n$$x_1, x_2, \ldots, x_n$$\mathbf{y}$

Dalam notasi ini menunjukkan terkecil dari nilai dibaca sejauh ini. adalah konstanta, ukuran buffer . i th n x m $x^{(n)}_{[i]}$$i^\text{th}$$n$ $x$$m$$\mathbf{y}$

Algoritma dimulai dengan mengisi dengan nilai data pertama yang ditemui dan menempatkannya dalam urutan diurutkan, terkecil hingga terbesar. Biarkan menjadi kuantil untuk diestimasi; misalnya, = 0,99. Setelah membaca ada tiga tindakan yang mungkin: m q q x n + $\mathbf{y}$$m$$q$$q$$x_{n+1}$

• Jika , tambahkan .$x_{n+1} \lt x^{(n)}_{[k+1]}$$k$

• Jika , jangan lakukan apa pun.$x_{n+1} \gt x^{(n)}_{[k+m]}$

• Jika tidak, masukkan ke .$x_{n+1}$$\mathbf{y}$

Dalam hal apa pun, kenaikan .$n$

The insert menempatkan prosedur ke dalam rangka diurutkan dan kemudian menghilangkan salah satu nilai ekstrim dalam : y $x_{n+1}$$\mathbf{y}$$\mathbf{y}$

• Jika , maka hapus dari dan increment ;x ( n ) [ k + 1 ] y$k + m/2 \lt n q$$x^{(n)}_{[k+1]}$$\mathbf{y}$$k$

• Kalau tidak, hapus dari .$x^{(n)}_{[k+m]}$$\mathbf{y}$

Asalkan cukup besar, prosedur ini akan mengurung kuantil sebenarnya dari distribusi dengan probabilitas tinggi. Pada setiap tahap dapat diperkirakan dengan cara biasa dalam hal dan , yang kemungkinan besar terletak di . (Saya percaya hanya perlu skala seperti akar kuadrat dari jumlah maksimum data ( ), tetapi saya belum melakukan analisis yang ketat untuk membuktikannya.) Bagaimanapun, algoritma akan mendeteksi apakah telah berhasil (oleh membandingkan dan ke ).n x ( n ) [ ⌊ q n ⌋ ] x ( n ) [ ⌈ q n ⌉ ] y m N k / n ( k + m ) / n $m$$n$$x^{(n)}_{[\lfloor{q n}\rfloor]}$$x^{(n)}_{[\lceil{q n}\rceil]}$$\mathbf{y}$$m$$N$$k/n$$(k+m)/n$$q$

Menguji hingga 100.000 nilai, menggunakan dan (kasus paling sulit) menunjukkan algoritma ini memiliki tingkat keberhasilan 99,5% dalam mendapatkan nilai . Untuk aliran nilai , yang akan membutuhkan buffer hanya dua juta (tetapi tiga atau empat juta akan menjadi pilihan yang lebih baik). Menggunakan daftar tertaut ganda yang diurutkan untuk buffer memerlukan = upaya sambil mengidentifikasi dan menghapus max atau min adalah operasi . Penyisipan yang relatif mahal biasanya hanya perlu dilakukan q=.5x ( n ) [ ⌊ q n ⌋ ] N=10 12 O(log($m = 2\sqrt{N}$$q=.5$$x^{(n)}_{[\lfloor{q n}\rfloor]}$$N=10^{12}$$O(\log(\sqrt{N}))$$O(\log(N))$$O(1)$$O(\sqrt{N})$waktu. Dengan demikian biaya komputasi dari algoritma ini adalah dalam waktu dan dalam penyimpanan.$O(N + \sqrt{N} \log(N)) = O(N)$$O(\sqrt{N})$

Saya pikir saran Whuber sangat bagus dan saya akan mencobanya terlebih dahulu. Namun, jika Anda benar-benar tidak dapat mengakomodasi penyimpanan atau tidak berhasil karena beberapa alasan lain, berikut adalah ide untuk generalisasi P2 yang berbeda. Ini tidak sedetail apa yang disarankan whuber - lebih seperti ide penelitian daripada sebagai solusi.$O(\sqrt N)$

Alih-alih melacak kuantil pada , p / 2 , p , ( 1 + p ) / 2 , dan 1 , seperti yang disarankan oleh algoritma P2 asli, Anda bisa melacak lebih banyak kuantil (tetapi masih berupa angka konstan). Sepertinya algoritma memungkinkan untuk itu dengan cara yang sangat mudah; yang perlu Anda lakukan adalah menghitung "bucket" yang benar untuk titik yang masuk, dan cara yang tepat untuk memperbarui kuantil (secara kuadrat menggunakan angka yang berdekatan).$0$$p/2$$p$$(1+p)/2$$1$

Katakanlah Anda melacak poin. Anda bisa mencoba melacak kuantil di 0 , p / 12 , ... , p ⋅ 11 / 12 , p , p + ( 1 - p ) / 12 , ... , p + 11 ⋅ ( 1 - p ) / 12 , 1 (memetik titik-titik secara merata di antara 0 dan p , dan antara $25$$0$$p/12$$\dotsc$$p \cdot 11/12$$p$$p + (1-p)/12$$\dotsc$$p + 11\cdot(1-p)/12$$1$$0$$p$$p$dan ), atau bahkan menggunakan 22 node Chebyshev dari bentuk p / 2 ⋅ ( 1 + cos ( 2 i - 1 ) $1$$22$ danp+(1-p)/2⋅(1+cos(2i-1)$p/2 \cdot (1 + \cos \frac{(2 i - 1)\pi}{22})$. Jikapmendekati0atau1, Anda bisa mencoba meletakkan lebih sedikit titik di sisi di mana ada massa probabilitas lebih sedikit dan lebih banyak di sisi lain.$p + (1 - p)/2 \cdot (1 + \cos \frac{(2i-1)\pi}{22})$$p$$0$$1$

Jika Anda memutuskan untuk mengejar ini, saya (dan mungkin orang lain di situs ini) akan tertarik mengetahui jika itu berhasil ...

Press et al., Numerical Recipes 8.5.2 "Estimasi single-pass dari kuantil arbitrer" hal. 435, berikan IQAgent kelas c ++ yang memperbarui cdf perkiraan piecewise-linear.

Ini dapat diadaptasi dari algoritma yang menentukan median dari dataset online. Untuk informasi lebih lanjut, lihat posting stackoverflow ini - /programming/1387497/find-median-value-from-a-growing-set

Saya akan melihat regresi kuantil. Anda dapat menggunakannya untuk menentukan estimasi parametrik dari kuantil mana pun yang ingin Anda lihat. Itu tidak membuat asumsi tentang normalitas, sehingga ia menangani heteroskedastisitas dengan cukup baik dan dapat digunakan sebagai basis bergulir. Ini pada dasarnya sebuah regresi yang dikenakan sanksi L1-Norm, jadi tidak terlalu intensif secara numerik dan ada paket R, SAS, dan SPSS yang berfitur lengkap lengkap ditambah beberapa implementasi matlab di luar sana. Inilah wiki utama dan paket R untuk info lebih lanjut.

Diedit:

Lihat crosslink exchange stack stack: Seseorang mencari beberapa makalah yang pada dasarnya menguraikan ide yang sangat sederhana hanya menggunakan jendela bergulir statistik pesanan untuk memperkirakan jumlah. Secara harfiah yang harus Anda lakukan adalah mengurutkan nilai dari terkecil ke terbesar, pilih mana yang Anda inginkan kuantil, dan pilih nilai tertinggi dalam kuantil itu. Anda jelas dapat memberikan bobot lebih untuk pengamatan terbaru jika Anda yakin mereka lebih mewakili kondisi aktual saat ini. Ini mungkin akan memberikan perkiraan kasar, tetapi itu cukup sederhana untuk dilakukan dan Anda tidak harus melalui gerakan pengangkatan berat kuantitatif. Hanya pemikiran saja.

Dimungkinkan untuk memperkirakan (dan melacak) kuantil secara on-line (yang sama berlaku untuk parameter regresi kuantil). Pada dasarnya, ini bermuara pada penurunan gradien stokastik pada fungsi check-loss yang mendefinisikan regresi-kuantil (kuantil diwakili oleh model yang hanya mengandung intersep), misalnya memperbarui parameter yang tidak diketahui saat dan ketika pengamatan tiba.

Lihat kertas Bell Labs "Estimasi Kuantitas Tambahan untuk Pelacakan Besar-besaran" ( ftp://ftp.cse.buffalo.edu/users/azhang/disc/disc01/cd1/out/papers/kdd/p516-chen.pdf )

Algoritma penting lainnya adalah M. Greenwald dan S. Khanna 2004 - Komputasi online ringkasan kuantil yang efisien-ruang.