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

Está la estadística 'remedian'. Funciona primero configurando arrays k, cada uno de longitud b. Los valores de datos se introducen en el primer array y, cuando este está lleno, la mediana se calcula y almacena en el primer pos del siguiente array, después de lo cual el primer array se reutiliza. Cuando la segunda matriz está llena, la mediana de sus valores se almacena en el primer pos de la tercera matriz, etc. sucesivamente. Usted consigue la idea:)

Es simple y bastante robusto. La referencia es aqui...

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

Espero que esto ayude

Michael

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

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

Donde eta es un pequeño parámetro de tasa de aprendizaje (por ejemplo, 0.001), y sgn() es la función signum que devuelve uno de {-1, 0, 1}.

Este tipo de estimador medio incremental parece ser utilizado en todas partes, por ejemplo, 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 a valores atípicos). Parece que el 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 una forma similar...

(Nota: También publiqué esto en un tema similar aquí: Algoritmos"On-line" (iteradores) para estimar la mediana estadística, el modo, la asimetría, la curtosis?)

Aquí hay un enfoque loco que puedes probar. Este es un problema clásico en los algoritmos de streaming. Las reglas son

1. Tiene memoria limitada, digamos O(log n) donde n es el número de elementos que desea
2. Puedes mirar cada artículo una vez y tomar una decisión entonces y allí qué hacer con él, si lo guardas, cuesta memoria, si lo tiras se ha ido 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 hacer esto a través del muestreo de reservorios (ver una 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 probabilidad al menos 1-p. Así que hay una probabilidad p de fallar, se puede elegir por muestreo más elementos. Y no devolverá la mediana o garantizará que el valor del elemento devuelto esté en cualquier lugar cerca de la mediana, solo que cuando ordene la lista el artículo devuelto estará cerca de la mitad de la lista.

Este algoritmo utiliza O(log n) espacio adicional y se ejecuta en tiempo lineal.

Esto es difícil de hacer bien en general, especialmente para manejar series degeneradas que ya están ordenadas, o tienen un montón de valores en el "inicio" 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) 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 puedes construir un histograma a partir de los primeros 100 valores y usar ese histograma continuamente.. los datos cambiantes pueden hacer que ese histograma no sea válido. Por lo tanto, necesita un histograma dinámico que pueda cambiar su rango y contenedores sobre la marcha.

Haga una estructura que tenga N contenedores. Almacenará el valor X de cada transición de ranura (N+1 valores totales), así como la población de la bandeja.

Transmitir en sus datos. Registre los primeros valores N + 1. Si la secuencia termina antes de esto, genial, tienes todos los valores cargados y puedes encontrar la mediana exacta y devolverla. De lo contrario, utilice los valores para definir su primer histograma. Solo ordena los valores y úsalos como definiciones de bin, cada bin tiene una población de 1. Está bien tener dupes (contenedores de 0 anchos).

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

Pero eso no es suficiente.. todavía necesita ADAPTAR el histograma a los datos a medida que se transmite. Cuando un contenedor se llena demasiado, estás perdiendo información sobre la sub-distribución de ese contenedor. Usted puede arreglar esto por adaptación basada en alguna heurística... La más fácil y robusta es si un bin alcanza cierta población de umbral (algo así como 10*v/N donde v=# de valores vistos hasta ahora en el flujo, y N es el número de bins), se DIVIDE ese bin sobrecargado. Agregue un nuevo valor en el punto medio del contenedor, dé a cada lado la mitad de la población del contenedor original. Pero ahora tiene demasiados contenedores, por lo que necesita eliminar un contenedor. Una buena heurística para eso es encontrar la papelera 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 en sí tiene el producto más pequeño de ancho y población.). Hecho! Tenga en cuenta que la fusión o división de contenedores pierde información, pero eso es inevitable.. solo tiene almacenamiento fijo.

Este algoritmo es bueno en que se ocupará de todos los 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 se fusiona.

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

Uso 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 necesitas adivinar con anticipación.

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

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

Una ejecución 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 los valores n, M_n-1 es el anterior significa, 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, dividido por el número de valores.

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

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

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

No creo que sea posible prescindir de tener la lista en memoria. Obviamente se puede aproximar con

• promedio si sabes que los datos están distribuidos simétricamente
• o calcular 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 toda la muestra (por ejemplo, que el primer elemento tiene la misma distribución que el último)

Encuentre Min y Max de la lista que contiene N elementos a través de la búsqueda lineal y nómbrelos como HighValue y LowValue Sea MedianIndex = (N+1)/2

Búsqueda binaria de 1er Orden:

Repita los siguientes 4 pasos hasta LowValue

1. Get MedianValue approximately = (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 2do orden:

LowIndex = 1 HighIndex = N

Repita Los Siguientes 5 Pasos hasta (LowIndex

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

2. Obtener MedianValue aproximado = LowValue + (MedianIndex-LowIndex) * Unidad de distribución

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 1er orden sin consumir memoria

También podemos pensar en ajustar HighValue, LowValue y MedianValue con HighIndex, LowIndex y MedianIndex a un Parabola, y puede obtener Búsqueda binaria de tercer orden que será más rápido que 2do 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 conteos: lea el código para "cuantil" e "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 entero dentro de algún rango utilizando una función que luego se invierte en la salida: IE: foo.push ((int) input / 1000000) y cuantil(foo)*1000000.

Si su entrada es un número arbitrario de doble precisión, entonces usted tiene que autoscale su histograma como valores vienen en que están fuera de rango (ver arriba).

O puede utilizar la mediana de trillizos método descrito en este artículo: http://web.cs.wpi.edu/~hofri/medsel.pdf