大數據分析作業-Hadley Wickham論文翻譯：合併-分組應用-平滑：一種大數據可視化的框架

01-23

本文是@猴子老師系列課程第4講：複雜數據分析的課後作業之一，翻譯一篇Hadley Wickham大神的論文。關於第4講的內容還不太了解的同學可以看一下我前一篇文章，第4講：複雜數據處理和分析聽課及實踐筆記 - 知乎專欄。在這一講裡面正好用了航班延誤的數據，我選的這篇文章也恰好與航班延誤數據有關，不同的是數據量更大，而且需要對大數據進行可視化處理，作者在這篇文章當中提出了一種大數據可視化的框架，下面就看看文章怎麼寫。

本人水平有限，翻譯難免有紕漏，有不清楚或者不明白的可以留言討論，或者直接看原文：

Bin-summarise-smooth: A framework for visualising large data by Hadley Wickham

引子

圖. 1. 7600萬條航班信息中平均延誤時間（底下彩條，分鐘）隨飛行里程（x軸，英里）和飛行速度（y軸，英里/小時）的變化圖

左邊的原圖需要一些技術處理才能夠展示有用的信息：首先，我們僅關注中間99.5%的數據（中圖），然後減小延誤時間異常高的數據的影響並專註於一些典型值（有圖）。不難發現，平均飛行速度以上的航班（右上）通常延誤時間更短（紅色）。更有趣的是，短途且飛行速度較低的部分航班（左下）延誤時間非常接近於0（白色）。

摘要——

在感知和計算兩方面，大數據可視化都非常有挑戰性。一方面，需要展示哪一部分數據非常困難，另一方面，當你知道想要展示什麼，如何高效地進行展示又是一個難題。本文提出一個排除這兩個難題的框架，基於以下四個步驟：分組（bin）、應用組合（summarise）、平滑和可視化。前面兩個步驟可以將原數據高效（O(n)）簡化成適合展示的形式（假設一塊屏幕上有3百萬個像素）。平滑對前面兩步處理過的數據進行分析，由於它處理的數據集是簡化過的，因此能夠使用一些依然消耗較多計算資源但在統計學上更為有效的演算法。本文隨附一個在單核以及內存內計算系統上的參考實現，在分散式以及內存外計算系統上也很容易進行擴展移植。

關鍵詞：大數據，統計圖形，核平滑

1 介紹

隨著數據增長的加速，我們對它進行可視化的能力同步增長尤為重要。本文給出了一個全新的以可計算且統計有效為設計目標、同時處理大數據要展示什麼以及如何快速展示以滿足人機交互需求這兩大挑戰的大數據可視化框架。完成本工作的靈感非常簡單：大數據可視化的瓶頸在於屏幕的像素數。最多我們有300萬像素可用，1d 概要圖僅需要約3000像素。比像素顯示更多數據沒有意義，預期依靠渲染引擎去智能的減少數據，不如在一些成熟的統計原則的基礎上開發一些概要圖。

我在R語言方面的工作提供了不少能夠指導本文寫作的一些約束條件。隨附的參考實現基於由經驗豐富的分析師與其它數據操作工具和統計模型結合使用的目的設計的。我的目標是讓用戶能夠在常規的硬體上在5秒之內繪製1億個觀測。1億個雙精度數據大約需要800Mb不到的空間，因此20個向量可以存儲在16Gb的內存內，且大約有1Gb剩餘。5秒遠遠高於直接操縱的閾值，但與其他數據處理和建模功能在R中所佔的時間一致。如果超過5秒太多，將導致人們放棄等待並切換到其它工作上去，導致打破工作流程和減少工作效率。進一步進行比較並校核，在R語言中繪製一個常規含20萬個點的散點圖大約需要5秒，所以我的目標是比現有的工作也快幾個數量級。

本框架包含四個步驟：分組（binning）、應用組合（summarising）、平滑和可視化。分組和應用組合將原數據簡化成與屏幕的像素數相同數量級的概要。為了計算高效，分組和應用組合在統計方面做一些犧牲，不過可以在平滑階段得到補償。通常，平滑在計算上更為困難，但是精簡數據更快，並且損失很少的統計細節。分組-應用組合-平滑框架包含最重要的1d和2d統計圖形：直方圖、頻率圖以及核密度估計（kdes）等1d圖形；散點圖、平滑散點圖以及箱圖等2d圖形。對於其他概要的新圖形也非常容易擴展。

第3部分具體討論分組和應用組合，重點關注可計算性和統計影響之間的平衡。從可計算的角度，我們想要線性複雜度（O(n)）和並行計算的能力，但從統計的角度，我們希望簡化後的概要數據集能夠不受異常值的影響和破壞。第4部分討論平滑，更多關注統計方面，同時給出如何修補在前兩個步驟當中產生的一些統計問題。儘管我們已經將數據減小到可管控的量級，大數據的可視化依然存在一些特殊的挑戰。第5部分討論通常如何可視化簡化後的數據，以及如何克服在大數據當中時常出現異常值的問題。

本文隨附一個開源的參考實現，以R語言bigvis包的形式提供。bigvis包可以到 http://github.com/hadley/bigvis 獲取，在第6部分當中將有具體描述。參考實現基於內存內計算、連續數據的單核心概要併產生靜態圖形。但本框架對此沒有限制，我將在第7部分對後續工作的方向進行討論。

為了將本框架描述清楚，我將交通統計局提供的航班準點表現數據所產生的圖像為例。我採用2000年到2011年間所有國內航班表現數據，總計約7800萬條。完整的數據集共有111個變數，這裡僅對其中4個進行探索研究：飛行距離（英里），飛行時間（分鐘），平均速度（英里/小時）以及到達延誤時間（分鐘）。數據進行了適度的清理：時間為負的，飛行速度超過音速的以及飛行距離超過2724英里（美國大陸內最長飛行距離，SEA-MIA之間的航班）由缺失值代替。大約對180萬行的數據有影響，佔總數據量的2.4%。重現本文的數據和代碼和隨附的圖像可以到http://github.com/hadley/bigvis下載。

2 相關工作

從上世紀70年代開始就有大量關於核密度估計（kde，又稱平滑直方圖）、平滑、拉伸的統計研究。文獻 [43, 4, 35] 是相關工作非常好的總結。文獻 [21, 49, 16] 關注計算側，其中在上世紀90年代早期一些統計學家所完成的大量工作主要是將他們的演算法從大型機遷移到PC。本文的工作主要關注來自統計方面的挑戰（漸進分析），並且是在隨時間改變的大數據背景下構建的。

相關統計文獻表明，平滑處理對信息可視化（infovis = information visualization）的影響相對較小。文件 [32] 採用核密度估計，並提供一個非常快的基於GPU計算的實現，但是無法與現有的一些統計文獻建立起聯繫，這樣相當於浪費時間做了一些前人已經做得很好的工作。其它來自信息可視化的技術——比如拋雪球法[1, 57] （footprint splatting）以及用透明度來處理疊加 [26, 47] ——都可以用核密度問題來構建。

對於大數據還有一些其它方法：文獻 [22] 討論了一些通用的挑戰，並提出交互是一個通用的解決方案。其它建議採用一些變換 [29] 或者抽樣 [50, 3] 的手段。但是這兩種方法都各有缺點，變換會分界高數據密度，而低密度區域由於距離較遠，潛在不易察覺的重要關係會變得嚴重失真。抽樣可以非常高效，特別是採用不均勻的方法處理過量的異常值，但是如果想對結果有足夠的信心，你必須要麼查看不同的圖形或者非常小心的選擇調整參數。

文獻 [34] 描述了一個與本文極為類似的框架，通過互動網路圖形驅動大數據。這是合併-分組應用-平滑框架的補充：關注與在瀏覽器內採用高性能並行GPU計算和人機交互，但是除了計數並沒有對如何展示概要圖進行研究，也沒有就平滑步驟的重要性進行進一步的探索。

3 數據簡化

合併和分組應用這兩個步驟將原大數據簡化為更小的經過合併後的概要數據集。圖2給出了一些基於飛行里程變數的統計分組原則（里程數分組航班計數、各組飛行速度平均值、各組飛行速度標準差）。將所有的航班合併成237組，每組的里程區間為10英里，並對每組數據統計三個量：組內航班數，平均飛行速度，平均速度標準差。一般來說，這個過程包含兩個步驟，首先是將各個觀測數據分配到合適的組，如3.1部分所述；然後將每一個分組內的所有觀測結果減少到少量的簡要統計數據，如3.2部分所述。

圖. 2. 飛行里程以10英里為區間共分為273組，並對每組數據統計三個量：組內航班數，平均飛行速度，平均速度標準差。注意到Y軸上一些大幅度的變化以及一些極大里程的斷點是由缺失數據引起。

3.1 合併

合併是一種從實數到固定整數集的注入映射。我們採用固定區間進行合併，速度較快，而且非常容易的從1維推廣到n維，同時在統計學上也沒有任何證據表明可變的合併區間效果更好。

考慮到合併可以在可視化環境外部直接進行，因此可以被看做單獨的一個步驟。舉個例子，合併可以在資料庫中進行以減小一半數據傳輸的成本，因為雙精度數據需要8位位元組，而整形只需要4位位元組。

3.1.1 計算

固定區間合併由兩個變數決定，原點（寬度區間的下限位置的點）和寬度。計算比較簡單：

分組內數據從1開始，保留0索引給缺失數據和比原點小的數據。

3.1.2 n維的擴展

固定區間合併能夠比較容易的擴展到多維的情況。首先你對每一個維度進行合併，產生一個整數向量（ $x_{1} ,x_{2} ,...x_{n}$ ）。假設我們知道每一個維度的最大合併（組），我們就可以直接建立起這個向量與單個整數之間的雙映射。假如我們有m維，每一個可以取值0,1,... $n_{m}$ ,然後我們可以將整形向量通過以下公式轉化成單個整數：

當每一個維度只有10個合併（組）時，我們很容易看到它的工作原理。舉個例子，將1維（5,0,4）降到1維時，計算可得5+0*10+4*100=4+*（0+10*5）=405。同樣的，給我們一個整數，我們可以逆向得到原來的含m個整數的向量，只要對其不停得除以10便可。舉個例子，1維的356對應的3維是（6,5,3）。

本函數是單調最小完美哈希演算法，文獻 [2] 提到通過利用它的一些特殊屬性可以獲得一些高效哈希的變體。比如，由於哈希是完美的，我們可以取消通常在找到具有哈希值的候選者後的等式比較。即使沒有用到這種數據結構（在參考實現當中），採用標準數據結構會更加容易而且高效地在高維時對合併的數據進行分組應用，如果大部分的合併（組）中有數據則用向量，否則用哈希圖。

與n維度的數據打交道的主要調整來自我們的認知和想像力的匱乏，而不是計算複雜度。圖3給出了一個2維（飛行里程和飛行速度）的概要圖：儘管只是從1維到2維，也使得精確的表示合併（組）中的計數變得非常困難 [11]。

圖. 3. 飛行里程以10英里為區間共分為273組，並對每組數據統計三個量：組內航班數，平均飛行速度，平均速度標準差。注意到Y軸上一些大幅度的變化以及一些極大里程的斷點是由缺失數據引起。

3.1.3 統計限制

理想情況下，我們希望在數據點較少的地方有更大的區間，因為概要的誤差通常是 $Theta left(1/sqrt{n} ight)$ 。舉個例子，在圖2當中對於較大的飛行里程，由於本身大里程的航班計數較小，我們希望合併分組的區間更大，能夠包含更多的數據，使得平均值和標準差的變化幅度不超出我們預期太多。然後，文獻[46]表明極少有證據表明可變區間會趨向於更小的漸近誤差。可變區間能夠對潛在重要的數據能夠有一個精確的估算，但是優化問題更具挑戰性，任何潛在的改進都會被抹去。我們將在平滑這個步驟而不是在本步驟用可變區間等其他更加複雜的合併演算法解決這個問題。

3.2 分組應用

當n個原數據點被合併到整數m個組內以後（ $mll n$ ），下一步就是對各個分組內的數據進行匯總統計，用更少量的統計參數來代替原數據。選擇合適的統計參數需要在計算效率和統計魯棒性之間平衡。

3.2.1 計算效率

Gray et al.在文獻 [19] 當中提供了一種對統計參數非常有用的分類：

分布的 可以是中間儲存的單個計算元素，並且可以將各個分組的概要進行匯總。比如計數、總和、最小值和最大值。
代數的 可以是固定個數分布統計值的變換組合。比如平均值（計數+總和），標準差（計數+總和+平方和）以及其它更高階參數向偏度和峰態。
整體的 可以是隨著輸入增長的中間儲存數據。比如分位數（中位數），不重複數據的計數或者最常用數據。

代數和分布統計數據很重要，因為各個分組的結果可以很容易的重新組合起來。這有兩點好處：它使並行化變得很容易實現，並且支持一種分層的探索方法。例如，如果您有1億次觀測，則可以先將其合併成100,000個分組。那麼對於任何具體的1維圖像繪製，你可以重新設置或者分配已合併後的分組而不是原始數據。這種分層的方法在互動式可視化當中特別有用。在可視化之前預先完成這種精細合併，可以在具體互動式非常方便地對區間和繪圖區限進行修改。

通常對於整理的統計參數可以用代數方式進行估計。舉個例子，不重複數據的計數，可以用hyperloglog演算法 [18] 進行估算，中位數可以用Remedian演算法 [39]，其它的分位數有其它的各自方法 [17, 25, 33]。還有人提出了估算各種整體統計參數的通用方法 [8]。

平均值、標準差以及高階參數都可以通過單次計算得到，計算時間複雜度為O(n)，空間複雜度為O(1)。一些想當然的實現（比如用 $sum_{i}^{n}{x_{i}^{2} /n} -left( sum_{i}^{n}{x_{i}/n} ight) ^{2}$ 計算方差）需要注意，可能會引起嚴重的數值問題，文獻 [51] 提出了更好的演算法。中位數計算也需要複雜度為O(n)的計算時間（採用快速選擇演算法），但是空間複雜度為O(n)。不存儲至少一半的數據，並給出兩個分組的中位數，無法計算完整數據集的中位數。

3.2.2 統計魯棒性

在平均數和中位數之間有一個有趣的矛盾：對於異常數據中位數比起平均數有著更好的魯棒性，但是需要極大的計算空間。一個非常有用用來查看統計魯棒性的方法是容離值（Breakdown point）。一個統計參數的容離值是指外界想任意影響參數結果所需要控制觀測的比例。對於平均數來說，容離值是0：假如你可以影響1個數據，你就可以讓平均值成為任意你想要的數據。中位數的容離值是0.5：你想任意改變中位數之前必須控制50%以上的觀測數據才行。從計算的角度，平均值更合意，但是只要改變一個數據就可以任意控制統計結果，因此在統計的角度不是特別合意。這是一個普遍性的問題：越容易計算的統計參數通常魯棒性不足，而魯棒性足夠好的參數一般又都是整體性的。

即使你使用魯棒性統計參數，你只能預防受到分散異常值的影響，而不是數據與參數之間的完全不匹配。例如，如果數據有多種模式，那麼關於中心趨勢的單一度量，無論是平均值還是中位數都不會是一個很的統計參數。對比一下圖2和圖3：對於飛行里程較短的航班，對於給定的航程似乎有多個不同的飛行速度，此時平均值並不是一個很好的統計參數。可視化必須是可以迭代的，在你對一個統計參數沒有拋棄重要信息有足夠信心之前你不能隨意的將一個變數變換到一個單一的數字。在實踐當中，用戶可能需要針對自己的數據開發對應的統計參數，這裡這裡討論的應該就常規的應用提供一個好的開頭。

3.2.3 更高維度

沒有理要將我們限定在1維的情況。2維的一些參數比如相關性也非常有趣。所有從線性模型來的統計參數都可以用時間複雜度為O(n)，空間複雜度為O(1)的演算法進行計算 [37]，從而為更廣義概念的提出提供了富有成果的基礎。其它一些快速計算2維參數的演算法也非常有趣，比如scagnostics [55] 就是一個開始的好地方。

4 平滑

平滑是非常重要的一步，它旨在允許我們解決統計參數變化過大的問題。這種變化的產生可能是因為分組的尺寸太小，或者有異常值在分組當中。無論是哪一種方式，平滑都可以採用快速且低容離值的方法而不是緩慢但高統計魯棒性的方法。圖4給出了平滑處理後的圖2的結果：大部分小幅度的變化都被平滑消除了，讓我們能夠更容易地關注整體的趨勢。我們可以看出在1000-1500英里飛行距離範圍內的飛行速度的標準差最小，而且在飛行距離較小以及較大時標準差會升高。這在圖2將很難發現。

圖. 4. 與圖2相同的數據，用50的帶寬（bandwidth）進行平滑處理。去除了大部分不感興趣的變化並保留了主要的趨勢。

平滑有很多種方法，但我們採用一組基於核函數的方法，因為它們：

簡單且能夠快速計算
只有一個參數，控制平滑量的帶寬
對於合併處理過的數據同樣起作用 [49]
與其它更複雜的平滑基本等同 [44]
是其他眾多現有統計可視化方法的核心組成部分，比如核密度圖 [43]，平均平移直方圖 [41]以及局部加權回歸散點平滑法 [9]

理想情況下，我們應該對原數據進行平滑，但是對於大數據，這樣太過於消耗計算資源。對合併後並分組應用得到的統計量進行平滑處理可以得到圖形上與對原始數據進行平滑類似的結果，但卻只需很少的計算時間。

4.1 如何實現

圖5描述了從快速粗糙到緩慢細緻不同平滑方法的進展。最簡單的平滑方法（頂端）是合併分組平均，我們計算合併後每個分組的平均值。這個方法足夠簡單，但是平滑度不夠，呈現階躍的常數狀。下一種是移動平均（或最近點平均），我們在每一個點選取距離最近的五個點然後求取平均。這樣看起來有些進步，但是依然非常鋸齒狀。

剩下的三種類型採用一個簡單的主意：我們不僅要利用鄰近的數據，而且還有根據它們與當前數據點的距離分配不同的權重。在統計學上，通常將這種權重函數稱為核函數（Kernel (statistics)）。核函數各種各樣，但是鮮有證據表明具體哪一種形式的核函數更重要 [10]。高斯核函數比較常用，不過我採用三重核函數（triweight） $K(x) = left( 1-left| x ight|^{3} ight) ^{2} , I_{left| x ight| <1}$ ，因為它有界而且簡單（估算該函數比起高斯核函數速度要快10倍）。

圖. 5. 在人工產生數據上運用五種平滑方法的結果，其中隨機數據服從正太分布（ $sigma = 0.2$ ，異常值為Pi/2），並將隨機數代入sin(x)。從最簡單的合併平均平滑（頂端）到最精確的魯棒核函數回歸（低端），五種不同的平滑方法依次應用。為了便於比較，每個平滑顯示兩次，突出顯示為粗黑色線條表示為當前平滑方法的結果，細紅色線條為上一種平滑方法的結果，差別最小的是第四和第五兩種方法（核函數回歸和魯棒核函數回歸）上，兩條線基本吻合。

對於每一個被記為i的合併分組，我們有 $x_{i}$ 在其中心位置；以及 $y_{i}$ ，相應的統計參數； $w_{i}$ ，合併分組當中的觀測數。為了預測在j位置的平滑估值，我們首先計算每一個位置的核權重值 $k_{i} = Kleft( frac{x_{j}- x_{i} }{h} ight)$ 。參數h被稱為帶寬（bandwidth），並由它來控制平滑度：較大的h能夠包含更多的鄰近值從而產生更為平滑的曲線。由於三重核函數的形式，任何 $x_{j}$ 帶寬外（距離較遠）的觀測數據對最終的平滑值都沒有貢獻，如此提高計算效率。

當選定核函數之後，一般有三種核函數處理技術：核函數平均（aka Nadaraya-

Watston smoothing）、核函數回歸（aka local regression）、以及魯棒核函數回歸（aka LOWESS）。如果選擇需要在性能和質量上做一個權衡。雖然聯繫比較緊密，但是卻在不同時間並在統計學的不同領域發展而來，而且相關的術語也經常無法保持一致。文獻 [10] 提供了一個很好的發展歷程綜述。我們採用標準統計技術（平均、回歸或魯棒回歸）並結合權重 $w_{i} cdot k_{i}$ 應用到每一個樣本的位置以計算每一種平滑結果。核函數平均計算時間最短，但是在邊緣地帶由於只有單側有鄰近值，所以存在較大偏差。核函數回歸有效地採用一級泰勒估算克服了這個問題。如圖5所示，不難發現核函數平均和核函數回歸這兩種平滑方法結果除了在邊緣地帶略有不同，其他地方完全一致。高階近似可以用來擬合模型中高階多項式，但是在實踐當中額外的好處極為有限 [10]。

最後，魯棒核函數回歸迭代計算減小那些遠離曲線的異常值的權重，當然，這種迭代繼續會增加計算時間（通常迭代次數是固定的，所以它比起常規的回歸只是慢常數因子倍）。有非常多的方式可以實現魯棒回歸，文獻 [9] 所採用的方式比較簡單，從實踐的角度，計算操控性和性能都表現良好。從圖5可以看出魯棒平滑的關鍵優點：是唯一一個不受在Pi/2處異常低點影響的平滑方法。

4.2 性能和高維擴展

上述三種核函數技術都能夠很容易地擴展到高維的情況：比如，高維時，你可以計算一個n維的權重平均，而不是1維的權重平均。核函數平均因為本身就是一個卷積，所以特別容易高效地擴展到高維場景。由於卷積本身的關聯，可以用一系列的1維平滑來代替n維平滑。這是一個非常重要的優化手段，因為它將計算複雜度從O( $n^{d}$ )降到了O(nd)。在核函數回歸當中你也可以用一系列的1維回歸代替n維回歸，但是它當且僅當網格中的潛在數據不相關才奏效。魯棒核函數回歸不能採用這種方法，必須特別的準確計算。

考慮到核函數平均是一個卷積，自然而然地想到離散快速傅立葉變換（dFFT）是否可用。我的經驗表明在本文當中它並沒有什麼好處：它需要更複雜的代碼來處理dFFT周期特性；如果只對某個位置子集進行平滑預測它的靈活性也不夠；文獻 [49] 指出它僅在處理1維問題時有著微不足道的性能提升。

4.3 自動選擇帶寬

核函數平滑介紹了一個調整參數來控制平滑度：帶寬。有大量的研究關注如何選擇最佳帶寬，但是通常停留在如何減小積分均方誤差的階段，這與我們想要的可視化之間的關聯並不明顯 [12]。根據文獻 [36]，我採用一種實用的方法並用留一交叉驗證法（LOOCV）[14]向用戶提供一個起始點。在現實的數據分析場景中，將補充相關交互控制功能以讓用戶能夠探索找到不同層面的解決方案。

LOOCV背後的原理非常簡單：我們比較每個位置的實際統計值與未包含該位置的平滑預測值。觀測水平誤差用均方差來表示：

我們尋找能夠使得均方差最小的帶寬。我們可以在一些列可能的網格值當中直觀地搜索或者用標準的數值優化（比如 L-BFGS-B [7]）來找到極值。圖6給出了圖2當中三個變數的LOOCV均方差。它表明單獨依賴於數值優化帶來的挑戰：平均值和標準差有一些局部最小值，而計數非常平坦。

圖. 6.採用留一交叉驗證法估計的不同帶寬下計數、平均值以及標準差平滑後的的均方差曲線。為了更關注較低誤差的區域，均方差被限定在2以內。

採用有界的三重核函數（tricube），LOOCV可以直接用計算複雜度為O(mb)的演算法實現，其中b是核函數所包含的合併分組數（b $ll$ m）。文獻 [16] 建議累加演算法可以進一步減小計算時間。

4.4 可變帶寬

直觀的，如果選擇自適應的分組區間我們應該做的更好。有大量數據的地方或者潛在曲線特別彎曲的地方我們可以用更小的分組區間，相關文獻 [46, 6, 40, 24] 給出了大量方法。我們採用文獻 [15] 給出的最簡單但是性能可以可以記得方法：尋找一個帶寬h，然後將數據分成 $m/left( 10cdot logleft( m ight) ight)$ 份，為每一份數據分別估算最優帶寬，然後進行平滑計算。

圖7給出了文獻 [15] 提出的一個挑戰性函數的處理過程。它演示了這種方法的有效性：固定帶寬將在左側過平滑或右側欠平滑，而可變帶寬可以適應於在整個功能範圍內提供視覺上相當的平滑度。

圖. 7.（最左）文獻[15提供的一個挑戰性函數]用固定帶寬的平滑所得的合併分組平均值；（次左）採用單一最佳帶寬平滑或的平均值；（次右）10份單獨數據上的最優帶寬估計；（最右）在每個位置使用單獨的帶寬進行平滑後的數據。

5 可視化

一旦我們對原始數據完成了合併、分組應用和平滑處理，那就可以比較直接的進行可視化處理。當討論可視化時，對從原數據集合併而來的變數和分組應用產生的新變數進行區分非常有必要。為了講清楚，我們將約定如下：（n, m）-d 數據集或者可視化表示具有n個合併變數和m分組應用變數。例如：圖2表示3個（1,3）-d 圖形（飛行里程，計數+平均值+標準差），圖3表示1個（2,1）-d 圖形（飛行里程+飛行速度，計數），圖1是一個從一個（2,2）-d 數據集（飛行里程+飛行速度，計數+平均值）演化而來的（2,1）-d 圖形（飛行里程+飛行速度，平均延誤時間）。

通常，我們對m和n都是1或者以上時的圖形更加感興趣。（0,1）圖形僅僅顯示所有合併分組的統計參數的分布，而（m，0）圖形僅僅顯示哪些地方有合併分組過。（0，2）圖形可能有點趣味，因你可以就每一個合併分組的統計參數進行比較（比如你可能對高平均數且低標準差的合併分組感興趣），但是由於它並不能表示原始數據內容，我們對它不會對它再做進一步的挖掘。5.1部分討論（1,1）-d 圖形，5.2部分討論（2,1）-d 圖形。5.3部分討論將分組應用處理n維數據的通用組合方法。

隨著數據規模的增加，發現極端異常值的概率也隨之增加。就實踐而言，我發現像圖1這樣的大數據可視化，都有大量數據聚集到一個很小的區域的情況。我們有兩種手段來應對這樣的問題：在空間上剝離異常值，如5.3.1，和用顏色及其它美學方面的手段對異常值設置不同的模式，如5.3.2。

最後，保留缺失值也很重要，這不僅僅是大數據的問題，但在這裡依然值得一提。5.4部分討論了缺失值的重要性，以及到目前為止你所看到的圖形可能會誤導你的原因。

5.1 （1,1）-d 圖形

（1,1）-d 圖形非常簡單，可以用一條線來表示。如果統計參數是計數，將產生一個頻率多邊形 [42]。在傳統直方圖上有所改進，因為它很容易在一個圖形上覆蓋多個頻率多邊形，並同意顯示計數以及其它統計參數。

假如統計參數不是計數，我們也需要其它一些手段來校驗估計的不確定性。這很重要，因為我們沒有從數據支持薄弱的地方得到強有力的結論。我們已經看到圖2中的一個選項：在相鄰的圖形上顯示計數和其它統計參數。圖8給出了另外兩種選項，將計數或者相對誤差映射到線的顏色。用計數可以告訴我們哪裡存在大量的數據，但是對於校驗我們對不確定性的期望，誤差的測量更為重要。用相對誤差使得在所有的圖形當中使用一個通用的刻度變得可能，當誤差超過某一個閾值（這裡是10%）將融入到圖形背景當中。在這個例子當中，除了第一個線段，所有的相對誤差都小於0.3%。

圖. 8. 20英里為區間的合併分組的（1,1）-d圖形的平均飛行速度不確定性的兩種校驗方式。從上到下，每個位置的觀測數，絕對誤差，或相對誤差。

誤差估計方法可以系通過漸近估計，像中心極值定理，或者bootstrap法 [14]。例如，根據中心極值定理，平均值的標準差是 $sigma /sqrt{n}$ ,而且這個估算對於任何n相對較大的分布都可以取得比較好的效果（通常n需要大於30）。其它統計參數的標準差通常比較難推導出來，不過通過bootstrap法能夠比較容易取得估算值。bootstrap法的缺點就是需要多次的通過數據，每一次隨機的選擇一個不同的隨機子集（bootstrap就是《R語言實戰》第三部分第十二章-重抽樣與自助法學習筆記中的自助法）。

5.2 （2,1）-d 圖形

（2,1）-d 圖形類似於圖1，通常還有另外一個名字叫做熱圖 [56] (雖然這個名字有時會被保留用作分類數據的圖形)或者瓦片圖。其它替代圖形有輪廓圖（尤其是平滑數據），或者其它顯示面的繪圖手段 [30]。

在2維圖當中校驗不確定性更有挑戰性。圖9給出了兩種與圖1當中估計值相關的誤差展示方式。頂上的圖形展示一個相對誤差的瓦片圖，並覆蓋有平滑的輪廓線。底下這幅圖將透明度映射到相對誤差，因此誤差較高的區域將難以看見。沒有一種方法是完美的，單獨的一張相對誤差的瓦片圖難以與其它統計參數進行整合；由於潛在的面非常不平滑而且有一些異常值鑲嵌其中，因此如果將這些輪廓線覆蓋到瓦片圖上也極具挑戰性；而使用透明度只能定性的而不能定量地表示不確定性。更好的需要交互的方法將在以下的內容中討論。

圖. 9. 展示圖1所示關於飛行速度，飛行里程以及平均延誤的（2,1）-d 圖形不確定性的三種方式。頂圖是一個瓦片圖疊加平滑的輪廓線表示相對誤差。底圖是將相對誤差映射到透明度。

5.3 （n, m）-d 圖形

將這些圖形擴展到高緯度的工作非常有挑戰性，但是存在兩種的突破途徑：小的倍數和交互。

小的倍數（aka 刻面）可以通過高維數據集展示低維度數據片段。產品圖 [54] 框架深入探討了分類數據的統計參數。因為合併分組過的變數可以以同樣的方式被視為分類變數，因此這種方法可以很容易的擴展到連續變數。這裡有兩個附加的約束：瓦片圖（樹圖）將不再適用，因為它們不保留排序，為了確保有足夠的空間展示在結構中層次較低的變數，初始變數的合併分組區間需要比較粗略。

另外一種替代的方法就是採用交互。選擇聯動提供了一個鏈接多個低維度圖形以獲得多維度展示的有效方式 [34, 45]。同時，這樣可以減少計算數據統計參數時的負擔 [22]。

5.3.1 剝離

處理空間異常值的最好方法就是將計數最少的合併分組直接刪除。我將這種方法為剝離，並通過逐漸刪除數據凸包上的最小計數來實現。圖1給出了這種技術的具體應用：剝離很小一部分的數據（0.5%）可以得到實質提高的圖形。小量數據的剝離（常常小於1%）可以提到大部分的2維圖形，將重點放在大部分數據上。對於其它非計數類的統計參數，在減少異常值方面也有額外的好處。

與其簡單的將異常值拋棄，最好還是將普通值和異常值分別進行分析。通常異常值都非常有趣！

5.3.2 模數變換

刪除計數較小的合併分組有時候會刪除統計概要維度當中最偏僻的值，但是通常很多離群值還是會保留下來。如果有一個靈活的技術能夠降低異常值對可視化的權重影響將更有用，而不用將他們全部都刪除。我建議採用文獻 [27] 提到的模式轉換，提供了一種可以縮小或者延長一個分布的尾部。圖1顯示了為了避免異常值所導致的顏色縮放而進行適度轉換的重要性。

模數變換歸納了文獻 [5] 提到的Box-Cox變換來處理正負數據：

$lambda$ 控制轉換的強度，當 $lambda = 0$ 的時候轉換強度最大。

當與交互性相結合的時候模數變換顯得特別有用，因為它允許用戶動態地關注某一分布的重要部分。這提供了一個強制包含某些值的離散尺度的平滑替代 [28]。

5.4 缺失值

一個重要的設計原則是在缺失值應該保留，除非用戶干預：從原始數據到最終可視化的整個過程中應該一直保留。有時候可以刪除它們，但是這個決定需要小心謹慎地分析後作出：你決不能夠悄無聲息地丟棄數據來進行可視化。這是MANET [48] 的一個重要原則，這對於無論是在原始數據中還是在數據清理期間引入的往往存在缺失值的實際數據，是至關重要的。這個原則實施起來非常簡單，但是必須通過框架內的其它組件實施：在合併、分組應用以及平滑階段都應該保留缺失值。

圖. 10. 是否保留缺失飛行里程數據對飛行速度分布的影響。

也就是說，本文中沒有一張圖形實際保留了缺失值。圖10證明了為什麼這是一個壞主意：是否保留缺失的飛行里程數據對速度分布影響很大。飛行里程數據顯然不會隨機丟失，所以無視丟失數據會導致有偏差的結論。

6 bigvis 包

bigvis包給出了本文所論述框架的開源R包實現，可以從http://github.com/hadley/bigvis下載。bigvis包主要包含兩部分：用C++寫的包含關鍵演算法的高性能實現部分，以及一個用R寫的支持探索性數據分析、用戶用好的封裝。連接這兩部分的是Rcpp包 [13]，該包提供了用整潔的C++ API來訪問R的內部數據結構的簡單方法。

C++模塊採用模板函數來避免虛擬方法查找的成本（本身比較小，但是累加會有上億次的調用）。因為模板函數專註於編譯時，而R的代碼需要在運行時動態地調用它們，所以在連接R與C++是會增加一些額外的挑戰。為了解決這個問題，一個小型代碼生成器產生了所有模板函數的特別版本。在某種程度上，這是偶然的，但在編譯連接不用語義的語言時又是不可避免的。

bigvis包中的API是為了讓R語言用戶熟悉大數據可視化而設計的。它實現了autoplot通用函數的方法，提供了基於上述原則的默認可視化方法，而且與R現有的繪圖工具比如ggplot2有著清晰的介面 [52, 53]。當默認圖形工具功能不夠的時候，這樣可以輕鬆基於簡化和平滑的數據上構建自定義圖形。本文中的所有圖形都是用ggplot2繪製的，而且將清晰度自定義為最大。

6.1 基準

圖11提供了bigvis包基於不同數據規模、合併分組數目以及不同的統計參數耗費時間的基本基準。耗時基於15寸Macbook retina屏幕的高配版本：2.6Ghz Intel Core i7的cpu，16Gb內存和固態硬碟。該基準同時假設數據已經在內存當中了：對於以R的二進位文件保留的1億個觀測數據，從磁碟系列化載入大約需要2秒鐘。

圖. 11. 採用bigvis包時，不同數據規模（顏色），不用合併分組數（x軸）以及不同統計參數（形狀和線型）的耗費時間基準。x軸和y軸都有記錄。

計算時間隨著數據規模呈線性增長，隨著合併分組數緩慢增長（只顯示每個合併分組中有10個以上觀測數據的結果）。不同統計參數比如計數、標準差和平均值之間的變化相對較小。三個參數的計算時間複雜度都為O(n)，但是標準差本身的計算比平均值高一個數量級，中位數是最慢的，因為它需要附加一個完整的數據拷貝過程。

這些時間是潛在表現的下限，後續會有更好的表現：在用C++編程還不到6個月的時間，在C++方面絕對不是專家，只是使用了一些C++的高級功能，後續可能有更多的優化機會。

7 未來工作展望

合併-分組應用-平滑框架提供了一個大數據可視化靈活的工具包，圍繞屏幕上像素數的瓶頸進行設計。在不犧牲底層數據保真度的前提下，通過平衡計算性能和統計魯棒性，創造了一個可以隨著數據規模而輕鬆擴展的框架。

參考實現是基於單核和內存內計算，並行化和內存外數據存儲是未來的工作領域。我們希望簡單的預合併並提取統計參數能夠在現有的資料庫當中進行，分組演算法在SQL中實現，其實目前大多數資料庫以及提供了簡單統計功能，比如求平均值。其它系統，比如madlibs [23]，可以提供更豐富的統計參數計算功能，讓分組應用再組合的技術在資料庫當中變得更有吸引力。列存儲資料庫 [31] 與統計數據自然匹配，並且更可能在後端提供高效地內存外存儲。多核和GPU實現能夠提供令人振奮的途徑將這個框架擴展到處理10億及以上數據點的數據。

本文重點關注連續數據，但是本身可以直接擴展到含有相對較少值得分類變數。這些變數可以簡單地映射到整數，但是平滑處理通常是不合適的。挑戰通常在可視化階段出現，並需要一些序列 [20] 來繪製重要的模式。另外一個挑戰是當類別數隨著數據規模增大而增大的時候，當類別數超過像素數的時候，你要放棄哪些類別呢？

最終，請注意，可視化只是數據分析難題的一部分：大數據的變換以及建模依然需要其它工具。可視化是提煉和總結問題非常好的手段，但是不能夠很好的擴展：一個人需要看每一個圖形。統計模型和其它演算法能夠很好的擴展，但是從來不會透露你根本沒有想到的。因此，用於可視化的工具必須與用於建模的工具相連接，配合使用，相關從業人員需要博採眾長，優勢互補，利用好兩種工具的優點。這也是我在R領域工作的一個原因。從業人員可以將獨立的可視化工具、建模工具以及操作工具解決實際問題。

致謝

最後我想感謝進行初步編碼的Hu Yue，以及幫助我學習C++的JJ Allaire, Dirk Eddelbuettel, Romain Francois and Carlos Scheidegger，他們回答了我很多愚蠢的問題。本工作的早期版本由Revolution Analytics和Google贊助，在此一併感謝！

參考文獻

略，請大家查閱原文。

再次給出原文鏈接：

Bin-summarise-smooth: A framework for visualising large data by Hadley Wickham

譯後小計：

最後，感謝大家耐心閱讀到這裡，斷斷續續一共大概花了十幾個小時的時間完成翻譯，期間google翻譯和百度翻譯都提供了很大的幫助，不過本人無論是英語還是中文的表達，都還有很多需要提高的地方，若有錯誤或者不對的地方請大家留言指出來，或者直接查看原文。

翻譯的過程也是深刻理解原文的過程，雖然對數據分析特別是大數據分析還只是輕輕推開了門，不過我已經鼓足勇氣再用點將門推得更大一點，讓我將裡面的精彩世界看得更清楚一些些。同時我也準備著邁開腿，小步快跑地踏入這個世界，相信有各位的陪伴，大家會走得更遠！

最樸素的願望是：希望本文對各位有用。