Algoritmos para calcular desacuerdo

Los algoritmos para calcular el desacuerdo desempeñan un papel principal en la informática estadística. Un problema clave en el diseño de algoritmos buenos para este problema consiste en que las fórmulas para el desacuerdo pueden implicar sumas de cuadrados, que pueden llevar a la inestabilidad numérica así como al desbordamiento aritmético tratando con valores grandes.

Algoritmo ingenuo

Una fórmula para calcular el desacuerdo de una población entera de talla n es:

:

Una fórmula para calcular una estimación imparcial del desacuerdo demográfico de una muestra finita de observaciones n es:

:

Por lo tanto un algoritmo ingenuo para calcular el desacuerdo estimado da lo siguiente:

def naive_variance (datos):

n = 0

Suma = 0

Sum_sqr = 0

para x en datos:

n = n + 1

Suma = Suma + x

Sum_sqr = Sum_sqr + x*x

quiera decir = Sum/n

desacuerdo = (Sum_sqr - Sum*mean) / (n - 1)

devuelva el desacuerdo

</fuente>

Este algoritmo se puede fácilmente adaptar para calcular el desacuerdo de una población finita: simplemente divídase en n en vez de n − 1 en la última línea.

Como y puede ser números muy similares, la precisión del resultado puede ser mucho menos que la precisión inherente de la aritmética del punto flotante solía realizar el cálculo. Esto es particularmente malo si la desviación estándar es pequeña con relación al medio. Sin embargo, el algoritmo se puede mejorar adoptando el método del medio asumido.

Algoritmo de dos pases

Un enfoque alterno, usando una fórmula diferente para el desacuerdo, primero calcula la muestra media,

:,

y luego calcula la suma de los cuadrados de las diferencias del medio,

:,

como dado por el pseudocódigo siguiente:

def two_pass_variance (datos):

n = 0

sum1 = 0

sum2 = 0

para x en datos:

n = n + 1

sum1 = sum1 + x

quiera decir = sum1/n

para x en datos:

sum2 = sum2 + (x - medio) * (x - medio)

desacuerdo = sum2 / (n - 1)

devuelva el desacuerdo

</fuente>

Este algoritmo a menudo es más numéricamente confiable que el algoritmo ingenuo para juegos grandes de datos, aunque pueda ser peor si la mayor parte de los datos está muy cerca de, pero no exactamente igual al medio y unos están completamente lejos de ello.

Los resultados de ambos de estos algoritmos simples (yo y II) pueden depender excesivamente del pedido de los datos y pueden dar resultados pobres para conjuntos de datos muy grandes debido al error roundoff repetido en la acumulación de las sumas. Las técnicas como la adición compensada pueden ser usadas para combatir este error a un grado.

Variante compensada

La versión de adición compensada del algoritmo encima lee:

def compensated_variance (datos):

n = 0

sum1 = 0

para x en datos:

n = n + 1

sum1 = sum1 + x

quiera decir = sum1/n

sum2 = 0

sum3 = 0

para x en datos:

sum2 = sum2 + (x - medio) ** 2

sum3 = sum3 + (x - medio)

desacuerdo = (sum2 - sum3 ** 2/n) / (n - 1)

devuelva el desacuerdo

</fuente>

Algoritmo en línea

A menudo es útil ser capaz de calcular el desacuerdo en un pase solo, inspeccionando cada valor sólo una vez; por ejemplo, cuando los datos se están coleccionando sin bastante almacenaje para guardar todos los valores, o cuando los gastos del acceso de memoria dominan a aquellos del cálculo. Para un algoritmo tan en línea, se requiere una relación de la repetición entre cantidades de las cuales la estadística requerida se puede calcular de una moda numéricamente estable.

Las fórmulas siguientes pueden ser usadas para actualizar el desacuerdo medio y (estimado) de la secuencia, para un elemento adicional. Aquí, denota la muestra media de las primeras muestras n (x..., x), s su desacuerdo de la muestra y σ su desacuerdo demográfico.

:

:

:

Resulta que una cantidad más conveniente para la actualización está la suma de cuadrados de diferencias de la (corriente) media, aquí denotado:

:

:

:

Dan un algoritmo numéricamente estable abajo. También calcula el medio.

Este algoritmo es debido a Knuth,

quien cita Welford.

def online_variance (datos):

n = 0

quiera decir = 0

M2 = 0

para x en datos:

n = n + 1

el delta = x - significa

quiera decir = medio + delta/n

M2 = M2 + delta * (x - medio)

variance_n = M2/n

desacuerdo = M2 / (n - 1)

vuelva (desacuerdo, variance_n)

</fuente>

Este algoritmo es mucho menos propenso a la pérdida de la precisión debido a la cancelación masiva, pero no podría ser tan eficiente debido a la operación de la división dentro del lazo. Para un algoritmo de dos pases particularmente robusto para calcular el desacuerdo, primero calcule y reste una estimación del medio, y luego use este algoritmo en el residuals.

El algoritmo paralelo abajo ilustra cómo combinar juegos múltiples de la estadística calculada en línea.

Algoritmo incremental ponderado

El algoritmo se puede ampliar para manejar pesos de la muestra desiguales, sustituyendo el contador simple n con la suma de pesos vistos hasta ahora. El Oeste (1979) sugiere este algoritmo incremental:

def weighted_incremental_variance (dataWeightPairs):

sumweight = 0

quiera decir = 0

M2 = 0

para x, peso en dataWeightPairs: # Alternativamente "para x, peso en cremallera (datos, pesos):"

temp = peso + sumweight

el delta = x − significa

R = delta * peso / temp

quiera decir = medio + R

M2 = M2 + sumweight * delta * R # O bien, "M2 = M2 + peso * delta * (x−mean)"

sumweight = temp

variance_n = M2/sumweight

desacuerdo = variance_n * len (dataWeightPairs) / (len (dataWeightPairs) − 1)

</fuente>

Algoritmo paralelo

Chan et al. note que el susodicho el algoritmo en línea III es un caso especial de un algoritmo que trabaja para cualquier partición de la muestra en juegos:

:

:

:.

Esto puede ser útil cuando, por ejemplo, unidades de procesamiento múltiples se pueden asignar a partes distintas de la entrada.

El método de Chan para estimar el medio es numéricamente inestable cuando y ambos son grandes, porque el error numérico en no se reduce en el modo que está en el caso. En tales casos, preferir.

Ejemplo

Suponga que todas las operaciones del punto flotante usen IEEE estándar 754 aritmética de doble precisión. Considere la muestra (4, 7, 13, 16) de una población infinita. Basado en esta muestra, la población estimada media es 10, y la estimación imparcial del desacuerdo demográfico es 30. Tanto Algoritmo I como Algoritmo II calculan estos valores correctamente. Después considere la muestra (10 + 4, 10 + 7, 10 + 13, 10 + 16), que da ocasión al mismo desacuerdo estimado que la primera muestra. El algoritmo II calcula esta estimación del desacuerdo correctamente, pero Algoritmo I vueltas 29.333333333333332 en vez de 30. Mientras esta pérdida de la precisión puede ser tolerable y vista como un defecto menor del Algoritmo I, es fácil encontrar datos que revelan un defecto principal en el algoritmo ingenuo: Tome la muestra para ser (10 + 4, 10 + 7, 10 + 13, 10 + 16). Otra vez el desacuerdo demográfico estimado de 30 es calculado correctamente por el Algoritmo II, pero el algoritmo ingenuo ahora lo calcula como 170.66666666666666. Esto es un grave problema con el Algoritmo I y es debido a la cancelación catastrófica en la substracción de dos números similares en la fase final del algoritmo.

Estadística de pedido más alto

Terriberry amplía las fórmulas de Chan al cálculo de los terceros y cuartos momentos centrales, necesarios por ejemplo estimando la oblicuidad y kurtosis:

:

:

M_ {4, X} = M_ {4, un} + M_ {4, B} & + \delta^4\frac {n_A n_B \left (n_A^2 - n_A n_B + n_B^2\right)} {n_X^3} \\

& + 6\delta^2\frac {n_A^2 M_ {2, B} + n_B^2 M_ {2, un}} {n_X^2} + 4\delta\frac {n_AM_ {3, B} - n_BM_ {3, un}} {n_X} \\

Los \end {alinean} </matemáticas>

Aquí ser otra vez las sumas de poderes de diferencias del medio, dando

:skewness:

:kurtosis:

Para el caso incremental (es decir,), esto simplifica a:

:

:

:

:

:

Conservando el valor, sólo una operación de la división es necesaria y la estadística de pedido más alto se puede así calcular para poco coste incremental.

Un ejemplo del algoritmo en línea para kurtosis puesto en práctica como descrito es:

def online_kurtosis (datos):

n = 0

quiera decir = 0

M2 = 0

M3 = 0

M4 = 0

para x en datos:

n1 = n

n = n + 1

el delta = x - significa

delta_n = delta / n

delta_n2 = delta_n * delta_n

term1 = delta * delta_n * n1

quiera decir = medio + delta_n

M4 = M4 + term1 * delta_n2 * (n*n - 3*n + 3) + 6 * delta_n2 * M2 - 4 * delta_n * M3

M3 = M3 + term1 * delta_n * (n - 2) - 3 * delta_n * M2

M2 = M2 + term1

kurtosis = (n*M4) / (M2*M2) - 3

devuelva kurtosis

</fuente>

Pébay

adelante amplía estos resultados al pedido arbitrario momentos centrales, para el incremental y los casos pares. Uno también puede encontrar fórmulas allí similares para la covariancia.

Choi y Sweetman

ofrezca dos métodos alternos de calcular la oblicuidad y kurtosis, cada uno de los cuales puede salvar requisitos de la memoria del ordenador sustanciales y tiempo de la CPU en ciertas aplicaciones. El primer enfoque debe calcular los momentos estadísticos separando los datos en recipientes y luego calculando los momentos de la geometría del histograma que resulta, que con eficacia se hace un algoritmo del Onepass durante momentos más altos. Una ventaja es que los cálculos del momento estadísticos se pueden realizar con la exactitud arbitraria tal que los cálculos se pueden sintonizar la precisión de, p.ej, el formato de almacenaje de datos o el hardware de medida original. Un histograma relativo de una variable arbitraria se puede construir en

el camino convencional: la variedad de valores potenciales es

dividido en recipientes y el número de acontecimientos dentro de cada recipiente son

contado y trazado tal que el área de cada rectángulo iguala

la parte de la muestra valora dentro de ese recipiente:

:

donde y representan la frecuencia y

la frecuencia relativa en recipiente y

\, \Delta x_k </matemáticas> es el área total del histograma. Después de este

normalización, los momentos crudos y momentos centrales de

se puede calcular del histograma relativo:

:

m_n^ {(h)} = \sum_ {k=1} ^ {K} x_k^n \, H (x_k) \Delta x_k

= \frac {1} {Un} \sum_ {k=1} ^ {K} x_k^n \, h (x_k) \Delta x_k

</matemáticas>

:

\theta_n^ {(h)} = \sum_ {k=1} ^ {K} \Big (x_k-m_1^ {(h) }\\Grande) ^n \, H (x_k) \Delta x_k

= \frac {1} {Un} \sum_ {k=1} ^ {K} \Big (x_k-m_1^ {(h) }\\Grande) ^n \, h (x_k) \Delta x_k

</matemáticas>

donde la superescritura indica que los momentos son

calculado del histograma. Para anchura del recipiente constante

el x_k =\Delta x </matemáticas> estas dos expresiones se puede simplificar usando:

:

m_n^ {(h)} = \frac {1} {yo} {\\sum_ {k=1} ^ {K} x_k^n \, h (x_k) }\

</matemáticas>

:

\theta_n^ {(h)} = \frac {1} {yo} {\\sum_ {k=1} ^ {K} \Big (x_k-m_1^ {(h) }\\Grande) ^n \, h (x_k) }\

</matemáticas>

El segundo enfoque de Choi y Sweetman

es una metodología analítica para combinar momentos estadísticos de segmentos individuales de una historia del tiempo tal que los momentos totales que resultan son aquellos de la historia del tiempo completa. Esta metodología se podría usar para el cálculo paralelo de momentos estadísticos con la combinación subsecuente de aquellos momentos, o para la combinación de momentos estadísticos calculados en tiempos secuenciales.

Si los juegos de momentos estadísticos se conocen:

\quad </matemáticas> para, entonces cada uno puede

exprésese en términos de momentos crudos equivalentes:

:

\gamma_ {n, q} = m_ {n, q} \gamma_ {0, q} \qquad \quad \textrm {para} \quad n=1,2,3,4 \quad \text {y} \quad q = 1,2, \dots, Q

</matemáticas>

donde generalmente se toma para ser la duración de la historia del tiempo o el número de puntos si es constante.

La ventaja de expresar los momentos estadísticos en

los términos de son que los juegos pueden ser combinados por

la adición y no hay ningún límite superior en el valor de.

:

\gamma_ {n, c} = \sum_ {q=1} ^ {Q }\\gamma_ {n, q} \quad \quad \textrm {para} \quad n=0,1,2,3,4

</matemáticas>

donde el subíndice representa concadenado

historia del tiempo o combinado. Estos valores combinados de

se puede inversamente transformar entonces en momentos crudos

la representación de la historia del tiempo concadenada completa

:

m_ {n, c} = \frac {\\gamma_ {n, c}} {\\gamma_ {0, c}} \quad \textrm {para} \quad n=1,2,3,4

</matemáticas>

Relaciones conocidas entre los momentos crudos y los momentos centrales

son

usados entonces para calcular los momentos centrales de la historia del tiempo concadenada. Finalmente, los momentos estadísticos de la historia concadenada se calculan a partir de los momentos centrales:

:

\mu_c=m_ {1, c }\

\\\\\\sigma^2_c =\theta_ {2, c }\

\\\\\\alpha_ {3, c} = \frac {\\theta_ {3, c}} {\\sigma_c^3 }\

\\\\\\alpha_ {4, c} = \frac {\\theta_ {4, c}} {\\sigma_c^4 }\

</matemáticas>

Covariancia

Los algoritmos muy similares pueden ser usados para calcular la covariancia. El algoritmo ingenuo es:

:

Para el algoritmo encima, uno podría usar el pseudocódigo siguiente:

def naive_covariance (data1, data2):

n = len (data1)

sum12 = 0

sum1 = suma (data1)

sum2 = suma (data2)

ya que yo en variedad (n):

sum12 + = data1 [yo] *data2 [yo]

covariancia = (sum12 - sum1*sum2 / n) / n

devuelva la covariancia

</fuente>

Un algoritmo de dos pases más numéricamente estable primero calcula los medios de la muestra, y luego la covariancia:

:

:

:

El algoritmo de dos pases se puede escribir como:

def two_pass_covariance (data1, data2):

n = len (data1)

mean1 = suma (data1) / n

mean2 = suma (data2) / n

covariancia = 0

ya que yo en variedad (n):

a = data1 [yo] - mean1

b = data2 [yo] - mean2

covariancia + = a*b / n

devuelva la covariancia

</fuente>

Una versión compensada ligeramente más exacta realiza el algoritmo ingenuo lleno en el residuals. Las sumas finales y deberían ser el cero, pero el segundo pase compensa cualquier pequeño error.

Un algoritmo del Onepass estable existe, similar al que encima, que calcula:

:

:

:

La asimetría aparente en esa última ecuación es debido a que, por tanto ambos términos de actualización son iguales a. Incluso la mayor exactitud puede ser conseguida por la primera informática de los medios, luego usando el algoritmo del Onepass estable en el residuals.

Igualmente, hay una fórmula para combinar las covariancias de dos juegos que pueden estar acostumbrados a parallelize el cálculo:

:.

Calcule el desacuerdo (continuo) que corre

El algoritmo siguiente se puede aplicar.

:

:

Para k = 1

M1 = x1 y S1 = 0

Para 2 ≤ k ≤ n </br>

El: estimación del medio:

El: la estimación del desacuerdo es:

El: la estimación de la desviación estándar es:

Véase también

Enlaces externos



Buscar