Как я могу выровнять распределение вероятностей в потоке в реальном времени?

Question

Я получаю (очень быстрый) поток данных в реальном времени между 0 и 1, и мне нужно отсортировать их в «корзины».

Предположим, что идет 0,6, и мои ведра занимают площадь по 0,25 каждый. Это означает, что 0,6 входит в третье ведро. Однако, когда будет около 0,6, все они окажутся в третьем сегменте, что плохо.

Я хочу изменить области, охватываемые четырьмя группами, так, чтобы каждая группа имела равную вероятность попадания. Например, может быть лучше сделать одну крышку ведра 0-0,5, вторую 0,5-0,6, одну 0,6-0,65 и последнюю 0,65-1.

Проблема в том, что я не могу сохранить значения - только в какие сегменты попадет как часто. Так есть ли рабочая формула обновления для этого?!

Заранее большое спасибо!

Answer 1

Я думаю, что вы хотите сохранить своего рода дерево ведер.

Это звучит как работа для кодирования Хаффмана или варианта арифметического кодирования .

Я знаю, что существует потоковый вариант кодирования Хаффмана,Я не уверен насчет Арифметики.Но кажется, что по крайней мере вы могли бы периодически определять новую модель и копировать старые значения в новую модель.

Поскольку у вас нет старых значений, вам, возможно, придется угадывать границы, а не вычислять их.Например, вы можете определить 100 новых сегментов до 0,6, а затем свернуть неиспользованные сегменты.

Answer 2

Если вы не храните значения, то в какой-то момент времени все, что у вас есть, это

, сколько значений находится между x и y.

Чтобы сохранить равную вероятность между вашими бинами /ведра значения очень важны.Давайте начнем с этого потока в реальном времени и предположим, что он начался изначально с 0,12 0,37, 0,62 и 0,87. В каждой ячейке будет по 1 ячейке.

Для значений 0,24,0,49,0,74,0,99 снова каждый бин получит 1

Для значений 0,01,0,26,0,51,0,76 снова каждый бин получит 1

.в конечном итоге с 3 в каждой корзине.Теперь, если 0,6 начинает поступать, приходит примерно 6 раз, делая 3-й бин на 9, а остальные - 3. Скажем, теперь вам нужно обновить свои границы.Если вы переместите границы бина сейчас, ваша вероятность для каждого бина не будет правильной.

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

Было бы интересно узнать, как другие думают об этом.