lisciatura dati temporali irregolarmente campionati

Question

Data una tabella in cui la prima colonna è secondi oltre un certo punto di riferimento e la seconda è una misura arbitraria:

6 0.738158581 
21 0.801697222 
39 1.797224596 
49 2.77920469 
54 2.839757536 
79 3.832232283 
91 4.676794376 
97 5.18244704 
100 5.521878863 
118 6.316630137 
131 6.778507504 
147 7.020395216 
157 7.331607129 
176 7.637492223 
202 7.848079136 
223 7.989456499 
251 8.76853608 
278 9.092367123 
    ... 

Come si vede, le misurazioni sono campionati in punti temporali irregolari . Ho bisogno di lisciare i dati calcolando la media della lettura fino a 100 secondi prima di ogni misurazione (in Python). Poiché la tabella di dati è enorme, un metodo basato su iteratore è davvero preferito. Sfortunatamente, dopo due ore di programmazione non riesco a capire una soluzione efficiente ed elegante.

Qualcuno può aiutarmi?

EDIT s

1. voglio una lettura lisciato per ogni lettura cruda, e la lettura lisciato è quello di essere la media aritmetica della lettura prima e tutti gli altri nei precedenti 100 (delta) secondi . (John, hai ragione)

2. enormi ~ 1E6 - linee 10E6 + necessità di lavorare con stretti RAM

3. I dati sono di circa random walk

4. I dati vengono ordinati

RISOLUZIONE

Ho provato le soluzioni proposte da J Machin e yairchu. Entrambi hanno dato gli stessi risultati, tuttavia, sul mio set di dati, la versione di J Machin ha prestazioni esponenziali, mentre quella di yairchu è lineare. Di seguito sono riportati i tempi di esecuzione come misurato da % timeit di IPython (in microsecondi):

data size J Machin yairchu 
10  90.2  55.6 
50   930   258 
100   3080  514 
500   64700  2660 
1000  253000  5390 
2000  952000  11500 

Grazie a tutti per l'aiuto.

Answer 1

Sto usando un risultato di somma a cui sto aggiungendo i nuovi membri e sottraendo quelli vecchi. Tuttavia in questo modo si può soffrire accumulando inesattezze in virgola mobile.

Pertanto, realizzo un "Deque" con un elenco. E ogni volta che la mia Deque si riallinea a una dimensione più piccola. Ricalcolo la somma nella stessa occasione.

Sto anche calcolando la media fino al punto x compreso il punto x quindi c'è almeno un punto di campionamento in media.

def getAvgValues(data, avgSampleTime): 
    lastTime = 0 
    prevValsBuf = [] 
    prevValsStart = 0 
    tot = 0 
    for t, v in data: 
    avgStart = t - avgSampleTime 
    # remove too old values 
    while prevValsStart < len(prevValsBuf): 
     pt, pv = prevValsBuf[prevValsStart] 
     if pt > avgStart: 
     break 
     tot -= pv 
     prevValsStart += 1 
    # add new item 
    tot += v 
    prevValsBuf.append((t, v)) 
    # yield result 
    numItems = len(prevValsBuf) - prevValsStart 
    yield (t, tot/numItems) 
    # clean prevVals if it's time 
    if prevValsStart * 2 > len(prevValsBuf): 
     prevValsBuf = prevValsBuf[prevValsStart:] 
     prevValsStart = 0 
     # recalculate tot for not accumulating float precision error 
     tot = sum(v for (t, v) in prevValsBuf) 

Answer 2

e qualcosa del genere, continua a memorizzare i valori fino alla differenza di orario con l'ultima volta è> 100, la media e produce tali valori ad es.

def getAvgValues(data): 
    lastTime = 0 
    prevValues = [] 
    avgSampleTime=100 

    for t, v in data: 
     if t - lastTime < avgSampleTime: 
      prevValues.append(v) 
     else: 
      avgV = sum(prevValues)/len(prevValues) 
      lastTime = t 
      prevValues = [v] 
      yield (t,avgV) 

for v in getAvgValues(data): 
    print v 

Answer 3

Non hai detto esattamente quando vuoi l'output. Suppongo che tu voglia una lettura lisciata per ogni lettura grezza, e la lettura lisciata deve essere la media aritmetica della lettura grezza e qualsiasi altra nei 100 precedenti (delta) secondi.

Risposta breve: utilizzare un collections.deque ... non manterrà mai più di "delta" secondi di letture. Il modo in cui l'ho impostato è che puoi trattare la deque come una lista e calcolare facilmente la media o qualche gizmoide di fantasia che dà più peso alle letture recenti.

Risposta lunga:

>>> the_data = [tuple(map(float, x.split())) for x in """\ 
... 6  0.738158581 
... 21  0.801697222 
[snip] 
... 251  8.76853608 
... 278  9.092367123""".splitlines()] 
>>> import collections 
>>> delta = 100.0 
>>> q = collections.deque() 
>>> for t, v in the_data: 
...  while q and q[0][0] <= t - delta: 
...   # jettison outdated readings 
...   _unused = q.popleft() 
...  q.append((t, v)) 
...  count = len(q) 
...  print t, sum(item[1] for item in q)/count, count 
... 
... 
6.0 0.738158581 1 
21.0 0.7699279015 2 
39.0 1.112360133 3 
49.0 1.52907127225 4 
54.0 1.791208525 5 
79.0 2.13137915133 6 
91.0 2.49500989771 7 
97.0 2.8309395405 8 
100.0 3.12993279856 9 
118.0 3.74976297144 9 
131.0 4.41385300278 9 
147.0 4.99420529389 9 
157.0 5.8325615685 8 
176.0 6.033109419 9 
202.0 7.15545189083 6 
223.0 7.4342562845 6 
251.0 7.9150342134 5 
278.0 8.4246097095 4 
>>> 

Modifica

One-stop shop: ottenere la vostra fantasia gizmoid qui.Ecco il codice:

numerator = sum(item[1] * upsilon ** (t - item[0]) for item in q) 
denominator = sum(upsilon ** (t - item[0]) for item in q) 
gizmoid = numerator/denominator 

dove upsilon dovrebbe essere un po 'meno di 1,0 (< = zero è illegale, appena sopra lo zero fa poco levigante, quello che si ottiene la media aritmetica più il tempo di CPU sprecato, e maggiore di uno dà l'inverso del tuo scopo).

Answer 4

Suoi dati sembra essere grosso modo lineare:

Plot of your data http://rix0r.nl/~rix0r/share/shot-20090621.144851.gif

Che tipo di smoothing stai cercando? Un quadratino di una linea per questo set di dati? Una specie di filtro passa-basso? O qualcos'altro?

Si prega di dirci l'applicazione in modo che possiamo consigliarvi un po 'meglio.

MODIFICA: Ad esempio, a seconda dell'applicazione, l'interpolazione di una linea tra il primo e l'ultimo punto può essere sufficiente per i propri scopi.

Answer 5

Questo rende lineare:

def process_data(datafile): 
    previous_n = 0 
    previous_t = 0 
    for line in datafile: 
     t, number = line.strip().split() 
     t = int(t) 
     number = float(number) 
     delta_n = number - previous_n 
     delta_t = t - previous_t 
     n_per_t = delta_n/delta_t 
     for t0 in xrange(delta_t): 
      yield previous_t + t0, previous_n + (n_per_t * t0) 
     previous_n = n 
     previous_t = t 

f = open('datafile.dat') 

for sample in process_data(f): 
    print sample 

Answer 6

Suona come avete bisogno di una semplice formula di arrotondamento. Per arrotondare un numero qualsiasi di un intervallo arbitrario:

round (num/intervallo) * intervallo

È possibile sostituire rotonda con pavimento oa soffitto per "che porta fino a" o "dal momento che" colpisce. Può funzionare in qualsiasi lingua, incluso SQL.

Answer 7

O (1) memoria nel caso in cui è possibile iterare l'input più di una volta - è possibile utilizzare un iteratore per "sinistra" e uno per "destra".

def getAvgValues(makeIter, avgSampleTime): 
    leftIter = makeIter() 
    leftT, leftV = leftIter.next() 
    tot = 0 
    count = 0 
    for rightT, rightV in makeIter(): 
    tot += rightV 
    count += 1 
    while leftT <= rightT - avgSampleTime: 
     tot -= leftV 
     count -= 1 
     leftT, leftV = leftIter.next() 
    yield rightT, tot/count 

Answer 8

mentre dà una media diminuisce in modo esponenziale, piuttosto che una media totale, penso che si potrebbe voler quello che ho chiamato un exponential moving average with varying alpha, che in realtà è un filtro passa-basso unipolare. Ora c'è una soluzione a questa domanda, che corre nel tempo in modo lineare al numero di punti dati. Guarda se va bene per te.