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

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

  •  10-07-2019
  •  | 
  •  

Вопрос

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

В идеале я хотел бы написать свой код примерно следующим образом

var medianCalculator = new MedianCalculator();
foreach (var value in SourceData)
{
  medianCalculator.Add(value);
}
Console.WriteLine("The median is: {0}", medianCalculator.Median);

Все, что мне нужно, это фактический код MedianCalculator!

Обновить: Некоторые люди спрашивали, обладают ли значения, для которых я пытаюсь вычислить медиану, известными свойствами.Ответ - да.Одно значение имеет приращение в 0,5 примерно от -25 до -0,5.Другой также с шагом 0,5 от -120 до -60.Я предполагаю, что это означает, что я могу использовать некоторую форму гистограммы для каждого значения.

Спасибо

Ник

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

Решение

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

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

Существует статистика "ремеди".Это работает путем предварительной настройки k массивов, каждый длиной b.Значения данных вводятся в первый массив, и, когда он заполняется, вычисляется медиана и сохраняется в первом pos следующего массива, после чего первый массив используется повторно.Когда второй массив заполнен, медиана его значений сохраняется в первом поз третьего массива и т.д.и т.д.Вы поняли идею :)

Это просто и довольно надежно.Ссылка находится здесь...

http://web.ipac.caltech.edu/staff/fmasci/home/astro_refs/Remedian.pdf

Надеюсь, это поможет

Майкл

Я использую эти инкрементные / рекурсивные средние и медианные оценки, которые оба используют постоянное хранилище:

mean += eta * (sample - mean)
median += eta * sgn(sample - median)

где eta - небольшой параметр скорости обучения (например,0.001), а sgn() - это функция signum, которая возвращает одно из {-1, 0, 1}.

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

Мне бы хотелось увидеть оценщик инкрементного режима аналогичной формы...

(Примечание:Я также опубликовал это в аналогичной теме здесь: "On-line" (итераторные) алгоритмы для оценки статистической медианы, моды, асимметрии, эксцесса?)

Вот безумный подход, который вы могли бы попробовать.Это классическая проблема в потоковых алгоритмах.Правила таковы

  1. Скажем, у вас ограниченная память O(log n) где n это количество элементов, которые вы хотите
  2. Вы можете взглянуть на каждый предмет один раз и тут же принять решение, что с ним делать, если вы будете хранить его, это будет стоить памяти, если вы выбросите его, он исчезнет навсегда.

Идея нахождения медианы проста.Образец O(1 / a^2 * log(1 / p)) * log(n) элементы из списка случайным образом, вы можете сделать это с помощью отбора проб из резервуара (см. предыдущий вопрос).Теперь просто верните медиану из выбранных вами элементов, используя классический метод.

Гарантия заключается в том, что индекс возвращаемого товара будет (1 +/- a) / 2 с вероятностью , по крайней мере 1-p.Таким образом, существует вероятность p сбоя, вы можете выбрать ее, выбрав больше элементов.И это не вернет медиану или не гарантирует, что значение возвращаемого элемента где-либо близко к медиане, просто при сортировке списка возвращаемый элемент будет близок к половине списка.

Этот алгоритм использует O(log n) дополнительное пространство и выполняется в линейном времени.

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

Основная идея создания гистограммы является наиболее многообещающей.Это позволяет вам накапливать информацию о распространении и отвечать на запросы (например, медианные) на ее основе.Медиана будет приблизительной, поскольку вы, очевидно, сохраняете не все значения.Место для хранения фиксировано, поэтому оно будет работать с любой имеющейся у вас последовательностью длин.

Но вы не можете просто построить гистограмму, скажем, из первых 100 значений, и постоянно использовать эту гистограмму..изменяющиеся данные могут сделать эту гистограмму недействительной.Итак, вам нужна динамическая гистограмма, которая может изменять свой диапазон и ячейки "на лету".

Создайте структуру, в которой есть N ячеек.Вы будете сохранять значение X для каждого перехода в слот (всего N + 1 значений), а также заполнение ячейки.

Поток ваших данных.Запишите первые N+ 1 значения.Если поток заканчивается до этого, отлично, у вас загружены все значения, и вы можете найти точную медиану и вернуть ее.В противном случае используйте значения для определения вашей первой гистограммы.Просто отсортируйте значения и используйте их в качестве определений ячеек, причем каждая ячейка имеет совокупность, равную 1.Это нормально иметь дубликаты (ячейки шириной 0).

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

Но этого недостаточно..вам все еще нужно АДАПТИРОВАТЬ гистограмму к данным по мере их поступления в потоковом режиме.Когда ячейка переполняется, вы теряете информацию о дополнительном распределении этой ячейки.Вы можете исправить это, адаптировав на основе некоторой эвристики...Самый простой и надежный вариант - если ячейка достигает некоторого определенного порогового значения заполнения (что-то вроде 10 * v / N, где v = # значений, видимых на данный момент в потоке, а N - количество ячеек), вы РАЗБИВАЕТЕ эту переполненную ячейку.Добавьте новое значение в среднюю точку ячейки, присвоив каждой стороне половину заполнения исходной ячейки.Но теперь у вас слишком много ячеек, поэтому вам нужно УДАЛИТЬ одну из них.Хорошая эвристика для этого - найти ячейку с наименьшим произведением численности населения на ширину.Удалите его и объедините со своим левым или правым соседом (в зависимости от того, какой из соседей сам по себе имеет наименьшее произведение ширины и численности населения.).Сделано!Обратите внимание, что при слиянии или разделении ячеек теряется информация, но это неизбежно..у вас есть только фиксированное хранилище.

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

Алгоритм также позволяет вам запрашивать любой процентиль, а не только медиану, поскольку у вас есть полная оценка распределения.

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

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

Я не думаю, что это возможно сделать, не имея списка в памяти.Очевидно, вы можете приблизиться с помощью

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

Предложение Дэвида кажется наиболее разумным подходом для аппроксимации медианы.

Бегущий подлый для той же задачи это гораздо проще вычислить:

Mn = Мn-1 + ((Вn - Мn-1) / n)

Где Mn является средним из n значений, Mn-1 является предыдущим средним значением, а Vn это новое значение.

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

В коде это выглядело бы примерно так:

new_mean = prev_mean + ((value - prev_mean) / count)

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

Найдите минимальное и максимальное значение списка, содержащего N элементов, с помощью линейного поиска и назовите их как highValue и lowValue Пусть MedianIndex = (N + 1) /2

бинарный поиск 1- го Порядка:

Повторяйте следующие 4 шага до получения низкого значения < Высокая ценность.

  1. Получаем приблизительно среднее значение = ( Высокое значение + низкое значение ) / 2

  2. Получаем число элементов , которое меньше или равно среднему значению = K

  3. является K = MedianIndex, затем возвращает MedianValue

  4. является ли K > MedianIndex ?тогда высокое значение = среднее значение , Остальное низкое значение = среднее значение

Это будет быстрее, не потребляя памяти

бинарный поиск 2 - го Порядка:

Низкий индекс = 1 Высокий индекс = N

Повторяйте следующие 5 Шагов до тех пор, пока (lowIndex < Высокий индекс)

  1. Получаем приблизительный distrubutionperunit=(highValue-lowValue)/(highIndex-lowIndex)

  2. Получаем приблизительное среднее значение = низкое значение + (MedianIndex-lowIndex) * DistributionPerUnit

  3. Получаем число элементов , которое меньше или равно среднему значению = K

  4. является (K=MedianIndex) ?возвращает среднее значение

  5. является ли (K > MedianIndex) ?тогда highIndex=K и highValue= среднее значение, иначе lowIndex=K и lowValue= среднее значение

Это будет быстрее, чем 1-й порядок, без потребления памяти

Мы также можем подумать о том, чтобы сопоставить highValue, lowValue и MedianValue с highIndex, lowIndex и MedianIndex с Параболой, и можем получить бинарный поиск третьего порядка, который будет быстрее, чем 2-й порядок, без потребления памяти и так далее...

Обычно, если входные данные находятся в определенном диапазоне, скажем, от 1 до 1 миллиона, легко создать массив значений:прочтите код для "квантиля" и "ibucket" здесь: http://code.google.com/p/ea-utils/source/browse/trunk/clipper/sam-stats.cpp

Это решение может быть обобщено как приближение путем преобразования входных данных в целое число в пределах некоторого диапазона с использованием функции, которую вы затем переворачиваете на выходе:IE:foo.push((int) ввод /1000000) и квантиль(foo)*1000000.

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

Или вы можете использовать метод медианных тройняшек, описанный в этой статье: http://web.cs.wpi.edu /~хофри/medsel.pdf

Я подхватил идею итеративного вычисления квантиля.Важно иметь хорошее значение для начальной точки и eta, они могут исходить из среднего значения и сигмы.Итак, я запрограммировал это:

Функция квантилеитеративная (Var x :Массив Двойных;n :Целое число;p, среднее значение, сигма :Двойной) :Двойной;
Var eta, квантиль, q1, dq :Двойной;
i :Целое число;
Начинать
квантиль: = среднее значение + 1,25 * сигма* (p-0,5);
q1:=квантиль;
eta:=0,2*сигма/xy(1+ n, 0,75);// не должно быть слишком большим!устанавливает точность
Для i: от=1 до n Делаем квантиль:= квантиль + eta * (signum_smooth(x[i] - квантиль, eta) + 2 * p - 1);
dq:=abs(q1-квантиль);
Если dq>eta
тогда начинайте
Если dq<3* eta, затем eta:=eta/4;
Для i: от=1 до n Делаем квантиль:= квантиль + eta * (signum_smooth(x[i] - квантиль, eta) + 2 * p - 1);
конец;
Квантилеитеративный:=квантиль
конец;

Поскольку медианой для двух элементов было бы среднее значение, я использовал сглаженную функцию signum, а xy() - x ^ y .Есть ли идеи, как сделать это лучше?Конечно, если у нас есть еще какие-то априорные знания, мы можем добавить код, используя min и max массива, перекос и т.д.Возможно, для больших данных вы бы не использовали массив, но для тестирования это проще.

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