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

Ответ 1

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

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

Медиана

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

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

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

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

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

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

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

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

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

Ответ 2

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

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

Ответ 3

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

Ответ 4

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

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

Ответ 5

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

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

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

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

Ответ 6

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

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

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

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

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

Ответ 7

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

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

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

Ответ 8

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

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

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

Ответ 9

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

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

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

Ответ 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 (среднее - среднее)/стандартное отклонение у вас медиана как max - min/2

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

Ответ 11

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

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

Ответ 12

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)