Method and system for clustering using generalized sentence patterns

• US 7,584,100 B2
• Filed: 06/30/2004
• Issued: 09/01/2009
• Est. Priority Date: 06/30/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ma, Wei-Ying, Chen, Zheng, Zhang, Benyu, Zeng, Hua-Jun
• Primary Examiner(s): Hudspeth; David R
• Assistant Examiner(s): Rider; Justin W
• Application Number:
  US10/880,662
• Publication Number:
  US 20060004561A1
• Time in Patent Office: 1,889 Days
• Field of Search: 704/245
• US Class Current: 704/245
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A method and system for clustering documents based on generalized sentence patterns of the topics of the documents is provided. A generalized sentence patterns (“GSP”) system identifies a “sentence” that describes the topic of a document. To cluster documents, the GSP system generates a “generalized sentence” form of the sentence that describes the topic of each document. The generalized sentence is an abstraction of the words of the sentence. The GSP system identifies clusters of documents based on the patterns of their generalized sentences. The GSP system clusters documents when the generalized sentence representations of their topics have a similar pattern.

Claims

1. A method in a computer system with a processor and memory for identifying clusters of documents, the method comprising:

providing sentences having words, each sentence representing a topic of a document;

for each sentence representing the topic of a document, identifying a generalized sentence for the sentence, the generalized sentence representing a generalization of words of the sentence, a generalization including a part of speech of a word;

identifying by the processor generalized sentence patterns for the identified generalized sentences, each generalized sentence pattern representing a pattern of generalizations of the generalized sentences;

grouping the identified generalized sentence patterns into groups of generalized sentence patterns based on similarity of the generalized sentence patterns;

selecting identified generalized sentence patterns to guide the identification of clusters wherein the groups of generalized sentence patterns are used to guide the identification of clusters; and

applying a cluster identification algorithm to identify clusters of documents using the selected generalized sentence patterns to guide the identification such that documents whose generalized sentences are similar to the same generalized sentence pattern are identified as being in the same cluster

wherein similarity of generalized sentence patterns is defined as;

2. The method of claim 1 generalized sentence patterns are similar when one generalized sentence pattern is a subset of another generalized sentence pattern and the ratio of support for the other generalized sentence pattern to support for the generalized sentence pattern is greater than a minimum threshold.

3. The method of claim 1 wherein the grouping uses a single-link clustering algorithm.

4. The method of claim 1 wherein groups of generalized sentence patterns are selected for guiding the identification of clusters based on length and support of generalized sentence patterns in each group.

5. The method of claim 1 wherein the documents are electronic mail messages and the topics are subjects of the electronic mail messages.

6. The method of claim 1 wherein the documents are web pages.

7. The method of claim 1 including automatically selecting a name for a cluster based on generalized sentence patterns of the cluster.

8. A method in a computer system with a processor and memory for identifying clusters of documents, the method comprising:

identifying by the processor generalized sentence patterns for sentences, each sentence representing a document;

grouping the identified generalized sentence patterns into groups of generalized sentence patterns based on similarity of the generalized sentence patterns;

selecting identified generalized sentence patterns to guide the identification of clusters wherein the groups of generalized sentence patterns are used to guide the identification of clusters; and

applying a cluster identification algorithm to identify clusters using the selected generalized sentence patterns to guide the identification

wherein the cluster identification algorithm is a constraint-based k-means algorithm and

wherein similarity of generalized sentence patterns is defined as;

9. The method of claim 8 wherein a constraint is that when two generalized sentences match a group of generalized sentence patterns, the two generalized sentences are in the same cluster.

10. The method of claim 9 wherein a generalized sentence matches a group of generalized sentence patterns when the generalized sentence is a superset of a generalized sentence pattern of the group.

11. A method in a computer system with a processor and memory for identifying clusters of documents, the method comprising:

identifying by the processor generalized sentence patterns for sentences, each sentence representing a document;

grouping the identified generalized sentence patterns into groups of generalized sentence patterns based on similarity of the generalized sentence patterns;

selecting identified generalized sentence patterns to guide the identification of clusters wherein the groups of generalized sentence patterns are used to guide the identification of clusters; and

applying a cluster identification algorithm to identify clusters using the selected generalized sentence patterns to guide the identification

wherein the cluster identification algorithm is a conditional expectation maximization algorithm and

wherein similarity of generalized sentence patterns is defined as;

12. The method of claim 11 wherein a support vector machine is a classifier for the conditional expectation maximization algorithm.

13. The method of claim 11 including upon completion of iterations of the conditional expectation maximization algorithm, applying a k-means algorithm to generate clusters for generalized sentence patterns that are not classified.