smile.association

Class FPGrowth

java.lang.Object

smile.association.FPGrowth

public class FPGrowth
extends Object

Frequent item set mining based on the FP-growth (frequent pattern growth) algorithm, which employs an extended prefix-tree (FP-tree) structure to store the database in a compressed form. The FP-growth algorithm is currently one of the fastest approaches to discover frequent item sets. FP-growth adopts a divide-and-conquer approach to decompose both the mining tasks and the databases. It uses a pattern fragment growth method to avoid the costly process of candidate generation and testing used by Apriori.

The basic idea of the FP-growth algorithm can be described as a recursive elimination scheme: in a preprocessing step delete all items from the transactions that are not frequent individually, i.e., do not appear in a user-specified minimum number of transactions. Then select all transactions that contain the least frequent item (least frequent among those that are frequent) and delete this item from them. Recurse to process the obtained reduced (also known as projected) database, remembering that the item sets found in the recursion share the deleted item as a prefix. On return, remove the processed item from the database of all transactions and start over, i.e., process the second frequent item etc. In these processing steps the prefix tree, which is enhanced by links between the branches, is exploited to quickly find the transactions containing a given item and also to remove this item from the transactions after it has been processed.

References

1. Jiawei Han, Jian Pei, Yiwen Yin, and Runying Mao. Mining frequent patterns without candidate generation. Data Mining and Knowledge Discovery 8:53-87, 2004.
2. Gosta Grahne and Jianfei Zhu. Fast algorithms for frequent itemset mining using FP-trees. IEEE TRANS. ON KNOWLEDGE AND DATA ENGINEERING 17(10):1347-1362, 2005.
3. Christian Borgelt. An Implementation of the FP-growth Algorithm. OSDM, 1-5, 2005.

Author:

Haifeng Li

Constructor Summary

Constructors

Constructor and Description
FPGrowth(int[][] itemsets, double minSupport) Constructor.
FPGrowth(int[][] itemsets, int minSupport) Constructor.
FPGrowth(int[] frequency, int minSupport) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
void	add(int[] itemset) Add an item set into the object.
List<ItemSet>	learn() Mines the frequent item sets.
long	learn(PrintStream out) Mines the frequent item sets.
int	size() Returns the number transactions in the database.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

FPGrowth

public FPGrowth(int[] frequency,
        int minSupport)

Constructor. This is for mining frequent item sets by scanning database twice. The user first scans the database to obtains the frequency of single items and calls this constructor. Then the user add item sets to the object by add(int[]) during the second scan of the database. In this way, we don't need load the whole database into the main memory. In the database, the item identifiers have to be in [0, n), where n is the number of items.

Parameters:

frequency - the frequency of single items.

minSupport - the required minimum support of item sets in terms of frequency.

FPGrowth

public FPGrowth(int[][] itemsets,
        double minSupport)

Constructor. This is a one-step construction of FP-tree if the database is available in main memory.

Parameters:

itemsets - the item set dataset. Each row is a item set, which may have different length. The item identifiers have to be in [0, n), where n is the number of items.

minSupport - the required minimum support of item sets in terms of percentage.

FPGrowth

public FPGrowth(int[][] itemsets,
        int minSupport)

Constructor. This is a one-step construction of FP-tree if the database is available in main memory.

Parameters:

itemsets - the item set database. Each row is a item set, which may have different length. The item identifiers have to be in [0, n), where n is the number of items. Item set should NOT contain duplicated items. Note that it is reordered after the call.

minSupport - the required minimum support of item sets in terms of frequency.

Method Detail

add

public void add(int[] itemset)

Add an item set into the object.

Parameters:

itemset - an item set, which should NOT contain duplicated items. Note that it is reordered after the call.

size

public int size()

Returns the number transactions in the database.

Returns:

the number transactions in the database

learn

public List<ItemSet> learn()

Mines the frequent item sets. The discovered frequent item sets will be returned in a list.

Returns:

the list of frequent item sets

learn

public long learn(PrintStream out)

Mines the frequent item sets. The discovered frequent item sets will be printed out to the provided stream.

Parameters:

out - a print stream for output of frequent item sets.

Returns:

the number of discovered frequent item sets.