2
$\begingroup$

I have a very big set of high-dimensional, but sparse binary vectors. Each vector represents a "one-hot-style" n-gram sequence of words where each index of the words that occur in the n-gram is set to 1, all others to 0. E.g.

[0,0,0,0,0,1,0,0,0,0,1,0,0,0,...]

An efficient representation for a 5-gram:

[5,10,235,1253,5521]

What I would like to do is generate such n-gram representations from a large text corpus. Hence, this may easily result in a vocabulary size of hundreds of thousands (depending on potential pre-processing steps including stopword removal, stemming, etc.) and even more distinct n-grams (m). This could be represented as a matrix of size m x vocab_size.

Subsequently, I would like to reduce the number of rows by clustering similar n-grams together while retaining the contained words. For instance:

[5,7,10,12,15],[5,8,10,15,18] -> [5,7,8,10,12,15,18]

My naive approach would be to apply some traditional clustering algorithm in order to assign each entry in the initial n-gram set to a specific cluster and then perform a union over all the n-grams assigned to a cluster.

1st question: what would be an sensible algorithm for clustering sparse binary representations? 2nd question: how could this be done with a very big data set?

$\endgroup$
  • $\begingroup$ Machine learning on text data is not my area, but the data encoding you describe does not seem the most natural: you encode each n-gram as a sparse vector where each index represents a different word, rather than (what I would try first) encoding each document as a sparse vector, where each index represents a different n-gram. Whatever clustering or duplicate detection algorithm you use should result in merging subsequent n-grams, thus indirectly you go back to the alternative (traditional?) document-by-ngram representation. $\endgroup$ – Valentas Aug 7 '16 at 12:57
2
$\begingroup$

I don't think clustering is the right approach here. You want to merge them automatically, but clustering is too unpredictable for this; you need to manually examine clustering results.

I suggest you look at near duplicate detection instead. You want to merge documents that have a high overlap. There are some interesting - and scalable - algorithma for that. In particular, minhash (and later work) is worth looking at.

$\endgroup$
1
$\begingroup$

A few points. First, if you're doing text analytics, there are methods to reduce the space, e.g. stop word filtering and word stemming. You can also consider training a word2vec model, such as that provided by gensim: https://radimrehurek.com/gensim/models/word2vec.html

The particular strength of this method will be to take the space from O(10^7) to O(10^2) (but the vectors will become dense). From there, you can either try approximate nearest neighbor, or cosine similarity.

$\endgroup$
  • $\begingroup$ Thanks for the advice, but your points do not really address my specific questions. I had even explicitly mentioned stop word removal and stemming in the question. Also, I know word2vec, but I am following a different trail here. $\endgroup$ – Carsten Jul 28 '16 at 11:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.