# Cluster very many sparse binary vectors

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?

• 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. Aug 7 '16 at 12:57