Extracting topically related keywords from related documents

• US 8,463,786 B2
• Filed: 06/10/2010
• Issued: 06/11/2013
• Est. Priority Date: 06/10/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Udupa, Uppinakuduru Raghavendra, Vysyaraju, Santosh Raju
• Primary Examiner(s): AL HASHEMI, SANA A
• Application Number:
  US12/813,037
• Publication Number:
  US 20110307485A1
• Time in Patent Office: 1,097 Days
• Field of Search: 707/737, 707/722, 707/748, 707/795, 707/708, 707/804
• US Class Current: 707/737
• CPC Class Codes: G06F 16/367 Ontology
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

Keyword extraction technique embodiments are presented which extract topically related keywords from a set of topically related documents. In one general embodiment, this keyword extraction involves first accessing a set of topically related documents. A number of candidate keywords are then identified from the set of related documents. A weighted keyword candidate-document matrix is formed using these candidate keywords, and it is partitioned into multiple groups of keyword candidates. Dense clusters of keyword candidates whose density exceeds a prescribed density threshold are then identified in each of the groups of keyword candidates. Finally, the keyword candidates associated with each dense cluster are designated as topically related keywords.

Claims

1. A computer-implemented process for extracting topically related keywords from topically related documents, comprising:

using a computer to perform the following process actions;

accessing a set of topically related documents;

identifying a number of candidate keywords from the set of related documents, wherein a candidate keyword can be an individual term or a multiple word phrase;

forming a weighted keyword candidate-document matrix using the candidate keywords;

partitioning the keyword candidate-document matrix into multiple groups of keyword candidates;

identifying dense clusters of keyword candidates in each of the groups of keyword candidates whose density exceeds a prescribed density threshold, said keyword candidate cluster density for a group of keyword candidates being based on co-occurrences of keyword candidates belonging to the group in documents from the set of related documents; and

for each of the identified dense clusters,

designating the keyword candidates associated with that cluster as topically related keywords, and

extracting the topically related keywords from the set of topically related documents.

2. The process of claim 1, wherein the process action of accessing a set of topically related documents comprises an action of accessing documents identified in a prescribed number of the top ranking search results found in one or more searches based on a search query pertaining a topic of interest.

3. The process of claim 2, wherein the search query is provided by a user.

4. The process of claim 2, wherein the search results are provided by a user.

5. The process of claim 2, wherein the search query is constructed using a Uniform Resource Locator (URL) corresponding to a user-supplied document or a document a user is accessing.

6. The process of claim 5, wherein the search query is constructed using a title of the document.

7. The process of claim 5, wherein the search query is constructed using all or a part of the URL string of the document.

8. The process of claim 1, wherein the process action of identifying candidate keywords from the set of related documents, comprises an action of using a controlled vocabulary, wherein the controlled vocabulary comprises a list of keywords believed to be relevant to a topic of interest associated with the set of related document, and wherein only terms and phrases found in the set of related documents that are included in the controlled vocabulary are identified as candidate keywords.

9. The process of claim 8, wherein the process action of using a controlled vocabulary, comprises an action of obtaining the controlled vocabulary, said obtaining comprising searching an encyclopedia-type site using a search query pertaining said topic of interest and employing a prescribed number of top ranking articles returned as search results to establish the controlled vocabulary.

10. The process of claim 9, wherein titles of said articles are employed to establish the controlled vocabulary.

11. The process of claim 8, wherein the process action of using a controlled vocabulary, comprises obtaining an advertisement dictionary and employing the terms and phrases included therein as the controlled vocabulary.

12. The process of claim 8, wherein the process action of using a controlled vocabulary, comprises an action of obtaining the controlled vocabulary, said obtaining comprising identifying search queries used in previous searches that produced search results identifying one or more of the documents in the set of related document, and employing the identified search queries to establish the controlled vocabulary.

13. The process of claim 1, wherein the process action of forming a weighted keyword candidate-document matrix using the candidate keywords, comprises for each keyword candidate-document pair in the matrix assigning an element weight computed as the product of an importance factor representing a prescribed degree of importance assigned to the keyword candidate of the pair, and a computed frequency factor representing a measure of the frequency that the keyword candidate of the pair appears in the document of the pair.

14. The process of claim 13, wherein computing the frequency factor comprises computing the quotient of the number of times the keyword candidate of the pair appears in the document of the pair, divided by the sum of the number of times each of the candidate keywords appears in the document of the pair.

15. The process of claim 1, wherein the process action of partitioning the keyword candidate-document matrix into multiple groups of keyword candidates, comprises employing a spectral partitioning technique.

16. The process of claim 15, wherein the spectral partitioning technique is employed to partition the matrix into two groups of keyword candidates.

17. The process of claim 1, wherein the process action of identifying clusters of keyword candidates in each of the groups of keyword candidates, comprises the action of:

constructing a co-occurrence graph in the form of a weighted undirected graph comprising vertices and edges, wherein each vertex represents a different one of the candidate keywords and each edge connects a pair of vertices whose corresponding candidate keywords co-occur in at least one of the documents in the set of related documents, and wherein a weight is assigned to each edge which represents the number of documents in which the candidate keywords associated with the connected vertices co-occur;

discarding each edge whose assigned weight does not exceed a prescribed minimum edge weight threshold;

eliminating the candidate keyword associated with each vertex, if any, that is not connected to at least one other vertex by an edge, from consideration as a related keyword;

designating each group of interconnected vertices as a sub-graph;

for each sub-graph,

computing the density of the sub-graph,

determining if the sub-graph density exceeds a prescribed density threshold, and

designating the sub-graph as a dense cluster of keyword candidates whenever its density exceeds the prescribed density threshold.

18. The process of claim 17, wherein the process action of computing the density of a sub-graph, comprises:

for each vertex of the sub-graph,

identifying the edges connected to the vertex under consideration,

for each identified edge, computing the difference between the weight assigned to that edge and the prescribed minimum edge weight threshold, and

summing the computed differences to establish a vertex sum for the vertex under consideration; and

summing the vertex sums computed for the vertices of the sub-graph.

19. A computer-readable computer storage medium having computer-executable instructions for performing the process actions recited in claim 1.

20. A system for extracting topically related keywords from topically related documents, comprising:

a general purpose computing device; and

a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to,

access a set of topically related documents,

extract a number of candidate keywords from the set of related documents using a controlled vocabulary, wherein the controlled vocabulary comprises a list of keywords believed to be relevant to a topic of interest associated with the set of related document, and wherein only terms and phrases found in the set of related documents that are included in the controlled vocabulary are identified as candidate keywords,

form a weighted keyword candidate-document matrix using the candidate keywords, and partition the matrix into multiple groups of keyword candidates using a spectral partitioning technique,

identify dense clusters of keyword candidates in each of the groups of keyword candidates whose density exceeds a prescribed density threshold, said keyword candidate cluster density for a group of keyword candidates being based on co-occurrences of keyword candidates belonging to the group in documents from the set of related documents, and

for each of the identified dense clusters,

designate the keyword candidates associated with that cluster as topically related keywords, and

extract the topically related keywords from the set of topically related documents.