Вычисление стандартного отклонения по кольцевому буферу - PullRequest
Новая
       20

Вычисление стандартного отклонения по кольцевому буферу

3 голосов
/ 12 июля 2011

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

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

tl; dr: как я могу вычислить стандартное отклонение по кругубуфер с минимальными вычислительными затратами?

Ответы [ 3 ]

8 голосов
/ 12 июля 2011

Стандартное отклонение может быть выражено как: 

 stddev = sqrt(1/N * SUM(x[i]^2) - 1/N^2 * SUM(x[i])^2)

Для стандартного отклонения неоткорректированного образца. Для исправленного стандартного отклонения выборки можно написать: 

 stddev = sqrt(1/(N-1) * SUM(x[i]^2) - 1/(N^2-N) * SUM(x[i])^2)

Если вы поддерживаете два аккумулятора, один для SUM(x[i]^2) и один для SUM(x[i]), то их тривиально обновить для каждого нового значения (вычесть эффект самого старого значения и добавить эффект самого нового значения ). N конечно будет длиной вашего буфера.

Конечно, если вы делаете это с плавающей запятой, то вы, вероятно, столкнетесь с ошибками округления ((x + y) - x != y, в общем). Я не думаю, что есть какое-то легкое решение для этого.

2 голосов
/ 12 июля 2011

Сохраните три числа для набора: количество значений, сумма значений и сумма квадратов значений. Для удобства назовем их k, sn и sn2.

Если, как я думаю, вы подразумеваете, новое значение всегда заменяет старое значение в циклической очереди, то, возможно, число является постоянным. Или, возможно, очередь может быть меньше полной. В любом случае:

Каждый раз, когда вы добавляете значение в очередь, добавляете его к счетчику, добавляете это значение к сумме и добавляете квадрат этого значения к квадратной сумме. То есть, если вы добавите новое значение «n», то k = k + 1, sn = sn + n и sn2 = sn2 + n ^ 2.

Каждый раз, когда вы удаляете значение из очереди, вычитаете его из числа, вычитаете это значение из суммы и вычитаете квадрат этого значения из квадратной суммы. То есть, если вы удалите значение «n», то k = k-1, sn = sn-n и sn2 = sn2-n ^ 2.

Затем вы можете легко пересчитать стандартное отклонение после каждого изменения без необходимости пересчитывать все.

Обратите внимание, это означает, что вы должны иметь возможность "перехватить" значение, прежде чем оно действительно будет удалено.

Примечание: я подозреваю, что так делает мой карманный калькулятор, потому что в нем есть функции для сброса сумм (n) и сумм (n ^ 2), и я могу «удалить» значение, которое я никогда не добавлял, как я могу скажем, добавить 2 и 4 к набору, а затем удалить 3, и это говорит, что все в порядке. Поэтому я не думаю, что он хранит список: он должен просто вести подсчет и суммы.

1 голос
/ 12 июля 2011

Самое простое, что нужно сделать - это инвертировать формулы Кнута (из статьи Википедии о расчете дисперсии:

M k-1 = M k - (x k - M k ) / (k-1)

S k-1 = S k - (x k - M k-1 ) (x k - M k )

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

Стабильный онлайн-метод, который использует O (log N) операций для выборки (где N - количество элементов в вашей очереди), - это использование двоичного дерева слияния статистических элементов с использованием формулы для "параллельного слияния" из статьи в Википедии, следующим образом (в форме C ++): 

struct Statistic {
  int k;
  Element M;
  Element S;

  Statistic(Element x)
    : k(1)
    , M(x)
    , S(0)
  {}
  Statistic(Statistic a, Statistic b)
    : k(a.k + b.k)
    , M(a.M*a.k + b.M*b.k)/float(k)
    , S(a.S + b.S + (a.M-b.M)*(a.M-b.M)*(a.k*b.k/float(k)))
  {}
};

Для стабильного онлайн-алгоритма O (log N) сохраняйте сбалансированное двоичное дерево вышеприведенной статистики, причем листья представляют отдельные элементы; корень даст желаемую онлайн статистику. Когда вы обновляете элементы (в стиле вращающегося буфера), для распространения каждого обновления от листа к корню потребуются O (log N) операций.

...