Jaki jest dobry algorytm do oszacowania mediany ogromnego zestawu danych do odczytu?

Szukam dobrego algorytmu (co oznacza minimalne obliczenia, minimalne wymagania dotyczące miejsca do przechowywania), aby oszacować medianę zestawu danych, który jest zbyt duży, aby go zapisać, tak aby każdą wartość można było odczytać tylko raz (chyba że jawnie zapiszesz tę wartość). Dane nie mają granic, które można założyć.

Przybliżenia są w porządku, o ile znana jest dokładność.

Jakieś wskazówki?

Czy możesz pogrupować zestaw danych w znacznie mniejsze zestawy danych (powiedzmy 100 lub 1000 lub 10 000 punktów danych) Jeśli następnie obliczysz medianę każdej z grup. Jeśli zrobiłeś to z wystarczającą liczbą zestawów danych, możesz wykreślić coś w rodzaju średniej wyników każdego z mniejszych zestawów i tego problemu, uruchamiając wystarczająco dużo mniejszych zestawów danych, aby uzyskać rozwiązanie „przeciętne”.

A może coś takiego jak procedura grupowania? Załóżmy (dla celów ilustracyjnych), że wiesz, że wartości wynoszą od 1 do 1 miliona. Skonfiguruj N pojemników o rozmiarze S. Więc jeśli S = 10000, będziesz mieć 100 pojemników, odpowiadających wartościom [1: 10000, 10001: 20000, ..., 990001: 1000000]

Następnie przejdź przez wartości. Zamiast zapisywać każdą wartość, wystarczy zwiększyć licznik w odpowiednim pojemniku. Wykorzystując punkt środkowy każdego przedziału jako oszacowanie, można dokonać rozsądnego przybliżenia mediany. Możesz skalować do tak dokładnej lub zgrubnej rozdzielczości, jak chcesz, zmieniając rozmiar pojemników. Jesteś ograniczony tylko ilością pamięci.

Ponieważ nie wiesz, jak duże mogą być Twoje wartości, po prostu wybierz rozmiar pojemnika wystarczająco duży, aby prawdopodobnie nie zabrakło pamięci, korzystając z szybkich obliczeń z tyłu koperty. Możesz również przechowywać pojemniki rzadko, tak że dodajesz kosz tylko wtedy, gdy zawiera on wartość.

Edytować:

Łącze, które zapewnia Ryfm, daje przykład tego, z dodatkowym krokiem użycia skumulowanych wartości procentowych w celu dokładniejszego oszacowania punktu w środkowym przedziale, zamiast tylko użycia punktów środkowych. To niezła poprawa.

Przekierowuję cię do mojej odpowiedzi na podobne pytanie . W skrócie, jest to algorytm „odczytu w locie” o złożoności najgorszego przypadku służący do obliczenia (dokładnej) mediany.$O(n)$

Algorytm Rivest-Tarjan-Selection (czasami nazywane także mediana-of-mediany algorytm) pozwoli Ci obliczyć medianę element w czasie liniowym bez sortowania. W przypadku dużych zestawów danych może to być nieco szybsze niż sortowanie log-liniowe. Nie rozwiąże to jednak problemu z pamięcią.

Zaimplementowałem algorytm kwadratu P do dynamicznego obliczania kwantyli i histogramów bez przechowywania obserwacji w zgrabnym module napisanym przeze mnie Pythona o nazwie LiveStats . Powinno to dość skutecznie rozwiązać Twój problem.

Nigdy nie musiałem tego robić, więc to tylko sugestia.

Widzę dwie (inne) możliwości.

Połowa danych

1. Załaduj połowę danych i posortuj
2. Następnie odczytaj pozostałe wartości i porównaj z posortowaną listą.
   1. Jeśli nowa wartość jest większa, odrzuć ją.
   2. w przeciwnym razie umieść wartość na posortowanej liście i usuń największą wartość z tej listy.

Dystrybucja próbek

Inną opcją jest użycie aproksymacji obejmującej rozkład próbkowania. Jeśli dane są normalne, błąd standardowy dla umiarkowanego n wynosi:

1.253 * sd / sqrt (n)

Aby określić rozmiar n , z którego byłbyś zadowolony, przeprowadziłem szybką symulację Monte-Carlo w 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

Dla n = 10000 15% jednolitych szacunków mediany było poza CI.

Możesz spróbować znaleźć medianę opartą na zgrupowanym rozkładzie częstotliwości, oto kilka szczegółów

Oto odpowiedź na pytanie zadane podczas stackoverflow: https://stackoverflow.com/questions/1058813/on-line-iterator-algorithms-for-estimating-statistic-median-mode-skewness/2144754#2144754

Mediana aktualizacji iteracyjnej + = eta * sgn (sample - mediana) wydaje się być dobrą drogą.

Remedian algorytm (PDF) daje jednoprzebiegowy medianę oszacowanie przy niskich wymagań magazynowania i dobrze określonej dokładności.

Środek zaradczy z bazą b przebiega przez obliczenie median z grup obserwacji b, a następnie median tych median, aż pozostanie tylko jedno oszacowanie. Ta metoda wymaga jedynie k tablic o rozmiarze b (gdzie n = b ^ k) ...

Jeśli używane wartości mieszczą się w pewnym zakresie, powiedzmy od 1 do 100000, możesz skutecznie obliczyć medianę na bardzo dużej liczbie wartości (powiedzmy, bilionach wpisów), z przedziałem liczb całkowitych (ten kod pochodzi z licencji BSD ea -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;
        }
}