Wie schätze ich Parameter für die abgeschnittene Zipf-Verteilung aus einer Datenprobe?

Ich habe ein Problem mit dem Schätzparameter für Zipf. Meine Situation ist folgende:

Ich habe einen Beispielsatz (gemessen aus einem Experiment, das Aufrufe generiert, die einer Zipf-Verteilung folgen sollten). Ich muss zeigen, dass dieser Generator wirklich Anrufe mit zipf-Verteilung generiert. Ich habe diese Fragen und Antworten bereits gelesen. Wie berechnet man den Zipf-Gesetzkoeffizienten aus einer Reihe von Spitzenfrequenzen? aber ich erreiche schlechte Ergebnisse, weil ich eine abgeschnittene Verteilung verwende. Wenn ich zum Beispiel den Wert "s" für den Generierungsprozess auf "0,9" setze und versuche, den Wert "s" zu schätzen, wie in den gemeldeten Fragen und Antworten angegeben, erhalte ich "s" gleich 0,2. Ich denke, das liegt an der Tatsache, dass ich eine TRUNCATED-Distribution verwende (ich muss das zipf mit einem Kürzungspunkt begrenzen, es ist rechts abgeschnitten).

Wie kann ich Parameter mit einer abgeschnittenen zipf-Verteilung schätzen?

distributions estimation pareto-distribution zipf Maurizio
quelle

um klar zu sein, was genau schneidest du richtig ab? Die Verteilung der Werte oder das Zipf-Diagramm selbst? Kennen Sie den Kürzungspunkt? Ist die Kürzung ein Artefakt der Daten oder ein Artefakt der Datenverarbeitung (z. B. eine Entscheidung, die Sie oder der Experimentator getroffen haben)? Alle zusätzlichen Details wären hilfreich.

Kardinal

@Kardinal. (Teil 1/2) Danke Kardinal. Ich werde weitere Details angeben: Ich habe einen VoIP-Generator, der Anrufe nach dem Zipf (und einer anderen Verteilung) für die Lautstärke pro Anrufer generiert. Ich muss überprüfen, ob dieser Generator diesen Verteilungen wirklich folgt. Für die Zipf-Verteilung muss der Kürzungspunkt definiert werden (daher ist er bekannt und bezieht sich auf die Verteilung der Werte). Dies ist die maximale Anzahl der vom Benutzer generierten Anrufe und der Skalierungsparameter. Insbesondere in meinem Fall ist dieser Wert gleich 500, was bedeutet, dass ein Benutzer maximal 500 Anrufe generieren kann.

Maurizio

(Teil 2/2) Der andere einzustellende Parameter ist der Skalierungsparameter für Zipf, der die Streuung der Verteilung definiert (dieser Wert ist in meinem Fall 0,9). Ich habe alle Parameter (Stichprobengröße, Häufigkeit pro Benutzer usw.), muss jedoch überprüfen, ob mein Datensatz der zipf-Verteilung entspricht.

Maurizio

Sie normalisieren also anscheinend die Verteilung um

, da für das, was ich als "abgeschnittenes Zipf" betrachten würde, ein Skalierungsparameter von 0,9 unmöglich wäre. Wenn Sie viele dieser Daten generieren können und "nur" 500 mögliche Ergebnisse haben, warum nicht einfach einen Chi-Quadrat-Anpassungstest verwenden? Da Ihre Distribution einen Long-Tail hat, benötigen Sie möglicherweise eine ziemlich große Stichprobe. Aber das wäre eine Möglichkeit. Eine andere schnelle und schmutzige Methode wäre, zu überprüfen, ob Sie die richtige empirische Verteilung für kleine Werte der Anzahl der Anrufe erhalten.

\sum_{i = 1}^{500} i^{- 0.9}

$\sum_{i=1}^{500} i^{-0.9}$

Kardinal

Antworten:

Update : 7. April 2011 Diese Antwort wird ziemlich lang und deckt mehrere Aspekte des vorliegenden Problems ab. Bisher habe ich mich jedoch geweigert, es in separate Antworten aufzuteilen.

Ich habe ganz unten eine Diskussion über die Leistung von Pearson's für dieses Beispiel hinzugefügt . $\chi^2$

Bruce M. Hill hat vielleicht das "wegweisende" Papier über die Schätzung in einem Zipf-ähnlichen Kontext verfasst. Mitte der 1970er Jahre schrieb er mehrere Artikel zu diesem Thema. Der "Hill Estimator" (wie er jetzt genannt wird) stützt sich jedoch im Wesentlichen auf die maximale Ordnungsstatistik der Stichprobe. Je nach Art der vorhandenen Kürzung kann dies zu Problemen führen.

Das Hauptpapier ist:

BM Hill, Ein einfacher allgemeiner Ansatz zur Schlussfolgerung über den Schwanz einer Verteilung , Ann. Stat. 1975.

Wenn Ihre Daten anfänglich wirklich Zipf sind und dann abgeschnitten werden, kann eine nette Entsprechung zwischen der Gradverteilung und dem Zipf-Diagramm zu Ihrem Vorteil genutzt werden.

d_{i} = \frac{# {j : X_{j} = i}}{n} .

$d_i = \frac{\#\{j: X_j = i\}}{n} .$

$i$

Wenn wir dagegen das Zipf-Diagramm zeichnen , bei dem wir die Stichprobe vom größten zum kleinsten sortieren und dann die Werte gegen ihre Ränge zeichnen, erhalten wir einen anderen linearen Trend mit einer anderen Steigung. Die Pisten sind jedoch verwandt.

$\alpha$ $-\alpha$ $-1/(\alpha-1)$ $\alpha = 2$ $n = 10^6$ $-2$ $-1/(2-1) = -1$

Gradverteilungsdiagramme (links) und Zipf-Diagramme (rechts) für eine iid-Stichprobe aus einer Zipf-Verteilung.

$\tau$ $\tau$ $\alpha$

$\hat{\beta}$

\hat{α} = 1 - \frac{1}{\hat{β}} .

$\hat{\alpha} = 1 - \frac{1}{\hat{\beta}} .$

@csgillespie gab kürzlich einen von Mark Newman in Michigan mitverfassten Artikel zu diesem Thema. Er scheint viele ähnliche Artikel darüber zu veröffentlichen. Unten finden Sie eine weitere zusammen mit einigen anderen Referenzen, die von Interesse sein könnten. Newman macht statistisch gesehen manchmal nicht das Vernünftigste, seien Sie also vorsichtig.

MEJ Newman, Potenzgesetze, Pareto-Verteilungen und Zipf-Gesetz , Contemporary Physics 46, 2005, S. 323-351.

M. Mitzenmacher, Eine kurze Geschichte generativer Modelle für Potenzrecht und logarithmische Normalverteilungen , Internet Math. vol. 1, nein. 2, 2003, S. 226-251.

K. Knight, Eine einfache Modifikation des Hill-Schätzers mit Anwendungen auf Robustheit und Bias-Reduktion , 2010.

Nachtrag :

$R$ $10^5$

> x <- (1:500)^(-0.9)
> p <- x / sum(x)
> y <- sample(length(p), size=100000, repl=TRUE, prob=p)
> tab <- table(y)
> plot( 1:500, tab/sum(tab), log="xy", pch=20, 
        main="'Truncated' Zipf simulation (truncated at i=500)",
        xlab="Response", ylab="Probability" )
> lines(p, col="red", lwd=2)

Das resultierende Diagramm ist

Zipf-Plot "abgeschnitten" (abgeschnitten bei i = 500)

$i \leq 30$

Aus praktischer Sicht sollte eine solche Handlung jedoch relativ überzeugend sein.

$\alpha = 2$ $n = 300\,000$ $x_{\mathrm{max}} = 500$

$\chi^2$

X^{2} = \sum_{i = 1}^{500} \frac{(O_{i} - E_{i})^{2}}{E_{i}}

$X^2 = \sum_{i=1}^{500} \frac{(O_i - E_i)^2}{E_i}$

O_{i}

$O_i$

i

$i$

E_{i} = n p_{i} = n i^{- α} / \sum_{j = 1}^{500} j^{- α}

$E_i = n p_i = n i^{-\alpha} / \sum_{j=1}^{500} j^{-\alpha}$

Wir berechnen auch eine zweite Statistik, die erstellt wird, indem zuerst die Anzahl in Bins der Größe 40 zusammengefasst wird, wie in Maurizios Tabelle gezeigt (der letzte Bin enthält nur die Summe von zwanzig separaten Ergebniswerten.

$n$ $p$

$p$

Geben Sie hier die Bildbeschreibung ein

$R$

# Chi-square testing of the truncated Zipf.

a <- 2
n <- 300000
xmax <- 500

nreps <- 5000

zipf.chisq.test <- function(n, a=0.9, xmax=500, bin.size = 40)
{
  # Make the probability vector
  x <- (1:xmax)^(-a)
  p <- x / sum(x)

  # Do the sampling
  y <- sample(length(p), size=n, repl=TRUE, prob=p)

  # Use tabulate, NOT table!
  tab <- tabulate(y,xmax)

  # unbinned chi-square stat and p-value
  discrepancy <- (tab-n*p)^2/(n*p)
  chi.stat <- sum(discrepancy)
  p.val    <- pchisq(chi.stat, df=xmax-1, lower.tail = FALSE)

  # binned chi-square stat and p-value
  bins <- seq(bin.size,xmax,by=bin.size)
  if( bins[length(bins)] != xmax )
    bins <- c(bins, xmax)

  tab.bin  <- cumsum(tab)[bins]
  tab.bin <- c(tab.bin[1], diff(tab.bin))

  prob.bin <- cumsum(p)[bins] 
  prob.bin <- c(prob.bin[1], diff(prob.bin))

  disc.bin <- (tab.bin - n*prob.bin)^2/(n * prob.bin)
  chi.stat.bin <- sum(disc.bin)
  p.val.bin <- pchisq(chi.stat.bin, df=length(tab.bin)-1, lower.tail = FALSE)

  # Return the binned and unbineed p-values
  c(p.val, p.val.bin, chi.stat, chi.stat.bin)
}

set.seed( .Random.seed[2] )

all <- replicate(nreps, zipf.chisq.test(n, a, xmax))

par(mfrow=c(2,1))
hist( all[1,], breaks=20, col="darkgrey", border="white",
      main="Histogram of unbinned chi-square p-values", xlab="p-value")
hist( all[2,], breaks=20, col="darkgrey", border="white",
      main="Histogram of binned chi-square p-values", xlab="p-value" )

type.one.error <- rowMeans( all[1:2,] < 0.05 )

Kardinal
quelle

+1, tolle Antwort wie immer. Sie sollten sich als Moderator nominieren, es bleibt noch 1 Stunde :)

mpiktas

@mpiktas, danke für die Komplimente und die Ermutigung. Ich bin mir nicht sicher, ob ich es rechtfertigen könnte, mich mit der bereits sehr starken Liste von Kandidaten zu nominieren, die einheitlich umfangreicher und länger als ich teilgenommen haben.

Kardinal

@cardinal, hier sind einige Links zur Alternative zu Hill's Estimator: Originalartikel von Paulauskas und Follow-ups von Vaiciulis und Gadeikis und Paulauskas . Dieser Schätzer hatte angeblich bessere Eigenschaften als der ursprüngliche Hill's.

mpiktas

@mpiktas, danke für die Links. Es gibt einige "neue und verbesserte" Versionen des Hill-Schätzers. Der Hauptnachteil des ursprünglichen Ansatzes besteht darin, dass eine Auswahl von "Cutoff" erforderlich ist, um die Mittelwertbildung zu stoppen. Ich denke, das wurde meistens durch "Augapfel" gemacht, was einen für Anklagen der Subjektivität öffnet. Wenn ich mich recht erinnere, wird dies in einem von Resnicks Büchern über Long-Tailed-Distributionen ausführlich behandelt. Ich denke, es ist seine neuere.

Kardinal

@ Cardinal, vielen Dank, Sie sind sehr nett und sehr detailliert! Ihr Beispiel in R war für mich sehr nützlich, aber wie kann ich in diesem Fall einen formalen Chi-Quadrat-Test durchführen? (Ich habe den Chi-Quadrat-Test mit anderen Verteilungen wie Uniform, Exponential, Normal verwendet, aber ich habe viele Zweifel an der Zipf. Tut mir leid, aber dies ist meine erste Herangehensweise an diese Themen). Frage an die Modetatoren: Muss ich eine weitere Frage und Antwort schreiben wie "Wie führe ich einen Chi-Quadrat-Test für eine abgeschnittene Zipf-Verteilung durch?" oder weiter in diesen Fragen und Antworten, vielleicht Tags und Titel aktualisieren?

Maurizio

Das Papier

Clauset, A et al. , Potenzgesetzverteilungen in empirischen Daten . 2009

enthält eine sehr gute Beschreibung der Vorgehensweise beim Anpassen von Potenzgesetzmodellen. Die zugehörige Webseite enthält Codebeispiele. Leider gibt es keinen Code für abgeschnittene Distributionen, aber es kann Ihnen einen Zeiger geben.

Im Übrigen wird in dem Artikel die Tatsache erörtert, dass viele "Potenzgesetz-Datensätze" mit den Log-Normal- oder Exponentialverteilungen gleich gut (und in einigen Fällen besser) modelliert werden können!

csgillespie
quelle

Leider sagt dieses Papier nichts über die abgeschnittene Verteilung aus. Ich habe einige Pakete in R gefunden, die sich auf einfache Weise mit Zipf-Schätzparametern befassen (zipfR, VGAM), aber die abgeschnittene Verteilung benötigt eine "spezielle Behandlung". Meinten Sie mit Ihrem letzten Satz, dass es möglich ist, einen Potenzgesetz-Datensatz mit einer z. B. Exponentialverteilung zu modellieren und dann einen Schätzparameterprozess für die "abgeschnittene" Exponentialverteilung anzuwenden? Ich bin ein Neuling in diesem Thema!

Maurizio

In der Arbeit analysieren die Autoren verschiedene Datensätze, bei denen ein Potenzgesetz angepasst wurde. Die Autoren weisen darauf hin, dass das Potenzgesetzmodell in einigen Fällen nicht so gut ist und eine alternative Verteilung besser wäre.

Csgillespie

Nach der detaillierten Antwort des Benutzerkardinals führte ich den Chi-Quadrat-Test für meine vermutete abgeschnittene Zipf-Verteilung durch. Die Ergebnisse des Chi-Quadrat-Tests sind in der folgenden Tabelle angegeben:

Geben Sie hier die Bildbeschreibung ein

Wenn StartInterval und EndInterval beispielsweise den Anrufbereich darstellen und Observed die Anzahl der Anrufer ist, die 0 bis 19 Anrufe usw. generieren. Der Chi-Quadrat-Test ist gut, bis die letzten Spalten erreicht sind, und erhöht das Finale Berechnung, ansonsten war bis zu diesem Zeitpunkt der "partielle" Chi-Quadrat-Wert akzeptabel!

Bei anderen Tests ist das Ergebnis dasselbe, die letzte Spalte (oder die letzten 2 Spalten) erhöht immer den Endwert und ich weiß nicht warum und ich weiß nicht, ob (und wie) ein anderer Validierungstest verwendet wird.

PS: Der Vollständigkeit halber folge ich zur Berechnung der erwarteten Werte ( erwartet ) dem Vorschlag des Kardinals folgendermaßen:

Geben Sie hier die Bildbeschreibung ein

wo X_i 's zu berechnen , sind: x <- (1:n)^-Sdie P_i s berechnen p <- x / sum(x)die und schließlich E_i wird (Erwartete nr der Benutzer für jeden der Anrufe nr) , erhalten durchP_i * Total_Caller_Observed

und mit Freiheitsgrad = 13 lehnt die Chi-Quadrat-Güte immer die Hyphotese ab, dass der Probensatz der Zipf-Verteilung folgt, da die Teststatistik (in diesem Fall 64,14) größer ist als die in den Chi-Quadrat-Tabellen angegebene "Fehler". für die letzte Spalte. Das grafische Ergebnis wird hier angegeben: Geben Sie hier die Bildbeschreibung ein

Obwohl der Abschneidepunkt auf 500 eingestellt ist, ergibt sich ein Maximalwert von 294. Ich denke, dass die endgültige "Dispersion" die Ursache für das Scheitern des Chi-Quadrat-Tests ist.

AKTUALISIEREN!!

Ich versuche, den Chi-Quadrat-Test an einem mutmaßlichen Zipf-Datenmuster durchzuführen, das mit dem in der obigen Antwort angegebenen R-Code generiert wurde.

> x <- (1:500)^(-2)
> p <- x / sum(x)
> y <- sample(length(p), size=300000, repl=TRUE, prob=p)
> tab <- table(y)
> length(tab)
[1] 438
> plot( 1:438, tab/sum(tab), log="xy", pch=20, 
        main="'Truncated' Zipf simulation (truncated at i=500)",
        xlab="Response", ylab="Probability" )
> lines(p, col="red", lwd=2)

Das zugehörige Diagramm ist das folgende: Geben Sie hier die Bildbeschreibung ein

Die Chi-Quadrat-Testergebnisse sind in der folgenden Abbildung dargestellt: Geben Sie hier die Bildbeschreibung ein

und die Chi-Quadrat-Teststatistik (44,57) ist zu hoch für die Validierung mit dem gewählten Freiheitsgrad. Auch in diesem Fall ist die endgültige "Streuung" der Daten die Ursache für den hohen Chi-Quadrat-Wert. Aber es gibt ein Verfahren, um diese Zipf-Verteilung zu validieren (unabhängig von meinem "falschen" Generator möchte ich mich auf das R-Datenbeispiel konzentrieren) ???

Maurizio
quelle

@ Maurizio, aus irgendeinem Grund habe ich diesen Beitrag bis jetzt verpasst. Können Sie es trotzdem bearbeiten und ein Diagramm hinzufügen, das dem letzten in meinem Beitrag ähnelt, aber Ihre beobachteten Daten verwendet? Das könnte helfen, das Problem zu diagnostizieren. Ich glaube, ich habe eine andere Frage von Ihnen gesehen, bei der Sie Probleme hatten, eine gleichmäßige Verteilung zu erstellen. Vielleicht überträgt sich dies auch auf diese Analysen. (?) Grüße.

Kardinal

@ Cardinal, ich habe die Ergebnisse aktualisiert! Was denken Sie? Die Frage nach der gleichmäßigen Verteilung ist eine andere Sache, die ich besser spezifizieren muss und die ich heute oder morgen tun werde;)

Maurizio

S = 0.9

$S = 0.9$

p = P (X_{i} = 500) \approx 4.05 \times 10^{- 4}

$p = \mathbb{P}(X_i = 500) \approx 4.05 \times 10^{-4}$

n = 8454

$n = 8454$

8454 \cdot 4.05 \cdot 10^{- 4} \approx 3.43

$8454 \cdot 4.05 \cdot 10^{-4} \approx 3.43$

1 - (1 - 0.000405)^{8454} \approx 0.9675

$1 - (1 - 0.000405)^{8454} \approx 0.9675$ . Beachten Sie, wie genau dies mit der obigen Simulation übereinstimmt.

Kardinal

@cardinal, ich denke auch, dass etwas "falsch" in der Generierungsprozedur ist (mein Ziel ist es zu validieren, dass dieser Generator wirklich der Zipf-Verteilung folgt). Ich muss in diesen Tagen mit den Designern des Projekts sprechen.

Maurizio