Extracting product purchase information from electronic messages

• US 9,875,486 B2
• Filed: 10/21/2014
• Issued: 01/23/2018
• Est. Priority Date: 10/21/2014
• Status: Active Grant

• Current Assignee: Nielsen Consumer LLC (Nielsen Holdings plc)
• Original Assignee: Slice Technologies, Inc. (Rakuten Group, Inc.)
• Inventors: Mastierov, Ievgen, Sathi, Conal
• Primary Examiner(s): Long, Meredith A
• Application Number:
  US14/519,975
• Publication Number:
  US 20160110763A1
• Time in Patent Office: 1,190 Days
• Field of Search: None
• CPC Class Codes: G06Q 30/0255 based on user history
• CPC Class Codes: G06Q 30/0269 based on user profile or attribute

Abstract

Improved systems and methods for extracting product purchase information from electronic messages transmitted between physical network nodes to convey product purchase information to designated recipients. These examples provide a product purchase information extraction service that is able to extract product purchase information from electronic messages with high precision across a wide variety of electronic message formats and thereby solve the practical problems that have arisen as a result of the proliferation of different electronic message formats used by individual merchants and across different merchants and different languages. In this regard, these examples are able to automatically learn the structures and semantics of different message formats, which accelerates the ability to support new message sources, new markets, and different languages.

Claims

1. A method, comprising,

by computer apparatus:

grouping electronic messages into respective clusters based on similarities between the electronic messages;

for each of one or more of the clusters, extracting a respective grammar defining a respective arrangement of structural elements of the electronic messages in the cluster, wherein the extracting comprises, for each of the one or more clusters,

in non-transitory computer-readable memory, building a respective generalized suffix tree representation from a concatenation of tokenized contents of electronic messages in the cluster into a single respective string, wherein the generalized suffix tree representation maintains the order of suffixes from the single respective string in a hierarchical tree structure of nodes that are linearly interconnected from root to leaf node and, for each suffix, identifies the electronic messages in which the suffix appears and a respective count of times the suffix appears in each electronic message in the cluster, and

traversing the respective generalized suffix tree, wherein the traversing comprises ascertaining the respective arrangement of structural elements for the respective grammar based on appearance frequencies of substrings in the electronic messages in the cluster;

based on training data comprising training data fields, building one or more classifiers that classify field tokens extracted from selected electronic messages with respective product purchase relevant labels based on correspondences between tokens extracted from the selected electronic messages and the structural elements of the grammars respectively matched to the selected electronic messages; and

in non-transitory computer-readable memory, storing the grammars and the one or more classifiers in one or more data structures associated with a parser executable by a processor to parse product purchase information from electronic messages.

2. The method of claim 1, wherein the grouping comprises:

for each of the electronic messages, identifying a message sender of the electronic message;

sorting the electronic messages into groups by message sender, wherein each message sender is associated with a respective one of the groups of electronic messages; and

for each group, clustering the electronic messages within the group into one or more clusters based on similarities between the electronic messages.

3. The method of claim 2, wherein the clustering comprises clustering electronic messages based on measures of content similarity between pairs of the electronic messages.

4. The method of claim 3, wherein the clustering comprises:

for each electronic message, extracting content from lines of the electronic message; and

measuring similarities between electronic messages based on line-based comparisons of the extracted content.

5. The method of claim 3, wherein the measures of content similarity compare similarity and diversity of the contents of the selected electronic message and contents of a respective one of the electronic messages of the associated cluster.

6. The method of claim 1, wherein, for each cluster:

the traversing comprises generating a list of substrings of symbols contained in the contents of the electronic messages in the cluster, and indications of the occurrence frequencies of the substrings; and

the ascertaining comprises designating respective ones of the substrings as structural elements of the electronic messages in the cluster based on the respective occurrence frequencies of the substrings.

7. The method of claim 6, wherein, for each cluster:

the ascertaining comprises labeling respective ones of the substrings that appear in all the electronic messages of the cluster as static structural elements.

8. The method of claim 6, wherein, for each cluster:

the ascertaining comprises labeling respective ones of the substrings that appear in all the electronic messages of the cluster and repeat in multiple of the electronic messages of the cluster as iterating static structural elements.

9. The method of claim 6, wherein, for each cluster:

the ascertaining comprises labeling respective ones of the substrings that appear in a majority but less than all of the electronic messages of the cluster as optional structural elements.

10. The method of claim 6, further comprising denominating non-structural-element ones of the substrings as respective non-structural field tokens of the electronic messages in the cluster.

11. The method of claim 1, wherein, for at least one of the one or more classifiers and at least one of the data fields to be labeled, ones of the features correspond to two-word phrases extracted from the sequences of tokens in respective ones of the electronic messages in the respective training set that precede the data field and correspond to structural elements of the respective grammar.

12. The method of claim 1, wherein, for at least one of the one or more classifiers, the building comprises training the classifier to classify price related field tokens in the selected electronic message with a respective price label in a predetermined price field labeling taxonomy.

13. The method of claim 1, wherein, for at least one of the one or more classifiers, the building comprises training the classifier to classify identifier related field tokens in the selected electronic message with a respective identifier label in a predetermined identifier field labeling taxonomy.

14. The method of claim 13, wherein, for the at least one classifier, the training comprises training the classifier to classify an identifier related field token extracted from the selected electronic message based on features comprising (i) a token extracted from the selected electronic message that corresponds to a static structural element of the respective grammar and immediately precedes the identifier related field token in the selected electronic message, and (ii) characteristics of the identifier related field token.

15. The method of claim 1, wherein, for at least one of the one or more classifiers, the building comprises training the classifier to classify item description related field tokens in the selected electronic message as item descriptions based on comparisons between features of the item description related field tokens and features of known item descriptions.

16. The method of claim 1, further comprising

by a processor, executing the processor-executable parser to perform operations comprising parsing tokens extracted from an electronic message according to a respective one of the grammars and applying at least one of the one or more classifiers to label respective ones of the parsed tokens.

17. The method of claim 1, wherein each stored grammar preserves the arrangement of structural elements in the respective generalized suffix tree.

18. Apparatus, comprising a memory storing processor-readable instructions, and a processor coupled to the memory, operable to execute the instructions, and based at least in part on the execution of the instructions operable to perform operations comprising:

grouping electronic messages into respective clusters based on similarities between the electronic messages;

for each of one or more of the clusters, extracting a respective grammar defining a respective arrangement of structural elements of the electronic messages in the cluster, wherein the extracting comprises, for each of the one or more clusters,

in non-transitory computer-readable memory, building a respective generalized suffix tree representation from a concatenation of tokenized contents of electronic messages in the cluster into a single respective string, wherein the generalized suffix tree representation maintains the order of suffixes from the single respective string in a hierarchical tree structure of nodes that are lineally interconnected from root to leaf node and, for each suffix, identifies the electronic messages in which the suffix appears and a respective count of times the suffix appears in each electronic message in the cluster, and

traversing the respective generalized suffix tree, wherein the traversing comprises ascertaining the respective arrangement of structural elements for the respective grammar based on appearance frequencies of substrings in the electronic messages in the cluster;

based on training data comprising training data fields, building one or more classifiers that classify field tokens extracted from selected electronic messages with respective product purchase relevant labels based on correspondences between tokens extracted from the selected electronic messages and the structural elements of the grammars respectively matched to the selected electronic messages; and

in non-transitory computer-readable memory, storing the grammars and the at least one classifier in one or more data structures associated with a parser executable by a processor to parse product purchase information from electronic messages.

19. At least one non-transitory computer-readable medium having processor-readable program code embodied therein, the processor-readable program code adapted to be executed by a processor to implement a method comprising:

grouping electronic messages into respective clusters based on similarities between the electronic messages;

for each of one or more of the clusters, extracting a respective grammar defining a respective arrangement of structural elements of the electronic messages in the cluster, wherein the extracting comprises, for each of the one or more clusters,

in non-transitory computer-readable memory, building a respective generalized suffix tree representation from a concatenation of tokenized contents of electronic messages in the cluster into a single respective string, wherein the generalized suffix tree representation maintains the order of suffixes from the single respective string in a hierarchical tree structure of nodes that are linearly interconnected from root to leaf node and, for each suffix, identifies the electronic messages in which the suffix appears and a respective count of times the suffix appears in each electronic message in the cluster, and

traversing the respective generalized suffix tree, wherein the traversing comprises ascertaining the respective arrangement of structural elements for the respective grammar based on appearance frequencies of substrings in the electronic messages in the cluster;

based on training data comprising training data fields, building one or more classifiers that classify field tokens extracted from selected electronic messages with respective product purchase relevant labels based on correspondences between tokens extracted from the selected electronic messages and the structural elements of the grammars respectively matched to the selected electronic messages; and

in non-transitory computer-readable memory, storing the grammars and the one or more classifiers in one or more data structures associated with a parser executable by a processor to parse product purchase information from electronic messages.

20. Apparatus, comprising at least one non-transitory memory storing processor-readable instructions, and at least one processor coupled to the memory, operable to execute the instructions, and based at least in part on the execution of the instructions operable to implement:

a product purchase information grammar extractor operable by a processor to group electronic messages into respective clusters based on similarities between the electronic messages, and

for each of one or more of the clusters, extract a respective grammar defining a respective arrangement of structural elements of the electronic messages in the cluster wherein, for each of the one or more clusters,

a respective generalized suffix tree representation is built in non-transitory computer-readable memory from a concatenation of tokenized contents of electronic messages in the cluster into a single respective string, wherein the generalized suffix tree representation maintains the order of suffixes from the single respective string in a hierarchical tree structure of nodes that are linearly interconnected from root to leaf node and, for each suffix, identities the electronic messages in which the suffix appears and a respective count of times the suffix appears in each electronic message in the cluster, and

the respective generalized suffix tree is traversed to ascertain the respective arrangement of structural elements for the respective grammar based on appearance frequencies of substrings in the electronic message in the cluster;

a product purchase information token classifier trainer operable by a processor to build, based on training data comprising training data fields, one or more classifiers that classify field tokens extracted from selected electronic messages with respective product purchase relevant labels based on correspondences between tokens extracted from the selected electronic messages and the structural elements of the grammars respectively matched to the selected electronic messages; and

a processor-executable electronic message parser stored in non-transitory computer-readable memory and executable by a processor to extract purchase-related information from purchase related electronic messages and, according to at least one of the one or more classifiers, ascertain respective product purchase relevant labels for the extracted purchase-related information based on associations between the clusters and the respective grammars that are stored in non-transitory computer-readable memory.