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

W ostatnim artykule na temat liczenia liniowego dokonaliśmy przeglądu podstawowych algorytmów obliczania i szacowania liczby unikalnych wartości w zbiorze danych. Dziś mamy kolejny algorytm probabilistyczny, który pozwala nam oszacować liczbę unikatów z przyzwoitą dokładnością i niewielkim zapotrzebowaniem na pamięć.

Min Value

W tym artykule będziemy pracować tylko z liczbami rzeczywistymi z przedziału jednostkowego (0; 1). Rozważmy zbiór liczb z tego przedziału, który jest równomiernie rozłożony, np. zbiór liczb {0,25; 0,5; 0,75}. Sąsiednie liczby są zawsze oddalone od siebie o dokładnie 0,25 (oraz od zera i jedynki). W jaki sposób pomaga nam to policzyć liczbę unikalnych elementów?

Jeśli powiem ci, że mamy taki równomiernie rozłożony zbiór liczb z przedziału jednostkowego, a te liczby mają odległość między sobą wynoszącą zaledwie 0,2 - czy możesz obliczyć, ile elementów ma taki zbiór? Oczywiście jest to zbiór {0,2; 0,4; 0,6; 0,8}, którego liczność jest równa cztery. Jeśli jako dane wejściowe mamy równomiernie rozłożone liczby z przedziału jednostkowego i jeśli znamy odległość między sąsiednimi liczbami, możemy łatwo obliczyć liczbę elementów.

Odległość między sąsiednimi liczbami jest równa minimalnemu elementowi zbioru - odległość między sąsiednimi elementami zbioru {0,25; 0,5; 0,75} wynosi 0,25 itd. Obliczając liczbę elementów równomiernie rozłożonych liczb, musimy po prostu w jakiś sposób znaleźć minimalny element. Następnie możemy obliczyć liczbę elementów p za pomocą prostego wzoru:

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

gdzie m jest pierwiastkiem minimalnym.

I znowu będziemy hashować...

No tak, ale jak tego użyć, jeśli na wejściu mamy jakieś ciągi lub inne wartości, które nie spełniają dokładnie warunku równomiernego rozkładu w przedziale jednostkowym? Ponownie z pomocą przyjdzie stara dobra funkcja haszująca, która dla dowolnego wejścia może zwrócić liczbę wymierną z przedziału jednostkowego. Łatwo będzie skonstruować taką funkcję haszującą.

Dałoby nam to liczby wymierne z danych, ale jak sprawić, by liczby te były równomiernie rozłożone? Nie możemy tego zrobić, ale możemy sobie pomóc na inne sposoby. W rzeczywistości funkcja skrótu zachowuje się raczej "losowo" z naszego punktu widzenia. Dla bardzo podobnych słów, takich jak "hello", "ahok" i "ahol", funkcja skrótu prawdopodobnie zwróci bardzo różne sumy kontrolne. Innymi słowy, jeśli haszujemy tysiąc różnych wartości w przedziale jednostkowym, jest bardzo mało prawdopodobne, że znacząca większość liczb będzie mniejsza niż na przykład połowa. I odwrotnie, jest bardzo prawdopodobne, że liczby te będą rozłożone mniej lub bardziej regularnie. Im więcej danych zbierzemy, tym bardziej regularny będzie rozkład.

Z tego pomysłu otrzymujemy prosty algorytm: przechodzimy przez dane wejściowe, hashujemy każdy element do przedziału jednostkowego i zapamiętujemy minimalny element. Szacujemy liczbę unikalnych elementów za pomocą 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 liczbę dziesiętną z przedziału (0, 1>). Funkcja count_unique_using_minimum najpierw konwertuje wszystkie wartości wejściowe na tę liczbę, znajduje minimum i zwraca 1 / minimum - 1. Zwróć uwagę, że nie ma znaczenia, ile identycznych wartości znajduje się w zbiorze danych - dla dwóch identycznych wartości funkcja hash zwraca tę samą liczbę wymierną, co nie wpływa na wynikowe minimum. Dlatego używamy tego algorytmu do liczenia liczby unikalnych elementów.

Jakie są wyniki? (W każdym wierszu znajduje się szacunkowa kardynalność, ale poprawna kardynalność wynosi 10 000).

5957 16384 13107 9362 65536 8192 21845 13107 21845 8192

Cóż, niewiele, prawda? Algorytm przeszedł przez dziesięć różnych zestawów identyfikatorów, każdy z dziesięcioma tysiącami unikalnych wartości. Tak więc obliczone szacunki są w większości dalekie od prawdy. Gdybyśmy je uśrednili, otrzymalibyśmy wartość 18 352. Z drugiej strony, weźmy pod uwagę zapotrzebowanie na pamięć - jest ono stałe! Aby znaleźć minimum, wystarczy zawsze przechowywać w pamięci jedną zmienną do przechowywania bieżącego minimum i to wszystko. Więc tak, szacowanie jest do bani, ale z drugiej strony prawie nic nie kosztuje.

Poprawa

Widzimy, że algorytm jest w większości niestabilny - raz zwraca całkiem dobre oszacowanie (9362), drugim razem zwraca oszacowanie, które jest całkowicie błędne (65536). Jak się z tego wydostać? Możemy pomóc, dzieląc dane wejściowe na kilka części i licząc liczbę unikalnych elementów dla każdej części, a na koniec wszystko ładnie uśredniając. Możemy zdecydować się na pierwszy znak w naszym id. Będziemy więc liczyć liczbę unikatów osobno dla identyfikatorów zaczynających się na literę "a", następnie dla tych zaczynających 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 dotyczą funkcji count_unique_using_minimum. W zmiennej min_values przechowujemy minima dla każdej grupy. Na koniec sumujemy wszystkie minima i dzielimy je przez liczbę wszystkich przechowywanych wartości - otrzymujemy średnie minimum. Używamy wyrażenia 1/average_minimum, aby znaleźć średnią liczbę unikalnych wartości w każdej grupie - więc mnożymy tę wartość przez liczbę grup, aby uzyskać szacunkową liczbę unikalnych wartości w przekazanym zbiorze danych. Jak działa ta zmodyfikowana procedura?

11312 7504 10560 8160 9344 12688 10976 11616 16240 6832

Cóż, nadal nie jest dobrze, ale z pewnością jest lepiej. Algorytm jest bardziej stabilny. Możemy spróbować zmodyfikować funkcję tak, aby grupy nie były tworzone przez pierwszy znak, ale np. przez dwa pierwsze znaki id, czyli np. tak:

first_char = str(item)[0:2] # ToDo: wybierz lepszą nazwę dla zmiennej

Wyniki byłyby wtedy następujące:

9728 9728 9984 10240 8960 10752 9728 9472 11264 9472

Nie jest źle, prawda? Jeśli nadal spróbujemy sto tysięcy unikalnych wartości, pierwsze dwa znaki i n = 24, otrzymamy następujące wyniki:

103936 110080 102656 101120 101376 108288 97536 97024 107776 92416

Nieźle. Ale nadal istnieją lepsze algorytmy, nie martw się.

A jaki jest ślad pamięciowy? Musimy zachować minimum dla każdej grupy, nic więcej. Jeśli nasze identyfikatory są w formacie szesnastkowym, oznacza to, że musimy zapamiętać co najwyżej ^16x minimum, gdzie x to liczba znaków składających się na klucz grupy. Jedno minimum to jedna liczba wymierna, tj. jakiś typ liczby podwójnej lub zmiennoprzecinkowej.

Ostatnia uwaga: mogliśmy sobie pozwolić na podzielenie danych wejściowych na kilka grup, ponieważ mieliśmy identyfikatory na danych wejściowych, które zachowywały się jak losowy ciąg znaków. Gdybyśmy nie mieli losowego ciągu na wejściu, ale dane w określonym formacie, musielibyśmy dokonać podziału w inny sposób. Na przykład, jeśli każdy identyfikator zaczynałby się od prefiksu userid-, to grupowanie według pierwszego znaku prawdopodobnie nie działałoby zbyt dobrze, prawda?