Min value: het aantal unieke waarden schatten

In het vorige artikel over linear counting hebben we de basisalgoritmen behandeld om het aantal unieke waarden in een dataset te berekenen en te schatten. Vandaag volgt nog een probabilistisch algoritme, waarmee je het aantal unieke waarden met een redelijke nauwkeurigheid en een laag geheugengebruik kunt schatten.

Min value

In dit artikel werken we alleen met reële getallen uit het eenheidsinterval ⟨0, 1⟩. Stel je een gelijkmatig verdeelde verzameling getallen uit dit interval voor, bijvoorbeeld de verzameling getallen {0,25; 0,5; 0,75}. Naburige getallen liggen steeds precies 0,25 van elkaar (en van nul en van één). Hoe helpt ons dat om het aantal unieke elementen te tellen?

Als ik je zeg dat we zo'n gelijkmatig verdeelde verzameling getallen uit het eenheidsinterval hebben en dat deze getallen precies 0,2 van elkaar liggen — kun je dan uitrekenen hoeveel elementen zo'n verzameling heeft? Natuurlijk, het gaat om de verzameling {0,2; 0,4; 0,6; 0,8}, waarvan de kardinaliteit vier is. Als de invoer gelijkmatig verdeelde getallen uit het eenheidsinterval zijn en we de afstand tussen naburige getallen kennen, kunnen we het aantal elementen eenvoudig uitrekenen.

De afstand tussen naburige getallen is bovendien gelijk aan het kleinste element van de verzameling — de afstand tussen naburige elementen van de verzameling {0,25; 0,5; 0,75} is 0,25 enzovoort. Om het aantal elementen van gelijkmatig verdeelde getallen te berekenen, volstaat het dus dat we op de een of andere manier het kleinste element te weten komen. Dan kunnen we het aantal elementen p berekenen met een eenvoudige formule:

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

waarbij m dat kleinste element is.

En weer gaan we hashen…

Oké, maar hoe gebruiken we dit als de invoer uit strings of andere waarden bestaat die niet toevallig gelijkmatig over het eenheidsinterval verdeeld zijn? We nemen opnieuw onze goede oude hashfunctie te hulp, die voor elke invoer een rationaal getal uit het eenheidsinterval kan teruggeven. Zo'n hashfunctie bouwen is eenvoudig.

Daarmee krijgen we uit de gegevens rationale getallen, maar hoe zorgen we dat die getallen gelijkmatig verdeeld zijn? Dat lukt niet, maar we kunnen ons op een andere manier redden. Vanuit ons gezichtspunt gedraagt een hashfunctie zich namelijk vrij “willekeurig”. Bij sterk op elkaar lijkende woorden als “hallo”, “halla” en “hallu” geeft de hashfunctie ons waarschijnlijk heel verschillende checksums terug. Met andere woorden: als we duizend verschillende waarden hashen naar het eenheidsinterval, is het erg onwaarschijnlijk dat het overgrote deel van de getallen bijvoorbeeld kleiner is dan een half. Daarentegen is het zeer waarschijnlijk dat die getallen min of meer regelmatig verdeeld zijn. Hoe meer gegevens we hashen, hoe regelmatiger die verdeling wordt.

Uit dit idee volgt een eenvoudig algoritme: we lopen de invoergegevens door, hashen elk element naar het eenheidsinterval en onthouden het kleinste element. Het aantal unieke elementen schatten we met de vorige formule. Implementatie in 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)

De functie unit_interval_hash geeft ons een decimaal getal uit het interval ⟨0, 1]. De functie count_unique_using_minimum zet eerst alle invoerwaarden om in precies zo'n getal, zoekt het minimum en geeft 1 / minimum - 1 terug. Merk op dat het helemaal niet uitmaakt hoeveel gelijke waarden er in de dataset zitten — voor twee gelijke waarden geeft de hashfunctie hetzelfde rationale getal terug, wat het uiteindelijke minimum op geen enkele manier beïnvloedt. Daarom tellen we met dit algoritme het aantal unieke elementen.

Wat zijn de resultaten? (Op elke regel staat de geschatte kardinaliteit, de juiste kardinaliteit is 10 000.)

5957
16384
13107
9362
65536
8192
21845
13107
21845
8192

Nou, niet zo geweldig, hè? Het algoritme heeft tien verschillende sets id's doorlopen, waarin telkens tienduizend unieke waarden zaten. De berekende schattingen zitten er dus meestal behoorlijk naast. Als we ze middelen, komen we uit op 18 352. Dat zit er nog steeds flink naast, maar bekijk eens het geheugengebruik — dat is constant! Om het minimum te vinden, hoef je in het geheugen alleen steeds één variabele te bewaren waarin je het huidige minimum opslaat en dat is alles. Dus ja, een rotschatting, maar het kost ook bijna niets.

Verbeteringen

We zien dat het algoritme vooral onstabiel is — de ene keer geeft het een redelijk goede schatting (9362), de andere keer een schatting die er helemaal naast zit (65536). Hoe lossen we dat op? We kunnen de invoergegevens in een aantal delen splitsen, voor elk deel het aantal unieke elementen berekenen en uiteindelijk alles mooi middelen. We zouden kunnen beslissen op basis van het eerste teken van onze id. We berekenen dan apart het aantal unieke waarden voor de id's die met de letter “a” beginnen, dan voor die met de letter “b” enzovoort. De code:

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)

De wijzigingen zitten in de functie count_unique_using_minimum. In de variabele min_values bewaren we de minima voor elke groep. Aan het einde tellen we alle minima op en delen we ze door het aantal opgeslagen waarden — zo krijgen we het gemiddelde minimum. Met de uitdrukking 1/average_minimum bepalen we wat het gemiddelde aantal unieke waarden in elke groep is — die waarde vermenigvuldigen we nog met het aantal groepen en zo krijgen we het geschatte aantal unieke waarden in de aangeboden dataset. En hoe werkt deze aangepaste werkwijze?

11312
7504
10560
8160
9344
12688
10976
11616
16240
6832

Nou, het is nog steeds niet goed, maar zeker beter. Het algoritme is stabieler. We kunnen proberen de functie zo aan te passen dat de groepen niet op basis van het eerste teken worden gevormd, maar bijvoorbeeld op basis van de eerste twee tekens van de id, dus zo:

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

De resultaten zijn dan als volgt:

9728
9728
9984
10240
8960
10752
9728
9472
11264
9472

Nou, dat is al niet slecht meer, toch? Als we het ook nog met honderdduizend unieke waarden proberen, met de eerste twee tekens en n = 24, krijgen we deze resultaten:

103936
110080
102656
101120
101376
108288
97536
97024
107776
92416

Dat gaat nog wel. Maar er bestaan nog steeds betere algoritmen, geen zorgen.

En hoe zit het met het geheugengebruik? We moeten het minimum van elke groep bewaren, niets meer. Als de id's in hexformaat zijn, betekent dat dat we maximaal 16^x minima moeten onthouden, waarbij x het aantal tekens is waaruit we de sleutel van de groep vormen. Eén minimum is één rationaal getal, dus een type als double of float.

Een opmerking tot slot: we konden ons veroorloven de invoer in meerdere groepen te splitsen omdat de invoer uit id's bestond die zich als een willekeurige string gedroegen. Als de invoer geen willekeurige string was, maar gegevens in een bepaald formaat, zouden we de splitsing anders moeten doen. Als bijvoorbeeld elke id met het prefix userid- begon, zou een indeling in groepen op basis van het eerste teken waarschijnlijk niet echt werken, nietwaar.