¿Cómo mantener un histograma dinámico?

Question

¿existe un algoritmo conocido + estructura de datos para mantener un histograma dinámico?

Imagine que tengo una secuencia de datos (x_1, w_1), (x_2, w_2), ... donde los x_t son dobles, que representan una variable medida y w_t es el peso asociado.

tan sólo pudiera hacer la (pseudo código en Python) obvia:

x0,xN = 0, 10 
numbins = 100 
hist = [(x0 + i * delta , 0) for i in xrange(numbins)] 
def updateHistogram(x, w): 
    k = lookup(x, hist) #find the adequated bin where to put x 
    hist[k][1] += 1 

pero tengo algunos problemas con eso cuando tengo un flujo continuo de datos. No tengo el conjunto de datos completo en las manos, y tengo que verificar el histograma entre la recopilación de datos. Y no tengo ninguna expectativa sobre: ​​

• los tamaños bin ideales para no terminar con una gran cantidad de contenedores vacíos,
• el rango de los datos

Así que me gustaría definir el Papeleras dinámicamente. Podría hacer lo estúpida:

for x in data_stream: 
     data.append(x) 
     hist = make_histogram(data) 

pero supongo que esto va a ser lento muy rápidamente ...

Si los pesos de todos los que la igualdad de una de las cosas que pensé que era el almacenamiento de los datos en una matriz ordenada e insertando nuevos datos de una manera que mantiene ordenada la matriz. Esta manera de que pudiera tener:

data = sortedarray(); 
for x in data_stream: 
    data.insert(x) 
    bins = [ data[int(i * data.size()/numbins)] for i in xrange(numbins)] 

y el recuento dentro de cada bin serían iguales a data.size()/numbins para todos los contenedores.

No puedo pensar en una forma de incluir los pesos en esto ... ¿alguien tiene alguna sugerencia? (También sería bienvenido el conocimiento sobre las bibliotecas de C++ que hacen esto).

EDIT: (para la clarificación pedido)

El x_t son números de punto flotante. Para calcular el histograma, debo dividir el rango continuo en el que las x pertenecen en varios compartimientos. Así que tendré una secuencia de números bin [0], bin [1], etc ... así que debo determinar por qué lo hago bin [i] < x < bin [i + 1].

Así es como suele hacer un histograma cuando tiene todos los datos de antemano. Entonces conocería los límites max (x) y min (x) y sería fácil determinar los contenedores adecuados. Podría tenerlos igualmente espaciados entre min (x) y max (x), por ejemplo.

Si no conoce el rango de antemano, no puede determinar las ubicaciones. Podría recibir una x que no caiga en ningún contenedor. O podría haber muchos contenedores vacíos porque eligió un rango demasiado grande para crear los contenedores.

Answer 1

Cómo determinar el número de contenedores

Hay una serie de reglas para determinar el number of bins en un histograma.Para su problema, me gustaría ir con la elección de Scott:

bin_width = 3.5*sd*n^{-1/3} 

donde sd es la desviación estándar y n es el número de puntos de datos. Crucialmente, puede usar un algoritmo online para calcular la desviación estándar. El número de contenedores, k, está dada por:

k = ceil((max(x) - min(x))/bin_width) 

de almacenamiento los datos de

Supongamos que hemos observado N puntos de datos. Entonces, el intervalo de confianza para la desviación estándar,

Lower limit: sd*sqrt((N-1)/CHIINV((alpha/2), N-1)) 
Upper limit: sd*sqrt((N-1)/CHIINV(1-(alpha/2), N-1)) 

donde PRUEBA.CHI.INV es un valor de la distribución chi-cuadrado. Cuando N = 1000, el CI para la sd es:

(0.96*sd, 1.05*sd) 

y así un IC del 95% el bin-anchura es:

(3.5*0.96*sd*1000^{-1/3}, 3.5*1.05*sd*1000^{-1/3}) 
(0.336*sd, 0.3675*sd) 

Usted puede obtener algo similar para el número de bins.

Algoritmo

1. almacenar todos los datos hasta que haya una buena estimación de la papelera de ancho óptimo , por ejemplo cuando el CI inferior y superior para el número de contenedores son iguales.
2. Crea la cantidad de contenedores y coloca los datos en contenedores.
3. Todos los nuevos puntos de datos se ponen en los contenedores, luego se descartan.

Comentarios

1. regla El Freedman-Diaconis' es mejor para elegir el número de contenedores, pero implica el rango inter-cuantil que es calcular un poco más complejo en línea.
2. Técnicamente, el intervalo CI no es correcto cuando los datos son secuenciales. Pero si establece una cantidad mínima razonable de puntos de datos para observar, digamos ~ 100 o 1000, debería estar bien.
3. Esto supone que todos los datos siguen la misma distribución.
4. El número de contenedores depende de n^{- 1/3}. Si sabe aproximadamente cuántos puntos esperar, es decir, 10^5, 10^6 o 10^7, entonces podría crear contenedores más pequeños con la expectativa de cambiar el ancho del contenedor en el futuro.

Answer 2

ROOT es la herramienta utilizada por los físicos de partículas para este tipo de trabajo ... y viene con enlaces de pitón. Eso sí, no es una pieza de software ligera.

en C++ que haría algo como

TH1D hist("hist","longer title for hist",numbins,lowlimit,highimit); 

... 

for (int i=0; i<num; ++i){ 
    hist.Fill(x[i],w[i]); 
} 

... 

hist.Draw(); 

---

RAÍZ ofrece ninguna solución integrada al problema de agrupación, las entradas por debajo/por encima del rango binned se añaden al flujo de más de sub/papeleras

Inicialmente, puede establecer el agrupamiento en un amplio rango y convertir a un rango más corto en un momento posterior. Creo que el método es Rebin. Todas las limitaciones obvias se aplican.

Answer 3

Tengo algo de experiencia con la tabla de frecuencias y el histograma. Solo necesita valores mínimos y máximos para decidir el ancho del contenedor. Por lo tanto, en el caso de datos grandes, ya conocería los valores posibles de min y max. y así calcular fácilmente el ancho del contenedor de antemano, antes de que los datos se transmitan.

Como parte de los datos están entrando, solo puede actualizar los contenedores necesarios de acuerdo con cada área del contenedor y visualizar el histograma.

Answer 4

Parece que desea una implementación del siguiente tipo de datos abstractos.

insert(x, w): add item x to the collection with weight x 
select(p): return the item greater than a p weighted fraction of the items 

Por ejemplo, select(0) devuelve el mínimo, select(0.5) Devuelve la mediana ponderada, y select(1) Devuelve el máximo.

Implementaré este ADT en una de dos formas. Si la selección no es frecuente, colocaría los datos en una matriz y usaría un algoritmo de selección de tiempo lineal, para inserciones O (1) -time y O (n) -time selecciones. Si la selección es frecuente, usaría un árbol de búsqueda binaria donde cada nodo almacena el peso total en su subárbol. Por ejemplo, después

insert(2, 10) 
insert(1, 5) 
insert(3, 100) 
insert(4, 20) 

el árbol podría ser similar

2 (135) 
/\ 
/ \ 
1 (5) 4 (120) 
    /
    /
    3 (100) 

Ahora, para encontrar la mediana ponderada, se multiplica por 1350.5 y obtener 67.5 como el "índice" deseada. Comenzando por la raíz 2, encontramos que 5 es menor que 67.5, por lo que el elemento no está en el subárbol izquierdo y restamos 5 para obtener 62.5, el índice en el resto del árbol. Como 135 - 120 = 15 es menor que 62.5, la mediana no es 2. Restamos 15 de 62.5 para obtener 47.5 y descendemos a 4. En 4, encontramos que 100 es mayor que 47.5, por lo que 3 es la mediana.

Asumiendo un árbol balanceado, el tiempo de ejecución de insert y select es O(log n). Si estuviera implementando desde cero, probablemente optaría por un árbol desplegable.