7
$\begingroup$

I'm working on a project where I'm trying to take a pair of documents and find and group (cluster) similar words and phrases between them.

Which algorithm would solve this kind of a problem? I know this is a very mundane and probably subjective question, but I'm new to clustering, and I'm still trying to work my way around the vocabulary.

Your help would be appreciated.

$\endgroup$
8
$\begingroup$

Right off the bat, you may want to look at various string distances. The only one I'm familiar with is the Levenshtein distance, which is pretty rudimentary. You could apply this on sentences or phrases.

You may want to take a look at some natural language processing techniques, too, such as stemming and tokenizing your data before running any clustering algorithms on it. If you like Python, I highly recommend nltk, which has lots of packages for natural language processing. It may even have a clustering or distance algorithm for you. A quick google gives me this package, but I've never used it.

Edit: Upon reflection, I might have misunderstood your question - are you clustering documents, or words/phrases?

$\endgroup$
  • 1
    $\begingroup$ Thank you for your reply. In response to your question, I want to cluster word and/or phrase similarities between a pairs of documents. $\endgroup$ – subtlearray Mar 16 '12 at 23:07
  • 2
    $\begingroup$ Hm. You could look into natural language summarization techniques. Often, automatic summarization of a document involves splitting the document into sentences, clustering the sentences, and then reporting one sentence from each cluster. One basic way to do this is to represent each sentence as a bag-of-words vector. You define a high-dimension vector space where each dimension is a word. Sentences are vectors of the number of occurrences of each word. You can then cluster these vectors using common algorithms (e.g., k-means). Does this help? $\endgroup$ – Oliver Mar 16 '12 at 23:30
  • $\begingroup$ It helps a lot. Thank you for your time. You've given me some good info to look up. $\endgroup$ – subtlearray Mar 17 '12 at 0:00
  • $\begingroup$ Happy to help, good luck with your project :) $\endgroup$ – Oliver Mar 17 '12 at 0:04
2
$\begingroup$

For pretty much any clustering algorithm that can work with such data, you will need to define a distance or similarity function first. So you might want to browse through the literature on appropriate distance functions for your task.

E.g. cosine distance on a TF-IDF normalized vector representation.

$\endgroup$

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.