de manera incremental de contar cuantiles de gran cantidad de datos

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

Pregunta

Necesito contar los cuantiles para un gran conjunto de datos.

Vamos a suponer que podemos obtener los datos sólo a través de algunas partes (es decir, una fila de una matriz grande). Para contar el Q3 cuantil 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 la de contar con algunos parámetros de mediados de los resultados de la primera fila y luego ajustar paso a paso para los próximos filas.

Nota:

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

Esta pregunta es similar a “on-line ”(iterador) algoritmos para estimar la mediana estadística, modo, asimetría, curtosis , pero necesito contar cuantiles.

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

Antes de tratar de poner en práctica estos enfoques, que se preguntó si tal vez hay otras maneras más rápidas, de contar los 0,25 / 0,75 cuantiles?

¿Fue útil?

Solución 5

Inspirado por esta respuesta he creado un método que estima los cuantiles bastante bueno. Es buena aproximación suficiente para mis propósitos.

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

Así que si podemos aproximar la mediana, podemos en forma 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);
}

A destacar:

  • Si la distribución de sus datos es extraño, que tendrá que tener eta más grandes con el fin de ajustarse a los datos extraño. Sin embargo, la precisión será peor.
  • Si la distribución es extraño, pero ya se sabe el tamaño total de su colección (es decir, N) se puede ajustar el parámetro eta de esta manera: en el beggining establece la eta a ser casi igual a un valor grande (es decir, 0,2). A medida que pasa el lazo, menor es el valor de eta así cuando llegue a casi el final de la colección, el eta será casi igual a 0 (por ejemplo, en compute bucle de esa manera: eta = 0.2 - 0.2*(i/N);

Otros consejos

Secundo la idea de utilizar cubos. No se limite a 100 cubos - bien podría utilizar 1 millón. La parte difícil es escoger sus gamas de cubo para que todo no termine en un solo cubo. Probablemente la mejor manera de estimar los rangos de cubo es tomar una muestra aleatoria razonable de sus datos, calcular los 10% y 90% cuantiles utilizando el algoritmo de ordenación simple, a continuación, generar cubos de igual tamaño para llenar ese rango. No es perfecto, pero si sus datos no es de una distribución súper raro, que debería funcionar.

Si usted no puede hacer muestras al azar, que está en más problemas. Usted puede recoger una estimación inicial bucketing en función de su distribución de datos era de esperar, a continuación, mientras se trabaja a través de sus datos en caso de cualquier cubo (normalmente el primer o el último cubo) se pone demasiado lleno, empezar de nuevo con una nueva gama de cubo.

Hay un algoritmo más reciente y mucho más simple para esto que ofrece 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 tanto los límites del tamaño de la estructura de datos y garantiza una mayor precisión para la pequeña o grande q. El algoritmo está disponible en varios idiomas y muchos paquetes. La versión MergingDigest no requiere la asignación dinámica ... una vez que el MergingDigest se crea una instancia, no se requiere ninguna nueva asignación montón.

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

  1. Sólo recuperar los datos que realmente necesita -. Es decir, lo que sea de valor (s) está / están siendo utilizados como la clave para la clasificación, no todo lo demás asociado a él
  2. Usted probablemente puede utilizar Seleccionar algoritmo de Tony Hoare para encontrar su cuantil más rápidamente que clasificando todos los datos.

Si los datos tienen una distribución de Gauss, se puede estimar los cuantiles de la desviación estándar. Asumo que sus datos no es gaussiano distribuido o usted acaba de estar usando la SD de todos modos.

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

  • primera pasada, calcular la max, min, SD y media.
  • segundo paso, dividir el intervalo [min, max] en algún número de cubetas (por ejemplo 100); hacer lo mismo para (media - 2 * SD, media + 2 SD *) (con cubos adicionales para los valores extremos). A continuación, ejecute a través de los datos de nuevo, los números lanzando en estos cubos.
  • Count cubos hasta que esté en el 25% y el 75% de los datos. Si desea obtener extra de fantasía, se puede interpolar entre los valores de cubo. (Es decir, si necesita el 10% de un cubo para que alcance su 25o cuantil, suponga que el valor es 10% de la distancia desde la baja unido al límite superior.)

Esto debe darle un buen algoritmo lineal de tiempo que funciona bien para la mayoría de los conjuntos de datos no del todo-perversa.

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