1 00:00:00,480 --> 00:00:03,750 We're now going to take up a class of problems where we're given a large 2 00:00:03,750 --> 00:00:05,640 collection of sets, millions or 3 00:00:05,640 --> 00:00:09,280 billions perhaps, and we are asked to find those sets that are similar. 4 00:00:09,280 --> 00:00:14,730 The notion of similarity is quite specific and it's called Jaccard Similarity. 5 00:00:15,860 --> 00:00:20,010 We'll learn this concept soon, but the idea is roughly, that the larger 6 00:00:20,010 --> 00:00:24,450 the fraction of elements the two sets have in common the more similar they are. 7 00:00:26,770 --> 00:00:28,910 There is a fundamental problem of scale. 8 00:00:28,910 --> 00:00:33,150 If we have even a million sets not a large number compared with the number of 9 00:00:33,150 --> 00:00:37,870 web pages or Amazon users, the number of pairs of sets is half a trillion. 10 00:00:39,220 --> 00:00:43,480 We don't have the resources to compare them all, so we need some magic defor, 11 00:00:43,480 --> 00:00:48,160 focus us on the pairs that are likely to be highly similar, 12 00:00:48,160 --> 00:00:50,590 never looking at the vast majority of pairs. 13 00:00:52,390 --> 00:00:56,890 When you learned about hashing you're, it probably seemed like a bit of magic. 14 00:00:56,890 --> 00:01:00,090 You have a large set of keys, and when you want to find some key k, 15 00:01:00,090 --> 00:01:03,120 you go right to it without having to look very far at all. 16 00:01:05,140 --> 00:01:06,540 The technique we're going to learn, 17 00:01:06,540 --> 00:01:09,990 locality sensitive hashing, is another bit of magic. 18 00:01:11,090 --> 00:01:14,080 Here we are pointed right at the similar pairs without having to 19 00:01:14,080 --> 00:01:16,500 wade through the morass of all pairs. 20 00:01:16,500 --> 00:01:19,980 We'll begin by looking at some applications where finding similar sets is 21 00:01:19,980 --> 00:01:21,690 very useful. 22 00:01:21,690 --> 00:01:25,730 We then are going to focus initially on finding similar documents, 23 00:01:25,730 --> 00:01:29,610 meaning that they have a substantial amount of text in common. 24 00:01:29,610 --> 00:01:32,820 For this problem we first study shingling, which is a way to convert 25 00:01:32,820 --> 00:01:38,980 the informal notion of similar documents into a formal test for similarity of sets. 26 00:01:38,980 --> 00:01:42,190 Then we learn the remarkable technique called min hashing, 27 00:01:42,190 --> 00:01:46,500 which allows us to replace a large set by a much smaller list of values. 28 00:01:46,500 --> 00:01:49,930 The magic of min hashing is that the similarity of the small lists, 29 00:01:49,930 --> 00:01:53,690 called signatures, predicts the similarity of the whole sets. 30 00:01:55,010 --> 00:01:59,090 Finally, we take up the locality sensitive hashing technique itself and 31 00:01:59,090 --> 00:02:00,733 see how to find similar sets or 32 00:02:00,733 --> 00:02:05,800 similar documents without doing anything that involves searching all pairs. 33 00:02:05,800 --> 00:02:08,920 To begin, let's look at some of the interesting data mining problems that 34 00:02:08,920 --> 00:02:11,300 fit the pattern of mining for similar sets. 35 00:02:12,880 --> 00:02:16,720 For example, we can view web pages as the set of words they contain. 36 00:02:16,720 --> 00:02:18,840 If two pages have similar sets of words, 37 00:02:18,840 --> 00:02:21,200 we might expect them to be about the same topic. 38 00:02:23,280 --> 00:02:28,120 For another example, imagine a matrix of Netflix users where the rows correspond to 39 00:02:28,120 --> 00:02:30,400 the users, and the columns to the movies. 40 00:02:31,400 --> 00:02:32,900 The entry for a given user and 41 00:02:32,900 --> 00:02:37,240 movie is the rating that the user has given the movie, blank if no rating. 42 00:02:38,360 --> 00:02:41,400 We might see a user as the set of movies they have rated four or 43 00:02:41,400 --> 00:02:42,910 five, that is movies they like. 44 00:02:44,320 --> 00:02:49,240 Two users who have similar sets of liked movies probably have the same tastes, and 45 00:02:49,240 --> 00:02:51,910 Netflix can use the movies one user said they 46 00:02:51,910 --> 00:02:54,140 liked to recommend movies to the other. 47 00:02:55,200 --> 00:02:57,500 We can use the same idea backwards. 48 00:02:57,500 --> 00:03:01,090 Where we think of a movie as the set of users who like that movie. 49 00:03:01,090 --> 00:03:04,020 Movies with similar sets of users can be expected to 50 00:03:04,020 --> 00:03:05,850 belong to the same genre of movie. 51 00:03:09,330 --> 00:03:13,030 People create records of data about themselves at many different sites, 52 00:03:13,030 --> 00:03:15,220 Google, Amazon, Facebook and so on. 53 00:03:16,710 --> 00:03:20,780 We may want to figure out when two records refer to the same individual, and 54 00:03:20,780 --> 00:03:24,600 this need gives rise to the problem called entity resolution, 55 00:03:24,600 --> 00:03:28,550 determining the set of records that refer to the same individual. 56 00:03:28,550 --> 00:03:31,290 To see the problem, many sites will ask for phone number. 57 00:03:33,030 --> 00:03:36,900 But you might give your land line at one site, your cell phone number at another, 58 00:03:36,900 --> 00:03:41,109 not give a number at all at a third site, and mistype your number at a fourth. 59 00:03:42,360 --> 00:03:44,990 However, we can often wade through the errors and 60 00:03:44,990 --> 00:03:49,970 ambiguities by thinking of a record as a set of attribute value pairs. 61 00:03:49,970 --> 00:03:58,110 Pairs like, oh, phone is 555, I don't know, whatever okay? 62 00:03:58,110 --> 00:04:00,820 Records with similar even if not identical sets of 63 00:04:00,820 --> 00:04:06,080 attribute value pairs may well represent the same individual, and 64 00:04:06,080 --> 00:04:08,790 these records can be merged to combine their information. 65 00:04:10,020 --> 00:04:13,840 We're going to focus on a particular important application, 66 00:04:13,840 --> 00:04:18,160 finding lexically similar documents in a large collection of docs such as the web. 67 00:04:19,750 --> 00:04:22,410 Note we are not talking about docs on a similar topic. 68 00:04:22,410 --> 00:04:25,100 We want them to have sequences of characters in common. 69 00:04:26,750 --> 00:04:29,440 This question has a variety of applications. 70 00:04:29,440 --> 00:04:32,680 For example, the techniques we’re going to learn were used to find mirror 71 00:04:32,680 --> 00:04:34,360 pages on the web. 72 00:04:34,360 --> 00:04:37,910 Mirror pages are typically almost the same, but they will differ, for example, 73 00:04:37,910 --> 00:04:42,970 in the information about the host site for the page and links to the other mirrors. 74 00:04:42,970 --> 00:04:45,750 Search engines use a technique like the one we’ll learn so 75 00:04:45,750 --> 00:04:50,070 they don’t show more than one of a set of mirror sites. 76 00:04:50,070 --> 00:04:53,030 Another application of finding lexically similar documents is to 77 00:04:53,030 --> 00:04:54,960 search for plagiarisms. 78 00:04:54,960 --> 00:04:58,060 For example, spammers will take your webpage, give it a new URL, 79 00:04:58,060 --> 00:05:00,590 and place ads around it. 80 00:05:00,590 --> 00:05:04,740 The plagiarizer may be clever, taking only a part of the plagiarized document, 81 00:05:04,740 --> 00:05:08,250 reordering pieces, perhaps changing a word here and there. 82 00:05:08,250 --> 00:05:11,070 We still want to be able to find such pairs of documents in 83 00:05:11,070 --> 00:05:16,200 a collection as large as the web without having to compare all pairs of documents. 84 00:05:16,200 --> 00:05:17,320 It can be done. 85 00:05:17,320 --> 00:05:19,250 In fact, it's much easier than it looks. 86 00:05:21,460 --> 00:05:24,510 And another application concerns sites like Google News that 87 00:05:24,510 --> 00:05:26,300 aggregate new stories. 88 00:05:26,300 --> 00:05:28,760 An article may be written by the Associated Press and 89 00:05:28,760 --> 00:05:32,090 distributed to thousands of newspapers and online news sites. 90 00:05:33,200 --> 00:05:36,270 Each will make modifications, perhaps truncating the story, 91 00:05:36,270 --> 00:05:38,790 surrounding it with ads, and so on. 92 00:05:38,790 --> 00:05:41,690 It's important for an aggregator to realize that the two web 93 00:05:41,690 --> 00:05:44,680 pages are really telling the same story because they came from 94 00:05:44,680 --> 00:05:48,540 the same original even if they have been significantly modified. 95 00:05:50,240 --> 00:05:51,980 As we suggested in the introduction, 96 00:05:51,980 --> 00:05:54,730 we're going to learn three important new techniques. 97 00:05:57,830 --> 00:06:00,365 Shingling is how we convert documents to sets so 98 00:06:00,365 --> 00:06:03,600 that documents that have a lot of text in common will be converted to 99 00:06:03,600 --> 00:06:07,420 sets that are similar in the sense that they have a lot of members in common. 100 00:06:09,450 --> 00:06:11,670 Then we'll learn about minhashing, 101 00:06:11,670 --> 00:06:14,780 which is how we convert sets to short signatures. 102 00:06:14,780 --> 00:06:18,400 The important property is that we can look at the signatures of two sets and tell 103 00:06:18,400 --> 00:06:22,870 approximately how similar are the sets that we obtained by the shingling process. 104 00:06:24,040 --> 00:06:25,130 And last but not least, 105 00:06:25,130 --> 00:06:27,980 we'll learn the technique called Locality-sensitive hashing or 106 00:06:27,980 --> 00:06:31,440 LSH that let's us avoid looking at most of the pairs of 107 00:06:31,440 --> 00:06:34,170 signatures that do not represent similar sets. 108 00:06:37,770 --> 00:06:41,220 Here's an outline of how we'd process documents to find those that 109 00:06:41,220 --> 00:06:44,070 are similar without comparing all pairs. 110 00:06:44,070 --> 00:06:47,530 At the outset, I want to emphasize that there can be both false positives and 111 00:06:47,530 --> 00:06:48,520 false negatives. 112 00:06:49,590 --> 00:06:53,480 That is, the algorithms we use can sometimes fail to find a pair of 113 00:06:53,480 --> 00:06:56,350 documents that we would regard as similar. 114 00:06:56,350 --> 00:06:58,440 That's a false negative. 115 00:06:58,440 --> 00:07:01,890 We can also, if we're not careful to check the details of the document, 116 00:07:01,890 --> 00:07:04,310 sometimes have false positives. 117 00:07:04,310 --> 00:07:08,450 Pairs of documents we declared to be similar, but they really aren't. 118 00:07:08,450 --> 00:07:11,760 However, by carefully choosing the parameters involved, we can 119 00:07:11,760 --> 00:07:17,655 make the probability of false positives and negatives be as small as, as we like. 120 00:07:17,655 --> 00:07:21,365 Okay so, we start by shingling the document. 121 00:07:21,365 --> 00:07:27,070 Okay, that is we replace the document by the set of strings of some chosen length, 122 00:07:27,070 --> 00:07:28,930 k, that appear in the document. 123 00:07:30,480 --> 00:07:33,550 That's how we convert documents to sets. 124 00:07:33,550 --> 00:07:35,100 We then construct signatures for 125 00:07:35,100 --> 00:07:39,460 the sets of single, shingles using the technique called minhashing. 126 00:07:39,460 --> 00:07:43,110 The result of minhashing a set is a short vector of integers. 127 00:07:43,110 --> 00:07:43,930 The key property, 128 00:07:43,930 --> 00:07:48,010 which we'll prove, is that the number of components in which the, two of 129 00:07:48,010 --> 00:07:53,470 these vectors agree is the expected value of the similarity of the underlying sets. 130 00:07:53,470 --> 00:07:57,420 Incidentally, the reason we want to replace sets by their signatures is that 131 00:07:57,420 --> 00:07:59,460 the signatures take up much less space. 132 00:07:59,460 --> 00:08:03,030 If we're dealing with a large set of documents, we'd like to be able to work in 133 00:08:03,030 --> 00:08:07,540 main memory rather than with disc for efficiency, and reducing the space of 134 00:08:07,540 --> 00:08:10,850 the representations makes it more likely that we can work in main memory. 135 00:08:12,920 --> 00:08:16,360 But it seems we still need to compare all pairs of signatures, and 136 00:08:16,360 --> 00:08:19,580 that takes time that is quadratic in the number of documents. 137 00:08:19,580 --> 00:08:23,490 As we mentioned, even a million documents leads to half a trillion pairs of 138 00:08:23,490 --> 00:08:26,780 signatures to compare, and that is too much. 139 00:08:26,780 --> 00:08:29,660 So that's where locality sensitive hashing comes in. 140 00:08:29,660 --> 00:08:33,440 We do some magic, which we'll explain soon, that allows us to look at 141 00:08:33,440 --> 00:08:38,700 a small subset of the possible pairs, and test only those pairs with similarity. 142 00:08:38,700 --> 00:08:42,530 By doing so, we get almost all the pairs that are truly similar, and 143 00:08:42,530 --> 00:08:45,199 the total time spent is much less than quadratic. 144 00:08:46,540 --> 00:08:49,590 So lets begin the story by finding exactly what shingles are. 145 00:08:52,470 --> 00:08:56,640 For any integer k, a k-shingle is sometimes called a k-gram, 146 00:08:56,640 --> 00:08:59,370 is a sequence of k consecutive characters in the document. 147 00:08:59,370 --> 00:09:02,430 The blanks that separate the words of 148 00:09:02,430 --> 00:09:05,140 the document are normally considered characters. 149 00:09:05,140 --> 00:09:09,790 If the document involves tags such as an HTML document then the tags may 150 00:09:09,790 --> 00:09:12,580 also be considered characters or they can be ignored. 151 00:09:14,250 --> 00:09:19,240 So here's an example of a little document consisting of the five characters abcab. 152 00:09:21,400 --> 00:09:22,896 We'll use k equals two for 153 00:09:22,896 --> 00:09:26,772 this little example, although in practice you want to use a k that is 154 00:09:26,772 --> 00:09:31,330 large enough that most sequences of k characters do not appear in the document. 155 00:09:31,330 --> 00:09:36,321 A k in the range five to ten is used, 156 00:09:36,321 --> 00:09:42,690 generally used but the two shingles for 157 00:09:42,690 --> 00:09:49,059 our little document are ab, which is that, 158 00:09:49,059 --> 00:09:54,590 then bc, then ca, and then ab again. 159 00:09:58,280 --> 00:10:02,682 Since we're constructing a set, 160 00:10:02,682 --> 00:10:09,056 we include the repeated two shingle ab only once, 161 00:10:09,056 --> 00:10:14,824 and thus our document abcab is represented by 162 00:10:14,824 --> 00:10:19,260 the set of shingles ab, bc and ca. 163 00:10:19,260 --> 00:10:22,270 We need to assure ourselves that replacing a document by 164 00:10:22,270 --> 00:10:26,960 its shingles still lets us detect pairs of documents that are intuitively similar. 165 00:10:28,658 --> 00:10:31,995 In fact, similarity of shingle sets captures many of the kinds of 166 00:10:31,995 --> 00:10:35,770 document changes that we would regard as keeping the documents similar. 167 00:10:39,468 --> 00:10:44,334 For example, if we're using k-shingles and we change one word, only the k-shingles to 168 00:10:44,334 --> 00:10:48,700 the left and right of the word as well as shingles within the word can be effected. 169 00:10:50,350 --> 00:10:54,180 And we can re-order entire paragraphs without affecting any shingles except 170 00:10:54,180 --> 00:10:58,130 the shingles that cross the boundaries between the paragraph we moved and 171 00:10:58,130 --> 00:11:01,930 the paragraphs just before and after in both the new and old positions. 172 00:11:05,240 --> 00:11:07,750 For example, suppose we use k equals three, and 173 00:11:07,750 --> 00:11:12,950 we correctly change the which in the sentence to that, 174 00:11:12,950 --> 00:11:16,630 the only shingles that can be affected are the ones that begin at most two 175 00:11:16,630 --> 00:11:22,390 characters before which and end at most two characters after which. 176 00:11:22,390 --> 00:11:28,120 Okay, these are g blank w, blank wh, 177 00:11:28,120 --> 00:11:33,270 and so on, up to h blank c. 178 00:11:33,270 --> 00:11:36,820 A total of seven shingles. 179 00:11:38,080 --> 00:11:40,530 These are replaced by six different shingles. 180 00:11:42,176 --> 00:11:47,346 G blank t, t is it blank th, 181 00:11:47,346 --> 00:11:51,190 and so on up to t blank c. 182 00:11:53,100 --> 00:11:57,900 however, all shingles other than these remain the same in the two sentences. 183 00:11:59,330 --> 00:12:02,660 Because documents tend to consist mostly of the 26 letters, and 184 00:12:02,660 --> 00:12:06,430 we want to make sure that most shingles do not appear in a document, 185 00:12:06,430 --> 00:12:11,020 we are often forced to use a large value of k, like k equals ten. 186 00:12:11,020 --> 00:12:15,927 But the number of different strings of length ten that will actually appear in 187 00:12:15,927 --> 00:12:19,778 any document is much smaller than 256 to the tenth power or 188 00:12:19,778 --> 00:12:21,682 even 26 to the tenth power. 189 00:12:25,944 --> 00:12:29,285 Thus, it common to compress shingles to save space while still 190 00:12:29,285 --> 00:12:34,040 preserving the property that most shingles do not appear in a given document. 191 00:12:34,040 --> 00:12:39,730 For example, we can hash strings of length ten to 32 bits or four bytes, thus 192 00:12:39,730 --> 00:12:47,110 saving 60% of the space that are needed to shore, to store the shingle sets. 193 00:12:47,110 --> 00:12:50,050 The result of hashing shingles is often called a token. 194 00:12:51,255 --> 00:12:53,900 Thus, we can construct for a document the set of it's tokens. 195 00:12:53,900 --> 00:12:58,390 We construct the shingle set and then hash each shingle to get a token. 196 00:12:58,390 --> 00:13:04,380 Since documents are much shorter than two to the 32nd power byte, 197 00:13:04,380 --> 00:13:07,860 we still can be sure that a document is only a small fraction of 198 00:13:07,860 --> 00:13:09,770 the possible tokens in it's sets. 199 00:13:13,310 --> 00:13:17,080 There's a small chance of a collision where two shingles hashed to 200 00:13:17,080 --> 00:13:21,650 the same token, but that could make two documents appear to have shingles in 201 00:13:21,650 --> 00:13:24,530 common when in fact they have different shingles. 202 00:13:24,530 --> 00:13:28,090 But such an an occurrence will be quite rare. 203 00:13:28,090 --> 00:13:32,350 In what follows we'll continue to refer to shingles sets when these sets 204 00:13:32,350 --> 00:13:35,100 might consist of token rather than the raw shingles