Каков хороший алгоритм для оценки медианы огромного набора данных с однократным чтением?

48

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

Аппроксимации хороши, пока точность известна.

Есть указатели?

PeterR
источник
4
Возможно, запрос на Stackoverflow может получить лучшие ответы.
2
@Srikant:> это довольно активная область исследований в области статистики :) Решение, наиболее близкое к нижним теоретическим границам с точки зрения хранения, также включает некоторые довольно умные вероятностные конструкции. В общем, я был удивлен, когда впервые посмотрел на него пару месяцев назад; Здесь больше статистики, чем кажется на первый взгляд.
user603

Ответы:

6

Не могли бы вы сгруппировать набор данных в гораздо меньшие наборы данных (скажем, 100, 1000 или 10000 точек данных)? Если затем вы рассчитали медиану каждой из групп. Если вы сделали это с достаточным количеством наборов данных, вы могли бы построить что-то вроде среднего значения результатов каждого из меньших наборов и этого анализа, запустив достаточно небольшие наборы данных, сходящиеся к «среднему» решению.

Ян Тернер
источник
Это интересно, и где некоторые статистические советы могут прийти! Предположим, что у меня есть, скажем, 500 000 очков iid, и я смотрю на группы, скажем, 1000 из них, и вычисляю медиану каждой группы. Теперь у меня 500 медиан. Есть ли теория, которая могла бы позволить мне рассчитать доверительный интервал для общей медианы на основе этих 500 медиан?
PeterR
4
Так, по словам давно потерянного коллеги, лучшим подходом, по-видимому, являются Чиранджиб Бурагохайн и Субхаш Сури. Квантили на ручьях. cs.ucsb.edu/~suri/psdir/ency.pdf Мне также нравится подход Яна, так как эти медианы небольших наборов данных будут сходиться к нормальному распределению, и поэтому я могу сформировать интервалы conf для медиан.
PeterR
10

Как насчет процедуры биннинга? Предположим (в целях иллюстрации), что вы знаете, что значения находятся в диапазоне от 1 до 1 миллиона. Установите N лотков размера S. Поэтому, если S = ​​10000, у вас будет 100 лотков, соответствующих значениям [1: 10000, 10001: 20000, ..., 990001: 1000000]

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

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

Редактировать:

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

chrisamiller
источник
Проблема с подходом биннинга заключается в том, что у нас нет хорошей верхней границы для данных, и поэтому средняя точка для самого большого бина должна быть огромной. Итак, нам нужно огромное количество бинов (недостаточно памяти для этого) или достаточно широкие бины (что приведет к довольно неточному ответу). И данные не очень редки.
PeterR
Поскольку вас интересует только медиана, почему вы не можете расширить ячейки при более высоких значениях вашей переменной?
Расселпирс
drknexus - потому что мы не знаем, какой должна быть самая большая корзина.
PeterR
Есть ли у вас какие - либо интуиции относительно того , что будет диапазон? Если вы точно уверены, что более половины ответов будут ниже числа N, тогда вы можете сделать свой последний бин настолько большим, насколько захотите. Может быть, ваша последняя корзина содержит все числа, превышающие 1 триллион - это будет достаточно высоко? Имея объем памяти в современных системах, вы можете хранить МНОГО лотков и достигать довольно высокого разрешения. С точки зрения структур данных, мы не говорим здесь ничего необычного и интенсивного использования памяти.
chrisamiller
Любая интуиция? да. И ваш подход может работать в целом. Однако в этом случае у нас не может быть много памяти / вычислений. Это сетевое приложение, в котором устройство может видеть десятки тысяч элементов в секунду, и для этого осталось ОЧЕНЬ мало обработки. Я знаю, что это не идеальный / типичный сценарий, но именно это делает его интересным!
PeterR
9

Я перенаправляю вас к моему ответу на подобный вопрос . В двух словах, это алгоритм чтения «на лету», с сложностью в худшем случае для вычисления (точной) медианы.O(n)

user603
источник
8

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

Робби МакКиллиам
источник
7

Я реализовал алгоритм P-квадрата для динамического вычисления квантилей и гистограмм без сохранения наблюдений в аккуратном Python-модуле, который я написал под названием LiveStats . Это должно решить вашу проблему довольно эффективно.

Шон
источник
(+1) Спасибо, что зашли и предоставили эту ссылку, Шон!
whuber
2

Мне никогда не приходилось это делать, так что это всего лишь предложение.

Я вижу две (другие) возможности.

Половина данных

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

Выборочное распределение

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

1,253 * SD / sqrt (н)

Чтобы определить размер n, которым вы будете довольны, я запустил быстрое моделирование Монте-Карло в R

n = 10000
outside.ci.uni = 0
outside.ci.nor = 0
N=1000
for(i in 1:N){
  #Theoretical median is 0
  uni = runif(n, -10, 10)
  nor  = rnorm(n, 0, 10)

  if(abs(median(uni)) > 1.96*1.253*sd(uni)/sqrt(n))
    outside.ci.uni = outside.ci.uni + 1

  if(abs(median(nor)) > 1.96*1.253*sd(nor)/sqrt(n))
    outside.ci.nor = outside.ci.nor + 1
}

outside.ci.uni/N
outside.ci.nor/N

Для n = 10000 15% единообразных медианных оценок были вне CI.

csgillespie
источник
3
Набор данных потенциально слишком велик, чтобы его можно было прочитать наполовину ... он находится в сетевом контексте, где устройство, выполняющее обработку, может видеть десятки тысяч элементов в секунду и, вероятно, имеет достаточно памяти для хранения только нескольких сотен. Также данные точно не гауссовы. На самом деле он не подходит ни к одному из распространенных дистрибутивов.
PeterR
1

Вот ответ на вопрос, заданный на stackoverflow: https://stackoverflow.com/questions/1058813/on-line-iterator-algorithms-for-estimating-statistical-median-mode-skewness/2144754#2144754

Итеративное обновление медиана + = eta * sgn (образец - медиана) звучит так, как будто это может быть путь.

Сообщество
источник
1
но тогда как выбрать eta, и что тогда это значит статистически? т.е. как сформировать доверительные интервалы для медианы из этого результата?
PeterR
@PeterR, эй, какое окончательное решение вы использовали?
Аакаш Гоэль
1

Remedian Алгоритм (PDF) дает однопроходную медианную оценку с низкими требованиями к хранению и хорошо определенной точностью.

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

shoelzer
источник
1

Если значения, которые вы используете, находятся в определенном диапазоне, скажем, от 1 до 100000, вы можете эффективно вычислять медиану для чрезвычайно большого числа значений (скажем, триллионов записей) с целочисленным сегментом (этот код взят из лицензии BSD ea). -utils / САМ-stats.cpp)

class ibucket {
public:
    int tot;
    vector<int> dat;
    ibucket(int max) {dat.resize(max+1);tot=0;}
    int size() const {return tot;};

    int operator[] (int n) const {
        assert(n < size());
        int i;
        for (i=0;i<dat.size();++i) {
            if (n < dat[i]) {
                return i;
            }
            n-=dat[i];
        }
    }

    void push(int v) {
        assert(v<dat.size());
        ++dat[v];
        ++tot;
    }
};


template <class vtype>
double quantile(const vtype &vec, double p) {
        int l = vec.size();
        if (!l) return 0;
        double t = ((double)l-1)*p;
        int it = (int) t;
        int v=vec[it];
        if (t > (double)it) {
                return (v + (t-it) * (vec[it+1] - v));
        } else {
                return v;
        }
}
Эрик Аронесты
источник
Кроме того, это можно распространить на использование конечного числа бинов для медиан в реальном времени и т. Д.
Эрик Аронести,