¿Cómo estimar los parámetros para la distribución truncada Zipf a partir de una muestra de datos?

Tengo un problema con el parámetro de estimación para Zipf. Mi situación es la siguiente:

Tengo un conjunto de muestra (medido a partir de un experimento que genera llamadas que deberían seguir una distribución Zipf). Tengo que demostrar que este generador realmente genera llamadas con distribución zipf. Ya leí estas preguntas y respuestas ¿Cómo calcular el coeficiente de ley de Zipf a partir de un conjunto de frecuencias máximas? pero alcanzo malos resultados porque uso una distribución truncada. Por ejemplo, si configuro el valor "s" en "0.9" para el proceso de generación, si trato de estimar el valor "s" como se escribió en las preguntas y respuestas reportadas, obtengo una "s" igual a 0.2 ca. Creo que esto se debe al hecho de que uso una distribución TRUNCADA (tengo que limitar el zipf con un punto de truncamiento, está truncado a la derecha).

¿Cómo puedo estimar parámetros con una distribución zipf truncada?

distributions estimation pareto-distribution zipf Maurizio
fuente

para ser claros, ¿qué es exactamente lo que estás truncando? ¿La distribución de valores o la propia trama Zipf? ¿Conoces el punto de truncamiento? ¿Es el truncamiento un artefacto de los datos o un artefacto del procesamiento de datos (por ejemplo, alguna decisión que usted o el experimentador tomaron)? Cualquier detalle adicional sería útil.

cardenal

@cardenal. (parte 1/2) Gracias cardenal. Daré más detalles: tengo un generador de VoIP que genera llamadas siguiendo el Zipf (y otra distribución) para el volumen por persona que llama. Tengo que verificar que este generador realmente siga estas distribuciones. Para la distribución Zipf, necesito definir el punto de truncamiento (por lo tanto, es conocido y se refiere a la distribución de valores), que es el número máximo de llamadas generadas por el usuario y el parámetro de escala. En particular, en mi caso, este valor es igual a 500, lo que indica que un usuario puede generar un máximo de 500 llamadas.

Maurizio

(parte 2/2) El otro parámetro para establecer es el parámetro de escala para Zipf que define la extensión de la distribución (este valor en mi caso es 0.9). Tengo todos los parámetros (tamaño de la muestra, frecuencia por usuario, etc.) pero tengo que verificar que mi conjunto de datos sigue la distribución zipf.

Maurizio

aparentemente está renormalizando la distribución por

, ya que para lo que yo pensaría como un "Zipf truncado", un parámetro de escala de 0.9 sería imposible. Si puede generar muchos de estos datos y "solo" tiene 500 resultados posibles, ¿por qué no usar una prueba de bondad de ajuste de chi-cuadrado? Como su distribución tiene una cola larga, es posible que necesite un tamaño de muestra bastante grande. Pero, eso sería de una manera. Otro método rápido y sucio sería verificar que obtenga la distribución empírica correcta para valores pequeños de la cantidad de llamadas.

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

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

cardenal

Respuestas:

Actualización : 7 de abril de 2011 Esta respuesta se está haciendo bastante larga y cubre varios aspectos del problema en cuestión. Sin embargo, me he resistido, hasta ahora, dividiéndolo en respuestas separadas.

Agregué al final una discusión sobre el rendimiento de Pearson para este ejemplo. $\chi^2$

Bruce M. Hill escribió, tal vez, el documento "seminal" sobre estimación en un contexto tipo Zipf. Escribió a mediados de los años 70 varios artículos sobre el tema. Sin embargo, el "estimador de Hill" (como se lo llama ahora) se basa esencialmente en las estadísticas de orden máximo de la muestra y, por lo tanto, dependiendo del tipo de truncamiento presente, eso podría ocasionarle algunos problemas.

El papel principal es:

BM Hill, Un enfoque general simple de inferencia sobre la cola de una distribución , Ann. Stat. 1975.

Si sus datos realmente son inicialmente Zipf y luego se truncan, entonces se puede aprovechar una buena correspondencia entre la distribución de grados y el gráfico Zipf .

Específicamente, la distribución de grados es simplemente la distribución empírica del número de veces que se ve cada respuesta entera,

{re}_{yo} = \frac{# # {j : X_{j} = yo}}{norte} .

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

Si graficamos esto contra en un gráfico log-log, obtendremos una tendencia lineal con una pendiente correspondiente al coeficiente de escala. $i$

Por otro lado, si trazamos el gráfico Zipf , donde clasificamos la muestra de mayor a menor y luego graficamos los valores contra sus rangos, obtenemos una tendencia lineal diferente con una pendiente diferente . Sin embargo, las pendientes están relacionadas.

Si es el coeficiente de la ley de escala para la distribución Zipf, entonces la pendiente en la primera gráfica es y la pendiente en la segunda gráfica es . A continuación se muestra un gráfico de ejemplo para y . El panel de la izquierda es la distribución de grados y la pendiente de la línea roja es . El lado derecho es el gráfico Zipf, con la línea roja superpuesta con una pendiente de $\alpha$ $-\alpha$ $-1/(\alpha-1)$ $\alpha = 2$ $n = 10^6$ $-2$ . $-1/(2-1) = -1$

Gráficos de distribución de grados (izquierda) y Zipf (derecha) para una muestra iid de una distribución Zipf.

Por lo tanto, si sus datos se han truncado para que no vea valores mayores que algún umbral , pero los datos están distribuidos por Zipf y es razonablemente grande, entonces puede estimar partir de la distribución de grados . Un enfoque muy simple es ajustar una línea al gráfico log-log y usar el coeficiente correspondiente. $\tau$ $\tau$ $\alpha$

$\hat{\beta}$

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

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

@csgillespie dio un artículo reciente escrito en colaboración con Mark Newman en Michigan sobre este tema. Parece que publica muchos artículos similares sobre esto. A continuación hay otra junto con otras referencias que pueden ser de interés. Newman a veces no hace las cosas más sensatas estadísticamente, así que tenga cuidado.

MEJ Newman, Leyes de poder, distribuciones de Pareto y la ley de Zipf , Contemporary Physics 46, 2005, pp. 323-351.

M. Mitzenmacher, Una breve historia de los modelos generativos para la ley de potencia y las distribuciones logarítmicas , Internet Math. vol. 1, no. 2, 2003, pp. 226-251.

K. Knight, una modificación simple del estimador Hill con aplicaciones a la robustez y reducción de sesgos , 2010.

Anexo :

$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)

La trama resultante es

Gráfico Zipf "truncado" (truncado en i = 500)

$i \leq 30$

Aún así, desde un punto de vista práctico, tal argumento debería ser relativamente convincente.

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

$\chi^2$

X^{2} = \sum_{yo = 1}^{500} \frac{(O_{yo} - {mi}_{yo})^{2}}{{mi}_{yo}}

$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}$

También calcularemos un segundo estadístico formado al agrupar primero los conteos en contenedores de tamaño 40, como se muestra en la hoja de cálculo de Maurizio (el último contenedor solo contiene la suma de veinte valores de resultados separados.

$n$ $p$

$p$

ingrese la descripción de la imagen aquí

$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 )

cardenal
fuente

+1, gran respuesta como siempre. Debes

nominarte a

@mpiktas, gracias por los cumplidos y el aliento. No estoy seguro de poder justificar mi nominación con la lista de candidatos, que ya es muy fuerte, y que, de manera uniforme, han participado más ampliamente y por más tiempo que yo.

cardenal

@cardinal, aquí hay algunos enlaces a alternativas al estimador de Hill: artículo original de Paulauskas y seguimientos de Vaiciulis y Gadeikis y Paulauskas . Este estimador supuestamente tenía mejores propiedades que el original de Hill.

mpiktas

@mpiktas, gracias por los enlaces. Hay bastantes versiones "nuevas y mejoradas" del estimador Hill. El principal inconveniente del enfoque original es que requiere una opción de "corte" sobre dónde dejar de promediar. Creo que, sobre todo, eso se ha hecho "mirando", lo que abre uno a los cargos de subjetividad. Recuerdo que uno de los libros de Resnick sobre distribuciones de cola larga trata esto con cierto detalle. Creo que es la más reciente.

cardenal

@ cardinal, muchas gracias, ¡eres muy amable y muy detallado! Su ejemplo en R fue muy útil para mí, pero ¿cómo puedo realizar una prueba de chi-cuadrado formal en este caso? (Utilicé la prueba de chi-cuadrado con otras distribuciones como uniforme, exponencial, normal, pero tengo muchas dudas sobre el zipf ... Lo siento, pero este es mi primer enfoque sobre estos temas). Pregunta para los moderadores: ¿tengo que escribir otras preguntas y respuestas como "cómo realizar la prueba de chi-cuadrado para la distribución zipf truncada?" o continuar en estas preguntas y respuestas, ¿quizás actualizar las etiquetas y el título?

Maurizio

El papel

Clauset, A et al , Distribuciones de la ley de poder en datos empíricos . 2009

contiene una muy buena descripción de cómo hacer para adaptar modelos de ley de potencia. La página web asociada tiene ejemplos de código. Desafortunadamente, no proporciona código para distribuciones truncadas, pero puede darle un puntero.

Como comentario aparte, el documento discute el hecho de que muchos "conjuntos de datos de leyes de poder" se pueden modelar igualmente bien (y en algunos casos mejor) con las distribuciones Log normales o exponenciales.

csgillespie
fuente

Desafortunadamente, este documento no dice nada sobre la distribución truncada ... Encontré algunos paquetes en R que tratan el parámetro de estimación Zipf de una manera simple (zipfR, VGAM) pero la distribución truncada necesita un "tratamiento especial". Con su última oración, ¿quiso decir que es posible modelar un conjunto de datos de ley de potencia con, por ejemplo, una distribución exponencial y luego aplicar algún proceso de parámetros de estimación para la distribución exponencial "truncada"? Soy muy novato en este tema!

Maurizio

En el documento, los autores vuelven a analizar diferentes conjuntos de datos donde se ha ajustado una ley de poder. Los autores señalan que en varios casos el modelo de ley de poder no es tan bueno y una distribución alternativa sería mejor.

csgillespie

Siguiendo la respuesta detallada del cardenal del usuario, realicé la prueba de chi-cuadrado en mi distribución zipf truncada presumible. Los resultados de la prueba de chi-cuadrado se presentan en la siguiente tabla:

ingrese la descripción de la imagen aquí

Donde StartInterval y EndInterval representan, por ejemplo, el rango de llamadas y Observado es el número de llamadas que generan de 0 a 19 llamadas, y así sucesivamente. La prueba de chi-cuadrado es buena hasta que se alcanzan las últimas columnas, aumentan la cantidad final cálculo, de lo contrario hasta ese punto, ¡el valor de chi-cuadrado "parcial" era aceptable!

Con otras pruebas, el resultado es el mismo, la última columna (o las últimas 2 columnas) siempre aumenta el valor final y no sé por qué y no sé si (y cómo) usar otra prueba de validación.

PD: para completar, para calcular los valores esperados ( esperados ), sigo la sugerencia del cardenal de esta manera:

ingrese la descripción de la imagen aquí

donde se usan las X_i para calcular:, x <- (1:n)^-Slas P_i para calcular p <- x / sum(x)y finalmente la E_i (número esperado de usuarios para cada número de llamadas) se obtiene medianteP_i * Total_Caller_Observed

y con Grado de libertad = 13, la bondad de Chi-cuadrado rechaza siempre la Hipótesis de que el conjunto de muestras sigue la Distribución Zipf porque la Estadística de prueba (64,14 en este caso) es mayor que la informada en las tablas de chi-cuadrado, "demérito" para la última columna El resultado gráfico se informa aquí: ingrese la descripción de la imagen aquí

aunque el punto de truncamiento se establece en 500, el valor máximo obtenido es 294. Creo que la "dispersión" final es la causa del fracaso de la prueba de chi-cuadrado.

¡¡ACTUALIZAR!!

Intento realizar la prueba de chi-cuadrado en una muestra presumible de datos zipf generada con el código R informado en la respuesta anterior.

> 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)

La trama asociada es la siguiente: ingrese la descripción de la imagen aquí

Los resultados de la prueba de chi-cuadrado se presentan en la siguiente figura: ingrese la descripción de la imagen aquí

y la estadística de prueba de chi-cuadrado (44,57) es demasiado alta para la validación con el Grado de Libertad elegido. También en este caso, la "dispersión" final de datos es la causa del alto valor de chi-cuadrado. Pero hay un procedimiento para validar esta distribución zipf (independientemente de mi generador "incorrecto", quiero centrarme en la muestra de datos R) ???

Maurizio
fuente

@Maurizio, por alguna razón, me perdí esta publicación hasta ahora. ¿Hay alguna forma de editarlo y agregar un gráfico similar al último en mi publicación, pero usando sus datos observados? Eso podría ayudar a diagnosticar el problema. Creo que vi otra pregunta tuya en la que tenías problemas para producir una distribución uniforme, así que tal vez eso también se esté trasladando a estos análisis. (?) Saludos.

cardenal

@cardinal, ¡actualicé los resultados! ¿Qué piensas? La pregunta sobre la distribución uniforme es otra cosa que tengo que especificar de una mejor manera y lo haré hoy o mañana;)

Maurizio

S = 0.9

$S = 0.9$

@Maurizio, para explicar los resultados que publiqué, considere que

. Entonces, en un tamaño de muestra de

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$ . Tenga en cuenta qué tan cerca coincide con la simulación anterior.

cardenal

@cardinal, también creo que hay algo "incorrecto" en el procedimiento de generación (mi objetivo es validar que este generador realmente siga la distribución Zipf). Tengo que hablar con los diseñadores del proyecto en estos días.

Maurizio