инкрементный способ подсчета квантилей для большого набора данных

Я поддерживаю идею использования ведер. Не ограничивайте себя 100 ведрами - с таким же успехом можно использовать 1 миллион. Сложная часть - выбрать диапазон ковшей, чтобы все не попало в одно ведро. Вероятно, лучший способ оценить диапазоны ваших сегментов - это взять разумную случайную выборку ваших данных, вычислить 10% и 90% квантилей с помощью простого алгоритма сортировки, а затем сгенерировать сегменты одинакового размера для заполнения этого диапазона. Это не идеально, но если ваши данные не из сверхъестественного дистрибутива, все должно работать.

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

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

Основная идея состоит в том, что меньшие ячейки используются в крайних случаях таким образом, чтобы ограничить размер структуры данных и гарантировать более высокую точность для малых или больших q. Алгоритм доступен на нескольких языках и во многих пакетах. Версия MergingDigest не требует динамического выделения ... после создания экземпляра MergingDigest дальнейшее выделение кучи не требуется.

См. https://github.com/tdunning/t-digest.

1. Извлекайте только те данные, которые вам действительно нужны, то есть какие бы значения ни использовались в качестве ключа для сортировки, а не все, что с ними связано.
2. Вероятно, вы можете использовать алгоритм Select Тони Хоара, чтобы найти свой квантиль быстрее, чем сортировка всех данных.

Если ваши данные имеют гауссовское распределение, вы можете оценить квантили по стандартному отклонению. Я предполагаю, что ваши данные не распределены по Гауссу, или вы все равно использовали бы SD.

Если вы можете дважды передать свои данные, я бы сделал следующее:

• Сначала вычислите максимальное, минимальное, стандартное отклонение и среднее значение.
• Во втором проходе разделите диапазон [min, max] на некоторое количество сегментов (например, 100); сделайте то же самое для (среднее - 2 * SD, среднее + 2 * SD) (с дополнительными сегментами для выбросов). Затем снова просмотрите данные, бросая числа в эти корзины.
• Считайте сегменты, пока не получите 25% и 75% данных. Если вы хотите получить экстра-фантазию, вы можете интерполировать значения сегмента. (То есть, если вам нужно 10% емкости для достижения 25-го квантиля, предположите, что значение составляет 10% пути от нижней границы до верхней границы.)

Это должно дать вам довольно хороший алгоритм линейного времени, который нормально работает для большинства наборов не совсем искаженных данных.

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

Идея заключается в следующем: квантиль 0,75 на самом деле является медианой всех значений, лежащих выше глобальной медианы. И, соответственно, квантиль 0,25 - это медиана всех значений ниже глобальной медианы.

Итак, если мы можем аппроксимировать медиану, мы можем точно так же аппроксимировать и квантили.

double median = 0;
double q1 = 0;
double q3 = 0;
double eta = 0.005;

foreach( var value in listOfValues) // or stream, or any other large set of data...
{
    median += eta * Math.Sign(p.Int - median);
}
// Second pass. We know the median, so we can count the quantiles.
foreach(var value in listOfValues)
{ 
    if(p.Int < median)
        q1 += eta*Math.Sign(p.Int - q1);
    else
        q3 += eta*Math.Sign(p.Int - q3);
}

Примечания:

• Если ваши данные распределяются странно, вам понадобится больший eta, чтобы соответствовать странным данным. Но точность будет хуже.
• Если распределение странное, но вы знаете общий размер вашей коллекции (то есть N), вы можете настроить параметр eta таким образом: вначале установите eta, чтобы он был почти равен некоторому большому значению (например, 0,2). По мере прохождения цикла уменьшайте значение eta, чтобы, когда вы дойдете почти до конца коллекции, eta будет почти равным 0 (например, в цикле вычислите это так: eta = 0.2 - 0.2*(i/N);

q-digest - это приблизительный онлайн-алгоритм, который позволяет вычислить квантиль: http://www.cs.virginia.edu/~son/cs851/papers/ucsb.sensys04.pdf

Вот реализация:

https://github.com/airlift/airlift/blob/master/stats/src/main/java/io/airlift/stats/QuantileDigest.java.