The original association rule mining framework considers only presence of items together in the same transaction. There are situations in which itemsets that are infrequent may also be informative. For instance, the itemset TV, DVD, ¬ VCR suggests that many customers who buy TVs and DVDs do not buy VCRs.
In this problem, you are asked to extend the association rule framework to negative itemsets (i.e., itemsets that contain both presence and absence of items). We will use the negation symbol (¬) to refer to absence of items.
(a) A naive way for deriving negative itemsets is to extend each transaction to include absence of items as shown in Table 7.17.
i. Suppose the transaction database contains 1000 distinct items.
What is the total number of positive itemsets that can be generated from these items? (Note: A positive itemset does not contain any negated items).
Table 7.17. Example of numeric data set.

ii. What is the maximum number of frequent itemsets that can be generated from these transactions? (Assume that a frequent itemset may contain positive, negative, or both types of items)
iii. Explain why such a naive method of extending each transaction with negative items is not practical for deriving negative itemsets.
(b) Consider the database shown in Table 7.14. What are the support and
confidence values for the following negative association rules involving
regular and diet soda?
i. ¬Regular ˆ’†’ Diet.
ii. Regular ˆ’†’ ¬Diet.
iii. ¬Diet ˆ’†’ Regular.
iv. Diet ˆ’†’ ¬Regular.

Transcribed Image Text:

TID TTV -TV DVDDVD VCRVCR 0