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

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

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

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

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

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

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

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

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

Этот алгоритм «on-line» имеет слабые места (например, проблемы с точностью, так как sum_of_squares быстро растет больше, чем целочисленный диапазон или точность float), но в основном дает мне то, что мне нужно, без необходимости хранить каждое значение в каждом наборе.

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

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

    Подкожность и эксцесс

    Для онлайновых алгоритмов асимметрии и эксцесса (в соответствии с дисперсией) см. На той же странице wiki параллельные алгоритмы для статистики с более высоким моментом.

    медиана

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

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

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

    Обычно распределенные случайные переменные

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

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

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

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

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

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

    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 данных меньше / больше, чем оценка квантиля, соответственно). Заметим, что при р = 0,5 это сводится к медианной оценке.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Хорошо, чувак, попробуй:

    для c ++:

     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), вы указываете их на свои функции для doin.

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

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

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

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

     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) 
    Давайте будем гением компьютера.