Frequent Pattern Growth & Constraint-based Mining

Principle of Frequent Pattern Growth: search for frequent pattern in the relevant part of database.
Principle of Constrained-based Mining: make use of some properties of constraint to speed up the mining of frequent pattern.

What have been done for Constraint-based Mining?
Objective: Mining Frequent Itemsets with Constraints
Input: Item, tran(tid,itemset), iteminfo(item,type,price), support threshold, constraints

• Ng98: Identify 2 common constaint properties, anti-monotone and succinct. Classify all constraints into 4 classes, namely anti-monotone & succinct, succinct but non-anti-monotone, anti-monotone but non-succinct and none. Design strategies for the 4 constraint classes so that their pruning power can be fully utilized with Apriori-based algorithm.
• Pei01: Identify 2 more constraint properties than Ng98, monotone and convertible. Prove that anti-monotone, monotone and succinct constraints are all convertible constraints. Classify all constraints into 4 classes, namely convertible anti-monotone, convertible monotone, strongly convertible and inconvertible. Design strategies for the 3 classes convertible constraints so that their pruning power can be fully utilized with Frequent Pattern Growth algorithm.

The Development Trend
The simplest method to mine frequent itemsets with constraints is to first find the frequent itemsets and then do the constraint tests on the frequent itemsets.This method is not good. If we imagine all itemsets as a lattice space, both support threshold and constraints prune the search space. It is straightforward to combine their pruning power by doing constraint testing before counting support for candidates. However, this approach does not work when the constraints are not anti-monotone. Thus, succinct constraints and their member generating functions(MGF) are found and we can use the MGFs of succinct constraints to speed up frequent itemset mining. However, there are constraints which are neither anti-monotone nor succinct constraints which we call tough constraints. One way to handle tough constraint is to transform tough constraints into anti-monotone and succinct constraints and have an additional post-processing step. On the other hand, some tough constraints are convertible constraints which can be pushed into the frequent pattern growth method only. In addition, there is another constraint property called monotone which can further improve the mining algorithm.

Comparisons of the Ng98 and Pei01

• Anti-monotone & succinct constraint: Ng98 reduces the number of candidates in counting support frequency at the beginning using member generating function(MGF) of the constraint and allows no constraint testing due to MGF. Pei01 reduces the number of transactions considered in counting support frequency by projecting the original database to smaller databases.
• Succinct Only constraint: Similar to Anti-monotone & sucinct constraint.
• Anti-monotone only: Obviously, Pei01 is better due to database projection.
• None: The performance of Ng98 depends on what properties the weak induced constraint has while that of Pei01 depends on if the constraint is inconvertible.
• In addition, Pei01 can be modified to include the techniques used in Ng98.