Min Value: så uppskattar du antalet unika värden

I förra artikeln om Linear Counting gick vi igenom grundläggande algoritmer för att beräkna och uppskatta antalet unika värden i en datamängd. Nu är det dags för en ny probabilistisk algoritm som med hyfsad noggrannhet och litet minnesbehov kan uppskatta antalet unika värden.

Min Value

I den här artikeln arbetar vi bara med reella tal i enhetsintervallet ]0, 1[. Tänk dig en mängd tal i det här intervallet som är jämnt fördelade, till exempel mängden {0,25; 0,5; 0,75}. Intilliggande tal ligger alltid exakt 0,25 från varandra (och från noll och från ett). Hur hjälper det oss att räkna antalet unika element?

Om jag säger att vi har en sådan jämnt fördelad mängd tal från enhetsintervallet och att avståndet mellan talen är exakt 0,2 — kan du då räkna ut hur många element mängden har? Naturligtvis handlar det om mängden {0,2; 0,4; 0,6; 0,8}, vars kardinalitet är fyra. Om vi har jämnt fördelade tal från enhetsintervallet som indata och känner till avståndet mellan intilliggande tal, kan vi enkelt räkna ut antalet element.

Avståndet mellan intilliggande tal är dessutom lika med mängdens minsta element — avståndet mellan intilliggande tal i mängden {0,25; 0,5; 0,75} är 0,25 osv. När vi räknar antalet element i jämnt fördelade tal räcker det alltså att på något sätt ta reda på det minsta elementet. Då kan vi räkna ut antalet element p med en enkel formel:

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

där m är det minsta elementet.

Och så ska vi hasha igen…

Men hur använder vi det här om indata består av strängar eller andra värden som inte är jämnt fördelade i enhetsintervallet? Vi tar återigen hjälp av en god gammal hashfunktion, som för vilken indata som helst kan ge oss ett rationellt tal från enhetsintervallet. Det är lätt att konstruera en sådan hashfunktion.

Då har vi gjort om data till rationella tal, men hur ser vi till att talen blir jämnt fördelade? Det går visserligen inte, men vi kan lösa det på ett annat sätt. Hashfunktionen beter sig nämligen ganska ”slumpmässigt” sett från vårt håll. För mycket lika ord som ”hej”, ”hek” och ”hel” kommer hashfunktionen med all sannolikhet att ge helt olika checksummor. Med andra ord: om vi hashar tusen olika värden till enhetsintervallet är det mycket osannolikt att en klar majoritet av talen är till exempel mindre än en halv. Däremot är det mycket sannolikt att talen blir mer eller mindre regelbundet fördelade. Ju mer data vi hashar, desto regelbundnare blir fördelningen.

Av den här tanken får vi en enkel algoritm: vi går igenom indata, hashar varje element till enhetsintervallet och kommer ihåg det minsta elementet. Antalet unika element uppskattar vi med formeln ovan. Implementation 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 ger oss ett decimaltal i intervallet ]0, 1]. Funktionen count_unique_using_minimum gör först om alla indatavärden till just ett sådant tal, hittar minimum och returnerar 1 / minimum - 1. Observera att det inte spelar någon roll hur många lika värden som finns i datamängden — för två lika värden returnerar hashfunktionen samma rationella tal, och det påverkar inte det slutliga minimumet. Därför räknar algoritmen unika element.

Hur blev resultaten? (På varje rad står den uppskattade kardinaliteten, och den riktiga kardinaliteten är 10 000.)

5957
16384
13107
9362
65536
8192
21845
13107
21845
8192

Tja, inte mycket att hurra för, eller hur? Algoritmen gick igenom tio olika uppsättningar ID:n med tio tusen unika värden i varje. De uppskattade värdena ligger oftast ganska långt från det rätta. Om vi tar medelvärdet av dem får vi 18 352. Det är fortfarande en bra bit fel, men tänk på minnesbehovet — det är konstant! För att hitta minimum behöver du bara ha en enda variabel i minnet där du sparar det aktuella minimumet, och det är allt. Så ja, uppskattningen är värdelös, men den kostar nästan ingenting.

Vi förbättrar algoritmen

Vi ser att algoritmen framför allt är instabil — ena gången ger den en ganska bra uppskattning (9362), nästa gång en som är helt fel (65536). Hur kommer vi runt det? Vi kan dela upp indata i flera delar, räkna antalet unika element för varje del och till sist ta medelvärdet av allt. Vi skulle kunna dela upp dem efter det första tecknet i vårt ID. Då räknar vi antalet unika värden separat för de ID:n som börjar på bokstaven ”a”, sedan för dem som börjar på bokstaven ”b” osv. Koden:

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)

Ändringarna finns i funktionen count_unique_using_minimum. I variabeln min_values sparar vi minimumet för varje hink. Till sist summerar vi alla minima och delar med antalet sparade värden — då får vi det genomsnittliga minimumet. Med uttrycket 1/average_minimum får vi reda på det genomsnittliga antalet unika värden i varje hink — det värdet multiplicerar vi dessutom med antalet hinkar, och då får vi det uppskattade antalet unika värden i den datamängd vi skickade in. Hur fungerar den här justerade metoden?

11312
7504
10560
8160
9344
12688
10976
11616
16240
6832

Det är fortfarande inte bra, men det är definitivt bättre. Algoritmen är stabilare. Vi kan försöka ändra funktionen så att hinkarna inte bildas efter första tecknet utan till exempel efter de två första tecknen i ID:t, alltså så här:

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

Resultaten skulle då bli de här:

9728
9728
9984
10240
8960
10752
9728
9472
11264
9472

Naaa, nu är det faktiskt inte helt dåligt, eller hur? Om vi dessutom provar hundra tusen unika värden, de två första tecknen och n = 24, får vi de här resultaten:

103936
110080
102656
101120
101376
108288
97536
97024
107776
92416

Det går an. Men det finns fortfarande bättre algoritmer, oroa dig inte.

Och hur är det med minnesbehovet? Vi måste spara minimumet för varje hink, inget mer. Om ID:n är i hexformat betyder det att vi högst behöver komma ihåg 16^x minima, där x är antalet tecken som vi bildar hinkens nyckel av. Ett minimum är ett rationellt tal, alltså någon typ av double eller float.

En sista anmärkning: vi kunde dela upp indata i flera hinkar just för att vi hade ID:n som beter sig som slumpmässiga strängar. Om indata inte vore slumpmässiga strängar utan data i något bestämt format, skulle vi behöva dela upp dem på något annat sätt. Om till exempel varje ID började med prefixet userid- skulle det nog inte fungera särskilt bra att dela upp i hinkar efter första tecknet, eller hur.