Necesito calcular los cuartiles (Q1,mediana y Q3) en tiempo real en un gran conjunto de datos sin guardar las observaciones. Probé por primera vez el P cuadrado algoritmo (Jain/Chlamtac), pero no estaba satisfecho con ella (un poco demasiado uso de la cpu y no convencido por la precisión, al menos en mi conjunto de datos).
Yo uso ahora el algoritmo FAME (Feldman/Shavitt) para la estimación de la mediana sobre la marcha y tratar de derivar el algoritmo para calcular también la Q1 y Q3 :
M = Q1 = Q3 = first data value
step =step_Q1 = step_Q3 = a small value
for each new data :
# update median M
if M > data:
M = M - step
elif M < data:
M = M + step
if abs(data-M) < step:
step = step /2
# estimate Q1 using M
if data < M:
if Q1 > data:
Q1 = Q1 - step_Q1
elif Q1 < data:
Q1 = Q1 + step_Q1
if abs(data - Q1) < step_Q1:
step_Q1 = step_Q1/2
# estimate Q3 using M
elif data > M:
if Q3 > data:
Q3 = Q3 - step_Q3
elif Q3 < data:
Q3 = Q3 + step_Q3
if abs(data-Q3) < step_Q3:
step_Q3 = step_Q3 /2
Para reanudar, simplemente utiliza la mediana de M obtenidos sobre la marcha para dividir el conjunto de datos en dos y, a continuación, volver a usar el mismo algoritmo tanto para Q1 y Q3.
Esto parece funcionar de alguna manera, pero no soy capaz de demostrar (no soy un matemático) . Es flawned ? Agradecería cualquier sugerencia o eventual otra técnica de montaje el problema.
Muchas gracias por su Ayuda !
==== EDITAR =====
Para aquellos que se interesan por este tipo de preguntas, después de un par de semanas, que finalmente terminó por el simple uso del Embalse de Muestreo con un revervoir de 100 los valores, y dio muy satistfying resultados (para mí).
