6

I'm trying to write an algorithm (which I'm assuming will rely on natural language processing techniques) to 'fill out' a list of search terms. There is probably a name for this kind of thing which I'm unaware of. What is this kind of problem called, and what kind of algorithm will give me the following behavior?

Input:

    docs = [
    "I bought a ticket to the Dolphin Watching cruise",
    "I enjoyed the Dolphin Watching tour",
    "The Miami Dolphins lost again!",
    "It was good going to that Miami Dolphins game"
    ], 
    search_term = "Dolphin"

Output:

["Dolphin Watching", "Miami Dolphins"]

It should basically figure out that if "Dolphin" appears at all, it's virtually always either in the bigrams "Dolphin Watching" or "Miami Dolphins". Solutions in Python preferred.

Trindaz
  • 17,029
  • 21
  • 82
  • 111
  • How do you know that Dolphin is part of the bigrams "Dolphin Watching" or "Miami Dolphins?" Is it because both of the words in each bigram are capitalized? Or do you have another list containing the desired bigrams? – Robert Harvey Sep 29 '11 at 23:35
  • @RobertHarvey: A good NLP algorithm should be able parse out [Miami Dolphins] as a term. Same with [Dolphin Watching]. It's easier when you think about it like if you formed each of the phrases as a question. Q: "What tour did you enjoy watching?" A: [The [Dolphin Watching] tour], Q: Who lost the game? A: [The [Miami Dolphins]]. You have to parse it into a tree to see what belongs with what. Not an easy problem by any means...but you can get somewhat accurate results. – mpen Sep 29 '11 at 23:46
  • @RobertHarvey I have a list of specific words so I know Dolphin has to be in there somewhere. – Trindaz Sep 29 '11 at 23:59

2 Answers2

7

It should basically figure out that if "Dolphin" appears at all, it's virtually always either in the bigrams "Dolphin Watching" or "Miami Dolphins".

Sounds like you want to determine the collocations that Dolphin occurs in. There are various methods for collocation finding, the most popular being to compute point-wise mutual information (PMI) between terms in your corpus, then select the terms with the highest PMI for Dolphin. You might remember PMI from the sentiment analysis algorithm that I suggested earlier.

A Python implementation of various collocation finding methods is included in NLTK as nltk.collocations. The area is covered in some depth in Manning and Schütze's FSNLP (1999, but still current for this topic).

Community
  • 1
  • 1
Fred Foo
  • 355,277
  • 75
  • 744
  • 836
0

I used the Natural Language Toolkit in my NLP class in university with decent success. I think it's got some taggers that can help you determine which are the nouns, and help you parse it into a tree. I don't remember much, but I'd start there.

mpen
  • 272,448
  • 266
  • 850
  • 1,236