Method and system for clustering using generalized sentence patterns

• US 20060004561A1
• Filed: 06/30/2004
• Published: 01/05/2006
• 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
• Granted Patent: US 7,584,100 B2
• Time in Patent Office: Days
• US Class Current: 704/4
• 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 for identifying generalized sentence patterns for sentences, the method comprising:

for each sentence, generating a generalized sentence by generalizing parts of speech of the sentence; and

selecting a generalized sentence to be a generalized sentence pattern based on the generalized sentence being a subset of another generalized sentence.

2. The method of claim 1 wherein the generating of a generalized sentence includes building a syntax tree for the sentence and predicting generalizations of the part of speech of the sentence using a statistical language model.

3. The method of claim 1 wherein the generating of a generalized sentence includes using a natural language processor.

4. The method of claim 3 wherein the natural language processor is a NLPWin-based parser.

5. The method of claim 1 wherein the selecting Qf a generalized sentence to be a generalized sentence pattern includes:

calculating a support level for a plurality of the generalized sentences, the support level of a generalized sentence indicating support of that generalized sentence to be a generalized sentence pattern for the generalized sentences; and

selecting a generalized sentence with a high support level to be a generalized sentence pattern.

6. The method of claim 5 wherein the support for a generalized sentence is defined as:

sup(p)=|{s|s∈

Sp⊂

s}|

where sup(p) represents the support of generalized sentence p to be a generalized sentence pattern and s is a generalized sentence in a set of generalized sentences S.

7. The method of claim 6 wherein a generalized sentence is selected to be a generalized sentence pattern when the support is above a threshold support level.

8. The method of claim 1 wherein the selecting of a generalized sentence to be a generalized sentence pattern includes applying a frequent itemset algorithm.

9. The method of claim 8 including removing redundancies from frequent itemsets identified by the frequent itemset algorithm.

10. The method of claim 8 wherein the frequent itemset algorithm identifies frequent itemsets that are closed.

11. The method of claim 1 wherein the sentences are derived from subjects of electronic mail messages.

12. The method of claim 1 wherein the sentences are derived from topics of documents.

13. The method of claim 12 wherein the documents are web pages.

14. A method in a computer system for identifying clusters of documents, the method comprising:

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

selecting identified generalized sentence patterns 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.

15. The method of claim 14 including grouping the identified generalized sentence patterns into groups of generalized sentence patterns based on similarity of the generalized sentence patterns, wherein the groups of generalized sentence patterns are used to guide the identification of clusters.

16. The method of claim 15 wherein similarity is defined as:

sup(p)=|{s|s∈

Sp⊂

s}|

where sup(p) represents the support of generalized sentence p to be a generalized sentence pattern and s is a generalized sentence in the set of sentences S.

17. The method of claim 15 wherein 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.

18. The method of claim 15 wherein the grouping uses a single-link clustering algorithm.

19. The method of claim 15 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.

20. The method of claim 14 wherein the cluster identification algorithm is a constraint-based k-means algorithm.

21. The method of claim 20 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.

22. The method of claim 21 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.

23. The method of claim 14 wherein the cluster identification algorithm is a conditional expectation maximization algorithm.

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

25. The method of claim 23 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.

26. The method of claim 14 wherein the documents are electronic mail messages and the topics are subjects of the electronic mail messages.

27. The method of claim 14 wherein the documents are web pages.

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

29. A method in a computer system for naming clusters of groups of generalized sentence patterns, the method comprising:

when generalized sentences in a cluster match one or more groups of generalized sentence patterns, selecting the generalized sentence pattern from the group with the highest support as the name.

30. The method of claim 29 including:

when generalized sentences in a cluster do not match a group of generalized sentence patterns,

ranking words of documents with the cluster; and

selecting the highest ranked words as the name.

31. The method of claim 29 wherein a generalized sentence matches a group of generalized sentence patterns when a generalized sentence pattern of the group is a subset of the generalized sentence.

32. A computer-readable medium containing instructions for controlling a computer system to identify generalized sentence patterns for sentences, by a method comprising:

for each sentence, generating a generalized sentence by generalizing parts of speech of the sentence; and

selecting a generalized sentence pattern based on the frequency with which the generalized sentence pattern is a subset of a generalized sentence.

33. The computer-readable medium of claim 32 wherein the generating of a generalized sentence includes building a syntax tree for the sentence and predicting generalizations of the part of speech of the sentence using a statistical language model.

34. The computer-readable medium of claim 32 wherein the selecting of a generalized sentence pattern includes:

calculating a support level for a plurality of the generalized sentences, the support level of a generalized sentence indicating support of that generalized sentence to be a generalized sentence pattern for the generalized sentences; and

selecting a generalized sentence with a high support level to be a generalized sentence pattern.

35. The computer-readable medium of claim 32 wherein the selecting of a generalized sentence to be a generalized sentence pattern includes applying a frequent itemset algorithm.

36. A computer-readable medium containing instructions for controlling a computer system to identify clusters of documents, by a method comprising:

identifying generalized sentence patterns for sentences, each sentence representing a document; and

identifying clusters of documents using the identified generalized sentence patterns to guide the identification of clusters.

37. The computer-readable medium of claim 36 including grouping the identified generalized sentence patterns into groups of generalized sentence patterns based on similarity of the generalized sentence patterns, wherein the groups of generalized sentence patterns are used to guide the identification of clusters.

38. The computer-readable medium of claim 36 wherein the clusters are identified using a conditional expectation maximization algorithm.

39. The computer-readable medium of claim 38 wherein a support vector machine is a classifier for the conditional expectation maximization algorithm.

40. The computer-readable medium of claim 36 wherein the clusters are identified using a constraint-based k-means algorithm.