Association rule mining
It is equivalent to frequent itemsets mining. It can only be solved by
generate-and-test. The Apriori property of frequent itemsets help to
reduce the total size of candidate itemsets. The basic building block of
frequent itemsets is frequent items, so length-1 itemsets are tested
first. When we have the frequent items (e.g. A,B,C,...), we want to find
length-2 itemsets. To test a length-2 itemsets (e.g. {AB}), we may count
the support of {AB} in the original DB or count the support of B in the
transactions containing A (i.e. projected DB of A). As a result, we have
Apriori-based and growth-based mining methods. Growth is better because
fewer transactions are examined when counting {AB} and we only need to
prove {A} and {AB} to be frequent before counting {ABC} (Apriori needs to
prove {A}, {B}, {C}, {AB}, {BC} and {AC}.). If we only know the support of
A and B, growth is the best way to count {AB}. Does it mean that growth
is the optimum method?