Онлайн алгоритм для вычисления среднего и отклонения от подмножества данных
Я взял это как справочник для онлайн-вычисления дисперсии и среднего значения из массива данных переменной длины: http://www.johndcook.com/standard_deviation.html.
Данные представляют собой набор из 16-битных значений без знака, которые могут иметь любое количество выборок (на самом деле, минимум будет около 20 выборок, а максимум около 2e32 выборок.
Поскольку набор данных может быть слишком большим для хранения, я уже реализовал это с помощью вышеупомянутого онлайн-алгоритма в C и проверил, что он правильно вычисляет.
Проблема начинается со следующего требования к приложению: помимо вычисления дисперсии и среднего значения для всего набора, мне также необходимо вычислить отдельный результат (как среднее, так и дисперсию) для совокупности, состоящей из средних 50% значений, т.е. без учета первых 25% и последних 25% образцов. Количество сэмплов заранее неизвестно, поэтому я должен вычислить дополнительный набор онлайн.
Я понимаю, что могу как добавлять, так и вычитать подмножество, вычисляя его отдельно и используя нечто вроде реализации operator+, описанной здесь: http://www.johndcook.com/skewness_kurtosis.html (за исключением особенностей асимметрии и kurtosis, для которых я не имеет смысла). Вычитание может быть получено из этого.
Проблема в том, как мне поддерживать эти подмножества? Или я должен попробовать другую технику?
1 ответ
Если пространство является проблемой, и вы были бы рады принять приближение, я бы начал с алгоритма из следующей статьи:
Вы можете использовать алгоритм для вычисления текущих оценок 25-го и 75-го процентилей наблюдений, замеченных до настоящего времени. Затем вы можете подать эти наблюдения, которые попадают между двумя процентилями, в алгоритм Уэлфорда, описанный в статье Джона Д. Кука, для вычисления скользящего среднего и дисперсии.