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

Question

Мне нужно посчитать квантили для большого набора данных.

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

List<double> allData = new List<double>();
// This is only an example; the portions of data are not really rows of some matrix
foreach(var row in matrix) 
{
    allData.AddRange(row);
}

allData.Sort();
double p = 0.75 * allData.Count;
int idQ3 = (int)Math.Ceiling(p) - 1;
double Q3 = allData[idQ3];

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

Примечание:

• Эти наборы данных очень большие (около 5000 элементов в каждом ряду)
• Q3 можно оценить, оно не должно быть точным значением.
• Я называю части данных «строками», но они могут иметь разные длины! Обычно оно варьируется не так много (+/- несколько сотен образцов), но оно варьируется!

Этот вопрос похож на «Он-лайн» (итератор) алгоритмы для оценки статистической медианы, моды, асимметрии, эксцесса , но мне нужно посчитать квантили.

ТАКЖЕ есть несколько статей в этой теме, т. Е.

• Эффективный алгоритм для приближенной задачи выбора медианы
• Инкрементная квантильная оценка для массивного отслеживания

Прежде чем пытаться реализовать эти подходы, я подумал, есть ли еще какие-нибудь более быстрые способы подсчета квантилей 0,25 / 0,75?

Answer 1

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

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

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

Answer 2

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

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

Answer 3

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

Answer 4

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

Идея заключается в следующем: квантиль 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);

Answer 5

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

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

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

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

Answer 6

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