Saya perlu menghitung kuartil (Q1, median dan Q3) secara real-time pada set besar data tanpa menyimpan pengamatan. Saya pertama kali mencoba algoritma P square (Jain / Chlamtac) tapi saya tidak puas dengan itu (penggunaan cpu terlalu banyak dan tidak yakin dengan presisi setidaknya pada dataset saya).
Saya menggunakan sekarang algoritma FAME ( Feldman / Shavitt ) untuk memperkirakan median dengan cepat dan mencoba untuk menurunkan algoritma untuk menghitung juga Q1 dan Q3:
M = Q1 = Q3 = first data value
step =step_Q1 = step_Q3 = a small value
for each new data :
# update median M
if M > data:
M = M - step
elif M < data:
M = M + step
if abs(data-M) < step:
step = step /2
# estimate Q1 using M
if data < M:
if Q1 > data:
Q1 = Q1 - step_Q1
elif Q1 < data:
Q1 = Q1 + step_Q1
if abs(data - Q1) < step_Q1:
step_Q1 = step_Q1/2
# estimate Q3 using M
elif data > M:
if Q3 > data:
Q3 = Q3 - step_Q3
elif Q3 < data:
Q3 = Q3 + step_Q3
if abs(data-Q3) < step_Q3:
step_Q3 = step_Q3 /2
Untuk melanjutkan, itu hanya menggunakan median M yang diperoleh dengan cepat untuk membagi kumpulan data menjadi dua dan kemudian menggunakan kembali algoritma yang sama untuk Q1 dan Q3.
Ini tampaknya berfungsi entah bagaimana tetapi saya tidak dapat menunjukkan (saya bukan ahli matematika). Apakah itu cacat? Saya akan sangat menghargai saran atau teknik lain yang sesuai dengan masalah.
Terima kasih banyak atas bantuan Anda !
==== EDIT =====
Bagi mereka yang tertarik dengan pertanyaan seperti itu, setelah beberapa minggu, saya akhirnya berakhir hanya dengan menggunakan Reservoir Sampling dengan daftar nilai 100 dan itu memberikan hasil yang sangat memuaskan (bagi saya).
Jawaban:
Median adalah titik di mana 1/2 pengamatan jatuh di bawah dan 1/2 di atas. Demikian pula, perecentile ke-25 adalah median untuk data antara min dan median, dan persentil ke-75 adalah median antara median dan maks, jadi ya, saya pikir Anda berada di tanah padat menerapkan algoritma median apa pun yang Anda gunakan pertama pada seluruh data diatur untuk mempartisi itu, dan kemudian pada dua bagian yang dihasilkan.
Perbarui :
Pertanyaan tentang stackoverflow ini mengarah ke makalah ini: Raj Jain, Imrich Chlamtac: Algoritma P² untuk Perhitungan Dinamis Kuantil dan Histogram Tanpa Menyimpan Pengamatan. Komunal. ACM 28 (10): 1076-1085 (1985) yang abstraknya menunjukkan itu mungkin sangat menarik bagi Anda:
sumber
Perubahan yang sangat kecil pada metode yang Anda posting dan Anda dapat menghitung persentil sewenang-wenang, tanpa harus menghitung semua kuantil. Berikut kode Python:
dan sebuah contoh:
sumber