Min Value: Sådan estimerer du antallet af unikke værdier

I den forrige artikel om Linear Counting gennemgik vi de grundlæggende algoritmer til at beregne og estimere antallet af unikke værdier i et datasæt. I dag venter en anden probabilistisk algoritme, som gør det muligt at estimere antallet af unikke værdier med fornuftig præcision og et lille hukommelsesforbrug.

Min Value

I artiklen arbejder vi kun med reelle tal fra enhedsintervallet ]0; 1[. Lad os forestille os en mængde af tal fra dette interval, som er jævnt fordelt, fx mængden af tallene {0,25; 0,5; 0,75}. Nabotal ligger altid præcis 0,25 fra hinanden (og fra nul og fra et). Hvordan hjælper det os med at tælle antallet af unikke elementer?

Hvis jeg siger, at vi har sådan en jævnt fordelt mængde af tal fra enhedsintervallet, og at tallene ligger præcis 0,2 fra hinanden — kan du så beregne, hvor mange elementer sådan en mængde har? Selvfølgelig, det er mængden {0,2; 0,4; 0,6; 0,8}, hvis kardinalitet er lig med fire. Når vi har jævnt fordelte tal fra enhedsintervallet som input og kender afstanden mellem nabotal, kan vi let beregne antallet af elementer.

Afstanden mellem nabotal er samtidig lig med mængdens mindste element — afstanden mellem nabotallene i mængden {0,25; 0,5; 0,75} er 0,25 osv. Når vi skal beregne antallet af elementer i jævnt fordelte tal, er det nok, at vi på en eller anden måde finder det mindste element. Så kan vi beregne antallet af elementer p med en enkel formel:

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

hvor m er det mindste element.

Og igen skal vi hashe…

Ja, men hvordan udnytter vi det, hvis vi har strenge eller andre værdier som input, der ikke opfylder betingelsen om jævn fordeling i enhedsintervallet? Vi hjælper os igen med den gode gamle hashfunktion, som kan returnere et rationalt tal fra enhedsintervallet for et vilkårligt input. Det er let at konstruere sådan en hashfunktion.

Dermed ville vi få rationale tal ud af data, men hvordan sikrer vi, at disse tal er jævnt fordelt? Det kan vi nok ikke, men vi kan hjælpe os på en anden måde. Set fra vores side opfører hashfunktionen sig nemlig ret »tilfældigt«. For meget ens ord som »hej«, »hek« og »hel« vil hashfunktionen sandsynligvis returnere meget forskellige checksums. Med andre ord: hvis vi hasher tusind forskellige værdier ind i enhedsintervallet, er det meget usandsynligt, at et markant flertal af tallene fx er mindre end en halv. Omvendt er det meget sandsynligt, at tallene vil være fordelt mere eller mindre regelmæssigt. Jo flere data vi hasher, desto mere regelmæssig bliver fordelingen.

Ud fra denne tanke får vi en enkel algoritme: vi gennemgår inputdata, hasher hvert element ind i enhedsintervallet og husker det mindste element. Antallet af unikke elementer estimerer vi efter den foregående formel. Implementering i 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)

Funktionen unit_interval_hash returnerer et decimaltal fra intervallet ]0; 1]. Funktionen count_unique_using_minimum omdanner først alle inputværdier netop til dette tal, finder minimum og returnerer 1 / minimum - 1. Læg mærke til, at det slet ikke betyder noget, hvor mange ens værdier der er i datasættet — for to ens værdier returnerer hashfunktionen det samme rationale tal, hvilket ikke på nogen måde påvirker det resulterende minimum. Derfor tæller vi med denne algoritme antallet af unikke elementer.

Hvad er resultaterne? (På hver linje står den estimerede kardinalitet, den korrekte kardinalitet er 10.000.)

5957
16384
13107
9362
65536
8192
21845
13107
21845
8192

Altså, ikke ret godt, vel? Algoritmen kørte ti forskellige sæt af ID'er igennem, hvor der hver gang var ti tusind unikke værdier. De beregnede estimater er for det meste ret langt fra målet. Hvis vi tog gennemsnittet af dem, ville vi komme frem til værdien 18.352. Det er stadig ret langt fra målet, men til gengæld skal du se på hukommelsesforbruget — det er konstant! For at finde minimum er det nok altid at have én variabel i hukommelsen, hvor du gemmer det aktuelle minimum, og det er det hele. Så ja, estimatet er elendigt, men det koster til gengæld næsten ingenting.

Vi forbedrer det

Vi ser, at algoritmen først og fremmest er ustabil — én gang giver den et ret godt estimat (9362), en anden gang et estimat, der er helt ved siden af (65536). Hvordan kommer vi ud af det? Vi kan hjælpe os ved at dele inputdata op i flere dele, beregne antallet af unikke elementer for hver del og til sidst tage gennemsnittet af det hele. Vi kunne dele dem op efter det første tegn i vores ID. Så beregner vi særskilt antallet af unikke værdier for de ID'er, der begynder med bogstavet »a«, derefter for dem, der begynder med bogstavet »b« osv. Kode:

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)

Ændringerne er i funktionen count_unique_using_minimum. I variablen min_values gemmer vi minima for hver gruppe. Til sidst lægger vi alle minima sammen og dividerer dem med antallet af alle gemte værdier — vi får det gennemsnitlige minimum. Med udtrykket 1/average_minimum finder vi ud af, hvad det gennemsnitlige antal unikke værdier i hver gruppe er — denne værdi ganger vi så med antallet af grupper og får det estimerede antal unikke værdier i det givne datasæt. Og hvordan fungerer denne ændrede fremgangsmåde?

11312
7504
10560
8160
9344
12688
10976
11616
16240
6832

Altså, det er stadig ikke godt, men det er helt sikkert bedre. Algoritmen er mere stabil. Vi kan prøve at ændre funktionen, så grupperne ikke dannes efter det første tegn, men fx efter de to første tegn i ID'et, dvs. sådan her:

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

Resultaterne ville så være disse:

9728
9728
9984
10240
8960
10752
9728
9472
11264
9472

Nååå, det er ikke helt dårligt, vel? Hvis vi yderligere prøver hundrede tusind unikke værdier, de to første tegn og n = 24, får vi disse resultater:

103936
110080
102656
101120
101376
108288
97536
97024
107776
92416

Det går nogenlunde. Men der findes stadig bedre algoritmer, bare rolig.

Og hvor hukommelseskrævende er det? Vi skal gemme minimum for hver gruppe, intet mere. Hvis vi har ID'er i hex-format, betyder det, at vi højst skal huske 16^x minima, hvor x er antallet af tegn, som vi danner gruppens nøgle af. Ét minimum er ét rationalt tal, dvs. en eller anden type double eller float.

En bemærkning til sidst: vi kunne tillade os at dele input op i flere grupper, fordi vi havde ID'er som input, der opførte sig som en tilfældig streng. Hvis vi ikke havde en tilfældig streng som input, men nogle data i et bestemt format, ville vi være nødt til at lave opdelingen anderledes. Hvis fx hvert ID begyndte med præfikset userid-, ville opdelingen i grupper efter det første tegn nok ikke fungere så godt, vel?