Explications
On cherche à connaitre la taille d'un ensemble. Mais, problème, on a accès a seulement quelques éléments de cet ensemble.
Par exemple, j'ai en ma possession les pages 2, 3 et 6 d'un livre inconnu (bien entendu, vu que je vous donne l'explication, je connais déjà la taille du livre: il fait 8 pages, mais ça vous ne le savez pas encore). Et je dois deviner la taille la plus probable du livre auquel ces pages appartiennent.
La méthode est simple et intuitive : elle consiste a ajouter à la plus grande valeur des données fournies (ici les numéros des pages 2, 3 et 6) , la moyenne de chaque intervalle, en supposant que les numéros d'éléments que je connais sont distribuées uniformément.
Reprenons : mes données sont les numéros 2, 3 et 6. Leurs intervalles sont : 1 et 3. La moyenne de 1 et 3 vaut 2. La somme de 6 et 2 vaut 8. Le livre a donc 8 pages.
Autre exemple: si j'ai les deux valeurs 8 et 9, leur intervalle vaut 1. J'ajoute 1 à 9, la taille de l'ensemble est donc estimée à 10.
Si j'ai les valeurs 1, 6 et 9, le premier intervalle vaut 5 (distance entre 1 et 6), le second vaut 3(distance entre 6 et 9). La moyenne entre 5 et 3 vaut 4. J'ajoute 4 à 9, la taille de l'ensemble est donc estimée à 13.
L'algorithme est donc le suivant :
Ajouter à la valeur maximum la moyenne des valeurs absolues des différences par paires des données triées.
Nous allons à présent le transcrire en J.
Implémentation
Reprenons la définition de l'algorithme d'estimation : ajouter à la valeur maximum la moyenne des valeurs absolues des différences par paires des données triées.
On connait a priori la valence de chaque verbe. On peut immédiatement écrire l'algorithme en J :
En supposant que nous ayons défini chaque verbe ainsi :
On peut aussi l'écrire d'une traite dans le style tacite :
Utilisation
Retourne:
Soit la taille estimée totale de l'échantillon de donnée 2,3,6.
Test
On va tester la puissance de cette méthode d'estimation.
On choisi des ensemble de 50, 100, 200, 1000, et 10000 éléments.
Pour chaque ensemble, on choisi progressivement de 2% à 100% d'éléments au hasard.
On effectue l'estimation 100 fois de suite à chaque fois, et enfin, on moyenne le tout. On affiche l'évolution de la qualité de prédiction de l'estimation dans un graphique :
Ce qui donne :
On voit que très rapidement, quelque soit la taille de l'ensemble, que l'on est en dessous des 3% de marge d'erreur. Pas mal.
Variation
La même chose, en utilisant les sommes harmoniques :
Commentaires
Enregistrer un commentaire