Min Value : comment estimer le nombre de valeurs distinctes

Dans l’article précédent sur le Linear Counting, nous avons vu les algorithmes de base pour calculer et estimer le nombre de valeurs distinctes dans un ensemble de données. Aujourd’hui, un autre algorithme probabiliste nous attend : il permet d’estimer le nombre de valeurs distinctes avec une précision correcte et très peu de mémoire.

Min Value

Dans cet article, nous allons travailler uniquement avec des nombres réels de l’intervalle unité ]0 ; 1[. Imaginons un ensemble de nombres de cet intervalle, régulièrement répartis, par exemple l’ensemble de nombres {0,25 ; 0,5 ; 0,75}. Deux nombres voisins sont toujours séparés (et séparés de zéro et de un) d’exactement 0,25. En quoi cela nous aide-t-il à compter le nombre d’éléments distincts ?

Si je te dis que nous avons un tel ensemble de nombres de l’intervalle unité, régulièrement répartis, et que la distance entre deux nombres voisins est exactement 0,2 — peux-tu calculer combien d’éléments contient cet ensemble ? Bien sûr, il s’agit de l’ensemble {0,2 ; 0,4 ; 0,6 ; 0,8}, dont le cardinal est égal à quatre. Si l’entrée est constituée de nombres de l’intervalle unité régulièrement répartis et si nous connaissons la distance entre deux nombres voisins, nous pouvons facilement calculer le nombre d’éléments.

Or la distance entre deux nombres voisins est égale au plus petit élément de l’ensemble — la distance entre deux éléments voisins de l’ensemble {0,25 ; 0,5 ; 0,75} est 0,25, etc. Pour calculer le nombre d’éléments d’un ensemble de nombres régulièrement répartis, il nous suffit donc de trouver d’une manière ou d’une autre le plus petit élément. Nous pouvons alors calculer le nombre d’éléments p avec une formule simple :

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

où m est ce plus petit élément.

Et encore une fois, nous allons hacher…

Oui, mais comment s’en servir si l’entrée est constituée de chaînes ou d’autres valeurs qui ne sont pas régulièrement réparties dans l’intervalle unité ? Nous nous aidons de nouveau de la bonne vieille fonction de hachage, qui peut, pour n’importe quelle entrée, nous renvoyer un nombre rationnel de l’intervalle unité. Construire une telle fonction de hachage est facile.

Nous obtiendrions ainsi des nombres rationnels à partir des données, mais comment faire pour que ces nombres soient régulièrement répartis ? Cela, ce ne sera pas possible, mais nous pouvons nous aider autrement. Du point de vue qui nous intéresse, la fonction de hachage se comporte en effet de façon plutôt « aléatoire ». Pour des mots très proches comme « salut », « salus » et « salue », la fonction de hachage nous renverra très probablement des sommes de contrôle (checksum) très différentes. En d’autres termes : si nous hachons mille valeurs différentes dans l’intervalle unité, il est très improbable que la grande majorité des nombres soient par exemple inférieurs à un demi. Il est au contraire très probable que ces nombres soient répartis plus ou moins régulièrement. Plus nous hachons de données, plus cette répartition sera régulière.

De cette idée, nous tirons un algorithme simple : on parcourt les données d’entrée, on hache chaque élément dans l’intervalle unité et on retient le plus petit élément. On estime le nombre de valeurs distinctes avec la formule précédente. Implémentation 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 fonction unit_interval_hash nous renvoie un nombre décimal de l’intervalle ]0 ; 1]. La fonction count_unique_using_minimum convertit d’abord toutes les valeurs d’entrée en un tel nombre, trouve le minimum et renvoie 1 / minimum - 1. Remarque que le nombre de valeurs identiques dans l’ensemble de données n’a aucune importance — pour deux valeurs identiques, la fonction de hachage nous renvoie le même nombre rationnel, ce qui n’influence en rien le minimum final. C’est pourquoi cet algorithme compte les éléments distincts.

Quels sont les résultats ? (Chaque ligne donne la cardinalité estimée, alors que la cardinalité exacte est 10 000.)

5957
16384
13107
9362
65536
8192
21845
13107
21845
8192

Bof, pas terrible, n’est-ce pas ? L’algorithme a parcouru dix ensembles différents d’identifiants, contenant chacun dix mille valeurs distinctes. Les estimations obtenues sont donc pour la plupart assez loin de la réalité. Si nous en faisions la moyenne, nous arriverions à 18 352. C’est encore assez loin, mais d’un autre côté, regarde la consommation de mémoire — elle est constante ! Pour trouver le minimum, il te suffit de garder en mémoire une seule variable, dans laquelle tu stockes le minimum actuel, et c’est tout. Donc oui, l’estimation est nulle, mais en contrepartie cela ne coûte presque rien.

Amélioration

Nous voyons que l’algorithme est surtout instable — une fois il nous renvoie une estimation plutôt bonne (9 362), une autre fois une estimation complètement à côté de la plaque (65 536). Comment s’en sortir ? Nous pouvons nous aider en répartissant les données d’entrée en plusieurs parties, en calculant le nombre de valeurs distinctes pour chaque partie et en faisant enfin la moyenne de tout cela. Nous pourrions décider selon le premier caractère de notre identifiant. Nous calculons donc séparément le nombre de valeurs distinctes pour les identifiants qui commencent par la lettre « a », puis pour ceux qui commencent par la lettre « b », etc. Code :

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)

Les changements sont dans la fonction count_unique_using_minimum. Dans la variable min_values, nous conservons les minima de chaque groupe. À la fin, nous additionnons tous les minima et nous les divisons par le nombre de valeurs conservées — nous obtenons le minimum moyen. Avec l’expression 1/average_minimum, nous trouvons le nombre moyen de valeurs distinctes dans chaque groupe — nous multiplions encore cette valeur par le nombre de groupes et nous obtenons le nombre estimé de valeurs distinctes dans l’ensemble de données fourni. Et comment fonctionne ce procédé modifié ?

11312
7504
10560
8160
9344
12688
10976
11616
16240
6832

Bon, ce n’est toujours pas bon, mais c’est sûrement mieux. L’algorithme est plus stable. Nous pouvons essayer de modifier la fonction pour que les groupes ne soient pas formés d’après le premier caractère, mais par exemple d’après les deux premiers caractères de l’identifiant, c’est-à-dire ainsi :

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

Les résultats seraient alors les suivants :

9728
9728
9984
10240
8960
10752
9728
9472
11264
9472

Ouais, ce n’est déjà plus tout à fait mauvais, non ? Si nous essayons encore avec cent mille valeurs distinctes, les deux premiers caractères et n = 24, nous obtenons ces résultats :

103936
110080
102656
101120
101376
108288
97536
97024
107776
92416

Ça passe à peu près. Mais il existe encore de meilleurs algorithmes, ne t’inquiète pas.

Et quelle est la consommation de mémoire ? Nous devons conserver le minimum de chaque groupe, rien de plus. Si les identifiants sont au format hexadécimal, cela signifie que nous devons retenir au maximum 16^x minima, où x est le nombre de caractères avec lesquels nous formons la clé du groupe. Un minimum est un nombre rationnel, c’est-à-dire un type double ou float.

Remarque pour finir : nous avons pu nous permettre de répartir l’entrée en plusieurs groupes parce que nous avions en entrée des identifiants qui se comportaient comme une chaîne aléatoire. Si nous n’avions pas en entrée une chaîne aléatoire, mais des données d’un certain format, il faudrait faire la répartition autrement. Si par exemple chaque identifiant commençait par le préfixe userid-, la répartition en groupes d’après le premier caractère ne marcherait sans doute pas très bien, pas vrai ?