1 00:00:00,190 --> 00:00:02,860 The study of how we find frequent itemsets was one of 2 00:00:02,860 --> 00:00:06,068 the earliest directions taken by data mining researchers. 3 00:00:06,068 --> 00:00:10,710 And the A-Priori algorithm is probably the most sited work in the data mining field. 4 00:00:11,800 --> 00:00:15,050 The motivation for this study was to determine unusual sets of 5 00:00:15,050 --> 00:00:18,440 items that people purchase together in supermarkets. 6 00:00:18,440 --> 00:00:21,780 No discussion of finding frequent itemsets would be complete without 7 00:00:21,780 --> 00:00:25,010 mentioning the possibly apocryphal story of beer and 8 00:00:25,010 --> 00:00:27,460 diapers, and we'll tell that one soon enough. 9 00:00:28,460 --> 00:00:31,760 but, in rough outline, we're going to start with a model of 10 00:00:31,760 --> 00:00:36,550 data called The Market-Basket Model, where data consists of sets of items, 11 00:00:36,550 --> 00:00:40,270 the sets are called baskets for a reason we'll discuss. 12 00:00:40,270 --> 00:00:43,320 And a set of items is called frequent if it appears in some large 13 00:00:43,320 --> 00:00:44,199 number of baskets. 14 00:00:45,640 --> 00:00:49,270 We'll talk about association rules which are statements that when a certain set of 15 00:00:49,270 --> 00:00:54,000 items are found in a basket then it is unusually likely that another items will 16 00:00:54,000 --> 00:00:55,940 also be found there. 17 00:00:55,940 --> 00:01:00,710 And finally we'll give A-Priori algorithm for finding frequent item sets. 18 00:01:00,710 --> 00:01:03,830 This algorithm while it has been improved upon over the years 19 00:01:03,830 --> 00:01:06,489 is the fundamental starting point for all of these improvements. 20 00:01:10,410 --> 00:01:13,580 The Market-Basket model is essentially a representation of the many, 21 00:01:13,580 --> 00:01:17,860 many relationships between two concepts, which we'll call items in baskets. 22 00:01:19,410 --> 00:01:21,990 On one hand, there's a large set of items. 23 00:01:23,080 --> 00:01:26,430 An example is all the different items Wal-Mart sells. 24 00:01:26,430 --> 00:01:28,910 Of which there are hundreds of thousands. 25 00:01:28,910 --> 00:01:31,130 This was the original purpose of the model, 26 00:01:31,130 --> 00:01:34,220 analyzing the things people bought at a store. 27 00:01:34,220 --> 00:01:36,510 However the model has many other applications, a, 28 00:01:36,510 --> 00:01:39,050 a few of which we'll talk about shortly. 29 00:01:40,520 --> 00:01:42,910 And then on the other hand, there's a large set of baskets. 30 00:01:42,910 --> 00:01:45,200 Each basket contains a small set of items. 31 00:01:45,200 --> 00:01:49,420 The original picture was that a market basket was a shopping cart, 32 00:01:49,420 --> 00:01:52,220 a physical, that is not electronic. 33 00:01:52,220 --> 00:01:55,700 And customer's would wheel their market basket up to the check-out. 34 00:01:55,700 --> 00:01:59,960 The cash register would group all the items in the basket together in one bill, 35 00:01:59,960 --> 00:02:02,470 and that bill would be stored in the store's computer system. 36 00:02:03,720 --> 00:02:06,790 Plus by mining the contents of the various market baskets. 37 00:02:06,790 --> 00:02:09,190 The store can learn what people bought together. 38 00:02:09,190 --> 00:02:11,010 A hamburger and ketchup for example. 39 00:02:12,120 --> 00:02:16,810 And that in turn would let the store figure out some ploys to increase sales. 40 00:02:16,810 --> 00:02:20,150 Think about what a store might do to exploit this information. 41 00:02:20,150 --> 00:02:22,060 We're going to return to the subject shortly. 42 00:02:24,930 --> 00:02:26,130 The most useful, and 43 00:02:26,130 --> 00:02:30,570 also the most basic question to ask about data in the form of market baskets is to 44 00:02:30,570 --> 00:02:34,500 find those sets of items that appear in some minimum number of baskets. 45 00:02:36,860 --> 00:02:38,130 Define the support for 46 00:02:38,130 --> 00:02:42,419 an itemset to be the number of baskets of which that itemset is a subset. 47 00:02:44,700 --> 00:02:47,540 We can give the support either as an absolute number or 48 00:02:47,540 --> 00:02:49,350 as a percentage of all the baskets. 49 00:02:51,570 --> 00:02:56,010 Data mining problem called frequent itemsets involve a number or 50 00:02:56,010 --> 00:02:59,270 percentage s called the support threshold. 51 00:02:59,270 --> 00:03:02,811 Any set of items with support at least s is called a frequent itemset 52 00:03:06,373 --> 00:03:09,990 'Kay, here's a very simple example of data in the market basket model. 53 00:03:09,990 --> 00:03:15,080 Okay, there are five items, milk, Coke, Pepsi, beer and juice. 54 00:03:17,360 --> 00:03:19,140 The support threshold will be three, 55 00:03:19,140 --> 00:03:21,989 it's an absolute number not a percentage of the baskets. 56 00:03:23,720 --> 00:03:24,720 Here are the baskets. 57 00:03:24,720 --> 00:03:30,270 We're using M for milk; C for coke; and you can probably figure out the rest. 58 00:03:33,530 --> 00:03:35,800 Now, what are the frequent itemsets? 59 00:03:35,800 --> 00:03:40,109 Well, almost all the singletons are frequent. 60 00:03:41,200 --> 00:03:46,173 Each of the items except Pepsi appears in at least three baskets For 61 00:03:46,173 --> 00:03:51,510 example, beer appears in b1, 62 00:03:51,510 --> 00:03:57,830 b3, b5, b7, b6 and b8. 63 00:03:59,520 --> 00:04:01,200 'Kay. 64 00:04:02,562 --> 00:04:08,627 Pepsi itself is not frequent because 65 00:04:08,627 --> 00:04:13,328 it appears only in B2 and B5. 66 00:04:21,029 --> 00:04:23,442 There are also some frequent doubletons. 67 00:04:23,442 --> 00:04:27,390 For example, milk and beer appear together in the four baskets shown. 68 00:04:31,554 --> 00:04:34,939 And beer and Coke also appear in four baskets. 69 00:04:36,700 --> 00:04:39,490 And finally, Coke and ju- 70 00:04:39,490 --> 00:04:43,450 juice appear together in three baskets. 71 00:04:43,450 --> 00:04:45,740 But no other doubletons are frequent. 72 00:04:45,740 --> 00:04:52,110 For example, milk and juice appear together in B2 and B6. 73 00:04:55,780 --> 00:04:58,370 But in no other baskets, okay? 74 00:04:58,370 --> 00:05:01,810 Also, there are no sets with three or more items that are frequent. 75 00:05:01,810 --> 00:05:02,400 So we're done. 76 00:05:02,400 --> 00:05:05,720 We have found all the frequent items sets. 77 00:05:05,720 --> 00:05:07,490 One might have included the empty set, 78 00:05:07,490 --> 00:05:10,330 that is surely a subset of all eight baskets. 79 00:05:10,330 --> 00:05:13,750 But the fact is uninteresting and we usually ignore the empty set. 80 00:05:19,255 --> 00:05:22,032 As I mentioned, the, the original application for 81 00:05:22,032 --> 00:05:27,130 this sort of analysis was looking at the things people bought together in a store. 82 00:05:27,130 --> 00:05:30,920 In this case the items really are the items one might buy, and 83 00:05:30,920 --> 00:05:34,060 the baskets are sets of items bought together by one purchaser. 84 00:05:37,340 --> 00:05:40,200 There's a story that the first interesting discovery of 85 00:05:40,200 --> 00:05:43,900 a frequent item set was that diapers and beer were frequently bought together. 86 00:05:45,540 --> 00:05:48,430 And once you think about it it makes sense. 87 00:05:48,430 --> 00:05:50,730 If you're buying diapers you probably have a baby at home. 88 00:05:50,730 --> 00:05:55,680 If you have a baby at home you probably aren't going out to a bar to drink. 89 00:05:55,680 --> 00:05:56,580 So you bring the beer home. 90 00:05:58,090 --> 00:06:01,940 I have heard several people claim that they themselves discovered this, so 91 00:06:01,940 --> 00:06:06,650 I suspect that really nobody did and it's just an illustration of something that you 92 00:06:06,650 --> 00:06:11,600 wouldn't think of without a way to analyze massive amounts of data but 93 00:06:11,600 --> 00:06:15,840 which proves to be true and explainable rationally once you see it. 94 00:06:15,840 --> 00:06:16,350 Okay. 95 00:06:16,350 --> 00:06:20,020 The first thing marketers did with information like this was to 96 00:06:20,020 --> 00:06:21,210 reorganize their shelves. 97 00:06:22,350 --> 00:06:25,320 They would put the diapers and beer near each other, but 98 00:06:25,320 --> 00:06:28,560 put another item that made sense between them, like potato chips. 99 00:06:29,640 --> 00:06:33,110 But there is a more subtle way to exploit the data mining discovery. 100 00:06:35,650 --> 00:06:40,120 Suppose we want a, a sale on diapers, but we raise the price of beer. 101 00:06:41,500 --> 00:06:44,070 People will come in to buy the cheap diapers, and 102 00:06:44,070 --> 00:06:47,290 while they are there in store, they are likely to pick up some beer, 103 00:06:47,290 --> 00:06:50,920 not noticing the price is too high, or even if they do. 104 00:06:50,920 --> 00:06:55,210 Figuring it doesn't make sense to drive to another store just to buy beer. 105 00:06:55,210 --> 00:06:56,380 Everybody wins. 106 00:06:56,380 --> 00:06:57,810 The customer doesn't lose money. 107 00:06:57,810 --> 00:07:00,060 And the store gets more customers and 108 00:07:00,060 --> 00:07:02,760 on average receives the same amount from each customer. 109 00:07:03,970 --> 00:07:06,670 Only the competitors of the store who don't have their own 110 00:07:06,670 --> 00:07:08,279 data mining experts lose. 111 00:07:10,970 --> 00:07:16,150 Incidentally, a subtle point here is that there is causality operating. 112 00:07:16,150 --> 00:07:19,500 And it's very hard to deduce causality from data. 113 00:07:19,500 --> 00:07:23,300 That is, if you don't think about the causes underlying the data, 114 00:07:23,300 --> 00:07:27,130 you might imagine that you could just as well run a sale on beer and 115 00:07:27,130 --> 00:07:29,350 raise the price of diapers. 116 00:07:29,350 --> 00:07:30,500 But people who come in for 117 00:07:30,500 --> 00:07:34,590 the sale on beer are not going to buy diapers if they don't have a baby. 118 00:07:37,690 --> 00:07:41,090 I just want to point out that these techniques are appropriate mainly for 119 00:07:41,090 --> 00:07:42,880 brick and mortar stores. 120 00:07:42,880 --> 00:07:46,360 A brick and mortar store needs to know that lots of people buy diapers and 121 00:07:46,360 --> 00:07:48,720 beer, or else they're wasting time and 122 00:07:48,720 --> 00:07:52,270 money optimizing the sale of something that is rarely bought anyway. 123 00:07:53,630 --> 00:07:56,260 That viewpoint matches well with the idea that we're looking for 124 00:07:56,260 --> 00:08:01,970 high frequency rather than correlation between rarely purchased sets of items. 125 00:08:01,970 --> 00:08:05,560 Online stores, on the other hand, do not need to rely on high frequencies since 126 00:08:05,560 --> 00:08:09,200 they can tailor their store differently for each customer. 127 00:08:09,200 --> 00:08:12,380 Thus, entirely different forms of analysis are leaded, are, 128 00:08:12,380 --> 00:08:17,350 are needed for online stores, and we'll cover that as a separate topic. 129 00:08:21,860 --> 00:08:24,550 Here's another problem that uses the same data model with 130 00:08:24,550 --> 00:08:26,220 an entirely different interpretation. 131 00:08:27,970 --> 00:08:29,850 Suppose our data is a collection of documents. 132 00:08:31,000 --> 00:08:34,660 Think of the sentences that appear in one or more documents as a basket. 133 00:08:35,990 --> 00:08:39,750 The items are the documents themselves, and the basket corresponding to 134 00:08:39,750 --> 00:08:43,290 a sentence contains all the documents in which that sentence appears. 135 00:08:45,230 --> 00:08:50,260 Now what does it mean if a set of items appears together in many baskets? 136 00:08:50,260 --> 00:08:53,000 The item set is a set of documents. 137 00:08:53,000 --> 00:08:57,410 And these documents or items appear in a lotta baskets together. 138 00:08:57,410 --> 00:09:00,900 That means there's a collection of documents in which a lot of 139 00:09:00,900 --> 00:09:03,240 the same sentences appear. 140 00:09:03,240 --> 00:09:06,490 Documents that look like that may well be an instance of plagiarism. 141 00:09:09,930 --> 00:09:12,420 It is interesting to note that in this case the items, 142 00:09:12,420 --> 00:09:15,690 the documents are not in the baskets which are sentences. 143 00:09:15,690 --> 00:09:17,790 In, in fact it's the other way around. 144 00:09:17,790 --> 00:09:22,220 But as we mentioned, items in baskets form a many to many relationship, and 145 00:09:22,220 --> 00:09:24,810 you can always view such a relationship from either side. 146 00:09:26,870 --> 00:09:30,340 However, when it comes to the algorithms we'll discuss there is an asymmetry. 147 00:09:32,030 --> 00:09:34,670 We assume that baskets contain small numbers of items, 148 00:09:34,670 --> 00:09:38,790 while items can be in very very large number of, of baskets. 149 00:09:38,790 --> 00:09:44,350 The algorithms would take too much time if baskets contain large numbers of items, 150 00:09:44,350 --> 00:09:48,200 because the work done processing each basket is normally quadratic in 151 00:09:48,200 --> 00:09:49,560 the number of items it contains. 152 00:09:54,430 --> 00:09:56,870 Here's another application involving documents. 153 00:09:56,870 --> 00:10:01,300 Let the baskets now be the documents and let the items be words. 154 00:10:01,300 --> 00:10:07,120 We can think of a basket, a document that is as the set of words it contains. 155 00:10:07,120 --> 00:10:10,980 But remember what we just said we have to be careful that the average basket doesn't 156 00:10:10,980 --> 00:10:12,730 contain too many items. 157 00:10:12,730 --> 00:10:16,090 If documents are books for example it would contain thousands of 158 00:10:16,090 --> 00:10:21,080 different words but if documents are tweets or emails we're okay. 159 00:10:21,080 --> 00:10:27,060 Because these are typically short in the case of tweets they're necessarily short. 160 00:10:27,060 --> 00:10:30,270 We can cut down on the number of words in the document by 161 00:10:30,270 --> 00:10:35,150 ignoring stop words as well the common, these are the common little words that 162 00:10:35,150 --> 00:10:37,160 usually don't carry any significant meaning. 163 00:10:40,460 --> 00:10:42,830 Now what does it mean if a set of items is frequent. 164 00:10:44,240 --> 00:10:45,260 That means, we have a set of 165 00:10:45,260 --> 00:10:48,270 words that appear together in a large number of documents. 166 00:10:48,270 --> 00:10:51,450 By the way, that's another reason to get rid of all the words that 167 00:10:51,450 --> 00:10:52,920 are not pretty rare. 168 00:10:52,920 --> 00:10:55,370 Or we'll just discover the words like the and, 169 00:10:55,370 --> 00:10:57,860 and, appear together in many documents. 170 00:10:57,860 --> 00:10:59,770 That's a big deal, right? 171 00:11:00,820 --> 00:11:01,380 On the other hand, 172 00:11:01,380 --> 00:11:05,800 if rare words are, are relatively, frequently found in the same documents. 173 00:11:05,800 --> 00:11:08,620 And there might be some connection between the words. 174 00:11:08,620 --> 00:11:14,880 Supposing say that Brad and Angelina might be two such words or is that old news? 175 00:11:14,880 --> 00:11:19,630 Probably is. 176 00:11:19,630 --> 00:11:24,880 Anyway just to remind you of the scale of the sort of problem we're thinking about. 177 00:11:24,880 --> 00:11:28,120 If we're dealing with real market baskets a big store like Wal-Mart will 178 00:11:28,120 --> 00:11:30,710 sell a hundred thousand different items, and 179 00:11:30,710 --> 00:11:35,510 stores billions of baskets in its database for analysis. 180 00:11:35,510 --> 00:11:38,800 On the other hand, the web has billions of different words, 181 00:11:38,800 --> 00:11:42,709 most of them by the way are misspellings, and many billions of pages 182 00:11:47,410 --> 00:11:51,743 Often the problem of finding frequent item sets is characterized is the problem of 183 00:11:51,743 --> 00:11:54,200 discovering association rules. 184 00:11:54,200 --> 00:11:58,450 These are rules that say, if a basket contains some collection of items, 185 00:11:58,450 --> 00:12:01,319 then it is also likely to contain another particular item. 186 00:12:04,091 --> 00:12:07,870 The notation for association rules that we use, is shown here. 187 00:12:07,870 --> 00:12:13,080 Informally if we assert an association rule that says, i1 through ik, implies j. 188 00:12:14,170 --> 00:12:16,840 We mean that if a basket contains all of i1 through ik, 189 00:12:18,180 --> 00:12:20,050 then it is likely to contain j as well. 190 00:12:22,830 --> 00:12:26,150 The degree to which this event is likely is called the confidence of the rule. 191 00:12:27,530 --> 00:12:30,690 It's the fraction of the baskets containing i1 through ik that 192 00:12:30,690 --> 00:12:31,860 also contain j. 193 00:12:34,970 --> 00:12:37,750 For example, here are the eight baskets we saw earlier. 194 00:12:39,300 --> 00:12:42,550 A possible association rule is this. 195 00:12:42,550 --> 00:12:44,620 Milk and beer imply Coke. 196 00:12:47,880 --> 00:12:51,260 Let's focus on the four baskets that have both milk and beer. 197 00:12:52,400 --> 00:12:55,850 We see that B1 and B6 do have Coke. 198 00:12:57,280 --> 00:12:59,540 While B3 and B5 do not. 199 00:13:01,600 --> 00:13:04,520 Plus two out of the four baskets with milk and 200 00:13:04,520 --> 00:13:08,926 beer do have Coke and the confidence of this rule is 50%. 201 00:13:08,926 --> 00:13:14,158 [SOUND] One reasonable thing to do with market basket data is 202 00:13:14,158 --> 00:13:19,620 to find all association rules that have a minimum support s. 203 00:13:19,620 --> 00:13:21,690 And in minimum confidence c. 204 00:13:21,690 --> 00:13:25,460 For some values of s and c that you decide on before you run the algorithms. 205 00:13:26,500 --> 00:13:33,070 The support of an association rules the support side to the left of the arrow. 206 00:13:33,070 --> 00:13:36,659 That is it is the number of baskets containing all the items on the left. 207 00:13:38,570 --> 00:13:42,360 The hard part of finding association rules is really finding the frequent itemsets. 208 00:13:45,920 --> 00:13:52,460 If an association rule like this has support s, then 209 00:13:52,460 --> 00:13:56,770 the set on the left will be frequent with support s, that is the set i1 through ik. 210 00:13:58,830 --> 00:14:01,220 But if the confidence of the rule is also high. 211 00:14:01,220 --> 00:14:06,300 That is the confidence c is close to 1, then the set of items with j, 212 00:14:06,300 --> 00:14:11,100 the item on the right thrown in will have support cs. 213 00:14:19,660 --> 00:14:27,019 Now if c is large then cs would be close to s, say perhaps, one-half of s. 214 00:14:30,650 --> 00:14:31,910 Okay, and here's a recipe for 215 00:14:31,910 --> 00:14:35,430 finding all the association rules that support s in confidence c. 216 00:14:37,790 --> 00:14:41,160 Start by finding all the item sets with support at least cs. 217 00:14:42,300 --> 00:14:45,580 Also find the item sets with support at least s. 218 00:14:45,580 --> 00:14:48,189 Now that will be a subset of the first set of item sets. 219 00:14:51,960 --> 00:14:55,370 Lets focus on an item set in the first collection that is one with support at 220 00:14:55,370 --> 00:14:56,670 least cs. 221 00:14:56,670 --> 00:14:59,160 Suppose it has k plus one items as members. 222 00:15:00,270 --> 00:15:05,700 There are k plus one subsets of size k each formed by removing one of the items. 223 00:15:05,700 --> 00:15:08,950 I've abused the notation abit by singling out one of them as j. 224 00:15:10,880 --> 00:15:13,730 The item to be removed, leaving i 1 through i k. 225 00:15:14,810 --> 00:15:19,010 But in fact we have to do this k plus 1 times, one for each of the items. 226 00:15:20,850 --> 00:15:25,350 Having removed j, look at the support of the remaining set i 1 through i k. 227 00:15:26,990 --> 00:15:29,140 If it is at least s. 228 00:15:29,140 --> 00:15:33,720 We might have an association rule with the set that set on the left and 229 00:15:33,720 --> 00:15:35,300 the first item j on the right. 230 00:15:37,450 --> 00:15:39,200 Now suppose this set without j. 231 00:15:43,320 --> 00:15:44,550 Has support as 1. 232 00:15:44,550 --> 00:15:48,215 And with j the support goes down to s2. 233 00:15:48,215 --> 00:15:54,868 [SOUND] And the confidence with the rule is the ration S2 over S1, because 234 00:15:54,868 --> 00:16:01,643 that is the fraction of the baskets with I1 through IK that also contain J. 235 00:16:01,643 --> 00:16:06,079 If that confidence is at least C, then we have an acceptable association rule. 236 00:16:09,230 --> 00:16:12,360 We're gong to look at finding frequent item sets in a setting where the basket 237 00:16:12,360 --> 00:16:17,030 data is kept in a flat file, not any sort of database system. 238 00:16:17,030 --> 00:16:20,280 As I tried to argue in the previous slides, it is finding frequent item 239 00:16:20,280 --> 00:16:24,090 sets that is the hard part of finding association rules. 240 00:16:24,090 --> 00:16:28,010 So even if our goal is to get association rules and in many cases we really 241 00:16:28,010 --> 00:16:32,120 want only the frequent item sets anyway, not the association rules. 242 00:16:33,160 --> 00:16:36,480 We're going to talk from this point only about the problem of, 243 00:16:36,480 --> 00:16:38,360 of identifying the frequent item sets. 244 00:16:41,260 --> 00:16:44,360 We assume the data is so big that it has to be stored on disk. 245 00:16:44,360 --> 00:16:47,910 Since reading data from disk often takes more time than what you 246 00:16:47,910 --> 00:16:50,570 do with the data once it is in main memory. 247 00:16:50,570 --> 00:16:54,420 Our primary goal will be to minimize the number of times each disk block has to 248 00:16:54,420 --> 00:16:55,660 be read into main memory. 249 00:16:59,430 --> 00:17:04,420 We're also going to assume the data is stored basket-by-basket rather than by 250 00:17:04,420 --> 00:17:06,350 item or in any stranger way. 251 00:17:08,460 --> 00:17:12,170 And we're going to have to find for each basket, 252 00:17:12,170 --> 00:17:14,780 all it's subsets of a particular size. 253 00:17:14,780 --> 00:17:18,530 We can do that in main memory once the basket itself is there. 254 00:17:20,880 --> 00:17:24,950 We can use K nested loops to generate all subsets of size K. 255 00:17:24,950 --> 00:17:29,270 Since we assume baskets are small and often k will be only 1 or 2 anyway. 256 00:17:29,270 --> 00:17:32,400 We're not going to worry about the cost of doing this generation. 257 00:17:32,400 --> 00:17:34,950 However you should be alert to the possibility. 258 00:17:34,950 --> 00:17:38,700 That if you're asked to generate all subsets of size 100,000 259 00:17:38,700 --> 00:17:41,940 from a basket with a million items you just couldn't do it. 260 00:17:44,480 --> 00:17:45,030 Okay. 261 00:17:45,030 --> 00:17:48,070 So here's a picture of what we imagine the file looks like. 262 00:17:48,070 --> 00:17:52,620 Items have been coded as integers, so the file is a sequence of integers. 263 00:17:52,620 --> 00:17:56,340 We need to, a way to indicate where one basket ends and 264 00:17:56,340 --> 00:17:59,100 the next begins so we might use an integer like -1. 265 00:17:59,100 --> 00:18:03,999 Which we suppose can't represent an item as the separator for baskets. 266 00:18:06,930 --> 00:18:09,670 As we mentioned, we can focus on the number of times that this block 267 00:18:09,670 --> 00:18:11,530 has moved between disc and main memory. 268 00:18:14,070 --> 00:18:18,810 Turns out that the algorithms we will study each operate in passes. 269 00:18:18,810 --> 00:18:22,110 During a pass, the entire file is read block by block in order. 270 00:18:24,860 --> 00:18:29,960 A surrogate for the, the cost of the algorithm is thus the number of passes. 271 00:18:29,960 --> 00:18:33,670 The number of disk I/O's is, is that number, number of passes, 272 00:18:33,670 --> 00:18:38,633 times the number of blocks that the file of the basket, occupies. 273 00:18:38,633 --> 00:18:45,600 Another non-obvious point is that, for the algorithms we consider, 274 00:18:45,600 --> 00:18:48,920 the limiting factor is usually how much main memory is available. 275 00:18:50,060 --> 00:18:55,100 So for example, it is common to have a pass where the file of baskets is red, and 276 00:18:55,100 --> 00:18:57,780 as we read the baskets, we count. 277 00:18:57,780 --> 00:19:00,310 All the pairs of items contained within that basket. 278 00:19:04,153 --> 00:19:07,110 We need to have a place in main memory to count each pair. 279 00:19:08,470 --> 00:19:12,040 So that means at least a few bytes per pair. 280 00:19:12,040 --> 00:19:14,570 If we have 100,000 items then there are 5 billion pairs. 281 00:19:15,800 --> 00:19:19,490 At 4 bytes per count that's 20 gigs of main memory. 282 00:19:19,490 --> 00:19:20,600 Okay we can do that. 283 00:19:20,600 --> 00:19:22,230 Buy a little extra for our machine. 284 00:19:22,230 --> 00:19:24,820 Or use several processors. 285 00:19:24,820 --> 00:19:26,890 But if we have a million items. 286 00:19:26,890 --> 00:19:28,690 That's a half a trillion pairs. 287 00:19:28,690 --> 00:19:31,450 And we can't really manage all the counts in main memory. 288 00:19:34,080 --> 00:19:37,540 And if it isn't obvious using disks to store the counts. 289 00:19:37,540 --> 00:19:42,650 WIll not work, the counts have, we have to increment are essentially random, 290 00:19:42,650 --> 00:19:46,750 so if even half the counts need to be on disk at any time, 291 00:19:46,750 --> 00:19:50,970 we have a 50% chance of needing two disk IOs with every increment. 292 00:19:56,274 --> 00:19:59,349 I'm going to concentrate on how you find frequent pairs of items. 293 00:20:02,470 --> 00:20:05,410 Often finding frequent items, that is sets of size one or, 294 00:20:05,410 --> 00:20:09,510 or, s, or singletons, is not too hard because there aren't so many items that we 295 00:20:09,510 --> 00:20:13,620 can't count them all in main memory as we make a pass through the baskets. 296 00:20:13,620 --> 00:20:15,040 But it's also common for 297 00:20:15,040 --> 00:20:19,600 the pairs to be too large to count them all in main memory. 298 00:20:19,600 --> 00:20:23,900 You might think that there are even more triples of items than there are pairs. 299 00:20:23,900 --> 00:20:25,250 You'd be right. 300 00:20:25,250 --> 00:20:28,500 However, the algorithms we'll cover exploit the fact that once you have 301 00:20:28,500 --> 00:20:32,520 the frequent pairs, you can eliminate most of the triples and not count them at all. 302 00:20:35,080 --> 00:20:38,930 One might ask why there shouldn't be lots and lots of frequent triples. 303 00:20:38,930 --> 00:20:42,030 The reason is that if we're going to bother to do a frequent item 304 00:20:42,030 --> 00:20:43,320 sets analysis,. 305 00:20:43,320 --> 00:20:47,100 We don't want so many answers that we can't even think about them all. 306 00:20:47,100 --> 00:20:51,390 As a result it is normal to set the support threshold high enough that it 307 00:20:51,390 --> 00:20:55,050 is hard for a large item set to be sufficiently frequent. 308 00:20:55,050 --> 00:20:57,850 As a result most of the sets that we meet that will meet 309 00:20:57,850 --> 00:21:00,939 the threshold will be singletons or doubletons. 310 00:21:03,760 --> 00:21:06,430 The bottom line is that we're going to concentrate on algorithms for 311 00:21:06,430 --> 00:21:07,900 finding pairs. 312 00:21:07,900 --> 00:21:11,190 The extension to larger item sets will be given once and 313 00:21:11,190 --> 00:21:13,790 can be used with any of the algorithms we discussed. 314 00:21:17,890 --> 00:21:20,740 Let's start by talking about what we might call the Naive Algorithm. 315 00:21:22,110 --> 00:21:26,930 We want to read the baskets in some number of passes so why not use just one pass and 316 00:21:26,930 --> 00:21:28,640 count all the pairs in main memory? 317 00:21:30,810 --> 00:21:31,770 We mention this briefly. 318 00:21:31,770 --> 00:21:35,320 But just to make sure we understand what happen, happens when we process a basket. 319 00:21:35,320 --> 00:21:39,290 We use a double loop to generate all the pairs of items in the basket. 320 00:21:39,290 --> 00:21:41,360 And for each pair we add one to it's count. 321 00:21:44,190 --> 00:21:47,560 This algorithm actually works provided there's enough space in main 322 00:21:47,560 --> 00:21:50,720 memory to count all the pairs of items. 323 00:21:50,720 --> 00:21:54,770 The number of bytes we need is roughly the square of the number of items in our data. 324 00:21:54,770 --> 00:21:59,070 That is, the number of pairs of items is the number of items choose two or 325 00:21:59,070 --> 00:22:02,390 approximately half the square of the number items. 326 00:22:02,390 --> 00:22:04,500 And if we can count each pair in two bytes, 327 00:22:04,500 --> 00:22:09,140 which is possible if the threshold is no more than two to the sixteenth 328 00:22:09,140 --> 00:22:12,550 then the number of bytes we need is exactly the square of the number of items. 329 00:22:14,520 --> 00:22:17,650 If we need four byte integers to count then we need twice that square. 330 00:22:20,800 --> 00:22:24,400 And just to recall, the typical number of items if you're Wal-Mart. 331 00:22:24,400 --> 00:22:28,600 The number of items is about 100,000, so you might be okay. 332 00:22:28,600 --> 00:22:31,690 But if you're dealing with items as webpages, then you're definitely not okay. 333 00:22:35,510 --> 00:22:38,660 Before we proceed, I need to talk a little more detail about how you 334 00:22:38,660 --> 00:22:41,169 organize main memory to do the counting of pairs. 335 00:22:44,300 --> 00:22:47,990 There are actually two approaches, and which is better depends on whether it 336 00:22:47,990 --> 00:22:52,390 is likely or unlikely that two given items ever appear together in a basket. 337 00:22:56,060 --> 00:22:58,550 One approach is to maintain a triangular matrix. 338 00:22:58,550 --> 00:23:00,560 I'll, I'll talk about this on the next slide, but 339 00:23:00,560 --> 00:23:02,848 the idea is to maintain a two dimensional ray. 340 00:23:02,848 --> 00:23:08,620 Where A of I and 341 00:23:08,620 --> 00:23:13,340 J is only there if I is strictly less than J. 342 00:23:13,340 --> 00:23:22,800 The second approach is to keep records with three components, 343 00:23:22,800 --> 00:23:29,190 I, J, and C, meaning that the count for the set of items I and J is currently C. 344 00:23:29,190 --> 00:23:32,650 You organize this collection of records by indexing on i and j. 345 00:23:32,650 --> 00:23:36,680 So given a pair i,j, you're going to quickly find its record and 346 00:23:36,680 --> 00:23:40,130 increment its count, or just read its count, if that's what you want. 347 00:23:42,260 --> 00:23:48,980 The triangular matrix approach, requires four bytes per pair of items. 348 00:23:51,670 --> 00:23:55,680 I'm going to assume from here on that integers require four bytes, even though, 349 00:23:55,680 --> 00:23:58,930 if as we just mentioned, it is okay to keep them small, and 350 00:23:58,930 --> 00:24:00,080 fewer bytes could be okay. 351 00:24:01,230 --> 00:24:04,610 It is even possible in some circumstances there can be more than four bytes but 352 00:24:04,610 --> 00:24:06,720 I'm not going to worry about that case either. 353 00:24:09,510 --> 00:24:12,920 On the other hand, if we keep a table of triples and 354 00:24:12,920 --> 00:24:18,880 we need 12 bytes per pair, four each for i, j, and c. 355 00:24:18,880 --> 00:24:23,100 But the advantage is that a pair only needs a record that appears in at 356 00:24:23,100 --> 00:24:24,540 least one basket. 357 00:24:24,540 --> 00:24:26,310 As a result the space requirement for 358 00:24:26,310 --> 00:24:32,210 the tabular approach is 12 bytes per existing pair, but not per possible pair. 359 00:24:36,730 --> 00:24:38,350 Here's a picture of the difference. 360 00:24:38,350 --> 00:24:43,209 For the triangular matrix, you need four bytes per unit area of the triangle. 361 00:24:45,030 --> 00:24:49,420 For the tabular method, you need 12 bytes times the fraction of 362 00:24:49,420 --> 00:24:52,400 the area that represents pairs actually present. 363 00:24:52,400 --> 00:24:56,990 So if more than one-third of possible pairs are present in at least one basket, 364 00:24:56,990 --> 00:24:59,080 you prefer the triangular matrix. 365 00:24:59,080 --> 00:25:03,960 If you expect fewer than a third of the possible pairs to be present in the data, 366 00:25:03,960 --> 00:25:05,700 then you should go for the tabular approach. 367 00:25:09,308 --> 00:25:13,094 Now let's look at how we construct a triangular matrix given the, 368 00:25:13,094 --> 00:25:17,770 given that this structure is not exactly built into most programming languages. 369 00:25:18,860 --> 00:25:22,420 First of all we'll assume the items are represented by consecutive integers 370 00:25:22,420 --> 00:25:23,209 starting at one. 371 00:25:25,776 --> 00:25:28,700 If items in your data are represented by their names, or 372 00:25:28,700 --> 00:25:32,373 by integers that are not consecutive, then you need to build a table to 373 00:25:32,373 --> 00:25:35,650 translate from an items name in the data to its integer. 374 00:25:35,650 --> 00:25:39,340 A hash table whose key is the original name of the item in 375 00:25:39,340 --> 00:25:40,820 the data will do just fine. 376 00:25:43,350 --> 00:25:45,340 Okay. We're counting sets of two items, so 377 00:25:45,340 --> 00:25:47,750 we can think of each set as an ordered list of length two. 378 00:25:47,750 --> 00:25:51,140 In other words, we'll count all i and js such that i is less than j. 379 00:25:51,140 --> 00:25:57,620 I want to use an order for the pairs that look like this. 380 00:25:59,550 --> 00:26:00,940 If there are n items in total. 381 00:26:02,610 --> 00:26:06,330 Then first come the n minus one pairs whose smaller member is one. 382 00:26:06,330 --> 00:26:08,230 That's these. 383 00:26:11,050 --> 00:26:14,320 These pairs are in order of their larger member. 384 00:26:14,320 --> 00:26:17,860 Then come the n minus two pairs whose smaller member is two. 385 00:26:21,440 --> 00:26:23,990 Again, these are ordered by the larger member. 386 00:26:23,990 --> 00:26:27,890 And the n minus 3 pairs with 3 as the smaller and so on. 387 00:26:27,890 --> 00:26:33,140 What we really have is a one dimensional ray and 388 00:26:33,140 --> 00:26:36,630 we need a function that takes i and j, where i is less than j. 389 00:26:36,630 --> 00:26:39,790 And turns it into the into the position in the array belonging to this pair. 390 00:26:40,900 --> 00:26:43,010 Here's the magic formula. 391 00:26:43,010 --> 00:26:47,640 I'll let you figure out why it works, but for example, 392 00:26:47,640 --> 00:26:53,504 if n equals 10, let's look at the pair, (3,5). 393 00:26:55,750 --> 00:27:02,390 I claim it is at postion two, that's i minus 1, i is 3 of course, 394 00:27:02,390 --> 00:27:06,960 times 10, that's n, minus i over 2, 395 00:27:06,960 --> 00:27:11,200 that's three halves, plus 5, that's j. 396 00:27:11,200 --> 00:27:13,034 Remember j is 5. 397 00:27:15,560 --> 00:27:17,470 And then minus 3 which is i. 398 00:27:18,530 --> 00:27:19,665 You work that out it's 19. 399 00:27:19,665 --> 00:27:20,165 'Kay? 400 00:27:21,610 --> 00:27:25,530 That makes sense because there are nine pairs ahead of the, the pair 3, 401 00:27:25,530 --> 00:27:27,990 5 that have a 1. 402 00:27:27,990 --> 00:27:30,870 As the lowest the lowest member of the pair. 403 00:27:30,870 --> 00:27:35,740 Another eight pairs that have Two as the lowest and 404 00:27:35,740 --> 00:27:39,340 then there's one more pair three four that comes ahead of three five. 405 00:27:39,340 --> 00:27:48,520 The total number of pairs that are represented 406 00:27:48,520 --> 00:27:53,020 as N choose two or about N squared over two and we used four bytes per pair. 407 00:27:54,190 --> 00:27:56,830 So the number of bytes needed is about 2n squared. 408 00:28:01,339 --> 00:28:05,223 If we use a table of existing pairs, then we need space 12p for 409 00:28:05,223 --> 00:28:09,340 the triples, where p is the number of pairs that occur in the data. 410 00:28:13,708 --> 00:28:20,557 As we mentioned, this amount of space is less than that of the triangular 411 00:28:20,557 --> 00:28:26,282 matrix as long as p is at most one third of the possible pairs, 412 00:28:26,282 --> 00:28:30,240 or about p less than n squared over six 413 00:28:32,985 --> 00:28:38,214 However, for this method, we also need an index of the pairs of integers so 414 00:28:38,214 --> 00:28:42,180 that we can quickly find the record for that pair. 415 00:28:42,180 --> 00:28:46,260 This structure also requires space depending on how we implement it. 416 00:28:46,260 --> 00:28:50,390 For example, we might implement the hash table in which case we 417 00:28:50,390 --> 00:28:52,230 need pointers to link. 418 00:28:52,230 --> 00:28:54,210 A list for the, for each bucket. 419 00:28:54,210 --> 00:29:01,360 So let's say here's the hash table, here's a pointer to the first elements. 420 00:29:01,360 --> 00:29:04,260 We'll have an i, a j, and a c. 421 00:29:04,260 --> 00:29:06,990 And then a pointer to the next element. 422 00:29:09,010 --> 00:29:09,580 And so on. 423 00:29:12,220 --> 00:29:15,551 That would add another four bytes per pair. 424 00:29:15,551 --> 00:29:24,160 In particular not counted in the 12p is all the space for the, the bucket headers. 425 00:29:24,160 --> 00:29:25,880 That's probably not too much. 426 00:29:25,880 --> 00:29:30,690 But then another integer at least for each of the links. 427 00:29:30,690 --> 00:29:31,470 That. 428 00:29:31,470 --> 00:29:40,296 Is going to lead to a cost of about 16 p, rather than the the 12 p. 429 00:29:40,296 --> 00:29:43,563 and, and in addition again is the, the cost for 430 00:29:43,563 --> 00:29:47,415 the bucket headers which is probably negligible.