Алгоритмы для вычисления текущей медианы?

18

При меньших размерах окна n log nсортировка может работать. Есть ли лучшие алгоритмы для достижения этой цели?

Мик
источник
1
Я думаю, что это первый кандидат, который будет перемещен в Stack Overflow.
Возможно, но для SO потребуется гораздо больше объяснений.
walkytalky
2
Большинство программистов знают «медиану». (sort (array)) [length / 2] достаточно большой совет для тех, кто забыл. Кроме того, в самом основном для каждой новой точки вам нужно только выполнить деление пополам на одну половину массива ...
Пол
1
Повторно открыл после обсуждения на meta.stats.stackexchange.com/questions/276/…
Роб Хиндман
2
Слишком тривиально, чтобы быть чем-то большим, чем комментарий, но код для медианы 3s - это просто a + b + c - max (a, b, c) - min (a, b. C). Это прекрасно работает, даже если есть связи. Это было очевидно для меня, как только я подумала об этом из чужого кода (почему он (в данном случае) добавляет и вычитает, чтобы получить медиану ???), и некоторые другие могут иметь такую ​​же реакцию. max () и min () часто реализуются как сверхбыстрые функции. К сожалению, такого трюка нет вообще.
Ник Кокс

Ответы:

11

Нехорошо сортировать массив для вычисления медианы. Медианы (и другие квантили) обычно вычисляются с использованием алгоритма быстрого выбора со сложностью .О(N)

Вы также можете посмотреть мой ответ на недавний связанный с этим вопрос здесь .

user603
источник
7

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

Лукаш Лью
источник
1
Ссылка не работает, и без заголовка или информации об авторе трудно найти то, на что она ссылается.
Кристофер Джонсон
6

Если вы готовы терпеть приближение, есть другие методы. Например, одно приближение - это значение, ранг которого находится на некотором (указанном пользователем) расстоянии от истинной медианы. Например, медиана имеет (нормализованный) ранг 0,5, и если вы укажете погрешность 10%, вам потребуется ответ с рангом от 0,45 до 0,55.

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

Таким образом, главный вопрос заключается в том, как сохранить текущую выборку данных определенного размера, и для этого существует множество подходов, включая метод, известный как отбор проб из пласта. Например, этот документ: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.7136

Суреш Венкатасубраманян
источник
4

Если вы сохраняете окно данных длины k в виде отсортированного двусвязного списка, то с помощью бинарного поиска (для вставки каждого нового элемента по мере его перемещения в окно) и кругового массива указателей (чтобы сразу найти элементы, которые необходимо удалить), каждый сдвиг окна требует O (log (k)) усилий для вставки одного элемента, только O (1) усилий для удаления элемента, сдвинутого из окна, и только O (1) усилий для поиска медиана (потому что каждый раз, когда один элемент вставляется или удаляется в список, вы можете обновить указатель на медиану за O (1) раз). Таким образом, общее усилие по обработке массива длины N составляет O ((nk) log (k)) <= O (n log (k)). Это лучше, чем любой другой метод, предложенный до сих пор, и это не приближение, это точно.

Whuber
источник
1
Не могли бы вы рассказать о том, как вы предлагаете выполнить бинарный поиск в отсортированном двусвязном списке?
NPE
одна «ссылка» позволяет просматривать список в отсортированном порядке; другой позволяет перемещаться в порядке появления элементов. Непонятно, как бы вы делали это с указателями, хотя, как вопросы @aix.
Шаббычеф
2
@aix Я думаю, что твоя подсказка верна; Мне нужен индексируемый список пропусков, а не просто отсортированный двусвязный список. Идея состоит в том, чтобы иметь структуру данных, которая позволяет вставлять один элемент, удалять один элемент и находить медиану за ожидаемое время O (log (n)) (или лучше).
whuber
3

Как вы упоминали, сортировка будет O(n·log n)для окна длины n. Выполнение этого перемещения добавляет еще одну l=vectorlengthобщую стоимость O(l·n·log n).

Самый простой способ добиться этого - сохранить упорядоченный список последних n элементов в памяти при переходе от одного окна к следующему. Поскольку удаление / вставка одного элемента из / в упорядоченный список являются обоими, O(n)это приведет к затратам на O(l·n).

псевдокод:

l = length(input)
aidvector = sort(input(1:n))
output(i) = aid(n/2)
for i = n+1:l
    remove input(i-n) from aidvector
    sort aid(n) into aidvector
    output(i) = aid(n/2)
ymihere
источник
2

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

Средство с базой b вычисляет медианы групп наблюдений b, а затем медианы этих медиан до тех пор, пока не останется только одна оценка. Этот метод просто нуждается в k массивах размера b (где n = b ^ k) ...

shoelzer
источник
0

Я использовал эту библиотеку RunningStats C ++ во встроенном приложении. Это самая простая библиотека статистики, которую я когда-либо нашел.

По ссылке:

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

Крис К
источник
Эта страница что-нибудь говорит о медиане?
Musiphil