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

[0001] 1. Technical Field

[0002] The invention relates to data mining. More particularly, the invention relates to a method and apparatus for retail data mining using pair-wise co-occurrence consistency.

[0003] 2. Description of the Prior Art

[0004] Retail leaders recognize today that the greatest opportunity for innovation lies at the interface between the store and the customer. The retailer owns vital marketing information on the purchases of millions of customers: information that can be used to transform the store from a fancy warehouse where the customer is a mere stock picker into a destination where customers go because of the value the store gives them. The opportunity is enormous: seventy to eighty percent of buying choices are made at the point of purchase, and smart retailers can influence the choices to maximize economic value and customer satisfaction. Because the retailer is closest to the consumer, he has the unique opportunity and power to create loyalty, encourage repeat purchase behavior and establish high value purchase career paths. However, to optimize the customer interface in this fashion, retailers must be extremely sophisticated with analysis of their purchase data. The sheer volume of purchase data, while offering unprecedented opportunities for such customer centric retailing, also challenges the traditional statistical and mathematical techniques at the retailer's disposal. Retail data analysts frequently find it difficult, if not impossible, to derive concrete, actionable decisions from such data. Most traditional retailers use only limited OLAP capabilities to slice and dice the transaction data to extract basic statistical reports and use them and other domain knowledge to make marketing decisions. Only in the last few years have traditional retailers started warming up to segmentation, product affinity analysis, and recommendation engine technologies to make business decisions. Traditional computational frameworks, such as classification and regression, seek optimal mappings between a set of input features that either cause or correlate-with a target variable. It would be advantageous to provide improved approaches to retail data mining.

[0005] The herein disclosed Pair-wise Co-occurrence Consistency Co-occurrence (PeaCoCk) framework seeks patterns of interest in pair-wise relationships between entities. Such a framework may be applied in a wide variety of domains with unstructured or hyper-structured data, for example in language understanding and text mining (syntactic and semantic relationships between words, phrases, named entities, sentences, and documents), bioinformatics (structural, functional, and co-occurrence relationships between nucleotides in gene sequences, proteins in amino acid sequences, and genes in gene expression experiments), image understanding and computer vision (spatial co-occurrence relationships of pixels, edges, and objects in images), transaction data analytics (consistent co-occurrence relationships between events), and retail data analytics (co-occurrence consistency relationships between products and similarity relationships between customers). The preferred embodiment of the invention disclosed herein applies the PeaCoCk framework to Retail Data Mining, i.e. finding insights and creating decisions from retail transaction data that is being collected by almost all large retailers for over a decade.

[0006] Data driven, customer-centric analyses, enabled by the herein disclosed novel data mining methodologies, are expected to open up fundamentally novel opportunities for retailers to dramatically improve customer experience, loyalty, profit margins, and customer lifetime value. The PeaCoCk retail mining framework enables mass retailers to capitalize on such opportunities. Using PeaCoCk, retailers can analyze very large scale purchase transaction data and generate targeted customer-centric marketing decisions with exceptionally high economic value. The invention provides a method and apparatus that discovers consistent relationships in massive amounts of purchase data, bringing forth product relationships based on purchase-behavior, both in market baskets and across time. It helps retailers identify opportunities for creating an efficient alignment of customer intent and store content using purchase data. This helps customers find the products they want, and be offered the products they need. It helps segment customers and products based on purchase behavior to create a differentiated customer experience and generate recommendations tailored to each customer and each store. It helps retailers analyze purchase career paths that lend themselves to generating accurate cross-sell and up-sell recommendations and targeted promotions. It helps determine bridge products that can influence future purchase sequences and help move a customer's purchase career path from one category to another higher value category. Finally it can be used to generate valuable in-the-field analyses of product purchase affinities that retailers can offer for sale to manufacturers and distributors as information products. Thus, an agile organization can harness PeaCoCk to completely redefine the retail enterprise as customer-centric, information driven business that in addition, manufactures its own value-added information products.

[0007] FIG. 1 shows retail transaction data as a time stamped sequence of market baskets;

[0008] FIG. 2 shows an example of a PeaCoCk consistency graph for a grocery retailer, in which nodes represent products and edges represent consistency relationships between pairs of nodes;

[0009] FIG. 3 shows a product neighborhood, in which a set of products is shown with non-zero consistency with the target product, where the left figure is shown without cross edges and the right figure is shown with a cross edge;

[0010] FIG. 4 shows a bridge structure in which two or more product groups are connected by a bridge product;

[0011] FIG. 5 shows a logical bundle of seven products;

[0012] FIG. 6 shows data pre-processing, which involves both data filtering (at customer, transaction, line item, and product levels) and customization (at customer and transaction levels);

[0013] FIG. 7 shows that PeaCoCk is context rich, where there are two types of contexts in PeaCoCk: market basket context and purchase sequence context; where each type of context allows a number of parameters to define contexts as necessary and appropriate for different applications for different retailer types;

[0014] FIG. 8 is a description of Algorithm 1;

[0015] FIG. 9 is a description of Algorithm 2;

[0016] FIG. 10 shows a definition of consistency;

[0017] FIG. 11 shows four counts and their Venn diagram interpretation;

[0018] FIG. 12 shows the wide variety of PeaCoCk applications divided into three types: Product affinity applications, Customer affinity applications, and Purchase behavior applications;

[0019] FIG. 13 shows a discrete bundle lattice space used to define a locally optimal product bundle for Algorithms 4 and 5;

[0020] FIG. 14 shows an example of polyseme where a word can have multiple meanings. This is the motivation for bridge structures;

[0021] FIG. 15 shows an example of a product bundle with six products and time-lags between all pairs of products in the bundle;

[0022] FIG. 16 shows the Recommendation Engine process;

[0023] FIG. 17 shows two types of recommendation engine modes depending on how customer history is interpreted: The Market Basket Recommendation Engine (top) and the Purchase Sequence Recommendation Engine (bottom); and

[0024] FIG. 18 shows the motivation for using density score for post-processing the recommendation score if the business goal is to increase the market basket size.

[0025] 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.

[0026] The invention is also unique in that it allows such product associations to be analyzed in various contexts, e.g. within individual market baskets, or in the context of a next visit market basket, or across all purchases in an interval of time, so that different kinds of purchase behavior associated with different types of products and different types of customer segments can be revealed. Therefore, accurate customer-centric and product-centric decisions can be made. PeaCoCk analysis can be scaled to very large volumes of data, and is capable of analyzing millions of products and billions of transactions. It is interpretable and develops a graphical network structure that reveals the product associations and provides insight into the decisions generated by the analysis. It also enables a real-time customer-specific recommendation engine that can use a customer's past purchase behavior and current market basket to develop accurate, timely, and very effective cross-sell and up-sell offers.

[0027] The PeaCoCk Framework

[0028] Traditional modeling frameworks in statistical pattern recognition and machine learning, such as classification and regression, seek optimal causal or correlation based mapping from a set of input features to one or more target values. The systems (input-output) approach suits a large number of decision analytics problems, such as fraud prediction and credit scoring. The transactional data in these domains is typically collected in, or converted to, a structured format with fixed number of observed and/or derived input features from which to choose. There are a number of data and modeling domains, such as language understanding, image understanding, bioinformatics, web cow-path analysis etc., in which either (a) the data are not available in such a structured format or (b) we do not seek input-output mappings, where a new computational framework might be more appropriate. To handle the data and modeling complexity in such domains, the inventors have developed a semi-supervised insight discovery and data-driven decision analytics framework, known as Pair-wise Co-occurrence Consistency or PeaCoCk that:

• • [0029] Seeks Pair-wise relationships between large numbers of entities,
  • [0030] In a variety of domain specific contexts,
  • [0031] From appropriately filtered and customized transaction data,
  • [0032] To discover insights in the form of relationship patterns of interest,
  • [0033] That may be projected (or scored) on individual or groups of transactions or customers,
  • [0034] And to make data-driven-decisions for a variety of business goals.

[0035] Each of the highlighted terms has a very specific meaning as it applies to different domains. Before describing these concepts as they apply to the retail domain, consider the details of the retail process and the retail data abstraction based on customer purchases.

[0036] Retail Transaction Data

[0037] At a high level, the retail process may be summarized as Customers buying products at retailers in successive visits, each visit resulting in the transaction of a set of one or more products (market basket). In its fundamental abstraction, as used in the PeaCoCk framework, the retail transaction data is treated as a time stamped sequence of market baskets, as shown in FIG. 1.

[0038] Transaction data are a mixture of two types of interspersed customer purchases:

[0039] (1) Logical/intentional purchases (Signal): Largely, customers tend to buy what they need/want and when they need/want them. These may be called intentional purchases, and may be considered the logical or signal part of the transaction data as there is a predictable pattern in the intentional purchases of a customer.

[0040] (2) Emotional/impulsive purchases (Desirable Noise)—In case of most customers, the logical intentional purchase may be interspersed with emotion driven impulsive purchases. These appear to be unplanned and illogical compared to the intentional purchases. Retailers deliberately encourage such impulsive purchases through promotions, product placements, and other incentives because it increases their sales. But from an analytical and data perspective, impulsive purchases add noise, to the intentional purchase patterns of customers. This makes the problem of finding logical patterns associated with intentional purchases more challenging.

[0041] Key Challenges in Retail Data Analysis

[0042] Based on this abstraction of the transaction data that they are a mixture of both intentional and impulsive purchases, there are three key data mining challenges:

[0043] (a) Separatinq Intentional (Signal) from Impulsive (Noise) purchases: As in any other data mining problem, it is important to first separate the wheat from the chaff or signal from the noise. Therefore, the first challenge is to identify the purchase patterns embedded in the transaction data that are associated with intentional behaviors.

[0044] (b) Complexity of Intentional behavior: The intentional purchase part of the transaction data is not trivial. It is essentially a mixture of projections of (potentially time-elapsed) latent purchase intentions. In other words:

• • [0045] (i) a customer purchases a particular product at a certain time in a certain store with a certain intention, e.g. weekly grocery, back-to-school, etc.
  • [0046] (ii) Each visit by a customer to the store may reflect one or more (mixture of) intention(s).
  • [0047] (iii) Each intention is latent, i.e. they are not obvious or announced although they may be deduced from the context of the products purchased.
  • [0048] (iv) Each intention may involve purchase of one or more products. For a multi-product intention, it is possible that the customer may not purchase all the products associated with that intention either at the same store or in the same visit. Hence, the transaction data only reflects a subset or a projection of a latent intention for several reasons: Maybe the customer already has some products associated with the intention, or he got them as a gift, or he purchased them at a different store, etc.
  • [0049] (v) Finally, an intention may be spread across time. For example, an intention such as garage re-modeling or setting up a home office may take several weeks and multiple visits to different stores.

[0050] Finding patterns in transaction data with noisy (due to impulsive), incomplete (projections of intentions), overlapping (mixture of intentions), and indirect (latent intentions) underlying drivers presents a unique set of challenges.

[0051] (c) Matching the right impulses to the right intentions

[0052] As mentioned above, the customer's impulsive behavior is desirable for the retailer. Therefore instead of ignoring the noise associated with it, the retailers might be interested in finding patterns associating the right kind of impulsive buying purchases with specific intentional purchases.

[0053] Overview

[0054] In the following discussion, a high level overview of the PeaCoCk framework is given. The terminology used to define the PeaCoCk framework is described. The PeaCoCk process and benefits of the PeaCoCk framework are also provided.

[0055] Entities in Retail Domain

[0056] In the retail domain, there are a number of entity-types: Products, Customers, Customer segments, Stores, Regions Channels, Web pages, Offers, etc. PeaCoCk primarily focuses on two main entity types: Products and Customers.

[0057] Products are goods and services sold by a retailer. We refer to the set of all products and their associated attributes including hierarchies, descriptions, properties, etc. by an abstraction called the product space. A typical product space exhibits the following four characteristics:

• • [0058] Large—A typical retailer has thousands to hundreds of thousands of products for sale.
  • [0059] Heterogeneous—Products in a number of different areas might be sold by the retailer.
  • [0060] Dynamic—New products are added and old products removed frequently.
  • [0061] Multi-Resolution—Products are organized in a product hierarchy for tractability

[0062] The set of all customers that have shopped in the past forms the retailer's customer base. Some retailers can identify their customers either through their credit cards or retailer membership card. However, most retailers lack this ability because customers are using either cash or they do not want to participate in a formal membership program. Apart from their transaction history, the retailer might also have additional information on customers, such as their demographics, survey responses, market segments, life stage, etc. The set of all customers, their possible organization in various segments, and all additional information known about the customers comprise the customer space. Similar to a product space, a typical customer space exhibits the following four characteristics:

• • [0063] Large—A customer base might have hundreds of thousands to millions of customers.
  • [0064] Heterogeneous—Customers are from various demographics, regions, life styles/stages.
  • [0065] Dynamic—Customers are changing over time as they go through different life stages.
  • [0066] Multi-Resolution—Customers may be organized by household, various segmentations.

[0067] Relationships in Retail Domain

[0068] There are different types of relationships in the retail domain. The three main types of relationships considered by PeaCoCk are:

[0069] 1. First order, explicit purchase-relationships between customers and products, i.e. who purchased what, when, for how much, and how (channel, payment type, etc.)?

[0070] 2. Second order, implicit consistency-relationships between two products, i.e. how consistently are two products co-purchased in a given context?

[0071] 3. Second order, implicit similarity-relationships between two customers, i.e. how similar are the purchase behaviors exhibited by two customers?

[0072] While the purchase relationships are explicit in the transaction data, the PeaCoCk framework is used primarily to infer the implicit product-product consistency relationships and customer-customer similarity relationships. To do this, PeaCoCk views products in terms of customers and views customers in terms of products.

[0073] PeaCoCk Graphs

[0074] The most natural representation of pair-wise relationships between entities abstraction is a structure called Graph. Formally, a graph contains

• • [0075] a set of Nodes representing entities (products or customers); and
  • [0076] a set of Edges representing strength of relationships between pairs of nodes (entities).

[0077] FIG. 2 shows an example of a PeaCoCk Consistency Graph created using the transaction data from a Grocery retailer. In FIG. 2, nodes represent products and edges represent consistency relationships between pairs of nodes. This graph has one node for each product at a category level of the product hierarchy. These nodes are further annotated or colored by department level. In general, these nodes could be annotated by a number of product properties, such as total revenue, margin per customers, etc. There is a weighted edge between each pair of nodes. The weight represents the consistency with which the products in those categories are purchased together. Edges with weights below a certain threshold are ignored. For visualization purposes, the graph is projected on a two-dimensional plane, such that edges with high weights are shorter or, in other words, two nodes that have higher consistency strength between them are closer to each other than two nodes that have lower consistency strength between them.

[0078] PeaCoCk graphs are the internal representation of the pair-wise relationships between entities abstraction. There are three parameters that define a PeaCoCk Graph.

[0079] 1. Customization defines the scope of the PeaCoCk graph by identifying the transaction data slice (customers and transactions) used to build the graph. For example, one might be interested in analyzing a particular customer segment or a particular region or a particular season or any combination of the three. Various types of customizations that are supported in PeaCoCk are described below.

[0080] 2. Context defines the nature of the relationships between products (and customers) in the PeaCoCk graphs. For example, one might be interested in analyzing relationships between two products that are purchased together or within two weeks of each other, or where one product is purchased three months after the other, and so on. As described below, PeaCoCk supports both market basket contexts and purchase sequence contexts.

[0081] 3. Consistency defines the strength of the relationships between products in the product graphs. There are a number of consistency measures based on information theory and statistics that are supported in the PeaCoCk analysis. Different measures have different biases. These are discussed further below.

[0082] Insight-Structures in PeaCoCk Graphs

[0083] As mentioned above, the PeaCoCk graphs may be mined to find insights or actionable patterns in the graph structure that may be used to create marketing decisions. These insights are typically derived from various structures embedded in the PeaCoCk graphs. The five main types of structures in a PeaCoCk graph that are explored are:

[0084] (1) Sub-graphs—A sub-graph is a subset of the graph created by picking a subset of the nodes and edges from the original graph. There are a number of ways of creating a sub-graph from a PeaCoCk graph. These may be grouped into two types:

• • [0085] Node based Sub-graphs are created by selecting a subset of the nodes and therefore, by definition, keeping only the edges between selected nodes. For example, in a product graph, one might be interested in analyzing sub-graph of all products within the electronics department or clothing merchandise, or only the top 10% high value products, or products from a particular manufacturer, etc. Similarly, in a customer graph, one might be interested in analyzing customers in a certain segment, or high value customers, or most recent customers, etc.
  • [0086] Edge based Sub-graphs are created by pruning a set of edges from the graph and therefore, by definition, removing all nodes that are rendered disconnected from the graph. For example, one might be interested in removing low consistency strength edges (to remove noise), and/or high consistency strength edges (to remove obvious connections), or edges with a support less than a threshold, etc.

[0087] (2) Neighborhoods—A neighborhood of a target product in a PeaCoCk graph is a special sub-graph that contains the target product and all the products that are connected to the target product with consistency strength above a threshold. This insight structure shows the top most affiliated products for a given target product. Decisions about product placement, store signage, etc. can be made from such structures. A neighborhood structure may be seen with or without cross edges as shown in FIG. 3, which shows a Product Neighborhood having a set of products with non-zero consistency with the target product. In FIG. 3, the left figure is without cross edges and the right figure is with cross edges. A cross-edge in a neighborhood structure is defined as an edge between any pair of neighbors of the target product. More details on product neighborhoods are given below.

[0088] (3) Product Bundles—A bundle structure in a PeaCoCk graph is defined as a sub-set of products such that each product in the bundle has a high consistency connection with all the other products in the bundle. In other words, a bundle is a highly cohesive soft clique in a PeaCoCk graph. The standard market basket analysis tools seek to find Item-Sets with high support (frequency of occurrence). PeaCoCk product bundles are analogous to these item-sets, but they are created using a very different process and are based on a very different criterion known as bundleness that quantifies the cohesiveness of the bundle. The characterization of a bundle and the process involved in creating a product bundle exemplify the novel generalization that is obtained through the pair-wise relationships and is part of a suite of propriety algorithms that seek to discover higher order structures from pair-wise relationships.

[0089] FIG. 4 shows two examples of product bundles. Each product in a bundle is assigned a product density with respect to the bundle. FIG. 4 shows a cohesive soft clique where each product is connected to all others in the bundle. Each product is assigned a density measure which is high if the product has high consistency connection with others in the bundle and low otherwise. Bundle structures may be used to create co-promotion campaigns, catalog and web design, cross-sell decisions, and analyze different customer behaviors across different contexts. More details on product bundles are given below.

[0090] (4) Bridge Structures—The notion of a bridge structure is inspired from that of polyseme in language where a word might have more than one meaning (or belongs to more than one semantic family). For example, the word ‘can’ may belong to the semantic family {‘can’, ‘could’, ‘would’ . . . } or {‘can’, ‘bottle’, ‘canister’ . . . }. In retail, a bridge structure embedded in the PeaCoCk graph is a collection of two or more, otherwise disconnected, product groups (product bundle or an individual product) that are bridged by one or more bridge product(s).. For example, a wrist-watch may be a bridge product between electronics and jewelry groups of products. A bridge pattern may be used to drive cross department traffic and diversify a customer's market basket through strategic promotion and placement of products. More details on bridge structures are given below.

[0091] (5) Product Phrases—A product phrase is a product bundle across time, i.e. it is a sequence of products purchased consistently across time. For example, a PC purchase followed by a printer purchase in a month, followed by a cartridge purchase in three months is a product phrase. A product bundle is a special type of product phrase where the time-lag between successive products is zero. Consistent product phrases may be used to forecast customer purchases based on their past purchases to recommend the right product at the right time. More details about product phrases is given below.

[0092] Logical vs. Actual Structures

[0093] All the structures discussed above are created by (1) defining a template-pattern for the structure and (2) efficiently searching for those patterns in the PeaCoCk graphs. One of the fundamental differences between PeaCoCk and conventional approaches is that PeaCoCk seeks logical structures in PeaCoCk graphs while conventional approaches, such as frequent item-set mining, seek actual structures directly in transaction data.

[0094] Consider, for example, a product bundle or an item-set shown in FIG. 6 with seven products. For the prior art to discover it, a large number of customers must have bought the entire item-set or, in other words, the support for the entire item-set should be sufficiently high. The reality of transaction data, however, is that customers buy projections or subsets of such logical bundles/item-sets. In the example of FIG. 6, it is possible that not a single customer bought all these products in a single market basket and, hence, the entire logical bundle never exists in the transaction data (has a support of zero) and is therefore not discovered by standard item-set mining techniques. In reality, customers only buy projections of the logical bundles. For example, some customers might buy a subset of three out of seven products, another set of customers might buy some other subset of five out of seven products, and it is possible that there is not even a single customer who bought all the seven products. There could be several reasons for this: May be they already have the other products, or they bought the remaining products in a different store or at a different time, or they got the other products as gifts, and so on.

[0095] The limitation of the transaction data that they do not contain entire logical bundles throws a set of unique challenges for retail data mining in general, and item-set mining in particular. PeaCoCk addresses this problem in a novel way. First, it uses these projections of the logical bundles by projecting them further down to their atomic pair-wise levels and strengthens only these relationships between all pairs within the actual market basket. Secondly, when the PeaCoCk graphs are ready, PeaCoCk discards the transaction data and tries to find these structures in these graphs directly. So even if edges between products A and B are strengthened because of a different set of customers, between A and C by another set of customers and between B and C by a third set of customers (because they all bought different projections of the logical bundle {A, B, C}), still the high connection strengths between A-B, B-C, and A-C result in the emergence of the logical bundle {A, B, C} in the PeaCoCk graph. Thus, the two stage process of first creating the atomic pair-wise relationships between products and then creating higher order structures from them gives PeaCoCk a tremendous generalization capability that is not present in any retail mining framework. The same argument applies to other higher order structures such as bridges and phrases as well. This provides PeaCoCk a unique ability to find very interesting, novel, and actionable logical structures (bundles, phrases, bridges, etc.) that cannot be found otherwise.

[0096] The PeaCoCk Retail Mining Process

[0097] There are three stages in the PeaCoCk retail mining process for extracting actionable insights and data-driven decisions from this transaction data:

[0098] (1) Data Pre-processing—In this stage, the raw transaction data are (a) filtered and (b) customized for the next stage. Filtering cleans the data by removing the data elements (customers, transactions, line-items, and products) that are to be excluded from the analysis. Customization creates different slices of the filtered transaction data that may be analyzed separately and whose results may be compared for further insight generation, e.g. differences between two customer segments. This stage results in one or more clean, customized data slices on which further analyses may be done. Details of the Data Pre-processing stage are provided below.

[0099] (2) PeaCoCk Graph Generation: In this stage, PeaCoCk uses information theory and statistics to create PeaCoCk Graphs that exhaustively capture all pair-wise relationships between entities in a variety of contexts. There are several steps in this stage:

• • [0100] Context-instance Creation—depending on the definition of the context, a number of context instances are created from the transaction data slice.
  • [0101] Co-occurrence Counting—For each pair of products, a co-occurrence count is computed as the number of context instances in which the two products co-occurred.
  • [0102] Co-occurrence Consistency—Once all the co-occurrence counting is done, information theoretic consistency measures are computed for each pair of products resulting in a PeaCoCk graph.

[0103] (3) Insight Discovery and Decisioninq from PeaCoCk Graphs: The PeaCoCk graphs serve as the model or internal representation of the knowledge extracted from transaction data. They are used in two ways:

• • [0104] Product Related Insight Discovery—Here, graph theory and machine learning algorithms are applied to the PeaCoCk graphs to discover patterns of interest such as product bundles, bridge products, product phrases, and product neighborhoods. These patterns may be used to make decisions, such as store layout, strategic co-promotion for increased cross department traffic, web-site layout and customization for identified customer, etc. Visualization tools such as a Product Space Browser have been developed to explore these insights.
  • [0105] Customer Related Decisioning—Here, the PeaCoCk graph is used as a model to decisions, such as recommendation engine that predict the most likely products a customer may buy given his past purchases. PeaCoCk recommendation engine may be used to predict not only what products the customer will buy, but also the most likely time when the customer will buy it, resulting in PeaCoCk's ability to make precise and timely recommendations. Details of the PeaCoCk recommendation engine are provided below.

[0106] PeaCoCk Benefits

[0107] The PeaCoCk framework integrates a number of desirable features in it that makes it very compelling and powerful compared to the current state of the art retail analytic approaches, such as association rule based market basket analysis or collaborative filtering based recommendation engines. The PeaCoCk framework is:

• • [0108] Generalizable: In association rules for a product bundle (or itemset) to be selected as a potential candidate, it must occur sufficient number of times among all the market baskets, i.e. it should have a high enough support. This criterion limits the number and kind of product bundles that can be discovered especially, for large product bundles. PeaCoCk uses only pair-wise consistency relationships and uses the resulting graph to expand the size of the candidate item-sets systematically. This approach makes PeaCoCk far more accurate and actionable compared to association rules and similar frequency based approaches.
  • [0109] Scalable: Again, because of pair-wise relationships among the product and customers, the PeaCoCk framework can represent a large number of sparse graphs. A typical PeaCoCk implementation on a single processor can easily handle hundreds of thousands of products, millions of customers, and billions of transactions within reasonable disk space and time complexities. Moreover, the PeaCoCk framework is highly parallelizable and, therefore, can scale well with the number of products, number of customers, and number of transactions.
  • [0110] Flexible: PeaCoCk is flexible in several ways: First it supports multiple contexts simultaneously and facilitates the search for the right context(s) for a given application. Secondly, it represents and analyzes graphs at possibly multiple levels of entity hierarchies. Thirdly, it represents entity spaces as graphs and therefore draws upon the large body of graph theoretic algorithms to address complex retail analytics problems. Most other frameworks have no notion of context; they can work well only at certain resolutions, and are very specific in their applications.
  • [0111] Adaptive: As noted before, both the product space and the customer space is very dynamic. New products are added, customers change over time, new customers get added to the market place, purchase trends change over time etc. To cope up with these dynamics of the modern day retail market, one needs a system that can quickly assimilate the newly generated transaction data and adapt its models accordingly. PeaCoCk is very adaptive as it can update its graph structures quickly to reflect any changes in the transaction data.
  • [0112] Customizable: PeaCoCk can be easily customized at various levels of operations: store level, sub-region level, region level, national level, international level. It can also be customized to different population segments. This feature allows store managers to quickly configure the various PeaCoCk applications to their stores or channels of interest in their local regions.
  • [0113] Interpretable: PeaCoCk results can be interpreted in terms of the sub-graphs that they depend upon. For example, bridge products, seed products, purchase career paths, product influences, similarity and consistency graphs, everything can be shown as two dimensional graph projections using the PeaCoCk visualization tool. These graphs are intuitive and easy to interpret by store managers and corporate executives both to explain results and make decisions.

[0114] Retail Data

[0115] In the following discussion, a formal description of the retail data is presented. Mathematical notations are introduced to define products in the product space, customers in the customer space, and their properties. Additionally, the data pre-processing step involving filtering and customization are also described in this discussion.

[0116] Product Space

[0117] A retailer's product space is comprised of all the products sold by the retailer. A typical large retailer may sell anywhere from tens of thousands to hundreds of thousands of products. These products are organized by the retailer in a product hierarchy in which the finest level products (SKU or UPC level) are grouped into higher product groups. The total numbers of products at the finest level change over time as new products are introduced and old products are removed. However, typically, the numbers of products at coarser levels are more or less stable. The number of hierarchy levels and the number of products at each level may vary from one retailer to another. The following notation is used to represent products in the product space:

• • [0118] Total number of product hierarchy levels is L (indexed 0 . . . L−1), 0 being the finest level
  • [0119] Product Universe at level l is the set: U_l{u₁^(l), . . . , u_m^(l), . . . , u_ml^(l)} with M_l products
  • [0120] Every product at the finest resolution is mapped to a coarser resolution product using many-to-one Product Maps that define the product hierarchy:
    M_l:U₀→U_l

[0121] In addition to these product sets and mappings, each product has a number of properties as described below.

[0122] Customer Space

[0123] The set of all customers who have shopped at a retailer in the recent past form the customer base of the retailer. A typical large retailer may have anywhere from hundreds of thousands to tens of millions of customers. These customers may be geographically distributed for large retail chains with stores across the nation or internationally. The customer base might be demographically, financially, and behaviorally heterogeneous. Finally, the customer base might be very dynamic in three ways:

[0124] (i) new customers add over time to the customer base,

[0125] (ii) old customers churn or move out of the customer base, and

[0126] (iii) existing customers change in their life stage and life style.

[0127] Due to the changing nature of the customer base, most retail analysis including customer segmentation must be repeated every so often to reflect the current status of the customer base. We use the following formal notation to represent customers in the customer space:

• • [0128] Total number of customers in the customer space at any snapshot: N
  • [0129] Customers will be indexed by η∈{1 . . . N}

[0130] As described below, each customer is associated with additional customer properties that may be used their retail analysis.

[0131] Retail Transaction Data

[0132] As described earlier, transaction data are essentially a time-stamped sequence of market baskets and reflect a mixture of both intentional and impulsive customer behavior. A typical transaction data record is known as a line-item, one for each product purchased by each customer in each visit. Each line-item contains fields such as customer id, transaction date, SKU level product id, and associated values, such as revenue, margin, quantity, discount information, etc.

[0133] Depending on the retailer, on an average, a customer may make anywhere from two, e.g. electronic and sports retailers, to 50, e.g. grocery and home improvement retailers, visits to the store per year. Each transaction may result in the regular purchase, promotional purchase, return, or replacement of one or more products. A line-item associated with a return transaction of a product is generally identified by the negative revenue. Herein, we are concerned only with product purchases. We use the following formal notation to represent transactions:

• • [0134] The entire transaction data is represented by: $X={\left\{x^{\left(n\right)}\right\}}_{n=1^{\prime }}^N,$
    where
  • [0135] Transactions of customer n are represented by the time-stamped sequence of market baskets: $x^{\left(n\right)}=\left(\langle t_1^{\left(n\right)},x_1^{\left(n\right)}\rangle ,\dots ,\langle t_q^{\left(n\right)},x_q^{\left(n\right)}\rangle ,\dots ,\langle t_{Q_n}^n,x_{Q_n}^{\left(n\right)}\rangle \right),$
    Where:
  • [0136] t_q⁽ⁿ⁾ is the date of the q^th transaction by the n^th customer, and $x_q^{\left(n\right)}=y_{0,q}^{\left(n\right)}={\left\{x_{q,s}^{\left(n\right)}\right\}}_{s=1}^{S_{0,q}^{\left(n\right)}}\subseteq U_0$
    is the q^th market basket of n^th customer at level 0
  • [0137] Size of market basket at level 0 is s_0,q⁽ⁿ⁾
  • [0138] Market basket at resolution l is defined as: $y_{l,q}^{\left(n\right)}=\bigcup _{{\mathrm{xex}}_q^{\left(n\right)}}{M}_l\left(x\right)$

[0139] Properties in Retail Data

[0140] There are four types of objects in the retail data:

[0141] 1. Product—atomic level object in the product space

[0142] 2. Line Item—each line (atomic level object) in transaction data

[0143] 3. Transaction—collection of all line items associated with a single visit by a customer

[0144] 4. Customer—collection of all transactions associated with a customer

[0145] Typically, each of these objects is further associated with one or more properties that may be used to (i) filter, (ii) customize, or (iii) analyze the results of various retail applications. Notation and examples of properties of these four types of objects are as follows:

[0146] Product Properties

[0147] PeaCoCk recognizes two types of product properties:

[0148] (1) Given or Direct product properties that are provided in the product dictionary, e.g. manufacturer, brand name, product type (consumable, general merchandise, service, warranty, etc.), current inventory level in a store, product start date, product end date (if any), etc. These properties may also be level dependent, for example, manufacture code may be available only for the finest level.

[0149] (2) Computed or Indirect product properties are summary properties that can be computed from the transaction data using standard OLAP summarizations, e.g. average product revenue per transaction, total margin in the last one year, average margin percent, etc. Indirect properties of a coarser level product may be computed by aggregating the corresponding properties of its finer level products.

[0150] Line Item Properties

[0151] Each line item is typically associated with a number of properties such as quantity, cost, revenue, margin, line item level promotion code, return flag, etc.

[0152] Transaction Properties

[0153] PeaCoCk recognizes two types of transaction properties:

[0154] (1) Direct or Observed properties such as transaction channel, e.g. web, phone, mail, store id, etc., transaction level promotion code, transaction date, payment type used, etc. These properties are typically part of the transaction data itself.

[0155] (2) Indirect or Derived properties such as aggregates of the line item properties, e.g. total margin of the transaction, total number of products purchased, and market basket diversity across higher level product categories, etc.

[0156] Customer Properties

[0157] PeaCoCk recognizes three types of customer properties:

[0158] (1) Demographic Properties about each customer, e.g. age, income, zip code, occupation, household size, married/unmarried, number of children, owns/rent flag, etc., that may be collected by the retailer during an application process or a survey or from an external marketing database.

[0159] (2) Segmentation Properties are essentially segment assignments of each customer (and may be associated assignment weights) using various segmentation schemes, e.g. demographic segments, value based segments (RFMV), or purchase behavior based segment.

[0160] (3) Computed Properties are customer properties computed from customer transaction history, e.g. low vs. high value tier, new vs. old customer, angle vs. demon customer, early/late adopter etc.

[0161] Data Pre-processing

[0162] As described herein, the first step in the PeaCoCk process is data pre-processing. It involves two types of interspersed operations. As shown in FIG. 7, data pre-processing involves both data filtering (at customer, transaction, line item, and product levels) and customization (at customer and transaction levels).

[0163] Filtering

[0164] Not everything in the transaction data may be useful in a particular analysis. PeaCoCk manages this through a series of four filters based on the four object types in the transaction data: products, line items, transactions, customers.

[0165] (a) Product Filter: For some analyses, the retailer may not be interested in using all the products in the product space. A product filter allows the retailer to limit the products for an analysis in two ways:

• • [0166] (1) Product Scope List allows the retailer to create a list of in-scope products. Only products that are in this list are used in the analyses. For example, a manufacturer might be interested in analyzing relationships between his own products in a retailer's data;
  • [0167] (2) Product Stop List allows the retailer to create a list of out-of-scope products that must not be used in the analyses. For example, a retailer might want to exclude any discontinued products. These product lists may be created from direct and product properties.

[0168] (b) Line Item Filter: For some analyses, the retailer may not be interested in using all the line items in a customer's transaction data. For example, he may not want to include products purchased due to a promotion, or products that are returned, etc. Rules based on line item properties may be defined to include or exclude certain line items in the analyses.

[0169] (c) Transaction Filter: Entire transactions may be filtered out of the analyses based on transaction level properties. For example, one may be interested only in analyzing data from last three years or transactions containing at least three or more products, etc. Rules based on transaction properties may be used to include or exclude certain transactions from the analysis.

[0170] (d) Customer Filter: Finally, transaction data from a particular customer may be included or excluded from the analysis. For example, the retailer may want to exclude customers who did not buy anything in the last six months or who are in the bottom 30% by value. Rules based on customer properties may be defined to include or exclude certain customers from the analysis.

[0171] Customization

[0172] To create specific insights and/or tailored decisions, PeaCoCk allows customization of the analyses either by customer, e.g. for specific customer segments, or by transactions, e.g. for specific seasons or any combination of the two. This is achieved by applying the PeaCoCk analyses on a customization specific sample of the transaction data, instead of the entire data.

[0173] (a) Customer Customization: Retailers might be interested in customizing the analyses by different customer properties. One of the most common customer properties is the customer segment which may be created from a combination of demographic, relationship (i.e. how the customer buys at the retailer: recency, frequency, monetary value, (RFMV)), and behavior (i.e. what the customer buys at the retailer) properties associated with the customer. Apart from customer segments, customizations may also be done, for example, based on: customer value (high, medium, low value), customer age (old, new customers), customer membership (whether or not they are members of the retailer's program), customer survey responses, and demographic fields, e.g. region, income level, etc. Comparing PeaCoCk analyses results across different customer customizations and across all customers generally leads to valuable insight discovery.

[0174] (b) Transaction Customization: Retailers might be interested in customization of the analyses by different transaction properties. The two most common transaction customizations are: (a) Seasonal customization and (b) Channel customization. In seasonal customization the retailer might want to analyze customer behavior in different seasons and compare that to the overall behavior across all seasons. This might be useful for seasonal products, such as Christmas gifts or school supplies, etc. Channel customization might reveal different customer behaviors across different channels, such as store, web site, phone, etc.

[0175] Together all these customizations may result in specific insights and accurate decisions regarding offers of the right products to the right customers at the right time through the right channel. At the end of the data-preprocessing stage the raw transaction data is cleaned and sliced into a number of processed transaction data sets each associated with a different customization. Each of these now serve as possible inputs to the next stages in the PeaCoCk process.

[0176] Pair-wise Contextual Co-occurrences

[0177] According to the definition of PeaCoCk herein, it seeks pair-wise relationships between entities in specific contexts. In the following discussion, the notion of context is described in detail, especially as it applies to the retail domain. For each type of context the notion of a context instance, a basic data structure extracted from the transaction data, is described. These context instances are used to count how many times a product pair co-occurred in a context instance. These co-occurrence counts are then used in creating pair-wise relationships between products.

[0178] Definition of a Context

[0179] The concept of Context is fundamental to the PeaCoCk framework. A context is nothing but a way of defining the nature of relationship between two entities by way of their juxtaposition in the transaction data. The types of available contexts depend on the domain and the nature of the transaction data. In the retail domain, where the transaction data are a time-stamped sequence of market baskets, there are a number of ways in which two products may be juxtaposed in the transaction data. For example, two products may be purchased in the same visit, e.g. milk and bread, or one product may be purchased three months after another, e.g. a printer purchased three months after a PC, or a product might be purchased within six months of another product, e.g. a surround sound system may be purchased within six months of a plasma TV, or a product may be purchased between two to four months of another, e.g. a cartridge is purchased between two to four months of a printer or previous cartridge. The PeaCoCk retail mining framework is context rich, i.e. it supports a wide variety of contexts that may be grouped into two types as shown in FIG. 8: market basket context and purchase sequence context. Each type of context allows is further parameterized to define contexts as necessary and appropriate for different applications and for different retailer types.

[0180] For every context, PeaCoCk uses a three step process to quantify pair-wise co-occurrence consistencies for all product pairs: (α,β)∈U_l×U_l for each level l at which the PeaCoCk analysis is to be done:

[0181] (1) Create context instances from filtered and customized, transaction data slice,

[0182] (2) Count the number of times the two products co-occurred in those context instances, and

[0183] (3) Compute information theoretic measures to quantify consistency between them.

[0184] These three steps are described for both the market basket and purchase sequence contexts next.

[0185] Market Basket Context

[0186] Almost a decade of research in retail data mining has focused on market basket analysis. Traditionally, a market basket is defined as the set of products purchased by a customer in a single visit. In PeaCoCk, however, a market basket context instance is defined as a SET of products purchased on one or more consecutive visits. This definition generalizes the notion of a market basket context in a systematic, parametric way. The set of all products purchased by a customer (i) in a single visit, or (ii) in consecutive visits within a time window of (say) two weeks, or (iii) all visits of a customer are all valid parameterized instantiations of different market basket contexts. A versatile retail mining framework should allow such a wide variety of choices for a context for several reasons:

• • [0187] Retailer specific market basket resolution—Different market basket context resolution may be more appropriate for different types of retailers. For example, for a grocery or home improvement type retailer, where customers visit more frequently, a fine time resolution, e.g. single visit or visits within a week, market basket context might be more appropriate. While for an electronics or furniture type retailer, where customers visit less frequently, a coarse time resolution, e.g. six months or a year, market basket context might be more appropriate. Domain knowledge such as this may be used to determine the right time resolution for different retailer types.
  • [0188] Time elapsed intentions—As mentioned above, transaction data is a mixture of projections of possibly time-elapsed latent intentions of customers. A time elapsed intention may not cover all its products in a single visit. Sometimes the customer just forgets to buy all the products that may be needed for a particular intention, e.g. a multi-visit birthday party shopping, and may visit the store again the same day or the very next day or week. Sometimes the customer buys products as needed in a time-elapsed intention for example a garage re-modeling or home theater set up that might happen in different stages, the customer may choose to shop for each stage separately. To accommodate both these behaviors, it is useful to have a parametric way to define the appropriate time resolution for a forgot visit, e.g. a week, to a intentional subsequent visit, e.g. 15 to 60 days.

[0189] For a given market basket definition, the conventional association rules mining algorithms try to find high support and high confidence item-sets. As mentioned above, these approaches fail because of two fundamental reasons: First the logical product bundles or item-sets typically do not occur as the transaction data is only a projection of logical behavior and, secondly, using frequency in a domain where different products have different frequency of purchase leads to a large number of spurious item-sets. The PeaCoCk framework corrects these problems in a novel way as described above. Now let us consider the first two steps of creating pair-wise co-occurrence counts for the market basket context.

[0190] Creating Market Basket Context Instances

[0191] A parametric market basket context is defined by a single parameter: window width: ω. Algorithm 1 below describes how PeaCoCk creates market basket context instances, B_n, given:

• • [0192] A customer's transaction history: x⁽ⁿ⁾
  • [0193] The last update date (for incremental updates): t_last (which is 0 for the first update)
  • [0194] The window width parameter ω (number of days)

[0195] The function M that maps a SKU level market basket into a desired level basket.

	B = CreateMarketBasketContextInstances (x(n), tlast, ω, M)
	Initialize ⁢ : ⁢   ⁢ B ← ∅ ; q prev ← Q n + 1 ; q ← Q n
	While (q ≧ 1) and (tq ≧ tlast)
	q last ← q ;   ⁢ b q ← M ⁢   ⁢ ( x q ( n ) ) ;   ⁢ p ← q - 1
	While ⁢   ⁢   ( p ≥ 1 ) ⁢   ⁢ and ⁢   ⁢ ( ⌊ t q ( n ) - t p ( n ) ω ⌋ = 0 )
	b q ← b q ⋃ M ⁢   ⁢ ( x p ( n ) ) ;
	q last ← p ;   ⁢ p ← p - 1
	If (qlast < qprev) and (|bq| > 1)
	B ← B ⊕ b q
	q prev ← q last ;   ⁢ q ← q - 1
	Return B

[0196] The algorithm returns a (possibly empty) set of market basket context instances or a set of market baskets, B=B_n(ω). The parameter t_last is clarified later when we show how this function is used for the initial co-occurrence count and incremental co-occurrence updates since the last update.

[0197] The basic idea of Algorithm 1 is as follows: Consider a customer's transaction data shown in FIG. 9(a). In FIG. 9, each cell in the three time lines represents a day. A grey cell in the time line indicates that the customer made a purchase on that day. The block above the time line represents the accumulated market basket. The thick vertical lines represent the window boundary starting from any transaction day (dark grey cell) going backwards seven (window size in this example) days in the past. We start from the last transaction, (the darkest shade of grey) and accumulate two lighter grey market baskets in the time line, i.e. take the union of the dark grey market basket with the two lighter grey market baskets as they are purchased within a window of seven days prior to it. The union of all three results in the first market basket context instance represented by the block above the time line for this customer. In the second iteration, shown in FIG. 9(b), we move to the second last transaction and repeat the process. FIG. 9(c) highlights an important caveat in this process. If FIG. 9(c) represents the customer data instead of FIG. 9(a), i.e. the lightest grey transaction in FIG. 9(a) is missing. In the second iteration on FIG. 9(c), the resulting market basket context instance should be a union of the two (dark and lighter) grey market baskets. However, these two transactions are already part of the first market basket context instance in FIG. 9(a). Therefore, if FIG. 9(c) is the transaction history, then the market basket context instance in the second iteration is ignored because it is subsumed by the market basket context instance of the first iteration.

[0198] Creating Market Basket Co-occurrence Counts

[0199] PeaCoCk maintains the following four counts for each product level l at which the market basket analysis is done.

• • [0200] Total number of market basket instances: η_ω^mb(●,●) ${\eta }_{\omega }^{\mathrm{mb}}\left(·,·\right)=\sum _{n=1}^NB_n\left(\omega \right)$
  • [0201] Total number of market basket instances in which a product occurred, also known as product margin: η_ω^mb(α,●)=η_ω^mb(●,α) for all products α●U_l(δ(e) is 1 if the Boolean expression e is true, otherwise it is 0) ${\eta }_{\omega }^{\mathrm{mb}}\left(\alpha ,·\right)={\eta }_{\omega }^{\mathrm{mb}}\left(·,\alpha \right)=\sum _{n=1}^N\sum _{{\mathrm{beB}}_n\left(\omega \right)}\delta \left(\alpha \in b\right)$
  • [0202] Total number of market basket instances in which the product pair (α,β): α≠β co-occurred for all product pairs: $\left(\alpha ,\beta \right)\in U_l\times U_l:{\eta }_{\omega }^{\mathrm{mb}}\left(\alpha ,\beta \right)$ ${\eta }_{\omega }^{\mathrm{mb}}\left(\alpha ,\beta \right)={\eta }_{\omega }^{\mathrm{mb}}\left(\beta ,\alpha \right)=\sum _{n=1}^N\sum _{{\mathrm{beB}}_n\left(\omega \right)}\delta \left(\alpha \in b\right)\times \delta \left(\beta \in b\right)$

[0203] Note that the market basket context results in a symmetric co-occurrence counts matrix. Also, the diagonal elements of the matrix are zero because the product co-occurrence with itself is not a useful thing to define. A threshold is applied to each count such that if the count is less than the threshold, it is considered zero. Also note that the single visit market basket used in traditional market basket analysis tools is a special parametric case: ω=0.

[0204] Purchase Sequence Context

[0205] While market basket context is ubiquitous in the retail mining literature, it is clear that it either ignores when it uses single visits as market baskets, or looses when it uses consecutive visits as market baskets, temporal information that establishes contexts across time. These purchase sequence contexts as they are called in PeaCoCk may be very critical in making not only precise decisions about what product to offer a particular customer, but also timely decisions about when the product should be offered. For example, in grocery domain, there might be one group of customers who buy milk every week while another group who might buy milk once a month. In, for example electronics retailers, where this is even more useful, there might be one group of customers who use cartridge more quickly than others or who change their cell phones more frequently than others, etc. Further, there might be important temporal relationships between two or more products for example between a PC purchase; followed by a new printer purchase; followed by the first cartridge purchase. There might be consistent product phrases that may be result in important insights and forecasting or prediction decisions about customers. The purchase sequence type context in PeaCoCk makes such analyses possible.

[0206] Creating Purchase Sequence Context Instances

[0207] Unlike a market basket context instance, which is nothing but a market basket or a single set of products, the purchase sequence context instance is a triplet: (a,b,Δt) with three elements:

• • [0208] The from set: a=set of products purchased at some time in the past
  • [0209] The to set: b=set of products purchased at some time in the future (relative to set a)
  • [0210] The time lag between the two: Δt

[0211] The time t in the transaction data is in days. Typically, it is not useful to create purchase sequence context at this resolution because at this resolution we may not have enough data, moreover, this may be a finer resolution than the retailer can make actionable decisions on. Therefore, to allow a different time resolution, we introduce a parameter: ρ that quantifies the number of days in each time unit (Δt). For example, if ρ=7, the purchase sequence context is computed at week resolution. Algorithm 2 below describes the algorithm for creating a set of purchase sequence context instances, given:

• • [0212] A customer's transaction history: x⁽ⁿ⁾
  • [0213] The last update date (for incremental updates): t_last (which is 0 for the first update)
  • [0214] The time resolution parameter ρ
  • [0215] The function M that maps a SKU level market basket into a desired level basket.

[0216] The time in days is converted into the time units in Algorithm 2 using the function: $\gamma \left(t_{\mathrm{future}},t_{\mathrm{past}},\rho \right)=\lfloor \frac{t_{\mathrm{future}}-t_{\mathrm{past}}}{\rho }\rfloor$

[0217] The algorithm returns a (possibly empty) set of purchase sequence context instances or a set of triplets, (a, b, Δt), P=P_n(ρ). Again, the parameter t_last is clarified later when we show how this function is used for the initial co-occurrence count and incremental co-occurrence updates since the last update.

P = CreatePurchaseSequenceContextInstances (x(n), tlast, ρ, M)
Initialize ⁢ : ⁢   ⁢ P ← ∅ ;   ⁢ q ← Q n
While (q ≧ 2) and (tq ≧ tlast)
	b q ← M ⁢   ⁢ ( x q ( n ) ) ;   ⁢ p ← q - 1 ;
	While ⁢   ⁢ ( p ≥ 1 ) ⁢   ⁢ and ⁢   ⁢ ( γ ⁡ ( t q ( n ) , t p ( n ) , ρ ) = 0 ) ⇒ p ← p - 1 ; // Skip ⁢   ⁢ all ⁢   ⁢ market ⁢   ⁢ basket ⁢   ⁢ contexts
	If ⁢   ⁢ ( p = 0 ) ⇒ Break ;
	a q ← M ⁢   ⁢ ( x p ( n ) ) ; Δt last = γ ⁢   ⁢ ( t q ( n ) , t p ( n ) , ρ ) ; p ← p - 1 ;
	While (p ≧ 1)
	Δt = γ ⁢   ⁢ ( t q ( n ) , t p ( n ) , ρ )
	If ⁢   ⁢ ( Δt = Δt last ) ⇒ a q ← a q ⋃ M ⁢   ⁢ ( x p ( n ) ) ;
	Else
	If ⁢   ⁢ ( a q ≠ ∅ ) ⁢   ⁢ and ⁢   ⁢ ( b q ≠ ∅ ) ⇒   ⁢ P ←   ⁢ P ⊕   ⁢ 〈 a q , b q , Δt last 〉
	a q ← M ⁢   ⁢ ( x p ( n ) ) ; Δt last ← Δt
	p ← p - 1 ;
	If ⁢   ⁢ ( a q ≠ ∅ ) ⁢   ⁢ and ⁢   ⁢ ( b q ≠ ∅ ) ⇒   ⁢ P ←   ⁢ P ⊕   ⁢ 〈 a q , b q , Δt last 〉
Return P

[0218] FIG. 10 shows the basic idea of Algorithm 2. In FIG. 10, each non-empty cell represents a transaction. If the last grey square on the right is the TO transaction, then there are two FROM sets: the union of the two center grey square transactions and the union of the two left grey square transactions resulting, correspondingly, in two context instances. Essentially we start from the last transaction (far right) as in the market basket context. We ignore any transactions that might occur within the previous seven days (assuming the time resolution parameter ρ=7. Now continuing back, we find the two transactions at Δt=1 (second and third grey squares from the right). The union of the two becomes the first FROM set resulting in the purchase sequence context instance (the grey square above the time line union=FROM, last grey square on the right=TO, Δt=1. Going further back we find two transactions at Δt=2 (two left most grey squares). The union of these two becomes the second FROM set resulting in the purchase sequence context instance (grey square below the time line union=FROM, last grey square on the right=TO, Δt=1).

[0219] Creating Purchase Sequence Co-occurrence counts

[0220] In the market basket context, we have a symmetric 2-D matrix with zero diagonals to maintain the co-occurrence counts. In purchase sequence context, we use a non-symmetric, three dimensional matrix to denote the co-occurrence counts. PeaCoCk maintains the following matrices for the purchase sequence co-occurrence counts:

• • [0221] Total number of purchase sequence instances with each time lag $\mathrm{\Delta \tau }:{\eta }_{\rho }^{\mathrm{ps}}\left(·,·|\mathrm{\Delta \tau }\right)$ ${\eta }_{\rho }^{\mathrm{ps}}\left(·,·|\mathrm{\Delta \tau }\right)=\sum _{n=1}^N\sum _{\left(a,b,\Delta t\right){\mathrm{eP}}_n\left(\rho \right)}\delta \left(\Delta t=\mathrm{\Delta \tau }\right)$
  • [0222] Total number of market basket instances in which a product occurred in the FROM set a, (From Margin) for each time lag Δτ for all products $\alpha \in U_l:{\eta }_{\rho }^{\mathrm{ps}}\left(\alpha ,·|\mathrm{\Delta \tau }\right)$ ${\eta }_{\rho }^{\mathrm{ps}}\left(\alpha ,·|\mathrm{\Delta \tau }\right)=\sum _{n=1}^N\sum _{\left(a,b,\Delta t\right){\mathrm{eP}}_n\left(\rho \right)}\delta \left(\alpha \in a\right)\times \delta \left(\Delta t=\mathrm{\Delta \tau }\right)$
  • [0223] Total number of market basket instances in which a product occurred in the TO set b, (To Margin) for each time lag Δτ for all products $\beta \in U_l:{\eta }_{\rho }^{\mathrm{ps}}\left(•,\beta ❘\mathrm{\Delta \tau }\right)$ ${\eta }_{\rho }^{\mathrm{ps}}\left(•,\beta ❘\Delta \tau \right)=\sum _{n=1}^N\sum _{\left(a,b,\Delta t\right)\in P_n\left(\rho \right)}\delta \left(\beta \in b\right)\times \delta \left(\Delta t=\mathrm{\Delta \tau }\right)$
  • [0224] Total number of market basket instances in which the product pair (α,β):α≠β co-occurred where the FROM product a occurred time lag Δt before the TO product β for all product pairs: $\left(\alpha ,\beta \right)\in U_l\times U_l:{\eta }_{\rho }^{\mathrm{ps}}\left(\alpha ,\beta ❘\mathrm{\Delta \tau }\right)$ ${\eta }_{\rho }^{\mathrm{ps}}\left(\alpha ,\beta ❘\mathrm{\Delta \tau }\right)=\sum _{n=1}^N\sum _{\left(a,b,\Delta t\right)\in P_n\left(\rho \right)}\delta \left(\alpha \in a\right)\times \delta \left(\beta \in b\right)\times \delta \left(\Delta t=\mathrm{\Delta \tau }\right)$ ${\eta }_{\rho }^{\mathrm{ps}}\left(\alpha ,\beta ❘\mathrm{\Delta \tau }\right)={\eta }_{\rho }^{\mathrm{ps}}\left(\beta ,\alpha ❘-\mathrm{\Delta \tau }\right)$

[0225] Note that:

[0226] Initial vs. Incremental Updates

[0227] Transaction data are collected on a daily basis as customers shop. When in operation, the PeaCoCk co-occurrence count engine uses an initial computation of the four counts: totals, margins, and co-occurrence counts using one pass through the transaction data. After that incremental updates may be done on a daily, weekly, monthly, or quarterly basis depending on how the incremental updates are set up.

• • [0228] Let t₀=the earliest date such that all transactions on or after this date to be included.

[0229] Let t_last=the last transaction date of last update

InitialUpdate(t0,ω,M)
	For n = 1...N
	Bn(ω)=CreateMarketBasketContextInstance(x(n),t0,ω,M)
	ProcessMarketBasketContext(Bn(ω))
	Pn(ρ)=CreatePurchaseSequenceContextInstance(x(n),t0,ρ,M)
	ProcessPurchaseSequenceContext(Pn(ρ))
IncrementalUpdate(tlast,ω,M)
	For n = 1...N
	If( > tlast) // If the customer purchased since last update
	Bn(ω)=CreateMarketBasketContextInstance(x(n),tlast,ω,M)
	ProcessMarketBasket(Bn(ω))
	Pn(ρ)=CreatePurchaseSequenceContextInstance(x(n),t0,ρ,M)
	ProcessPurchaseSequenceContext(Pn(ρ))

[0230] The time complexity of the initial update is $O\left(\sum _{n=1}^N{Q}_n^2\right)$
and the time complexity of the incremental update is $O\left(\sum _{n=1}^N{I}_n^2\right)$
where I_n is the number of new transactions since the last update.

[0231] Consistency Measures

[0232] PeaCoCk framework does not use the raw co-occurrence counts (in either context) because the frequency counts do not normalize for the margins. Instead, PeaCoCk uses consistency measures based on information theory and statistics. A number of researchers have created a variety of pair-wise consistency measures with different biases that are available for use in PeaCoCk. In the following discussion, we describe how these consistency matrices may be computed from the sufficient statistics that we have already computed in the co-occurrence counts.

[0233] Definition of Consistency

[0234] Instead of using frequency of co-occurrence, we use consistency to quantify the strength of relationships between pairs of products. Consistency is defined as the degree to which two products are more likely to be co-purchased in a context than they are likely to be purchased independently. There are a number of ways to quantify this definition. The four counts, i.e. the total, the two margins, and the co-occurrence, are sufficient statistics needed to compute pair-wise co-occurrence. FIG. 11 shows the four counts and their Venn diagram interpretation. For any product pair (α,β) let A denote the set of all the context instances in which product α occurred and let B denote the set of all context instances in which product β occurred and let T denote the set of all context instances.

[0235] In terms of these sets,  η(α,β)=|A∩B|:η(●,●)=|T|
η(α,●)=|A|;η(●,β)=|B|

[0236] In the left and the right Venn diagrams, the overlap between the two sets is the same. However, in case of sets A′ and B′, the relative size of the overlap compared to the sizes of the two sets is higher than that for the sets A and B and hence by our definition, the consistency between A′, B′ is higher than the consistency between A, B.

[0237] For the purchase sequence context, the four counts are available at each time-lag therefore all the equations above and the ones that follow can be generalized to purchase sequence as follows: η(*, *)→η(*,*|Δτ), i.e. all pair-wise counts are conditioned on the time-lag in the purchase sequence context.

[0238] Co-occurrence counts: Sufficient Statistics

[0239] The counts, i.e. total, the margin(s), and the co-occurrence counts, are sufficient statistics to quantify all the pair-wise co-occurrence consistency measures in PeaCoCk. From these counts, we can compute the following probabilities: $P\left(\alpha ,•\right)=\frac{\eta \left(\alpha ,•\right)}{\eta \left(•,•\right)};P\left(\stackrel{\_}{\alpha },•\right)=1-P\left(\alpha ,•\right)=\frac{\eta \left(•,•\right)-\eta \left(\alpha ,•\right)}{\eta \left(•,•\right)}$ $P\left(\beta ,•\right)=\frac{\eta \left(•,\beta \right)}{\eta \left(•,•\right)};P\left(•,\stackrel{\_}{\beta }\right)=1-P\left(\beta ,•\right)=\frac{\eta \left(•,•\right)-\eta \left(•,\beta \right)}{\eta \left(•,•\right)}$ $P\left(\alpha ,\beta \right)=\frac{\eta \left(\alpha ,\beta \right)}{\eta \left(•,•\right)};$ $P\left(\stackrel{\_}{\alpha },\stackrel{\_}{\beta }\right)=\frac{\eta \left(•,•\right)-\left[\eta \left(\alpha ,•\right)+\eta \left(•,\beta \right)-\eta \left(\alpha ,\beta \right)\right]}{\eta \left(•,•\right)}$ $P\left(\alpha ,\stackrel{\_}{\beta }\right)=\frac{\eta \left(\alpha ,•\right)-\eta \left(\alpha ,\beta \right)}{\eta \left(•,•\right)};P\left(\stackrel{\_}{\alpha },\beta \right)=\frac{\eta \left(•,\beta \right)-\eta \left(\alpha ,\beta \right)}{\eta \left(•,•\right)}$

[0240] There are two caveats in these probability calculations: First if any of the co-occurrence or margin counts is less than a threshold then it is treated as zero. Second, it is possible to use smoother versions of the counts, which is not shown in these equations. Finally, if due to data sparsity, there are not enough counts, then smoothing from coarser class levels may also be applied.

[0241] Consistency Measures Library

[0242] There are a number of measures of interestingness that have been developed in statistics, machine learning, and data mining communities to quantify the strength of consistency between two variables. All these measures use the probabilities discussed above. Examples of some of the consistency measures are given below.

• • [0243] Context between all pairs of products at any product level is stored in a Consistency Matrix: Φ
    • [0244] For Market Basket Context
      Φ=[φ(α,β)]:∀α,β∈U_l
      φ(α,β)=f(η(●,●),η(α,●),η(●,β),η(α,β))
    • [0245] For Purchase Sequence Context used in product phrases:
      Φ=[φ(α,β;Δτ)]:∀α,β∈U_l,Δτ∈[0 . . . ΔT]
      φ(α,β;←τ)=f(η(●,●;←τ),η(α,●;Δτ),η(●,β;Δτ),η(α,β;←τ))

[0246] Before we go into the list of consistency measures, it is important to note some of the ways in which we can characterize a consistency measure. While all consistency measures normalize for product priors in some way, they may be:

• • [0247] Symmetric (non-directional) vs. Non-symmetric (directional)—There are two kinds of directionalities in PeaCoCk. One is the temporal directionality that is an inherent part of the purchase sequence context and which is missing from the market basket context. The second kind of directionality is based on the nature of the consistency measure. By definition:
    • [0248] φ(α,β)=φ(β,α)Symmetric Market Basket Cotisistency
    • [0249] φ(α|β)≠φ(β|α)Asymmetric Market Basket Consistency
    • [0250] φ(α,β;Δt)=φ(β,α;−Δt)Symmetric Purchase Sequence Consistency
    • [0251] φ(α|β;Δt)≠φ(β|α;−Δt)Asymetric Purcilase Sequence Consistency
  • [0252] Normalized or Un-normalized—Consistency measures that take a value in a fixed range (say 0-1) are considered normalized and those that take values from negative infinity (or zero) to positive infinity are considered un-normalized.
  • [0253] Uses absence of products as information or not—Typically in retail, the probability of absence of a product either in the margins or in the co-occurrence, i.e. P( α,●), P(●, β), P( α,β), P(α, β), P( α, β) would be relatively higher than the probability of the presence of the product, i.e. P(α, ●), P(●,β), P(α,β). Some consistency measures use absence of products also as information which may bias the consistency measures for rare or frequent products.

[0254] These properties are highlighted as appropriate for each of the consistency measures in the library. For the sake of brevity, in the rest of this discussion, we use the following shorthand notation for the marginal probabilities:
P(α,●)≡P(α); P(●,β)≡P(β)

[0255] Statistical Measures of Consistency

[0256] Pearson's Correlation Coefficient

[0257] Correlation coefficient quantifies the degree of linear dependence between two variables which are binary in our case indicating the presence or absence of two products. It is defined as: $\varphi \left(\alpha ,\beta \right)=\frac{\mathrm{Cov}\left(\alpha ,\beta \right)}{\mathrm{Std}\left(\alpha \right)\mathrm{Std}\left(\beta \right)}=\frac{{\chi }^2}{\eta \left(•,•\right)}=\frac{P\left(\alpha ,\beta \right)P\left(\stackrel{\_}{\alpha },\stackrel{\_}{\beta }\right)-P\left(\alpha ,\stackrel{\_}{\beta }\right)P\left(\stackrel{\_}{\alpha },\beta \right)}{\sqrt{P\left(\alpha ,•\right)P\left(\stackrel{\_}{\alpha },•\right)P\left(•,\beta \right)P\left(•,\stackrel{\_}{\beta }\right)}}\in \left[-1,+1\right]$

[0258] Comments:

• • [0259] Symmetric and Normalized, Related to χ².
  • [0260] Uses both presence and absence of products as information. Hard to distinguish whether the correlation is high because of co-occurrence, i.e. P(α,β) or because of co-non-occurrence, i.e. P( α, β). The latter tends to outweigh the former.

[0261] Goodman and Kruskal's λ-Coefficient

[0262] λ-coefficient minimizes the error of predicting one variable given the other. Hence, it can be used in both a symmetric and a non-symmetric version:

[0263] Asymmetric Versions: $\varphi \left(\alpha ❘\beta \right)=\frac{P\left({\varepsilon }_{\alpha }\right)-P\left({\varepsilon }_{\alpha }❘\beta \right)}{P\left({\varepsilon }_{\alpha }\right)}=\frac{M\left(\alpha ❘\beta \right)+M\left(\alpha ❘\stackrel{\_}{\beta }\right)-M\left(\alpha \right)}{1-M\left(\alpha \right)}$ $\varphi \left(\beta ❘\alpha \right)=\frac{P\left({\varepsilon }_{\beta }\right)-P\left({\varepsilon }_{\beta }❘\alpha \right)}{P\left({\varepsilon }_{\beta }\right)}=\frac{M\left(\beta ❘\alpha \right)+M\left(\beta ❘\stackrel{\_}{\alpha }\right)-M\left(\beta \right)}{1-M\left(\beta \right)}$ $\mathrm{Where}$ $M\left(\alpha ❘\beta \right)=\max \left\{P\left(\alpha ,\beta \right),P\left(\stackrel{\_}{\alpha },\beta \right)\right\};$ $M\left(\alpha ❘\stackrel{\_}{\beta }\right)=\max \left\{P\left(\alpha ,\stackrel{\_}{\beta }\right),P\left(\stackrel{\_}{\alpha },\stackrel{\_}{\beta }\right)\right\}$ $M\left(\beta ❘\alpha \right)=\max \left\{P\left(\alpha ,\beta \right),P\left(\alpha ,\stackrel{\_}{\beta }\right)\right\};$ $M\left(\beta ❘\stackrel{\_}{\alpha }\right)=\max \left\{P\left(\stackrel{\_}{\alpha },\beta \right),P\left(\stackrel{\_}{\alpha },\stackrel{\_}{\beta }\right)\right\}$ $M\left(\alpha \right)=\max \left\{P\left(\alpha \right),P\left(\stackrel{\_}{\alpha }\right)\right\};M\left(\beta \right)=\max \left\{P\left(\beta \right),P\left(\stackrel{\_}{\beta }\right)\right\}$

[0264] Symmetric Versions: $\begin{array}{c}\varphi \left(\alpha ,\beta \right)=\frac{P\left({\varepsilon }_{\alpha }\right)+P\left({\varepsilon }_{\beta }\right)-P\left({\varepsilon }_{\alpha }❘\beta \right)-P\left({\varepsilon }_{\beta }❘\alpha \right)}{P\left({\varepsilon }_{\alpha }\right)+P\left({\varepsilon }_{\beta }\right)}\\ =\frac{\begin{array}{c}M\left(\alpha ❘\beta \right)+M\left(\alpha ❘\stackrel{\_}{\beta }\right)+M\left(\beta ❘\alpha \right)+M\left(\beta ❘\stackrel{\_}{\alpha }\right)-\\ M\left(\alpha \right)-M\left(\beta \right)\end{array}}{2-M\left(\alpha \right)-M\left(\beta \right)}\end{array}$

[0265] Comments:

• • [0266] Both symmetric and non-symmetric versions available
  • [0267] Affected more by the absence of products than their presence

[0268] Odds Ratio and Yule's Coefficients

[0269] Odds Ratio measures the odds of two products occurring or not occurring compared to one occurring and another non-occurring: The odds ratio is given by: $\varphi \left(\alpha ,\beta \right)=\mathrm{odds}\left(\alpha ,\beta \right)=\frac{P\left(\alpha ,\beta \right)P\left(\stackrel{\_}{\alpha },\stackrel{\_}{\beta }\right)}{P\left(\stackrel{\_}{\alpha },\beta \right)P\left(\alpha ,\stackrel{\_}{\beta }\right)}$

[0270] Odds may be unbounded and hence two other measures based on odds ratio are also proposed:

[0271] Youle-Q: $\varphi \left(\alpha ,\beta \right)=\frac{\mathrm{odds}\left(\alpha ,\beta \right)-1}{\mathrm{odds}\left(\alpha ,\beta \right)+1}=\frac{P\left(\alpha ,\beta \right)P\left(\stackrel{\_}{\alpha },\stackrel{\_}{\beta }\right)-P\left(\stackrel{\_}{\alpha },\beta \right)P\left(\alpha ,\stackrel{\_}{\beta }\right)}{P\left(\alpha ,\beta \right)P\left(\stackrel{\_}{\alpha },\stackrel{\_}{\beta }\right)+P\left(\stackrel{\_}{\alpha },\beta \right)P\left(\alpha ,\stackrel{\_}{\beta }\right)}$

[0272] Youle's-Y: $\varphi \left(\alpha ,\beta \right)=\frac{\sqrt{\mathrm{odds}\left(\alpha ,\beta \right)}-1}{\sqrt{\mathrm{odds}\left(\alpha ,\beta \right)}+1}=\frac{\sqrt{P\left(\alpha ,\beta \right)P\left(\stackrel{\_}{\alpha },\stackrel{\_}{\beta }\right)}-\sqrt{P\left(\stackrel{\_}{\alpha },\beta \right)P\left(\alpha ,\stackrel{\_}{\beta }\right)}}{\sqrt{P\left(\alpha ,\beta \right)P\left(\stackrel{\_}{\alpha },\stackrel{\_}{\beta }\right)}+\sqrt{P\left(\stackrel{\_}{\alpha },\beta \right)P\left(\alpha ,\stackrel{\_}{\beta }\right)}}$

[0273] Piatetsky-Shapiro's
φ(α\β)=P(α,β)−P(α)P(β)

[0274] Added Value $\varphi \left(\alpha \text{❘}\beta \right)=\max \left\{P\left(\beta \text{❘}\alpha \right)-P\left(\beta \right),P\left(\alpha \text{❘}\beta \right)-P\left(\alpha \right)\right\}=\frac{P\left(\alpha ,\beta \right)-P\left(\beta \right)}{\min \left\{P\left(\alpha \right),P\left(\beta \right)\right\}}$
Klosgen $\begin{array}{c}\varphi \left(\alpha \text{❘}\beta \right)=\sqrt{P\left(\alpha ,\beta \right)}\max \left\{P\left(\beta \text{❘}\alpha \right)-P\left(\beta \right),P\left(\alpha \text{❘}\beta \right)-P\left(\alpha \right)\right\}\\ =\sqrt{P\left(\alpha ,\beta \right)}\left[\frac{P\left(\alpha ,\beta \right)-P\left(\beta \right)}{\min \left\{P\left(\alpha \right),P\left(\beta \right)\right\}}\right]\end{array}$

[0275] Certainty Coefficients

[0276] Asymmetric Versions: $\varphi \left(\alpha \text{❘}\beta \right)=\frac{P\left(\alpha \text{❘}\beta \right)-P\left(\beta \right)}{1-P\left(\beta \right)};\varphi \left(\beta \text{❘}\alpha \right)=\frac{P\left(\beta \text{❘}\alpha \right)-P\left(\alpha \right)}{1-P\left(\alpha \right)}$

[0277] Symmetric Version: $\varphi \left(\alpha ,\beta \right)=\max \left\{\frac{P\left(\alpha ,\beta \right)-P\left(\beta \right)}{1-P\left(\beta \right)},\frac{P\left(\beta ,\alpha \right)-P\left(\alpha \right)}{1-P\left(\alpha \right)}\right\}$

[0278] Data Mining Measures of Consistency

[0279] Support
φ(α,β)=P(α,β)

[0280] Confidence

[0281] Asymmetric Version: $\varphi \left(\alpha \text{❘}\beta \right)=P\left(\alpha \text{❘}\beta \right)=\frac{P\left(\alpha ,\beta \right)}{P\left(\beta \right)};\varphi \left(\beta \text{❘}\alpha \right)=P\left(\beta \text{❘}\alpha \right)=\frac{P\left(\alpha ,\beta \right)}{P\left(\alpha \right)}$

[0282] Symmetric Version: $\varphi \left(\alpha ,\beta \right)=\max \left\{P\left(\alpha \text{❘}\beta \right),P\left(\beta \text{❘}\alpha \right)\right\}=\frac{P\left(\alpha ,\beta \right)}{\min \left\{P\left(\alpha \right),P\left(\beta \right)\right\}}$

[0283] Conviction

[0284] Asymmetric Version: $\varphi \left(\alpha \text{❘}\beta \right)=\frac{P\left(\stackrel{\_}{\alpha }\right)P\left(\beta \right)}{P\left(\stackrel{\_}{\alpha },\beta \right)};\varphi \left(\beta \text{❘}\alpha \right)=\frac{P\left(\alpha \right)P\left(\stackrel{\_}{\beta }\right)}{P\left(\alpha ,\stackrel{\_}{\beta }\right)}$

[0285] Symmetric Version: $\varphi \left(\alpha ,\beta \right)=\max \left\{\frac{P\left(\stackrel{\_}{\alpha }\right)P\left(\beta \right)}{P\left(\stackrel{\_}{\alpha },\beta \right)},\frac{P\left(\alpha \right)P\left(\stackrel{\_}{\beta }\right)}{P\left(\alpha ,\stackrel{\_}{\beta }\right)}\right\}$

[0286] Interest and Cosine $\mathrm{Interest}\text{:}\varphi \left(\alpha ,\beta \right)=\frac{P\left(a,b\right)}{P\left(a\right)P\left(b\right)}\in \left[0,\dots ,1,\dots ,\infty \right]$ $\mathrm{Cosine}\text{:}\varphi \left(\alpha ,\beta \right)=\frac{P\left(a,b\right)}{\sqrt{P\left(a\right)P\left(b\right)}}\in \left[0,\dots ,\sqrt{P\left(a\right)P\left(b\right)},\dots ,1\right]$

[0287] Collective Strength $\varphi \left(\alpha ,\beta \right)=\left[\frac{P\left(\alpha ,\beta \right)+P\left(\stackrel{\_}{\alpha },\stackrel{\_}{\beta }\right)}{P\left(\alpha \right)P\left(\beta \right)+P\left(\stackrel{\_}{\alpha }\right)P\left(\stackrel{\_}{\beta }\right)}\right]\times \left[\frac{1-P\left(\alpha \right)P\left(\beta \right)-P\left(\stackrel{\_}{\alpha }\right)P\left(\stackrel{\_}{\beta }\right)}{1-P\left(\alpha ,\beta \right)-P\left(\stackrel{\_}{\alpha },\stackrel{\_}{\beta }\right)}\right]$

[0288] Information Theoretic Measures of Consistency

[0289] Point-Wise Mutual Information $\varphi \left(\alpha ,\beta \right)=\log \left[\frac{P\left(a_{2}b\right)}{P\left(a\right)P\left(b\right)}\right]$

[0290] PeaCoCk Suite of Applications

[0291] PeaCoCk is a general framework that allows formulation and solution of a number of different problems in retail. For example, it may be used to solve problems as varied as:

[0292] (i) customer segmentation using pair-wise similarity relationships between customers,

[0293] (ii) creating product bundles or consistent item-sets using pair-wise consistency between products purchased in market basket context, or

[0294] (iii) predicting the time and product of the next possible purchase of a customer using pair-wise consistency between products purchased in a purchase sequence context.

[0295] From a technology perspective, the various applications of PeaCoCk are divided into three categories:

• • [0296] Product Affinity Applications—that use product consistency relationships to analyze the product space. For example, finding higher order structures such as bundles, bridges, and phrases and using these for cross-sell, co-promotion, store layout optimization, etc.
  • [0297] Customer Affinity Applications—that use customer similarity relationships to analyze the customer space. For example, doing customer segmentation based on increasingly complex definitions of customer behavior and using these to achieve higher customer centricity.
  • [0298] Purchase Behavior Applications—that use both the products and the customers to create decisions in the joint product, customer space. For example, recommending the right product to the right customer at the right time.

[0299] FIG. 12 shows applications within each of these areas both from a technology and business perspective. The following discussion concerns the various product affinity applications created from PeaCoCk analysis.

[0300] PeaCoCk Product consistency graphs are the internal representation of the pair-wise co-occurrence consistency relationships created by the process described above. Once the graph is created, PeaCoCk uses graph theoretic and machine learning approaches to find patterns of interest in these graphs. While we could use the pair-wise relationships as such to find useful insights, the real power of PeaCoCk comes from its ability to create higher order structures from these pair-wise relationships in a very novel, scalable, and robust manner, resulting in tremendous generalization that is not possible to achieve by purely data driven approaches. The following discussion focuses on four important higher-order-structures that might constitute actionable insights:

[0301] (a) Product neighborhood,

[0302] (b) product bundles,

[0303] (c) bridge structures, and

[0304] (d) product phrases.

[0305] Before we go into these structures, however, we define a useful abstraction called the Product Space.

[0306] Product Space Abstraction

[0307] We introduced the notion of product space above as a collection of products and their properties. Now that we have a way to quantify connection strength (co-occurrence consistency) between all pairs of products, we can use this to create a discrete, finite, non-metric product space where:

• • [0308] Each point in this space is a product. There are as many points as there are products.
  • [0309] There is one such product space for each level in the product hierarchy and for each combination of customization, market basket context parameter, and customization.
  • [0310] The pair-wise co-occurrence consistency quantifies the proximity between two points. The higher the consistency, the closer the two points are.
  • [0311] The product space is not metric in the sense that it does not strength of connection between them.

[0312] Product Neighborhood

[0313] The simplest kind of insight about a product is that regarding the most consistent products sold with the target product in the PeaCoCk graph or the products nearest to a product in the Product Space abstraction. This type of insight is captured in the product neighborhood analysis of the PeaCoCk graph.

[0314] Definition of a Product Neighborhood

[0315] The neighborhood of a product is defined as an ordered set of products that are consistently co-purchased with it and satisfying all the neighborhood constraints. The neighborhood of a product his denoted by N_λ(γ|Φ), where:

• • [0316] Φ is the consistency matrix with respect to which neighborhood is defined:
  • [0317] λ={λ_scope,λ_size} are the neighborhood constraints based the parameters:
    N_λ(γ|Φ)={χ₁, χ₂, . . . , χ_K}
    Such that:
    φ(γ,χ_k)≧φ(γ,χ_k+1):∀k=1 . . . K−1
    g_scope(χ_k, λ_scope)=TRUE:∀k=1 . . . k
    g_size(N_λ(γ|Φ),λ_size)=TRUE:∀k=1 . . . K

[0318] Note that the set is ordered by the consistency between the target product and the neighborhood products: The most consistent product is the first neighbor of the target product, and so on. Also note that here are two kinds of constraints associated with a neighborhood:

[0319] Scope Constraint: This constraint filters the scope of the products that may or may not be part of the neighborhood. Essentially, these scope-filters are based on product properties and the parameter λ_scope encapsulates all the conditions. For example, someone might be interested in the neighborhood to be limited only to the target product's department or some particular department or to only high value products or only to products introduced in the last six months, etc. The function g_{scope(χ,λscope}) returns a true if the product x meets all the criteria in λ_scope.

[0320] Size Constraint: Depending on the nature of the context used, the choice of the consistency measure, and the target product itself the size of the product neighborhood might be large even after applying the scope constraints. There are three ways to control the neighborhood size:

• • [0321] Limit the number of products in the neighborhood:  g_size(N_λ(γ|Φ),λ_size^limit)=N_λ(γ|Φ)=K≦λ_size^limit
  • [0322] Apply an absolute threshold on consistency (absolute consistency radius):
    g_zise(N_λ(γ|Φ),λ_size^{absolute-threshold})=φ(γ,χ_K)≧λ_size^{absolute-threshold}
  • [0323] Apply a relative threshold on the consistency between target and neighborhood product: $g_{\mathrm{size}}\left(N_{\lambda }\left(\gamma \text{❘}\Phi \right),{\lambda }_{\mathrm{size}}\right)=\frac{\varphi \left(\gamma ,x_K\right)}{\varphi \left(\gamma ,x_1\right)}\ge {\lambda }_{\mathrm{size}}^{\mathrm{relative}-\mathrm{threshold}}$

[0324] Business Decisions based on Product Neighborhoods

[0325] Product neighborhoods may be used in several retail business decisions. Examples of some are given below:

• • [0326] Product Placement—To increase customer experience resulting in increased customer loyalty and wallet share for the retailer, it may be useful to organize the store in such a way that finding products that its customers need is easy. This applies to both the store and the web layout. Currently, stores are organized so all products that belong to the same category or department are placed together. There are no rules of thumb, however, how the products may be organized within a category or categories may be organized within the departments or how the departments may be organized within the store. Product neighborhood at the department and category level may be used to answer such questions. The general principle is that for every product category, its neighboring categories in the product space should be placed nearby this category.
  • [0327] Customized store Optimization—Product placement is a piecemeal solution for the overall problem of store optimization. PeaCoCk graphs and product neighborhoods derived from them may be used to optimize the store layout. Store layout may be formulated as a multi-resolution constrained optimization problem. First, the departments are optimally placed in the store. Second, the categories within each department are placed relative to each other in an optimal fashion, and so on. Since PeaCoCk graphs may be customized by stores, each store may be independently optimized based on its own co-occurrence consistency.
  • [0328] Influence based Strategic Promotions—Several retail business decisions such as pricing optimization, cross-sell, up-sell, etc. depend on how much a product influences the sale of other products. PeaCoCk graphs provide a framework for creating such product influence models based on product neighborhoods. In the next Section, two co-occurrence based product properties: product density and product diversity are defined. These properties may be used appropriately to strategically promote these products to influence the sale of other products with a wide variety of overall business goals.

[0329] Neighborhood based Product Properties

[0330] As discussed above, a number of direct and indirect product properties were introduced. The direct properties such as manufacturer, hierarchy level, etc. are part of the product dictionary. Indirect properties such as total revenue, margin percent per customer, etc. may be derived by simple OLAP statistics on transaction data. In the following discussion we introduce two more product properties that are based on the neighborhood of the product in the product graph: Value-based Product Density and Value-based Product Diversity.

[0331] Value-based Product Density

[0332] If the business goal for the retailer is to increase the sale of high margin products or high revenue products, a direct approach would be to promote those products more aggressively. An indirect approach would be to promote those products that influence the sale of high margin or high revenue products. This principle can be generalized whereby if the business goal is related to a particular product property then a value-based product density based on its product neighborhood may be defined for each product.

[0333] For a given product neighborhood, i.e. neighborhood constraints, consistency measure, and product value-property ν (revenue, frequency, etc.), the value-density of a product is defined as the linear combination of the follows:
D_ν(γ|λ, Φ, θ)=Σ_χ∈Nχw(χ|γ, θ, Φ)ν(x)
Where:

• • [0334] w(γ|x, θ, Φ)=weight-of-influence of the neighboring product x on the target product γ
  • [0335] ν(x)=value of product x with respect to which the value-density is computed; and
  • [0336] θ={θ₁, θ₂, . . . }=set of parameters associated with the weight function.

[0337] An example of the Gibbs weight function is: $w\left(x\text{❘}\gamma ,\theta ,\Phi \right)={\varphi \left(\gamma ,x\right)}^{{\theta }_1}\times \frac{\exp \left({\theta }_2\times \varphi \left(\gamma ,x\right)\right)}{\sum _{x^{\prime }\in N_{\lambda }\left(\gamma \text{❘}\Phi \right)}\exp \left({\theta }_2\times \varphi \left(\gamma ,x^{\prime }\right)\right)}\text{:}{\theta }_1\in \left\{0,1\right\},{\theta }_2\in \left[0,\infty \right]$

[0338] The parameter θ₂ can be interpreted as the temperature for the Gibb's distribution. When the parameter θ₁0 the weights are normalized otherwise the weights take the consistency into account.

[0339] Value-based product densities may be used in a number of ways. In the recommendation engine post processing, for example, the value-based density may be used to adjust the recommendation score for different objective functions.

[0340] Value-Based Product Diversity

[0341] Sometimes the business objective of a retailer is to increase diversity of a customer shopping behavior, i.e. if the customer shops in only one department or category of the retailer, then one way to increase the customer's wallet share is to diversify his purchases in other related categories. This can be accomplished in several ways, for example, by increasing (a) cross-traffic across departments, (b) cross-sell across multiple categories, or (c) diversity of the market basket. PeaCoCk graphs may be used to define value-based product diversity of each product. In recommendation engine post-processing, this score may be used to push high diversity score products to specific customers.

[0342] For every product γ, product property ν, and product level tabove the level of product γ, value based product diversity is defined as the variability in the product density along different categories at level l:
D_ν(γ|λ_scope=u_l, Φ, θ)=D_ν(γ|m, Φ, θ):∀m∈{1, . . . , M_l}

[0343] Diversity should be low (say zero) if all the neighbors of the products are in the same category as the product itself, otherwise the diversity is high. An example of such a function is: $\Delta D_v\left(\gamma \text{❘}l,\Phi ,\theta \right)=1-\frac{D_v\left(\gamma \text{❘}\Phi ,m\left(\gamma \right),\theta \right)}{\sum _{m=1}^{M_l}{D}_v\left(\gamma \text{❘}\Phi ,m,\theta \right)}\text{:}\forall m\in \left\{1,\dots ,M_l\right\}$

[0344] Product Bundles

[0345] One of the most important types of insight in retail pertains to product affinities or product groupings of products that are “co-purchased” in the same context. In the following discussion describes the application of PeaCoCk in finding, what we call, “Product bundles” in a highly scalable, generalized, and efficient way that they exceed both the quality and efficiency of the results of traditional frequency based market basket approaches. A large body of research in market-basket-analysis is focused on efficiently finding frequent item-sets, i.e. a set of products that are purchased in the same market basket. The support of an item-set is the number of market baskets in which it or its superset is purchased. The confidence of any subset of an item-set is the conditional probability that the subset will be purchased, given that the complimentary subset is purchased. Algorithms have been developed for breadth-first search of high support item-sets. Due to the reasons explained above, the results of such analysis have been largely unusable because this frequency based approach misses the fundamental observation that the customer behavior is a mixture of projections of latent behaviors. As a result, to find one actionable and insightful item-set, the support threshold has to be lowered so that typically millions of spurious item-sets have to be looked at.

[0346] PeaCoCk uses transaction data to first create only pair-wise co-occurrence consistency relationships between products. These are then used to find logical bundles of more than two products. PeaCoCk Product bundles and algorithm based item-sets are product sets, but they are very different in the way they are created and characterized.

[0347] Definition of a Logical Product Bundle

[0348] A PeaCoCk product bundle may be defined as a Soft Clique (completely connected sub-graphs) in the weighted PeaCoCk graph, i.e. a product bundle is a set of products such that the co-occurrence consistency strength between all pairs of products is high. FIG. 4 shows examples of some product bundles. The discussion above explained that the generalization power of PeaCoCk occurs because it extracts only pair-wise co-occurrence consistency strengths from mixture of projections of latent purchase behaviors and uses this to find logical structures instead of actual structures in these PeaCoCk graphs.

[0349] PeaCoCk uses a proprietary measure called bundleness to quantify the cohesiveness or compactness of a product bundle. The cohesiveness of a product bundle is considered high if every product in the product bundle is highly connected to every other product in the bundle. The bundleness in turn is defined as an aggregation of the contribution of each product in the bundle. There are two ways in which a product contributes to a bundle in which it belongs: (a) It can either be the principal or driver or causal product for the bundle or (b) it can be the peripheral or accessory product for the bundle. For example, in the bundle shown in FIG. 6, the Notebook is the principal product and the mouse is the peripheral product of the bundle. In PeaCoCk, we quantify a single measure of seedness of a product in a bundle to quantify its contribution. If the consistency measure used implies causality, then high centrality products cause the bundle.

[0350] In general, the seedness of a product in a bundle is defined as the contribution or density of this product in the bundle. Thus the bundleness quantification is a two step process. In the first, seedness computation stage, the seedness of each product is computed and in the second, seedness aggregation stage, the seedness of all products is aggregated to compute the overall bundleness.

[0351] Seedness Computation

[0352] The seedness of a product in a bundle is loosely defined as the contribution or density of a product to a bundle. There are two roles that a product may play in a product bundle:

• • [0353] Influencer or principal product in the bundle—The Authority products
  • [0354] Follower or peripheral product in the bundle—The Hub products

[0355] Borrowing terminology from the analysis of Web structure, we use the Klineberg's Hubs and Authority formulation in the seedness computation as follows:

• • [0356] Consider a product bundle: x={χ₁, . . . χ_n} of η products.
  • [0357] The n×n co-occurrence consistency sub-matrix for this bundle is defined by:
    Φ(x)=[φ_i,j=φ(χ_i,χ_j)].
  • [0358] Note that depending on the consistency measure, this could either be symmetric or non-symmetric. For each product in the bundle, we define two types of scores:

[0359] Authority (or Influencer) Score:

a, h = GenerateSeedness(x, Φ, εmin)
Initialize ⁢ : ⁢   ⁢ ɛ ← Inf
	a ( 0 ) ← [ 1 , 1 ,   ⁢ .   .   . ⁢   , 1 ] ; k ← 0
	h ( 0 ) ← [ 1 , 1 ,   ⁢ .   .   . ⁢   , 1 ] ; l ← 0
While (ε ≧ εmin)
	Normalize Hubness and Update Authority Measure
	h ^ ( l ) ← [ h ^ 1 ( l ) , .   .   . ⁢   , h ^ n ( l ) ] ⁢   ⁢ where ⁢   ⁢ h ^ i ( l ) ← h i ( l )  h ( l )  2
	a ( k + 1 ) ← [ a 1 ( k + 1 ) , .   .   . ⁢   , a n ( k + 1 ) ] ⁢   ⁢ where ⁢   ⁢ a i ( k + 1 ) ← ∑ j = 1 n ⁢ ϕ ⁡ ( x i | x j ) ⁢   ⁢ h ^ j ( l )
	k ← k + 1
	Normalize Authority and Update Hubness Measure
	a ^ ( k ) ← [ a ^ 1 ( k ) , .   .   . ⁢   , a ^ n ( k ) ] ⁢   ⁢ where ⁢   ⁢ a ^ i ( k ) ← a i ( k )  a ( k )  2
	h ( l + 1 ) ← [ h 1 ( l + 1 ) , .   .   . ⁢   , h n ( l + 1 ) ] ⁢   ⁢ where ⁢   ⁢ h i ( l + 1 ) ← ∑ j = 1 n ⁢ ϕ ⁡ ( x j | x i ) ⁢   ⁢ a ^ j ( k )
	l ← l + 1
	If (k ≧ 2) and (l ≧ 2)
	ɛ ← 1 - min ⁢   ⁢ { a ^ ( k ) T ⁢ a ^ ( k ) , h ^ ( l ) T ⁢ h ^ ( l ) }

[0360] The hub and authority measure converge to the first Eigen Vectors of following matrices:
a≡a^(∞)←eig₁[Φ(x)Φ(x)^T]
h≡h^(∞)←eig₁[Φ(x)^T Φ(x)]
Where
Φ(x)[φ_i,j=φ(χ_i|χ_j)]

[0361] If the consistency matrices are symmetric, the hubs and authority scores are the same. If they are non-symmetric, the hubs and authority measures are different. We only consider symmetric consistency measures and hence would only consider authority measures to quantify bundleness of a product bundle.

[0362] Seedness Aggregation

[0363] There are several ways of aggregating the seedness values of all the products in the product bundle. PeaCoCk uses a Gibbs aggregation for this purpose: $\pi \left(x\text{❘}\lambda ,\Phi \right)=\frac{\sum _{i=1}^{n}a\left(x_i\text{❘}x,\Phi \right)\times \exp \left[\lambda \times a\left(x_i\text{❘}x,\Phi \right)\right]}{\sum _{i=1}^n\exp \left[\lambda \times a\left(x_i\text{❘}x,\Phi \right)\right]}\text{:}\lambda \in \left[-\infty ,+\infty \right]$

[0364] Different settings of the temperature parameter A yield different aggregation functions: $\begin{array}{c}\pi \left(x\text{❘}\lambda =-\infty ,\Phi \right)=\underset{i=1\dots n}{\min }\left\{a\left(x_i\text{❘}x,\Phi \right)\right\}\\ \pi \left(x\text{❘}\lambda =0,\Phi \right)=\underset{i=1\dots n}{\mathrm{avg}}\left\{a\left(x_i\text{❘}x,\Phi \right)\right\}=\frac{1}{n}\sum _{i=1}^{n}a\left(x_i\text{❘}x,\Phi \right)\\ \pi \left(x\text{❘}\lambda =\infty ,\Phi \right)=\underset{i=1\dots n}{\max }\left\{a\left(x_i\text{❘}x,\Phi \right)\right\}\end{array}$

[0365] Although this defines a wide range of bundleness functions, by the definition of cohesiveness, i.e. every product should be highly connected to every other product in the product bundle, the most appropriate definition of bundleness would be based on the minimum temperature: $\mathrm{Bundleness}\text{:}\pi \left(x\text{❘}\Phi \right)=\pi \left(x\text{❘}\lambda =-\infty ,\Phi \right)=\underset{i=1\dots n}{\min }\left\{a\left(x_i\text{❘}x,\Phi \right)\right\}$

[0366] Algorithms for finding Cohesive Product Bundles

[0367] Similar to the automated item-set mining, the PeaCoCk affinity analysis engine provides for automatically finding high consistency cohesive product bundles given the above definition of cohesiveness and a market basket coo-occurrence consistency measure. Essentially the goal is to find these optimal soft-cliques in the PeaCoCk graphs. We first define the meaning of optimal in the context of a product bundle and note that this is an NP hard problem. Following this, we describe two broad classes of greedy algorithms: depth first and breadth first methods.

[0368] Problem Formulation

[0369] The overall problem of finding all cohesive product bundles in a product space may be formulated in terms of the following simple problem: Given

• • [0370] A PeaCoCk graph represented by an n×n consistency matrix Φ over product universe U
  • [0371] A set of candidate products that may be in the product bundles: CU
  • [0372] Where, any product outside this candidate set cannot be part of the product bundle
  • [0373] A set of foundation products that must be in the product bundles: FCU
  • [0374] Boundary conditions: F=Ø,C=UAll bundles at the product level of the universe F=COne bundle: F

[0375] The problem is to find a set of all locally optimal product bundles x={χ₁, . . . χ_n} of size two or more such that:

• • [0376] FxC
  • [0377] π(x|Φ)≧π(x′|Φ):∀x′∈BNeb(x|F,C)
    Where:
  • [0378] BNeb (x|F, C)=Bundle Neighborliood of bundle x

[0379] The bundle-neighborhood of a bundle is the set of all feasible bundles that may be obtained by either removing a non-foundation product from it or by adding a single candidate product to it.
BNeb (x|F, C)=BNebGrow (x|F, C)∪BNebShrink(x|F, C)
BNebGrow(x|F, C)={x═=x⊕χ: ∀χ∈C−x}
BNebShrink(x|F, C)={x′=x\χL∀χ∈x−F}

[0380] In other words, a bundle x is local optima for a given candidate set C if: $\pi \left(x\text{❘}\Phi \right)\ge \underset{xeC-x}{\max }\pi \left(x\oplus x\text{❘}\Phi \right)$ $\pi \left(x\text{❘}\Phi \right)\ge \underset{xex-F}{\max }\pi \left(x\backslash x\text{❘}\Phi \right)$

[0381] The definition of a bundle as a subset of products bounded by a the foundation set F (as a subset of every product bundle) and a candidate set C (as a superset of every product bundle) together with the definition of the neighborhood function defined above results in an abstraction called the Bundle Lattice-Space (BLS). FIG. 13 shows an example of a bundle lattice space bounded by a foundation set and a candidate set. Each point in this space is a feasible product bundle. A measure of bundleness is associated with each bundle. It also shows examples of the BShrink and BGrow neighbors of a product bundle. If the product bundle is locally optimal then all its neighbors should have a smaller bundleness than it has.

[0382] The BGrow and BShrink sets may be further partitioned into two subsets each depending on whether the neighboring bundle has a higher or lower bundleness as factored by a slack-parameter o: $\begin{array}{c}\mathrm{BGrow}\left(x|C\right)={\mathrm{BGrow}}_{+}\left(x|C,{\pi }_{\lambda },\theta \right)\bigcup {\mathrm{BGrow}}_{-}\left(x|C,{\pi }_{\lambda },\theta \right)\\ {\mathrm{Grow}}_{+}\left(x|C,{\pi }_{\lambda },\theta \right)=\left\{x^{\prime }\in \mathrm{BGrow}\left(x|C\right)|{\pi }_{\lambda }\left(x^{\prime }\right)\ge \theta \times {\pi }_{\lambda }\left(x\right)\right\}\\ {\mathrm{BGrow}}_{-}\left(x|C,{\pi }_{\lambda },\theta \right)=\left\{x^{\prime }\in \mathrm{BGrow}\left(x|C\right)|{\pi }_{\lambda }\left(x^{\prime }\right)<\theta \times {\pi }_{\lambda }\left(x\right)\right\}\end{array}$ $\begin{array}{c}\mathrm{BShrink}\left(x|F\right)={\mathrm{BShrink}}_{+}\left(x|F,{\pi }_{\lambda },\theta \right)\bigcup {\mathrm{BShrink}}_{-}\left(x|F,{\pi }_{\lambda },\theta \right)\\ {\mathrm{BShrink}}_{+}\left(x|F,{\pi }_{\lambda },\theta \right)=\left\{x^{\prime }\in \mathrm{BShrink}\left(x|F\right)|{\pi }_{\lambda }\left(x^{\prime }\right)\ge \theta \times {\pi }_{\lambda }\left(x\right)\right\}\\ {\mathrm{BShrink}}_{-}\left(x|F,{\pi }_{\lambda },\theta \right)=\left\{x^{\prime }\in \mathrm{BShrink}\left(x|F\right)|{\pi }_{\lambda }\left(x^{\prime }\right)<\theta \times {\pi }_{\lambda }\left(x\right)\right\}\end{array}$

[0383] The condition for optimality may be stated in a number of ways: $\begin{array}{c}\mathrm{Bundle}x\mathrm{is}\mathrm{Locally}\mathrm{Optimal}\mathrm{for}a\mathrm{given}\text{:}\Phi ,C,F,{\pi }_{\lambda }\mathrm{if}\text{:}\\ \mathrm{IsOptimal}\left(x\text{❘}\Phi ,C,F,{\pi }_{\lambda }\right)\\ \begin{array}{c}={\pi }_{\lambda }\left(x\text{❘}\Phi \right)\ge \max \left\{\underset{x\in C-x}{\max }{\pi }_{\lambda }\left(x\oplus x\text{❘}\Phi \right),\underset{x\in x-F}{\max }{\pi }_{\lambda }\left(x\backslash x\text{❘}\Phi \right)\right\}\\ =\left({\mathrm{BGrow}}_{+}\left(x\text{❘}C,{\pi }_{\lambda },1\right)=Ø\right)\mathrm{and}\left({\mathrm{BShrink}}_{+}\left(x\text{❘}C,{\pi }_{\lambda },1\right)=Ø\right)\end{array}\end{array}$

[0384] For a given candidate set C and foundation set F, there are O(2^|C|−|F|) possible bundles to evaluate in an exhaustive approach. Finding a locally optimal bundle is NP Complete because it reduces to the Clique problem in the simple case that the Authority measure (used to calculate your bundle-ness metric) is “1” or “0”, depending on whether a node is fully connected to other nodes in the bundle. The Clique problem (determining if a graph has a clique of a certain size K) is NP Complete

[0385] Depth First Greedy Algorithms

[0386] Depth first class of algorithms start with a single bundle and apply a sequence of grow and shrink operations to find as many locally optimal bundles as possible. In addition to the consistency matrix, 4D, the candidate set, C, and the foundation set, F, a depth first bundle search algorithm also requires: (1) Root Set, Rcontaining root-bundles to start each the depth search, (2) Explored Set, Z containing the set of product bundles that have already been explored. A typical depth first algorithm starts off by first creating a Root-Set. From this root-set, it picks one root at a time and performs a depth first search on it by adding/deleting an product from it until local optima is reached. In the process, it may create additional roots-bundles and add to the root set. The process finishes when all the roots have been exhausted. Algorithm 4 below describes how PeaCoCk uses Depth first search to create locally optimal product bundles.

	B = DepthFirstBundle(F, C, Φ, πλ, θ)
	Initialize
	Root: R = {r1 = F}
	Set of optimal bundles: B = ø
	Set of explored bundles: Z = ø
	While (R ≠ ø)
	x ← arg ⁢   ⁢   ⁢ max r ∈ R ⁢   ⁢ π λ ⁡ ( r | Φ )
	R ← R ∖ x ; Z ← Z ⋃ x
	If ⁢   ⁢ ( IsOptimal ⁡ ( x | Φ , C , F , π λ ) ) ⇒ B ← B ⋃ x
	Z ← Z ⋃ BGrow - ⁡ ( x | C , π λ , 1 ) ⋃ BShrink - ⁡ ( x | F , π λ , 1 )
	R ← R ⋃ BGrow + ⁡ ( x | C , π λ , θ ) ⋃ BShrink + ⁡ ( x | F , π λ , θ )
	R ← R ∖ Z
	Return B

[0387] A key observation that makes this algorithm efficient is that for each bundle x, any of its neighbors in the lattice space with bundleness less than the bundleness of x cannot be local optima. This is used to prune out a number of bundles quickly to make the search faster. Efficient implementation for maintaining the explored set Z for quick look-up and the root set R for quick way of finding the maximum makes this very efficient. The parameter θ controls the stringency of the greediness. It is typically in the range of 0 to infinity with 1 being the typical value to use.

[0388] Breadth First Greedy Algorithms

[0389] An-other class of greedy algorithms for finding locally optimal bundles is the Breadth First approach. Here, the search for optimal bundles of size k+1 happens only after all the bundles of size k have been explored. The algorithm presented below is similar to the algorithm used in standard market basket analysis. There are two main differences in the PeaCoCk approach and that used for standard market basket analysis:

• • [0390] (1) Quality: the standard market basket analysis algorithm seeks actual high support item-sets while PeaCoCk seeks logical high consistency bundles. This is a very big qualitative difference in the nature, interpretation and usability of the resulting bundles from the two methods. This distinction is already discussed above.
  • [0391] (2) Efficiency: the standard market basket analysis algorithm requires a pass through the data after each iteration to compute the support of each item-set, while PeaCoCk uses the co-occurrence matrix to compute the bundleness without making a pass through the data. This makes PeaCoCk extremely efficient compared to the standard market basket analysis algorithm algorithm.

[0392] PeaCoCk's breadth-first class of algorithms for finding locally optimal product bundles start from the foundation set and in each iteration maintains and grows a list of potentially optimal bundles to the next size of product bundles. The standard market basket analysis algorithm monotonic property also applies to a class of bundleness functions where the parameter λ is low for example: π_−∞(x|Φ). In other words, for bundieness measures, a bundle may have high bundleness only if all of its subsets of one size less have high bundleness. This property is used in a way similar to the standard market basket analysis algorithm to find locally optimal bundles in the Algorithm 5 described below. In addition to the consistency matrix, Φ, the candidate set, C, and the foundation set, F, a breadth first bundle search algorithm also requires a Potentials Set, PS of bundles of size s that have a potential to grow into an optimal bundle.

B = BreadthFirstBundle(F, C, Φ, πλ, θ, smax)
Initialize
	Size ⁢   ⁢ s ← 1 ;   ⁢ P s ← C
	Set ⁢   ⁢ of ⁢   ⁢ optimal ⁢   ⁢ bundles ⁢ : ⁢   ⁢ B ← ∅
While (s ≦ min {smax, |C|})
	Q s + 1 ← ⋃ x ∈ P s ⁢   ⁢ BGrow + ⁡ ( x | C , π λ , θ )
	P s + 1 ← { x ∈ Q s + 1 | BShrink ( x | F ) ⊆ P s } // All ⁢   ⁢ subsets ⁢   ⁢ of ⁢   ⁢ x ⁢   ⁢ are ⁢   ⁢ in ⁢   ⁢ P s
	s ← s + 1
	∀ x ∈ P s : If ⁢   ⁢ ( IsOptimal ⁡ ( x | Φ , C , F , π λ ) ) ⇒ B ← B ⋃ x
Return B

[0393] The Breadth vs. Depth first search methods both have their trade-offs in terms of completeness vs. time/space complexity. While the depth first algorithms are fast, the breadth first algorithms may result in more coverage i.e. find majority of locally optimal bundles.

[0394] Business Decisions based on Product Bundles

[0395] Product bundles may be used in several retail business decisions as well as in advanced analysis of retail data. Examples of some are given below:

• • [0396] Assortment Promotions—Often retailers create promotions that involve multiple products. For example, “buy product A and get product B half off” or “buy the entire bundle for 5% less.” Historically, retailers have used their domain knowledge or market surveys to create these product assortments. Recently, with the advent of market basket analysis, some retailers have started using transaction data to find product bundles that make sense to customers. However, there has not been much success with traditional techniques because they could not find logical or natural product assortments for the reasons described earlier. The product bundles created by PeaCoCk using the techniques described above may be used very effectively in creating product assortment promotions because they capture the latent intentions of customers in a way that was not possible before.
  • [0397] Cross-sell Campaigns—One of the key customer-centric decisions that a retailer is faced with is how to promote the right product to the right customer based on his transaction history. There are a number of ways of approaching this problem: Customer segmentation, transaction history based recommendation engine, and product bundle based product promotions. As described earlier, a customer typically purchases a projection of an intention at a store during a single visit. If a customer's current or recent purchases partially overlap with one or more bundles, decisions about the right products to promote to the customer may be derived from the products in those product bundles that they did not buy. This can be accomplished via a customer score and query templates associated product bundles as discussed later.
  • [0398] Latent Intentions Analysis—Traditionally, retail data mining is done at products level, there is a higher conceptual level in the retail domain—intentions. PeaCoCk product bundles (and later product phrases) are the higher order structures that may be thought of as proxy for the latent-logical intentions. In a later discussion we describe how a customer's transaction data may be scored against different product bundles. These scores may be used to characterize whether or not the associated intentions are reflected in the customer's transaction data. This opens up a number of possibilities on how to use these intentions. For example, intentions based customer segmentation, intentions based product recommendation, intention prediction based on past intentions, life style/stage modeling for customers, etc.

[0399] Business Projection Scores

[0400] Product bundles generated in PeaCoCk represent logical product associations that may or may not exist completely in the transaction data i.e. a single customer may have not bought all the products in a bundle as part of a single market basket. These product bundles may be analyzed by projecting them along the transaction data and creating bundle projection-scores, defined by the a bundle set, a market basket, and a projection scoring function:

• • [0401] Bundle-Set denoted by B={b_k}_k=1^K is the set of K product bundles against which bundle projection scores are computed. One can think of these as parameters for feature extractors.
  • [0402] Market Basket denoted by xU is a market basket obtained from the transaction data. In general, depending on the application, it could be either a single transaction basket or a union of recent customer transactions or all of customer transactions so far. One can think of these as the raw input data for which features are to be created.
  • [0403] Projection-Scoring Function denoted by f(x|b_k, Φ, λ) is a scoring function that may use the co-occurrence consistency matrix Φ and a set of parameters λ and creates a numeric score. One can think of these as feature extractors.

[0404] PeaCoCk supports a large class of projection-scoring functions, for example:

• • [0405] Overlap Score that quantifies the relative overlap between a market basket and a product bundle $\begin{array}{cc}{f}_{\mathrm{overlap}\text{-}A}\left(x|b_k\right)=\frac{x\bigcap b_k}{x\bigcup b_k};& f_{\mathrm{overlap}\text{-}B}\left(x|b_k\right)=\frac{x\bigcap b_k}{\min \left\{x,b_k\right\}}\end{array}$
  • [0406] Coverage Score: that quantifies the fraction of product bundle purchased in the market basket. $\begin{array}{cc}{f}_{\mathrm{coverage}}\left(x|b_k\right)=\frac{x\bigcap b_k}{b_k};& f_{\mathrm{wtd}\text{-}\mathrm{coverage}}\left(x|b_k,\Phi ,\lambda \right)=\frac{{\pi }_{\lambda }\left(x\bigcap b_k❘\Phi \right)}{{\pi }_{\lambda }\left(b_k❘\Phi \right)}\end{array}$

[0407] A market basket can now be represented by a set of K bundle-features: $f\left(x|B\right)=\left(f\left(x|b_1\right),f\left(x|b_1\right),\dots ,f\left(x|b_k\right)\right)$

[0408] Such a fixed length, intention level feature representation of a market basket, e.g. single visit, recent visits, entire customer, may be used in a number of applications such as intention-based clustering, intention based product recommendations, customer migration through intention-space, intention-based forecasting, etc.

[0409] Bundle based Product Recommendations

[0410] There are two ways of making decisions about which products should be promoted to which customer: (1) product-centric customer decisions about top customers for a given product and (2) customer-centric product decisions about top products for a given customer. Product bundles, in conjunction with customer transaction data and projection scores may be used to make both types of decisions. Consider, for example the coverage projection score. If we assume that (1) a product bundle represents a complete intention and (2) that a customer eventually buys either all the products associated with an intention or none of the products, then if a customer has a partial coverage for a bundle, the rest of the products in the bundle may be promoted to the customer. This can be done by first computing a bundle based propensity score for each customer n, product γ combination and is defined as a weighted combination of coverage scores across all available bundles: $\begin{array}{c}\begin{array}{c}\\ \begin{array}{c}s\left(\gamma ,n|B\right)=\\ \delta \left(\gamma \notin x^{\left(n\right)}\right)\times \end{array}\left[\frac{\begin{array}{c}\sum _{b\in B}^{}\delta \left(\gamma \in b\right)\times w\left(f_{\mathrm{overlap}}*x|b\right))\times \\ f_{\mathrm{coverage}}\left(x|b\right)\end{array}}{\sum _{b\in B}^{}\delta \left(\gamma \in b\right)\times w\left(f_{\mathrm{overlap}}\left(x|b\right)\right)}\right]\end{array}\\ \end{array}$
Where:

• • [0411] w(f_overlap(x|b))=Monotonically increasing weight function of overlap
  • [0412] δ(boolean)=1 if boolean argument is true and 0 otherwise

[0413] To make product centric customer decisions, we sort the scores across all customers for a particular product in a descending order and pick the top customers. To make customer centric product decisions, all products are sorted for each customer in descending order and top products are picked.

[0414] Bridge Structures in PeaCoCk Graphs

[0415] There are two extensions of the product bundle structures:(1) Bridge structures that essentially contain more than one product bundles that share very small number of products, and(2) Product phases that are essentially bundles extended along time. The following discussion focuses on characterizing, discovering, analyzing, and using bridge structures.

[0416] Definition of a Logical Bridge Structure

[0417] In PeaCoCk a bridge structure is defined as a collection of two or more, otherwise disconnected or sparsely connected product groups, i.e. a product bundle or an individual product, that are connected by a single or small number of bridge product(s). Such structures may be very useful in increasing cross department traffic and strategic product promotions for increased lifetime value of a customer. FIG. 5 shows examples of two bridge structures. A logical bridge structure G={g₀,g} is formally defined by:

• • [0418] Bridge Product(s), g₀=the product(s) that bridge various groups in the bridge structure and
  • [0419] Bridge Groups: g={g₁, g₂, . . . }=the ORDERED set of groups bridged by the structure.
  • [0420] Groups are ordered by the way they relate to the bridge product (more later)
  • [0421] Each group could be either a single product or a product bundle.

[0422] Motivation from Polyseme

[0423] The key motivation for bridge structures in PeaCoCk product graphs comes from polyseme in language: A word may have more than one meaning. The right meaning is deduced from the context in which the word is used. FIG. 14 shows an example of two polysemous words: ‘can’ and ‘may.’ The word families shown herein are akin to the product bundles and a single word connecting the two word families is akin to a bridge structure. The only difference is that in FIG. 14 similarity between the meanings of the words is used while in PeaCoCk, consistency between products is used to find similar structures.

[0424] Bridgeness of a Bridge Structure

[0425] Earlier we defined a measure of cohesiveness for a bundle i.e. the “bundleness” measure. Similarly, for each bridge structure we define a measure called bridgeness that depends on two types of cohesiveness measures:

• • [0426] Intra-Group Cohesiveness is the aggregate of cohesiveness of each group. If the group has only one product, its cohesiveness is zero. But if the group has two or more products (as in a product bundle) then its cohesiveness can be measured in several ways. One way would be to use bundleness of the group as its cohesiveness. But in this definition, we do not use the bundleness measure because the same cannot be done for the other component of the bridgeness measure. Hence, we use a simple measure of intra-group cohesiveness based on the average of the consistency strength of all edges in the group. Formally, for a given bridge structure: G={g.g}, and co-occurrence consistency matrix(D, the intra-group cohesiveness for each group is given by: $\mathrm{intra}\left(g_k|\Phi \right)=\{\begin{array}{cc}0& \mathrm{if}g_k=1\\ \frac{1}{g_k\left(g_k-1\right)}\sum _{x\in g_k}\sum _{x^{\prime }\in g_k\backslash x}\varphi \left(x,x^{\prime }\right)& \mathrm{otherwise}\end{array}$

[0427] The overall intra-group cohesiveness may be defined as weighted combination with weight w(g_k) for group k of the individual intra-group consistencies: $\begin{array}{c}\mathrm{intra}\left(g|\Phi ,k_{\max }\right)=\frac{\sum _{k=1}^{k_{\max }}w\left(g_k\right)\mathrm{intra}\left(g_k|\Phi \right)}{\sum _{k=1}^{k_{\max }}w\left(g_k\right)};\\ w\left(g_k\right)=\{\begin{array}{c}\delta \left(g_k>1\right)\\ g_k\\ g_k\left(g_k-1\right)\end{array}\end{array}$

• • [0428] Inter-Group Cohesiveness is the aggregate of the consistency connections going across the groups. Again, there are several ways of quantifying this but the definition used here is based on aggregating the inter-group cohesiveness between all pairs of groups and then taking a weighted average of all those. More formally, for every pair of groups: g_i and g_j, the inter-group cohesiveness is defined as: $\begin{array}{c}\mathrm{inter}\left(g_i,g_j❘\Phi \right)=\mathrm{inter}\left(g_j,g_i|\Phi \right)\\ =\frac{1}{g_i\times g_i}\sum _{x\in g_i}\sum _{x^{\prime }\in g_j}\varphi \left(x,x^{\prime }\right)\end{array}$