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

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

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

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

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 () - знаковая функция, которая возвращает одно из значений {-1, 0, 1}. (Используйте константу eta, если данные нестационарны и вы хотите отслеживать изменения во времени; в противном случае для стационарных источников вы можете использовать что-то вроде eta = 1 / n для среднего оценщика, где n - количество наблюдаемых на данный момент выборок ... к сожалению, это не работает для медианного оценщика.)

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

Кроме того, я модифицировал инкрементную медианную оценку для оценки произвольных квантилей. Как правило, функция квантиля сообщает вам значение, которое делит данные на две части: p и 1-стр. Следующее оценивает это значение постепенно:

quantile += eta * (sgn(sample - quantile) + 2.0 * p - 1.0)

Значение p должно быть в пределах [0,1]. Это существенно сдвигает симметричный вывод функции sgn () {-1,0,1} в сторону одной стороны, разделяя выборки данных на две ячейки разного размера (доли p и 1-p от данные меньше / больше квантильной оценки соответственно). Обратите внимание, что для p = 0,5 это сводится к средней оценке.

Я бы хотел увидеть оценщик в инкрементальном режиме подобной формы ...

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

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

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).

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

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

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

Текущее среднее для той же проблемы вычислить гораздо проще:

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)

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

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

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

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

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

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

3. равно K = MedianIndex, тогда верните MedianValue

4. такое K> MedianIndex? затем HighValue = MedianValue Else LowValue = MedianValue

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

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

LowIndex = 1 HighIndex = N

Повторяйте следующие 5 шагов, пока (LowIndex ‹HighIndex)

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

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

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

4. есть (K = MedianIndex)? return MedianValue

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

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

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

Обычно, если ввод находится в определенном диапазоне, скажем, от 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) * 1000000 .

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

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

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

Function QuantileIterative(Var x : Array of Double; n : Integer; p, mean, sigma : Double) : Double;
Var eta, quantile,q1, dq : Double;
    i : Integer;
Begin
  quantile:= mean + 1.25*sigma*(p-0.5);
  q1:=quantile;
  eta:=0.2*sigma/xy(1+n,0.75); // should not be too large! sets accuracy
  For i:=1 to n Do 
     quantile := quantile + eta * (signum_smooth(x[i] - quantile,eta) + 2*p - 1);
  dq:=abs(q1-quantile);
  If dq>eta
     then Begin
          If dq<3*eta then eta:=eta/4;
          For i:=1 to n Do 
             quantile := quantile + eta * (signum_smooth(x[i] - quantile,eta) + 2*p - 1);
     end;
  QuantileIterative:=quantile
end;

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

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

    # find min on the fly
    if minDataPoint > dataPoint:
        minDataPoint = dataPoint  

    # find max on the fly
    if maxDataPoint < dataPoint:
        maxDataPoint = dataPoint
    
    # estimate median base on the current data
    estimate_mid = (maxDataPoint + minDataPoint) / 2
    
    #if **new** dataPoint is closer to the mid? stor it
    if abs(midDataPoint - estimate_mid) > abs(dataPoint - estimate_mid):
        midDataPoint = dataPoint    

В духе @lakshmanaraj