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

StackOverflow https://stackoverflow.com/questions/2837311

Вопрос

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

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

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];

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

Примечание:

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

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

Также в этой теме мало предметов, т. Е.

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

Это было полезно?

Решение 5

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

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

Другие советы

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

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

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

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

Видеть https://github.com/tdunning/t-digest.

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

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

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

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

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

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.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top