Comments 6
Интересно, что Канн-Гринвальд детерминированный и всегда дает ответ с нужной погрешностью. Но он мне в свое время показался очень сложным, особенно в смысле понимания, почему работает.
У задачи поиска медианы и произвольного
-квантиля есть очень простое вероятностное решение через сэмплирование. Берем из всего набора случайно 
элементов, сортируем. Теперь, если хотим посчитать -квантиль, нужно просто вернуть 
-ый элемент. С константной вероятностью ответ будет на расстоянии не более 
от правильного. Если нужна вероятность ошибки 
, берем соответсвенно 
элементов.
Гарантия доказывается довольно просто через неравенство Чернова.
P.S. Предлагаю на подобные вещи ставить тэг data streaming.
У задачи поиска медианы и произвольного
Гарантия доказывается довольно просто через неравенство Чернова.
P.S. Предлагаю на подобные вещи ставить тэг data streaming.
На практике часто случается, что наши данные есть поток каких-то показаний с датчика, причем разрядность датчика часто довольно небольшая (8, 16, 24, пусть даже 32 бита). В этом случае можно посчитать медиану поточно за счет памяти. Просто создаем массив счетчиков, сколько раз встретился 0, сколько 1 и т.д. до maxval, тупо counter[sample]++. По сути строим гистограмму, найти по которой медиану вообще не проблема. При этом гистограмма сама по себе очень полезна в плане статистики, посмотреть распределение, посчитать отклонения, всякие колмогоровы-смирновы, вот это все.
В тексте есть ссылка на этот подход. И да, практически все пакеты предлагают именно гистограммный подход, например (раз уж я тут пишу на скале), он предлагается в mllib spark-а и breeze (scala backend) для spark. Тут я описываю метод, когда мы хотим обойтись минимальнымы предположениями о структуре входных данных, то есть мы не знаем min/max, не знаем разброс, да и вообще почти ничего не знаем. =)
Надо среднюю зарплату так считать
Sign up to leave a comment.
Медиана: точно, иногда точно и почти точно