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 na ??ve 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).

ii. What is the maximum number of frequent itemsets that can be

generated from these transactions? (Assume that a frequent item-
set may contain positive, negative, or both types of itemsiii. Explain why such a na ??ve method of extending each transaction
with negative items is not practical for deriving negative itemsets.

---

(a) A na ??ve 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).

ii. What is the maximum number of frequent itemsets that can be

generated from these transactions? (Assume that a frequent item-
set may contain positive, negative, or both types of itemsiii. Explain why such a na ??ve method of extending each transaction
with negative items is not practical for deriving negative itemsets.