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?
algorithms
median
large-data
PeterR
źródło
źródło
Odpowiedzi:
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”.
źródło
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.
źródło
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)
źródło
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ą.
źródło
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.
źródło
Nigdy nie musiałem tego robić, więc to tylko sugestia.
Widzę dwie (inne) możliwości.
Połowa danych
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.
Dla n = 10000 15% jednolitych szacunków mediany było poza CI.
źródło
Możesz spróbować znaleźć medianę opartą na zgrupowanym rozkładzie częstotliwości, oto kilka szczegółów
źródło
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ą.
źródło
Remedian algorytm (PDF) daje jednoprzebiegowy medianę oszacowanie przy niskich wymagań magazynowania i dobrze określonej dokładności.
źródło
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)
źródło