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

Ответ 1

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

Ответ 2

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

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

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

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

Майкл

Ответ 3

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

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

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

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

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

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

Ответ 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) дополнительного пространства и выполняется за линейное время.

Ответ 5

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

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

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

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

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

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

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

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

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

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

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

Ответ 6

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

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

Ответ 7

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

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

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

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

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

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

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

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

Ответ 8

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

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

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

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

• Получить NumberOfItemsWhichAreLessThanorEqualToMedianValue = K

• - это K = MedianIndex, затем возвращает MedianValue

• есть K > MedianIndex? затем HighValue = MedianValue Else LowValue = MedianValue

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

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

LowIndex = 1 HighIndex = N

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

• Получите примерное решение: PerUnit = (HighValue-LowValue)/(HighIndex-LowIndex)

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

• Получить NumberOfItemsWhichAreLessThanorEqualToMedianValue = K

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

• есть (K > MedianIndex)? затем HighIndex = K и HighValue = MedianValue Else LowIndex = K и LowValue = MedianValue

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

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

Ответ 9

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

Ответ 10

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

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;

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