Min Value: slik anslår du antall unike verdier

I forrige artikkel om Linear Counting gikk vi gjennom grunnleggende algoritmer for å regne ut og anslå antall unike verdier i en datamengde. I dag ser vi på en ny probabilistisk algoritme som gjør det mulig å anslå antall unike verdier med god nøyaktighet og lite minnebruk.

Min Value

I artikkelen jobber vi bare med reelle tall fra enhetsintervallet ⟨0, 1⟩. La oss tenke oss en mengde tall fra dette intervallet som er jevnt fordelt, for eksempel mengden av tallene {0,25; 0,5; 0,75}. Nabotallene ligger alltid akkurat 0,25 fra hverandre (og fra null og fra én). Hvordan hjelper dette oss å telle antall unike elementer?

Hvis jeg forteller deg at vi har en slik jevnt fordelt mengde av tall fra enhetsintervallet, og at tallene ligger akkurat 0,2 fra hverandre — kan du regne ut hvor mange elementer en slik mengde har? Selvfølgelig, det er mengden {0,2; 0,4; 0,6; 0,8}, og kardinaliteten er lik fire. Hvis vi har jevnt fordelte tall fra enhetsintervallet som input og kjenner avstanden mellom nabotallene, kan vi lett regne ut antall elementer.

Avstanden mellom nabotall er dessuten lik det minste elementet i mengden — avstanden mellom nabo-elementene i mengden {0,25; 0,5; 0,75} er 0,25 osv. For å regne ut antall elementer i jevnt fordelte tall er det nok at vi på en eller annen måte finner det minste elementet. Da kan vi regne ut antall elementer p med en enkel formel:

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

der m er det minste elementet.

Og vi skal hashe igjen…

Ja, men hvordan bruker vi dette hvis vi har strenger eller andre verdier som input som ikke oppfyller kravet om jevn fordeling i enhetsintervallet? Vi hjelper oss igjen med den gode, gamle hashfunksjonen, som for vilkårlig input kan gi oss et rasjonalt tall fra enhetsintervallet. Det er lett å konstruere en slik hashfunksjon.

Dermed ville vi fått rasjonale tall ut av dataene, men hvordan sørger vi for at disse tallene er jevnt fordelt? Det går riktignok ikke, men vi kan hjelpe oss på en annen måte. Fra vårt ståsted oppfører hashfunksjonen seg nemlig ganske «tilfeldig». For veldig like ord som «hei», «hej» og «hel» vil hashfunksjonen sannsynligvis gi veldig ulike sjekksummer. Med andre ord: hvis vi hasher tusen ulike verdier til enhetsintervallet, er det veldig lite sannsynlig at et markant flertall av tallene er for eksempel mindre enn én halv. Tvert imot er det veldig sannsynlig at tallene er mer eller mindre jevnt fordelt. Jo mer data vi hasher, jo jevnere blir fordelingen.

Fra denne tanken får vi en enkel algoritme: vi går gjennom inputdataene, hasher hvert element til enhetsintervallet og husker det minste elementet. Antall unike elementer anslår vi etter den forrige formelen. Implementasjon 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)

Funksjonen unit_interval_hash gir oss et desimaltall fra intervallet ⟨0, 1]. Funksjonen count_unique_using_minimum gjør først alle inputverdiene om til akkurat dette tallet, finner minimumet og returnerer 1 / minimum - 1. Legg merke til at det ikke spiller noen rolle hvor mange like verdier det er i datamengden — for to like verdier gir hashfunksjonen det samme rasjonale tallet, og det påvirker ikke det endelige minimumet på noen måte. Derfor teller vi med denne algoritmen antall unike elementer.

Hva er resultatene? (På hver linje står den anslåtte kardinaliteten, og den riktige kardinaliteten er 10 000.)

5957
16384
13107
9362
65536
8192
21845
13107
21845
8192

Vel, ikke noe særlig, ikke sant? Algoritmen kjørte gjennom ti ulike sett med ID-er som hver hadde ti tusen unike verdier. De utregnede anslagene er for det meste ganske langt unna. Hvis vi tok gjennomsnittet av dem, ville vi fått verdien 18 352. Det er fortsatt ganske langt unna, men på den andre siden, tenk på minnebehovet — det er konstant! For å finne minimumet er det nok at du alltid har én variabel i minnet der du lagrer det nåværende minimumet, og det er alt. Så ja, anslaget er elendig, men det koster nesten ingenting.

Vi forbedrer

Vi ser at algoritmen først og fremst er ustabil — én gang gir den oss et ganske bra anslag (9362), neste gang gir den oss et anslag som er helt av gårde (65536). Hvordan kommer vi oss ut av det? Vi kan hjelpe oss ved å dele inputdataene i flere deler, regne ut antall unike elementer for hver del og til slutt ta gjennomsnittet av alt sammen. Vi kunne bestemme oss etter det første tegnet i ID-en vår. Da regner vi ut antall unike verdier for seg for ID-ene som begynner med bokstaven «a», så for dem som begynner med bokstaven «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)

Endringene er i funksjonen count_unique_using_minimum. I variabelen min_values lagrer vi minimumene for hver gruppe. På slutten summerer vi alle minimumene og deler dem på antall lagrede verdier — da får vi det gjennomsnittlige minimumet. Med uttrykket 1/average_minimum finner vi ut hva det gjennomsnittlige antallet unike verdier i hver gruppe er — denne verdien multipliserer vi i tillegg med antall grupper, og da får vi det anslåtte antallet unike verdier i datamengden som ble sendt inn. Og hvordan fungerer denne endrede framgangsmåten?

11312
7504
10560
8160
9344
12688
10976
11616
16240
6832

Vel, det er fortsatt ikke bra, men det er definitivt bedre. Algoritmen er mer stabil. Vi kan prøve å endre funksjonen slik at gruppene ikke dannes etter det første tegnet, men for eksempel etter de to første tegnene i ID-en, altså slik:

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

Resultatene ville da blitt slike:

9728
9728
9984
10240
8960
10752
9728
9472
11264
9472

Jaaa, det er jo ikke så verst, eller hva? Hvis vi i tillegg prøver hundre tusen unike verdier, de to første tegnene og n = 24, får vi disse resultatene:

103936
110080
102656
101120
101376
108288
97536
97024
107776
92416

Det går an. Men det finnes fortsatt bedre algoritmer, ikke vær redd.

Og hvor mye minne krever den? Vi må lagre minimumet for hver gruppe, ikke noe mer. Hvis vi har ID-er i heksadesimalt format, betyr det at vi må huske høyst 16^x minimumer, der x er antall tegn vi lager gruppenøkkelen av. Ett minimum er ett rasjonalt tall, altså en eller annen type double eller float.

En merknad til slutt: vi kunne tillate oss å dele input i flere grupper fordi vi hadde ID-er som oppførte seg som en tilfeldig streng. Hvis vi ikke hadde en tilfeldig streng som input, men data i et bestemt format, måtte vi gjort inndelingen på en annen måte. Hvis for eksempel hver ID begynte med prefikset userid-, ville inndeling i grupper etter det første tegnet neppe fungert så godt, ikke sant.