如何保持動態直方圖？

Question

是否有已知的算法+數據結構來維護動態直方圖？假設我有一個數據流（x_1，w_1），（x_2，w_2）...，其中x_t是雙精度的，表示一些測量變量，w_t是關聯的權重。

我可以做明顯的（僞Python代碼）：

x0,xN = 0, 10 
numbins = 100 
hist = [(x0 + i * delta , 0) for i in xrange(numbins)] 
def updateHistogram(x, w): 
    k = lookup(x, hist) #find the adequated bin where to put x 
    hist[k][1] += 1 

但我有一些問題，當我有一個連續的數據流。我手上沒有完整的數據集，我必須在數據收集之間檢查直方圖。而且我不知道期待：

• 理想的塊大小不有很多空箱的結束了，
• 的數據

的範圍所以我想定義動態垃圾箱。我可以做愚蠢的事情：

for x in data_stream: 
     data.append(x) 
     hist = make_histogram(data) 

，但我想這將很快得到減緩...

如果在那裏的東西等於一個我認爲是存儲在排序的數組數據的所有權重並以保持數組排序的方式插入新數據。這樣我可以有：

data = sortedarray(); 
for x in data_stream: 
    data.insert(x) 
    bins = [ data[int(i * data.size()/numbins)] for i in xrange(numbins)] 

並且每個bin內的計數將等於所有bin的data.size（）/ numbins。

我想不出一種包括權重在內的方法，但是......有沒有人有建議？ （關於這樣做的C++庫的知識也會受到歡迎）。

編輯：（爲澄清問）

的X_T是浮點數。要計算直方圖，我必須將連續範圍除以x所屬的多個分箱。所以我會有一系列的數字bin [0]，bin [1]等等...所以我必須確定我的bin [i] < x < bin [i + 1]。

當您事先獲得所有數據時，通常會這樣做直方圖。然後你會知道極限max（x）和min（x），並且很容易確定足夠的分箱。例如，您可以讓它們在min（x）和max（x）之間等距分佈。

如果您事先不知道範圍，則無法確定垃圾箱。你可能會收到一個不屬於任何垃圾箱的x。或者你可以有許多空箱子，因爲你選擇了太大的範圍來創建箱子。

Answer 1

如何確定箱

有在直方圖確定number of bins一些規則的數量。對於你的問題，我會去與斯科特的選擇：

bin_width = 3.5*sd*n^{-1/3} 

其中SD是標準差和ñ是數據點的數量。關鍵是，您可以使用online算法來計算標準偏差。倉的數量，ķ，由下式給出：

k = ceil((max(x) - min(x))/bin_width) 

寄存數據

假設我們已經觀察到N個數據點。然後標準差的置信區間爲

Lower limit: sd*sqrt((N-1)/CHIINV((alpha/2), N-1)) 
Upper limit: sd*sqrt((N-1)/CHIINV(1-(alpha/2), N-1)) 

其中CHIINV是來自卡方分佈的值。當N = 1000，對於SD的CI是：

(0.96*sd, 1.05*sd) 

等95％CI的Bin寬度：

(3.5*0.96*sd*1000^{-1/3}, 3.5*1.05*sd*1000^{-1/3}) 
(0.336*sd, 0.3675*sd) 

您可以獲得倉數目類似的東西。

算法

1. 存儲所有數據，直到你有一個很好的估計最佳濱寬，說時倉的數量的下限和上限CI是相等的。
2. 創建箱的數量並將數據放入箱中。
3. 將所有新數據點放入箱中，然後丟棄。

評論

1. 弗裏德曼-戴康尼斯的規則是選擇窗口的數量比較好，但它涉及的分位數之間的範圍是更有點棘手計算在線。
2. 從技術上講，當數據是連續的時，CI間隔不正確。但是，如果你設定一個合理的最小數量的數據點來觀察，例如〜100或1000，你應該沒問題。
3. 這假設數據都遵循相同的分佈。
4. 箱的數量取決於n^{ - 1/3}。如果您大致知道需要多少點，即10^5,10^6或10^7，那麼您可以創建更小的箱子，以期望在將來改變箱子寬度。

Answer 2

ROOT是粒子物理學家用於這類工作的工具......它帶有python綁定。請注意，它不是一個輕量級的軟件。

在C++中，你會做類似

TH1D hist("hist","longer title for hist",numbins,lowlimit,highimit); 

... 

for (int i=0; i<num; ++i){ 
    hist.Fill(x[i],w[i]); 
} 

... 

hist.Draw(); 

---

ROOT提供沒有內置在溶液中的合併的問題，輸入的分級範圍低於/高於被加入到欠壓/過流箱。

您可以在較寬的範圍內初始設置分檔並稍後轉換爲較短的分檔。我認爲這個方法是Rebin。所有明顯的限制都適用。

Answer 3

我有頻率表和直方圖的一些經驗。您只需要最小值和最大值來決定較好的紙箱寬度。所以在大數據的情況下，你已經知道可能的最小值和最大值。並且因此在數據流傳輸之前事先容易地計算箱寬度。

隨着部分數據進入，您只能根據每個倉區域更新必要的倉並顯示柱狀圖。

Answer 4

聽起來好像你想要實現下面的抽象數據類型。

insert(x, w): add item x to the collection with weight x 
select(p): return the item greater than a p weighted fraction of the items 

例如，select(0)返回最小，select(0.5)返回加權中值，和select(1)返回最大。

我會以兩種方式之一來實現這個ADT。如果選擇不頻繁，我會把數據放在一個數組中，並使用線性時間選擇算法，用於O（1）時間插入和O（n）時間選擇。如果選擇頻繁，我會使用二叉搜索樹，其中每個節點在其子樹中存儲總權重。例如，在

insert(2, 10) 
insert(1, 5) 
insert(3, 100) 
insert(4, 20) 

樹看起來像

2 (135) 
/\ 
/ \ 
1 (5) 4 (120) 
    /
    /
    3 (100) 

現在，找到加權中值，由0.5乘135並獲得67.5作爲期望的「指標」。從根2開始，我們發現5小於67.5，所以該項目不在左子樹中，並且我們減去5以獲得62.5，即索引到樹的其餘部分。由於135 - 120 = 15小於62.5，因此中位數不是2。我們從62.5減去15得到47.5並下降到4。在4處，我們發現100大於47.5，所以3是中位數。

假設平衡樹，insert和select的運行時間爲O(log n)。如果我從頭開始實施，我可能會選擇一個splay樹。