-3

给定相同数量的桶的一些直方图，我需要找到这些直方图的“中心”。“中心”是一个直方图，使得地球移动器与所有其他直方图的距离之和最小。

例如，给定 4 个直方图A, B, C, D，算法需要输出一个新的直方图X，使得它EMD(X, A) + EMD(X, B) + EMD(X, C) + EMD(X, D)是最小值。

简单算术平均找不到“中心”，这里是一个例子。

我需要计算数百万直方图的“中心”，那么如何有效地找到“中心”。如果不存在快速算法，是否有任何好的近似值？

=== 编辑 ===

添加了一个示例来澄清我的问题。

4

2 回答 2

1

推土机距离非正式地将每个分布或在这种情况下的直方图视为一堆泥土。然后根据 EMD 找到中心包括找到最小化每个直方图面积单位乘以它必须移动的距离的乘积的点。例如，移动具有 7 个成员的直方图 bin 与移动具有 1 个成员的 7 个单元的直方图 bin 具有相同的 EMD。为简单起见，我假设您的分布只有一个维度，但如果不是，则可以沿每个维度独立找到该中心点。

推土机距离实际上非常类似于物理学或静力学中的概念；第一刻。形状的一阶矩定义为每个面积单位乘以该单位面积到中心点的距离的乘积。找到中心点，使得中心点每一侧（沿任何主要维度）的总面积相同。

静态爱好者会记得，这个中心点实际上只是沿每个维度的区域分布的平均值。EMD 定义产生了类似的结果。因此，要找到直方图组的 EMD 质心，请执行以下操作：

将每个 bin 的每个成员视为一个单元。为每个单元分配与该 bin 关联的值。因此，如果对于给定维度 bin 0-10 有 5 个条目，则您有 5 个单元，每个单元的值为 5（bin 的平均值）。找到所有单位的中值，这是该维度的质心值。如果有多个维度，请重复所有维度，仅此而已！

在这个有 2 个直方图的简单示例中，将每个 bin 元素视为一个单元后，中位数（因此中心）为 4。显然，将中心移动到 4 以上或以下将导致 EMD 增加 5 并减少 4 .

进入问题的核心，您可以做得比对所有直方图元素进行排序以找到中位数略好，而不是使用 QuickSelect 获得平均时间复杂度 O(n)，最坏情况为 O(nlogn)。

于 2020-08-31T04:39:28.840 回答
0

如果“中心”指的是中位数，则需要对数据集进行排序；在这种情况下，直方图已经排序。可以理解，直方图的数据很可能不是列表形式；但是，由于没有其他选择，因此答案将如此安排。

原始数据：值列表直方图数据：元组列表“（（最小，最大），数量）”

可用的原始数据：

#all data from histogram w/o bucket approximation
data = []
#sorting algorithm should be optimized for the size of the dateset 
#skip this step if data set sorted
data.sort()
median = (data[int(len(data)/2)]+data[round(len(data)/2)])/2

直方图数据：

#data from histogram only
data = []
#sort by min
#skip this step if histogram is already sorted
sort(key=lambda x:x[0][0])
#n is the data quantity
n = sum([bucket[1] for bucket in data])

#loop checks to see if median is captured in current bucket 
#by expanding the "net" by the current bucket size
rollingQuant = 0
median = None
for bucket in data:
    rollingQuant += bucket[1]
    #if median captured in bucket True
    if rollingQuant >= n/2:
        median = bucket[0]

问题：

  • 只能估计直方图数据的中值是不可能计算的；估计的一个例子是定义具有最小值最大值和桶中点数的线性方程。
于 2020-08-31T02:13:00.510 回答