Tell me more ×
Cross Validated is a question and answer site for statisticians, data analysts, data miners and data visualization experts. It's 100% free, no registration required.
up vote 5 down vote favorite

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.

share|improve this question
1  
Some of the techniques in this syllabus will be relavant: coursera.org/nlp/wiki/view?page=syllabus – JonnyBoats Mar 17 '12 at 4:47

2 Answers

up vote 4 down vote accepted

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?

share|improve this answer
Thank you for your reply. In response to your question, I want to cluster word and/or phrase similarities between a pairs of documents. – Subtle Array Mar 16 '12 at 23:07
2  
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? – Oliver Mar 16 '12 at 23:30
It helps a lot. Thank you for your time. You've given me some good info to look up. – Subtle Array Mar 17 '12 at 0:00
Happy to help, good luck with your project :) – Oliver Mar 17 '12 at 0:04
up vote 1 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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