Min Value: cómo estimar el número de valores distintos

En el artículo anterior sobre Linear Counting vimos los algoritmos básicos para calcular y estimar el número de valores distintos de un conjunto de datos. Hoy toca otro algoritmo probabilístico que permite estimar el número de valores distintos con una precisión aceptable y un consumo de memoria pequeño.

Min Value

En este artículo trabajaremos únicamente con números reales del intervalo unidad (0, 1). Imaginemos un conjunto de números de este intervalo repartidos de manera uniforme, por ejemplo, el conjunto {0,25; 0,5; 0,75}. Los números vecinos están siempre a una distancia de exactamente 0,25 entre sí (y de cero y de uno). ¿Cómo nos ayuda esto a contar el número de elementos distintos?

Si te digo que tenemos un conjunto de números del intervalo unidad repartidos de manera uniforme y que la distancia entre ellos es exactamente 0,2, ¿puedes calcular cuántos elementos tiene ese conjunto? Claro, se trata del conjunto {0,2; 0,4; 0,6; 0,8}, cuyo cardinal es cuatro. Si la entrada son números del intervalo unidad repartidos uniformemente y conocemos la distancia entre números vecinos, podemos calcular fácilmente el número de elementos.

Además, la distancia entre números vecinos es igual al elemento mínimo del conjunto: la distancia entre elementos vecinos del conjunto {0,25; 0,5; 0,75} es 0,25, etc. Para calcular el número de elementos de unos números repartidos uniformemente nos basta con averiguar de algún modo el elemento mínimo. Entonces podemos calcular el número de elementos p con una fórmula sencilla:

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

donde m es ese elemento mínimo.

Y otra vez a hacer hashes…

Ya, pero ¿cómo aprovechar esto si la entrada son cadenas u otros valores que no cumplen la condición de estar repartidos uniformemente en el intervalo unidad? Nos ayudaremos de nuevo de la buena y vieja función hash, que para cualquier entrada puede devolvernos un número racional del intervalo unidad. Construir una función hash así será fácil.

Con ella obtendríamos a partir de los datos números racionales, pero ¿cómo lograr que estén repartidos uniformemente? Eso ya no será posible, pero podemos arreglárnoslas de otra manera. Desde nuestro punto de vista, la función hash se comporta de forma bastante «aleatoria». Para palabras muy parecidas como «hola», «holo» y «holi», la función hash devolverá probablemente checksums muy distintos. En otras palabras: si aplicamos el hash al intervalo unidad a mil valores distintos, es muy improbable que una mayoría notable de los números sea, por ejemplo, menor que un medio. Al contrario, es muy probable que esos números estén repartidos más o menos de forma regular. Cuantos más datos pasemos por el hash, más regular será el reparto.

De esta idea sale un algoritmo sencillo: recorremos los datos de entrada, aplicamos el hash al intervalo unidad a cada elemento y recordamos el elemento mínimo. El número de elementos distintos lo estimamos con la fórmula anterior. Implementación en 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 función unit_interval_hash nos devuelve un número decimal del intervalo (0, 1]. La función count_unique_using_minimum convierte primero todos los valores de entrada en ese número, encuentra el mínimo y devuelve 1 / minimum - 1. Fíjate en que no importa en absoluto cuántos valores iguales haya en el conjunto de datos: para dos valores iguales la función hash nos devuelve el mismo número racional, lo cual no influye en el mínimo resultante. Por eso este algoritmo cuenta el número de elementos distintos.

¿Cuáles son los resultados? (En cada línea está la cardinalidad estimada; la cardinalidad correcta es 10.000.)

5957
16384
13107
9362
65536
8192
21845
13107
21845
8192

Pues no es gran cosa, ¿verdad? El algoritmo ha recorrido diez conjuntos distintos de identificadores, cada uno con diez mil valores distintos. Las estimaciones calculadas están casi siempre bastante lejos. Si calculáramos su media, llegaríamos a 18.352. Sigue estando bastante lejos, pero, por otro lado, mira el consumo de memoria: ¡es constante! Para encontrar el mínimo te basta con guardar siempre en memoria una variable con el mínimo actual, y nada más. Así que sí, la estimación es mala, pero a cambio casi no cuesta nada.

Mejoras

Vemos que el algoritmo es sobre todo inestable: una vez nos devuelve una estimación bastante buena (9362) y otra una estimación totalmente descabellada (65536). ¿Cómo arreglarlo? Podemos dividir los datos de entrada en varias partes, calcular el número de elementos distintos de cada parte y al final hacer la media de todo. Podríamos decidir según el primer carácter de nuestro identificador. Así, calculamos por separado el número de valores distintos de los identificadores que empiezan por la letra «a», luego de los que empiezan por la letra «b», etc. Código:

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)

Los cambios están en la función count_unique_using_minimum. En la variable min_values guardamos los mínimos de cada grupo. Al final sumamos todos los mínimos y los dividimos entre el número de valores guardados: obtenemos el mínimo medio. Con la expresión 1/average_minimum averiguamos cuál es el número medio de valores distintos de cada grupo; multiplicamos este valor por el número de grupos y obtenemos el número estimado de valores distintos del conjunto de datos recibido. ¿Y cómo funciona este procedimiento modificado?

11312
7504
10560
8160
9344
12688
10976
11616
16240
6832

Pues sigue sin ser bueno, pero desde luego es mejor. El algoritmo es más estable. Podemos probar a modificar la función para que los grupos no se formen según el primer carácter, sino, por ejemplo, según los dos primeros caracteres del identificador, es decir, así:

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

Los resultados serían entonces estos:

9728
9728
9984
10240
8960
10752
9728
9472
11264
9472

Vaya, esto ya no está nada mal, ¿no? Si probamos además con cien mil valores distintos, los dos primeros caracteres y n = 24, obtenemos estos resultados:

103936
110080
102656
101120
101376
108288
97536
97024
107776
92416

Pasable. Pero todavía existen algoritmos mejores, no te preocupes.

¿Y el consumo de memoria? Tenemos que guardar el mínimo de cada grupo, nada más. Si los identificadores están en formato hexadecimal, eso significa que tenemos que recordar como máximo 16^x mínimos, donde x es el número de caracteres con los que formamos la clave del grupo. Un mínimo es un número racional, es decir, un tipo double o float.

Una nota final: hemos podido permitirnos dividir la entrada en varios grupos porque la entrada eran identificadores que se comportaban como una cadena aleatoria. Si la entrada no fuera una cadena aleatoria, sino datos con un formato determinado, tendríamos que hacer la división de otra manera. Si, por ejemplo, cada identificador empezara por el prefijo userid-, la división en grupos según el primer carácter probablemente no funcionaría demasiado bien, ¿no crees?