migrował z math.stackexchange .
Przetwarzam długi strumień liczb całkowitych i rozważam śledzenie kilku chwil, aby móc w przybliżeniu obliczyć różne percentyle dla strumienia bez przechowywania dużej ilości danych. Jaki jest najprostszy sposób obliczenia percentyli z kilku chwil. Czy istnieje lepsze podejście polegające na przechowywaniu tylko niewielkiej ilości danych?
Odpowiedzi:
Nie podajesz tego wprost, ale na podstawie opisu problemu wydaje się prawdopodobne, że szukasz wysoce tendencyjnego zestawu kwantyli (np. 50., 90., 95. i 99. percentyla).
W takim przypadku odniosłem duży sukces dzięki metodzie opisanej w „Efektywnym obliczeniu peryferyjnych kwantyli przez strumienie danych” autorstwa Cormode i in. Jest to szybki algorytm, który wymaga niewiele pamięci i jest łatwy do wdrożenia.
Metoda oparta jest na wcześniejszym algorytmie Greenwalda i Khanny, który utrzymuje małą próbkę strumienia wejściowego wraz z górnymi i dolnymi granicami rangi wartości w próbce. Wymaga więcej miejsca niż zbioru kilku chwil, ale znacznie lepiej będzie dokładnie opisywać interesujący obszar ogona rozkładu.
źródło
Istnieje do tego nowszy i znacznie prostszy algorytm, który zapewnia bardzo dobre oszacowania ekstremalnych kwantyli.
Zobacz https://github.com/tdunning/t-digest
źródło