Measuring topical coherence of keyword sets

• US 8,577,930 B2
• Filed: 08/20/2008
• Issued: 11/05/2013
• Est. Priority Date: 08/20/2008
• Status: Expired due to Fees

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Rajan, Suju, Gaffney, Scott J.
• Primary Examiner(s): Fleurantin, Jean B
• Application Number:
  US12/195,068
• Publication Number:
  US 20100049504A1
• Time in Patent Office: 1,903 Days
• Field of Search: 707/713, 707/765, 707/766, 707/769, 707/770, 707/804, 709/224, 709/225, 709/226, 711/150
• US Class Current: 707/804
• CPC Class Codes: G06F 16/358 Browsing; Visualisation therefor
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06Q 30/0257 User requested
• CPC Class Codes: G06Q 30/0277 Online advertisement
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

Methods and apparatus are described for measuring the topical coherence of a keyword set while simultaneously partitioning the set into contextually related clusters.

Claims

1. A computer-implemented method comprising:

expanding by a processor a text string set including a plurality of text strings using search results generated in response to at least one search query including the plurality of text strings thereby resulting in an expanded text string set;

identifying frequent itemsets in the expanded text string set;

developing a vocabulary for the text string set including selected ones of the frequent itemsets;

calculating a similarity measure for each pair of the selected frequent itemsets in the vocabulary; and

generating a topical coherence measure for the text string set with reference to the similarity measures, the topical coherence measure representing topical similarity among the plurality of text strings in the text string set.

2. The method of claim 1 wherein expanding the text string set comprises processing the search results to remove low relevance terms.

3. The method of claim 1 wherein identifying frequent itemsets comprises employing a clustering technique on the expanded text string set.

4. The method of claim 1 further comprising iteratively developing the vocabulary for each itemset having a support level above a threshold.

5. The method of claim 1 wherein each frequent itemset corresponds to a cluster of text strings within the text string set, the method further comprising identifying the cluster of text strings for each of the frequent itemsets.

6. The method of claim 5 wherein the text string set comprises advertising keywords for use in sponsored search advertising, the method further comprising initiating an advertising campaign using at least some of the clusters of text strings.

7. The method of claim 5 further comprising identifying a topic descriptor for each cluster of text strings identified, the topic descriptor being derived from the frequent itemset corresponding to the cluster.

8. The method of claim 1 further comprising identifying outlier text strings in conjunction with identification of the frequent itemsets.

9. The method of claim 1 wherein the text string set represents an ad group comprising advertiser keywords and a landing page, and the topical coherence measure represents a quality measure for the ad group, the method further comprising deriving landing page keywords for inclusion in the text string set, the landing page keywords representing a purpose of the landing page.

10. The method of claim 1 wherein the text string set comprises advertising keywords for use in sponsored search advertising.

11. The method of claim 1 wherein the similarity measure for each pair of the selected frequent itemsets comprises a cosine similarity measure.

12. At least one non-transitory computer-readable medium having computer program instructions stored therein, the computer program instructions being configured to enable at least one computing device to perform steps, comprising:

expand a text string set including a plurality of text strings using search results generated in response to at least one search query including the plurality of text strings thereby resulting in an expanded text string set;

identify frequent itemsets in the expanded text string set;

develop a vocabulary for the text string set including selected ones of the frequent itemsets;

calculate a similarity measure for each pair of the selected frequent itemsets in the vocabulary; and

generate a topical coherence measure for the text string set with reference to the similarity measures, the topical coherence measure representing topical similarity among the plurality of text strings.

13. The computer program product of claim 12 wherein the computer program instructions are configured to enable the at least one computing device to expand the text string set by processing the search results to remove low relevance terms.

14. The computer program product of claim 12 wherein the computer program instructions are configured to enable the at least one computing device to identify frequent itemsets using a clustering technique on the expanded text string set.

15. The computer program product of claim 12 wherein the computer program instructions are further configured to enable the at least one computing device to iterate developing the vocabulary for each itemset having a support level above a threshold.

16. The computer program product of claim 12 wherein each frequent itemset corresponds to a cluster of text strings within the text string set, and wherein the computer program instructions are configured to enable the at least one computing device to identify the cluster of text strings for each of the frequent itemsets.

17. The computer program product of claim 16 wherein the computer program instructions are further configured to enable the at least one computing device to identify a topic descriptor for each cluster of text strings identified, the topic descriptor being derived from the frequent itemset corresponding to the cluster.

18. The computer program product of claim 12 wherein the computer program instructions are further configured to enable the at least one computing device to identify outlier text strings in conjunction with identification of the frequent itemsets.

19. The computer program product of claim 12 wherein the similarity measure for each pair of the selected frequent itemsets comprises a cosine similarity measure.

20. A computer-implemented method comprising:

identifying a plurality of sponsored search advertisements in response to a search query from a user, each of the sponsored search advertisements having a keyword set associated therewith;

ranking by a processor each of the plurality of sponsored search advertisements with reference to a topical coherence measure for the associated keyword set, the topical coherence measure representing a topical similarity among keywords in the keyword set; and

transmitting the sponsored search advertisements for presentation to the user in accordance with the ranking, of the plurality of sponsored search advertisements with reference to the topical coherence measure.