“Онлайн” (итератор) алгоритмы для оценки статистической медианы, режима, скошенности, эксцесса?

медиана и режим не могут быть рассчитаны в интерактивном режиме с использованием только доступного постоянного пространства. Однако, поскольку медиана и мода в любом случае являются более «описательными», чем «количественными», вы можете оценить их, например, путем выборки набора данных.

Если данные нормально распределены в долгосрочной перспективе, вы можете просто использовать свое среднее значение для оценить медианное значение.

Вы также можете оценить медианное значение, используя следующую технику: установите среднюю оценку M [i] для каждого, скажем, 1 000 000 записей в потоке данных так, чтобы M [0] было медианным значением первого миллиона записей, M [1] - медиана второго миллиона записей и т. д. Затем используйте медиану M [0] ... M [k] как среднюю оценку. Это, конечно, экономит место, и вы можете контролировать, сколько вы хотите использовать пространство, «настраивая» параметр 1 000 000.

The Wikipedia article quoted in the question contains the formulas for calcualting skewness and kurtosis on-line.

For mode - I believe - there is no way doing this on-line. Why? Assume that all values of your input are different besides the last one that duplicates a previous one. In this case you have to remember all values allready seen in the input to detect that the last value duplicates a value seen befor and makes it the most frequent one.

For median it is almost the same - up to the last input you don't know what value will become the median if all input values are different because it could be before or after the current median. If you know the length of the input, you can find the median without storing all values in memory, but you will still have to store many of them (I guess around the half) because a bad input sequence could shift the median heavily in the second half possibly making any value from the first half the median.

(Note that I am refering to exact calculation only.)

Райан, я боюсь, что вы неправильно используете среднее значение и дисперсию ... Это появилось несколько недель назад здесь . И одной из сильных сторон онлайн-версии (которая на самом деле называется методом Велфорда) является то, что она особенно точна и стабильна, см. Обсуждение здесь . Одной из сильных сторон является тот факт, что вам не нужно хранить общую сумму или общую сумму квадратов ...

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

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

При этом, если вы не имеете дело с какой-либо патологической ситуацией, лекарство (Rousseuw and Bassett, 1990) вполне может быть достаточно хорошим для ваших целей.

Очень просто, это включает в себя вычисление медианы пакетов медиан.

Если у вас есть миллиарды точек данных, то маловероятно, что вам нужны точные ответы, в отличие от точных ответов. Как правило, если у вас есть миллиарды точек данных, основной процесс, который их генерирует, скорее всего, будет подчиняться некоторому свойству статистической стационарности / эргодичности / смешивания. Также может иметь значение, ожидаете ли вы, что распределения будут достаточно непрерывными или нет.

В этих обстоятельствах существуют алгоритмы для оперативной, низкой памяти, оценки квантилей (медиана - это частный случай квантиля 0,5), а также режимы, если вам не нужно точные ответы. Это активная область статистики.

Пример квантильной оценки: http://www.computer.org/portal/web/csdl/doi/10.1109/WSC.2006.323014 Пример оценки режима

: Bickel DR. Робастные оценки режима и асимметрии непрерывных данных. Вычислительная статистика и анализ данных. 2002; 39: 153–163. doi: 10.1016 / S0167-9473 (01) 00057-3.

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

Последний вопрос заключается в том, действительно ли вам нужны асимметрия и эксцесс сами по себе, или, что более вероятно, какие-то другие параметры, которые могут быть более надежными для характеристики распределения вероятностей (при условии, что у вас есть распределение вероятностей!). Вы ожидаете гауссова?

Есть ли у вас способы очистки / предварительной обработки данных, чтобы сделать их в основном гауссовскими? (например, суммы финансовых транзакций после логарифмирования часто становятся несколько гауссовыми). Вы ожидаете конечных стандартных отклонений? Вы ожидаете толстых хвостов? Какие количества, которые вам нужны, - в хвосте или в основной массе?

Я использую эти инкрементные/рекурсивные средние и медианные оценки, которые оба используют постоянное запоминающее устройство:

mean += eta * (sample - mean)
median += eta * sgn(sample - median)

где eta - небольшой параметр скорости обучения (например, 0,001), а sgn() - знаковая функция, которая возвращает одну из {-1, 0, 1}. (Используйте константу eta, если данные не стационарны и вы хотите отслеживать изменения во времени; в противном случае для стационарных источников можно использовать нечто вроде eta=1/n для среднего вычисления, где n - это количество просмотренных до сих пор отсчетов.... К сожалению, для медианной оценки это, по-видимому, не работает)

Этот тип инкрементальной средней оценки, похоже, используется повсеместно, например, в неконтролируемых нейросетевых правилах обучения, но медианная версия, несмотря на свои преимущества (устойчивость к выбросам), встречается гораздо реже. Похоже, что медианная версия может быть использована как замена средней оценки во многих приложениях.

Хотелось бы увидеть оценщик приращения в режиме...

UPDATE

Я только что модифицировал инкрементальную оценку медианы для оценки произвольных квантилей. В общем, функция квантиля (http://en.wikipedia.org/wiki/Quantile_function) сообщает значение, которое делит данные на две фракции: p и 1-p. Следующие оценки этого значения выполняются инкрементально:

quantile += eta * (sgn(sample - quantile) + 2.0 * p - 1.0)

Значение p должно быть в пределах [0,1]. Это существенно сдвигает симметричный выход функции sgn() {-1,0,1} в сторону одной стороны, разделяя образцы данных на два неравноразмерных бина (дроби p и 1-p данных меньше/гр больше, чем оценка квантиля, соответственно). Обратите внимание, что для p=0,5 это уменьшается до медианной оценки.