在R中进行非常快速的词语ngram向量化

16

编辑:新的text2vec软件包非常出色,很好地解决了这个问题(以及许多其他问题)。

text2vec在CRAN上的页面 text2vec在github上的页面 演示ngram标记化的vignette

我有一个相当大的R文本数据集,我已将其导入为字符向量:

#Takes about 15 seconds
system.time({
  set.seed(1)
  samplefun <- function(n, x, collapse){
    paste(sample(x, n, replace=TRUE), collapse=collapse)
  }
  words <- sapply(rpois(10000, 3) + 1, samplefun, letters, '')
  sents1 <- sapply(rpois(1000000, 5) + 1, samplefun, words, ' ')
})

我可以将这些字符数据转化为词袋表示,方法如下:

library(stringi)
library(Matrix)
tokens <- stri_split_fixed(sents1, ' ')
token_vector <- unlist(tokens)
bagofwords <- unique(token_vector)
n.ids <- sapply(tokens, length)
i <- rep(seq_along(n.ids), n.ids)
j <- match(token_vector, bagofwords)
M <- sparseMatrix(i=i, j=j, x=1L)
colnames(M) <- bagofwords

所以R可以在大约3秒钟内将1,000,000个短句子向量化为词袋表示(不错!):

> M[1:3, 1:7]
10 x 7 sparse Matrix of class "dgCMatrix"
      fqt hqhkl sls lzo xrnh zkuqc mqh
 [1,]   1     1   1   1    .     .   .
 [2,]   .     .   .   .    1     1   1
 [3,]   .     .   .   .    .     .   .

我可以将这个稀疏矩阵投入到 glmnetirlba中,对文本数据进行一些很棒的量化分析。太好了!

现在我想将这个分析扩展到 n-gram 的矩阵上,而不是单词矩阵。到目前为止,我发现最快的方法是按照以下步骤操作(我找到的所有n-gram函数都无法处理这个数据集,所以我从SO得到了一些帮助):

find_ngrams <- function(dat, n, verbose=FALSE){
  library(pbapply)
  stopifnot(is.list(dat))
  stopifnot(is.numeric(n))
  stopifnot(n>0)
  if(n == 1) return(dat)
  pblapply(dat, function(y) {
    if(length(y)<=1) return(y)
    c(y, unlist(lapply(2:n, function(n_i) {
      if(n_i > length(y)) return(NULL)
      do.call(paste, unname(as.data.frame(embed(rev(y), n_i), stringsAsFactors=FALSE)), quote=FALSE)
    })))
  })
}

text_to_ngrams <- function(sents, n=2){
  library(stringi)
  library(Matrix)
  tokens <- stri_split_fixed(sents, ' ')
  tokens <- find_ngrams(tokens, n=n, verbose=TRUE)
  token_vector <- unlist(tokens)
  bagofwords <- unique(token_vector)
  n.ids <- sapply(tokens, length)
  i <- rep(seq_along(n.ids), n.ids)
  j <- match(token_vector, bagofwords)
  M <- sparseMatrix(i=i, j=j, x=1L)
  colnames(M) <- bagofwords
  return(M)
}

test1 <- text_to_ngrams(sents1)

这个函数大约需要150秒的时间(对于一个纯R函数来说还不错),但是我希望能更快地处理更大的数据集。

在R中有没有非常快速的函数可以用于n-gram文本向量化?理想情况下,我正在寻找一种Rcpp函数,它以字符向量作为输入,并将文档x ngrams返回为稀疏矩阵输出,但也很乐意获得编写Rcpp函数的指导。

即使是find_ngrams函数的更快版本也会很有帮助,因为那是主要的瓶颈。在分词方面,R表现出惊人的速度。

编辑1: 这里是另一个示例数据集:

sents2 <- sapply(rpois(100000, 500) + 1, samplefun, words, ' ')
在这种情况下,我的创建词袋矩阵的函数大约需要30秒,而创建n-gram词袋矩阵的函数则需要大约500秒。同样,在R中现有的n-gram向量化程序似乎无法处理此数据集(虽然我很希望被证明是错误的!) 编辑2 时间 vs tau:
zach_t1 <- system.time(zach_ng1 <- text_to_ngrams(sents1))
tau_t1 <- system.time(tau_ng1 <- tau::textcnt(as.list(sents1), n = 2L, method = "string", recursive = TRUE))
tau_t1 / zach_t1 #1.598655

zach_t2 <- system.time(zach_ng2 <- text_to_ngrams(sents2))
tau_t2 <- system.time(tau_ng2 <- tau::textcnt(as.list(sents2), n = 2L, method = "string", recursive = TRUE))
tau_t2 / zach_t2 #1.9295619

你考虑过使用 tau::textcnt(as.list(sents), n = 2L, method = "string", recursive = TRUE) 替代 find_ngrams 吗?它只需要一半的时间,但是只提供二元组(n=2)。 - lukeA
我还没有尝试过那个,但会尝试一下。如果对于两个数据集来说速度比我上面的代码快,那么二元组将起作用。 - Zach
@lukeA 在我的系统上,tau::textct 在两个数据集上都比较慢,慢了50%。我会更新我的问题,并提供时间和示例代码,请您在您的系统上尝试并比较结果。 - Zach
1
stringdist::qgrams 可以非常快速地生成字符 qgrams。作者目前正在努力支持单词(ints)。 - Jan van der Laan
@Zach Strange。现在我得到了 tau_t1 / zach_t1 = 649.48 / 675.82。差别不大了。 - lukeA
显示剩余6条评论
2个回答

10

这是一个非常有趣的问题,我在 quanteda 包中花费了很多时间来探讨它。虽然关于你的问题只有第三点真正回答了这个问题,但前两点解释了为什么我只关注了 ngram 创建函数,因为正如你所指出的那样,那里是可以提高速度的地方。

  1. 分词。您在此处使用的是空格字符上的 string::str_split_fixed(),这是最快的方法,但不是最好的分词方法。我们在quanteda::tokenize(x,what =“fastest word”)中实现了几乎完全相同的内容。这不是最好的方法,因为 stringi 可以更智能地实现分割空格。 (即使字符类 \\s 更聪明,但稍微慢一些 - 这被实现为 what =“fasterword”)。不过,您的问题并不是关于分词,所以这一点只是上下文。

  2. 制表文档特征矩阵。 在这里,我们还使用 Matrix 包,并索引文档和特征(我称之为特征而不是术语),并像您在上面的代码中直接创建稀疏矩阵。 但是,您使用的 match() 比我们通过 data.table 使用的匹配/合并方法要快得多。我将重新编写 quanteda::dfm() 函数,因为您的方法更简洁、更快速。真的非常高兴看到这个!

  3. ngram 创建。 在这里,我认为我实际上可以帮助提高性能。 我们通过 quanteda::tokenize() 中的一个参数来实现这一点,称为 grams = c(1),其中该值可以设置为任何整数。例如,我们匹配单元和双字节码的方法将是 ngrams = 1:2。您可以在https://github.com/kbenoit/quanteda/blob/master/R/tokenize.R 上查看代码,看看内部函数 ngram()。我已经重现了这个函数并制作了一个包装器,以便我们可以直接将其与您的find_ngrams()函数进行比较。

代码:

# wrapper
find_ngrams2 <- function(x, ngrams = 1, concatenator = " ") { 
    if (sum(1:length(ngrams)) == sum(ngrams)) {
        result <- lapply(x, ngram, n = length(ngrams), concatenator = concatenator, include.all = TRUE)
    } else {
        result <- lapply(x, function(x) {
            xnew <- c()
            for (n in ngrams) 
                xnew <- c(xnew, ngram(x, n, concatenator = concatenator, include.all = FALSE))
            xnew
        })
    }
    result
}

# does the work
ngram <- function(tokens, n = 2, concatenator = "_", include.all = FALSE) {

    if (length(tokens) < n) 
        return(NULL)

    # start with lower ngrams, or just the specified size if include.all = FALSE
    start <- ifelse(include.all, 
                    1, 
                    ifelse(length(tokens) < n, 1, n))

    # set max size of ngram at max length of tokens
    end <- ifelse(length(tokens) < n, length(tokens), n)

    all_ngrams <- c()
    # outer loop for all ngrams down to 1
    for (width in start:end) {
        new_ngrams <- tokens[1:(length(tokens) - width + 1)]
        # inner loop for ngrams of width > 1
        if (width > 1) {
            for (i in 1:(width - 1)) 
                new_ngrams <- paste(new_ngrams, 
                                    tokens[(i + 1):(length(tokens) - width + 1 + i)], 
                                    sep = concatenator)
        }
        # paste onto previous results and continue
        all_ngrams <- c(all_ngrams, new_ngrams)
    }

    all_ngrams
}

这是一个简单文本的比较:

txt <- c("The quick brown fox named Seamus jumps over the lazy dog.", 
         "The dog brings a newspaper from a boy named Seamus.")
tokens <- tokenize(toLower(txt), removePunct = TRUE)
tokens
# [[1]]
# [1] "the"    "quick"  "brown"  "fox"    "named"  "seamus" "jumps"  "over"   "the"    "lazy"   "dog"   
# 
# [[2]]
# [1] "the"       "dog"       "brings"    "a"         "newspaper" "from"      "a"         "boy"       "named"     "seamus"   
# 
# attr(,"class")
# [1] "tokenizedTexts" "list"     

microbenchmark::microbenchmark(zach_ng <- find_ngrams(tokens, 2),
                               ken_ng <- find_ngrams2(tokens, 1:2))
# Unit: microseconds
#                                expr     min       lq     mean   median       uq     max neval
#   zach_ng <- find_ngrams(tokens, 2) 288.823 326.0925 433.5831 360.1815 542.9585 897.469   100
# ken_ng <- find_ngrams2(tokens, 1:2)  74.216  87.5150 130.0471 100.4610 146.3005 464.794   100

str(zach_ng)
# List of 2
# $ : chr [1:21] "the" "quick" "brown" "fox" ...
# $ : chr [1:19] "the" "dog" "brings" "a" ...
str(ken_ng)
# List of 2
# $ : chr [1:21] "the" "quick" "brown" "fox" ...
# $ : chr [1:19] "the" "dog" "brings" "a" ...

对于您的大量模拟文本,以下是比较结果:

tokens <- stri_split_fixed(sents1, ' ')
zach_ng1_t1 <- system.time(zach_ng1 <- find_ngrams(tokens, 2))
ken_ng1_t1 <- system.time(ken_ng1 <- find_ngrams2(tokens, 1:2))
zach_ng1_t1
#    user  system elapsed 
# 230.176   5.243 246.389 
ken_ng1_t1
#   user  system elapsed 
# 58.264   1.405  62.889 

已经有所改进,如果能再进一步改进,我会感到非常高兴。我也应该能够将更快的dfm()方法实现到quanteda中,这样你就可以通过以下方式轻松获得所需:

Already an improvement, I'd be delighted if this could be improved further. I also should be able to implement the faster dfm() method into quanteda so that you can get what you want simply through:

dfm(sents1, ngrams = 1:2, what = "fastestword",
    toLower = FALSE, removePunct = FALSE, removeNumbers = FALSE, removeTwitter = TRUE)) 

(已经能够工作,但比你的总体结果慢,因为你创建最终稀疏矩阵对象的方式更快 - 但我很快就会改变这一点。)


1
我很高兴我们可以互相帮助! - Zach
我也是。Quanteda的GitHub版本现在已经将此帖子中的方法应用于tokenize()和dfm()的更改中。现在应该按照我在答案末尾描述的方式非常快速地为您工作。我很快就会处理您在GitHub上的其余问题。谢谢! - Ken Benoit
与Zach的答案相比,他的风格仍然比quanteda快得多。为什么?我以为在你的更改之后,这个问题应该已经解决了,@Ken Benoit - ambodi
2
@ambodi quanteda::ngrams()自此帖子以来已经有所改变,因此我会尽快进行审核并回复您。 - Ken Benoit
1
@KenBenoit 谢谢。我真的想使用quanteda,因为我喜欢它的API,但由于我的文本文件很大,所以我暂时放弃了它并使用了Zach的解决方案。 - ambodi

2
这里是使用 tokenizers 开发版本的测试,你可以使用 devtools::install_github("ropensci/tokenizers") 获取。
根据上面的 sents1sents2find_ngrams() 的定义:
library(stringi)
library(magrittr)
library(tokenizers)
library(microbenchmark)
library(pbapply)


set.seed(198)
sents1_sample <- sample(sents1, 1000)
sents2_sample <- sample(sents2, 1000)

test_sents1 <- microbenchmark(
  find_ngrams(stri_split_fixed(sents1_sample, ' '), n = 2), 
  tokenize_ngrams(sents1_sample, n = 2),
  times = 25)
test_sents1

结果:

Unit: milliseconds
                                                     expr       min        lq       mean
 find_ngrams(stri_split_fixed(sents1_sample, " "), n = 2) 79.855282 83.292816 102.564965
                    tokenize_ngrams(sents1_sample, n = 2)  4.048635  5.147252   5.472604
    median         uq        max neval cld
 93.622532 109.398341 226.568870    25   b
  5.479414   5.805586   6.595556    25  a 

在sents2上进行测试

test_sents2 <- microbenchmark(
  find_ngrams(stri_split_fixed(sents2_sample, ' '), n = 2), 
  tokenize_ngrams(sents2_sample, n = 2),
  times = 25)
test_sents2

结果:

Unit: milliseconds
                                                     expr      min       lq     mean
 find_ngrams(stri_split_fixed(sents2_sample, " "), n = 2) 509.4257 521.7575 562.9227
                    tokenize_ngrams(sents2_sample, n = 2) 288.6050 295.3262 306.6635
   median       uq      max neval cld
 529.4479 554.6749 844.6353    25   b
 306.4858 310.6952 332.5479    25  a 

仅检查直接时间

timing <- system.time({find_ngrams(stri_split_fixed(sents1, ' '), n = 2)})
timing

   user  system elapsed 
 90.499   0.506  91.309 

timing_tokenizers <- system.time({tokenize_ngrams(sents1, n = 2)})
timing_tokenizers

   user  system elapsed 
  6.940   0.022   6.964 

timing <- system.time({find_ngrams(stri_split_fixed(sents2, ' '), n = 2)})
timing

   user  system elapsed 
138.957   3.131 142.581 

timing_tokenizers <- system.time({tokenize_ngrams(sents2, n = 2)})
timing_tokenizers

   user  system elapsed 
  65.22    1.57   66.91

很多情况下,速度提升将取决于被分词的文本,但这似乎表明速度可以提高2倍到20倍。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接