维护一个对象容器,该容器按该对象的成员与其邻居的成员之间的差异排序

Question

我正在努力实现直方图,其中一个关键点是直方图箱的快速合并.因为我没有关于直方图近似的数据集的先验知识,所以我需要提出一种方法,在我超过最大数量的箱之后快速合并相邻的箱.

因此,作为一个例子,如果您使用五个直方图箱来近似数据流23,19,10,16,36,2,9,32,30,45,那么您将读入前五个元素,获得:

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

添加bin(2,1)会导致问题,因为我们已经超过了最大的bin数.因此,我们添加(2,1)并合并两个最接近的二进制位 - (16,1)和(19,1) - 以获得一个替换这两个的新bin(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将使用ordered_unique <>对HistogramBin :: bin进行排序.

现在,这并不能解决因相邻垃圾箱之间的差异而对垃圾箱进行排序的问题.通过HistogramBin :: bin索引为我们提供了一个有序的HistogramBin对象列表,但接下来的步骤是计算当前bin和下一个bin之间的差异,然后对这些值进行排序.

有没有办法对这些值进行排序,同时保持列表的完整性,而不引入新的容器(例如差异/迭代器键/值对的多重映射)？

维护此列表是我目前对复杂性问题的近似最优解决方案的想法,因为它只需要在合并时进行更改,并且仅在添加新值时才会进行合并.

任何想法或见解将不胜感激.

Answer 1

将此作为答案发布：

看看这个问题的答案：在线k-means聚类。如果我正确理解你的问题，这几乎就是你所寻找的，其中初始 k 猜测是你的第一个 k 值。

如果保持 bin 中心有序，则可以对列表进行二分搜索，最接近的值是之前的值或之后的值，总体复杂度为O(n*log(m))其中m是 bin 数量，n是数据量。