Frequent Itemsets via the FP-Growth Algorithm
Function implementing FP-Growth to extract frequent itemsets for association rule mining
from mlxtend.frequent_patterns import fpgrowth
FP-Growth  is an algorithm for extracting frequent itemsets with applications in association rule learning that emerged as a popular alternative to the established Apriori algorighm .
In general, the algorithm has been designed to operate on databases containing transactions, such as purchases by customers of a store. An itemset is considered as "frequent" if it meets a user-specified support threshold. For instance, if the support threshold is set to 0.5 (50%), a frequent itemset is defined as a set of items that occur together in at least 50% of all transactions in the database.
In particular, and what makes it different from the Apriori frequent pattern mining algorithm, FP-Growth is an frequent pattern mining algorithm that does not require candidate generation. Internally, it uses a so-called FP-tree (frequent pattern tree) datastrucure without generating the candidate sets explicitely, which makes is particularly attractive for large datasets.
 Han, Jiawei, Jian Pei, Yiwen Yin, and Runying Mao. "Mining frequent patterns without candidate generation. "A frequent-pattern tree approach." Data mining and knowledge discovery 8, no. 1 (2004): 53-87.
 Agrawal, Rakesh, and Ramakrishnan Srikant. "Fast algorithms for mining association rules." Proc. 20th int. conf. very large data bases, VLDB. Vol. 1215. 1994.
Example 1 -- Generating Frequent Itemsets
fpgrowth function expects data in a one-hot encoded pandas DataFrame.
Suppose we have the following transaction data:
dataset = [['Milk', 'Onion', 'Nutmeg', 'Kidney Beans', 'Eggs', 'Yogurt'], ['Dill', 'Onion', 'Nutmeg', 'Kidney Beans', 'Eggs', 'Yogurt'], ['Milk', 'Apple', 'Kidney Beans', 'Eggs'], ['Milk', 'Unicorn', 'Corn', 'Kidney Beans', 'Yogurt'], ['Corn', 'Onion', 'Onion', 'Kidney Beans', 'Ice cream', 'Eggs']]
We can transform it into the right format via the
TransactionEncoder as follows:
import pandas as pd from mlxtend.preprocessing import TransactionEncoder te = TransactionEncoder() te_ary = te.fit(dataset).transform(dataset) df = pd.DataFrame(te_ary, columns=te.columns_) df
|Apple||Corn||Dill||Eggs||Ice cream||Kidney Beans||Milk||Nutmeg||Onion||Unicorn||Yogurt|
Now, let us return the items and itemsets with at least 60% support:
from mlxtend.frequent_patterns import fpgrowth fpgrowth(df, min_support=0.6)
|9||0.6||(8, 3, 5)|
fpgrowth returns the column indices of the items, which may be useful in downstream operations such as association rule mining. For better readability, we can set
use_colnames=True to convert these integer values into the respective item names:
fpgrowth(df, min_support=0.6, use_colnames=True)
|5||0.8||(Eggs, Kidney Beans)|
|6||0.6||(Yogurt, Kidney Beans)|
|8||0.6||(Kidney Beans, Onion)|
|9||0.6||(Eggs, Kidney Beans, Onion)|
|10||0.6||(Kidney Beans, Milk)|
Example 2 -- Apriori versus FPGrowth
Since FP-Growth doesn't require creating candidate sets explicitly, it can be magnitudes faster than the alternative Apriori algorithm. For instance, the following cells compare the performance of the Apriori algorithm to the performance of FP-Growth -- even in this very simple toy dataset scenario, FP-Growth is about 5 times faster.
import pandas as pd from mlxtend.preprocessing import TransactionEncoder te = TransactionEncoder() te_ary = te.fit(dataset).transform(dataset) df = pd.DataFrame(te_ary, columns=te.columns_)
from mlxtend.frequent_patterns import apriori %timeit -n 100 -r 10 apriori(df, min_support=0.6)
2.52 ms ± 362 µs per loop (mean ± std. dev. of 10 runs, 100 loops each)
%timeit -n 100 -r 10 apriori(df, min_support=0.6, low_memory=True)
2.44 ms ± 119 µs per loop (mean ± std. dev. of 10 runs, 100 loops each)
from mlxtend.frequent_patterns import fpgrowth %timeit -n 100 -r 10 fpgrowth(df, min_support=0.6)
549 µs ± 17.7 µs per loop (mean ± std. dev. of 10 runs, 100 loops each)
Please note that since the
fpgrowth function is a drop-in replacement for
apriori, it comes with the same set of function arguments and return arguments. Thus, for more examples, please see the
fpgrowth(df, min_support=0.5, use_colnames=False, max_len=None, verbose=0)
Get frequent itemsets from a one-hot DataFrame
df: pandas DataFrame or pandas SparseDataFrame
pandas DataFrame the encoded format. The allowed values are either 0/1 or True/False. For example,
Apple Bananas Beer Chicken Milk Rice 0 1 0 1 1 0 1 1 1 0 1 0 0 1 2 1 0 1 0 0 0 3 1 1 0 0 0 0 4 0 0 1 1 1 1 5 0 0 1 0 1 1 6 0 0 1 0 1 0 7 1 1 0 0 0 0
min_support: float (default: 0.5)
A float between 0 and 1 for minimum support of the itemsets returned. The support is computed as the fraction transactions_where_item(s)_occur / total_transactions.
use_colnames: bool (default: False)
If true, uses the DataFrames' column names in the returned DataFrame instead of column indices.
max_len: int (default: None)
Maximum length of the itemsets generated. If
None(default) all possible itemsets lengths are evaluated.
verbose: int (default: 0)
Shows the stages of conditional tree generation.
pandas DataFrame with columns ['support', 'itemsets'] of all itemsets
that are >=
min_support and < than
max_len is not None).
Each itemset in the 'itemsets' column is of type
which is a Python built-in type that behaves similarly to
sets except that it is immutable
(For more info, see