直播數據的直方圖近似

Question

此問題是answered here的稍微延伸。我正在重新實現在this paper的第2.1節中找到的直方圖近似的一個版本，並且我想在再次開始此過程之前將所有的鴨子都連成一排。上次我使用boost::multi_index，但是性能並不是最好的，我想避免在桶的數量上插入對數/發現std::set的複雜性。由於我使用的直方圖的數量（隨機森林中隨機樹的每個葉節點的每個特徵每個特徵一個），計算複雜性必須儘可能接近常數。

用於實現直方圖的標準技術涉及將輸入實際值映射到箱號。爲此，一種方法是：

1. 初始化大小爲N的標準C數組，其中N =箱的數量;和
2. 將輸入值（實數）乘以某個因子並將結果發送到底以獲得C數組中的索引。

這適用於具有均勻分檔大小的直方圖，效率很高。然而，上述鏈接文件的第2.1節提供了一個沒有統一的容器大小的直方圖算法。

另一個問題是，簡單地將輸入實數值乘以一個因子，並將結果乘積作爲索引失敗，結果爲負數。爲了解決這個問題，我考慮在數組中的某個地方標識一個'0'。這個bin將會以0.0爲中心;在它之上/之下的箱可以使用剛剛解釋的相同的乘法和底板方法來計算，其中稍微修改的是將地板產品添加到兩個或根據需要從兩個中減去。

這就引發了合併的問題：本文中的算法將兩個最接近的二進制數據庫合併，如從中心到中心所測量的那樣。實際上，這會產生一個「鋸齒狀」的直方圖近似值，因爲一些箱子會有非常大的數量，而其他箱子則不會。當然，這是由於非均勻大小的分箱，並且不會導致任何精度損失。但是，如果我們試圖規範不均勻大小的箱子來製造制服，會發生精度損失。這是因爲假定m/2個樣本落在箱中心的左側和右側，其中m =箱數。我們可以將每個垃圾桶建模爲高斯，但這仍然會導致精度損失（儘管最小）

所以這就是我現在卡住的地方，導致這個主要問題：實施的最佳方式是什麼接收流式數據並將每個樣本存儲在統一大小的分箱中的直方圖？

Answer 1

保留四個變量。

int N; // assume for simplicity that N is even 
int count[N]; 
double lower_bound; 
double bin_size; 

當一個新的樣本x到來時，計算double i = floor(x - lower_bound)/bin_size。如果i >= 0 && i < N，則增量count[i]。如果i >= N，則反覆加倍bin_size，直到x - lower_bound < N * bin_size。在每次翻倍時，調整計數（通過利用稀疏進行多次倍增來優化）。

for (int j = 0; j < N/2; j++) count[j] = count[2 * j] + count[2 * j + 1]; 
for (int j = N/2; j < N; j++) count[j] = 0; 

的情況下i < 0是棘手的，因爲我們需要減少lower_bound以及增加bin_size（再次，優化稀疏或一步到位調整數）。

while (lower_bound > x) { 
    lower_bound -= N * bin_size; 
    bin_size += bin_size; 
    for (int j = N - 1; j > N/2 - 1; j--) count[j] = count[2 * j - N] + count[2 * j - N + 1]; 
    for (int j = 0; j < N/2; j++) count[j] = 0; 
} 

例外情況很貴，但在數據範圍內僅在初始bin大小範圍內發生對數次數。

如果實施該浮點，當心，浮點數並不是實數，並且像lower_bound -= N * bin_size語句可能無法正常運作（在這種情況下，如果N * bin_size比lower_bound小得多）。我建議bin_size在任何時候都是基數的權力（通常是兩個）。