Min Value: miten arvioidaan uniikkien arvojen lukumäärä

Edellisessä Linear Counting -artikkelissa kävimme läpi perusalgoritmit uniikkien arvojen lukumäärän laskemiseen ja arvioimiseen jossakin dataryhmässä. Tänään vuorossa on toinen todennäköisyysalgoritmi, jolla uniikkien lukumäärän voi arvioida kohtuullisella tarkkuudella ja pienillä muistivaatimuksilla.

Min Value

Artikkelissa työskentelemme vain yksikkövälin ]0, 1[ reaaliluvuilla. Kuvitellaan tämän välin lukujen joukko, joka on jakautunut tasaisesti, esimerkiksi lukujen joukko {0,25; 0,5; 0,75}. Vierekkäiset luvut ovat aina täsmälleen 0,25 päässä toisistaan (sekä nollasta ja ykkösestä). Miten tämä auttaa meitä laskemaan uniikkien alkioiden lukumäärän?

Jos kerron sinulle, että meillä on tällainen yksikkövälin tasaisesti jakautunut lukujen joukko, ja näiden lukujen keskinäinen etäisyys on täsmälleen 0,2 — osaatko laskea, kuinka monta alkiota tällaisessa joukossa on? Tietenkin kyseessä on joukko {0,2; 0,4; 0,6; 0,8}, jonka kardinaliteetti on neljä. Jos syötteenä on tasaisesti jakautuneita yksikkövälin lukuja ja tunnemme vierekkäisten lukujen etäisyyden, alkioiden lukumäärän laskeminen on helppoa.

Vierekkäisten lukujen etäisyys on samalla yhtä suuri kuin joukon pienin alkio — joukon {0,25; 0,5; 0,75} vierekkäisten alkioiden etäisyys on 0,25 jne. Kun lasketaan tasaisesti jakautuneiden lukujen alkioiden lukumäärää, riittää, että jotenkin selvitämme pienimmän alkion. Silloin voimme laskea alkioiden lukumäärän p yksinkertaisella kaavalla:

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

jossa m on tuo pienin alkio.

Ja taas tiivistetään…

Mutta miten tätä voi hyödyntää, jos syötteenä on merkkijonoja tai muita arvoja, jotka eivät juuri täytä yksikkövälille tasaisen jakautumisen ehtoa? Apuna on taas hyvä vanha tiivistefunktio, joka voi palauttaa mille tahansa syötteelle rationaaliluvun yksikkövälillä. Tällaisen tiivistefunktion rakentaminen on helppoa.

Näin saisimme datasta rationaalilukuja, mutta miten varmistamme, että nämä luvut ovat tasaisesti jakautuneita? Se ei enää onnistu, mutta voimme auttaa itseämme toisin. Tiivistefunktio nimittäin käyttäytyy meidän näkökulmastamme melko ”satunnaisesti”. Hyvin samankaltaisille sanoille kuten ”moi”, ”moj” ja ”mok” tiivistefunktio palauttaa todennäköisesti hyvin erilaisia tarkistussummia. Toisin sanoen: jos tiivistämme tuhat eri arvoa yksikkövälille, on hyvin epätodennäköistä, että selvä enemmistö luvuista olisi esimerkiksi pienempiä kuin puoli. Sen sijaan on hyvin todennäköistä, että luvut ovat jakautuneet enemmän tai vähemmän säännöllisesti. Mitä enemmän dataa tiivistämme, sitä säännöllisempi jakauma on.

Tästä ajatuksesta saamme yksinkertaisen algoritmin: käymme syötedatan läpi, tiivistämme jokaisen alkion yksikkövälille ja muistamme pienimmän alkion. Uniikkien alkioiden lukumäärän arvioimme edellisen kaavan mukaan. Toteutus Pythonilla:

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)

Funktio unit_interval_hash palauttaa meille desimaaliluvun väliltä ]0, 1]. Funktio count_unique_using_minimum muuntaa ensin kaikki syötearvot juuri tällaiseksi luvuksi, etsii minimin ja palauttaa 1 / minimum - 1. Huomaa, ettei ole lainkaan väliä, kuinka monta samaa arvoa dataryhmässä on — kahdelle samalle arvolle tiivistefunktio palauttaa saman rationaaliluvun, mikä ei vaikuta tulokseksi saatavaan minimiin mitenkään. Siksi tällä algoritmilla laskemme uniikkien alkioiden lukumäärän.

Millaisia tuloksia saadaan? (Jokaisella rivillä on arvioitu kardinaliteetti, oikea kardinaliteetti on tässä 10 000.)

5957
16384
13107
9362
65536
8192
21845
13107
21845
8192

No, ei kovin hääviä, vai mitä? Algoritmi kävi läpi kymmenen eri tunnistejoukkoa, joissa oli aina kymmenentuhatta uniikkia arvoa. Lasketut arviot ovat siis enimmäkseen aika kaukana. Jos keskiarvoistaisimme ne, päätyisimme arvoon 18 352. Se on yhä melko kaukana, mutta toisaalta ota huomioon muistivaatimukset — ne ovat vakiot! Minimin löytämiseksi riittää, että pidät muistissa aina yhtä muuttujaa, johon tallennat nykyisen minimin, ja siinä kaikki. Eli kyllä, arvio on ihan pielessä, mutta toisaalta se ei maksa melkein mitään.

Parannetaan

Näemme, että algoritmi on ennen kaikkea epävakaa — kerran se palauttaa melko hyvän arvion (9362), toisella kertaa arvion, joka on aivan pielessä (65536). Miten tästä päästään eteenpäin? Voimme auttaa itseämme jakamalla syötedatan useaan osaan, laskemalla uniikkien alkioiden lukumäärän jokaiselle osalle ja lopuksi keskiarvoistamalla kaiken kauniisti. Voisimme päättää jaon tunnisteemme ensimmäisen merkin perusteella. Laskemme siis erikseen uniikkien lukumäärän tunnisteille, jotka alkavat kirjaimella ”a”, sitten niille, jotka alkavat kirjaimella ”b” jne. Koodi:

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)

Muutokset ovat funktiossa count_unique_using_minimum. Muuttujassa min_values säilytämme jokaisen ryhmän minimin. Lopuksi laskemme kaikki minimit yhteen ja jaamme ne kaikkien tallennettujen arvojen lukumäärällä — saamme keskimääräisen minimin. Lausekkeella 1/average_minimum selvitämme, kuinka monta uniikkia arvoa on keskimäärin jokaisessa ryhmässä — kerromme tämän arvon vielä ryhmien lukumäärällä ja saamme arvioidun uniikkien arvojen lukumäärän annetussa dataryhmässä. Ja miten tämä muokattu menetelmä toimii?

11312
7504
10560
8160
9344
12688
10976
11616
16240
6832

No, ei se vieläkään ole hyvä, mutta se on varmasti parempi. Algoritmi on vakaampi. Voimme yrittää muokata funktiota niin, ettei ryhmiä muodosteta ensimmäisen merkin perusteella, vaan esimerkiksi tunnisteen kahden ensimmäisen merkin perusteella, eli näin:

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

Tulokset olisivat silloin tällaisia:

9728
9728
9984
10240
8960
10752
9728
9472
11264
9472

Nooo, eihän se ole enää ihan huono, vai mitä? Jos kokeilemme vielä sataatuhatta uniikkia arvoa, kahta ensimmäistä merkkiä ja n = 24, saamme nämä tulokset:

103936
110080
102656
101120
101376
108288
97536
97024
107776
92416

Kelpaa kyllä. Mutta parempiakin algoritmeja on yhä olemassa, älä huoli.

Ja mikä on muistivaatimus? Meidän täytyy säilyttää jokaisen ryhmän minimi, ei muuta. Jos tunnisteet ovat heksamuodossa, se tarkoittaa, että meidän täytyy muistaa enintään 16^x minimiä, jossa x on ryhmän avaimen muodostavien merkkien lukumäärä. Yksi minimi on yksi rationaaliluku, eli jokin double- tai float-tyyppi.

Huomautus loppuun: syöte oli mahdollista jakaa useaan ryhmään siksi, että syötteenä oli tunnisteita, jotka käyttäytyivät kuin satunnainen merkkijono. Jos syötteenä ei olisi satunnainen merkkijono vaan jotakin tietyssä muodossa olevaa dataa, jako täytyisi tehdä toisin. Jos esimerkiksi jokainen tunniste alkaisi etuliitteellä userid-, jako ryhmiin ensimmäisen merkin mukaan ei luultavasti toimisi kovin hyvin, vai mitä.