ストリームを等しい数のビンに分割する

Question

理想的には、ハードディスクからデータを何度も読み取らずに、次のようにします。データは大きく、メモリは同時にすべてのデータを保持することはできません。

1. 入力はハードディスクからのストリームx[t]です。数字のストリームには、N要素が含まれています。
2. xのヒストグラムをmビンとすることは可能です。
3. n個のビンは、ビンによって定義されるが、E < E 、...、< E _メートル縁。例えば、e _i = <x [0] <e _{i + 1}の場合、x [0]はi ^番目のビンに属します。
4. ビンがストリームとほぼ同じ数の要素を保持するビンエッジを見つけます。各ビン内の要素の数は、理想的には、N/mのあるパーセントの範囲内にある必要があります。これは、m個のビンにNの要素を均等に配分すると、各ビンは約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 

問題：

Iが閾値Sを指定して、ビンカウントが最大である期待することはできませんs％はビンごとの理想的なカウントとは異なります。

Answer 1

分布が（1.0000001と1.0000002の間の10000の値と9.0000001と9.0000002の間の10000の値のように）過度に歪んでいないと仮定すると、以下のように進めることができます。

十分な解像度のヒストグラム、たとえばKビンを計算します。これは範囲全体をカバーしています（あらかじめわかっていることが望ましい）。これは、データを1回通過することになります。

次に、累積ヒストグラムを計算して、m+1分位数の辺（累積数がN/mの倍数を超える場合）を特定します。

精度は、元のヒストグラムのビン内の要素の最大数によって決まります。 N要素について

、Kビンのヒストグラムを使用し、（合理的なディストリビューションのための少数の単位に等しい）いくつかの「不均一性因子」と仮定すると、最大誤差はf.N/Kあろう。

---

あなたが唯一のグローバルヒストグラムの分位のビンに落ちるの値を蓄積m+1補助ヒストグラムを考慮することにより、お好みであれば、精度を向上させることができます。次に、これらの補助ヒストグラムの解像度に分位数を絞り込むことができます。

これはあなたに余分なパスの費用がかかりますが、エラーは、代わりにK.K'のK、その後m.K'ヒストグラムのスペースを使用して、f.N/(K.K')に削減されます。

Answer 2

IFFあなたはあなたのデータは定義された分布（つまり、ランダムであると仮定することができます：順序であなたのデータの任意の非自明な割合を取ることは、全体のデータと同じ配分を「スケッチ」しようとしている、唯一の

1. は、いくつかのオーバーサンプリングされたヒストグラムでのデータの一部をお読みください。）粗い精度で、私は多くのオプションがあると想像しますこれに基づいて、のようにビンエッジの近似値を（あなたの質問で説明されているように）を選択し、これらのビンを一様にオーバーサンプリングし、新しいビンに新しいビンを読み込むなどです。十分なデータがある場合は、10％のチャンクで処理すると、10回の反復で1回のパスでビン構造が改善されます。

2. いくつかの（すべてではない）データを蓄積します。それらを見渡して、近隣の人が不都合に高い場合（精度/エラーが発生する可能性があります）、そのビンを2つに分け、ヒューリスティックに新しく作成したビンにヒューリスティックに古いビンを割り当てます。隣人の数に比例する）。最後に、ディストリビューションを並べ替えるための受け入れ可能なエラーによって何らかの形で制御されるディビジョンを持つべきです。

もちろん、上記はアプローチのアイデアだけであり、どの程度うまく動作するかについての保証はできません。