Wie kann ich anhand einer zufälligen Datenstichprobe die Anzahl der eindeutigen Vorkommen abschätzen?

15

Angenommen, ich habe eine große Menge von Werten, die sich manchmal wiederholen. Ich möchte die Gesamtzahl der eindeutigen Werte in der großen Menge schätzen .S

Wenn ich eine zufällige Stichprobe von nehme - Werte und bestimmen , dass es enthält T u eindeutige Werte, kann ich dies die Anzahl der eindeutigen Werte in der großen Menge zu schätzen?TTu

estimation sampling geistige Gesundheit
quelle
1
Können Sie auch die Anzahl der Kopien jedes einzelnen Werts in der Stichprobe zählen? Fällt mir auf, das könnte helfen.
onestop
@onestop, ja, ich könnte das tun
Vernunft

Antworten:

11

Hier ist ein ganzer Artikel über das Problem mit einer Zusammenfassung verschiedener Ansätze. Es heißt Distinct Value Estimation in der Literatur.

Wenn ich das selbst tun müsste, ohne ausgefallene Papiere gelesen zu haben, würde ich das tun. Bei der Erstellung von Sprachmodellen muss man häufig die Wahrscheinlichkeit abschätzen, ein zuvor unbekanntes Wort zu beobachten, wenn eine Reihe von Texten vorliegt. Ein ziemlich guter Ansatz, um dieses Problem insbesondere für Sprachmodelle zu lösen, besteht darin, die Anzahl der Wörter, die genau einmal vorkamen, dividiert durch die Gesamtzahl der Token, zu verwenden. Man nennt es die Schätzung der guten Türe .

Sei u1 die Anzahl der Werte, die genau einmal in einer Stichprobe von m Elementen vorkamen.

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

Sei u die Anzahl der Einzelstücke in Ihrer Stichprobe der Größe m.

Wenn Sie fälschlicherweise davon ausgehen, dass die Rate für das nächste Element nicht gesunken ist, wenn Sie mehr Daten erhalten haben, können Sie Good Turing verwenden

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

Dies hat ein unangenehmes Verhalten, da u1 sehr klein wird, aber in der Praxis ist dies möglicherweise kein Problem für Sie.

rrenaud
quelle
was ist sin diesem fall die Gesamtzahl der Wörter?
Nathan
Tritt das tatsächlich szweimal auf, sowohl bei der linken als auch bei der rechten Handgröße?
PascalVKooten
1

Die Simulationsstrategie

Collect m Stichproben der Größe N aus dem Satz S . Für jeden derBerechnen Sie m Abtastwerte die Anzahl u der eindeutigen Werte und dividieren Sie sie durch n, um sie zu normalisieren. Berechnen Sie aus der simulierten Verteilung von normalisiertem u zusammenfassende Statistiken von Interesse (z. B. Mittelwert, Varianz, Interquartilbereich). Multiplizieren Sie den simulierten Mittelwert von normalisiertem u mit der Kardinalität von S , um die Anzahl der eindeutigen Werte abzuschätzen.

Je größer m und n sind , desto genauer stimmt Ihr simulierter Mittelwert mit der tatsächlichen Anzahl eindeutiger Werte überein.

Dreistes Gleichgewicht
quelle
1
Ist diese Lösung nicht lahm? Sättigungseffekte werden dabei überhaupt nicht berücksichtigt.
Wiederholung
@rrenaud Im Vergleich zu Ihrer Lösung stimme ich zu, dass meine minderwertig erscheint.
Brash Equilibrium
@rrenaud Ich befürworte immer noch eine Simulationsstrategie, bei der Sie die Wahrscheinlichkeit eindeutiger Elemente mithilfe der GTFE anhand von möglichst großen Stichproben berechnen, um einen Eindruck von Stichprobenfehlern für die Wahrscheinlichkeit eindeutiger Elemente zu erhalten. Oder gibt es eine explizite Formel, um alle Momente zu berechnen? Ich würde nicht denken, dass es sich um das negative Binom handelt, da die Binomialverteilung laut Wikipedia-Referenz die Verteilung der Anzahl der eindeutigen Elemente nicht charakterisiert. Aber großartig! Ich werde das für später weglegen.
Brash Equilibrium
0

Hier ist eine Implementierung für 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

Stützt sich auf die Abschnitte 2 und 4 dieses Dokuments: http://ftp.cse.buffalo.edu/users/azhang/disc/disc01/cd1/out/papers/pods/towardsestimatimosur.pdf

PascalVKooten
quelle