Approssimazione dell'istogramma per lo streaming dei dati

Question

Questa domanda è una leggera estensione di quella answered here. Sto lavorando per ri-implementare una versione dell'approssimazione dell'istogramma trovata nella sezione 2.1 di this paper, e mi piacerebbe ottenere tutte le mie anatre di fila prima di ricominciare questo processo. L'ultima volta, ho usato boost::multi_index, ma le prestazioni non erano le migliori, e vorrei evitare il logaritmico in numero di bucket inserire/trovare la complessità di un std::set. A causa del numero di istogrammi che sto utilizzando (uno per caratteristica per classe per nodo foglia di un albero casuale in una foresta casuale), la complessità computazionale deve essere il più possibile vicina alla costante.

Una tecnica standard utilizzata per implementare un istogramma implica la mappatura del valore reale di input in un numero di contenitore. A tale scopo, un metodo è:

1. inizializzare una matrice C standard di dimensione N, dove N = numero di contenitori; e
2. moltiplicare il valore di input (numero reale) di qualche fattore e scalare il risultato per ottenere il suo indice nell'array C.

Questo funziona bene per gli istogrammi con dimensione bin uniforme ed è piuttosto efficiente. Tuttavia, la sezione 2.1 della carta di cui sopra fornisce un algoritmo di istogramma senza dimensioni bin uniform.

Un altro problema è semplicemente moltiplicando il valore reale di input per un fattore e utilizzando il prodotto risultante come un indice non riesce con numeri negativi. Per risolvere questo problema, ho preso in considerazione l'identificazione di un binario "0" da qualche parte nell'array. Questo bin sarebbe centrato a 0.0; i contenitori sopra/sotto possono essere calcolati usando lo stesso metodo multiplo e piano appena spiegato, con la leggera modifica che il prodotto a pavimento può essere aggiunto a due o sottratto da due se necessario.

Questo solleva quindi la questione delle unioni: l'algoritmo della carta unisce i due contenitori più vicini, misurati da centro a centro. In pratica, ciò crea un'approssimazione dell'istogramma "frastagliata", poiché alcuni contenitori avrebbero conteggi estremamente grandi e altri no. Ovviamente, ciò è dovuto a contenitori di dimensioni non uniformi e non comporta alcuna perdita di precisione. Tuttavia, si verifica una perdita di precisione se proviamo a normalizzare i raccoglitori di dimensioni non uniformi per realizzare l'uniforme. Ciò è dovuto al fatto che i campioni di m/2 cadono a sinistra ea destra del centro del contenitore, dove m = numero di bin. Potremmo modellare ogni bin come gaussiano, ma ciò causerà comunque una perdita di precisione (anche se minima)

Quindi è lì che sono bloccato in questo momento, portando a questa importante domanda: Qual è il modo migliore per implementare un istogramma che accetta i dati di streaming e memorizza ciascun campione in contenitori di dimensioni uniformi?

Answer 1

Conserva quattro variabili.

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

Quando un nuovo campione x arriva, calcolare double i = floor(x - lower_bound)/bin_size. Se i >= 0 && i < N, incrementare count[i]. Se i >= N, quindi ripetutamente doppio bin_size fino a x - lower_bound < N * bin_size. Ad ogni raddoppio, regolare i conteggi (ottimizzarlo sfruttando la scarsità per raddoppiamenti multipli).

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; 

Il caso i < 0 è più complicato, dal momento che abbiamo bisogno di diminuire lower_bound così come aumentare bin_size (ancora una volta, l'ottimizzazione per scarsità o regolare i conteggi in un solo passaggio).

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; 
} 

I casi eccezionali sono costosi, ma capita solo un numero logaritmico di volte nella gamma dei vostri dati attraverso la dimensione iniziale bin.

Se si implementa questa in virgola mobile, essere consapevoli che numeri in virgola mobile non sono numeri reali e che dichiarazioni come lower_bound -= N * bin_size possono comportano male (in questo caso, se N * bin_size è molto più piccolo di lower_bound). Raccomando che bin_size sia una potenza della radix (di solito due) in ogni momento.