Aproximación del histograma para transmitir datos

Question

Esta pregunta es una ligera extensión de la answered here. Estoy trabajando para volver a implementar una versión de la aproximación del histograma que se encuentra en la Sección 2.1 de this paper, y me gustaría obtener todos mis patos en una fila antes de comenzar este proceso nuevamente. La última vez, utilicé boost::multi_index, pero el rendimiento no fue el mejor, y me gustaría evitar la cantidad logarítmica de insertar/buscar complejidad de un cubo std::set. Debido a la cantidad de histogramas que estoy usando (uno por característica por clase por nodo hoja de un árbol aleatorio en un bosque aleatorio), la complejidad computacional debe ser lo más constante posible.

Una técnica estándar utilizada para implementar un histograma implica asignar el valor real de entrada a un número de contenedor. Para lograr esto, un método es:

1. inicializar una matriz C estándar de tamaño N, donde N = número de contenedores; y
2. multiplicar el valor de entrada (número real) por algún factor y bajar el resultado para obtener su índice en la matriz C.

Esto funciona bien para histogramas con un tamaño de bandeja uniforme, y es bastante eficiente. Sin embargo, la Sección 2.1 del documento vinculado anteriormente proporciona un algoritmo de histograma sin tamaños de contenedor uniformes.

Otro problema es que simplemente multiplicar el valor real de entrada por un factor y usar el producto resultante como un índice falla con números negativos. Para resolver esto, consideré identificar un contenedor '0' en algún lugar de la matriz. Este contenedor estaría centrado en 0.0; las casillas superiores/inferiores podrían calcularse usando el mismo método de multiplicación y piso que se acaba de explicar, con la ligera modificación de que el producto con piso se sumará a dos o se restará de dos según sea necesario.

Esto plantea la cuestión de las fusiones: el algoritmo en el documento combina los dos compartimientos más cercanos, medidos de centro a centro. En la práctica, esto crea una aproximación de histograma 'irregular', porque algunos contenedores tendrían recuentos extremadamente grandes y otros no. Por supuesto, esto se debe a los contenedores de tamaño no uniforme, y no da como resultado ninguna pérdida de precisión. Sin embargo, se produce una pérdida de precisión si tratamos de normalizar los contenedores de tamaño no uniforme para hacer el uniforme. Esto se debe a la suposición de que m/2 muestras caen a la izquierda y a la derecha del centro de contenedores, donde m = conteo de contenedores. Podríamos modelar cada contenedor como gaussiano, pero esto dará como resultado una pérdida de precisión (aunque mínima)

Así que ahí es donde estoy estancado ahora, lo que me lleva a esta gran pregunta: ¿Cuál es la mejor manera de implementar ¿un histograma que acepta datos de transmisión y almacena cada muestra en contenedores de tamaño uniforme?

Answer 1

Mantenga cuatro variables.

int N; // assume for simplicity that N is even 
int count[N]; 
double lower_bound; 
double bin_size; 

Cuando una nueva muestra x llega, calcular double i = floor(x - lower_bound)/bin_size. Si i >= 0 && i < N, entonces incremente count[i]. Si es i >= N, doble repetidamente bin_size hasta x - lower_bound < N * bin_size. En cada duplicación, ajuste los conteos (optimice esto explotando la dispersión para múltiples duplicaciones).

for (int j = 0; j < N/2; j++) count[j] = count[2 * j] + count[2 * j + 1]; 
for (int j = N/2; j < N; j++) count[j] = 0; 

i < 0 El caso es más complicado, ya que tenemos que disminuir lower_bound, así como aumentar bin_size (de nuevo, para optimizar la escasez o ajustar las cuentas en un solo paso).

while (lower_bound > x) { 
    lower_bound -= N * bin_size; 
    bin_size += bin_size; 
    for (int j = N - 1; j > N/2 - 1; j--) count[j] = count[2 * j - N] + count[2 * j - N + 1]; 
    for (int j = 0; j < N/2; j++) count[j] = 0; 
} 

Los casos excepcionales son caros, pero sólo ocurren una serie logarítmica de veces en el rango de los datos sobre el tamaño inicial bin.

Si decide implementar esta en coma flotante, ser conscientes de que los números de coma flotante no son números reales y que declaraciones como lower_bound -= N * bin_size pueden portan mal (en este caso, si N * bin_size es mucho más pequeño que lower_bound). Recomiendo que bin_size sea una potencia de la raíz (generalmente dos) en todo momento.