Эффективная оценка медианы

[Siper]

Если нужна гарантированная точность 0.5%-2%, то я бы просто завел массив из 200 счетчиков и инкременировал бы нужный (координата считается одной операцией деления, которая у вас тоже есть). При выходе за границы — пересчет массива в 2 раза, в пределе очень редкое событие… 2 таких расширения в худшем случае дадут сужение в 4 раза. Дальше допилил бы алгоритм уже по ситуации.
Или вы точность медианы не по крайним значениям считаете, а по сигме?

[zuborg]

Точность я считаю в процентах от действительного значения медианы (а не как отклонение вычисленного значения от середины выборки)

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

[sch1z0phr3n1a]

Можно воспользоваться такой штукой github.com/HdrHistogram/HdrHistogram
По факту это такой же массив, но шкала нелинейна. Можно хранить значения от 0 до 3,600,000,000 с точностью до трёх знаков.
И считать не только медиану, но и другие квантили:)

Есть порты на другие ЯП!;-)

[Siper]

>> в процентах от действительного значения медианы…
Т.е. я правильно понимаю что если значения сосредоточены скажем в диапазоне от 100.0 до 101.0 то даже совсем криво посчитанная медиана (по крайнему значению) заведомо даст ошибку в не более чем 1% (например, если метод ошибочно дает 101.0 а реальная медиана это 100.01). И наоборот если реальная медиана топчется возле нуля — то даже небольшая абсолютная ошибка в относительном значении может болтаться от минус до плюс бесконечности.
Но я просто не знаю реальной задачи, что там важно а что нет))

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

Вообще, мне кажется точность медианы нужно оценивать по тому на сколько полученное разделение отличается от 50/50. Например требовать не хуже 49/51. Если так, то мне на вскидку кажется это невозможно выдержать не сохраняя и анализирую все прошлые значения ((

[zuborg]

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

[Goodkat]

Нужно не только расширять интервал, но ещё и так же динамически увеличивать точность, добавлять счётчики — например, если диапазон от 0 до 1000, но большинство значений лежит между 0 и 1, то между 0 и 1 вам нужно соответственно больше счётчиков, иначе получите медиану где-то в районе ~5 вместо ~0,5.

[Siper]

Согласен. Но если точность считается от границ — то значение 5 вместо 0.5 приемлемо, т.к. это по прежнему — 0.5%. Выше написал дополнительно по этому поводу.

[Goodkat]

Точность медианы считать от границ диапазона?
Не думаю, что в этом есть какой-то смысл.

[retran]

Просто оставлю тут вот это — ru.wikipedia.org/wiki/%D0%A1%D0%BA%D0%BE%D0%BB%D1%8C%D0%B7%D1%8F%D1%89%D0%B0%D1%8F_%D1%81%D1%80%D0%B5%D0%B4%D0%BD%D1%8F%D1%8F

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

[zuborg]

Добавил таблички, можете сравнить.

[ffriend]

Я, может быть, чего-то не понял, но вроде бы автор говорил о медиане по всему набору данных, а в указанной статье речь в основном идёт об арифметическом среднем, причём скользящем, т.е. только по n последним значениям. Скользящие функции тривиально реализуются за O(n) времени и O(1) памяти, а вот по всему объёму — это уже интересней.

[zuborg]

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

[ffriend]

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

[zuborg]

Учитываются, верно. Просто потихоньку теряют свой вес.

[SeptiM]

Да, интересная задача. Если в один проход решать, то можно ткнуть в несколько случайных элементов и выбрать из них медиану. Если элементов будет порядка O(1/eps^2 \log(1/delta)), то вероятность, что выбранный элемент будет стоять от медианы на расстоянии не более eps * n будет не меньше 1 — delta.

А еще вроде есть хитрый алгоритм Мунро-Патерсона, который умеет эту задачу решать точно с O(1) памяти за O(log n) проходов.

[iroln]

Вопрос по теме и неплохой ответ на StackOverflow.

[zuborg]

Да, ничто не ново под Луной ;) Я не особо усердно искал решение этой проблемы, ограничившись только рускоязычными материалами.

[dimview]

Есть же Greenwald and Khanna GK01 и многочисленные его вариации, находятся по ключевым словам fast approximate quantiles.

[Rulexec]

По поводу эфективности… а оценка имеет наименьшую дисперсию в классе несмещённых оценок?

Такое ощущение, что вовсе нет.

[zuborg]

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

[Witold]

А почему в одном случае из десяти так резко отличается отклонение? Ещё я не вижу сильной корреляции на разных размерах выборки, вы пробовали задавать размер в районе 10^6 — 10^8?

[zuborg]

Случайное отклонение. На больших выборках (типа 10^6) их вероятность настолько ничтожна, что такие выбросы не встречаются.