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

Question

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

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

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. Я предполагаю, что это означает, что я могу использовать некоторую форму гистограммы для каждого значения.

Спасибо

Ник

Answer 1

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

Answer 2

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

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

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

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

Michael

Answer 3

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

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

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

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

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

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

Answer 4

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

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

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

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

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

Answer 5

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

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

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

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

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

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

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

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

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

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

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

Answer 6

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

Работающее среднее для той же задачи вычислить гораздо проще:

M _n = M _n-1 + ((V _n - M _n-1 ) / n)

Где M _n - среднее значение из n значений, M _n-1 - предыдущее среднее значение, а V _n - новое значение.

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

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

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

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

Answer 7

Не думаю, что можно обойтись без списка в памяти. Вы можете, очевидно, приблизиться с

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

Answer 8

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

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

Повторяйте следующие 4 шага, пока LowValue

1. Получить MedianValue приблизительно = (HighValue + LowValue) / 2

2. Получить NumberOfItemsWhichAreLessThanorEqualToMedianValue = K

3. - это K = MedianIndex, затем вернуть MedianValue

4. это K> MedianIndex? затем HighValue = MedianValue, иначе LowValue = MedianValue

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

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

* * LowIndex тысячи двадцать восемь = 1 HighIndex = N

Повторять следующие 5 шагов до (LowIndex

1. Получить приблизительное значение DistrbutionPerUnit = (HighValue-LowValue) / (HighIndex-LowIndex)

2. Получить Приблизительное MedianValue = LowValue + (MedianIndex-LowIndex) * DistributionPerUnit

3. Получить NumberOfItemsWhichAreLessThanorEqualToMedianValue = K

4. есть (K = MedianIndex)? вернуть MedianValue

5. это (K> MedianIndex)? тогда HighIndex = K и HighValue = MedianValue, иначе LowIndex = K и LowValue = MedianValue

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

Мы также можем подумать о подгонке HighValue, LowValue и MedianValue с HighIndex, LowIndex и MedianIndex к параболе и можем получить бинарный поиск ThirdOrder, который будет быстрее 2-го порядка без использования памяти и т. Д.

Answer 9

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

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

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

Answer 10

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

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

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

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