Comment estimer le nombre d'occurrences uniques à partir d'un échantillonnage aléatoire de données?

Disons que j'ai un grand ensemble de valeurs qui se répètent parfois. Je souhaite estimer le nombre total de valeurs uniques dans le grand ensemble.$S$

Si je prends un échantillon aléatoire de valeurs et détermine qu'il contient des valeurs uniques , puis-je l'utiliser pour estimer le nombre de valeurs uniques dans le grand ensemble?$T$$T_u$

Voici un document complet sur le problème, avec un résumé des différentes approches. Cela s'appelle Distinct Value Estimation dans la littérature.

Si je devais le faire moi-même, sans avoir lu de papiers fantaisistes, je le ferais. Dans la construction de modèles de langage, il faut souvent estimer la probabilité d'observer un mot inconnu auparavant, étant donné un tas de texte. Une assez bonne approche pour résoudre ce problème pour les modèles de langage en particulier consiste à utiliser le nombre de mots qui se sont produits exactement une fois, divisé par le nombre total de jetons. C'est ce qu'on appelle la bonne estimation de Turing .

Soit u1 le nombre de valeurs qui se sont produites exactement une fois dans un échantillon de m éléments.

P[new item next] ~= u1 / m.

Soit u le nombre d'articles uniques dans votre échantillon de taille m.

Si vous supposez à tort que le taux de `` nouvel article suivant '' n'a pas diminué à mesure que vous avez obtenu plus de données, alors en utilisant Good Turing, vous aurez

total uniq set of size s ~= u + u1 / m * (s - m) 

Cela a un comportement désagréable car u1 devient vraiment petit, mais cela pourrait ne pas être un problème pour vous dans la pratique.

La stratégie de simulation

Collect m échantillons aléatoires de taille n de l'ensemble S . Pour chacun des m échantillons, calculez le nombre u de valeurs uniques et divisez par n pour normaliser. À partir de la distribution simulée de u normalisé , calculer des statistiques sommaires d'intérêt (p. Ex. Moyenne, variance, plage interquartile). Multipliez la moyenne simulée de u normalisé par la cardinalité de S pour estimer le nombre de valeurs uniques.

Plus m et n sont élevés , plus votre moyenne simulée correspondra étroitement au nombre réel de valeurs uniques.

Voici une implémentation pour les pandas:

import math
import numpy as np
from collections import Counter

def estimate_uniqueness(df, col, r=10000, n=None):
    """ Draws a sample of size r from column col from dataframe df and 
        returns an estimate for the number of unique values given a
        population size of n """
    n = n or df.shape[0]
    sample = df[col][np.random.randint(0, n, r)]
    counts = sample.value_counts()
    fis = Counter(counts)
    estimate = math.sqrt(n / r) * fis[1] + sum([fis[x] for x in fis if x > 1])
    return estimate

Se base sur les sections 2 et 4 de ce document: http://ftp.cse.buffalo.edu/users/azhang/disc/disc01/cd1/out/papers/pods/towardsestimatimosur.pdf