Аппроксимация гистограммы для потоковых данных

Question

Этот вопрос является небольшим продолжением того, на который ответил здесь . Я работаю над повторной реализацией версии аппроксимации гистограммы, найденной в разделе 2.1 этой статьи , и я хотел бы собрать все свои утки подряд, прежде чем снова начать этот процесс. В прошлый раз я использовал boost::multi_index, но производительность была не самой большой, и я хотел бы избежать логарифмического числа вставок / сложностей в сегментах std::set. Из-за количества используемых мной гистограмм (по одной на элемент на класс на листовой узел случайного дерева в случайном лесу) сложность вычислений должна быть максимально близкой к постоянной.

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

1. инициализировать стандартный массив C размером N, где N = количество бинов; и
2. умножьте входное значение (действительное число) на некоторый коэффициент и напишите результат, чтобы получить его индекс в массиве C.

Это хорошо работает для гистограмм с одинаковым размером бина и довольно эффективно. Однако в разделе 2.1 вышеупомянутой статьи приведен алгоритм гистограммы без одинаковых размеров бинов.

Другая проблема заключается в том, что простое умножение входного реального значения на коэффициент и использование полученного продукта в качестве индекса дает сбой с отрицательными числами. Чтобы решить эту проблему, я подумал о том, чтобы идентифицировать бен '0' где-нибудь в массиве. Эта корзина будет центрирована на 0,0; бункеры выше / ниже могут быть рассчитаны с использованием только что объясненного метода умножения и дна, с небольшим изменением - добавление напольного продукта к двум или вычитание из двух при необходимости.

Тогда возникает вопрос о слияниях: алгоритм в статье объединяет два ближайших среза, измеряемых от центра к центру. На практике это создает приближение «густой» гистограммы, потому что некоторые ячейки будут иметь очень большие значения, а другие - нет. Конечно, это связано с ячейками неоднородного размера и не приводит к потере точности. Однако потеря точности произойдет, если мы попытаемся нормализовать ячейки неоднородного размера, чтобы получить однородную форму. Это связано с предположением, что m / 2 выборки попадают слева и справа от центра бина, где m = количество бинов. Мы могли бы смоделировать каждую ячейку как гауссовскую, но это все равно приведет к потере точности (хотя и минимальной)

Так вот где я застрял прямо сейчас, что приводит к следующему важному вопросу: Каков наилучший способ реализации гистограммы, принимающей потоковые данные и хранящей каждую выборку в ячейках одинакового размера?

Answer 1

Сохранить четыре переменные.

int N;  // assume for simplicity that N is even
int count[N];
double lower_bound;
double bin_size;

Когда поступит новый образец x, вычислите double i = floor(x - lower_bound) / bin_size. Если i >= 0 && i < N, то увеличить count[i]. Если i >= N, то многократно удваивайте bin_size до x - lower_bound < N * bin_size. При каждом удвоении корректируйте количество (оптимизируйте это, используя разреженность для множественных удвоений).

for (int j = 0; j < N / 2; j++) count[j] = count[2 * j] + count[2 * j + 1];
for (int j = N / 2; j < N; j++) count[j] = 0;

Случай i < 0 сложнее, так как нам нужно уменьшить lower_bound, а также увеличить bin_size (опять же, оптимизировать для разреженности или скорректировать число за один шаг).

while (lower_bound > x) {
    lower_bound -= N * bin_size;
    bin_size += bin_size;
    for (int j = N - 1; j > N / 2 - 1; j--) count[j] = count[2 * j - N] + count[2 * j - N + 1];
    for (int j = 0; j < N / 2; j++) count[j] = 0;
}

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

Если вы реализуете это с плавающей запятой, помните, что числа с плавающей запятой не являются действительными числами и что операторы типа lower_bound -= N * bin_size могут вести себя неправильно (в этом случае, если N * bin_size намного меньше, чем lower_bound). Я рекомендую, чтобы bin_size всегда был степенью радиуса (обычно два).