de manera incremental de contar cuantiles de gran conjunto de datos

Question

tengo que contar los cuantiles para un gran conjunto de datos.

Asumamos que podemos obtener los datos sólo a través de algunas partes (es decir, una fila de una matriz grande). Para contar el cuantil Q3 una necesidad de conseguir todas las partes de los datos y almacenarlo en algún lugar, a continuación, ordenar y contar el cuantil:

List<double> allData = new List<double>(); 
// This is only an example; the portions of data are not really rows of some matrix 
foreach(var row in matrix) 
{ 
    allData.AddRange(row); 
} 

allData.Sort(); 
double p = 0.75 * allData.Count; 
int idQ3 = (int)Math.Ceiling(p) - 1; 
double Q3 = allData[idQ3]; 

me gustaría encontrar una manera de obtener el cuantil sin almacenar los datos en una variable intermedia. La mejor solución sería contar algunos parámetros de resultados intermedios para la primera fila y luego ajustarlos paso por paso para las siguientes filas.

Nota:

• Estos datos son muy grandes (ca 5000 elementos en cada fila)
• El Q3 se puede estimar, que no tiene que ser un valor exacto.
• que llamar las porciones de datos "filas", pero pueden tener diferentes leghts! Por lo general, no varía mucho (+/- cientos de muestras) ¡pero varía!

Esta pregunta es similar a “On-line” (iterator) algorithms for estimating statistical median, mode, skewness, kurtosis, pero necesito contar los cuantiles.

También hay pocas noticias en esta sección, es decir:

• An Efficient Algorithm for the Approximate Median Selection Problem
• Incremental quantile estimation for massive tracking

Antes de tratar de poner en práctica estos enfoques, me preguntaba si tal vez hay alguna otra manera, más rápido de contar los cuantiles 0.25/0.75?

Answer 1

Inspirado por this answer Creé un método que estima los cuantiles bastante buenos. Es una aproximación lo suficientemente cerca para mis propósitos.

La idea es la siguiente: el cuantil 0.75 es de hecho una mediana de todos los valores que se encuentra por encima de la mediana global. Y, respectivamente, 0,25 cuantil es una mediana de todos los valores por debajo de la mediana global.

Entonces, si podemos aproximarnos a la mediana, podemos de manera similar aproximar los cuantiles.

double median = 0; 
double q1 = 0; 
double q3 = 0; 
double eta = 0.005; 

foreach(var value in listOfValues) // or stream, or any other large set of data... 
{ 
    median += eta * Math.Sign(p.Int - median); 
} 
// Second pass. We know the median, so we can count the quantiles. 
foreach(var value in listOfValues) 
{ 
    if(p.Int < median) 
     q1 += eta*Math.Sign(p.Int - q1); 
    else 
     q3 += eta*Math.Sign(p.Int - q3); 
} 

Observaciones:

• Si la distribución de sus datos es extraña, necesitará tener mayor eta con el fin de ajustarse a los datos extraños. Pero la precisión será peor.
• Si la distribución es extraña, pero conoce el tamaño total de su colección (es decir, N) puede ajustar el parámetro eta de esta manera: en el inicio configure eta para que sea casi igual a un valor grande (es decir, 0.2). A medida que pasa el bucle, bajar el valor de eta así cuando llegue a casi el final de la colección, el eta habrá casi igual 0 (por ejemplo, en bucle calcularla como que: eta = 0.2 - 0.2*(i/N);

Answer 2

1. Recupere solo los datos que realmente necesita, es decir, los valores que se utilizan como clave para la clasificación, no todo lo demás asociado.
2. probablemente puede utilizar Select algoritmo de Tony Hoare para encontrar su cuantil más rápidamente que clasificando todos los datos.

Answer 3

Si sus datos tienen una distribución gaussiana, puede estimar los cuantiles a partir de la desviación estándar. Supongo que sus datos no están distribuidos por Gauss o de todos modos estaría utilizando la tarjeta SD.

Si usted puede pasar a través de los datos dos veces, yo haría lo siguiente:

• primer pase, calcular el máximo, mínimo, Dakota del Sur y la media.
• segundo paso, dividir el intervalo [min, max] en algún número de cubetas (por ejemplo 100); haga lo mismo para (promedio - 2 * SD, promedio + 2 * SD) (con cubos adicionales para valores atípicos). Luego revise nuevamente los datos, lanzando números a estos segmentos.
• cubos Contar hasta que esté en el 25% y el 75% de los datos. Si desea obtener una mayor extravagancia, puede interpolar entre los valores de la cubeta. (Es decir, si necesita un 10% de un cubo para alcanzar su 25 ° cuantil, suponga que el valor es un 10% del camino desde el límite bajo al límite superior.)

Esto debería darle un buen algoritmo de tiempo lineal que funciona bien para la mayoría de los conjuntos de datos no totalmente perversos.

Answer 4

En segundo lugar, la idea de utilizar cubos. No se limite a 100 cubos, podría usar 1 millón. La parte difícil es elegir los rangos de su cubeta para que todo no termine en una sola cubeta. Probablemente la mejor manera de estimar los rangos de su cubeta es tomar una muestra razonable al azar de sus datos, calcular los 10% y 90% de los cuantiles usando el algoritmo de clasificación simple, luego generar cubos de igual tamaño para llenar ese rango. No es perfecto, pero si sus datos no provienen de una distribución súper rara, debería funcionar.

Si no puede hacer muestras aleatorias, tiene más problemas. Puede elegir una conjetura inicial basada en la distribución de datos esperados, y luego, al trabajar con sus datos, si alguna cubeta (generalmente la primera o la última cubeta) se sobrecarga, comience nuevamente con un nuevo rango de cubetas.

Answer 5

q-digest es un algoritmo línea aproximada que le permite calcular cuantil: http://www.cs.virginia.edu/~son/cs851/papers/ucsb.sensys04.pdf

Aquí es una implementación:

https://github.com/airlift/airlift/blob/master/stats/src/main/java/io/airlift/stats/QuantileDigest.java

Answer 6

Hay un algoritmo más reciente y mucho más simple para esto que proporciona muy buenas estimaciones de los cuantiles extremos.

La idea básica es que los contenedores más pequeños se utilizan en los extremos de una manera que limita el tamaño de la estructura de datos y garantiza una mayor precisión para q pequeño o grande. El algoritmo está disponible en varios idiomas y muchos paquetes. La versión de MergingDigest no requiere asignación dinámica ... una vez que MergingDigest se crea una instancia, no se requiere más asignación de pila.

Ver https://github.com/tdunning/t-digest