Min Value: come stimare il numero di valori distinti

Nell’articolo precedente sul Linear counting abbiamo visto gli algoritmi di base per calcolare e stimare il numero di valori distinti in un insieme di dati. Oggi ci aspetta un altro algoritmo probabilistico, che permette di stimare il numero di valori distinti con una buona precisione e un uso minimo di memoria.

Min Value

In questo articolo lavoreremo soltanto con numeri reali dell’intervallo unitario (0; 1). Immaginiamo un insieme di numeri di questo intervallo distribuiti in modo uniforme, per esempio l’insieme {0,25; 0,5; 0,75}. I numeri vicini distano sempre tra loro (e da zero e da uno) esattamente 0,25. Come ci aiuta questo a contare gli elementi distinti?

Se ti dico che abbiamo un insieme di numeri dell’intervallo unitario distribuiti in modo uniforme e che la distanza tra due numeri vicini è esattamente 0,2, riesci a calcolare quanti elementi ha l’insieme? Certo, si tratta dell’insieme {0,2; 0,4; 0,6; 0,8}, la cui cardinalità è quattro. Se in ingresso abbiamo numeri distribuiti in modo uniforme nell’intervallo unitario e conosciamo la distanza tra numeri vicini, possiamo calcolare facilmente il numero di elementi.

Inoltre la distanza tra numeri vicini è uguale all’elemento minimo dell’insieme: la distanza tra gli elementi vicini dell’insieme {0,25; 0,5; 0,75} è 0,25, e così via. Per contare i numeri distribuiti uniformemente ci basta trovare in qualche modo l’elemento minimo. Allora possiamo calcolare il numero di elementi p con una formula semplice:

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

dove m è l’elemento minimo.

E di nuovo useremo l’hash…

Ma come sfruttarlo se in ingresso abbiamo delle stringhe o altri valori che non rispettano la condizione di distribuzione uniforme nell’intervallo unitario? Ci aiutiamo di nuovo con la vecchia e cara funzione di hash, che per qualsiasi ingresso può restituirci un numero razionale dell’intervallo unitario. Costruire una funzione di hash di questo tipo è facile.

In questo modo otterremmo dai dati dei numeri razionali, ma come fare in modo che siano distribuiti uniformemente? Questo non è possibile, ma possiamo cavarcela in un altro modo. Dal nostro punto di vista, infatti, la funzione di hash si comporta in modo piuttosto «casuale». Per parole molto simili come «ciao», «ciap» e «ciaq» la funzione di hash restituirà con ogni probabilità checksum molto diversi. In altre parole: se calcoliamo l’hash di mille valori diversi nell’intervallo unitario, è molto improbabile che la netta maggioranza dei numeri sia, per esempio, minore di un mezzo. È invece molto probabile che questi numeri siano distribuiti più o meno regolarmente. Più dati passiamo per la funzione di hash, più la distribuzione sarà regolare.

Da questa idea ricaviamo un algoritmo semplice: scorriamo i dati in ingresso, calcoliamo l’hash di ogni elemento nell’intervallo unitario e ricordiamo l’elemento minimo. Il numero di valori distinti lo stimiamo con la formula precedente. Implementazione in 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)

La funzione unit_interval_hash ci restituisce un numero decimale dell’intervallo (0; 1]. La funzione count_unique_using_minimum converte prima tutti i valori in ingresso in questo numero, trova il minimo e restituisce 1 / minimum - 1. Osserva che non importa affatto quanti valori uguali ci siano nell’insieme di dati: per due valori uguali la funzione di hash restituisce lo stesso numero razionale, che non influisce in alcun modo sul minimo finale. Per questo con questo algoritmo contiamo i valori distinti.

Quali sono i risultati? (Su ogni riga c’è la cardinalità stimata; la cardinalità corretta è 10.000.)

5957
16384
13107
9362
65536
8192
21845
13107
21845
8192

Beh, niente di che, vero? L’algoritmo ha elaborato dieci diversi insiemi di identificatori, ciascuno con diecimila valori distinti. Le stime calcolate sono per lo più piuttosto lontane dal valore reale. Se ne facessimo la media, arriveremmo al valore 18.352. È ancora piuttosto lontano, ma d’altra parte pensa all’uso di memoria: è costante! Per trovare il minimo ti basta tenere in memoria una sola variabile, in cui salvi il minimo attuale, e basta. Quindi sì, la stima è pessima, ma in compenso non costa praticamente niente.

Miglioriamo l’algoritmo

Vediamo che l’algoritmo è soprattutto instabile: una volta ci restituisce una stima abbastanza buona (9362), un’altra volta una stima completamente sbagliata (65536). Come uscirne? Possiamo dividere i dati in ingresso in più parti, calcolare il numero di valori distinti per ciascuna parte e alla fine fare la media di tutto. Potremmo decidere in base al primo carattere del nostro identificatore. Contiamo quindi separatamente i valori distinti per gli identificatori che iniziano con la lettera «a», poi per quelli che iniziano con la lettera «b», e così via. Codice:

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)

Le modifiche riguardano la funzione count_unique_using_minimum. Nella variabile min_values conserviamo i minimi di ciascun gruppo. Alla fine sommiamo tutti i minimi e li dividiamo per il numero di tutti i valori salvati: otteniamo il minimo medio. Con l’espressione 1/average_minimum ricaviamo il numero medio di valori distinti in ogni gruppo; questo valore lo moltiplichiamo ancora per il numero di gruppi e otteniamo il numero stimato di valori distinti nell’insieme di dati ricevuto. E come funziona questo procedimento modificato?

11312
7504
10560
8160
9344
12688
10976
11616
16240
6832

Beh, non è ancora buono, ma è sicuramente meglio. L’algoritmo è più stabile. Possiamo provare a modificare la funzione in modo che i gruppi non si formino in base al primo carattere, ma, per esempio, in base ai primi due caratteri dell’identificatore, cioè così:

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

I risultati sarebbero questi:

9728
9728
9984
10240
8960
10752
9728
9472
11264
9472

Eeeh, ora non è più tanto male, no? Se proviamo ancora con centomila valori distinti, i primi due caratteri e n = 24, otteniamo questi risultati:

103936
110080
102656
101120
101376
108288
97536
97024
107776
92416

Può andare. Ma esistono ancora algoritmi migliori, non preoccuparti.

E quanta memoria richiede? Dobbiamo conservare il minimo di ogni gruppo, nient’altro. Se gli identificatori sono in formato esadecimale, significa che dobbiamo ricordare al massimo 16^x minimi, dove x è il numero di caratteri con cui formiamo la chiave del gruppo. Un minimo è un numero razionale, cioè un tipo double o float.

Una nota finale: abbiamo potuto permetterci di dividere l’ingresso in più gruppi perché in ingresso avevamo identificatori che si comportavano come stringhe casuali. Se in ingresso non avessimo stringhe casuali, ma dati in un certo formato, dovremmo fare la divisione in un altro modo. Se per esempio ogni identificatore iniziasse con il prefisso userid-, la divisione in gruppi in base al primo carattere non funzionerebbe granché, vero?