将流分成具有相等计数的箱

Question

理想情况下，我希望在不从硬盘读取数据太多次的情况下执行以下操作。数据大，内存不能同时保存所有数据。

输入是来自硬盘的流x[t]。数字流包含 N 个元素。
可以有 x 的直方图和 m 个分箱。
n 个 bin 由 bin 边定义 e₀ < e₁, ..., < e_米。例如，如果 e_i =< x[0] < e_i+1，则 x[0] 属于 i^th bin.
找到使 bin 包含流中几乎相等数量的元素的 bin 边缘。每个 bin 中的元素数量理想情况下应该在 N/m 的某个阈值百分比内。这是因为如果我们将 N 个元素平均分布在 m 个箱子中，每个箱子应该容纳大约 N/m 个元素。

当前解决方案：

import numpy as np


def test_data(size):
    x = np.random.normal(0, 0.5, size // 2)
    x = np.hstack([x, np.random.normal(4, 1, size // 2)])
    return x


def bin_edge_as_index(n_bin, fine_hist, fine_n_bin, data_size):
    cum_sum = np.cumsum(fine_hist)
    bin_id = np.empty((n_bin + 1), dtype=int)

    count_per_bin = data_size * 1.0 / n_bin

    for i in range(1, n_bin):
        bin_id[i] = np.argmax(cum_sum > count_per_bin * i)

    bin_id[0] = 0
    bin_id[n_bin] = fine_n_bin
    return bin_id


def get_bin_count(bin_edge, data):
    n_bin = bin_edge.shape[0] - 1
    result = np.zeros((n_bin), dtype=int)
    for i in range(n_bin):
        cmp0 = (bin_edge[i] <= data)
        cmp1 = (data < bin_edge[i + 1])
        result[i] = np.sum(cmp0 & cmp1)
    return result


# Test Setting
test_size = 10000
n_bin = 6
fine_n_bin = 2000  # use a big number and hope it works

# Test Data
x = test_data(test_size)

# Fine Histogram
fine_hist, fine_bin_edge = np.histogram(x, fine_n_bin)

# Index of the bins of the fine histogram that contains
# the required bin edges (e_1, e_2, ... e_n)
bin_id = bin_edge_as_index(
    n_bin, fine_hist, fine_n_bin, test_size)

# Find the bin edges
bin_edge = fine_bin_edge[bin_id]
print("bin_edges:")
print(bin_edge)

# Check
bin_count = get_bin_count(bin_edge, x)
print("bin_counts:")
print(bin_count)
print("ideal count per bin:")
print(test_size * 1.0 / n_bin)

程序输出：

bin_edges:
[-1.86507282 -0.22751473  0.2085489   1.30798591  3.57180559  4.40218207
  7.41287669]
bin_counts:
[1656 1675 1668 1663 1660 1677]
ideal count per bin:
1666.6666666666667

问题：

我无法指定阈值 s，并且预计 bin 计数最多与每个 bin 的理想计数相差 s%。

Answer 1

Iff 您可以假设您的数据是随机的，具有 定义的分布 （即：取数据的任何重要百分比in sequence 将 "sketch" 与整个数据相同的分布，只是精度较差），我想有很多选择：

读取一些过采样直方图中的部分数据。基于此，为 bin 边缘选择一个近似值 你现在做的方式 （如你的问题中所解释的），然后对这些 bin 进行均匀过采样，然后将另一块数据读入新的垃圾箱等。如果您有足够的数据，以块 0f 10% 的形式处理它们将允许进行 10 次迭代以在一次通过中改进您的 bins 结构。
从多个 bin 开始并积累一些（不是全部）数据。查看它们，如果一个 bin_width*count 不成比例地高于邻居（也许这就是 precision/error 可能发挥作用的地方），将该容器一分为二，并启发式地将旧容器计数分配给新创建的容器垃圾箱（一种可能的启发式 - 与邻居的数量成正比）。最后，您应该有一个由可接受的误差以某种方式控制的除法，从中可以对您的分布进行插值。

当然，以上仅是方法的想法，不能对它们的效果提供任何保证。

Answer 2

假设分布没有严重偏斜（例如 1.0000001 和 1.0000002 之间的 10000 个值和 9.0000001 和 9.0000002 之间的 10000 个值），您可以按以下步骤进行。

计算一个具有足够分辨率的直方图，比如说 K 个箱子，它覆盖了整个范围（希望事先知道）。这将对数据进行一次传递。

然后计算累积直方图，并在此过程中识别 m+1 分位数边缘（其中累积计数交叉 N/m 的倍数）。

您将获得的准确性取决于原始直方图的 bin 中元素的最大数量。

对于 N 个元素，使用 K 个 bin 的直方图并假设一些 "nonuniformity factor"（等于合理分布的几个单位），最大误差将是 f.N/K.

如果您愿意，可以通过考虑 m+1 辅助直方图来提高准确性，这些直方图仅累积落在全局直方图的分位数箱中的值。然后你可以将分位数细化到这些辅助直方图的分辨率。

这将花费您额外的 pass，但错误将减少到 f.N/(K.K')，使用 K 然后 m.K' 直方图 space，而不是 K.K'.

将流分成具有相等计数的箱

Divide a stream into bins with equal counts

python

algorithm

numpy

stream

numerical-methods