Apriori. Lets look at a concrete example, based on the AllElectronics transaction database, D, of Table 6.1. There are nine transactions in this database, that is, |D|=9. We use Figure 6.2 to illustrate the Apriori algorithm for nding frequent itemsets in D. 1. In the rst iteration of the algorithm, each item is a member of the set of candidate 1-itemsets, C1. The algorithm simply scans all of the transactions to count the number of occurrences of each item.

2. Suppose that the minimum support count required is 2, that is, min sup=2. (Here, we are referring to absolute support because we are using a support count.The corresponding relative support is 2/9=22%.)The set of frequent1-item sets,L1,can then be determined. It consists of the candidate 1-itemsets satisfying minimum support. In our example, all of the candidates in C1 satisfy minimum support.

3. To discover the set of frequent 2-itemsets, L2, the algorithm uses the join L1 1 L1 to generate a candidate set of 2-itemsets, C2.7 C2 consists of|L1| 22-itemsets. Note that no candidates are removed from C2 during the prune step because each subset of the candidates is also frequent. Table 6.1 Transactional Data for an AllElectronics Branch TID List of item IDs

T100 I1, I2, I5

T200 I2, I4

T300 I2, I3

T400 I1, I2, I4

T500 I1, I3

T600 I2, I3

T700 I1, I3

T800 I1, I2, I3, I5

T900 11, 12, 13

Data Mining Page 250