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

48

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?

PeterR
źródło
4
Być może pytanie w Stackoverflow może uzyskać lepsze odpowiedzi.
2
@Sikikant:> to dość aktywny obszar badań statystycznych :) Rozwiązanie najbliższe niższym teoretycznym granicom w zakresie przechowywania obejmuje również całkiem sprytne konstrukcje prawdopodobieństwa. W sumie byłem zaskoczony, kiedy po raz pierwszy spojrzałem na to kilka miesięcy temu; jest tu więcej statystyk niż na pierwszy rzut oka.
user603,

Odpowiedzi:

6

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”.

Ian Turner
źródło
To interesujące, i gdzie mogą pojawić się porady statystyczne! Załóżmy, że mam (powiedzmy) 500 000 punktów iid i patrzę na grupy (powiedzmy) 1000 z nich i obliczam medianę każdej grupy. Teraz mam 500 median. Czy istnieje teoria, która mogłaby pozwolić mi obliczyć przedział ufności dla ogólnej mediany na podstawie tych 500 median?
PeterR
4
Tak więc, według dawno zaginionego kolegi, najlepszym podejściem wydaje się być Chiranjeeb Buragohain i Subhash Suri. Kwantyle na strumieniach. cs.ucsb.edu/~suri/psdir/ency.pdf Podoba mi się również podejście Iana, ponieważ te mediany mniejszych zbiorów danych zbiegają się do rozkładu normalnego, więc mogę tworzyć przedziały konf dla median.
PeterR
10

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.

chrisamiller
źródło
Problem z podejściem grupowania polega na tym, że nie mamy dobrej górnej granicy dla danych, a zatem punkt środkowy największego przedziału musiałby być ogromny. Potrzebowalibyśmy więc ogromnej liczby pojemników (na to za mało pamięci) lub dość szerokich pojemników (co prowadziłoby do dość niedokładnej odpowiedzi). A dane nie są bardzo rzadkie.
PeterR
Skoro interesuje Cię tylko mediana, dlaczego nie możesz poszerzyć przedziałów przy wyższych wartościach swojej zmiennej?
russellpierce
drknexus - ponieważ nie wiemy, jaki powinien być największy kosz.
PeterR
Czy masz żadnej intuicji, co zakres będzie? Jeśli masz całkowitą pewność, że ponad połowa odpowiedzi będzie poniżej liczby N, możesz ustawić swój ostatni pojemnik tak duży, jak chcesz. Może twój ostatni kosz ma wszystkie liczby większe niż 1 bilion - czy to byłby wystarczająco wysoki? Dzięki ilości pamięci w nowoczesnych systemach można przechowywać DUŻO pojemników i osiągnąć dość wysoką rozdzielczość. Jeśli chodzi o struktury danych, nie mówimy tutaj o wymyślności i intensywności pamięci.
chrisamiller
Jakaś intuicja? tak. Twoje podejście może ogólnie działać. Jednak w tym przypadku nie możemy mieć dużo pamięci / obliczeń. Jest to aplikacja sieciowa, w której urządzenie może zobaczyć dziesiątki tysięcy elementów na sekundę i ma BARDZO mało przetwarzania do tego celu. Wiem, że nie jest to idealny / typowy scenariusz, ale właśnie dlatego jest interesujący!
PeterR
9

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)

użytkownik603
źródło
8

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ą.

Robby McKilliam
źródło
2

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.

csgillespie
źródło
3
Zestaw danych jest potencjalnie zbyt duży, aby można go było odczytać w połowie ... jest w kontekście sieci, w którym urządzenie przetwarzające może zobaczyć dziesiątki tysięcy elementów na sekundę i prawdopodobnie ma wystarczającą ilość pamięci do przechowywania tylko kilkuset. Również dane zdecydowanie nie są gaussowskie. W rzeczywistości nie pasuje dobrze do żadnej z popularnych dystrybucji.
PeterR
1

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ą.

Społeczność
źródło
1
ale jak wybrać eta, a co to znaczy statystycznie? tj. jak utworzyć przedziały ufności dla mediany na podstawie tego wyniku?
PeterR
@PeterR, hej, jakie było ostateczne rozwiązanie?
Aakash Goel
1

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) ...

szewc
źródło
1

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;
        }
}
Erik Aronesty
źródło
Można to również rozszerzyć na użycie skończonej liczby pojemników dla median czasu rzeczywistego itp.
Erik Aronesty