《海量数据挖掘-王永利》ch06-assocrules.pptVIP

* J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, * J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, * Phase 1: Find candidate itemsets Map? Reduce? Phase 2: Find true frequent itemsets Map? Reduce? J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, * * If confidence is high then interest cannot be negative * Why hash table takes full space? We want to make it as large as possible. Why hash table bigger than bitmap? Hash table contains counts * Why? While we were able to use the triangular-matrix method on the second pass of A-Priori if we wished, because the frequent items could be renumbered from 1 to some m, we cannot do so for PCY. The reason is that the pairs of frequent items that PCY lets us avoid counting are placed randomly within the triangular matrix; they are the pairs that happen to hash to an infrequent bucket on the ?rst pass. There is no known way of compacting the matrix to avoid leaving space for the uncounted pairs. * Na?ve approach to finding frequent pairs Read file once, counting in main memory the occurrences of each pair: From each basket of n items, generate its n(n-1)/2 pairs by two nested loops Fails if (#items)2 exceeds main memory Remember: #items can be 100K (Wal-Mart) or 10B (Web pages) Suppose 105 items, counts are 4-byte integers Number of pairs of items: 105(105-1)/2 = 5*109 Therefore, 2*1010 (20 gigabytes) of memory needed J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, * Two approaches: Approach 1: Count all pairs using a matrix Approach 2: Keep a table of triples [i, j, c] = “the count of the pair of items {i, j} is c.” If integers and item ids are 4 bytes, we need approximately 12 bytes for pairs with count 0 Plus some additional overhead for the hashtable Note: Approach 1 only requires 4 bytes per pair Approach 2 uses 12 bytes per pair (but only for pairs with count 0) J. Leskovec, A