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

Question

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

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

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

List allData = new List();
// 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];

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

Примечание:

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

Этот вопрос подобен “Онлайн” (итератор) алгоритмы для оценки статистической медианы, режима, скошенности, эксцесса, но я должен считать квантили.

Также существует немного статей в этой теме, т.е.:

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

9

algorithm statistics numerical-methods quantile

задан Community 23 May 2017 в 11:55

4 ответа

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

0

ответ дан 5 December 2019 в 02:07

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

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

1

ответ дан 5 December 2019 в 02:07

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

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

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

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

0

ответ дан 5 December 2019 в 02:07

Другие вопросы по тегам:

algorithm statistics numerical-methods quantile

Похожие вопросы:

score 0 · Accepted Answer

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

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