Min Value: hogyan becsüljük meg az egyedi értékek számát

Az előző, Linear Countingról szóló cikkben egy adathalmaz egyedi értékei számának kiszámítására és megbecslésére néztünk meg alapvető algoritmusokat. Ma egy másik valószínűségi algoritmus következik, amely elfogadható pontossággal és kis memóriaigénnyel képes megbecsülni az egyedi elemek számát.

Min Value

A cikkben csak a ]0; 1[ egységintervallum valós számaival dolgozunk. Képzeljünk el egy ebből az intervallumból vett, egyenletesen elosztott számhalmazt, például a {0,25; 0,5; 0,75} halmazt. A szomszédos számok mindig pontosan 0,25-re vannak egymástól (és a nullától, valamint az egyestől is). Hogyan segít ez az egyedi elemek megszámolásában?

Ha azt mondom, hogy van egy ilyen, az egységintervallumból vett, egyenletesen elosztott számhalmazunk, és a számok egymástól pontosan 0,2 távolságra vannak – ki tudod számolni, hány eleme van a halmaznak? Persze, ez a {0,2; 0,4; 0,6; 0,8} halmaz, amelynek a számossága négy. Ha a bemeneten az egységintervallum egyenletesen elosztott számai vannak, és ismerjük a szomszédos számok távolságát, könnyen ki tudjuk számolni az elemek számát.

A szomszédos számok távolsága pedig megegyezik a halmaz legkisebb elemével – a {0,25; 0,5; 0,75} halmaz szomszédos elemeinek távolsága 0,25, és így tovább. Az egyenletesen elosztott számok darabszámának kiszámításához elég valahogy megtudnunk a legkisebb elemet. Ekkor a p elemszámot egy egyszerű képlettel kiszámíthatjuk:

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

ahol m a legkisebb elem.

És megint hashelünk…

Jó, de hogyan használjuk ezt ki, ha a bemeneten szövegek vagy más értékek vannak, amelyek éppen nem teljesítik az egységintervallumon való egyenletes eloszlás feltételét? Megint segítségünkre lesz a jó öreg hash-függvény, amely tetszőleges bemenetre vissza tud adni egy racionális számot az egységintervallumból. Ilyen hash-függvényt könnyű készíteni.

Ezzel az adatokból racionális számokat kapnánk, de hogyan érjük el, hogy ezek a számok egyenletesen legyenek elosztva? Ez már nem fog menni, de segíthetünk magunkon másképp. A hash-függvény ugyanis a mi szemszögünkből eléggé „véletlenszerűen” viselkedik. Az olyan nagyon hasonló szavakra, mint az „ahoj”, „ahok” és „ahol”, a hash-függvény valószínűleg nagyon különböző checksumokat ad majd. Más szóval: ha ezer különböző értéket hashelünk az egységintervallumba, nagyon valószínűtlen, hogy a számok túlnyomó többsége például kisebb lenne 0,5-nél. Ellenkezőleg, nagyon valószínű, hogy ezek a számok többé-kevésbé szabályosan oszlanak el. Minél több adatot hashelünk, annál szabályosabb lesz az eloszlás.

Ebből a gondolatból egyszerű algoritmus adódik: végigmegyünk a bemeneti adatokon, minden elemet az egységintervallumba hashelünk, és megjegyezzük a legkisebbet. Az egyedi elemek számát az előző képlet szerint becsüljük meg. A megvalósítás Pythonban:

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)

A unit_interval_hash függvény a ]0; 1] intervallumból ad vissza tizedes törtet. A count_unique_using_minimum függvény először az összes bemeneti értéket éppen ilyen számmá alakítja, megkeresi a minimumot, és 1 / minimum - 1-et ad vissza. Figyeld meg, hogy egyáltalán nem számít, hány azonos érték van az adatok között – két azonos értékre a hash-függvény ugyanazt a racionális számot adja vissza, ami a kapott minimumot nem befolyásolja. Ezért ezzel az algoritmussal az egyedi elemek számát számoljuk meg.

Milyenek az eredmények? (Minden sorban a becsült számosság áll, a helyes számosság pedig 10 000.)

Hát, nem valami jó, ugye? Az algoritmus tíz különböző azonosítókészletet járt végig, mindegyikben tízezer egyedi érték volt. A kiszámított becslések tehát többnyire elég messze vannak. Ha átlagolnánk őket, 18 352-t kapnánk. Ez is elég messze van, másrészt viszont gondolj a memóriaigényre – állandó! A minimum megtalálásához elég a memóriában egyetlen változót tárolnod, amelybe az aktuális minimumot teszed, és ennyi az egész. Szóval igen, a becslés gyenge, de szinte semmibe sem kerül.

Fejlesztünk

Látjuk, hogy az algoritmus mindenekelőtt instabil – egyszer elég jó becslést ad (9362), máskor olyat, ami teljesen mellé megy (65536). Hogyan javítsunk ezen? Segíthetünk magunkon úgy, hogy a bemeneti adatokat több részre osztjuk, minden részre kiszámítjuk az egyedi elemek számát, és végül az egészet szépen átlagoljuk. A felosztás alapja lehetne az azonosítónk első karaktere. Vagyis külön kiszámítjuk az egyedi elemek számát az „a” betűvel kezdődő azonosítókra, aztán a „b” betűvel kezdődőkre, és így tovább. A kód:

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)

A változtatások a count_unique_using_minimum függvényben vannak. A min_values változóban minden csoport minimumát tároljuk. A végén összeadjuk az összes minimumot, és elosztjuk az eltárolt értékek számával – megkapjuk az átlagos minimumot. Az 1/average_minimum kifejezéssel kiderítjük, mekkora az egyedi értékek átlagos száma az egyes csoportokban – ezt az értéket tehát még megszorozzuk a csoportok számával, és megkapjuk az átadott adatokban az egyedi értékek becsült számát. És hogyan működik ez a módosított eljárás?

Hát, még mindig nem jó, de biztosan jobb. Az algoritmus stabilabb. Megpróbálhatjuk úgy módosítani a függvényt, hogy a csoportokat ne az első karakter alapján képezze, hanem például az azonosító első két karaktere alapján, vagyis így:

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

Az eredmények ekkor ilyenek lennének:

Hűha, ez már nem is rossz, igaz? Ha még kipróbálunk százezer egyedi értéket, az első két karaktert és n = 24-et, ezeket az eredményeket kapjuk:

Ez már elmegy. De még mindig vannak jobb algoritmusok, ne aggódj.

És mekkora a memóriaigény? Minden csoportra el kell tárolnunk a minimumot, semmi többet. Ha az azonosítóink hexadecimális formátumúak, akkor ez azt jelenti, hogy legfeljebb 16^x minimumot kell megjegyeznünk, ahol x a csoportkulcsot alkotó karakterek száma. Egy minimum egy racionális szám, azaz valamilyen double vagy float típus.

Záró megjegyzés: a bemenet több csoportra osztását azért engedhettük meg magunknak, mert a bemeneten olyan azonosítók voltak, amelyek véletlen szövegként viselkedtek. Ha nem véletlen szöveg lenne a bemeneten, hanem valamilyen meghatározott formátumú adat, az osztást másképp kellene végeznünk. Ha például minden azonosító a userid- előtaggal kezdődne, akkor az első karakter szerinti csoportosítás nem nagyon működne, ugye.

Fejezetek: Linear Counting, Min Value, LogLog, HyperLogLog

« Előző: Az egyedi értékek száma

Következő: LogLog »