Как сохранить динамическую гистограмму? - PullRequest
Новая
       11

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

16 голосов
/ 29 июля 2011

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

Представьте, что у меня есть поток данных (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 для всех бинов.

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

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

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

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

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

Ответы [ 3 ]

13 голосов
/ 30 июля 2011

Как определить количество бинов

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

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)

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

Алгоритм

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

Комментарии

  1. Правило Фридмана – Диакониса лучше для выбора количества бинов, но оно включает в себя интервал между квантилями, который немного сложнее вычислить онлайн.
  2. Техническиинтервал CI не корректен, когда данные последовательны.Но если вы установите разумное минимальное количество точек данных для наблюдения, скажем, ~ 100 или 1000, у вас должно быть все в порядке.
  3. Это предполагает, что все данные соответствуют одному и тому же распределению.
  4. Числобункеры зависит от п ^ {- 1/3}.Если вы приблизительно знаете, сколько точек ожидать, например, 10 ^ 5, 10 ^ 6 или 10 ^ 7, то вы можете создать меньшие ячейки с ожиданием изменения ширины ячейки в будущем.
5 голосов
/ 29 июля 2011

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

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) -время выбора. Если выбор частый, я бы использовал двоичное дерево поиска, где каждый узел хранит общий вес в своем поддереве. Например, после 

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.

2 голосов
/ 29 июля 2011

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

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

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. Все очевидные ограничения применяются.

...