Cómo calcular o aproximar la mediana de una lista sin almacenar la lista

StackOverflow https://stackoverflow.com/questions/638030

  •  10-07-2019
  •  | 
  •  

Pregunta

Estoy tratando de calcular la mediana de un conjunto de valores, pero no quiero almacenar todos los valores, ya que eso podría reducir los requisitos de memoria. ¿Hay alguna manera de calcular o aproximar la mediana sin almacenar y ordenar todos los valores individuales?

Idealmente, me gustaría escribir mi código un poco como el siguiente 

var medianCalculator = new MedianCalculator();
foreach (var value in SourceData)
{
  medianCalculator.Add(value);
}
Console.WriteLine("The median is: {0}", medianCalculator.Median);

¡Todo lo que necesito es el código real de MedianCalculator!

Actualización: Algunas personas han preguntado si los valores para los que estoy tratando de calcular la mediana tienen propiedades conocidas. La respuesta es sí. Un valor está en incrementos de 0.5 de aproximadamente -25 a -0.5. El otro también está en incrementos de 0.5 de -120 a -60. Supongo que esto significa que puedo usar alguna forma de histograma para cada valor.

Gracias

Nick

¿Fue útil?

Solución

Si los valores son discretos y el número de valores distintos no es demasiado alto, puede acumular la cantidad de veces que cada valor aparece en un histograma, luego encontrar la mediana de los recuentos de histogramas (solo sumar los recuentos de arriba y abajo del histograma hasta llegar al medio). O si son valores continuos, podría distribuirlos en contenedores; eso no le indicaría la mediana exacta, pero le daría un rango, y si necesita saber con mayor precisión, puede repetir la lista nuevamente, examinando solo los elementos en el contenedor central.

Otros consejos

Existe la estadística 'remedian'. Funciona configurando primero k matrices, cada una de longitud b. Los valores de datos se introducen en la primera matriz y, cuando está llena, la mediana se calcula y se almacena en la primera posición de la siguiente matriz, después de lo cual se reutiliza la primera matriz. Cuando la segunda matriz está llena, la mediana de sus valores se almacena en la primera posición de la tercera matriz, etc., etc. Se obtiene la idea :)

Es simple y bastante robusto. La referencia está aquí ...

http://web.ipac.caltech.edu/ staff / fmasci / home / astro_refs / Remedian.pdf

Espero que esto ayude

Michael

Utilizo estos estimadores de media y mediana incrementales / recursivos, que usan almacenamiento constante: 

mean += eta * (sample - mean)
median += eta * sgn(sample - median)

donde eta es un parámetro de velocidad de aprendizaje pequeño (p. ej., 0.001), y sgn () es la función signum que devuelve uno de {-1, 0, 1}.

Este tipo de estimador medio incremental parece usarse en todo el lugar, p. en reglas de aprendizaje de redes neuronales no supervisadas, pero la versión mediana parece mucho menos común, a pesar de sus beneficios (robustez para los valores atípicos). Parece que la versión mediana podría usarse como reemplazo del estimador medio en muchas aplicaciones.

Me encantaría ver un estimador de modo incremental de forma similar ...

(Nota: también publiqué esto en un tema similar aquí: " Algoritmos (iterador) en línea para estimar la mediana estadística, la moda, la asimetría, la curtosis? )

Aquí hay un enfoque loco que podrías probar. Este es un problema clásico en los algoritmos de transmisión. Las reglas son

  1. Tiene memoria limitada, diga O(log n) donde n es la cantidad de elementos que desea
  2. Puede mirar cada elemento una vez y tomar una decisión y luego qué hacer con él, si lo almacena, le cuesta memoria, si lo tira, desaparece para siempre.

La idea para encontrar una mediana es simple. Muestra O(1 / a^2 * log(1 / p)) * log(n) elementos de la lista al azar, puede hacerlo mediante muestreo de yacimientos (consulte un pregunta anterior ). Ahora simplemente devuelva la mediana de sus elementos muestreados, utilizando un método clásico.

La garantía es que el índice del artículo devuelto será (1 +/- a) / 2 con una probabilidad de al menos 1-p. Por lo tanto, existe una probabilidad p de falla, puede elegirla muestreando más elementos. Y no devolverá la mediana ni garantizará que el valor del artículo devuelto esté cerca de la mediana, solo que cuando clasifique la lista, el artículo devuelto estará cerca de la mitad de la lista.

Este algoritmo utiliza <=> espacio adicional y se ejecuta en tiempo lineal.

Esto es difícil de entender en general, especialmente para manejar series degeneradas que ya están ordenadas, o tienen un montón de valores en " start " de la lista pero el final de la lista tiene valores en un rango diferente.

La idea básica de hacer un histograma es muy prometedora. Esto le permite acumular información de distribución y responder consultas (como mediana) a partir de ella. La mediana será aproximada ya que obviamente no almacena todos los valores. El espacio de almacenamiento es fijo, por lo que funcionará con cualquier secuencia de longitud que tenga.

Pero no puede crear un histograma a partir de decir los primeros 100 valores y usar ese histograma continuamente ... los datos cambiantes pueden invalidar ese histograma. Por lo tanto, necesita un histograma dinámico que pueda cambiar su rango y contenedores sobre la marcha.

Crea una estructura que tenga N contenedores. Almacenará el valor X de cada transición de ranura (valores N + 1 en total), así como la población del contenedor.

Transmita sus datos. Registre los primeros valores N + 1. Si la secuencia termina antes de esto, genial, tiene todos los valores cargados y puede encontrar la mediana exacta y devolverla. De lo contrario, use los valores para definir su primer histograma. Simplemente ordene los valores y utilícelos como definiciones de bin, cada bin tiene una población de 1. Está bien tener duplicados (0 bin de ancho).

Ahora transmite en nuevos valores. Para cada uno, búsqueda binaria para encontrar el contenedor al que pertenece. En el caso común, simplemente incrementa la población de ese contenedor y continúa. Si su muestra está más allá de los bordes del histograma (más alto o más bajo), simplemente extienda el rango del contenedor final para incluirlo. Cuando termine su transmisión, encontrará el valor medio de la muestra al encontrar el contenedor que tiene la misma población en ambos lados e interpolar linealmente el ancho del contenedor restante.

Pero eso no es suficiente ... aún necesita ADAPTAR el histograma a los datos a medida que se transmiten. Cuando un contenedor se llena demasiado, está perdiendo información sobre la subdistribución de ese contenedor. Puede solucionar esto mediante la adaptación basada en alguna heurística ... La más fácil y robusta es si un bin alcanza cierta población umbral (algo así como 10 * v / N donde v = # de valores vistos hasta ahora en la secuencia, y N es el número de contenedores), DIVIDES ese contenedor demasiado lleno. Agregue un nuevo valor en el punto medio del contenedor, dele a cada lado la mitad de la población del contenedor original. Pero ahora tiene demasiados contenedores, por lo que debe ELIMINAR un contenedor. Una buena heurística para eso es encontrar el contenedor con el producto más pequeño de población y ancho. Elimínelo y combínelo con su vecino izquierdo o derecho (cualquiera de los vecinos tiene el producto más pequeño de ancho y población). ¡Hecho! Tenga en cuenta que al fusionar o dividir contenedores se pierde información, pero eso es inevitable ... solo tiene almacenamiento fijo.

Este algoritmo es bueno ya que tratará con todos tipos de flujos de entrada y dará buenos resultados. Si tiene el lujo de elegir el orden de la muestra, lo mejor es una muestra aleatoria, ya que minimiza las divisiones y las fusiones.

El algoritmo también le permite consultar cualquier percentil, no solo la mediana, ya que tiene una estimación de distribución completa.

Utilizo este método en mi propio código en muchos lugares, principalmente para depurar registros ... donde algunas estadísticas que estás grabando tienen una distribución desconocida. Con este algoritmo no necesita adivinar con anticipación.

La desventaja es que los anchos de bin desiguales significan que tiene que hacer una búsqueda binaria para cada muestra, por lo que su algoritmo neto es O (NlogN).

No creo que sea posible hacerlo sin tener la lista en la memoria. Obviamente puede aproximarse con

  • promedio si sabe que los datos se distribuyen simétricamente
  • o calcule una mediana adecuada de un pequeño subconjunto de datos (que cabe en la memoria), si sabe que sus datos tienen la misma distribución en la muestra (por ejemplo, que el primer elemento tiene la misma distribución que el último)

La sugerencia de David parece ser el enfoque más sensato para aproximar la mediana.

Una media para el mismo problema es mucho más fácil de calcular:

  

M n = M n-1 + ((V n - M n-1 ) / n)

     

Donde M n es la media de n valores, M n-1 es la media anterior y V n es el nuevo valor .

En otras palabras, la nueva media es la media existente más la diferencia entre el nuevo valor y la media, dividida por el número de valores.

En el código, esto se vería así: 

new_mean = prev_mean + ((value - prev_mean) / count)

aunque obviamente es posible que desee considerar cosas específicas del idioma, como errores de redondeo de punto flotante, etc.

Busque Min y Max de la lista que contiene N elementos a través de la búsqueda lineal y asígneles el nombre HighValue y LowValue Deje MedianIndex = (N + 1) / 2

Búsqueda binaria de primer orden:

Repita los siguientes 4 pasos hasta LowValue < HighValue.

  1. Obtenga MedianValue aproximadamente = (HighValue + LowValue) / 2

  2. Obtener NumberOfItemsWhichAreLessThanorEqualToMedianValue = K

  3. es K = MedianIndex, luego devuelve MedianValue

  4. es K > MedianIndex? entonces HighValue = MedianValue Else LowValue = MedianValue

Será más rápido sin consumir memoria

Búsqueda binaria de segundo orden:

LowIndex = 1 HighIndex = N

Repita los siguientes 5 pasos hasta que (LowIndex < HighIndex)

  1. Obtener DistrbutionPerUnit = (HighValue-LowValue) / (HighIndex-LowIndex)

  2. Obtener MedianValue aproximado = LowValue + (MedianIndex-LowIndex) * DistributionPerUnit

  3. Obtener NumberOfItemsWhichAreLessThanorEqualToMedianValue = K

  4. es (K = MedianIndex)? return MedianValue

  5. es (K > MedianIndex)? entonces HighIndex = K y HighValue = MedianValue Else LowIndex = K y LowValue = MedianValue

Será más rápido que el primer orden sin consumir memoria

También podemos pensar en ajustar HighValue, LowValue y MedianValue con HighIndex, LowIndex y MedianIndex a una parábola, y podemos obtener la búsqueda binaria ThirdOrder que será más rápida que el segundo orden sin consumir memoria y así sucesivamente ...

Por lo general, si la entrada está dentro de un cierto rango, digamos 1 a 1 millón, es fácil crear una matriz de recuentos: lea el código para " cuantile " y " ibucket " aquí: http://code.google .com / p / ea-utils / source / browse / trunk / clipper / sam-stats.cpp

Esta solución se puede generalizar como una aproximación mediante la coerción de la entrada en un número entero dentro de cierto rango utilizando una función que luego se invierte al salir: IE: foo.push ((int) input / 1000000) y cuantil (foo ) * 1000000.

Si su entrada es un número arbitrario de doble precisión, entonces debe escalar automáticamente su histograma a medida que los valores entran fuera de rango (ver arriba).

O puede usar el método de tripletas medianas descrito en este documento: http: / /web.cs.wpi.edu/~hofri/medsel.pdf

Tomé la idea del cálculo de cuantiles iterativos. Es importante tener un buen valor para el punto de partida y eta, estos pueden provenir de mean y sigma. Así que programé esto:

Función QuantileIterative (Var x: Array of Double; n: Integer; p, mean, sigma: Double): Double;
Var eta, cuantil, q1, dq: Doble;
    i: entero;
Comience
  cuantil: = media + 1.25 * sigma * (p-0.5);
  q1: = cuantil;
  eta: = 0.2 * sigma / xy (1 + n, 0.75); // ¡no debería ser demasiado grande! establece precisión
  Para i: = 1 a n Do cuantil: = cuantil + eta * (signum_smooth (x [i] - cuantil, eta) + 2 * p - 1);
  dq: = abs (q1-cuantil);
  Si dq & Gt; eta
     entonces comience
          Si dq & Lt; 3 * eta entonces eta: = eta / 4;
          Para i: = 1 a n Do cuantil: = cuantil + eta * (signum_smooth (x [i] - cuantil, eta) + 2 * p - 1);
     fin;
  QuantileIterative: = cuantil
fin;

Como la mediana para dos elementos sería la media, utilicé una función de signo suavizado, y xy () es x ^ y. ¿Hay ideas para mejorarlo? Por supuesto, si tenemos algo más de conocimiento a priori, podemos agregar código usando min y max de la matriz, sesgo, etc.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top