Consider the transactions shown in Table 7.14, with an item taxonomy given in Figure 7.25.

Question

(a) What are the main challenges of mining association rules with item

taxonomy?

(b) Consider the approach where each transaction t is replaced by an ex-

tended transaction t'

that contains all the items in t as well as their re-

spective ancestors. For example, the transaction t = { Chips, Cookies}

will be replaced by t'

= {Chips, Cookies, Snack Food, Food}. Use this

approach to derive all frequent itemsets (up to size 4) with support ?

70%.

(c) Consider an alternative approach where the frequent itemsets are gen-

erated one level at a time. Initially, all the frequent itemsets involving

items at the highest level of the hierarchy are generated. Next, we use

the frequent itemsets discovered at the higher level of the hierarchy to

generate candidate itemsets involving items at the lower levels of the hi-

erarchy. For example, we generate the candidate itemset {Chips, Diet

Soda} only if {Snack Food, Soda} is frequent. Use this ap

Answer 1

(a) Difficulty of deciding the right support and confidence thresholds. Items
residing at higher levels of the taxonomy have higher support than those
residing at lower levels of the taxonomy. Many of the rules may also be
redundant.
(b) There are 8 frequent 1-itemsets, 25 frequent 2-itemsets, 34 frequent
3-itemsets and 20 frequent 4-itemsets. The frequent 4-itemsets are:
{Food, Snack Food, Meat, Soda} {Food, Snack Food, Meat, Chips}
{Food, Snack Food, Meat, Pork} {Food, Snack Food, Meat, Chicken}
{Food, Snack Food, Soda, Chips} {Food, Snack Food, Chips, Pork}
{Food, Snack Food, Chips, Chicken} {Food, Meat, Soda, Chips}
{Food, Meat, Soda, Pork} {Food, Meat, Soda, Chicken}
{Food, Meat, Soda, Ham} {Food, Meat, Chips, Pork}
{Food, Meat, Chips, Chicken} {Food, Meat, Pork, Chicken}
{Food, Meat, Pork, Ham} {Food, Soda, Pork, Ham}
{Snack Food, Meat, Soda, Chips} {Snack Food, Meat, Chips, Pork}
{Snack Food, Meat, Chips, Chicken} {Meat, Soda, Pork, Ham}
(c) There are 8 frequent 1-itemsets, 6 frequent 2-itemsets, and 1 frequent
3-itemset. The frequent 2-itemsets and 3-itemsets are:
{Snack Food, Meat} {Snack Food, Soda}
{Meat, Soda} {Chips, Pork}
{Chips, Chicken} {Pork, Chicken}
{Snack Food, Meat, Soda}
(d) The method in part (b) is more complete but less efficient compared to
the method in part (c). The method in part (c) is more efficient but
may lose some frequent itemsets.