1 00:00:00,700 --> 00:00:03,960 We're now going to learn the basic A-Priori Algorithm. 2 00:00:03,960 --> 00:00:07,010 Later we'll see some improvements to this basic idea, but 3 00:00:07,010 --> 00:00:09,360 the fundamental inside is monotonicity. 4 00:00:09,360 --> 00:00:12,480 The idea that an itemset cannot be frequent unless all 5 00:00:12,480 --> 00:00:13,860 its subsets are frequent. 6 00:00:13,860 --> 00:00:18,750 The A-Priori Algorithm uses one pass for finding the frequent items, 7 00:00:18,750 --> 00:00:22,440 then another pass through the data for finding frequent pairs. 8 00:00:22,440 --> 00:00:26,070 And if we want frequent triples we need another pass and, and so on. 9 00:00:27,160 --> 00:00:31,310 Each pass after the first can be thought of as having identified a small number of 10 00:00:31,310 --> 00:00:36,210 sets with a relevent size that might be frequent, and therefore require a count. 11 00:00:36,210 --> 00:00:39,340 But the power of our priority comes from the fact that for 12 00:00:39,340 --> 00:00:42,950 many data sets we can eliminate almost all sets from candidacy and 13 00:00:42,950 --> 00:00:46,850 thus greatly reduce the number of counts we need to maintain in main memory. 14 00:00:50,160 --> 00:00:53,180 When you think of the a-priori algorithm as a two pass algorithm, 15 00:00:53,180 --> 00:00:55,970 since that what it needs to find frequent pairs, but 16 00:00:55,970 --> 00:00:59,350 as we just said if you want to go pass pairs to larger item sets, 17 00:00:59,350 --> 00:01:03,330 then you need k passes, define frequent items that's of size up to K. 18 00:01:03,330 --> 00:01:09,650 A monotonicity property which A-Priori exploits, says that 19 00:01:09,650 --> 00:01:14,710 if a set of items appears in at least S baskets, then so does each of its subsets. 20 00:01:14,710 --> 00:01:15,800 That should be obvious, 21 00:01:15,800 --> 00:01:19,260 since there are S baskets that contain all members of the set. 22 00:01:19,260 --> 00:01:23,230 And so, surely these s baskets also contain any of it's subsets. 23 00:01:23,230 --> 00:01:26,610 And there may be more baskets that contain the subset but not the full set. 24 00:01:29,300 --> 00:01:32,468 Now, we actually use this definition in it's contrapositive form. 25 00:01:32,468 --> 00:01:36,060 For example, when we're looking for frequent pairs, 26 00:01:36,060 --> 00:01:41,120 the key observation is that is an item i does not appear s times by itself, 27 00:01:41,120 --> 00:01:43,680 then no set containing I could be frequent. 28 00:01:43,680 --> 00:01:47,700 Because if, say the set of I and J appears in S baskets, 29 00:01:47,700 --> 00:01:52,030 then surely I appears in all those baskets and maybe others. 30 00:01:53,180 --> 00:01:56,506 This is all rea, really obvious, but it's also essential and 31 00:01:56,506 --> 00:01:58,653 I want to make sure everyone is onboard. 32 00:02:01,983 --> 00:02:05,520 On the first pass, we count the number of times each item occurs. 33 00:02:05,520 --> 00:02:07,185 We want to do this in main memory un, 34 00:02:07,185 --> 00:02:10,340 and unless the number of items is beyond billions. 35 00:02:10,340 --> 00:02:13,110 We can set up an integer count for each item in main memory. 36 00:02:16,180 --> 00:02:20,380 After the first pass, we see which items appear at least s times. 37 00:02:20,380 --> 00:02:21,460 These are the frequent items. 38 00:02:22,820 --> 00:02:26,350 Incidentally, if all we want is to tell whether or not an item appears s or 39 00:02:26,350 --> 00:02:31,490 more times, then it is sufficient to count up to s and not add ones beyond that. 40 00:02:31,490 --> 00:02:35,900 So, if say s is 10,000, then we only need to keep 2 bytes per count, 41 00:02:35,900 --> 00:02:39,337 regardless of how many times items might appear in the data. 42 00:02:43,226 --> 00:02:47,790 Now, let's look at pass two, where we read all the baskets from disk again. 43 00:02:47,790 --> 00:02:52,200 And as in the naive algorithm, we're going to try to count pairs in main memory. 44 00:02:52,200 --> 00:02:56,920 But now we use monotonicity, so we only have to count those pairs of items both of 45 00:02:56,920 --> 00:02:58,880 which are among the frequent items. 46 00:02:58,880 --> 00:02:59,930 So, for example, 47 00:02:59,930 --> 00:03:04,404 if only half the items are frequent, we need to count only a quarter of all pairs. 48 00:03:09,688 --> 00:03:11,650 Okay. The main memory we need depends on 49 00:03:11,650 --> 00:03:14,690 the square of the number of frequent items only, but 50 00:03:14,690 --> 00:03:17,710 there's a small amount of additional main memory we need for 51 00:03:17,710 --> 00:03:21,600 a table that lets us know which of the items are, in fact, frequent. 52 00:03:21,600 --> 00:03:24,750 As we read a basket from disk, we look at all its items and 53 00:03:24,750 --> 00:03:28,600 ignore any that are not in the table of frequent items. 54 00:03:28,600 --> 00:03:32,750 From what remains, we generate all pairs and increment each of their counts. 55 00:03:34,270 --> 00:03:35,620 So, here's a picture, 56 00:03:35,620 --> 00:03:39,039 the first of the series we're going to use to compare different algorithms. 57 00:03:41,010 --> 00:03:47,110 The rectangles each represent main memory and how it is used on each pass. 58 00:03:47,110 --> 00:03:50,670 On the left, we see the first pass of the A-Priori algorithm. 59 00:03:50,670 --> 00:03:54,730 We need space in main memory, only for the counts of the items and 60 00:03:54,730 --> 00:03:58,120 we show it as occupying only a small fraction of main memory, 61 00:03:58,120 --> 00:04:02,370 because typically we will need much more main memory for the second pass. 62 00:04:03,680 --> 00:04:07,440 In the second pass we distilled the item count from the first pass down to 63 00:04:07,440 --> 00:04:09,410 a list of frequent items. 64 00:04:09,410 --> 00:04:13,250 This list is probably implemented as a hash table or similar structure. 65 00:04:13,250 --> 00:04:17,410 So, given an item, we can quickly tell whether it is frequent. 66 00:04:17,410 --> 00:04:22,050 The rest of main memory is available for counting all the pairs of frequent items. 67 00:04:22,050 --> 00:04:25,190 For a-priori to work in a reasonable amount of time, 68 00:04:25,190 --> 00:04:29,060 these counts must all be able to fit in main memory. 69 00:04:29,060 --> 00:04:31,580 If there's still too many counts to maintain in main memory, 70 00:04:31,580 --> 00:04:34,880 we need to try something else, a different algorithm, 71 00:04:34,880 --> 00:04:38,039 splitting the task among different processors, or even buying more memory. 72 00:04:41,920 --> 00:04:45,210 You might suppose that when you're counting only pairs of frequent items you 73 00:04:45,210 --> 00:04:48,530 have to use the tabular method to store counts, 74 00:04:48,530 --> 00:04:52,150 since we hope that only a small fraction of the possible pairs need to be counted. 75 00:04:53,170 --> 00:04:56,060 Since the numbers associated with the frequent items are not likely to 76 00:04:56,060 --> 00:04:57,370 be consecutive. 77 00:04:57,370 --> 00:05:00,270 It looks like we can't use the triangular matrix with counts for 78 00:05:00,270 --> 00:05:02,490 only the pairs of frequent items. 79 00:05:02,490 --> 00:05:06,610 Or if we did, we'd use just as much space as if we were counting all pairs, and 80 00:05:06,610 --> 00:05:07,940 we might not have that much space. 81 00:05:09,174 --> 00:05:12,110 fortunately, there's a, a simple trick we can use. 82 00:05:13,450 --> 00:05:16,210 We re-number the frequent items, starting at one. 83 00:05:16,210 --> 00:05:19,560 And on the second pass, we store a table that translates the original 84 00:05:19,560 --> 00:05:25,190 integers used for all items into the new numbers for the frequent items only. 85 00:05:25,190 --> 00:05:27,950 This table also tells you whether an item is frequent or 86 00:05:27,950 --> 00:05:31,045 not, since it will not appear in the table if it is not frequent. 87 00:05:31,045 --> 00:05:36,943 [SOUND] So, here's the picture of A-Priori again. 88 00:05:36,943 --> 00:05:40,655 We show the table on the second pass as taking more space than before, 89 00:05:40,655 --> 00:05:43,220 since it stores two numbers per frequent item. 90 00:05:44,820 --> 00:05:48,280 And needs to store each item, even those that are not frequent. 91 00:05:48,280 --> 00:05:52,390 So, we can index into the table given an old number, and find either its number 92 00:05:52,390 --> 00:05:57,530 among the frequent items, like 1, which has new frequent, number 1. 93 00:05:57,530 --> 00:06:00,488 3 has new number 2. 94 00:06:00,488 --> 00:06:03,960 or, as in this case, we can find it's not frequent. 95 00:06:07,110 --> 00:06:09,660 There are better ways to organize the table that save space, 96 00:06:09,660 --> 00:06:12,460 if the fraction of items that are frequent is small. 97 00:06:12,460 --> 00:06:16,350 For example, we could use a hash table in which we stored only the frequent items 98 00:06:16,350 --> 00:06:20,252 with the key being the old number and the associated value being the new number. 99 00:06:20,252 --> 00:06:25,540 What we're, we're not showing as a table that all algorithms may need, one 100 00:06:25,540 --> 00:06:30,899 that translates from the representation of items in the raw data, to the old numbers, 101 00:06:31,980 --> 00:06:36,150 that is the consecutive integers that we used for all the items. 102 00:06:40,790 --> 00:06:43,810 The idea used on the second pass extends to later passes that 103 00:06:43,810 --> 00:06:45,130 construct larger sets. 104 00:06:47,000 --> 00:06:50,760 Let's use the term k-set for an item set with k members. 105 00:06:50,760 --> 00:06:54,270 Then there are two collections of k-sets associated with our effort to 106 00:06:54,270 --> 00:06:58,620 find all the frequent k-sets. 107 00:06:58,620 --> 00:07:02,750 C sub k is the candidate case sets. 108 00:07:02,750 --> 00:07:06,690 These are the sets that based on what information we have from previous passes, 109 00:07:06,690 --> 00:07:07,399 might be frequent. 110 00:07:08,520 --> 00:07:11,830 At least we can't rule out the possibility they're being frequent by using 111 00:07:11,830 --> 00:07:15,840 monotonicity, so we have to count them. 112 00:07:15,840 --> 00:07:20,690 And then, the result of the kth pass we'll call L sub k. 113 00:07:20,690 --> 00:07:24,910 This is the subset of C sub k consisting of those k sets that are found on 114 00:07:24,910 --> 00:07:28,059 the kth facts to be really frequent. 115 00:07:31,115 --> 00:07:34,910 And here's a picture of the full A-Priori algorithm including not only pairs, but 116 00:07:34,910 --> 00:07:38,650 a suggestion of the process for larger item sets. 117 00:07:38,650 --> 00:07:40,220 In fact, this is the picture for 118 00:07:40,220 --> 00:07:44,630 a whole family of related algorith, algorithms where each algorithm is 119 00:07:44,630 --> 00:07:48,370 characterized by a different way to construct the set of candidate pair C2. 120 00:07:49,980 --> 00:07:54,160 Each pass consists of a filter step, where we look at the candidate sets for 121 00:07:54,160 --> 00:07:57,410 the pass and select only the frequent sets. 122 00:07:57,410 --> 00:07:59,430 That is CK is turned into LK. 123 00:08:01,210 --> 00:08:04,570 Each pass also has a construction step where the candidates for 124 00:08:04,570 --> 00:08:08,720 the next pass are constructed from the frequent sets for the current pass. 125 00:08:08,720 --> 00:08:13,050 That is on the K pass, CK is constructed from L sub K minus one. 126 00:08:16,580 --> 00:08:20,250 We start with C1, the set of candidate singleton item sets. 127 00:08:20,250 --> 00:08:21,350 These are all items, 128 00:08:21,350 --> 00:08:24,530 since we have no way of eliminating any items without looking at the data. 129 00:08:27,580 --> 00:08:30,360 The filter step for the first pass counts the items and 130 00:08:30,360 --> 00:08:31,610 finds those that are frequent. 131 00:08:35,830 --> 00:08:38,150 So, the set L1 is just the frequent items. 132 00:08:42,820 --> 00:08:47,330 From L1, we construct C2, the set of candidate pairs for the second pass. 133 00:08:47,330 --> 00:08:49,700 In this case we don't actually do anything. 134 00:08:49,700 --> 00:08:55,824 The set C2 is defined implicitly from the lists of, the list of items in the set L1. 135 00:09:01,087 --> 00:09:01,650 Okay. 136 00:09:01,650 --> 00:09:05,300 The filter step for the second pass counts all the pairs in C2, 137 00:09:06,620 --> 00:09:10,140 and the result is the truly frequent pairs of items. 138 00:09:13,728 --> 00:09:16,580 We can proceed like this from the frequent pairs. 139 00:09:16,580 --> 00:09:17,510 We construct C3, 140 00:09:17,510 --> 00:09:22,090 the candidate triples by a technique we’ll describe on the next slide. 141 00:09:22,090 --> 00:09:28,409 Then we filter C3 to get L3, from that we construct C4, and so on. 142 00:09:32,155 --> 00:09:34,220 We can describe the apriori algorithm for 143 00:09:34,220 --> 00:09:36,700 item sets of all sizes an as, as an induction on k. 144 00:09:36,700 --> 00:09:40,320 And the size of the item sets we construct. 145 00:09:40,320 --> 00:09:42,010 There, there is one pass for each k. 146 00:09:42,010 --> 00:09:46,720 The basis is that C1 is the set of all items. 147 00:09:46,720 --> 00:09:50,380 Strictly speaking C1 consists of all the singleton sets, 148 00:09:50,380 --> 00:09:52,430 each of those sets containing one of the items. 149 00:09:57,010 --> 00:10:01,010 Given the set CK, we can construct L K by making a path through the data and 150 00:10:01,010 --> 00:10:03,220 counting each set in CK. 151 00:10:03,220 --> 00:10:07,079 Those sets whose counts get up to the threshold S, become members of LK. 152 00:10:09,180 --> 00:10:12,990 The other part of the induction is how we construct CK plus one from LK. 153 00:10:14,010 --> 00:10:18,440 We look for sets of size K plus one, each of whose subsets are size K, 154 00:10:18,440 --> 00:10:21,770 those you get by dropping one element, or in LK. 155 00:10:22,940 --> 00:10:25,420 You have to be a little careful how you organize the search. 156 00:10:25,420 --> 00:10:29,050 For example, you wouldn't want to enumerate all sets of size four. 157 00:10:29,050 --> 00:10:32,970 And for each one, tested if each of its four subsets of size 3 are in L 3. 158 00:10:32,970 --> 00:10:38,680 A better idea is to start with some set, set in LK. 159 00:10:39,910 --> 00:10:41,640 For example, assume k equals 3. 160 00:10:42,940 --> 00:10:49,940 We might find the set let's say 1, 3, 5 is in L k. 161 00:10:51,470 --> 00:10:57,370 Now, look at each item who's number is higher than any in the set, say, six. 162 00:10:57,370 --> 00:10:59,910 Okay. 163 00:10:59,910 --> 00:11:01,680 This set might be in C 4. 164 00:11:01,680 --> 00:11:04,366 We already know its subset. 165 00:11:04,366 --> 00:11:09,990 That is a subset of well, so it's about, talking about really 1, 3, 5, 6. 166 00:11:09,990 --> 00:11:16,100 Now, we already know that its subset 1,3,5 is is in L3. 167 00:11:17,200 --> 00:11:19,980 So, we have to test three other sets. 168 00:11:19,980 --> 00:11:28,627 We have to test well, 3, 5, 6 and 1, 169 00:11:28,627 --> 00:11:34,480 5, 6, and I guess 1, 3, 6. 170 00:11:34,480 --> 00:11:40,870 And if all three of these are in L3, 171 00:11:40,870 --> 00:11:46,110 then we would put this guy, 1, 3, 5, 6 in C4. 172 00:11:47,940 --> 00:11:52,500 Then we're not done with starting again with 1, 3, 5. 173 00:11:52,500 --> 00:11:57,590 We might the, then throw in the element seven an so on and eight and, and nine 174 00:11:58,920 --> 00:12:04,310 all the time searching for sets of size four, 175 00:12:04,310 --> 00:12:09,950 each of whose subsets of size three are, are known to be frequent. 176 00:12:11,740 --> 00:12:12,780 The space needed on the, 177 00:12:12,780 --> 00:12:16,110 on the kth pass is proportional to the number of sets in CK. 178 00:12:18,530 --> 00:12:21,440 In principle there could be as many as n choose k. 179 00:12:27,150 --> 00:12:29,620 Candidate sets of size k. 180 00:12:29,620 --> 00:12:32,200 If there are k, if there are, are n items. 181 00:12:32,200 --> 00:12:38,670 So the space requirement could grow painfully each time k increased, but 182 00:12:38,670 --> 00:12:41,240 in cases where this method is used in practice, 183 00:12:41,240 --> 00:12:45,170 the support threshold is high enough that as k increases beyond two, 184 00:12:45,170 --> 00:12:48,960 the number of candidate sets that could be formed from the frequent sets on 185 00:12:48,960 --> 00:12:53,350 the previous pass, actually decreases, doesn't increase. 186 00:12:53,350 --> 00:12:56,100 Thus the memory requirements, peak at k equals 2, 187 00:12:56,100 --> 00:12:59,400 and that's why we concentrate on finding frequent pairs. 188 00:12:59,400 --> 00:13:02,460 And why the more advanced algorithms we'll see in the next unit, 189 00:13:02,460 --> 00:13:05,720 different from A-Priory, and how they handle the pairs.