Jak oszacować liczbę unikatowych zdarzeń na podstawie losowego próbkowania danych?

15

Powiedzmy, że mam duży zestaw wartości , które czasem się powtarzają. Chciałbym oszacować całkowitą liczbę unikalnych wartości w dużym zestawie.S.

Jeśli wezmę losową próbkę wartości, a także określić, że zawiera T Ü unikalne wartości, mogę to wykorzystać, aby oszacować liczbę unikatowych wartości w dużym zestawie?T.T.u

estimation sampling zdrowie psychiczne
źródło
1
Czy potrafisz również zliczać liczbę kopii każdej unikalnej wartości w próbce? Uderza mnie, że może pomóc.
onestop
@onstop, tak, mógłbym to zrobić
zdrowie psychiczne

Odpowiedzi:

11

Oto cały artykuł na temat problemu wraz z podsumowaniem różnych podejść. W literaturze nazywa się to Szacowaniem Wyróżniającej Wartości .

Gdybym musiał to zrobić sam, bez czytania fantazyjnych dokumentów, zrobiłbym to. Budując modele językowe, często trzeba oszacować prawdopodobieństwo zaobserwowania nieznanego wcześniej słowa, biorąc pod uwagę garść tekstu. Całkiem dobrym podejściem do rozwiązania tego problemu w szczególności w modelach językowych jest użycie liczby słów, które wystąpiły dokładnie raz, podzielonej przez całkowitą liczbę tokenów. To się nazywa Good Turing Estimate .

Niech u1 będzie liczbą wartości, które wystąpiły dokładnie raz w próbce m elementów.

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

Niech będzie liczbą unikalnych przedmiotów w Twojej próbce o rozmiarze m.

Jeśli błędnie założysz, że wskaźnik „nowy element następny” nie spadł, ponieważ masz więcej danych, to stosując Good Turing, będziesz mieć

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

Zachowuje się to paskudnie, ponieważ u1 staje się naprawdę mały, ale w praktyce może to nie stanowić problemu.

rrenaud
źródło
co jest sw tym przypadku? łączna liczba „słów”?
Nathan
Rzeczywiście, swystępuje w tym dwukrotnie, zarówno w rozmiarze lewej, jak i prawej ręki?
PascalVKooten
1

Strategia symulacji

Zbierać m losowych próbek o rozmiarze N ze zbioru S . Dla każdej z m próbek oblicz liczbę u niepowtarzalnych wartości i podziel przez n, aby normalizować. Na podstawie symulowanego rozkładu znormalizowanego u oblicz obliczeniowe statystyki podsumowujące zainteresowania (np. Średnia, wariancja, zakres międzykwartylowy). Pomnóż symulowaną średnią znormalizowaną u przez liczność S, aby oszacować liczbę unikalnych wartości.

Im większe są m i n , im ściślej symulowane średnie dopasuje prawdziwą liczbę unikatowych wartości.

Zuchwała równowaga
źródło
1
Czy to rozwiązanie nie jest kiepskie? W ogóle nie uwzględnia efektów nasycenia.
rrenaud
@rrenaud W porównaniu do twojego rozwiązania, zgadzam się, że moje wydaje się gorsze.
Brash Equilibrium
@rrenaud Nadal opowiadam się za strategią symulacji, w której obliczasz prawdopodobieństwo unikalnych przedmiotów za pomocą GTFE na tak wielu wykonalnych próbkach, jak to możliwe, aby uzyskać poczucie błędu próbkowania prawdopodobieństwa unikatowych przedmiotów. Czy istnieje wyraźna formuła do obliczania wszystkich chwil? Nie sądzę, że jest to ujemny dwumian, ponieważ rozkład dwumianowy, zgodnie z odniesieniem Wikipedii, nie charakteryzuje rozkładu liczby unikalnych przedmiotów. Ale super! Odłożę to na później.
Brash Equilibrium
0

Oto implementacja dla pand:

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

Opiera się na części 2 i 4 tego dokumentu: http://ftp.cse.buffalo.edu/users/azhang/disc/disc01/cd1/out/papers/pods/towardsestimatimosur.pdf

PascalVKooten
źródło