T-Digest 概念簡介

百分位數是敘述性統計中一個很好用的工具,像是

但是因為計算相對複雜,在資料量過大時往往無法計算, T-Digest 是一個近似大量資料中百分位數的演算法,這篇文章簡單介紹其想法。

Concepts

假設我們今天有很多數字,舉例來說這邊有 500 個 -30 ~ 30 間的數字

這種圖稱為 Rug plot, 其中的每一條直線代表一個數字,其 x 軸是它的值。

我們可以用 Probabilistic Density Function(PDF) 的形式來表示:

機率密度函數,\(PDF(x)\) 越高表示 \(x\) 發生的機率越高,其面積加總起來是 100%

75 百分位數就是面積佔 75% 時的 x 座標:

Centroid

但是這樣要知道 500 個數字的順序才能計算,這在數字非常多的時候是不容易的。取而代之的是,試著將用很少的數字來代替 500個數字,怎麼做呢?

將鄰近的數字們用兩個數字代表: 平均值跟個數 原始的論文中是用總和,但是兩者意義相同,實作上為了效率都會選用平均值。

這樣的一組平均值跟個數被稱為 Centroid ,我們可以用好幾個 centroid 來代替整個 PDF, T-Digest 就是在做這件事

當然可以自由決定要用幾個 centroid 來代表

計算百分位數時就是只需要從這些 centroids 中找出對應位置的項目來做內插法。

Clustering

將很多數字用一個或多個 centroids 代表的動作稱為 clustering. 我們知道當一個 centroid 代表的數字越多,流失的資訊也就越多,也就越不精確,因此怎麼 clustering 就是影響成效的一個重點

T-Digest 的作法是控制各個 centroid 的大小,在需要精確的部份用更多 centroids 來表達。為此論文提出了一個公式 k(q, δ) 的函數圖形

來定義這個行為:

\[k(q, δ) = δ\left(\frac{sin^{-1}(2q - 1)}{π} + \frac{1}{2}\right)\]

其中 \(q\) 是 quantile, \(δ\) 是壓縮率參數,而 \(k(q, δ)\) 表示 \(q\) 應該要用第幾個 centroid 表達。可以從圖中看到在靠近 \(q = 0\)\(q = 1\) 的時候,\(k\) 的變動很大,也就是說我們用比較多的 centroids 來表示。 為什麼這樣設計呢?

這是因為大部分計算百分位數時,真正關心的通常是 1、0.1、99、99.9、99.99…等很極端的百分位數,相較之下中間部份不那麼在意其精確程度了。

Merge and the rest …

除了透過 clustering 建構 T-Digest 之外,論文中也給了合併兩個 T-Digest 的方法。這帶來了一個很大的好處:當資料點太多時,我們可以分組計算 T-Digest 然後在合併起來,這讓平行分散計算變得可能很重要的一點是 T-Digest 的 merge 需要滿足結合律才能安全的用在平行分散的系統上。但很可惜的是, T-Digest 是近似演算法,所以沒有真正的滿足結合律。雖然如此,仍然可以在一定的誤差之下滿足這些條件,也使得實務上還是可行。

,也就是 Divide and Conquer.

論文中剩下的部份除了討論成效之外,還給出了幾個實用的演算法:

  • Trimmed Mean, 一個 quantile range 之間的平均值
  • Cumulative Density Function(CDF)
  • Inverse CDF

Reference