Czy obliczyć przybliżone kwantyle dla strumienia liczb całkowitych przy użyciu momentów?

20

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?

algorithms mathematical-statistics moments

— Jerry
źródło

2

Czy wiesz coś konkretnego na temat właściwości dystrybucyjnych swojego strumienia? Na przykład, czy są, powiedzmy, pozytywne? Zobowiązany? Wszelkie inne dane, które możesz podać, będą pomocne. Chwile są dość łatwe do obliczenia i przechowywania w strumieniu. Są tu również poprzednie pytania dotyczące bezpośredniego oszacowania kwantyli ze strumienia, co brzmi jak to, co naprawdę próbujesz zrobić. Możesz je wyszukać i przejrzeć.

— kardynał

Reprezentują czasy przetwarzania, więc są dodatnie i przeważnie ściśle zgrupowane, chyba że występuje jakiś problem techniczny lub przeciążenie w systemie. Poszukam pytań kwantylowych; mogą być wystarczająco dobre. Nadal jestem ciekawy, jak przejść od momentu do obliczenia wartości związanej z dowolnym percentylem. Wiem, że przechowywanie chwil jest łatwe, nie wiem, jak z nich korzystać.

— poniedziałek

Widziałeś to pytanie ?

— kardynał

15

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.

— NPE
źródło

1

Tak, to jest naprawdę droga. w rzeczywistości łatwiej jest uzyskać oszacowanie wysokich kwantyli, zwłaszcza jeśli chcesz tolerować błąd w rankingu postaci gdzie jest całkowitą liczbą elementów, a \ epsilon> 0 $ to jakiś użytkownik zdefiniowany termin błędu

ϵ n

$\epsilon n$

n

$n$

— Suresh Venkatasubramanian

2

Istnieje do tego nowszy i znacznie prostszy algorytm, który zapewnia bardzo dobre oszacowania ekstremalnych kwantyli.

$q$

Zobacz https://github.com/tdunning/t-digest

— Ted Dunning
źródło