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

Question

Существует ли алгоритм для оценки медианы, режима, асимметрии и / или эксцесса набора значений, но который НЕ требует сохранения всех значений в памяти сразу?

Я бы хотел вычислить базовую статистику:

• означает: среднее арифметическое
• дисперсия: среднее квадратов отклонений от среднего
• стандартное отклонение: квадратный корень из дисперсии
• медиана: значение, которое отделяет большую половину чисел от меньшей половины
• : наиболее часто встречающееся значение в наборе
• асимметрия: tl; др
• эксцесс: tl; др

Основные формулы для вычисления любого из них - арифметика начальной школы, и я знаю их. Также есть много библиотек статистики, которые их реализуют.

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

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

Я уже понял, как правильно обрабатывать среднее и дисперсию, перебирая каждое значение в наборе в любом порядке. (На самом деле, в моем случае, я беру их в том порядке, в котором они были сгенерированы.) Вот алгоритм, который я использую, любезно http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#On-line_algorithm:

• Инициализировать три переменные: count, sum и sum_of_squares
• Для каждого значения:
  • Количество приращений.
  • Добавьте значение к сумме.
  • Добавьте квадрат значения к sum_of_squares.
• Разделите сумму на число, сохранив ее как среднее значение.
• Разделите sum_of_squares на количество, сохраняя в качестве переменной mean_of_squares.
• Среднее значение квадрата, хранится как square_of_mean.
• Вычесть square_of_mean из mean_of_squares, сохраняя как дисперсию.
• Среднее значение и дисперсия.

У этого «онлайнового» алгоритма есть недостатки (например, проблемы с точностью, так как sum_of_squares быстро растет больше, чем целочисленный диапазон или точность с плавающей точкой), но в основном он дает мне то, что мне нужно, без необходимости хранить каждое значение в каждом наборе. 1054 *

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

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

Answer 1

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

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

, где eta - это параметр небольшой скорости обучения (например, 0,001), а sgn () - это функция signum, которая возвращает один из {-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 это сводится к медианной оценке.

Answer 2

асимметрия и куртоз

Он-лайн алгоритмы для асимметрии и куртоза (вдоль линий дисперсии) см. На той же вики-странице здесь параллельные алгоритмы для статистики более высокого момента.

Медиана

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

Медиана и режим с частотой отсчетов

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

нормально распределенные случайные величины

Если оно нормально распределено, я бы использовал выборку населения среднее , дисперсия , асимметрия и эксцесс в качестве максимальной вероятности Оценки для небольшого подмножества. (Он-лайн) алгоритмы для расчета тех, вы уже сейчас. Например. прочитайте пару сотен тысяч или миллионов точек данных, пока ваша ошибка оценки не станет достаточно маленькой. Просто убедитесь, что вы выбираете случайным образом из своего набора (например, что вы не вносите смещение, выбирая первые 100 000 значений). Тот же самый подход может также использоваться для оценки режима и медианы для нормального случая (для обоих выборка означает среднее значение).

Дополнительные комментарии

Все вышеперечисленные алгоритмы могут выполняться параллельно (включая множество алгоритмов сортировки и выбора, например, QuickSort и QuickSelect), если это помогает.

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

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

Answer 3

Я реализовал Алгоритм P-квадрата для динамического вычисления квантилей и гистограмм без сохранения наблюдений в аккуратном Python-модуле, который я написал под названием LiveStats . Это должно решить вашу проблему довольно эффективно. Библиотека поддерживает все упомянутые вами статистические данные, кроме режима. Я пока не нашел удовлетворительного решения для оценки режима.

Answer 4

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

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

Answer 5

Статья в Википедии, цитируемая в этом вопросе, содержит формулы для расчета асимметрии и эксцессов в режиме онлайн.

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

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

(Обратите внимание, что я ссылаюсь только на точный расчет.)

Answer 6

Все говорят, что вы не можете включить режим в режиме онлайн, но это просто неправда. Вот статья , в которой описан алгоритм решения именно этой проблемы, изобретенный в 1982 году Майклом Фишером и Стивеном Л. Зальцбергом из Йельского университета. Из статьи:

Алгоритм обнаружения большинства использует один из своих регистров для временного хранение одного элемента из потока; этот пункт является текущим кандидат на элемент большинства. Второй регистр является счетчиком инициализируется до 0. Для каждого элемента потока мы задаем алгоритм выполнить следующую процедуру. Если счетчик показывает 0, установите текущий элемент потока в качестве нового кандидата в большинство (смещение любого другой элемент, который уже может быть в реестре). Тогда, если текущий элемент соответствует мажоритарному кандидату, увеличивает счетчик; в противном случае уменьшите счетчик. На этом этапе цикла, если у части потока, замеченного до сих пор, есть элемент контрольного числа, этот элемент в регистре кандидатов, и счетчик содержит значение больше 0. Что если нет элемента большинства? Без повторного прохождения данных - что невозможно в потоковой среде - алгоритм не всегда может дать однозначный ответ в этом обстоятельство. Он просто обещает правильно определить большинство элемент, если таковой имеется.

Он также может быть расширен, чтобы найти верхнюю N с большим объемом памяти, но это должно решить эту проблему для режима.

Answer 7

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

В этих обстоятельствах существуют алгоритмы для оперативной, малой памяти, оценки квантилей (медиана - это особый случай 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.

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

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

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

Answer 8

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

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

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

Answer 9

Эта проблема была решена Pebay et al:

https://prod -ng.sandia.gov / techlib-NOAUTH / доступа control.cgi / 2008 / 086212.pdf

Answer 10

for j in range (1,M):
    y=np.zeros(M) # build the vector y
    y[0]=y0

    #generate the white noise
    eps=npr.randn(M-1)*np.sqrt(var)

    #increment the y vector
    for k in range(1,T):
        y[k]=corr*y[k-1]+eps[k-1]

    yy[j]=y

list.append(y)