計算大數據的分位數

Question

我有大約300個文件，每個文件包含1000個時間序列實現（〜76 MB每個文件）。

我想從整個300000實現的每個時間步計算分位數（0.05,0.50,0.95）。

我無法將1個文件中的實現合併在一起，因爲它會變得太大。

這樣做的最有效方法是什麼？

通過運行模型生成的每個矩陣，但這裏是一個包含隨機數的樣本：

x <- matrix(rexp(10000000, rate=.1), nrow=1000) 

Answer 1

至少有三種選擇：

1. 你確定它必須是從全套？ 10％的樣本應該是一個非常非常好的近似值。
2. 300k個元素不是那麼大的一個向量，但是一個300k x 100 +列矩陣很大。將需要的列拖到內存中，而不是整個矩陣（如果需要，可以在每列中重複）。
3. 按順序進行，可能與一個較小的樣本結合起來，讓您開始在正確的場地。對於第五百分位數，您只需知道當前猜測上方有多少物品，以及下方有多少物品。所以像這樣：
   1. 採取1％的樣本，找到它的第5個百分點。在上下跳動一些容差，以確保第5個百分點位於該範圍內。
   2. 以塊爲單位讀取矩陣。對於每個塊，計數在範圍之上和範圍之下的觀測值的數量。然後保留在該範圍內的所有觀察值。
   3. 當你讀完最後一個塊時，你現在有三條信息（上面的計數，下面的計數，內部的觀察向量）。採取分位數的一種方法是對整個向量進行排序並找到第n個觀察值，並且可以用上述信息做到這一點：對範圍內的觀察值進行排序，並找到（n-count_below）th。

編輯：實施例（3）。

請注意，我不是一個冠軍算法設計師，有人幾乎可以肯定爲此設計了一個更好的算法。而且，這個實現並不是特別有效。如果速度對您來說很重要，請考慮Rcpp，或者爲此更加優化R。製作一堆列表然後從中提取數值並不是那麼聰明，但是這樣做很容易，所以我就使用它。

library(plyr) 

set.seed(1) 

# -- Configuration -- # 
desiredQuantile <- .25 

# -- Generate sample data -- # 

# Use some algorithm (sampling, iteration, or something else to come up with a range you're sure the true value lies within) 
guessedrange <- c(.2, .3) 
# Group the observations to correspond to the OP's files 
dat <- data.frame(group = rep(seq(100), each=100), value = runif(10000)) 

# -- Apply the algorithm -- # 

# Count the number above/below and return the values within the range, by group 
res <- dlply(dat, .(group), function(x, guessedrange) { 
    above <- x$value > guessedrange[2] 
    below <- x$value < guessedrange[1] 
    list(
    aboveCount = sum(above), 
    belowCount = sum(below), 
    withinValues = x$value[ !above & !below ] 
) 
}, guessedrange = guessedrange) 
# Exract the count of values below and the values within the range 
belowCount <- sum(sapply(res, function(x) x$belowCount)) 
belowCount 
withinValues <- do.call(c, sapply(res, function(x) x$withinValues)) 
str(withinValues) 
# Count up until we find the within value we want 
desiredQuantileCount <- floor(desiredQuantile * nrow(dat)) #! Should fix this so it averages when there's a tie 
sort(withinValues)[ desiredQuantileCount - belowCount + 1 ] 
# Compare to exact value 
quantile(dat$value, desiredQuantile) 

最後，這個值與確切的版本有些偏差。我懷疑我被一個或一些同樣愚蠢的解釋轉移了過來，但也許我錯過了一些基本的東西。