¿Cuál es un buen algoritmo para estimar la mediana de un gran conjunto de datos de lectura única?

Estoy buscando un buen algoritmo (es decir, cómputo mínimo, requisitos mínimos de almacenamiento) para estimar la mediana de un conjunto de datos que es demasiado grande para almacenar, de modo que cada valor solo se pueda leer una vez (a menos que almacene explícitamente ese valor). No hay límites en los datos que se puedan suponer.

Las aproximaciones están bien, siempre que se conozca la precisión.

Cualquier puntero?

¿Podría agrupar el conjunto de datos en conjuntos de datos mucho más pequeños (digamos 100 o 1000 o 10,000 puntos de datos) Si luego calculó la mediana de cada uno de los grupos. Si hiciera esto con suficientes conjuntos de datos, podría trazar algo así como el promedio de los resultados de cada uno de los conjuntos más pequeños y esto, ejecutando suficientes conjuntos de datos más pequeños convergen en una solución 'promedio'.

¿Qué tal algo como un procedimiento de binning? Suponga (con fines ilustrativos) que sabe que los valores están entre 1 y 1 millón. Configure N contenedores, de tamaño S. Entonces, si S = 10000, tendría 100 contenedores, correspondientes a los valores [1: 10000, 10001: 20000, ..., 990001: 1000000]

Luego, recorre los valores. En lugar de almacenar cada valor, simplemente incremente el contador en el contenedor apropiado. Usando el punto medio de cada bin como una estimación, puede hacer una aproximación razonable de la mediana. Puede escalar esto a una resolución tan fina o gruesa como desee cambiando el tamaño de los contenedores. Estás limitado solo por la cantidad de memoria que tienes.

Dado que no sabe qué tan grandes pueden llegar a ser sus valores, simplemente elija un tamaño de contenedor lo suficientemente grande como para que no se le agote la memoria, utilizando algunos cálculos rápidos al final del sobre. También puede almacenar los contenedores escasamente, de modo que solo agregue un contenedor si contiene un valor.

Editar:

El enlace que proporciona ryfm da un ejemplo de esto, con el paso adicional de usar los porcentajes acumulativos para estimar con mayor precisión el punto dentro de la papelera mediana, en lugar de solo usar puntos medios. Esta es una buena mejora.

Te redirijo a mi respuesta a una pregunta similar . En pocas palabras, es un algoritmo de lectura única, 'sobre la marcha' con peor complejidad de caso para calcular la mediana (exacta).$O(n)$

El algoritmo Rivest-Tarjan-Selection (a veces también llamado algoritmo de mediana de medianas) le permitirá calcular el elemento mediano en tiempo lineal sin ningún tipo de clasificación. Para conjuntos de datos grandes, esto puede ser bastante más rápido que la clasificación logarítmica lineal. Sin embargo, no resolverá su problema de almacenamiento de memoria.

Implementé el algoritmo P-Square para el cálculo dinámico de cuantiles e histogramas sin almacenar observaciones en un módulo limpio de Python que escribí llamado LiveStats . Debería resolver su problema con bastante eficacia.

Nunca he tenido que hacer esto, así que esto es solo una sugerencia.

Veo dos (otras) posibilidades.

Datos medios

1. Cargue la mitad de los datos y ordene
2. A continuación, lea los valores restantes y compárelos con la lista ordenada.
   1. Si el nuevo valor es mayor, deséchelo.
   2. de lo contrario, coloque el valor en la lista ordenada y elimine el valor más grande de esa lista.

Distribución muestral

La otra opción es utilizar una aproximación que implique la distribución de muestreo. Si sus datos son normales, entonces el error estándar para n moderado es:

1.253 * sd / sqrt (n)

Para determinar el tamaño de n con el que estaría contento, ejecuté una simulación rápida de Montecarlo en R

n = 10000
outside.ci.uni = 0
outside.ci.nor = 0
N=1000
for(i in 1:N){
  #Theoretical median is 0
  uni = runif(n, -10, 10)
  nor  = rnorm(n, 0, 10)

  if(abs(median(uni)) > 1.96*1.253*sd(uni)/sqrt(n))
    outside.ci.uni = outside.ci.uni + 1

  if(abs(median(nor)) > 1.96*1.253*sd(nor)/sqrt(n))
    outside.ci.nor = outside.ci.nor + 1
}

outside.ci.uni/N
outside.ci.nor/N

Para n = 10000, el 15% de las estimaciones medias uniformes estaban fuera del IC.

Puede intentar encontrar una mediana basada en la distribución de frecuencia agrupada, aquí hay algunos detalles

Aquí hay una respuesta a la pregunta hecha en stackoverflow: https://stackoverflow.com/questions/1058813/on-line-iterator-algorithms-for-estimating-statistical-median-mode-skewness/2144754#2144754

La actualización iterativa mediana + = eta * sgn (muestra - mediana) parece que podría ser un camino a seguir.

El Algoritmo Remedian (PDF) proporciona una estimación mediana de una pasada con bajos requisitos de almacenamiento y precisión bien definida.

El remedio con base b procede calculando medianas de grupos de observaciones b, y luego medianas de estas medianas, hasta que solo quede una estimación. Este método simplemente necesita k matrices de tamaño b (donde n = b ^ k) ...

Si los valores que está utilizando están dentro de un cierto rango, digamos 1 a 100000, puede calcular eficientemente la mediana en un número extremadamente grande de valores (digamos, billones de entradas), con un cubo entero (este código tomado de BSD con licencia ea -utils / sam-stats.cpp)

class ibucket {
public:
    int tot;
    vector<int> dat;
    ibucket(int max) {dat.resize(max+1);tot=0;}
    int size() const {return tot;};

    int operator[] (int n) const {
        assert(n < size());
        int i;
        for (i=0;i<dat.size();++i) {
            if (n < dat[i]) {
                return i;
            }
            n-=dat[i];
        }
    }

    void push(int v) {
        assert(v<dat.size());
        ++dat[v];
        ++tot;
    }
};


template <class vtype>
double quantile(const vtype &vec, double p) {
        int l = vec.size();
        if (!l) return 0;
        double t = ((double)l-1)*p;
        int it = (int) t;
        int v=vec[it];
        if (t > (double)it) {
                return (v + (t-it) * (vec[it+1] - v));
        } else {
                return v;
        }
}