сглаживание нерегулярных данных о времени - PullRequest
Новая
       18

сглаживание нерегулярных данных о времени

6 голосов
/ 21 июня 2009

Учитывая таблицу, в которой первый столбец находится в секундах после определенной контрольной точки, а второй - произвольное измерение: 

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 
    ...

Как видите, измерения производятся в нерегулярные моменты времени. Мне нужно сгладить данные, усредняя показания за 100 секунд до каждого измерения (в Python). Поскольку таблица данных огромна, метод, основанный на итераторах, действительно предпочтителен. К сожалению, после двух часов кодирования я не могу найти эффективное и элегантное решение.

Кто-нибудь может мне помочь?

EDIT S

  1. Я хочу одно сглаженное чтение для каждого необработанного чтения, и сглаженное чтение должно быть средним арифметическим необработанного чтения и любых других за предыдущие 100 (дельта) секунд. (Джон, ты прав)

  2. Огромные ~ 1e6 - 10e6 строк + нужно работать с тесной оперативной памятью

  3. Данные примерно случайного блуждания

  4. Данные отсортированы

РАЗРЕШЕНИЕ

Я проверил решения, предложенные J Machin и Yairchu. Они оба дали одинаковые результаты, однако, на моем наборе данных, версия J Machin работает экспоненциально, в то время как версия yairchu линейна. Ниже приводится время выполнения, измеренное с помощью IPython % timeit (в микросекундах): 

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

Спасибо всем за помощь.

Ответы [ 8 ]

3 голосов
/ 21 июня 2009

Я использую результат суммирования, к которому я добавляю новых членов и вычитаю старых. Однако при этом могут возникать накопленные неточности с плавающей запятой.

Поэтому я реализую "Deque" со списком. И всякий раз, когда моя Deque перераспределяется на меньший размер. Я пересчитываю сумму одновременно.

Я также вычисляю среднее значение до точки x, включая точку x, поэтому есть как минимум одна точка выборки для усреднения. 

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)
2 голосов
/ 21 июня 2009

Вы не сказали точно, когда хотите вывод. Я предполагаю, что вы хотите одно сглаженное чтение для каждого необработанного чтения, и сглаженное чтение должно быть средним арифметическим необработанного чтения и любых других за предыдущие 100 (дельта) секунд.

Краткий ответ: используйте collection.deque ... он никогда не будет содержать больше, чем "дельта" секунд чтения. Как я настроил, вы можете рассматривать деку как список и легко вычислять среднее значение или некоторую причудливую штуковину, которая придает больший вес последним показаниям.

Длинный ответ: 

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

Редактировать

Универсальный магазин: купите здесь свою причудливую штуковину. Вот код: 

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

где upsilon должен быть чуть меньше 1,0 (<= ноль недопустимо, чуть больше нуля делает небольшое сглаживание, вы получаете среднее арифметическое плюс потраченное время процессора, а больше, чем наоборот) 1015 *

0 голосов
/ 23 июня 2009

Хотя это дает экспоненциально убывающее среднее, а не общее среднее, я думаю, вам может понадобиться то, что я назвал экспоненциальным скользящим средним с переменной альфа , который на самом деле является однополюсным фильтром нижних частот , Теперь есть решение этого вопроса, и оно работает во времени, линейном по отношению к количеству точек данных. Посмотрите, работает ли это для вас.

0 голосов
/ 21 июня 2009

O (1) памяти, если вы можете повторять ввод более одного раза - вы можете использовать один итератор для «левого» и один для «правого». 

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
0 голосов
/ 21 июня 2009

Похоже, вам нужна простая формула округления. Чтобы округлить любое число до произвольного интервала:

раунд (число / интервал) * Интервал

Вы можете заменить раунд с полом или потолком на "ведущие" или "поскольку" аффекты Он может работать на любом языке, включая SQL.

0 голосов
/ 21 июня 2009

Это делает его линейным: 

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
0 голосов
/ 21 июня 2009

Ваши данные кажутся примерно линейными:

Участок ваших данных http://rix0r.nl/~rix0r/share/shot-20090621.144851.gif

Какой тип сглаживания вы ищете? Наименьшие квадраты соответствуют линии для этого набора данных? Какой-то фильтр нижних частот? Или что-то еще?

Пожалуйста, сообщите нам приложение, чтобы мы могли посоветовать вам немного лучше.

РЕДАКТИРОВАТЬ: Например, в зависимости от приложения, интерполяция линии между первой и последней точкой может быть достаточно для ваших целей.

0 голосов
/ 21 июня 2009

что-то вроде этого, сохраняйте значения до тех пор, пока разница во времени с последним временем не станет> 100, усредните и получите такие значения например, 

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
...