Como posso estimar contagens de ocorrências únicas a partir de uma amostragem aleatória de dados?

15

Digamos que tenho um grande conjunto de valores que às vezes se repetem. Desejo estimar o número total de valores únicos no conjunto grande.S

Se eu coletar uma amostra aleatória de valores e determinar que ele contém T uTTu valores exclusivos, posso usar isso para estimar o número de valores exclusivos no conjunto grande?

estimation sampling sanidade
fonte
1
Você também pode contar o número de cópias de cada valor exclusivo da amostra? Parece-me que pode ajudar.
Onestop 27/11
@onestop, sim eu poderia fazer isso #
sanity

Respostas:

11

Aqui está um artigo inteiro sobre o problema, com um resumo de várias abordagens. É chamado de estimativa de valor distinto na literatura.

Se eu tivesse que fazer isso sozinho, sem ter lido papéis sofisticados, faria isso. Na construção de modelos de linguagem, muitas vezes é preciso estimar a probabilidade de observar uma palavra anteriormente desconhecida, dado um monte de texto. Uma abordagem bastante boa para resolver esse problema, especialmente para os modelos de linguagem, é usar o número de palavras que ocorreram exatamente uma vez, dividido pelo número total de tokens. É chamado de estimativa de Good Turing .

Seja u1 o número de valores que ocorreram exatamente uma vez em uma amostra de m itens.

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

Seja u o número de itens únicos em sua amostra de tamanho m.

Se você erroneamente presumir que a taxa de 'novo item seguinte' não diminuiu à medida que você obteve mais dados, usando o Good Turing, você terá

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

Isso tem um comportamento desagradável quando o u1 se torna realmente pequeno, mas isso pode não ser um problema para você na prática.

rrenaud
fonte
o que é snesse caso? o número total de 'palavras'?
Nathan
De fato, socorre duas vezes nisso, tanto no tamanho da mão esquerda quanto da direita?
PascalVKooten
1

A estratégia de simulação

Recolha m amostras aleatórias de tamanho n a partir do conjunto de S . Para cada uma das m amostras, calcule o número u de valores exclusivos e divida por n para normalizar. A partir da distribuição simulada de u normalizado , calcule as estatísticas resumidas de interesse (por exemplo, média, variância, intervalo interquartil). Multiplique a média simulada de u normalizado pela cardinalidade de S para estimar o número de valores únicos.

Quanto maiores são m e n , mais próxima sua média simulada corresponderá ao número real de valores únicos.

Equilíbrio Brash
fonte
1
Essa solução não é meio idiota? Ele não leva em consideração os efeitos de saturação.
Rdenaud
@renaena Comparado à sua solução, concordo que a minha parece inferior.
Equilíbrio Brash
@rrenaud Eu ainda defendo uma estratégia de simulação na qual você calcula a probabilidade de itens únicos usando o GTFE em amostras tão grandes quanto possível para obter algum senso de erro de amostragem quanto à probabilidade de itens únicos. Ou existe uma fórmula explícita para calcular todos os momentos? Não acho que seja o binômio negativo, pois a distribuição binomial, de acordo com a referência da Wikipedia, não caracteriza a distribuição do número de itens exclusivos. Mas demais! Vou arquivar isso para mais tarde.
Equilíbrio Brash
0

Aqui está uma implementação para os 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

Baseia-se nas seções 2 e 4 deste documento: http://ftp.cse.buffalo.edu/users/azhang/disc/disc01/cd1/out/papers/pods/towardsestimatimosur.pdf

PascalVKooten
fonte