Method and apparatus for retail data mining using pair-wise co-occurrence consistency

• US 7,672,865 B2
• Filed: 10/21/2005
• Issued: 03/02/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): Jeanty; Romain
• Application Number:
  US11/256,386
• Publication Number:
  US 20070100680A1
• Time in Patent Office: 1,593 Days
• Field of Search: 705/10
• US Class Current: 705/7.33
• 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. A method for semi-supervised insight discovery, the method being implemented by one or more data processors and comprising:

seeking, by at least one data processor, pair-wise relationships between large numbers of entities, in a variety of domain specific contexts, from appropriately filtered and customized transaction data;

representing, by at least one data processor, the pair-wise relationships between the entities in a graph structure containing a set of nodes representing entities, and a set of edges representing strength of relationships between pairs of nodes;

discovering, by at least one data processor, insights in the form of relationship patterns of interest that may be projected or scored on individual or groups of transactions or customers; and

using, by at least one data processor, said insights to make data-driven-decisions for a variety of business goals;

said graph structure comprising any of the following types of structures;

a sub-graph comprising a subset of a graph, created by picking a subset of nodes and edges from an original graph, a sub-graph comprising any of;

node based sub-graphs which are created by selecting a subset of the nodes and by keeping only those edges between selected nodes; and

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(s).

2. The method of claim 1, said transactions comprising transactions in a retail domain among customers buying products at retailers in successive visits, each visit resulting in a transaction of a set of one or more products;

wherein retail transaction data comprise a time stamped sequence of market baskets.

3. The method of claim 2, said transaction data comprising a mixture of interspersed customer purchases, said purchases comprising both of intentional purchases, which comprise a logical or signal part of said transaction data because there is a predictable pattern in intentional purchases of a customer, and emotion driven impulsive purchases, which add noise to the intentional purchase patterns of customers.

4. The method of claim 3, further comprising:

identifying, by at least one data processor, purchase patterns embedded in said transaction data that are associated with intentional behavior.

5. The method of claim 4, further comprising:

finding, by at least one data processor, patterns that associate a right kind of impulsive buying purchases with specific intentional purchases.

6. The method of claim 2, wherein said products comprise goods and services sold by a retailer, wherein the set of all products and their associated attributes, including hierarchies, descriptions, and properties, comprise a product space.

7. The method of claim 2, wherein a set of all customers, their organization in various segments, and all additional information known about customers comprises a customer space.

8. The method of claim 2, wherein said retail domain comprises any of the following relationships:

first order, explicit purchase-relationships between customers and products;

second order, implicit consistency-relationships between two products; and

second order, implicit similarity-relationships between two customers.

9. The method of claim 1, further comprising:

inferring, by at least one data processor, implicit product-product consistency relationships and customer-customer similarity relationships by viewing products in terms of customers and by viewing customers in terms of products.

10. The method of claim 1, further comprising:

using, by at least one data processor, a weighted edge between each pair of nodes to represent the consistency with which products in particular categories are purchased together, wherein edges with weights below a predetermined threshold are ignored.

11. The method of claim 10, further comprising:

projecting, by at least one data processor, said graph on a two-dimensional plane for visualization purposes, wherein nodes that have higher consistency strength between them are closer to each other than nodes that have lower consistency strength between them.

12. The method of claim 1, wherein said graph comprises an internal representation of pair-wise relationships between entities.

13. The method of claim 1, wherein the graph comprises any of the following parameters:

customization parameters which define the scope of a graph by identifying a transaction data slice used to build said graph;

context parameters which define the nature of relationships between products and customers in said graphs; and

consistency parameters which define the strength of relationships between products in product graphs.

14. The method of claim 1, further comprising:

mining, by at least one data processor, said graphs to find insights or actionable patterns in a graph structure; and

creating, by at least one data processor, marketing decisions from said insights or actionable patterns.

15. The method of claim 1, said bundle structure further comprising any of:

a product phrase which comprises a sequence of products purchased consistently across time; and

a product bundle which comprises a product phrase in which a time-lag between successive products is zero;

wherein consistent product phrases forecast customer purchases based on their past purchases to recommend a right product at a right time.

16. The method of claim 1, further comprising:

defining, by at least one data processor, a template pattern for a structure; and

searching, by at least one data processor, for template patterns in said graphs by seeking logical structures in said graphs.

17. The method of claim 1, further comprising:

projecting, by at least one data processor, logical bundles to their atomic pair-wise levels;

strengthening, by at least one data processor, only the relationships between pairs within an actual market basket;

discarding, by at least one data processor, transaction data; and

finding, by at least one data processor, structures in graphs directly.

18. A retail mining method for extracting actionable insights and data-driven decisions from transaction data, the method being implemented by one or more data processors and comprising:

data pre-processing by at least one data processor, wherein raw transaction data are filtered and customized;

said filtering cleaning said data by removing data elements that are to be excluded from analysis;

said customization creating different slices of said filtered transaction data that may be analyzed separately and whose results may be compared for further insight generation;

graph generation, by at least one data processor, to create graphs that capture all pair-wise relationships between entities in a variety of contexts, said graph generation step comprising;

context-instance creation wherein a number of context instances are created from said transaction data slice;

co-occurrence counting wherein, for each pair of products, a co-occurrence count is computed as the number of context instances in which two products co-occurred; and

co-occurrence consistency, wherein, once all co-occurrence counting is done, information theoretic consistency measures are computed for each pair of products, resulting in a graph; and

insight discovery and decisioning, by at least one data processor, from said graphs, wherein said graphs serve as a model or internal representation of knowledge extracted from transaction data, said insight discovery and decisioning step further comprising any of;

product related insight discovery, wherein graph theory and machine learning algorithms are applied to said graphs to discover patterns of interest, including product bundles, bridge products, product phrases, and product neighborhoods;

wherein said patterns may be used to make decisions; and

customer related decisioning, wherein a graph is used as a model to decisions;

said graphs comprising any of the following types of structures;

a sub-graph comprising a subset of a graph, created by picking a subset of nodes and edges from an original graph, a sub-graph comprising any of;

node based sub-graphs which are created by selecting a subset of the nodes and by keeping only those edges between selected nodes; and

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(s).

19. The method of claim 18, wherein said transaction data comprise a time-stamped sequence of market baskets and reflect a mixture of both intentional and impulsive customer behavior.

20. The method of claim 19, wherein a transaction data record comprises one line-item for each product purchased by each customer in each visit;

wherein each line-item comprises any of the following fields;

customer ID, transaction date, and SKU level product ID, and any of the following associated values;

revenue, margin, quantity, and discount information.

21. The method of claim 18 wherein said transaction data comprise any of the following retail data objects:

product objects comprising atomic-level object in a product space;

line item objects comprising each line (atomic level object) in said transaction data;

transaction objects comprising a collection of all line items associated with a single visit by a customer; and

customer objects comprising a collection of all transactions associated with a customer;

wherein each of said objects is further associated with one or more properties that may be used to filter, customize, or analyze the results of various retail applications.

22. The method of claim 18, wherein said products comprise any of the following product properties:

given or direct product properties that are provided in a product dictionary; and

computed or indirect product properties that are summary properties which can be computed from transaction data using standard summarizations.

23. The method of claim 18, wherein said transactions comprise any of the following transaction properties:

direct or observed properties which are part of the transaction data itself; and

indirect or derived properties.

24. The method of claim 18, wherein said customers comprise any of the following customer properties:

demographic properties about each customer that may be collected during an application process or a survey or from an external marketing database;

segmentation properties comprising segment assignments of each customer using various segmentation schemes; and

computed properties comprising customer properties computed from customer transaction history.

25. The method of claim 18, said filtering step further comprising:

applying, by at least one data processor, a series of filters based on products, line items, transactions, and customers object types in said transaction data, said filters comprising any of;

a product filter that allows a retailer to limit products for an analysis in either of;

a product scope list that allows said retailer to create a list of in-scope products, wherein only products that are in said list are used in analyses; and

a product stop list that allows said retailer to create a list of out-of-scope products that must not be used in analyses;

a line item filter, wherein rules based on line item properties are defined to include or exclude certain line items in analyses;

a transaction filter by which entire transactions may be filtered in or out of analyses based on transaction level properties, wherein rules based on transaction properties may be used to include or exclude certain transactions from analysis; and

a customer filter, wherein transaction data from a particular customer may be included or excluded from analysis, wherein rules based on customer properties may be defined to include or exclude certain customers from analysis.

26. The method of claim 18, said customization step further comprising either of:

customizing, by at least one data processor, analyses by different customer properties; and

customizing, by at least one data processor, analyses by different transaction properties.

27. The method of claim 18, further comprising:

extracting, by at least one data processor, a context instance from said transaction data;

performing, by at least one data processor, a co-occurrence count to count how many times a product pair co-occurred in a context instance; and

using, by at least one data processor, said co-occurrence count to create pair-wise relationships between products.

28. The method of claim 18, further comprising:

using, by at least one data processor, context to define the nature of relationship between two entities by way of their juxtaposition in said transaction data, wherein types of available contexts depend on the domain and nature of said transaction data.

29. The method of claim 28, further comprising:

for every context, using, by at least one data processor, a process to quantify pair-wise co-occurrence consistencies for all product pairs for each level at which analysis is to be done, said process comprising;

creating context instances from said transaction data;

counting a number of times two products co-occurred in said context instances; and

creating information theoretic measures to quantify consistency between said context instances.

30. The method of claim 18, further comprising:

using, by at least one data processor, context in the retail domain, where said transaction data comprise a time-stamped sequence of market baskets, wherein context comprises either of market basket context and purchase sequence context.

31. The method of claim 30, said market basket context instance comprising a set of products purchased on one or more consecutive visits.

32. The method of claim 18, further comprising:

using, by at least one data processor, consistency to quantify the strength of relationships between pairs of products, wherein consistency comprises the degree to which two products are more likely to be co-purchased in a context than they are likely to be purchased independently.

33. An article comprising a tangible computer-readable storage medium embodying instructions that when performed by one or more computer processors result in operations for semi-supervised insight discovery comprising:

seeking pair-wise relationships between large numbers of entities, in a variety of domain specific contexts, from appropriately filtered and customized transaction data;

representing the pair-wise relationships between the entities in a graph structure containing a set of nodes representing entities, and a set of edges representing strength of relationships between pairs of nodes;

discovering insights in the form of relationship patterns of interest that may be projected or scored on individual or groups of transactions or customers; and

using said insights to make data-driven-decisions for a variety of business goals;

said graph structure comprising any of the following types of structures;

a sub-graph comprising a subset of a graph, created by picking a subset of nodes and edges from an original graph, a sub-graph comprising any of;

node based sub-graphs which are created by selecting a subset of the nodes and by keeping only those edges between selected nodes; and

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(s).

34. An article comprising a tangible computer-readable storage medium embodying instructions that when performed by one or more computer processors result in operations for extracting actionable insights and data-driven decisions from transaction data comprising:

data pre-processing, wherein raw transaction data are filtered and customized;

said filtering cleaning said data by removing data elements that are to be excluded from analysis;

said customization creating different slices of said filtered transaction data that may be analyzed separately and whose results may be compared for further insight generation;

graph generation to create graphs that capture all pair-wise relationships between entities in a variety of contexts, said graph generation step comprising;

context-instance creation wherein a number of context instances are created from said transaction data slice;

co-occurrence counting wherein, for each pair of products, a co-occurrence count is computed as the number of context instances in which two products co-occurred; and

co-occurrence consistency, wherein, once all co-occurrence counting is done, information theoretic consistency measures are computed for each pair of products, resulting in a graph; and

insight discovery and decisioning from said graphs, wherein said graphs serve as a model or internal representation of knowledge extracted from transaction data, said insight discovery and decisioning step further comprising any of;

product related insight discovery, wherein graph theory and machine learning algorithms are applied to said graphs to discover patterns of interest, including product bundles, bridge products, product phrases, and product neighborhoods;

wherein said patterns may be used to make decisions; and

customer related decisioning, wherein a graph is used as a model to decisions;

said graphs comprising any of the following types of structures;

a sub-graph comprising a subset of a graph, created by picking a subset of nodes and edges from an original graph, a sub-graph comprising any of;

node based sub-graphs which are created by selecting a subset of the nodes and by keeping only those edges between selected nodes; and

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(s).