Min Value: cum estimăm numărul de valori unice

În articolul precedent despre Linear Counting am discutat algoritmii de bază pentru calculul și estimarea numărului de valori unice dintr-un set de date. Astăzi ne așteaptă un alt algoritm probabilistic, care permite să estimăm numărul de valori unice cu o precizie rezonabilă și cu cerințe mici de memorie.

Min Value

În acest articol vom lucra doar cu numere reale din intervalul unitate (0, 1). Să ne imaginăm o mulțime de numere din acest interval, repartizate uniform, de exemplu mulțimea numerelor {0,25; 0,5; 0,75}. Numerele vecine se află întotdeauna la distanța exactă de 0,25 unul de altul (și de zero, și de unu). Cum ne ajută asta să calculăm numărul de elemente unice?

Dacă îți spun că avem o astfel de mulțime de numere din intervalul unitate, repartizate uniform, iar distanța dintre numerele vecine este exact 0,2 – poți calcula câte elemente are mulțimea? Desigur, este mulțimea {0,2; 0,4; 0,6; 0,8}, al cărei cardinal este egal cu patru. Dacă avem la intrare numere repartizate uniform în intervalul unitate și cunoaștem distanța dintre numerele vecine, putem calcula ușor numărul de elemente.

Distanța dintre numerele vecine este egală cu elementul minim al mulțimii – distanța dintre elementele vecine ale mulțimii {0,25; 0,5; 0,75} este 0,25 etc. Pentru a calcula numărul de elemente ale unor numere repartizate uniform, ne ajunge să aflăm cumva elementul minim. Apoi putem calcula numărul de elemente p cu o formulă simplă:

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

unde m este elementul minim.

Și iar vom folosi hash…

Numai că, cum folosim asta dacă la intrare avem șiruri de caractere sau alte valori care nu îndeplinesc tocmai condiția repartizării uniforme în intervalul unitate? Ne ajutăm din nou de bătrâna și bună funcție hash, care ne poate returna, pentru orice intrare, un număr rațional din intervalul unitate. O astfel de funcție hash se construiește ușor.

Astfel am obține din date numere raționale, dar cum facem ca aceste numere să fie repartizate uniform? Asta nu se mai poate, dar ne putem ajuta altfel. Funcția hash se comportă, din punctul nostru de vedere, destul de „aleatoriu”. Pentru cuvinte foarte asemănătoare, precum „ahoj”, „ahok” și „ahol”, funcția hash ne va returna probabil valori hash foarte diferite. Cu alte cuvinte: dacă aplicăm funcția hash pe o mie de valori diferite, cu rezultate în intervalul unitate, este foarte improbabil ca marea majoritate a numerelor să fie, de exemplu, mai mici decât o jumătate. În schimb, este foarte probabil ca aceste numere să fie repartizate mai mult sau mai puțin regulat. Cu cât trecem mai multe date prin funcția hash, cu atât repartiția va fi mai regulată.

Din această idee obținem un algoritm simplu: parcurgem datele de intrare, transformăm fiecare element cu funcția hash într-un număr din intervalul unitate și memorăm elementul minim. Numărul de elemente unice îl estimăm după formula anterioară. Implementarea în Python:

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)

Funcția unit_interval_hash ne returnează un număr zecimal din intervalul (0, 1]. Funcția count_unique_using_minimum convertește mai întâi toate valorile de intrare tocmai în acest număr, află minimul și returnează 1 / minimum - 1. Observă că nu contează deloc câte valori identice sunt în setul de date – pentru două valori identice funcția hash ne returnează același număr rațional, ceea ce nu influențează în niciun fel minimul rezultat. De aceea, cu acest algoritm numărăm elementele unice.

Care sunt rezultatele? (Pe fiecare rând se află cardinalitatea estimată; cardinalitatea corectă este 10.000.)

Ei bine, nimic special, nu? Algoritmul a parcurs zece seturi diferite de ID-uri, în care erau de fiecare dată zece mii de valori unice. Estimările calculate sunt, în mare parte, destul de departe. Dacă am face media lor, am ajunge la valoarea 18.352. Tot destul de departe, dar, pe de altă parte, uită-te la cerințele de memorie – sunt constante! Ca să găsești minimul, îți ajunge să păstrezi în memorie o singură variabilă, în care stochezi minimul curent, și atât. Deci da, estimarea e slabă, dar în schimb nu costă aproape nimic.

Îmbunătățim

Vedem că algoritmul este, mai ales, instabil – o dată ne returnează o estimare destul de bună (9362), altă dată o estimare complet greșită (65536). Cum scăpăm? Ne putem ajuta împărțind datele de intrare în mai multe părți, calculând numărul de elemente unice pentru fiecare parte și, la final, făcând frumos media. Am putea decide după primul caracter din ID. Astfel calculăm separat numărul de valori unice pentru ID-urile care încep cu litera „a”, apoi pentru cele care încep cu litera „b” etc. Codul:

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)

Modificările sunt în funcția count_unique_using_minimum. În variabila min_values păstrăm minimele pentru fiecare grup. La final adunăm toate minimele și le împărțim la numărul tuturor valorilor stocate – obținem minimul mediu. Cu expresia 1/average_minimum aflăm care este numărul mediu de valori unice din fiecare grup – această valoare o înmulțim apoi cu numărul de grupuri și obținem numărul estimat de valori unice din setul de date primit. Și cum funcționează acest procedeu modificat?

Ei bine, tot nu e bine, dar sigur e mai bine. Algoritmul este mai stabil. Putem încerca să modificăm funcția astfel încât grupurile să nu se formeze după primul caracter, ci, de exemplu, după primele două caractere ale ID-ului, adică așa:

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

Rezultatele ar fi atunci acestea:

Hmmm, asta nu mai e chiar rău, nu? Dacă încercăm în plus o sută de mii de valori unice, primele două caractere și n = 24, obținem aceste rezultate:

E destul de acceptabil. Dar tot există algoritmi mai buni, nu te teme.

Și cât de mare e consumul de memorie? Trebuie să păstrăm minimul pentru fiecare grup, nimic mai mult. Dacă avem ID-uri în format hexazecimal, înseamnă că trebuie să ținem minte cel mult 16^x minime, unde x este numărul de caractere din care formăm cheia grupului. Un minim este un număr rațional, adică un tip double sau float.

O observație la final: împărțirea intrării în mai multe grupuri ne-am putut-o permite pentru că aveam la intrare ID-uri care se comportau ca un șir aleatoriu. Dacă la intrare nu am avea un șir aleatoriu, ci date într-un anumit format, ar trebui să facem împărțirea altfel. Dacă, de exemplu, fiecare ID ar începe cu prefixul userid-, atunci împărțirea în grupuri după primul caracter n-ar prea funcționa, nu-i așa.

Capitole: Linear Counting, Min Value, LogLog, HyperLogLog

« Anterior: Numărul de valori unice

Următor: LogLog »