Разделите поток в бункеры с равными значениями

Question

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

1. Ввод - это поток x[t] с жесткого диска. В потоке чисел содержится N элементов.
2. Возможно иметь гистограмму x с m ячейками.
3. п бункера определяются мусорными ребра х < е ..., < х _м. Например, если е _я = < х [0] < е _{+ 1}, то х [0] принадлежит к I-й бин.
4. Найти края бункеров, которые делают лоток, содержит почти равное количество элементов из потока. Количество элементов в каждом бункере должно быть идеально в пределах некоторого порогового процента от 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, и ожидать, что отсчеты бин находятся в наиболее s%, отличное от идеального количества в бункере.

Answer 1

Предполагая, что распределение не возмутительно искажено (например, 10000 значений между 1.0000001 и 1.0000002 и 10000 другими между 9.0000001 и 9.0000002), вы можете действовать, как показано ниже.

Вычислить гистограмму с достаточным разрешением, скажем, K бункеров, которые покрывают весь диапазон (мы надеемся, известно заранее). Это займет один проход по данным.

Затем вычислите накопленную гистограмму и, как вы идете, определите края квантилей m+1 (где накопленные подсчеты пересекают кратные N/m).

Точность, которую вы получите, определяется максимальным количеством элементов в корзине оригинальной гистограммы.

Для N элементов, используя гистограмму K бункеров и предполагая некоторый «коэффициент неравномерности» (равный нескольким единиц для разумных распределений), максимальная ошибка будет f.N/K.

---

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

Это будет стоить вам дополнительный проход, но ошибка будет сведена к f.N/(K.K'), используя K то m.K' гистограмм пространство только, вместо K.K'.

Answer 2

Ифф вы можете считать, что вы данные случайна определенное распределение (то есть: принимать какие-либо нетривиальное процент ваших данных в последовательности собирается «эскиз» то же самое распределение всех данных, только с более грубой точностью), я полагаю, есть несколько вариантов:

1. прочитал часть ваших данных в некоторой избыточной дискретизации гистограммы. Исходя из этого, выберите аппроксимацию для краев бункера , как вы это делаете сейчас (как объясняется в вашем вопросе), затем равномерно перевыполняйте эти бункеры, затем читайте другой кусок ваших данных в новые бункеры и так далее. Если у вас достаточно данных, обработка их в кусках 0f 10% позволит использовать 10 итераций, чтобы улучшить структуру ваших бункеров за один проход.

2. начните с нескольких ящиков и скопируйте некоторые (не все) данные. Посмотрите на них, и если у вас есть bin_width*count непропорционально выше, чем соседи (возможно, это то, где точность/ошибка может вступить в игру), разделите этот бит на двоих и эвристически присвойте старый счетчик бункера во вновь созданные бункеры (один из возможных эвристических - пропорционально числу соседей). В конце вы должны иметь подразделение, каким-то образом контролируемым приемлемой ошибкой, чтобы сортировать интерполяцию вашего дистрибутива.

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