Identification of topics for online discussions based on language patterns

• US 7,739,261 B2
• Filed: 06/14/2007
• Issued: 06/15/2010
• Est. Priority Date: 06/14/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhang, Duo, Li, Hua, Chen, Zheng, Wang, Jian, Zeng, Hua-Jun, Hu, Jian
• Primary Examiner(s): Vo; Tim T.
• Assistant Examiner(s): Fan; Shiow-Jy
• Application Number:
  US11/763,282
• Publication Number:
  US 20080313180A1
• Time in Patent Office: 1,097 Days
• Field of Search: 707/6, 707/E17.014, 707/101, 707/104.1, 707/708, 707/999.006, 707/731, 707/738, 707/749, 707/754, 704/9
• US Class Current: 707/708
• CPC Class Codes: G06F 16/36 Creation of semantic tools, e.g. ontology or thesauri
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

A topic identification system identifies topics of online discussions by iteratively identifying topic words or keywords of the online discussions and identifying language patterns associated with those keywords. The topic identification system starts out with an initial set of keywords and identifies language patterns that each include a keyword. The topic identification system then uses the identified language patterns to identify additional keywords of the online discussion that match the patterns. The topic identification system then again identifies language patterns using the keywords including the newly identified keywords. The topic identification system may repeat the process of identifying language patterns and keywords until a termination criterion is satisfied.

Claims

1. A method in a computing device for identifying keywords from a corpus of sentences of words, the method comprising:

storing an initial set of keywords as a current set of keywords;

locating, from sentences of the corpus, words that are keywords of the current set of keywords and replacing each located word with an occurrence of keyword symbol;

for each occurrence of a keyword symbol of a sentence of the corpus, identifying a sequence segment that includes the occurrence of the keyword symbol along with words of the sentence that are adjacent to the keyword symbol;

applying a pattern mining algorithm to the identified sequence segments to identify patterns of words adjacent to the occurrences of the keyword symbol by comparing words adjacent to an occurrence of a keyword symbol to words adjacent to other occurrences of the keyword symbol to derive patterns from the adjacent words, some of identified patterns including the keyword symbol and others of the identified patterns not including the keyword symbol;

filtering out from the identified patterns the identified patterns that do not include the keyword symbol;

filtering out from the identified patterns the identified patterns that include only prepositions in addition to the keyword symbol;

identifying, from the sentences of the corpus, a new current set of keywords that satisfy a keyword confidence criterion based on the identified patterns by applying each identified pattern to the sentences and when an identified pattern matches a sentence, designating the word of the sentence corresponding to the keyword symbol of the identified pattern as a keyword of the new current set of keywords; and

repeating the locating of words, the identifying of sequence segments, the applying of the pattern matching algorithm to identify patterns, and the identifying of keywords using the new current set of keywords until a termination criterion is satisfied and then indicating that the keywords of the identified new current sets of keywords are keywords of the corpus.

2. The method of claim 1 wherein the corpus includes content from online discussions.

3. The method of claim 2 wherein a pattern is identified as a candidate pattern when support for the pattern satisfies a pattern support criterion.

4. The method of claim 3 wherein the support for a pattern is represented by a pattern support score and the pattern support criterion is a minimum pattern support score needed for the pattern to be considered a candidate pattern.

5. The method of claim 1 wherein the identifying of the patterns applies a sequential pattern mining technique.

6. The method of claim 1 including submitting an advertisement for placement with content that relates to an identified keyword.

7. The method of claim 1 including filtering out patterns that do not satisfy a pattern confidence criterion.

8. The method of claim 1 wherein the keyword confidence criterion being based on pattern confidence scores of patterns from which a keyword was identified.

9. A computing device that identifies keywords from a corpus of sentences of words from online discussions, comprising:

a keyword store containing keywords, the keyword store having an initial set of keywords;

a corpus store containing sentences of the corpus;

a component that identifies sequence segments of the sentences of the corpus, a sequence segment being a sequence of words that includes a keyword of the keyword store;

a component that identifies, from the identified sequence segments, patterns of sequences of words that include a keyword by comparing a sequence segment to other sequence segments to determine whether a pattern can be derived from the sequence segments by applying a pattern mining algorithm to the identified sequence segments to identify patterns of words adjacent to the occurrences of the keywords based on comparison of words adjacent to an occurrence of a keyword to words adjacent to other occurrences of keywords to derive patterns from the adjacent words, some of identified patterns including a keyword;

a component that filters out from the identified patterns the identified patterns that do not include a keyword;

a component that filters out from the identified patterns the identified patterns that include only preposition in addition to a keyword;

a component that identifies, from the sentences of the corpus, keywords within the identified patterns that satisfy a keyword confidence criterion and adds the identified keywords to the keyword store; and

a component that determines whether a termination criterion is satisfied so that the iterative identification of sequence segments, patterns, and keywords is terminated.

10. The computing device of claim 9 including a component that substitutes a keyword symbol for the keywords of the sequence segments.

11. The computing device of claim 9 wherein the component that identifies keywords determines whether a keyword satisfies a keyword confidence criterion that is based on pattern confidence scores of patterns that match sequence segments that contain the keyword.

12. The computing device of claim 9 wherein the component that identifies patterns identifies a pattern when support for the pattern satisfies a pattern support criterion.

13. The computing device of claim 12 wherein the support for a pattern is represented by a pattern support score and the pattern support criterion is a minimum pattern support score needed for the pattern to be considered a candidate pattern.

14. The computing device of claim 9 wherein the component that identifies the patterns applies a sequential pattern mining technique.

15. A computer-readable medium containing instructions for controlling a computing device to identify topic information from a corpus of sentences of words, by a method comprising:

storing an initial set of keywords; and

repeating the steps of

identifying sequence segments of the sentences of the corpus, a sequence segment being a sequence of words that includes a keyword of the stored keywords;

identifying from the identified sequence segments patterns of sequences of words that include a keyword and that satisfy a pattern support criterion by comparing a sequence segment to other sequence segments to determine whether a pattern can be derived from the sequence segments by applying a pattern mining algorithm to the identified sequence segments to identify patterns of words adjacent to the occurrences of the keywords based on comparison of words adjacent to an occurrence of a keyword to words adjacent to other occurrences of keywords to derive patterns from the adjacent words, some of identified patterns including a keyword;

filtering out from the identified patterns the identified patterns that do not include a keyword;

filtering out from the identified patterns the identified patterns that include only prepositions in addition to a keyword;

identifying from the sentences of the corpus keywords within the identified patterns that satisfy a keyword confidence criterion; and

storing the identified keywords

until a termination criterion is satisfied.

16. The computer-readable medium of claim 15 wherein a termination criterion is satisfied when no new patterns are identified.

17. The computer-readable medium of claim 15 wherein an identified pattern further satisfies a pattern confidence criterion.