Come mantenere un istogramma dinamico?

Question

esiste un algoritmo noto + struttura dati per mantenere un istogramma dinamico?

Immaginate di avere un flusso di dati (x_1, w_1), (x_2, w_2), ... dove x_t sono doppi, che rappresentano alcune variabili misurate e w_t è il peso associato.

ho potuto solo fare il (codice di pseudo-python) ovvia:

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 

Ma ho alcuni problemi con che quando ho un flusso continuo di dati. Non ho il set di dati completo in mano e devo controllare l'istogramma tra la raccolta dei dati. E non ho alcuna aspettativa su:

• le dimensioni bin ideali per non finire con un sacco di bidoni vuoti,
• la gamma dei dati

Quindi mi piacerebbe definire il scomparti dinamicamente. Ho potuto fare la cosa stupida:

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

ma credo che questo avrà rallenterà molto rapidamente ...

Se i tutti i pesi in cui la parità una delle cose che ho pensato è stata la memorizzazione dei dati in un array ordinato e l'inserimento di nuovi dati in un modo che ha mantenuto ordinato l'array. In questo modo ho potuto avere:

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

e il conteggio all'interno di ogni bin sarebbe pari a data.size()/numbins per tutti i contenitori.

Non riesco a pensare a un modo di includere i pesi in questo però ... qualcuno ha un suggerimento? (la conoscenza delle librerie C++ che fanno questo sarebbe benvenuta anche).

EDIT: (per il chiarimento richiesto)

Il x_t sono numeri in virgola mobile. Per calcolare l'istogramma devo dividere l'intervallo continuo in cui le x appartengono a un numero di bin. Quindi avrò una sequenza di numeri bin [0], bin [1], etc ... quindi devo determinare per cosa faccio bin [i] < x < bin [i + 1].

Questo è il modo in cui si esegue di solito un istogramma quando si hanno tutti i dati in anticipo. Dovresti quindi conoscere i limiti max (x) e min (x) e sarebbe facile determinare contenitori adeguati. Potresti averli equamente distanziati tra min (x) e max (x), per esempio.

Se non si conosce l'intervallo in anticipo, non è possibile determinare i raccoglitori. Potresti ricevere una x che non cade in nessun contenitore. Oppure potresti scegliere molti contenitori vuoti perché hai scelto un intervallo troppo grande per creare i contenitori.

Answer 1

Come determinare il numero di bin

Ci sono una serie di regole per la determinazione del number of bins in un istogramma.Per il vostro problema, vorrei andare con la scelta di Scott:

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

dove sd è la deviazione standard e n è il numero di punti di dati. Fondamentalmente, è possibile utilizzare un algoritmo online per calcolare la deviazione standard. Il numero di contenitori, k, è data da:

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

bagagli i dati

Supponiamo abbiamo osservato punti dati N. Poi l'intervallo di confidenza per la deviazione standard,

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

dove INV.CHI è un valore dalla distribuzione del chi quadrato. Quando N = 1000, l'IC per la sd è:

(0.96*sd, 1.05*sd) 

e così un IC 95% il bin-larghezza è:

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

È possibile ottenere qualcosa di simile per il numero di contenitori.

Algoritmo

1. memorizzare tutti i dati fino ad avere una buona stima della ottimale bin-width , dire quando il CI inferiore e superiore per il numero di cassonetti sono uguali.
2. Creare il numero di contenitori e inserire i dati nei raccoglitori.
3. Tutti i nuovi punti dati vengono inseriti nei contenitori, quindi eliminati.

Commenti

1. regola Il Freedman-Diaconis' è meglio per la scelta del numero di contenitori, ma coinvolge l'intervallo inter-quantile che è calcolare un po 'più complicato online.
2. Tecnicamente, l'intervallo CI non è corretto quando i dati sono sequenziali. Ma se si imposta un numero minimo ragionevole di punti dati da osservare, ad esempio ~ 100 o 1000, si dovrebbe essere OK.
3. Ciò presuppone che tutti i dati seguano la stessa distribuzione.
4. Il numero di contenitori dipende da n^{- 1/3}. Se sai approssimativamente quanti punti aspettarti, cioè 10^5, 10^6 o 10^7, allora potresti creare contenitori più piccoli con l'aspettativa di cambiare la larghezza del cestino in futuro.

Answer 2

ROOT è lo strumento utilizzato dai fisici delle particelle per questo tipo di lavoro ... e viene fornito con collegamenti Python. Intendiamoci, non è un software leggero.

in C++ si dovrebbe fare qualcosa di simile

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(); 

---

ROOT fornisce una soluzione integrata al problema binning, ingressi di sotto/sopra la gamma cestinate vengono aggiunti alla/over-flow sotto- cassonetti.

È possibile impostare inizialmente il binning su un ampio intervallo e convertirlo in un intervallo più breve in un secondo momento. Penso che il metodo sia Rebin. Si applicano tutte le ovvie limitazioni.

Answer 3

Ho una certa esperienza con la tabella delle frequenze e l'istogramma. Hai solo bisogno di valori minimi e massimi per decidere la larghezza del cestino. Quindi, in caso di dati di grandi dimensioni, si conoscono già i valori possibili di min e max. e quindi calcolare facilmente la larghezza del cestino prima che i dati siano in streaming.

Durante l'immissione dei dati, è possibile aggiornare solo i raccoglitori necessari in base a ciascuna area del cestino e visualizzare l'istogramma.

Answer 4

Sembra come se si volesse un'implementazione del seguente tipo di dati astratto.

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 

Ad esempio, select(0) restituisce il minimo, select(0.5) restituisce la mediana ponderata e select(1) restituisce il massimo.

Vorrei implementare questo ADT in due modi. Se la selezione non è frequente, inserisco i dati in un array e utilizzo un algoritmo di selezione del tempo lineare, per gli inserimenti O (1) e O (n) -time. Se la selezione è frequente, utilizzerei un albero di ricerca binario in cui ogni nodo memorizza il peso totale nella sua sottostruttura. Ad esempio, dopo

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

l'albero potrebbe essere simile

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

Ora, per trovare la mediana ponderata, moltiplicare 135 da 0.5 e ottenere 67.5 come "indice" desiderato. A partire dalla radice 2, troviamo che 5 è inferiore a 67.5, quindi l'elemento non è nella sottostruttura di sinistra e sottraiamo 5 per ottenere 62.5, l'indice nel resto dell'albero. Poiché 135 - 120 = 15 è inferiore a 62.5, la mediana non è 2. Sottraiamo 15 da 62.5 per ottenere 47.5 e scendiamo a 4. A 4, troviamo che 100 è maggiore di 47.5, quindi 3 è la mediana.

Supponendo un albero bilanciato, il tempo di esecuzione di entrambi insert e select è O(log n). Se dovessi implementare da zero, probabilmente opterei per un albero di diffusione.