Как я могу оценить уникальные числа случаев по случайной выборке данных?

Допустим, у меня есть большой набор значений которые иногда повторяются. Я хочу оценить общее количество уникальных значений в большом наборе.$S$

Если я возьму случайную выборку значений и определю, что она содержит уникальные значения T u , могу ли я использовать это для оценки количества уникальных значений в большом наборе?$T$$T_u$

Вот целая статья о проблеме с кратким изложением различных подходов. В литературе это называется « Оценка отличительного значения» .

Если бы мне пришлось делать это самому, не читая фантастических статей, я бы сделал это. При построении языковых моделей часто приходится оценивать вероятность наблюдения ранее неизвестного слова, учитывая кучу текста. Довольно хороший подход к решению этой проблемы, в частности, для языковых моделей, состоит в том, чтобы использовать количество слов, которые встречались ровно один раз, деленное на общее количество токенов. Это называется оценка хорошего Тьюринга .

Пусть u1 будет количеством значений, которые встречались ровно один раз в выборке из m элементов.

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

Пусть u будет количеством уникальных предметов в вашей выборке размером m.

Если вы ошибочно предполагаете, что показатель «новый элемент следующий» не уменьшился при получении большего количества данных, то при использовании Good Turing вы получите

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

Это имеет неприятное поведение, так как u1 становится действительно маленьким, но на практике это может не быть проблемой для вас.

Стратегия симуляции

Сбор т случайных выборок размера п из множества S . Для каждой из m выборок вычислите число уникальных значений u и разделите на n для нормализации. Из смоделированного распределения нормализованного u вычислите итоговую статистику, представляющую интерес (например, среднее значение, дисперсия, межквартильный диапазон). Умножьте смоделированное среднее значение нормализованного u на мощность S, чтобы оценить количество уникальных значений.

Чем больше m и n , тем ближе ваше симулированное среднее будет соответствовать истинному числу уникальных значений.

Вот реализация для панд:

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

Полагается на разделы 2 и 4 этого документа: http://ftp.cse.buffalo.edu/users/azhang/disc/disc01/cd1/out/papers/pods/towardsestimatimosur.pdf