algorithm - Valor medio y desviación estándar de un conjunto de datos muy grande

statistics mean

Question

Me pregunto si hay un algoritmo que calcule el valor medio y la desviación estándar de un conjunto de datos no unidos.

por ejemplo, estoy monitoreando un valor de medición, por ejemplo, corriente eléctrica. Me gustaría tener el valor medio de todos los datos históricos. Cada vez que venga un nuevo valor, actualice la media y stdev? Debido a que los datos son demasiado grandes para almacenar, espero que solo pueda actualizar la media y el stdev sobre la marcha sin almacenar los datos.

Incluso los datos se almacenan, la forma estándar (d1 + ... + dn) / n, no funciona, la suma eliminará la representación de los datos.

I a través de la suma (d1 / n + d2 / n + ... d3 / n), si n es hugh, el error es demasiado grande y acumulado. Además, n no está consolidado en este caso.

La cantidad de datos definitivamente no está vinculada, siempre que venga, se requiere actualizar el valor.

¿Alguien sabe si hay un algoritmo para ello?

Answer 1

No.

(Pensé: No, pero me han equivocado).

Puedes llevar la suma y la cuenta, para que

sum(i)=500, count(i)=50, => avg:=10
next value = 20
sum=520, count=51 => avg:= 10.19

pero el stddev no se puede construir de esa manera. Tienes que producir el delta para cada valor según la nueva media y cuadrar esos, y solo después de eso, dividir por N. Sin embargo: la pregunta es, ¿qué tipo de valores son esos (desde un punto de vista matemático? ¡Mantente alejado de la física!) :)). En circunstancias normales, no esperaría que los valores cambien después de 2000 elementos. De lo contrario, podría ser cuestionable construir mean y stddev en primer lugar.

Y para 2000 elementos, debería ser posible calcular el valor rápidamente.

Tal vez pueda usar un búfer y calcular siempre el promedio y el estándar de los últimos 2000 valores cada 2000 valores. Si esto es información significativa es algo que tienes que decidir.

No podemos continuar nuestra conversación en el chat tan bien, ...

Porque no ha elaborado rebajas. Así que utilizo mi publicación para aclarar mi posición, que se distribuye sobre los comentarios principalmente con thb, pero Andrew también parece creer en el cálculo deslizante del estándar.

Aquí hay una tabla amplia para hacer el cálculo obvio y fácil de seguir. Las columnas son:

• i: el índice de ejecución. Primero calculamos los valores 1-3, luego los valores 1-5.
• x (i) son los datos, elegidos arbitrariamente por mí. 3,4,5 y 4,6
• La suma es solo lo que ellos resumen. El interesante es el último para el grupo: 12 y 22. Nota: No tomamos la suma de 3 valores y 2 valores, sino de los primeros 3 y luego de los primeros 5.
• El promedio es de 12/3 o 22/5. El promedio puede calcularse deslizándose, si sabe i y sum. sum(i+1) = (sum (i)+x(i))/i+1 No hay disputa hasta el momento.
• Para calcular el stddev., Tenemos que tomar la diferencia de cada valor al promedio, y cuadrarlo (por lo tanto, perder el signo, lo que de otro modo invalidaría la diferencia, siempre sería 0). Un segundo efecto es que pocas distancias grandes conducen a un estándar más grande que muchas distancias pequeñas. Distancia (1,1,-1,-1)=> 4*1² = 4. En contraste: (2,-2)=> 2² + -2² = 4+4 = 8 . La primera columna es para los 3 valores, la segunda para los 5 valores (para seguir el cálculo).
• La siguiente columna (última) ² hace la cuadratura.
• Añádelo
• dividir por n-1
• sacar la raíz cuadrada

Tal vez podamos estar de acuerdo en que esta es una forma válida de calcular el stddev. Ahora la pregunta es cómo calcularlo si conoce la línea completa 3 (excepto x (3) = 5), y ahora obtiene dos valores individuales (4, 6) como se muestra en la hoja, pero sin saber (x ( i) para i = 1, 2, 3.

Mi reclamo falló: usted puede.

Bien - Intenté usar tu fórmula.

ð² = 1 / (N-1) (Suma (x _i ²) - 1 / N (Suma (x _i )) ²)

Así que por los 4 valores que obtengo

• N = 5
• suma (x _i ) = 22
• suma (x _i ²) = 102

Insertado en su fórmula:

ð² = 1/(N-1) (Sum (x<sub>i</sub>²) - 1/N (Sum (x<sub>i</sub>))²)
ð² = 1/4 (102 - 1/5 (22²))
ð² = 1/4 (102 - 1/5 (484))
ð² = 1/4 (102 - 96.8)
ð² = 1/4 (5.2)
ð² = 1.3
ð  = 1.140

Mi resultado fue 1.14, el tuyo es 1.14 Así que hay un atajo. Muy interesante, todavía estoy sorprendido.

Answer 2

De hecho, incluso en conjuntos de datos más pequeños al calcular la desviación estándar, no debe calcular la suma de los cuadrados . El problema se llama cancelación catastrófica (el enlace es a Wikipedia).

Wikipedia también tiene dos artículos que te ayudan a salir de este problema:

• Algoritmo de suma Kahan que tiene un arrastre para evitar un error sistemático al sumar un gran número de valores muy pequeños (por ejemplo, al sumar todos los valores x / n)
• Los algoritmos para calcular la varianza , en particular la versión "en línea" deben ser apropiados para grandes conjuntos de datos. Se actualizará de manera incremental la media para cada observación, ¡por lo que el valor permanece en la escala de sus datos! Es posible que deba usar la versión de orden superior para la varianza, ya que el primer algoritmo en línea aún calcula la suma de las desviaciones de la medida de la media, por lo que, para una gran n, esto puede afectar su rango de valores. El M2 en la versión de orden superior debe contener el promedio de desviación al cuadrado de la media, que está en la escala de su salida.

Este es probablemente uno de los problemas más comunes con los cálculos estadísticos ingenuos.

Tenga en cuenta que el problema no se produce cuando la media permanece alrededor de 0, mucho más pequeña que la varianza.

Answer 3

Interesante pregunta.

Vamos a discutir la media primero, aunque solo sea porque es un poco más simple.

Tiene razón sobre el error de redondeo en un total acumulado. Matará tu precisión para un conjunto de datos lo suficientemente grande. Le gustaría precortar los datos, sumando primero los datos pequeños; Pero por supuesto esto es imposible en tu caso. Sin embargo, puede obtener la mayor parte del beneficio de los datos ordenados manteniendo varios totales acumulados.

Un ejemplo conceptual, estilo C- o C ++:

const double max_small  =    0.001;
const double max_medium = 1000.0;

double total_small;
double total_medium;
double total_large;

while(true) {
    const double datum = get_datum(); // (Use here whatever function you use to get a datum.)
    if (!is_datum_valid()) break;
    if (abs(datum) <= max_small) total_small += datum;
    else if (abs(datum) <= max_medium) total_medium += datum;
    else total_large += datum;
}

double total = 0.0;
total += total_small;
total += total_medium;
total += total_large;

En código realista, probablemente mantendrás más de tres totales acumulados (y, por supuesto, también mantendrás los totales acumulados de los cuadrados de los datos), pero el ejemplo anterior transmite la idea. Puede rellenar los detalles.

Además, adaptando la idea de @andrewcooke, puedes expandir el bucle de esta manera:

while(true) {
    const double datum = get_datum();
    if (!is_datum_valid()) break;
    if (abs(datum) <= max_small) {
        total_small += datum;
        if (abs(total_small) > max_medium) {
            total_large += total_small;
            total_small = 0.0;
        }
    }
    else if (abs(datum) <= max_medium) total_medium += datum;
    else total_large += datum;
}

Una vez más, puede rellenar los detalles. Buena suerte.

APÉNDICE: EL CÁLCULO PRÁCTICO DE LA DESVIACIÓN ESTÁNDAR

Se ha planteado una buena pregunta en los diversos subprocesos de comentarios sobre cómo calcular una desviación estándar sin un conocimiento previo de la media. Afortunadamente, se sabe un truco para calcular la desviación estándar. He preparado dos páginas de notas que explican el truco here (en PDF).

En cualquier caso, todo lo que es necesario para incluir la desviación estándar entre las estadísticas en ejecución es sumar no solo los datos, sino también los cuadrados de los datos; y, por supuesto, los cuadrados se pueden sumar de la misma manera que los datos, siguiendo el mismo patrón que en el código anterior.

Answer 4

[¿Cambió la pregunta? tal vez solo leo el comienzo He actualizado / editado para dar una mejor respuesta:]

No hay una solución perfecta (en memoria constante) que yo sepa, pero puedo dar varios enfoques.

primero, para el cálculo básico solo necesita la suma de todos los valores ( sum_x ), la suma de sus cuadrados ( sum_x2 ) y el recuento total ( n ). entonces:

mean = sum_x / n
stdev = sqrt( sum_x2/n - mean^2 )

y todos estos valores ( sum_x , sum_x2 , n ) se pueden actualizar desde una secuencia.

El problema (como usted dice) es lidiar con desbordamiento y / o precisión limitada. puede ver esto si considera un punto flotante cuando sum_x2 es tan grande que la representación interna no incluye valores de la magnitud de un solo valor cuadrado.

una forma sencilla de evitar el problema es usar la aritmética exacta , pero será cada vez más lenta (y también usa la memoria O (log (n))).

otra forma en que puede ayudar es normalizar los valores: si sabe que los valores son generalmente X entonces puede hacer cálculos en x - X que hace que las sumas sean más pequeñas (obviamente, ¡luego agrega X a la media!). eso ayuda a posponer el punto en el que se pierde la precisión (y puede / debe combinarse con cualquier otro método aquí; cuando se realiza el binning, por ejemplo, puede usar la media del bin anterior). vea este algoritmo (método de Knuth) para saber cómo hacer esto progresivamente .

Si no le importa un costo de memoria O (n) pequeño (factor constante pequeño), podría reiniciar cada valor N (p. ej., un millón - más inteligente aún sería adaptar este valor detectando cuando la precisión es demasiado baja), almacenando la media y el valor anterior. y luego combínelo para obtener el resultado final (de modo que su media es el valor ponderado adecuadamente del total acumulado reciente y de los valores agrupados anteriores).

el enfoque de agrupación probablemente se podría generalizar a múltiples niveles (usted comienza a agrupar las bandejas) y se reduciría al uso de memoria O (log (n)), pero no he resuelto los detalles.

finalmente, una solución más práctica probablemente sería hacer el enfoque inicial para, digamos, 1000 valores, y luego comenzar una nueva suma en paralelo. podría mostrar un promedio ponderado de los dos y, después de otros 1000 valores, eliminar las sumas antiguas (después de disminuir gradualmente su peso) y comenzar un nuevo conjunto. por lo tanto, siempre tiene dos conjuntos de sumas y muestra un promedio ponderado entre ellos, lo que proporciona datos continuos que reflejan los últimos 1000 valores (solo). me imagino que en algunos casos será lo suficientemente bueno (no es un valor exacto, ya que es solo para datos "recientes", pero es suave y representativo, y utiliza una cantidad fija de memoria).

ps, algo que se me ocurrió después, en realidad, hacer esto "para siempre" no tiene mucho sentido de todos modos, porque llegarás a un punto donde los valores están absolutamente dominados por los datos antiguos. sería mejor usar una "media móvil" que dé menos peso a los valores antiguos. Consulte, por ejemplo, https://en.wikipedia.org/wiki/Moving_average ; sin embargo, no conozco un equivalente común a stdev.