Min Value: jak oszacować liczbę unikalnych wartości

4. 10. 2022

Kapitoly: Linear Counting, Min Value, LogLog, HyperLogLog

W poprzednim artykule o Linear Counting omówiliśmy podstawowe algorytmy do obliczania i szacowania liczby unikalnych wartości w jakimś zbiorze danych. Dziś czeka nas kolejny algorytm probabilistyczny, który pozwala z przyzwoitą dokładnością i przy małym zużyciu pamięci oszacować liczbę unikalnych wartości.

Min Value

W artykule będziemy pracować wyłącznie z liczbami rzeczywistymi z przedziału jednostkowego (0; 1). Wyobraźmy sobie zbiór liczb z tego przedziału, które są rozmieszczone równomiernie, np. zbiór liczb {0,25; 0,5; 0,75}. Sąsiednie liczby są zawsze od siebie (i od zera, i od jedynki) oddalone dokładnie o 0,25. Jak nam to pomoże policzyć unikalne elementy?

Jeśli powiem ci, że mamy taki równomiernie rozmieszczony zbiór liczb z przedziału jednostkowego, a odległość między sąsiednimi liczbami wynosi dokładnie 0,2 — obliczysz, ile elementów ma taki zbiór? Oczywiście chodzi o zbiór {0,2; 0,4; 0,6; 0,8}, którego moc (liczba elementów) jest równa czterem. Jeśli na wejściu mamy równomiernie rozmieszczone liczby z przedziału jednostkowego i znamy odległość sąsiednich liczb, łatwo obliczymy liczbę elementów.

Przy tym odległość między sąsiednimi liczbami jest równa najmniejszemu elementowi zbioru — odległość sąsiednich elementów zbioru {0,25; 0,5; 0,75} wynosi 0,25 itd. Przy obliczaniu liczby równomiernie rozmieszczonych liczb wystarczy nam więc jakoś znaleźć najmniejszy element. Potem możemy obliczyć liczbę elementów p prostym wzorem:

$$\Large p=\frac{1}{m}-1$$

gdzie m jest tym najmniejszym elementem.

I znowu będziemy haszować…

No tak, tylko jak to wykorzystać, jeśli na wejściu mamy jakieś napisy albo inne wartości, które akurat nie spełniają warunku równomiernego rozmieszczenia w przedziale jednostkowym? Znowu pomożemy sobie starą dobrą funkcją haszującą, która dla dowolnego wejścia może nam zwrócić liczbę wymierną z przedziału jednostkowego. Zbudowanie takiej funkcji haszującej będzie łatwe.

W ten sposób dostalibyśmy z danych liczby wymierne, ale jak sprawić, żeby te liczby były rozmieszczone równomiernie? To się już co prawda nie uda, ale możemy sobie pomóc inaczej. Funkcja haszująca zachowuje się bowiem z naszego punktu widzenia dość „losowo”. Dla bardzo podobnych słów, takich jak „abc”, „abd” i „abe”, funkcja haszująca najprawdopodobniej zwróci bardzo różne hasze. Innymi słowy: jeśli zahaszujemy tysiąc różnych wartości do przedziału jednostkowego, jest bardzo mało prawdopodobne, żeby zdecydowana większość liczb była na przykład mniejsza niż jedna druga. Przeciwnie, jest bardzo prawdopodobne, że te liczby będą rozmieszczone mniej więcej regularnie. Im więcej danych zahaszujemy, tym to rozmieszczenie będzie bardziej regularne.

Z tej myśli dostajemy prosty algorytm: przejdziemy przez dane wejściowe, każdy element zahaszujemy do przedziału jednostkowego i zapamiętamy najmniejszy element. Liczbę unikalnych elementów oszacujemy według poprzedniego wzoru. Implementacja w Pythonie:

from uuid import uuid4

def nhash(item, n):
    return hash(item) % (2 ** n)

def unit_interval_hash(item, n):
    integer_hash = nhash(item, n) + 1
    return integer_hash / float(2 ** n)

def count_unique_using_minimum(values, n):
    numbers_from_unit_interval = (unit_interval_hash(item, n) for item in values)
    minimum = min(numbers_from_unit_interval)
    return int(1 / minimum) - 1

for _ in xrange(10):
    print count_unique_using_minimum((uuid4() for _ in xrange(10000)), 16)

Funkcja unit_interval_hash zwraca nam liczbę zmiennoprzecinkową z przedziału (0, 1>. Funkcja count_unique_using_minimum najpierw zamienia wszystkie wartości wejściowe właśnie na taką liczbę, znajduje minimum i zwraca 1 / minimum - 1. Zauważ, że zupełnie nie ma znaczenia, ile jest w zbiorze danych takich samych wartości — dla dwóch takich samych wartości funkcja haszująca zwróci tę samą liczbę wymierną, co w żaden sposób nie wpłynie na wynikowe minimum. Dlatego tym algorytmem policzymy liczbę unikalnych elementów.

Jakie są wyniki? (W każdym wierszu jest oszacowana liczba unikalnych wartości, a prawidłowa wynosi 10 000.)

No, nic specjalnego, prawda? Algorytm przeszedł dziesięć różnych zestawów identyfikatorów, w których było zawsze dziesięć tysięcy unikalnych wartości. Obliczone oszacowania są więc przeważnie mocno chybione. Gdybyśmy je uśrednili, doszlibyśmy do wartości 18 352. Nadal daleko od prawdy, ale z drugiej strony weź pod uwagę zużycie pamięci — jest stałe! Żeby znaleźć minimum, wystarczy ci trzymać w pamięci jedną zmienną, w której przechowujesz aktualne minimum, i to wszystko. Więc tak, oszacowanie do niczego, ale za to prawie nic nie kosztuje.

Ulepszamy

Widzimy, że algorytm jest przede wszystkim niestabilny — raz zwróci całkiem dobre oszacowanie (9362), innym razem oszacowanie zupełnie chybione (65536). Jak z tego wybrnąć? Możemy sobie pomóc tym, że podzielimy dane wejściowe na kilka części, policzymy liczbę unikalnych elementów dla każdej części, a na koniec wszystko ładnie uśrednimy. O podziale moglibyśmy decydować według pierwszego znaku naszego identyfikatora. Policzymy więc osobno liczbę unikalnych wartości dla identyfikatorów zaczynających się na literę „a”, potem dla tych, które zaczynają się na literę „b”, itd. Kod:

from uuid import uuid4

def nhash(item, n):
    return hash(item) % (2 ** n)

def unit_interval_hash(item, n):
    integer_hash = nhash(item, n) + 1
    return integer_hash / float(2 ** n)

def count_unique_using_minimum(values, n):
    min_values = {}
    for item in values:
        first_char = str(item)[0]
        hashed_value = unit_interval_hash(item, n)
        min_values[first_char] = min(min_values.get(first_char, 1), hashed_value)
    average_minimum = sum(min_values.values()) / len(min_values)
    return (int(1 / average_minimum) - 1) * len(min_values)

for _ in xrange(10):
    print count_unique_using_minimum((uuid4() for _ in xrange(10000)), 16)

Zmiany są w funkcji count_unique_using_minimum. W zmiennej min_values przechowujemy minima dla każdej grupy. Na końcu sumujemy wszystkie minima i dzielimy je przez liczbę wszystkich zapisanych wartości — dostajemy średnie minimum. Wyrażeniem 1/average_minimum sprawdzamy, jaka jest średnia liczba unikalnych wartości w każdej grupie — tę wartość mnożymy jeszcze przez liczbę grup i dostajemy oszacowaną liczbę unikalnych wartości w przekazanym zbiorze danych. A jak działa to zmodyfikowane podejście?

No, wciąż nie jest dobrze, ale na pewno lepiej. Algorytm jest stabilniejszy. Możemy spróbować zmienić funkcję tak, żeby grupy nie tworzyły się według pierwszego znaku, ale na przykład według dwóch pierwszych znaków identyfikatora, tzn. tak:

first_char = str(item)[0:2] # ToDo: choose better name for variable

Wyniki byłyby wtedy takie:

Nooo, to już nie jest całkiem źle, nie? Jeśli spróbujemy jeszcze sto tysięcy unikalnych wartości, dwa pierwsze znaki i n = 24, dostaniemy takie wyniki:

Całkiem znośnie. Ale wciąż istnieją lepsze algorytmy, bez obaw.

A jakie jest zużycie pamięci? Musimy przechowywać minimum dla każdej grupy, nic więcej. Jeśli mamy identyfikatory w formacie szesnastkowym, oznacza to, że musimy pamiętać co najwyżej 16^x minimów, gdzie x jest liczbą znaków, z których tworzymy klucz grupy. Jedno minimum to jedna liczba wymierna, tzn. jakiś typ double albo float.

Uwaga na koniec: na podział wejścia na kilka grup mogliśmy sobie pozwolić dlatego, że na wejściu mieliśmy identyfikatory, które zachowywały się jak losowy napis. Gdybyśmy na wejściu nie mieli losowego napisu, ale jakieś dane w określonym formacie, musielibyśmy podział zrobić inaczej. Gdyby na przykład każdy identyfikator zaczynał się od prefiksu userid-, to podział na grupy według pierwszego znaku raczej by się nie sprawdził, no nie?

« Poprzedni: Szacowanie liczby unikalnych wartości

Dalszy: LogLog »