What is the best algorithm to find similar text documents?

Question

I have many text documents and I would like to find similar documents to each document within my data set. Is Latent Dirichlet Allocation (LDA) the best way to do that, or are there other algorithms taht might work better? Any ideas?

As my data set in big, I would rather use Apache Mahout to find similar documents.

Answer 1

To find similar documents in very large document sets is locality sensitive hashing (LSH). An indication of the gist is: "One general approach to LSH is to “hash” items several times, in such a way that similar items are more likely to be hashed to the same bucket than dissimilar items are."

For in-depth information see: http://infolab.stanford.edu/~ullman/mmds/ch3a.pdf

Answer 2

Why cluster? Why LDA?Much too expensive, complicated, and unreliable. Let me present you an incredible novel technique to find similar documents:

text search

There is a wonderful tool called Apache Lucene, that makes text search fast and easy to integrate, too.

Answer 3

One good technique that I've seen used in the past for information retrieval applications is to shingle your target documents and query document, and then take the Jaccard similarity over sets of shingles.

Shingling is a procedure that takes a sliding window over characters in your document, representing a string as the set of character $k$-grams that occur in the strong. Now that we have a set representation of documents, we can compare them using their Jaccard similarity.

As an example, the 2-shingles of the string "racecar" would be the set {ra, ac, ce, ec, ca, ar}.

Below is some simple Python code that would do this to illustrate the point:

def shingle(doc, k=3):
    return { doc[i:i+k] for i in range(0, len(doc) - k + 1) }

def jaccard(a, b):
    return 1.0 * len(a.intersection(b)) / len(a.union(b))

documents = [...] # List of strings
query = "this week on twitter..."
query_shingles = shingle(query)

best_doc = -1
best_score = float("-inf")
for i, doc in enumerate(documents):
    doc_shingles = shingle(doc)
    similarity = jaccard(doc_shingles, query_shingles)
    if similarity > best_score:
        best_score = similarity
        best_doc = i

The idea is that documents with similar $k$-shingles have similar contents for a well-chosen value of $k$. For most applications $k$ is almost always between 2 and 4 (3 is the most popular choice that I've seen).

There are alternative formulations such as $w$-shingling which use word $n$-grams instead of character $n$-grams, but the idea is still the same.

Answer 4

This program uses word frequency analysis ("bag of words") and sorts the repository texts by Euclidian distance to the vector of frequencies of the sample text.

Given a sample text, this program lists the repository texts sorted by similarity: simple implementation of bag of words in C++. The algorithm is linear in the total length of the sample text and the repository texts. Plus the program is multi-threaded to process repository texts in parallel.

Here is the core algorithm:

class Statistics {
  std::unordered_map<std::string, int64_t> _counts;
  int64_t _totWords;

  void process(std::string& token);
public:
  explicit Statistics(const std::string& text);

  double Dist(const Statistics& fellow) const;

  bool IsEmpty() const { return _totWords == 0; }
};

namespace {
  const std::string gPunctStr = ".,;:!?";
  const std::unordered_set<char> gPunctSet(gPunctStr.begin(), gPunctStr.end());
}

Statistics::Statistics(const std::string& text) {
  std::string lastToken;
  for (size_t i = 0; i < text.size(); i++) {
    int ch = static_cast<uint8_t>(text[i]);
    if (!isspace(ch)) {
      lastToken.push_back(tolower(ch));
      continue;
    }
    process(lastToken);
  }
  process(lastToken);
}

void Statistics::process(std::string& token) {
  do {
    if (token.size() == 0) {
      break;
    }
    if (gPunctSet.find(token.back()) != gPunctSet.end()) {
      token.pop_back();
    }
  } while (false);
  if (token.size() != 0) {
    auto it = _counts.find(token);
    if (it == _counts.end()) {
      _counts.emplace(token, 1);
    }
    else {
      it->second++;
    }
    _totWords++;
    token.clear();
  }
}

double Statistics::Dist(const Statistics& fellow) const {
  double sum = 0;
  for (const auto& wordInfo : _counts) {
    const std::string wordText = wordInfo.first;
    const double freq = double(wordInfo.second) / _totWords;
    auto it = fellow._counts.find(wordText);
    double fellowFreq;
    if (it == fellow._counts.end()) {
      fellowFreq = 0;
    }
    else {
      fellowFreq = double(it->second) / fellow._totWords;
    }
    const double d = freq - fellowFreq;
    sum += d * d;
  }
  return std::sqrt(sum);
}

It's tested on Project Gutenberg books, as you can see in the example on GitHub.