大數據集計數分位數的遞增方式

我們假設我們只能通過某些部分（即大矩陣的一行）獲取數據。要算上Q3位數一個需要得到數據的所有部分，並存儲在某個地方，然後對它進行排序並計算位數：

List<double> allData = new List<double>(); 
// This is only an example; the portions of data are not really rows of some matrix 
foreach(var row in matrix) 
{ 
    allData.AddRange(row); 
} 

allData.Sort(); 
double p = 0.75 * allData.Count; 
int idQ3 = (int)Math.Ceiling(p) - 1; 
double Q3 = allData[idQ3];

我想找到獲得位數的方式，而不存儲數據在一箇中間變量中。最好的解決方案是計算第一行的中間結果的一些參數，然後逐步調整它以用於下一行。

注：

這些數據集是真正的大（每行中的CA 5000元）
的Q3可以估算，它並沒有成爲一個精確值。
我稱之爲數據「行」的部分，但他們可以有不同的leghts！通常它變化不大（+/-幾百個樣本），但它有所不同！

這個問題類似於「On-line」 (iterator) algorithms for estimating statistical median, mode, skewness, kurtosis，但我需要計算分位數。

也有這個主題的幾篇文章，即：

之前試圖執行這些方法，我想知道是否有可能任何其他更快的方式計算0.25/0.75分位數？

來源

2010-05-14 Gacek

。很多文獻都是由數據庫研究激發的。 – Ron 2010-05-15 00:59:16

[檢查此主題]（http://stats.stackexchange.com/questions/7959/algorithm-to-dynamically-monitor-quantiles/70905） – Quartz 2014-09-10 09:21:29

受this answer的啓發我創建了一個估計分位數相當好的方法。它近似於我的目的。

這個想法如下：0.75分位數實際上是位於全球中位數以上的所有數值的中位數。 0.25分位數是全球中位數以下所有值的中位數。

所以，如果我們可以近似中位數，我們可以以類似的方式近似分位數。

double median = 0; 
double q1 = 0; 
double q3 = 0; 
double eta = 0.005; 

foreach(var value in listOfValues) // or stream, or any other large set of data... 
{ 
    median += eta * Math.Sign(p.Int - median); 
} 
// Second pass. We know the median, so we can count the quantiles. 
foreach(var value in listOfValues) 
{ 
    if(p.Int < median) 
     q1 += eta*Math.Sign(p.Int - q1); 
    else 
     q3 += eta*Math.Sign(p.Int - q3); 
}

備註：

如果您的數據的分佈是奇怪，你需要有以適應怪數據更大eta。但準確性會更差。
如果分佈很奇怪，但是您知道集合的總大小（即N），則可以通過以下方式調整eta參數：在開始時，設置eta幾乎等於某個大值（即0.2）。作爲循環的推移，降低eta值，以便當到達集合的幾乎結束時，eta將幾乎等於0（例如，在循環計算它這樣：eta = 0.2 - 0.2*(i/N);

來源

2010-05-25 14:45:37 Gacek

僅檢索您真正需要的數據 - 即無論使用哪個值作爲排序的關鍵，而不是與其相關的所有其他值。
您可能可以使用Tony Hoare的Select算法來比分類所有數據更快地查找分位數。

來源

2010-05-14 20:26:10

如果您的數據具有高斯分佈，則可以根據標準偏差估算分位數。我假設你的數據不是高斯分佈的，或者你只是在使用SD。

如果你能穿過你的數據的兩倍，我會做到以下幾點：

第一遍，計算最大值，最小值，SD和意思。
第二遍，將範圍[min，max]分爲若干桶（例如100）; （平均值2 * SD，平均值+ 2 * SD）（對於異常值使用額外的桶）。然後再次運行數據，將數字扔到這些桶中。
計數桶直到您的數據量爲25％和75％。如果您想獲得額外的花式，可以在存儲桶值之間進行插值。（也就是說，如果你需要一個桶的10％來達到你的第25個分位數，假設這個值是從低界到上界的10％。）

這應該會給你一個相當不錯的線性時間算法，對於大多數非完全不正當數據集合都可以正常工作。

來源

2010-05-14 21:18:11

我第二個使用桶的想法。不要把自己限制在100桶以內 - 最好還是使用100萬桶。棘手的部分是選擇你的桶範圍，以便一切都不會在一個桶中結束。估計桶範圍的最好方法是對數據進行合理的隨機抽樣，使用簡單的排序算法計算10％和90％分位數，然後生成相同大小的桶來填充該範圍。這並不完美，但如果你的數據不是來自超級怪異的發行版，它應該可以工作。

如果你不能做隨機抽樣，你會遇到更多麻煩。您可以根據預期的數據分佈選擇初始分段猜測，然後在處理數據時（如果任何分段（通常是第一個分段或最後一個分段））過滿，則從新的分段範圍重新開始。

來源

2010-05-15 00:01:41