Bagaimana saya bisa memperkirakan jumlah kejadian unik dari pengambilan sampel data secara acak?

15

Katakanlah saya punya satu set besar S nilai yang kadang-kadang berulang. Saya ingin memperkirakan jumlah total nilai unik di set besar.

Jika saya mengambil sampel acak dari nilai-nilai, dan menentukan bahwa itu berisi T u nilai unik, saya dapat menggunakan ini untuk memperkirakan jumlah nilai unik dalam set besar?TTkamu

estimation sampling kewarasan
sumber
1
Bisakah Anda juga menghitung jumlah salinan dari setiap nilai unik dalam sampel? Membuatku kaget yang mungkin bisa membantu.
onestop
@onestop, ya saya bisa melakukan itu
kewarasan

Jawaban:

11

Berikut ini adalah keseluruhan makalah tentang masalah ini, dengan ringkasan berbagai pendekatan. Ini disebut Estimasi Nilai Berbeda dalam literatur.

Jika saya harus melakukan ini sendiri, tanpa membaca surat kabar mewah, saya akan melakukan ini. Dalam membangun model bahasa, kita sering harus memperkirakan probabilitas mengamati kata yang sebelumnya tidak diketahui, mengingat banyak teks. Pendekatan yang cukup bagus dalam memecahkan masalah ini untuk model bahasa khususnya adalah dengan menggunakan jumlah kata yang terjadi tepat sekali, dibagi dengan jumlah total token. Ini disebut Perkiraan Good Turing .

Biarkan u1 menjadi jumlah nilai yang terjadi tepat sekali dalam sampel item m.

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

Biarkan Anda menjadi jumlah item unik dalam sampel ukuran m Anda.

Jika Anda secara keliru menganggap bahwa tingkat 'item baru berikutnya' tidak berkurang karena Anda mendapatkan lebih banyak data, maka menggunakan Good Turing, Anda harus

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

Ini memiliki beberapa perilaku buruk karena Anda menjadi sangat kecil, tetapi itu mungkin tidak menjadi masalah bagi Anda dalam praktik.

Radenud
sumber
apa yang ada sdalam kasus ini? jumlah total 'kata-kata'?
Nathan
Memang, sterjadi dua kali dalam hal ini, baik pada ukuran tangan kiri dan kanan?
PascalVKooten
1

Strategi simulasi

Kumpulkan m sampel acak dengan ukuran n dari set S . Untuk masing-masing sampel m , hitung jumlah u dari nilai unik dan bagi dengan n untuk dinormalisasi. Dari distribusi simulasi u dinormalisasi , hitung ringkasan statistik yang menarik (misalnya, rata-rata, varians, kisaran interkuartil). Kalikan simulasi rata-rata dinormalisasi u oleh kardinalitas S untuk memperkirakan jumlah nilai unik.

Semakin besar m dan n , semakin dekat rata-rata simulasi Anda akan cocok dengan jumlah sebenarnya dari nilai unik.

Keseimbangan kurang ajar
sumber
1
Bukankah ini semacam solusi lumpuh? Itu tidak memperhitungkan efek saturasi akun sama sekali.
rrenaud
@rrenaud Dibandingkan dengan solusi Anda, saya setuju bahwa milik saya tampak lebih rendah.
Brash Equilibrium
@rrenaud Saya masih menganjurkan strategi simulasi di mana Anda menghitung probabilitas barang-barang unik menggunakan GTFE pada sampel besar-sebagai-layak-sebanyak-layak-sebagai-layak untuk mendapatkan beberapa rasa kesalahan pengambilan sampel untuk kemungkinan barang-barang unik. Atau adakah formula eksplisit untuk menghitung semua momen? Saya tidak akan berpikir itu adalah binomial negatif karena distribusi binomial, menurut referensi Wikipedia, tidak mencirikan distribusi jumlah item unik. Tapi luar biasa! Saya akan menyimpan ini untuk nanti.
Brash Equilibrium
0

Berikut ini adalah implementasi untuk panda:

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

Bergantung pada Bagian 2 dan 4 tulisan ini: http://ftp.cse.buffalo.edu/users/azhang/disc/disc01/cd1/out/papers/pods/towardsestimatimosur.pdf

PascalVKooten
sumber