Как сохранить динамическую гистограмму?

существует ли известный алгоритм + структура данных для поддержания динамической гистограммы?

Представьте, что у меня есть поток данных (x_1, w_1), (x_2, w_2),... где x_t - двойники, представляющие некоторую измеренную переменную, а w_t - связанный вес.

Я мог бы просто сделать очевидный (псевдо-питонный код):

x0,xN = 0, 10
numbins = 100
hist = [(x0 + i * delta , 0) for i in xrange(numbins)]
def updateHistogram(x, w):
    k = lookup(x,  hist)    #find the adequated bin where to put x
    hist[k][1] += 1

Но у меня есть некоторые проблемы с этим, когда у меня есть непрерывный поток данных. У меня нет полного набора данных в руках, и я должен проверить гистограмму между сбором данных. И я не ожидаю:

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

Итак, я хочу динамически определять бункеры. Я мог бы сделать глупость:

 for x in data_stream:
      data.append(x)
      hist = make_histogram(data)

но я думаю, что это будет очень быстро...

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

data = sortedarray();
for x in data_stream:
     data.insert(x)
     bins = [ data[int(i * data.size()/numbins)] for i in xrange(numbins)]

и подсчет внутри каждого бина будет равен data.size()/numbins для всех бинов.

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

EDIT: (для запрошенного разъяснения)

x_t - числа с плавающей запятой. Чтобы вычислить гистограмму, я должен разделить непрерывный диапазон, где x принадлежит в нескольких ячейках. Поэтому у меня будет последовательность чисел bin [0], bin [1] и т.д., Поэтому я должен определить, для чего я делаю bin [i] < x < бен [г + 1].

Вот как вы обычно делаете гистограмму, когда у вас есть все данные заранее. Затем вы должны знать пределы max (x) и min (x), и было бы легко определить соответствующие ячейки. Например, вы могли бы разделить их на равные промежутки между min (x) и max (x).

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

Ответы

Ответ 1

Как определить количество ящиков

В гистограмме существует ряд правил определения количества ящиков. Для вашей проблемы я бы пошел с выбором Скотта:

bin_width = 3.5*sd*n^{-1/3}

где sd - стандартное отклонение, а n - количество точек данных. Реально, вы можете использовать алгоритм онлайн для расчета стандартного отклонения. Число бинов k задается выражением:

k = ceil((max(x) - min(x))/bin_width)

Сохранение данных

Предположим, что мы наблюдали N точек данных. Тогда доверительный интервал для стандартного отклонения,

Lower limit: sd*sqrt((N-1)/CHIINV((alpha/2), N-1))
Upper limit: sd*sqrt((N-1)/CHIINV(1-(alpha/2), N-1))

где CHIINV является значением из хи-квадратного распределения. Когда N = 1000, CI для sd:

(0.96*sd, 1.05*sd)

и, следовательно, 95% CI ширина бина:

(3.5*0.96*sd*1000^{-1/3}, 3.5*1.05*sd*1000^{-1/3})
(0.336*sd, 0.3675*sd)

Вы можете получить что-то похожее для количества ящиков.

Алгоритм

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

Комментарии

Правило Freedman-Diaconis лучше выбирать количество ящиков, но оно включает в себя диапазон между квантилями, который немного сложнее рассчитать в Интернете.
Технически, интервал CI неверен, когда данные являются последовательными. Но если вы установите разумное минимальное количество точек данных для наблюдения, скажем ~ 100 или 1000, вы должны быть в порядке.
Это предполагает, что все данные следуют за тем же распределением.
Количество ячеек зависит от n ^ {- 1/3}. Если вы знаете примерно, сколько очков ожидать, т.е. 10 ^ 5, 10 ^ 6 или 10 ^ 7, то вы могли бы создать небольшие бункеры с ожиданием изменения ширины бункера в будущем.

Ответ 2

Звучит так, как будто вы хотите реализовать следующий абстрактный тип данных.

insert(x, w): add item x to the collection with weight x
select(p): return the item greater than a p weighted fraction of the items

Например, select(0) возвращает минимум, select(0.5) возвращает взвешенную медианную форму, а select(1) возвращает максимум.

Я бы реализовал этот ADT одним из двух способов. Если выбор нечасто, я бы поместил данные в массив и использовал алгоритм выбора по линейному времени, для O (1) -временных вставок и O (n) -time выбирает. Если выбор частый, я бы использовал двоичное дерево поиска, где каждый node хранит общий вес в своем поддереве. Например, после

insert(2, 10)
insert(1, 5)
insert(3, 100)
insert(4, 20)

дерево может выглядеть как

   2 (135)
  / \
 /   \
1 (5) 4 (120)
     /
    /
   3 (100)

Теперь, чтобы найти взвешенную медиану, умножьте 135 на 0.5 и получим 67.5 как желаемый "индекс". Начиная с корня 2, мы находим, что 5 меньше 67.5, поэтому элемент не находится в левом поддереве и мы вычитаем 5, чтобы получить 62.5, индекс в остальную часть дерева, Так как 135 - 120 = 15 меньше 62.5, медиана не является 2. Вычитаем 15 из 62.5, чтобы получить 47.5 и опуститься до 4. При 4 мы находим, что 100 больше, чем 47.5, поэтому 3 является медианом.

Предполагая сбалансированное дерево, время работы как insert, так и select равно O(log n). Если бы я реализовал с нуля, я бы предпочел использовать splay tree.

Ответ 3

ROOT - это инструмент, используемый физиками частиц для такого рода работ... и он связан с привязками python. Имейте в виду, что это не легкая часть программного обеспечения.

В С++ вы бы сделали что-то вроде

TH1D hist("hist","longer title for hist",numbins,lowlimit,highimit);

...

for (int i=0; i<num; ++i){
   hist.Fill(x[i],w[i]);
}

...

hist.Draw();

ROOT не содержит встроенного решения проблемы с биннингами, в нижнем и верхнем потоках добавляются входные данные ниже/выше диапазона бит.

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

Ответ 4

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

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