2015/10/26

split-apply-combine strategy in R: R 的分進合擊

split-apply-combine SAC strategy 是 R 語言在處理大量資料的策略,有人直接翻譯成「拆開-套用-整合」,有人翻譯成「化整為零」,我有另一個更貼切的翻譯:「分進合擊」。

SAC strategy 是用來處理大數據的策略,當某一個類型原始資料的數量很多,有數萬、數十萬以上的資料筆數的時候,可以先將資料切割分塊 (split),然後套用 (apply) 運算在分塊的數據資料上,最後再合併 (combine) 運算結果,將結果全部一次回傳給使用者。

  1. "split" the original dataset
  2. "apply" the computation to each dataset
  3. "combine" the result into a new single dataset

聽起來跟先前比較熟悉的 Map-Reduce 很像,差別只在於 Map-Reduce 是用在大量機器的分工處理上,split-apply-combine 是用在單機的資料分析處理。

如果有用過 Mathemetica 這種數學軟體的人,就會知道先將資料存放到矩陣當中,再利用平行計算的方式,可以很快地就得到每一行或是每一列的總和。

一般用途的程式語言,要實作一個 excel 或 csv 二維矩陣資料的運算時,通常會直覺地以迴圈進行運算,然而這些迴圈在經過 compiler 編譯後得到的機器碼,我們回看到機器是循序地一個一個地取出資料,計算後儲存到暫存變數,然後再取出下一個資料進行運算,總終就能得到結果,計算第二行的總和只能等到第一行加總處理完成後,才會進行計算。

但最好的方式,是同時針對每一行的資料,同時做加總,最後同時得到結果,也就是將整個矩陣,split 成一行一行的單位,接著以行為單位,apply 加總運算,最終 combine 每一行的總和到新的 dataset。

雖然 R 語言也有支援一般語言的迴圈語法,但最重要的是,R 語言的 apply 相關函數。

以下是最基本,使用 apply 處理矩陣的行/列總和的範例:

# 產生 3x3 矩陣
> theMatrix <- matrix(1:9, nrow = 3)

# 每一橫排的總和
> apply(theMatrix, 1, sum)
[1] 12 15 18

# 每一直排的總和
> apply(theMatrix, 2, sum)
[1]  6 15 24

其他比較常用的是 lapply 與 sapply,跟 apply 的差別是 lapply, sapply 是用來處理 list。

# 產生 list,兩個元素:3x3 矩陣與向量
> theList <- list(A = matrix(1:9, nrow=3), B=1:5)
# 計算總和,並以 list 為回傳值
> lapply(theList, sum)
$A
[1] 45

$B
[1] 15

# 計算總和,以 vector 為回傳值
> sapply(theList, sum)
 A  B 
45 15

mapply 是將某個函數,同時套用在多個 list

# 產生 3 個 list
> list1 <- list( A = matrix(1:9, nrow=3), B = matrix(1:16,nrow=2), C=1:5)
> list2 <- list( A = matrix(1:9, nrow=3), B = matrix(1:16,nrow=8), C=15:1)
> list3 <- list( A = matrix(1:9, nrow=3), B = 15:1, C = 1:10 )

# 同時套用 sum
> mapply( sum, list1, list2, list3 )
  A   B   C 
135 392 190 

# 同時套用 identical 
> mapply( identical, list1, list2, list3 )
    A     B     C 
 TRUE FALSE FALSE

現在原生的 apply 相關函數,已經被 Hadley Wickham 提供的 plyr 套件取代了,Split-Apply-Combine2 提供了一個整理好的 table。

- array data frame list nothing
array aaply adaply alply a_ply
data frame daply ddply dlply d_ply
list laply ldply llply l_ply
n replicates raply rdply rlply r_ply
function arguments maply mdply mlply m_ply

所有的函數都是以 *ply 為結尾,前面兩個字母分別代表著資料結構,例如 ddply 就是輸入 data.frame 資料,運算後,取回 data.frame 資料,dlply 是輸入 data.frame,運算後,取回 list 資料,第二個字元如果是底線 _ ,代表沒有輸出的資料。

plyr 裡面包含了一份 1871 ~ 2007 年 1228 個 baseball batting 的資料,裡面只包含了超過 15 個球季的 MLB 球員資料,總共有 21,699 個 records。

> require(plyr)
> head(baseball)
           id year stint team lg  g  ab  r  h X2b X3b hr rbi sb cs bb so ibb hbp sh sf gidp
4   ansonca01 1871     1  RC1    25 120 29 39  11   3  0  16  6  2  2  1  NA   0 NA  0   NA
44  forceda01 1871     1  WS3    32 162 45 45   9   4  0  29  8  0  4  0  NA   0 NA  0   NA
68  mathebo01 1871     1  FW1    19  89 15 24   3   1  0  10  2  1  2  0  NA   0 NA  0   NA
99  startjo01 1871     1  NY2    33 161 35 58   5   1  1  34  4  2  3  0  NA   0 NA  0   NA
102 suttoez01 1871     1  CL1    29 128 35 45   3   7  3  23  3  1  1  0  NA   0 NA  0   NA
106 whitede01 1871     1  CL1    29 146 40 47   6   5  1  21  2  2  4  1  NA   0 NA  0   NA

以下的範例,利用 ddply 對 baseball 資料進行統計,我們可以算出全壘打數量最多的選手,是 Barry Bonds。

# 製作加總所有全壘打數量的函數
> calhr <- function(data) { c(TOTALHR = with(data, sum(hr))) }

# 利用 ddply,對每一個球員,進行 calhr 運算,計算結果會放到 TOTALHR
> totalhr <- ddply(baseball, .variable="id", .fun=calhr )

# 針對 TOTALHR 進行排序
> totalhr <- totalhr[ order(totalhr$TOTALHR, decreasing=TRUE), ]

# 列印生涯全壘打數量前十名的選手
> head(totalhr, 10)
            id TOTALHR
95   bondsba01     762
1    aaronha01     755
964   ruthba01     714
707   mayswi01     660
1045  sosasa01     609
424  griffke02     593
946  robinfr02     586
726  mcgwima01     583
590  killeha01     573
849  palmera01     569