Prove Equation 6.3. (Hint: First, count the number of ways to create an itemset that forms the left hand side of the rule. Next, for each size k itemset selected for the left-hand side, count the number of ways to choose the remaining d ? k items to form the right-hand side of the rule.)

What will be an ideal response?

Answer:





Suppose there are d items. We first choose k of the items to form the left-


hand side of the rule. There are





d


k


ways for doing this. After selecting the





items for the left-hand side, there are


d?k


i


ways to choose the remaining


items to form the right hand side of the rule, where 1 ? i ? d ? k. Therefore


the total number of rules (R) is: