Generating a co-occurrence matrix

Question

I am generating co-occurrence matrix (2000X2000) in Python.

• Vocab is a list of the 2000 top words in corpus. It does not contain all words in corpus.

• Corpus is a Pandas dataframe of 30000 (rows) sentences.
  An example of a single row in the corpus:

  the energy classroom high the room filled scholars eager learn they embarking learning journey unlike no these scholars asked learn time rapidly changing technology communication as teacher job give tools successful our school special always looking ways give students best education possible my 4th grade students counting provide tools necessary success i want keep love learning alive giving students access technology critical success 21st century learning environment our school 1 3 ratio ipads kids we use variety apps allow kids collaborate build critical thinking skills even though ipads keyboard ipad cumbersome difficult kids use therefore i asking 15 keyboards plug ipads having wired keyboard allows kids practice keyboarding skills standard collaborate others effectively utilize technology accesskeyboards enhance collaboration choice critical thinkin

My code is currently taking 120s per iteration and 364 hours to complete run. I am running this code in Google Colab with 25GB RAM.

The code works fine with small data like 10 row corpus and 5 word vocab. Is there a better way to complete this task or speed up this process?

tqdm is required because if the code runs for longer than 12 hours, which it is, then it gets disconnected from Google Colab.

coocur_matrix = np.zeros((len(voca), len(voca)),np.float64)

#python
from tqdm import tqdm


window_size=5
corpus=corpu1
vocab = voca

for word1 in tqdm(vocab):
  for word2 in vocab:
    for sent in corpus:
      doc_tokens = []
      doc_tokens=sent.split()

      p1= [i for i in range(len(doc_tokens)) if doc_tokens[i] == word1]
      p2= [i for i in range(len(doc_tokens)) if doc_tokens[i] == word2]
      for k in p1:
        print(9)
        for l in p2:
          if (abs(l-k)<=window_size):
            if(word1!=word2):
              coocur_matrix[vocab.index(word1),vocab.index(word2)] += 1

print(coocur_matrix)

Answer 1

Readability

Your code is visually unappealing. You have multiple PEP 8 violations, and your variable names really don't speak volumes. You have 2 spaces of indentation which is pretty much un-heard of in Python. If we move your code into a function and perform a little clean up we can get something like:

import numpy as np


def get_indexes(tokens, word):
    return [
        index
        for index, token in enumerate(tokens)
        if token == word
    ]


def co_occurrence_matrix(corpus, vocabulary, window_size=5):
    matrix = np.zeros((len(vocabulary), len(vocabulary)), np.float64)
    for word_1 in vocabulary:
        for word_2 in vocabulary:
            for sent in corpus:
                tokens = sent.split()
                tokens_1 = get_indexes(tokens, word_1)
                tokens_2 = get_indexes(tokens, word_2)
                for k in tokens_1:
                    for l in tokens_2:
                        if abs(l - k) > window_size:
                            continue
                        if word_1 == word_2:
                            continue
                        matrix[
                            vocabulary.index(word_1),
                            vocabulary.index(word_2),
                        ] += 1
    return matrix


print(co_occurrence_matrix(corpu1, voca))

Performance

Now It doesn't look too bad, but it doesn't really look nice. From here we can see clearly that word_1 and word_2 are defined in the first two loops, however the check word_1 == word_2 is on the inner-most level of the loops. This means you're needlessly looping over sent, tokens_1 and tokens_2. These loops, totalling around 12000000, are useless and a waste of time.

It can be hard to see, but vocabulary.index(word_1) has a for loop in it. How else is it getting the index? This means you're looping 2000 times, this is a waste as you can define a variable to store the index when looping through vocabulary.

You don't need to iterate over vocabulary, you can just iterate over corpus. This is because if word_1 or word_2 is not in tokens then the for loop will iterate over an empty list and so will do nothing. And so we can derive word_1 and word_2 from corpus.

Since vocabulary only contains the top 2000 words in the corpus. Then a naïve flip of the loops is still going to waste some cycles. And so we can just filter sent to ones in the vocabulary. To achieve this I opted to use a closure as I think it makes the code cleaner and easier to read. This is because I don't have the walrus on Python 3.7 and wanted to use dict.get rather than perform two dictionary lookups per filter of each token.

import numpy as np
import itertools


def by_indexes(iterable):
    output = {}
    for index, key in enumerate(iterable):
        output.setdefault(key, []).append(index)
    return output


def co_occurrence_matrix(corpus, vocabulary, window_size=5):
    def split_tokens(tokens):
        for token in tokens:
            indexs = vocabulary_indexes.get(token)
            if indexs is not None:
                yield token, indexs[0]

    matrix = np.zeros((len(vocabulary), len(vocabulary)), np.float64)
    vocabulary_indexes = by_indexes(vocabulary)

    for sent in corpus:
        tokens = by_indexes(split_tokens(sent.split())).items()
        for ((word_1, x), indexes_1), ((word_2, y), indexes_2) in itertools.permutations(tokens, 2):
            for k in indexes_1:
                for l in indexes_2:
                    if abs(l - k) <= window_size:
                        matrix[x, y] += 1
    return matrix


print(co_occurrence_matrix(corpu1, voca))

This currently isn't fully optimized, as you can use combinations rather than permutations but that would require mirroring the non-empty values of the matrix. That would likely half the time it takes to run, but would require additional code.

This is answer is entirely hypothetical. This means using dict[] twice rather than dict.get may be faster. It also means that many of the assumptions I made may not translate into performance benefits due to the way Python is.