Python: implementing feature vectors efficiently

Question

I'm implementing feature vectors as bit maps for documents in a corpus. I already have the vocabulary for the entire corpus (as a list/set) and a list of the terms in each document.

For example, if the corpus vocabulary is ['a', 'b', 'c', 'd'] and the terms in document d1 is ['a', 'b', 'd', 'd'], the feature vector for d1 should be [1, 1, 0, 2].

To generate the feature vector, I'd iterate over the corpus vocabulary and check if each term is in the list of document terms, then set the bit in the correct position in the document's feature vector.

What would be the most efficient way to implement this? Here are some things I've considered:

Using a set would make checking vocab membership very efficient but sets have no ordering, and the feature vector bits need to be in the order of the sorted corpus vocabulary.
Using a dict for the corpus vocab (mapping each vocab term to an arbitrary value, like 1) would allow iteration over sorted(dict.keys()) so I could keep track of the index. However, I'd have the space overhead of dict.values().
Using a sorted(list) would be inefficient to check membership.

What would StackOverflow suggest?

Why is a sorted list inefficient for lookup? Do you need better than the O(log(n)) afforded by a binary search? — Cameron
– Cameron, Commented Apr 12, 2011 at 23:36
Tens of thousands of terms, thousands of documents. I'd like to minimize it, and hashing allows nearly O(1). — yavoh
– yavoh, Commented Apr 12, 2011 at 23:37
@yavoh: OK, fair point. Can you change your data structure for the initial document terms to be sets instead of lists? And are you sure you really need the feature vectors exactly this way? Can you take advantage of parallelization? — Cameron
– Cameron, Commented Apr 12, 2011 at 23:40
I forgot to mention that I need to save the frequency of terms, not just the presence of terms, my mistake- I've updated the original question. So, a set wouldn't work. — yavoh
– yavoh, Commented Apr 12, 2011 at 23:42

Glorfindel · Accepted Answer · 2023-02-06 19:00:25Z

2

I think the most efficient way is to loop over each document's terms, get the position of the term in the (sorted) corpus and set the bit accordingly.

The sorted list of corpus terms can be stored as dictionary with term -> index mapping (basically an inverted index).

You can create it like so:

corpus = dict(((term, index) for index, term in enumerate(sorted(all_words))))

For each document you'd have to generate a list of 0's as feature vector:

num_words = len(corpus)
fvs = [[0]*num_words for _ in docs]

Then building the feature vectors would be:

for i, doc_terms in enumerate(docs):
    fv = fvs[i]
    for term in doc_terms:
        fv[corpus[term]] += 1

There is no overhead in testing membership, you just have to loop over all terms of all documents.

That all said, depending on the size of the corpus, you should have a look at numpy and scipy. It is likely that you will run into memory problems and scipy provides special datatypes for sparse matrices (instead of using a list of lists) which can save a lot of memory.
You can use the same approach as shown above, but instead of adding numbers to list elements, you add it to matrix elements (e.g. the rows will be the documents and the columns the terms of the corpus).

You can also make use of some matrix operations provided by numpy if you want to apply local or global weighting schemes.

I hope this gets you started :)

edited Feb 6, 2023 at 19:00

Glorfindel

22.8k13 gold badges97 silver badges124 bronze badges

answered Apr 12, 2011 at 23:47

Felix Kling

820k181 gold badges1.1k silver badges1.2k bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

yavoh Over a year ago

Thanks! I'll look into the scipy classes.

Felix Kling Over a year ago

@yavoh: There are two things you have to consider: (a) How to efficiently build the feature vectors. The approach above should be quite efficient (actually I think one cannot do better). (b) How to efficiently store the feature vectors. And as it is likely that these vectors contain a lot of zeros, sparse matrices is the way to go...

yavoh Over a year ago

You're right, @Felix Kling. I'm looking into using scipy.sparse.dok_matrix.

Collectives™ on Stack Overflow

Python: implementing feature vectors efficiently

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related