Method and apparatus for recommendation engine using pair-wise co-occurrence consistency

• US 7,801,843 B2
• Filed: 01/06/2006
• Issued: 09/21/2010
• Est. Priority Date: 10/21/2005
• Status: Active Grant

• Current Assignee: Fair Isaac Corporation
• Original Assignee: Fair Isaac Corporation
• Inventors: Momma, Michinari, Kumar, Shailesh, Chow, Edmond D.
• Primary Examiner(s): Sparks; Donald
• Assistant Examiner(s): COUGHLAN, PETER D
• Application Number:
  US11/327,822
• Publication Number:
  US 20070094066A1
• Time in Patent Office: 1,719 Days
• Field of Search: 705/10, 706/61
• US Class Current: 706/61
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0201 Market modelling; Market analysis; Collecting market data
• CPC Class Codes: G06Q 30/0202 Market predictions or forecasting for commercial activities
• CPC Class Codes: G06Q 30/0204 Market segmentation
• CPC Class Codes: G06Q 30/0224 based on user history
• CPC Class Codes: G06Q 30/06 Buying, selling or leasing transactions
• CPC Class Codes: G06Q 30/0605 Supply or demand aggregation

Abstract

The invention, referred to herein as PeaCoCk, uses a unique blend of technologies from statistics, information theory, and graph theory to quantify and discover patterns in relationships between entities, such as products and customers, as evidenced by purchase behavior. In contrast to traditional purchase-frequency based market basket analysis techniques, such as association rules which mostly generate obvious and spurious associations, PeaCoCk employs information-theoretic notions of consistency and similarity, which allows robust statistical analysis of the true, statistically significant, and logical associations between products. Therefore, PeaCoCk lends itself to reliable, robust predictive analytics based on purchase-behavior.

Claims

1. An article comprising a tangible machine-readable storage medium embodying instructions that when performed by one or more processors result in operations comprising:

selecting a transaction data slice based on a customization parameter, the transactional data slice corresponding to a plurality of entities, the transaction data slice characterizing a time stamped sequence of market baskets, each market basket characterizing a transaction of a set of one or more products;

generating pair-wise relationships between entities in the selected transaction data slice based on a context parameter, each pair-wise relationship linking two entities to each other;

determining a strength value of each pair-wise relationship, the strength value corresponding to a consistency parameter;

transforming data corresponding to at least one pair-wise relationship and at least one strength value into a recommendation; and

initiating a visual presentation of the recommendation in the form of a graph comprising a plurality of nodes and edges, the nodes corresponding to entities and the edges corresponding to strength values, a structure of the graph being selected from a group comprising;

(a) a sub-graph comprising a subset of a graph, created by picking a subset of nodes and edges from an original graph, the sub-graph selected from a group comprising (i) node based sub-graphs which are created by selecting a subset of the nodes and by keeping only those edges between selected nodes, and (ii) edge based sub-graphs which are created by pruning a set of edges from the graph and removing all nodes that are rendered disconnected from the graph;

(b) a neighborhood of a target product comprising a sub-graph that contains the target product and all the products that are connected to the target product with consistency strength above a predefined threshold to show the top most affiliated products for a given target product;

(c) a bundle structure comprising a sub-set of products wherein each product in the bundle has a high consistency connection with all the other products in the bundle, wherein each product in a bundle is assigned a product density with respect to the bundle which is high if the product has high consistency connection with other products in the bundle and low otherwise; and

(d) a bridge structure comprising a collection of two or more, otherwise disconnected, product groups that are bridged by one or more bridge product.

2. The article of claim 1, wherein the visually presented recommendation is a graph comprising a plurality of nodes and edges, the nodes corresponding to entities and the edges corresponding to strength values.

3. The article of claim 2, wherein the tangible machine-readable storage medium further embodies instructions that when performed by one or more processors result in operations comprising:

receiving a user selection corresponding to a subset of the graph.

4. The article of claim 3, wherein the subset of the graph is selected based on at least one entity.

5. The article of claim 3, wherein the subset of the graph is selected based on at least one strength value.

6. The article of claim 3, wherein the subset of the graph is selected based on a subset of entities and a set of strength values corresponding to the subset of entities.

7. The article of claim 2, wherein the tangible machine-readable storage medium further embodies instructions that when performed by one or more processors result in operations comprising:

discovering patterns in the graph, the patterns corresponding to at least one of the entities and at least one of the strength values.

8. The article of claim 7, wherein the visually presented recommendation is based on at least one pattern.

9. The article of claim 7, wherein the entities correspond to products and the patterns are discovered based on product properties.

10. The article of claim 9, wherein the product properties are selected from the group consisting of manufacturer, brand name, product type, current inventory levels, product start date, product end date.

11. The article of claim 9, wherein the product properties are derived from the transactional data slice.

12. The article of claim 9, wherein the product properties comprise at least one of the average product revenue per transaction and average margin percent.

13. The article of claim 7, wherein the entities correspond to customers and the patterns are discovered based on customer properties.

14. The article of claim 13, wherein the customer properties are selected from the group consisting of demographic properties, segmentation properties, computed properties.

15. The article of claim 14, wherein the demographic properties comprise at least one of the age, income, occupation, address, household size and marriage status.

16. The article of claim 14, wherein the segmentation properties are based on at least one of a demographic, business value and purchase behavior properties.

17. The article of claim 14, wherein the computed properties comprise at least one of the value tier, new/old customer flag, early/late adopter flag.

18. The article of claim 1, wherein the transactional data slice comprises customer information and the entities correspond to customers.

19. The article of claim 1, wherein the transactional data slice comprises product information and the entities correspond to products.

20. The article of claim 1, wherein the tangible machine-readable storage medium further embodies instructions that when performed by one or more processors result in operations comprising:

filtering the transaction data slice prior to generating the pair wise relationships by removing one or more data elements.

21. The article of claim 20, wherein the data elements are selected from the group consisting of customers, transactions, products.

22. The article of claim 1, wherein the tangible machine-readable storage medium further embodies instructions that when performed by one or more processors result in operations comprising:

performing customer segmentation based on the pair-wise relationships.

23. The article of claim 1, wherein the tangible machine-readable storage medium further embodies instructions that when performed by one or more processors result in operations comprising:

creating product bundles based on the pair-wise relationships.

24. The article of claim 1, wherein the tangible machine-readable storage medium further embodies instructions that when performed by one or more processors result in operations comprising:

predicting time and product of a next possible purchase based on the pair-wise relationships.

25. The article of claim 1, wherein the tangible machine-readable storage medium further embodies instructions that when performed by one or more processors result in operations comprising:

generating a co-occurrence count for each pair-wise relationship.

26. The article of claim 1, wherein the context parameter comprises at least one of a market basket context and a purchase sequence context.

27. The article of claim 26, wherein the market basket context corresponds to a set of products purchased on one or more consecutive visits.

28. The article of claim 26, wherein the purchase sequence context comprises a first set of products purchased at a first point in time, a second set of products purchased at a second point in time and the time lag between the first point in time and the second point in time.

29. The article of claim 1, wherein the consistency parameter corresponds to a degree to which two products are more likely to be co-purchased in a context than are likely to be purchased independently.

30. The article of claim 29, wherein the consistency parameter is computed based on at least one co-occurrence count.

31. The article of claim 29, wherein the consistency parameter is computed based on a Pearson'"'"'s Correlation Coefficient.

32. The article of claim 29, wherein the consistency parameter is computed based on a Goodman and Kruskal'"'"'s Coefficients.

33. A method for implementation by one or more data processors, the method comprising:

selecting, by at least one data processor, a transaction data slice based on a customization parameter, the transactional data slice corresponding to a plurality of entities, the transaction data slice characterizing a time stamped sequence of market baskets, each market basket characterizing a transaction of a set of one or more products;

generating, by at least one data processor, pair-wise relationships between entities in the selected transaction data slice based on a context parameter, each pair-wise relationship linking two entities to each other;

determining, by at least one data processor, a strength value of each pair-wise relationship, the strength value corresponding to a consistency parameter;

transforming, by at least one data processor, data corresponding to at least one pair-wise relationship and at least one strength value into a recommendation; and

initiating, by at least one data processor, a visual presentation of the recommendation in the form of a graph comprising a plurality of nodes and edges, the nodes corresponding to entities and the edges corresponding to strength values, a structure of the graph being selected from a group comprising;

a sub-graph comprising a subset of a graph, created by picking a subset of nodes and edges from an original graph, the sub-graph selected from a group comprising (i) node based sub-graphs which are created by selecting a subset of the nodes and by keeping only those edges between selected nodes, and (ii) edge based sub-graphs which are created by pruning a set of edges from the graph and removing all nodes that are rendered disconnected from the graph;

a neighborhood of a target product comprising a sub-graph that contains the target product and all the products that are connected to the target product with consistency strength above a predefined threshold to show the top most affiliated products for a given target product;

a bundle structure comprising a sub-set of products wherein each product in the bundle has a high consistency connection with all the other products in the bundle, wherein each product in a bundle is assigned a product density with respect to the bundle which is high if the product has high consistency connection with other products in the bundle and low otherwise; and

a bridge structure comprising a collection of two or more, otherwise disconnected, product groups that are bridged by one or more bridge product.

34. A system comprising:

means for selecting a transaction data slice based on a customization parameter, the transactional data slice corresponding to a plurality of entities, the transaction data slice characterizing a time stamped sequence of market baskets, each market basket characterizing a transaction of a set of one or more products;

means for generating pair-wise relationships between entities in the selected transaction data slice based on a context parameter, each pair-wise relationship linking two entities to each other;

means for determining a strength value of each pair-wise relationship, the strength value corresponding to a consistency parameter;

means for transforming data corresponding to at least one pair-wise relationship and at least one strength value into a recommendation; and

means for initiating a visual presentation of the recommendation in the form of a graph comprising a plurality of nodes and edges, the nodes corresponding to entities and the edges corresponding to strength values, a structure of the graph being selected from a group comprising;

a sub-graph comprising a subset of a graph, created by picking a subset of nodes and edges from an original graph, the sub-graph selected from a group comprising (i) node based sub-graphs which are created by selecting a subset of the nodes and by keeping only those edges between selected nodes, and (ii) edge based sub-graphs which are created by pruning a set of edges from the graph and removing all nodes that are rendered disconnected from the graph;

a neighborhood of a target product comprising a sub-graph that contains the target product and all the products that are connected to the target product with consistency strength above a predefined threshold to show the top most affiliated products for a given target product;

a bundle structure comprising a sub-set of products wherein each product in the bundle has a high consistency connection with all the other products in the bundle, wherein each product in a bundle is assigned a product density with respect to the bundle which is high if the product has high consistency connection with other products in the bundle and low otherwise; and

a bridge structure comprising a collection of two or more, otherwise disconnected, product groups that are bridged by one or more bridge product.