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

Question

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

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

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

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

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

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

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

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

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

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

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

Answer 1

Асимметрия и эксцесс

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

медиана

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

Медиана и мода с подсчетом частот

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

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

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

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

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

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

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

Answer 2

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

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

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

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

Мне бы очень хотелось увидеть оценщик инкрементного режима аналогичной формы...

ОБНОВЛЯТЬ

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

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

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

Answer 3

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

Answer 4

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

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

Answer 5

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

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

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

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

Answer 6

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

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

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

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

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

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

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

Answer 7

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

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

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

Answer 8

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

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

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

Answer 9

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

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

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

Answer 10

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

для С++:

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 11

Эту проблему решили Пебай и др.:

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

Answer 12

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

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

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)