sacar saca moda mediana estadistica ejemplos cual como calcular algorithm optimization median

algorithm - saca - mediana estadistica ejemplos



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

Estoy tratando de calcular la mediana de un conjunto de valores, pero no quiero almacenar todos los valores, ya que eso podría afectar los requisitos de memoria. ¿Hay alguna manera de calcular o aproximar la mediana sin almacenar y clasificar 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 intento calcular la mediana tienen propiedades conocidas. La respuesta es sí. Un valor está en incrementos de 0.5 desde aproximadamente -25 a -0.5. El otro también está en 0.5 incrementos de -120 a -60. Supongo que esto significa que puedo usar alguna forma de histograma para cada valor.

Gracias

Mella

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

  1. Tiene memoria limitada, por ejemplo O(log n) donde n es la cantidad de elementos que desea
  2. Puede ver cada elemento una vez y tomar una decisión en ese momento y qué hacer con él, si lo almacena, le cuesta memoria, si lo tira, se va para siempre.

La idea de encontrar una mediana es simple. Muestre O(1 / a^2 * log(1 / p)) * log(n) elementos de la lista al azar, puede hacerlo mediante el muestreo de yacimientos (vea una pregunta anterior ). Ahora simplemente devuelva la mediana de los 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 de al menos 1-p . Entonces, hay 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 O(log n) espacio adicional y se ejecuta en tiempo lineal.

En general, es complicado hacerlo bien, especialmente para manejar series degeneradas que ya están ordenadas, o tener un montón de valores al principio 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 la 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 la secuencia de longitud que tenga.

Pero no se puede simplemente construir un histograma de, digamos, los primeros 100 valores y usar ese histograma continuamente ... el cambio de datos puede hacer que el histograma no sea válido. Por lo tanto, necesita un histograma dinámico que pueda cambiar su alcance y compartimientos sobre la marcha.

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

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

Ahora transmita 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 (el más alto o el más bajo), simplemente extienda el rango del contenedor para incluirlo. Cuando finalice su transmisión, encontrará el valor mediano de la muestra encontrando el contenedor que tiene una población igual en ambos lados del mismo, e interpolando linealmente el ancho restante del contenedor.

Pero eso no es suficiente ... aún necesita ADAPTAR el histograma a los datos a medida que se transmiten. Cuando un contenedor se llena, está perdiendo información sobre la subdistribución del contenedor. Puede solucionar esto adaptándose en función de alguna heurística ... La más sencilla y más robusta es si un contenedor alcanza cierta población de umbral (algo así como 10 * v / N donde v = # de valores vistos hasta ahora en la transmisión, y N es la cantidad de contenedores), DIVIDE ese contenedor lleno. 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 tienes demasiados contenedores, por lo que debes BORRAR 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ínalo y combínalo 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 fusionar o dividir contenedores pierde información, pero eso es inevitable ... solo tiene almacenamiento fijo.

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

El algoritmo también le permite consultar cualquier percentil, no solo la 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 necesita adivinar antes de tiempo.

La desventaja es que el ancho desigual de los contenedores significa que debe hacer una búsqueda binaria para cada muestra, por lo que su algoritmo de red es O (NlogN).

Encuentre 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 Let 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. Obtenga NumberOfItemsWhichAreLessThanorEqualToMedianValue = K

  3. es K = MedianIndex, luego devuelve MedianValue

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

Será más rápido sin consumir memoria

Búsqueda binaria de segundo orden:

LowIndex = 1 HighIndex = N

Repita después de 5 pasos hasta (LowIndex <HighIndex)

  1. Obtenga una DistrbutionPerUnit = (HighValue-LowValue) aproximada / (HighIndex-LowIndex)

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

  3. Obtenga NumberOfItemsWhichAreLessThanorEqualToMedianValue = K

  4. es (K = MedianIndex)? devolver MedianValue

  5. es (K> MedianIndex)? luego 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 una parábola, y puede obtener ThirdOrder Binary Search, que será más rápido que 2nd order sin consumir memoria y así sucesivamente ...

Existe la estadística ''remediar''. Funciona al configurar k arrays, cada uno 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 la primera matriz se vuelve a utilizar. Cuando la segunda matriz está llena, la mediana de sus valores se almacena en la primera posición de la tercera matriz, etc., etc. 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

Miguel

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

Un promedio continuo 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 previa, 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 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 en coma flotante, etc.

No creo que sea posible sin tener la lista en la memoria. Obviamente puedes aproximar con

  • promedio si sabes que los datos están distribuidos 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)

Por lo general, si la entrada está dentro de un rango determinado, digamos de 1 a 1 millón, es fácil crear una matriz de recuentos: lea el código para "cuantile" 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 forzando la entrada en un entero dentro de cierto rango usando una función que luego se revierte al salir: IE: foo.push ((int) input / 1000000) y cuantile (foo) * 1000000 .

Si su entrada es un número arbitrario de doble precisión, debe autoescalar su histograma a medida que ingresan los valores que están 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

Si los valores son discretos y el número de valores distintos no es demasiado alto, puede simplemente acumular la cantidad de veces que se produce cada valor en un histograma, luego buscar la mediana a partir de los recuentos del histograma (solo sumar cuentas desde arriba y abajo del histograma hasta llegar al medio). O si son valores continuos, podrías distribuirlos en contenedores, eso no te indicaría la mediana exacta, pero te daría un rango, y si necesitas saber con más precisión, podrías repetir la lista nuevamente, examinando solo los elementos en el contenedor central.

Utilizo estos estimadores medianos y promedios 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 de signo que devuelve uno de {-1, 0, 1}.

Este tipo de estimador de promedios incrementales parece usarse en todas partes, por ejemplo, en reglas de aprendizaje de redes neuronales no supervisadas, pero la versión mediana parece ser mucho menos común, a pesar de sus beneficios (solidez a valores atípicos). Parece que la versión mediana podría usarse como reemplazo del estimador promedio en muchas aplicaciones.

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

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