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

Question

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

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

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

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

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

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

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

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

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

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

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

Answer 1

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

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

медиана

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

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

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

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

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

Дальнейшие комментарии

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

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

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

Answer 2

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

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

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

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

Я хотел бы видеть оценщик возрастающего режима подобной формы...

ОБНОВИТЬ

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

Медиана

Два недавних алгоритма процентильного приближения и их реализации на Python можно найти здесь:

t-дайджесты

• https://arxiv.org/abs/1902.04023
• https://github.com/CamDavidsonPilon/tdigest

DDSketch

• https://arxiv.org/abs/1908.10693
• https://github.com/DataDog/sketches-py

Оба алгоритма хранят данные. Поскольку T-Digest использует меньшие интервалы рядом с хвостами, точность лучше на крайних точках (и слабее ближе к медиане). DDSketch дополнительно обеспечивает гарантии относительных ошибок.

Answer 9

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

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

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

Answer 10

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

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

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

Answer 11

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

https://prod-ng.sandia.gov/techlib-noauth/access-control.cgi/2008/086212.pdf

Answer 12

ОК, чувак, попробуйте это:

для с ++:

double skew(double* v, unsigned long n){
    double sigma = pow(svar(v, n), 0.5);
    double mu = avg(v, n);

    double* t;
    t = new double[n];

    for(unsigned long i = 0; i < n; ++i){
        t[i] = pow((v[i] - mu)/sigma, 3);
    }

    double ret = avg(t, n);

    delete [] t;
    return ret;
}

double kurt(double* v, double n){
    double sigma = pow(svar(v, n), 0.5);
    double mu = avg(v, n);

    double* t;
    t = new double[n];

    for(unsigned long i = 0; i < n; ++i){
        t[i] = pow( ((v[i] - mu[i]) / sigma) , 4) - 3;
    }

    double ret = avg(t, n);

    delete [] t;
    return ret;
}

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

Кроме того, взгляните на приближение Пирсона. для такого большого набора данных это было бы очень похоже. 3 (среднее значение - медиана) / стандартное отклонение, у вас медиана как максимум - мин /2

для поплавков режим не имеет смысла. как правило, их можно сунуть в контейнеры значительного размера (например, 1/100 * (макс. - мин.)).

Answer 13

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)

Answer 14

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

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