FP-Growth (Concurrency)

Description

When online shopping, you will sometimes get a suggestion of the following form: "Customers who bought item X also bought item Y." This suggestion is an example of an association rule. To derive it, you first have to know which items on the market most frequently co-occur in customers' shopping baskets, and here the FP-Growth algorithm has a role to play.

The FP-Growth algorithm is an efficient algorithm for calculating frequently co-occurring items in a transaction database. To understand how it works, let's start with some terminology, using a customer transaction as an example:

• item - any object that is sold on the market
• basket - a container for one or more items selected by the customer
• itemset - any subset of items that are sold together, in the same shopping basket
• transaction - the complete set of items in an individual shopping basket, at the moment of purchase
• transaction database - the complete set of shopping baskets / transactions recorded by the merchant

Here, the words "basket" and "transaction" are used interchangably, because we identify the customer's shopping basket with the items that were purchased. To make these definitions concrete, consider the following transaction database:

• transaction1 = (product1, product2, product7)
• transaction2 = (product2, product5, product7)
• transaction3 = (product6, product7, product8, product9)
• transaction4 = (product1, product3, product4, product6, product7)

Nine distinct items are for sale, and there are four baskets / transactions, with a varying number of items. The item appearing most frequently, product7, appears four times in the transactions database. Each of the following itemsets occurs twice: (product1, product7), (product2, product7), (product6, product7).

An FP-tree data structure can be efficiently created, compressing the data so much that, in many cases, even large databases will fit into main memory. In the example above, the FP-tree would have product7, the most frequently occurring product, next to the root, with branches from product7 to product1, product2, and product6. If we insist that a product must appear more than once in the transaction database, then the remaining products are excluded from the FP-tree. The transaction database might have started out as a 4 x 9 (transactions x products) data table, with many zero entries, but now it is reduced to a minimalistic tree that captures only the relevant frequency data.

Even with an efficient tree structure, the number of itemsets considered by the algorithm can grow very large. With the help of the parameter max number of itemsets, you can if necessary reduce runtime and memory.

Remember that online shopping is merely an example; the FP-Growth algorithm can be applied to any problem that can be formulated in terms of items, itemsets, and baskets / transactions. The typical setting for the algorithm is a large transaction database (many baskets), with only a small number of items in each basket -- small compared to the set of all items.

• support = (Number of times an item or itemset appears in the database) / (Number of baskets in the database)

In general, the concept of "minimum support" creates a cutoff, defining what is meant by frequent or not-so-frequent occurrences of an itemset. If an item or an itemset appears in only a few baskets, it is excluded, via the parameters min support or min frequency. The exclusion of infrequently-occurring items and itemsets helps to compress the data and improves the statistical significance of the results. On the other hand, if the value for min support or min frequency is set too high, the algorithm may find zero itemsets. Hence, this Operator provides two major modes, via the checkbox find min number of itemsets:

1. if unchecked, with a fixed minimum support value, and

2. if checked, with a dynamic minimum support value, to ensure that the result includes a minimum number of itemsets.

FP-Growth supports several different formats for the input data. Please note the following requirements:

• in the ExampleSet, one transaction = one row. For a discussion of the columns, see below.
• all the item values must be nominal
• a transaction ID is optional and, if present, it should have the "id" role, so that it is not identified as an item.

For the columns, the three available input formats are illustrated in the second tutorial, together with necessary pre-processing. Here's the summary:

• item list in a column: All the items belonging to a transaction appear in a single column, separated by item separators, in a CSV-like format. As with CSV files, the items can be quoted, and escape characters are available. You can trim item names.
• items in separate columns: All the items belonging to a transaction appear in separate columns. For each transaction, the first item name appears in the first column, the second item name in the second column, etc. The number of columns corresponds to the basket with the maximum number of items. Missing values indicate no item. You can trim item names.
• items in dummy coded columns: Every item in the set of all items has its own column, and the item name is the column name. For each transaction, the binominal values (true/false) indicate whether the item can be found in the basket. If your data is binominal but does not identify the values as true/false, you may have to set the positive value parameter.