REORDERING AND PRUNING

REORDERING AND PRUNING

The itemset is initially reordered and pruned. It is reordered so that the most common single attributes appear first, and pruned so that the unsupported itemsets are not included. The effect of this reordering and pruning is to make the running of the code more computationally efficient.

3.2.3 FP TREE
A popular "preprocessing" tree structure is the FP-tree proposed by Han et al. The FP-tree stores a single item at each node, and includes additional links to facilitate processing. These links start from a header table and link together all nodes in the FP-tree which store the same item.
The construction process begins with an initial pass to count support for the single items. Those that fail to meet the support threshold are eliminated, and the others ordered by decreasing frequency. We then pass through the dataset a second time and produce an initial FP-tree. We commence by reading the first record in the dataset and place this in the FP-tree. We then add the second record; the first element of this is common with an existing node and so we add the new node to the FP-tree structure.