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

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

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

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

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

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

Answer 2

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

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

Answer 3

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

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

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