一塊紅布

人民力量拉一塊布,建制派接招,也拉來了一塊布。那塊布是紅色的,封閉了我們的雙眼。
封閉了雙眼,人們竟看到幸福,感到舒服,一切現實中的痛苦都忘記了。
蒙著雙眼的人們,被問到你想怎樣,人們答不如由別人作主吧。

中文 text processing #1

原來的 title 是「文字處理」,但是那會和 Word processing 混淆,故此用了如此的奇怪的 term 。
分析中文文本,對比英文是有非常大的分別。英文的分析我認為是相對較易,而且理論也基本上是以英文分析最為完備。

參考以下英文及中文句子:

Our introduction to the R environment did not mention statistics, yet many people use R as a statistics system. We prefer to think of it of an environment within which many classical and modern statistical techniques have been implemented. A few of these are built into the base R environment, but many are supplied as packages.

我們對 R 環境的介紹中沒有提到統計,但是大多數人用 R 就是因為它的統計功能。不過,我們寧可把 R 當作一個內部實現了許多經典的時髦的統計技術的環境。部分的統計功能是整合在 R 環境的底層,但是大多數功能則以「包」的形式提供。

英文用空格或標點符號等等 delimiter 將詞1 隔開。故此要計算每個關鍵詞的頻率,電腦處理會較易。但是中文的情況,詞並不是用 delimiter 隔開,我們用人腦會知道「我們對 R 環境的介紹中沒有提到統計」是可以分成「我們、對、R、環境、的、介紹、中、沒有、提到、統計」,但是電腦處理會有困難。
電腦分詞是自然語言處理2 的第一步。就這個問題,曾經詢問過朋友。友人 Clement T 先生想出了類似英語 N-gram 的方法。例如第一句:「我們對 R 環境的介紹中沒有提到統計」頭幾個字是可以分成:


我們
我們對
我們對 R
我們對 R 環
我們對 R 環境 ….

「我」這個詞,在文中出現兩次。「我們」這個詞,在文中也出現兩次。但是「我們對」之後的,只出現過一次。故此,我們有理由相信「我」或「我們」是常用的詞,而「我們」較「我」長,貪婪地是應選「我們」,故此「我們對 R 環境的介紹中沒有提到統計」中的頭兩個字應該可以獨立成詞。
這個方法經過查書之後,知道名為 forward greedy matching 。事實上,市面有不同的方法進行中文分詞處理,這個 stackoverflow 問題列出不少相關的方案。
基於歷史原因,最近我在工作上使用的是據聞由雅虎研製的 nlpbamboo 。但是長遠來說,我想轉用 Stanford Word Segmenter3 據聞中科院研製的 ICTCLAS 也不錯,但可惜並非完全 opensource 。
下集再講講實際操作時所面對的問題,以及 R 整合方法。

  1. 我想用的字眼是 Token ,但中文不知如何譯。 []
  2. 我並不想用簡寫 NLP ,怕會被人以為我是張慧慈那些大茶飯人士的朋友。 []
  3. 我想這是我對 Stanford 大學的單戀。 []

Higher-order functions in functional programming languages in R

R 有個 function 叫 paste() 。

paste(“The current date and time is”, Sys.time(), “and you current working directory is”, getwd(), “. Mr Stark.”)

Output 是

“The current date and time is 2012-05-18 13:05:39 and you current working directory is /home/chainsaw/Stat . Mr Stark.”

基本上就是將一大堆的 String 串成一個大 String 。此 paste() 為我常用的功能之一。
但是,此 paste function 有一個問題。例如我想將存有 1-4 string 的 vector 串成 “1 2 3 4″ ,如下 code :

paste(as.character(1:4))

出來的結果仍是 vector ,不是如我所預料那樣。解決方法是用 Higher-order function Reduce() ,如此:

Reduce(paste, as.character(1:4))

此 Reduce 是將 paste 變成這樣:

paste(paste(paste(1,2),3),4)

此類的 function 還有 Map, Filter, Find, Position 和 Negate 。最近工作上要常常用到如此 function 去除去 for loop 。

《大豐收》推出及其他

圖片來自 CUP Facebook

最近太多事忙,沒理由人生首次出書都不在網誌寫兩個字。1
拙作其實已經推出幾天,兩星期前我已收到一本作者書。多位好友到大書店(三聯商務)找本書卻仍未進貨。根據線報暫時城邦書店是有的。
拙作成書精美,我相當滿意,這全為 CUP 出版社編輯、設計、校對團隊的功勞。之前的大妄想,基本上是達成了。
小弟不才,除了拙作文筆青澀稚嫰,還有就是多次修稿後仍留有大量錯別字。小弟會在本文編集勘誤表,以供參考。
如果你喜歡、討厭,又或者又不喜歡又不討厭拙作,也請您留個言。您的意見將推動我的前進。

—–
勘誤表

  1. P 178 第三及四行的「吳儒明」應為「伍儒明」。
  2. P 185 第五行的「周求暉」應為「周永暉」。
  1. 沒有寫在 blog 的東西日後很快會忘記,這個 blog 已變成我腦袋的 external harddisk 。 []

Vectorization of lookup tasks in R

A task that come up regularly during data munging is like this: you have a list of user ID (uid). Then, you have another table that has the user ID(lookup.uid) and the value of interest(lookup.value). You would like to fetch the list of value (lookup.value) with the uid = lookup.uid and retaining the order of uid.
I don’t know the terminology for this task. I usually call it “lookup”.
Programmatically, lookup can be done with a simple for-loop to loop through the uid and match the uid with the lookup.uid one by one. In R, the following is the usual pattern for this for-loop.

1
2
3
4
5
6
7
8
#< -
forlooplookup <- function(uid, lookup) {
  uid.value <- rep(NA, length(uid))
  for (i in 1:length(uid)) {
    uid.value[uid == lookup[i,1]] <- lookup[i,2]
  }
  return(uid.value)
}
#< -
forlooplookup <- function(uid, lookup) {
  uid.value <- rep(NA, length(uid))
  for (i in 1:length(uid)) {
    uid.value[uid == lookup[i,1]] <- lookup[i,2]
  }
  return(uid.value)
}

However, for loop is slow. The whole point of R programming is vectorization1 . The above for-loop can be rewritten using the vectorized match() function.

1
2
3
vectorlookup <- function(uid, lookup) {
  return(lookup[match(uid, lookup[,1]),2])
}
vectorlookup <- function(uid, lookup) {
  return(lookup[match(uid, lookup[,1]),2])
}

Let’s benchmark the for-loop version and vectorized version of lookup.

1
2
3
4
lookup <- data.frame(ID=1:30000, value=rnorm(30000))
uid <- sample(1:30000)
system.time(forlooplookup(uid, lookup))
system.time(vectorlookup(uid, lookup))
lookup <- data.frame(ID=1:30000, value=rnorm(30000))
uid <- sample(1:30000)
system.time(forlooplookup(uid, lookup))
system.time(vectorlookup(uid, lookup))

For-loop version took 29.4s to complete but only 0.007s for vectorized version. The performance was increased by 4200 folds.
We can also assert two functions are doing the same thing to check for correctness.

1
sum(forlooplookup(uid, lookup) - vectorlookup(uid, lookup)) == 0
sum(forlooplookup(uid, lookup) - vectorlookup(uid, lookup)) == 0
  1. I would say the whole point of R programming is functional programming, but I guess OO people may not agree. []