Implement target word-based collocation finder

[koheiw]

There are fcm() and collocations(), but they are all-by-all collocations analysis, which is inefficient with large corpus when users are interested in particular word. I need this function in my ongoing project, in which I analyze a 1GB corpus.

I tries to create this using existing functions, but R part appeared too slow to go through 138,108 full text news. One option is to add window argument to qatd_cpp_tokens_detect.

[koheiw]

If this does not fit to quanteda well, I can add this to my LSS package (there is one for tokenizedTexts obejct already).

[kbenoit]

Let's schedule a design meeting and discussion about collocations generally. I am eager to develop this part of the package in a coordinated and efficient fashion, and agree that the "all ngram" approach from collocations is inefficient for large texts (but it does work!).

[koheiw]

Here is my target word-based collocation finder created from kwic. Not superfast but works with a large corpus (600MB).

text <- c('z a b c d c b a')
collocations_target(tokens(text), 'z', window = 1)

collocations_target <- function(x, keywords, window = 5, valuetype = c("glob", "regex", "fixed"), 
                                case_insensitive = TRUE, ..., new = TRUE) {
    
    valuetype <- match.arg(valuetype)
    keywords <- quanteda:::vector2list(keywords)
    
    # add document names if none
    if (is.null(names(x))) {
        names(x) <- paste("text", 1:length(x), sep="")
    }
    
    types <- attr(x, 'types')
    keywords_id <- quanteda:::regex2id(keywords, types, valuetype, case_insensitive, FALSE)
    
    target <- quanteda:::qatd_cpp_tokens_detect(x, keywords_id)
    
    ids <- which(sapply(target, sum, USE.NAMES = FALSE) > 0)
    
    spread <- target
    df_result <- data.frame()
    if (length(ids)) {
        for (id in ids) {
            spread[[id]] <- spread_mask(spread[[id]], window)
        }
    }
    index <- unlist(x, use.names = FALSE)
    mask <- as.integer(unlist(spread, use.names = FALSE) != 0 & 
                       unlist(target, use.names = FALSE) == 0)

    if (attr(x, 'padding')) {
        types <- c("", types)
        index <- index + 1
    }
    result <- Matrix::sparseMatrix(i = mask + 1,
                                   j = index,
                                   x = 1L,
                                   dimnames = list(class = c('F', 'T'), 
                                                   features = as.character(types)))
    
    mx <- new("dfmSparse", result)
    mx <- mx[,which(featnames(mx) == '') * -1] # drop padding
    return(mx)
    
}

spread_mask <- function(mask, window) {
    
    # Expand vector for matches at the top or end
    mask <- c(0, mask, 0)
    len <- length(mask)
    
    # Detect starting and ending positions of keywords
    start <- which(diff(c(0, mask)) == 1)
    end <- which(diff(c(mask, 0)) == -1)
    
    for (i in 1:length(start)) {
        mask[max(0, start[i] - window):min(len, end[i] + window)] <- 1
    }
    return(mask[c(-1, length(mask) * -1)])
}

[koheiw]

The parallel fcm looks fairly fast but not working with my 800MB tokens.

toks <- readRDS('data_tokens_asahi.RDS')
out <- fcm(toks, 'window')
object.size(toks) # 843907544 bytes

error: SpMat::init(): requested size is too large
 Show Traceback
 
 Rerun with Debug
 Error in qatd_cpp_fcm(x, nfeature(x), count, window, weights, ordered,  : 
  SpMat::init(): requested size is too large > object.size(toks)

I am only interested only one word "United States", nothing else! It would be good to add target option with multi-word feature support (easy).

[kbenoit]

I think that’s called “kwic” !! On 8 Feb 2017, at 22:17, Kohei Watanabe <notifications@github.com<mailto:notifications@github.com>> wrote: The parallel fcm looks fairly fast but not working with my 800MB tokens. toks <- readRDS('data_tokens_asahi.RDS') out <- fcm(toks, 'window') object.size(toks) # 843907544 bytes error: SpMat::init(): requested size is too large Show Traceback Rerun with Debug Error in qatd_cpp_fcm(x, nfeature(x), count, window, weights, ordered, : SpMat::init(): requested size is too large > object.size(toks) I am only interested only one word "United States", nothing else! It would be good to add target word option with multi-word feature support (easy). — You are receiving this because you commented. Reply to this email directly, view it on GitHub<#521 (comment)>, or mute the thread<https://github.com/notifications/unsubscribe-auth/ACFMZtfAgKd8bAaPXlQBd9LtZm22hSxKks5raj7pgaJpZM4LvA9S>.

[koheiw]

I agree that it is close to kwic (the underlying function of collocation_target is actually tokens_detect), but kwic object is not good because I will construct a collocation matrix, and put it into dfm_keyness(). This is what people has been doing in other tools (QDA Miner, WordSmith, Sketch Engine etc.) when they investigate how particular entities or concepts are represented in documents. I will use all-by-all collocation to fit vector space models, but more often target-by-all to obtain syntactical associates. Others users would agree with me.

[kbenoit]

If you just want a window-based collocation around a target word, why not use fcm on a kwic output? But maybe I didn't catch what it was you wanted exactly. Could you be more specific, showing the example of the outputs you want?

[koheiw]

kwic is inefficient because it returns characters. Here is an example of my collocation analysis:

collocations_target <- function(x, keywords, window = 5, valuetype = c("glob", "regex", "fixed"), 
                                case_insensitive = TRUE, ..., new = TRUE) {
    
    valuetype <- match.arg(valuetype)
    keywords <- quanteda:::vector2list(keywords)
    
    # add document names if none
    if (is.null(names(x))) {
        names(x) <- paste("text", 1:length(x), sep="")
    }
    
    types <- attr(x, 'types')
    keywords_id <- quanteda:::regex2id(keywords, types, valuetype, case_insensitive, FALSE)
    
    target <- quanteda:::qatd_cpp_tokens_detect(x, keywords_id)
    
    ids <- which(sapply(target, sum, USE.NAMES = FALSE) > 0)
    
    spread <- target
    df_result <- data.frame()
    if (length(ids)) {
        for (id in ids) {
            spread[[id]] <- spread_mask(spread[[id]], window)
        }
    }
    index <- unlist(x, use.names = FALSE)
    mask <- as.integer(unlist(spread, use.names = FALSE) != 0 & 
                           unlist(target, use.names = FALSE) == 0)
    
    if (attr(x, 'padding')) {
        types <- c("", types)
        index <- index + 1L
    }
    result <- Matrix::sparseMatrix(i = mask + 1L,
                                   j = index,
                                   x = 1L,
                                   dimnames = list(class = c('F', 'T'), 
                                                   features = as.character(types)))
    mx <- new("dfmSparse", result)
    mx <- quanteda::dfm_remove(mx, '')
    return(mx)
    
}



spread_mask <- function(mask, window) {
    
    # Expand vector for matches at the top or end
    mask <- c(0, mask, 0)
    len <- length(mask)
    
    # Detect starting and ending positions of keywords
    start <- which(diff(c(0, mask)) == 1)
    end <- which(diff(c(mask, 0)) == -1)
    
    for (i in 1:length(start)) {
        mask[max(0, start[i] - window):min(len, end[i] + window)] <- 1
    }
    return(mask[c(-1, length(mask) * -1)])
}

# Run -------------------------------
toks <- tokens(data_corpus_inaugural)
mx_col <- collocations_target(toks, 'president*', window = 5)
head(textstat_keyness(mx_col, 'T'), 10)