1 00:00:00,740 --> 00:00:04,890 We're now going to forget whether the sets we deal with come from single documents or 2 00:00:04,890 --> 00:00:08,200 any other source and concentrate on the sets themselves. 3 00:00:08,200 --> 00:00:12,030 We'll learn the formal definition of similarity that is commonly used for sets. 4 00:00:12,030 --> 00:00:14,200 This notion is called Jaccard similarity. 5 00:00:15,760 --> 00:00:16,510 We'll then learn how to 6 00:00:16,510 --> 00:00:19,380 construct signatures from sets using the menhashing technique. 7 00:00:21,020 --> 00:00:23,640 And will prove the strong relationship between the similarity of 8 00:00:23,640 --> 00:00:29,020 the signatures and the sets they represent. 9 00:00:29,020 --> 00:00:33,460 Let C1 and C2 be two sets, their Jaccard similarity is the size of 10 00:00:33,460 --> 00:00:38,180 the intersection of these two sets, divided by the size of the union. 11 00:00:38,180 --> 00:00:41,830 We'll use Sim as the function representing the Jaccard similarity. 12 00:00:42,930 --> 00:00:46,230 For example, these two circles represent sets. 13 00:00:46,230 --> 00:00:48,440 There are three elements in common to both sets. 14 00:00:51,480 --> 00:00:54,250 So, the size of their intersection is three. 15 00:00:54,250 --> 00:00:57,290 And there are eight elements in the union, so the size of their union is eight. 16 00:00:57,290 --> 00:01:01,360 The Jaccard similarity of these sets is the ratio of the sizes of 17 00:01:01,360 --> 00:01:05,750 their intersection and un, and union or three eighths in this example. 18 00:01:07,140 --> 00:01:10,410 We're going to be dealing with large collections of sets and 19 00:01:10,410 --> 00:01:15,200 it is useful to think of these collections as represented by a single Boolean matrix, 20 00:01:15,200 --> 00:01:17,890 even if the collection is not likely to be stored that way. 21 00:01:19,160 --> 00:01:22,050 First, we assume that there's a universal set, 22 00:01:22,050 --> 00:01:24,420 from which the elements of all sets are drawn. 23 00:01:24,420 --> 00:01:28,430 For example, if the sets come from k-shingling documents, 24 00:01:28,430 --> 00:01:32,680 then the universal set is the set of all possible sequences of K characters or 25 00:01:32,680 --> 00:01:36,160 the set of all tokens if we hash the shingles. 26 00:01:36,160 --> 00:01:41,270 Each element in the universal set is represented by a row of the matrix. 27 00:01:41,270 --> 00:01:45,600 And each set in the collection is represented by a column of the matrix. 28 00:01:47,670 --> 00:01:51,310 The matrix has one in the row for element E and the column for 29 00:01:51,310 --> 00:01:55,390 S, if and only if E is a member of S. 30 00:01:55,390 --> 00:01:56,900 Otherwise that entry is zero. 31 00:01:58,460 --> 00:02:03,040 The column corresponding to a set as the characteristic vector of the set S. 32 00:02:03,040 --> 00:02:07,470 The vector with ones only in the positions that correspond to the members of S. 33 00:02:07,470 --> 00:02:11,210 We shall often talk about the Jaccard similarity of 2 columns. 34 00:02:11,210 --> 00:02:14,330 From each column, form the set represented by the column, 35 00:02:14,330 --> 00:02:17,300 except consisting of the rows where the column has 1. 36 00:02:17,300 --> 00:02:20,950 Then the Jaccard similarity of the two columns is the Jaccard similarity of 37 00:02:20,950 --> 00:02:21,990 the sets they represent. 38 00:02:24,410 --> 00:02:28,380 It is important to note that in typical applications, the matrix is very sparse. 39 00:02:28,380 --> 00:02:30,610 It has many more zeros than ones. 40 00:02:30,610 --> 00:02:34,110 For example, we choose k for k shingling, so 41 00:02:34,110 --> 00:02:37,660 that documents have relatively few of the possible shingles. 42 00:02:37,660 --> 00:02:40,660 We translate into columns having many more zeroes than ones. 43 00:02:41,880 --> 00:02:45,320 For another example, suppose the matrix represents the books bought by 44 00:02:45,320 --> 00:02:49,595 Amazon customers, rows are the books and columns are the customers. 45 00:02:49,595 --> 00:02:53,510 And customers are similar if they buy many of the same books. 46 00:02:53,510 --> 00:02:57,380 Typical customer buys only a tiny fraction of the books Amazon sells. 47 00:02:57,380 --> 00:03:00,219 So again, we would expect our matrix to be very sparse. 48 00:03:01,810 --> 00:03:03,890 Here are two columns, C1 and C2. 49 00:03:03,890 --> 00:03:05,080 They're not sparse, 50 00:03:05,080 --> 00:03:09,120 because it's hard to do small examples when most entries are zero. 51 00:03:09,120 --> 00:03:11,960 However, the calculation of their Jaccard similarity is simple. 52 00:03:16,360 --> 00:03:18,320 There are two rows where they both have one, so 53 00:03:18,320 --> 00:03:21,370 the intersection of the sets they represent is of size two. 54 00:03:22,570 --> 00:03:26,470 And there are five rows where at least one of the columns has one, 55 00:03:26,470 --> 00:03:30,010 so the size of the union of the represented sets is five. 56 00:03:30,010 --> 00:03:32,516 Thus the Jacquard similarity is two fifths of 40%. 57 00:03:32,516 --> 00:03:36,510 In general, you can compute the similarity of two columns, 58 00:03:36,510 --> 00:03:39,310 by counting the number of rows where both have one, and 59 00:03:39,310 --> 00:03:42,250 dividing by the number of rows in which one or both have one. 60 00:03:46,470 --> 00:03:50,010 Our goal is to describe how min hashing of sets or 61 00:03:50,010 --> 00:03:54,140 matrix column works, and to show that we can deduce the similarity of the sets or 62 00:03:54,140 --> 00:03:57,250 columns by looking at the signatures that result from in hashing. 63 00:03:59,540 --> 00:04:03,040 Our first step will be to observe that given two columns we can find four 64 00:04:03,040 --> 00:04:08,120 different kinds of row, depending upon which bits are present in that row. 65 00:04:08,120 --> 00:04:11,800 For example, type a row has one in both columns. 66 00:04:11,800 --> 00:04:13,510 Notice that if the matrix is sparse, 67 00:04:13,510 --> 00:04:17,420 most of the rows will be of type d with zeros in both columns. 68 00:04:19,040 --> 00:04:24,660 I find it useful to abuse the notation and use a, b, c and d also 69 00:04:24,660 --> 00:04:30,180 as integers representing the number of rows of types A, B, C and D in the matrix. 70 00:04:31,370 --> 00:04:35,130 We can express the Jaccard similarity of two columns in terms of the counts of 71 00:04:35,130 --> 00:04:36,460 the row types. 72 00:04:36,460 --> 00:04:42,350 That is the similarity of columns C1 and C2 is A, divided by A plus B plus C. 73 00:04:42,350 --> 00:04:45,880 The reason is that A is the number of rows in the intersection, and 74 00:04:45,880 --> 00:04:48,500 A plus B plus C is the number of rows in the union. 75 00:04:51,060 --> 00:04:52,970 We're now going to define Minhashing. 76 00:04:54,840 --> 00:04:58,470 Each Minshashing hash function is associated with a permutation of 77 00:04:58,470 --> 00:04:59,850 the rows of the matrix. 78 00:04:59,850 --> 00:05:03,730 We don't physically permute the rows, that would take much too much time. 79 00:05:03,730 --> 00:05:05,745 We just imagine that the rows are permuted. 80 00:05:07,630 --> 00:05:12,370 The definition of the minhash function h, associated with a permutation is, 81 00:05:12,370 --> 00:05:18,280 is that h of a column C is the number of the first row in the permuted order, 82 00:05:18,280 --> 00:05:20,350 in which that column has 1. 83 00:05:20,350 --> 00:05:22,600 To create a signature for 84 00:05:22,600 --> 00:05:25,260 each of the columns of the matrix, we pick some number. 85 00:05:26,260 --> 00:05:30,020 About 100 is often a good choice of permutations. 86 00:05:30,020 --> 00:05:33,330 And use their associated Minhash functions, say H1 through H100. 87 00:05:34,540 --> 00:05:38,370 For each column, the signature is the sequence of row numbers we 88 00:05:38,370 --> 00:05:43,020 get when we apply each of these Minhash functions in turn to the column. 89 00:05:43,020 --> 00:05:44,630 It is important to remember that for 90 00:05:44,630 --> 00:05:49,700 the entire matrix or collection of sets, we select the Minhash functions once and 91 00:05:49,700 --> 00:05:52,380 apply the same Minhash functions to each of the columns. 92 00:05:55,230 --> 00:05:57,270 We can think of the signatures as another matrix. 93 00:05:57,270 --> 00:06:00,840 The columns of the signature matrix correspond to the columns of 94 00:06:00,840 --> 00:06:04,650 the original matrix, that is, to the sets in the collection. 95 00:06:04,650 --> 00:06:08,570 While each row in the signature matrix is the result of applying one of 96 00:06:08,570 --> 00:06:12,270 the chosen Minhash functions to each of the columns. 97 00:06:12,270 --> 00:06:15,070 Let's look at a little example that can make things clearer. 98 00:06:17,210 --> 00:06:20,220 Here's an example matrix with four columns and seven rows. 99 00:06:24,250 --> 00:06:28,539 Okay, and here's a random well, quote random permutation of the rows. 100 00:06:31,300 --> 00:06:37,260 The fifth row is the first in order, that's this. 101 00:06:41,030 --> 00:06:49,220 And the sixth row is next, and the top row is third and, and so on. 102 00:06:50,750 --> 00:06:53,500 We construct the first component of the signature for 103 00:06:53,500 --> 00:06:56,520 each of the columns using this permutation. 104 00:06:56,520 --> 00:06:59,730 We start with the row ordered first, that is row 5. 105 00:06:59,730 --> 00:07:00,230 This. 106 00:07:04,180 --> 00:07:07,409 And this row has one in the second and fourth columns. 107 00:07:10,450 --> 00:07:12,440 And thus we gave columns two and 108 00:07:12,440 --> 00:07:17,830 four, their first Minhash value, it is one, and that appears here. 109 00:07:20,300 --> 00:07:24,600 Okay, because the first row in the permuted order is surely the first in that 110 00:07:24,600 --> 00:07:26,670 order to have a one in these columns. 111 00:07:26,670 --> 00:07:31,100 We still don't know about the 2s in the first row of the signature matrix. 112 00:07:31,100 --> 00:07:31,680 These this. 113 00:07:32,770 --> 00:07:34,090 We'll discover those next. 114 00:07:35,460 --> 00:07:36,925 So now, we proceed to row 6. 115 00:07:36,925 --> 00:07:39,610 This, which is the second in the permuted order. 116 00:07:42,130 --> 00:07:44,894 And this row has 1s in column 1 and 3. 117 00:07:46,000 --> 00:07:49,090 It happens that neither of those columns has been assigned a value yet, 118 00:07:49,090 --> 00:07:52,910 because we haven't encountered a row in which either of those columns have 1. 119 00:07:52,910 --> 00:07:55,200 But they both get the value 2. 120 00:07:58,370 --> 00:08:01,363 Because the second row in the permuted order, but 121 00:08:01,363 --> 00:08:06,040 not the first row in that order has 1 in each of these columns. 122 00:08:06,040 --> 00:08:09,890 In principle, we have to proceed down the list of rows in the permuted order. 123 00:08:09,890 --> 00:08:12,080 But since we've discovered the Minhash value for 124 00:08:12,080 --> 00:08:14,700 each column, there's no point in doing so. 125 00:08:14,700 --> 00:08:17,650 Here's the second, quote, random permutation, and 126 00:08:17,650 --> 00:08:20,430 it's resulting row of the signature matrix. 127 00:08:20,430 --> 00:08:25,159 In this permutation, row 3 comes first. 128 00:08:30,798 --> 00:08:34,452 It has a 1 in the second and fourth column, so 129 00:08:34,452 --> 00:08:39,150 the second row of the signature matrix gets 1 in those columns. 130 00:08:42,160 --> 00:08:44,890 Okay. Now look at the second row in this order, 131 00:08:44,890 --> 00:08:46,170 which is row two. 132 00:08:50,580 --> 00:08:54,610 It has one in columns one and four. 133 00:08:54,610 --> 00:08:59,880 We can't assign value two to column four because we already have a value one. 134 00:09:01,540 --> 00:09:04,770 But we don't yet have a value for column one. 135 00:09:04,770 --> 00:09:05,680 So, we assign it, 136 00:09:07,290 --> 00:09:13,400 the value 2 as its Minhash value in the, in the second Minhash function. 137 00:09:13,400 --> 00:09:15,630 We still don't know the value for column 3, 138 00:09:15,630 --> 00:09:20,280 because neither of the two rows examined so far, have 1 in that column. 139 00:09:20,280 --> 00:09:25,304 So, we proceeds to the third row in the permuted order, which is row 4. 140 00:09:28,970 --> 00:09:30,880 And it has one's in columns two and 141 00:09:30,880 --> 00:09:36,070 four, but both these columns have smaller values already, so we're still not done. 142 00:09:36,070 --> 00:09:37,680 So we move on to the fourth row. 143 00:09:40,280 --> 00:09:41,860 It happens to be the top row here. 144 00:09:44,970 --> 00:09:48,780 And now we find finally, a one in column 3. 145 00:09:48,780 --> 00:09:52,630 So, the Minhash value for that column is four. 146 00:09:55,820 --> 00:09:58,957 Okay, and now we're done with this Minhash function. 147 00:10:00,380 --> 00:10:04,410 He, here's a third permutation and the resulting role of the signature matrix. 148 00:10:04,410 --> 00:10:07,424 I'll, I'll leave it to you to study the matter and work out, why the Minhash. 149 00:10:10,870 --> 00:10:14,740 Now, the reason we like mean hashing is a way to summarize answers expressed by 150 00:10:14,740 --> 00:10:16,490 the following remarkable property. 151 00:10:19,590 --> 00:10:23,740 Suppose we consider all possible permutations of the rows and ask, for 152 00:10:23,740 --> 00:10:26,750 what fraction of the permutations would the mean hash values for 153 00:10:26,750 --> 00:10:29,760 the two columns, C1 and C2, be the same? 154 00:10:29,760 --> 00:10:35,760 It turns out this probability is exactly the Juccard similarity of the columns or 155 00:10:35,760 --> 00:10:36,850 the sets they represent. 156 00:10:39,490 --> 00:10:42,570 Okay, now, here's a simple proof of this fact. 157 00:10:42,570 --> 00:10:47,160 Both the probability and the similarity are a over a plus b plus c. 158 00:10:47,160 --> 00:10:50,910 We already know that the Jucard similarity of columns is given by that formula. 159 00:10:52,590 --> 00:10:58,040 So, why is the probability of the Minhash values being the same also given by 160 00:10:58,040 --> 00:11:00,830 A over A plus B plus C? 161 00:11:00,830 --> 00:11:05,530 Imagine the rows are commuted in a random order, and imagine going down the two 162 00:11:05,530 --> 00:11:10,180 columns in this order, let's see here, C1, here C2. 163 00:11:11,770 --> 00:11:14,960 Since most entries are zero, we'll probably need a lot of type d rows zero, 164 00:11:14,960 --> 00:11:21,159 zero, zero, zero zero, and so on. 165 00:11:21,159 --> 00:11:23,720 Okay, and 166 00:11:23,720 --> 00:11:27,270 eventually we'll come to a row where at least one of the columns has a one. 167 00:11:27,270 --> 00:11:28,700 So, let's suppose here's a one. 168 00:11:33,007 --> 00:11:36,554 Now, if we came first to a type A row, then the MinHash values for 169 00:11:36,554 --> 00:11:40,120 the columns would agree, because we'd have a one here, okay? 170 00:11:42,460 --> 00:11:49,070 Okay, and they would both get this row as the as their MinHash value. 171 00:11:49,070 --> 00:11:51,830 If we come to a type B or C row first, or 172 00:11:51,830 --> 00:11:56,370 let's say there's a zero here, then one of the columns, 173 00:11:56,370 --> 00:12:01,550 the first one with the one gets this row as the, as it's meant hash value. 174 00:12:01,550 --> 00:12:04,730 But the other column will have to wait until we see a one. 175 00:12:04,730 --> 00:12:08,450 So, it's definitely going to get something higher, and 176 00:12:08,450 --> 00:12:11,090 they will not have same MinHash value. 177 00:12:11,090 --> 00:12:14,390 Thus the probability that the two columns will have the same MinHash value, 178 00:12:14,390 --> 00:12:19,540 is the probability that the first row that isn't of type-d is a type-a row. 179 00:12:19,540 --> 00:12:22,310 That probability is the number of type-a rows 180 00:12:22,310 --> 00:12:26,200 divided by the number of rows of any of the types a, b or c. 181 00:12:26,200 --> 00:12:31,710 That is, A divided by A plus B plus C. 182 00:12:31,710 --> 00:12:35,200 Armed with this observation we can sensibly define the similarity of 183 00:12:35,200 --> 00:12:36,040 two signatures. 184 00:12:37,140 --> 00:12:39,940 It is the fraction of the Minhash functions for 185 00:12:39,940 --> 00:12:41,959 which the two signatures have the same value. 186 00:12:44,110 --> 00:12:47,040 It follows that the expected value of the similarity of two 187 00:12:47,040 --> 00:12:49,760 signatures is the Jaccard similarity of the underlying sets. 188 00:12:50,900 --> 00:12:53,450 Moreover, as we use more and more minhash functions, 189 00:12:53,450 --> 00:12:56,800 the standard deviation of the signature similarity goes down. 190 00:12:57,850 --> 00:13:00,920 So, if we use several hundred Minhash functions, that is, 191 00:13:00,920 --> 00:13:03,500 signatures of several hundred components,. 192 00:13:03,500 --> 00:13:07,080 We get a small enough standard deviation that we can estimate the true 193 00:13:07,080 --> 00:13:11,820 Jaccard similarity of the represented sets to within a few percent. 194 00:13:11,820 --> 00:13:14,900 That is good enough for most data mining purposes. 195 00:13:18,640 --> 00:13:21,400 Let's revisit our example of computing signatures of 196 00:13:21,400 --> 00:13:22,940 length three from this matrix. 197 00:13:24,430 --> 00:13:27,210 Let's look at some of the signature similarities and 198 00:13:27,210 --> 00:13:29,140 the actual column similarities. 199 00:13:29,140 --> 00:13:33,440 Remember that similarity means different things for columns and signatures. 200 00:13:33,440 --> 00:13:37,960 For columns or sets it is the jacard similarity, while for signatures it 201 00:13:37,960 --> 00:13:40,780 is the fraction of components in which the two signatures agree. 202 00:13:43,290 --> 00:13:45,170 So let's look at columns one and 203 00:13:45,170 --> 00:13:53,705 three and their corresponding signatures. 204 00:13:53,705 --> 00:14:01,940 Yeah, the Jaccard similarity of the two columns is three fourths. 205 00:14:01,940 --> 00:14:05,990 Notice that there are four rows where at least one of these two columns is 1. 206 00:14:05,990 --> 00:14:11,096 That is here, here, 207 00:14:11,096 --> 00:14:16,600 here, and here. 208 00:14:16,600 --> 00:14:23,030 And in all of this one, they both have one. 209 00:14:23,030 --> 00:14:26,730 Thus the size of the intersection is three, and the size of the union is four. 210 00:14:27,780 --> 00:14:30,250 Now, look at signatures one and three. 211 00:14:30,250 --> 00:14:33,167 They agree for the first and third Minhash functions. 212 00:14:35,780 --> 00:14:38,419 But they disagree on the, the second. 213 00:14:40,170 --> 00:14:43,126 Thus the si, signature similarity is two-thirds. 214 00:14:43,126 --> 00:14:45,960 Now two-thirds is pretty close to three quarters, but 215 00:14:45,960 --> 00:14:50,920 there is some discrepancy as we note, here. 216 00:14:53,896 --> 00:15:00,704 If we look at columns two and four [NOISE] 217 00:15:00,704 --> 00:15:10,174 We again find the Jaccard similarity is three-quarters. 218 00:15:10,174 --> 00:15:12,770 But here the similarity of the signatures is 1. 219 00:15:12,770 --> 00:15:18,039 They are in fact identical in all three components. 220 00:15:19,170 --> 00:15:22,220 Another int, interesting example is columns 1 and 2. 221 00:15:24,980 --> 00:15:26,980 These columns have an empty intersection. 222 00:15:28,266 --> 00:15:30,970 So their Jaccard similarity similarities zero. 223 00:15:30,970 --> 00:15:34,190 It turns out that when the similarity is zero it is impossible for 224 00:15:34,190 --> 00:15:38,570 any min hash function to return the same value for these two columns. 225 00:15:38,570 --> 00:15:41,390 As we see again in the white table. 226 00:15:44,250 --> 00:15:49,870 Thus the similarity of these signatures is zero as, as it, as it must be. 227 00:15:49,870 --> 00:15:53,430 Remember that we've defined minhashing as if we'd actually permuted the rows. 228 00:15:53,430 --> 00:15:56,840 But it is not really feasible to do so. 229 00:15:56,840 --> 00:16:02,080 So let's, consider, data of modest size where there are a billion rows. 230 00:16:03,090 --> 00:16:07,130 First of all, takes a lot of time to pick a random permutation of a billion things. 231 00:16:07,130 --> 00:16:10,770 You essentially have to generate a build a billion random integers and 232 00:16:10,770 --> 00:16:15,190 do something with each, and representing a random permutation of 233 00:16:15,190 --> 00:16:19,200 a billion items takes at least, four gigabytes of space. 234 00:16:19,200 --> 00:16:22,090 If we had, say, 100 random permutations, 235 00:16:22,090 --> 00:16:26,030 then that's four tenths of a terabyte just to store the permutations. 236 00:16:30,200 --> 00:16:32,566 Okayt, And if you try to access the rows of the matrix, 237 00:16:32,566 --> 00:16:34,882 according to the order of one of these permutations, 238 00:16:34,882 --> 00:16:38,150 then you'll have to do many disk accesses to get each row. 239 00:16:38,150 --> 00:16:39,710 And that's incredibly time consuming. 240 00:16:41,510 --> 00:16:45,830 Here's how we simulate permutations without actually permuting rows. 241 00:16:45,830 --> 00:16:49,920 For each main hash function pick a normal sort of hash function that 242 00:16:49,920 --> 00:16:54,490 hashes integers to some number of buckets. 243 00:16:54,490 --> 00:16:58,850 We pretend that the position of row R in the permutation is H of R 244 00:16:58,850 --> 00:17:00,060 where H is the hash function. 245 00:17:01,500 --> 00:17:03,630 so, for each column, we'll look for 246 00:17:03,630 --> 00:17:09,820 that row r, in which the column has a one and for which h of r is the smallest. 247 00:17:09,820 --> 00:17:14,280 More specifically let's pick some number of ordinary hash functions, 248 00:17:14,280 --> 00:17:15,840 say 100 hash functions. 249 00:17:15,840 --> 00:17:18,720 One for each Minhash function we want to simulate. 250 00:17:18,720 --> 00:17:19,220 Okay? 251 00:17:20,260 --> 00:17:24,510 For each column c, we keep a slot for each of the hash functions. 252 00:17:24,510 --> 00:17:29,340 Call the slot for column c and the ith hash function m of i and c. 253 00:17:30,790 --> 00:17:33,343 If we want a 100 minhash functions, 254 00:17:33,343 --> 00:17:37,070 then the number of slots is 100 times the numbers of columns. 255 00:17:38,880 --> 00:17:41,610 Our goal is that eventually M of i and 256 00:17:41,610 --> 00:17:45,560 c will become the smallest value of h sub i of r. 257 00:17:45,560 --> 00:17:47,510 For which column c has a 1 in row r. 258 00:17:48,680 --> 00:17:52,890 That is, we suppose that the ith min hash function orders rows by the value to 259 00:17:52,890 --> 00:17:55,160 which h sub i sends each row. 260 00:17:56,820 --> 00:17:59,670 Notice that this order is not exactly a permutation. 261 00:17:59,670 --> 00:18:02,670 It's Entirely possible that h of i, 262 00:18:02,670 --> 00:18:07,900 h sub i, maps two or more rows to the same designation. 263 00:18:07,900 --> 00:18:12,410 But if we make the number of buckets into which h of i hash is very large, 264 00:18:12,410 --> 00:18:15,660 larger than the number of rows, then the probability of a collision at 265 00:18:15,660 --> 00:18:19,840 the smallest value is very small, and we can ignore the probability of a collision. 266 00:18:22,580 --> 00:18:24,570 So here's the algorithm in a nutshell. 267 00:18:25,890 --> 00:18:27,340 The outer loop is on the rows. 268 00:18:27,340 --> 00:18:27,840 Okay. 269 00:18:30,930 --> 00:18:33,840 For each row r, the first thing we do is compute each of the, 270 00:18:33,840 --> 00:18:38,890 perhaps, hundred hash values, h sub i of r. 271 00:18:38,890 --> 00:18:40,159 That's this. 272 00:18:42,190 --> 00:18:46,550 Then, we'll loop over all the column c, and 273 00:18:46,550 --> 00:18:51,620 if column c does not have a one in row r then we do nothing for r and c. 274 00:18:54,212 --> 00:18:59,400 Okay, but, now suppose matrix m has one in row r in column c. 275 00:19:01,272 --> 00:19:09,302 Then we're going to loop over the index I. 276 00:19:09,302 --> 00:19:11,945 For all the hash functions, and for 277 00:19:11,945 --> 00:19:18,560 each of these perhaps hundred values of I, we check whether H of S of R is smaller. 278 00:19:18,560 --> 00:19:22,517 Then the smallest value currently in the slot for 279 00:19:22,517 --> 00:19:28,114 the hash function, for, hash function i in column c, 280 00:19:28,114 --> 00:19:33,830 see, if that is the case then we replace that slot by, h by r. 281 00:19:35,540 --> 00:19:39,230 We take M of i and c to be infinity initially. 282 00:19:39,230 --> 00:19:46,260 So the first row in which we find has a won in column, 283 00:19:46,260 --> 00:19:50,290 Also note that it is important we compute h survive r only once for 284 00:19:50,290 --> 00:19:52,710 each hash function in each row. 285 00:19:52,710 --> 00:19:55,938 Outside the loop over the columns, that's, that was, that was this. 286 00:20:02,334 --> 00:20:03,960 So, let's do a little example. 287 00:20:05,840 --> 00:20:11,803 Our matrix has only two columns and five rows, that's, that's this, 288 00:20:13,620 --> 00:20:18,160 We're going to use two hash functions, that is we compute signatures of length 2. 289 00:20:18,160 --> 00:20:22,640 The two hash function, functions that we use are, are shown here. 290 00:20:25,260 --> 00:20:27,440 Each maps integers to five buckets. 291 00:20:27,440 --> 00:20:34,490 The, the first which we call h of x, maps any integer X to X marginal 5. 292 00:20:36,370 --> 00:20:39,680 That is the remainder when X is divided by 5. 293 00:20:39,680 --> 00:20:44,610 The second G of X computes a 2X plus 1, 294 00:20:44,610 --> 00:20:49,059 and again takes that modual 5, takes the remainder of 2X plus 1 mod 5. 295 00:20:50,430 --> 00:20:53,264 Okay, we are ready to compute the two components of the signatures for 296 00:20:53,264 --> 00:20:55,220 each of these columns. 297 00:20:55,220 --> 00:20:57,590 Remember that initially, we'll assume all slots are infinity. 298 00:20:58,964 --> 00:21:00,240 Begin by looking at the first row. 299 00:21:03,120 --> 00:21:07,640 And we find h of one is one and g of one is three. 300 00:21:10,572 --> 00:21:11,220 modulus. 301 00:21:11,220 --> 00:21:15,640 Take, take them all modulus five, so three modular five is in fact three. 302 00:21:17,690 --> 00:21:23,836 now, row one has one in the first column, but zero in, in the second column. 303 00:21:23,836 --> 00:21:26,555 Therefore the second signature is not changed, and 304 00:21:26,555 --> 00:21:28,730 both its components remain at infinity. 305 00:21:31,080 --> 00:21:33,930 But the first signature is changed to the values of h of 1 and 306 00:21:33,930 --> 00:21:37,078 g of 1 that is 1 and 3. 307 00:21:37,078 --> 00:21:42,282 Okay, now, consider the second row, 308 00:21:42,282 --> 00:21:48,286 h of 2 is 2 and g of 2 is 5 modular 5, or 0. 309 00:21:50,962 --> 00:21:57,919 Since column 1 has 0 in the second row, 310 00:21:57,919 --> 00:22:02,870 we do not change its signature. 311 00:22:02,870 --> 00:22:05,390 But column 2 has 1 in row 2, so 312 00:22:05,390 --> 00:22:09,114 we replace the infinite values in its signature by 2 and 0. 313 00:22:12,000 --> 00:22:15,380 Next, the third row, H of three is three, and 314 00:22:15,380 --> 00:22:18,900 G of three is seven, modular five, which is two. 315 00:22:19,918 --> 00:22:22,032 There is one in row three of both columns, so 316 00:22:22,032 --> 00:22:25,420 both signatures are candidates for being lowered. 317 00:22:25,420 --> 00:22:29,914 However, H of three is three in the first components of both signatures are already 318 00:22:29,914 --> 00:22:37,810 lower, one and two respectively So, we do not change either first component. 319 00:22:38,810 --> 00:22:42,600 Now g of 3 is 2, so we might change either second component. 320 00:22:43,630 --> 00:22:46,090 For the first signature the current value is 3. 321 00:22:48,530 --> 00:22:49,744 So we lower it to 2. 322 00:22:52,010 --> 00:22:53,940 But for the second signature, the signature, 323 00:22:53,940 --> 00:22:55,990 the current value is already zero. 324 00:22:57,420 --> 00:22:59,625 So we leave it at zero. 325 00:23:07,214 --> 00:23:13,050 H of 4 is 4 and G of 4 is 9 modular five, which is four. 326 00:23:13,050 --> 00:23:16,530 And since four is larger than any of the current slots for 327 00:23:16,530 --> 00:23:18,980 the first column, no changes are made. 328 00:23:23,820 --> 00:23:28,600 Finally, h of five is five modular five or zero. 329 00:23:28,600 --> 00:23:32,890 And g of 5 is 11 modulo 5, or 1. 330 00:23:32,890 --> 00:23:38,860 Only the second column has a 1 in row 5, 331 00:23:38,860 --> 00:23:42,648 so we can only change its signature. 332 00:23:42,648 --> 00:23:48,039 Since h to 5 equals 0, and the old value of the slot for h is 2. 333 00:23:49,260 --> 00:23:50,340 We change it to zero. 334 00:23:52,150 --> 00:23:58,570 But the slot for g already has zero, which is lower than g of five, which is one. 335 00:23:58,570 --> 00:24:00,120 So, no change is made there. 336 00:24:02,570 --> 00:24:06,950 Thus, the final symmetry is r one two for the first column. 337 00:24:09,090 --> 00:24:11,660 And zero, zero for the second column. 338 00:24:14,820 --> 00:24:18,442 Incidentally notice that the two signatures disagree for both components, 339 00:24:18,442 --> 00:24:22,020 so they estimate the Jaccard similarities of the columns that are zero. 340 00:24:22,020 --> 00:24:23,500 That's off by a little since, 341 00:24:23,500 --> 00:24:27,469 as you can see the true Jaccard's similarity of the columns is one fifth. 342 00:24:29,120 --> 00:24:30,870 One last detail is worth mentioning. 343 00:24:32,180 --> 00:24:36,990 The algorithm we, we describe as soon as we can visit the matrix row by row. 344 00:24:36,990 --> 00:24:40,600 But often the data is available by columns and not by rows. 345 00:24:42,320 --> 00:24:44,360 For instance, if we have a file of documents, 346 00:24:44,360 --> 00:24:47,489 it's natural to process each document once, computing its shingles. 347 00:24:48,910 --> 00:24:51,160 That, in effect, gives us one column of the matrix. 348 00:24:54,050 --> 00:25:00,800 If so, we need to do one preliminary step, sort the data, so it is organized by row. 349 00:25:00,800 --> 00:25:01,630 That's not hard. 350 00:25:01,630 --> 00:25:05,260 Start with a list of row column pairs where the ones are. 351 00:25:05,260 --> 00:25:09,004 Initially sort it by column, and sort these pairs by row.