Clustering communications based on classification

• US 10,007,717 B2
• Filed: 09/18/2014
• Issued: 06/26/2018
• Est. Priority Date: 09/18/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Zhang, Xincheng, Tan, Hui, Wang, Zhiyu, Lou, Jinan
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Cheung, Hubert
• Application Number:
  US14/414,855
• Publication Number:
  US 20160314182A1
• Time in Patent Office: 1,377 Days
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: H04L 43/04 Processing captured monitoring data, e.g. for logfile generation

Abstract

Methods and apparatus related to clustering documents based on one or more classification terms and optionally based on similarity of structural paths of the documents. In some implementations, the documents are communications such as structured emails or other structured communications. In some of those implementations, clustering the communications includes identifying a plurality of classification terms indicative of a classification, identifying a corpus of communications that includes communications that are not labeled with an association to the classification, and determining a cluster of the communications based on occurrence of one or more of the classification terms in the communications of the cluster.

Claims

1. A computer implemented method, comprising:

identifying a plurality of classification terms indicative of a classification;

identifying a corpus of communications from one or more databases, the corpus of communications including a plurality of communications that are not labeled with an association to the classification;

determining a cluster of the communications based on occurrence of one or more of the classification terms in the communications of the cluster;

subsequent to determining the cluster, determining a feature set based on the communications of the cluster, wherein determining the feature set comprises;

determining one or more features that are based on content that appears in a plurality of the communications of the cluster,

wherein the content is in addition to the classification terms used in determining the cluster, and

wherein determining the features based on the content that is in addition to the classification terms comprises determining the features based on the content appearing in the plurality of the communications of the cluster;

assigning the feature set to an indication of the classification; and

using the assigned feature set to classify an additional communication with the classification or using the assigned feature set to select a data extraction parser, for the classification, for the additional communication.

2. The computer implemented method of claim 1, wherein the communications of the cluster include structured communications that are each structured using a given markup language, wherein the given markup language is eXtensible Markup Language or Hypertext Markup Language, and wherein determining the cluster of the communications is further based on similarity of structural paths of the structured communications of the cluster, the structural paths each referencing an address to reach a node, of the given markup language, in a corresponding structured communication.

3. The computer implemented method of claim 2, wherein determining the feature set comprises:

determining structural features of the features based on the structural paths of the structured communications of the cluster, the structural features indicating at least one of;

hierarchical structure of the structural paths, and node types of the nodes of the structural paths.

4. The computer implemented method of claim 3, wherein determining the feature set comprises:

determining term features of the features based on communication terms of the structured communications of the cluster;

wherein one or more of the communication terms on which the term features are determined are in addition to the classification terms.

5. The computer implemented method of claim 1, wherein determining the feature set comprises:

determining term features of the features based on communication terms of the communications of the cluster;

wherein one or more of the communication terms on which the term features are determined are in addition to the classification terms.

6. The computer implemented method of claim 1, wherein the communications of the cluster include structured communications that are each structured using a given markup language, wherein the given markup language is eXtensible Markup Language or Hypertext Markup Language, and wherein determining the feature set comprises:

determining term features of the features based on communication terms of the structured communications of the cluster and structural paths of the structured communications of the cluster, wherein the structural paths each reference an address to reach a node, of the given markup language, in a corresponding structured communication, and wherein each of the term features is indicative of a term of the communication terms and one or more of the structural paths in which the term appears in the structured communications of the given cluster.

7. The computer implemented method of claim 1, wherein the communications of the cluster are from a plurality of sending entities.

8. The computer implemented method of claim 1, wherein identifying the classification terms indicative of the classification comprises:

identifying one or more labeled communications having labels indicating the classification; and

determining one or more of the classification terms based on the labeled communications.

9. The computer implemented method of claim 8, wherein the labels indicating the classification are based on names of inbox subfolders with which the labeled communications are associated.

10. The computer implemented method of claim 8, wherein the labels indicating the classification are based on annotations of the labeled communications by users that received the labeled communications.

11. The computer implemented method of claim 8, wherein determining the one or more of the classification terms based on the labeled communications comprises:

selecting a term of the classification terms based on comparison of a frequency of occurrence of the term in the labeled communications to a frequency of occurrence of the term in a larger corpus of documents.

12. The computer implemented method of claim 1, wherein the communications are emails.

13. The computer implemented method of claim 1, further comprising:

identifying the additional communication; and

determining the additional communication is associated with the indication of the classification based on comparing the feature set to content of the additional communication.

14. The computer implemented method of claim 13, wherein the indication of the classification is an indication of the data extraction parser for that classification, and further comprising:

selecting the data extraction parser for parsing the additional communication.

15. The computer implemented method of claim 14, wherein the data extraction parser is configured based on the communications of the given cluster.

16. The computer implemented method of claim 14, further comprising:

classifying structural paths of the communications of the cluster as transient based on text, in the communications of the cluster, corresponding to those structural paths satisfying a criterion; and

configuring the data extraction parser to extract data from the structural paths classified as transient.

17. The computer implemented method of claim 1, wherein the communications of the cluster include structured communications, and wherein determining the cluster of the communications is further based on hierarchical structure of structural paths of the structured communications of the cluster, the structural paths being structural paths of eXtensible Markup Language or Hypertext Markup Language.

18. The computer implemented method of claim 1, wherein the communications of the cluster include structured communications, and wherein determining the feature set comprises:

determining structural features of the features based on hierarchical structure of structural paths of the structured communications of the cluster, the structural paths being structural paths of eXtensible Markup Language or Hypertext Markup Language.

19. The computer implemented method of claim 1, wherein determining the feature set further comprises:

determining a weight, for a given feature of the features, based on a quantity, of the communications of the cluster, in which given content of the content, appears; and

including the weight for the given feature in the feature set.

20. The computer implemented method of claim 1, wherein determining the feature set further comprises:

determining a weight, for given content of the content, based on a quantity, of the communications of the cluster, in which the given content appears; and

based on the weight satisfying a threshold;

including a given feature that corresponds to the given content in the feature set, the given feature being one of the features.

21. A system including memory and one or more processors configured to execute instructions stored in the memory, comprising instructions to:

identify a plurality of classification terms indicative of a classification;

identify a corpus of communications from one or more databases, the corpus of communications including a plurality of communications that are not labeled with an association to the classification;

determine a cluster of the communications based on occurrence of one or more of the classification terms in the communications of the cluster;

subsequent to determining the cluster, determine a feature set based on the communications of the cluster, wherein the instructions to determine the feature set comprise instructions to determine one or more features that are based on content that appears in a plurality of the communications of the cluster,

wherein the content is in addition to the classification terms used in determining the cluster, and

wherein the instructions to determine the features based on the content that is in addition to the classification terms include instructions to determine the content based on the content appearing in the plurality of the communications of the cluster;

assign the feature set to an indication of the classification; and

using the assigned feature set to classify an additional communication with the classification or using the assigned feature set to select a data extraction parser, for the classification, for the additional communication.

22. The system of claim 21, wherein the communications of the cluster include structured communications that are each structured using a corresponding markup language, and wherein the instructions to determine the cluster of the communications further include instructions to determine the cluster based on similarity of structural paths of the structured communications of the cluster.

23. The system of claim 22, wherein the instructions to determine the feature set comprise instructions to:

determine structural features of the features based on the structural paths of the structured communications of the cluster, the structural features indicating hierarchical structure of the structural paths.

24. The system of claim 23, wherein the instructions to determine the feature set comprise instructions to:

determine term features of the features based on communication terms of the structured communications of the cluster;

wherein one or more of the communication terms on which the term features are determined are in addition to the classification terms.

25. The system of claim 21, wherein the instructions to determine the feature set comprise instructions to:

determine term features of the features based on communication terms of the communications of the cluster;

wherein one or more of the communication terms on which the term features are determined are in addition to the classification terms.