Apa algoritma yang baik untuk memperkirakan median dari set data baca-sekali yang besar?

48

Saya mencari algoritme yang baik (yang berarti perhitungan minimal, persyaratan penyimpanan minimal) untuk memperkirakan median kumpulan data yang terlalu besar untuk disimpan, sehingga setiap nilai hanya dapat dibaca satu kali (kecuali jika Anda secara eksplisit menyimpan nilai itu). Tidak ada batasan pada data yang dapat diasumsikan.

Perkiraannya baik-baik saja, asal akurasinya diketahui.

Ada petunjuk?

PeterR
sumber
4
Mungkin, bertanya di Stackoverflow mungkin mendapatkan jawaban yang lebih baik.
2
@ Srikant:> ini adalah area penelitian statistik yang cukup aktif :) Solusi yang paling dekat dengan batas teoretis yang lebih rendah dalam hal penyimpanan melibatkan beberapa konstruk probabilitas yang cukup pintar juga. Secara keseluruhan, saya terkejut ketika saya pertama kali melihatnya beberapa bulan yang lalu; ada lebih banyak statistik di sini daripada yang terlihat.
user603

Jawaban:

6

Bisakah Anda mengelompokkan kumpulan data ke dalam kumpulan data yang jauh lebih kecil (katakanlah 100 atau 1000 atau 10.000 poin data) Jika Anda kemudian menghitung median masing-masing kelompok. Jika Anda melakukan ini dengan set data yang cukup, Anda dapat memplot sesuatu seperti rata-rata hasil dari masing-masing set yang lebih kecil dan ini, dengan menjalankan set data yang lebih kecil, konvergen ke solusi 'rata-rata'.

Ian Turner
sumber
Ini menarik, dan di mana beberapa saran statistik bisa masuk! Anggaplah secara total saya mendapatkan (katakanlah) 500.000 poin awal dan saya melihat kelompok (katakanlah) 1.000 di antaranya, dan menghitung median masing-masing kelompok. Sekarang saya punya 500 median. Adakah teori yang memungkinkan saya menghitung interval kepercayaan untuk median keseluruhan berdasarkan 500 median ini?
PeterR
4
Jadi, menurut seorang kolega yang telah lama hilang, pendekatan terbaik tampaknya adalah Chiranjeeb Buragohain dan Subhash Suri. Kuantil pada Streaming. cs.ucsb.edu/~suri/psdir/ency.pdf Saya juga menyukai pendekatan Ian, karena median kumpulan data yang lebih kecil ini akan menyatu ke distribusi normal, dan dengan demikian saya dapat membentuk interval conf untuk median.
PeterR
10

Bagaimana dengan sesuatu seperti prosedur binning? Asumsikan (untuk tujuan ilustrasi) bahwa Anda tahu bahwa nilainya antara 1 dan 1 juta. Siapkan N nampan, berukuran S. Jadi, jika S = 10.000, Anda akan memiliki 100 nampan, sesuai dengan nilai [1: 10000, 10001: 20000, ..., 990001: 1000000]

Kemudian, selesaikan nilainya. Alih-alih menyimpan nilai masing-masing, hanya menambah penghitung di tempat sampah yang sesuai. Menggunakan titik tengah dari masing-masing nampan sebagai perkiraan, Anda dapat membuat perkiraan median yang masuk akal. Anda dapat mengatur skala ini menjadi resolusi halus atau kasar seperti yang Anda inginkan dengan mengubah ukuran nampan. Anda hanya dibatasi oleh berapa banyak memori yang Anda miliki.

Karena Anda tidak tahu seberapa besar nilainya, dapatkan saja ukuran nampan yang cukup besar sehingga Anda tidak akan kehabisan memori, menggunakan beberapa perhitungan back-of-the-envelope yang cepat. Anda juga dapat menyimpan nampan secara jarang, sehingga Anda hanya menambahkan nampan jika nilainya mengandung.

Sunting:

Tautan ryfm memberikan contoh melakukan hal ini, dengan langkah tambahan menggunakan persentase kumulatif untuk lebih akurat memperkirakan titik dalam nampan median, daripada hanya menggunakan titik tengah. Ini peningkatan yang bagus.

chrisamiller
sumber
Masalah dengan pendekatan binning adalah bahwa kita tidak memiliki batas atas yang baik untuk data, sehingga titik tengah untuk bin terbesar harus besar. Jadi, kita membutuhkan sejumlah besar nampan (tidak cukup memori untuk itu), atau memiliki nampan yang cukup lebar (yang kemudian akan mengarah ke jawaban yang cukup tidak akurat.) Dan datanya tidak terlalu jarang.
PeterR
Karena Anda hanya tertarik pada median mengapa Anda tidak dapat membuat tempat sampah lebih luas dengan nilai variabel yang lebih tinggi?
russellpierce
drknexus - karena kita tidak tahu apa yang seharusnya menjadi bin terbesar.
PeterR
Apakah Anda memiliki setiap intuisi seperti apa rentang akan? Jika Anda cukup yakin bahwa lebih dari setengah jawaban akan berada di bawah angka N, maka Anda dapat membuat nampan terakhir Anda sebesar yang Anda inginkan. Mungkin nampan terakhir Anda semua jumlahnya lebih dari 1 triliun - apakah itu cukup tinggi? Dengan jumlah memori dalam sistem modern, Anda dapat menyimpan BANYAK sampah dan mencapai resolusi yang cukup tinggi. Dalam hal struktur data, kita tidak membicarakan sesuatu yang mewah dan intensif memori di sini.
chrisamiller
Ada intuisi? Iya. Dan pendekatan Anda bisa bekerja secara umum. Namun, dalam hal ini kita tidak dapat memiliki banyak memori / perhitungan. Ada dalam aplikasi jaringan di mana perangkat dapat melihat puluhan ribu item per detik, dan memiliki SANGAT sedikit pemrosesan yang tersisa untuk tujuan ini. Bukan skenario ideal / tipikal, saya tahu, tapi itulah yang membuatnya menarik!
PeterR
9

HAI(n)

pengguna603
sumber
8

The algoritma Rivest-Tarjan-Seleksi (kadang-kadang juga disebut median-median dari-algoritma) akan membiarkan Anda menghitung elemen median dalam linear-waktu tanpa penyortiran apapun. Untuk set data besar, ini bisa sedikit lebih cepat daripada penyortiran log-linear. Namun, itu tidak akan menyelesaikan masalah penyimpanan memori Anda.

Robby McKilliam
sumber
2

Saya tidak pernah melakukan ini, jadi ini hanya saran.

Saya melihat dua kemungkinan (lainnya).

Setengah data

  1. Muat dalam setengah data dan urutkan
  2. Selanjutnya baca nilai-nilai yang tersisa dan bandingkan dengan daftar yang diurutkan.
    1. Jika nilai baru lebih besar, buang saja.
    2. selain itu masukkan nilai dalam daftar yang disortir dan hapus nilai terbesar dari daftar itu.

Distribusi pengambilan sampel

Pilihan lain, adalah menggunakan perkiraan yang melibatkan distribusi sampling. Jika data Anda Normal, maka kesalahan standar untuk n sedang adalah:

1.253 * sd / sqrt (n)

Untuk menentukan ukuran n yang Anda senangi, saya menjalankan simulasi Monte-Carlo cepat di R

n = 10000
outside.ci.uni = 0
outside.ci.nor = 0
N=1000
for(i in 1:N){
  #Theoretical median is 0
  uni = runif(n, -10, 10)
  nor  = rnorm(n, 0, 10)

  if(abs(median(uni)) > 1.96*1.253*sd(uni)/sqrt(n))
    outside.ci.uni = outside.ci.uni + 1

  if(abs(median(nor)) > 1.96*1.253*sd(nor)/sqrt(n))
    outside.ci.nor = outside.ci.nor + 1
}

outside.ci.uni/N
outside.ci.nor/N

Untuk n = 10.000, 15% dari estimasi median seragam berada di luar CI.

csgillespie
sumber
3
Kumpulan data berpotensi terlalu besar untuk dibaca dalam setengahnya ... itu dalam konteks jaringan di mana perangkat yang melakukan pemrosesan dapat melihat puluhan ribu item per detik, dan mungkin memiliki memori yang cukup untuk menyimpan hanya beberapa ratus. Juga datanya jelas bukan Gaussian. Sebenarnya itu tidak cocok dengan distribusi umum mana pun.
PeterR
1

Berikut jawaban atas pertanyaan yang diajukan pada stackoverflow: https://stackoverflow.com/questions/1058813/on-line-iterator-algorithms-for-estimating-statistical-median-mode-skewness/2144754#2144754

Pembaruan berulang median + = eta * sgn (sampel - median) terdengar seperti itu bisa menjadi cara untuk pergi.

Komunitas
sumber
1
tetapi kemudian bagaimana memilih eta, dan apa artinya ini secara statistik? yaitu bagaimana membentuk interval kepercayaan untuk median dari hasil ini?
PeterR
@ PeterR, hei, apa solusi terakhir yang Anda gunakan?
Aakash Goel
1

The Algoritma Remedian (PDF) memberikan satu-pass estimasi median dengan kebutuhan penyimpanan rendah dan akurasi didefinisikan dengan baik.

Penyembuhan dengan basis b dilanjutkan dengan menghitung median kelompok-kelompok pengamatan b, dan kemudian median median-median ini, hingga hanya satu estimasi yang tersisa. Metode ini hanya membutuhkan k array ukuran b (di mana n = b ^ k) ...

pembuat sepatu
sumber
1

Jika nilai yang Anda gunakan berada dalam kisaran tertentu, katakan 1 hingga 100000, Anda dapat menghitung median dengan efisien pada nilai yang sangat besar (misalnya, triliunan entri), dengan ember bilangan bulat (kode ini diambil dari BSD yang dilisensikan dengan -utils / sam-stats.cpp)

class ibucket {
public:
    int tot;
    vector<int> dat;
    ibucket(int max) {dat.resize(max+1);tot=0;}
    int size() const {return tot;};

    int operator[] (int n) const {
        assert(n < size());
        int i;
        for (i=0;i<dat.size();++i) {
            if (n < dat[i]) {
                return i;
            }
            n-=dat[i];
        }
    }

    void push(int v) {
        assert(v<dat.size());
        ++dat[v];
        ++tot;
    }
};


template <class vtype>
double quantile(const vtype &vec, double p) {
        int l = vec.size();
        if (!l) return 0;
        double t = ((double)l-1)*p;
        int it = (int) t;
        int v=vec[it];
        if (t > (double)it) {
                return (v + (t-it) * (vec[it+1] - v));
        } else {
                return v;
        }
}
Erik Aronesty
sumber
Juga, ini dapat diperluas untuk menggunakan jumlah sampah yang terbatas untuk median real-time, dll.
Erik Aronesty