Поддержание контейнера объектов, отсортированных по разнице между членом этого объекта и членом его соседа - PullRequest
Новая
       26

Поддержание контейнера объектов, отсортированных по разнице между членом этого объекта и членом его соседа

5 голосов
/ 27 июля 2011

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

Так, например, если вы аппроксимируете поток данных 23, 19, 10, 16, 36, 2, 9, 32, 30, 45 пятью ячейками гистограммы, вы прочитали бы первые пять элементов , получив:

(23, 1), (19,1), (10,1), (16,1), (36,1)

Добавление корзины (2,1) вызывает проблему, так как мы превысили максимальное количество корзин. Итак, мы добавляем (2,1) и объединяем два ближайших контейнера - (16,1) и (19,1) - чтобы получить новый контейнер (17.5,2), который заменяет эти два.

Повторение этого метода для остальной части гистограммы дает нам окончательный результат:

(2,1), (9,5,2), (19,33,3), (32,67,3), (45,1).

Реализация этого без учета сложностей является тривиальной. Тем не менее, я действительно обеспокоен оптимизацией этого для больших наборов данных, потому что моя «тривиальная» реализация в конечном итоге занимает 15 секунд для запуска в потоке 100 000 гауссовских распределенных значений.

Моя текущая мысль - использовать boost :: multi_index для отслеживания моей структуры HistogramBin, которая определяется как: 

struct HistogramBin
{
    double bin;
    unsigned long count;
    bool isNull;

    HistogramBin(double x, bool n = false)
    : bin(x), count(1), isNull(n) {}

    bool operator<(const HistogramBin &other) const
    { return (bin < other.bin); }

    // Merges other with this histogram bin
    // E.g., if you have (2.0,1) and (3.0,2), you'd merge them into (2.67,3)
    void merge(const HistogramBin &other)
    {
        unsigned long old_count = count;
        count += other.count;
        bin = (bin*old_count + other.bin*other.count)/count;
    }

    // Gets the difference between two histogram bins
    const double getDifference(const HistogramBin &other) const
    { return (double)abs(bin - other.bin); }
};

Итак, multi_index будет использовать order_unique <> для сортировки по HistogramBin :: bin.

Теперь, это не решает проблему сортировки бинов по различиям между соседними бинами. Индексирование с помощью HistogramBin :: bin дает нам упорядоченный список объектов HistogramBin, но затем следующим шагом является вычисление разницы между текущим bin и следующим, а затем сортировка по этим значениям.

Есть ли способ сортировки по этим значениям, сохраняя целостность списка и не вводя новый контейнер (например, мультикарту пар разностей / ключей и значений итератора)?

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

Будем благодарны за любые мысли или понимание.

Ответы [ 2 ]

1 голос
/ 27 июля 2011

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

Как насчет этого:

  1. Для N бинов, Bin min для Bin max , присвойте им начальное значение вашего ввода
  2. Для каждого нового номера X, если X равен min , задайте Bin min = X, если X> Bin max установите Bin max = X
  3. Если вы изменили границы в 2, установите значение каждого бина так, чтобы Бин L = (Бин макс - Бин мин ) / N * L, где L - порядковый номер бина
  4. Добавьте X в корзину с ближайшим значением к X.

Это задняя часть салфетки, так что я уверен, что где-то есть ошибка. Идея состоит в том, чтобы «рефакторизовать» гистограмму только тогда, когда значение выходит за ее пределы, поэтому в обычном случае все, что вам нужно сделать, это добавить X в корзину, которая наиболее точно соответствует ей. Я считаю, что это должно привести к очень похожей гистограмме, если не эквивалентной. Шаг 1 - ваша инициализация, шаги 2-4 - цикл, если неясно.

0 голосов
/ 27 июля 2011

Публикация этого ответа:

Посмотрите на ответ на этот вопрос: Онлайн-кластеризация k-средних . Если я правильно понимаю вашу проблему, это в значительной степени то, что вы ищете, где начальные угадывания - ваши первые значения k.

Если вы сохраняете порядок в своих бин-центрах, вы можете выполнить двоичный поиск в списке, и ближайшим значением будет либо предыдущее, либо последующее, с общей сложностью O(n*log(m)), где m - количество бинов n - объем данных.

.
...