We're now going to forget whether the sets
we deal with come from single documents or
any other source and
concentrate on the sets themselves.
We'll learn the formal definition of
similarity that is commonly used for sets.
This notion is called Jaccard similarity.
We'll then learn how to
construct signatures from sets
using the menhashing technique.
And will prove the strong relationship
between the similarity of
the signatures and
the sets they represent.
Let C1 and C2 be two sets,
their Jaccard similarity is the size of
the intersection of these two sets,
divided by the size of the union.
We'll use Sim as the function
representing the Jaccard similarity.
For example,
these two circles represent sets.
There are three elements
in common to both sets.
So, the size of their
intersection is three.
And there are eight elements in the union,
so the size of their union is eight.
The Jaccard similarity of these
sets is the ratio of the sizes of
their intersection and un, and union or
three eighths in this example.
We're going to be dealing with
large collections of sets and
it is useful to think of these collections
as represented by a single Boolean matrix,
even if the collection is not
likely to be stored that way.
First, we assume that
there's a universal set,
from which the elements
of all sets are drawn.
For example, if the sets come
from k-shingling documents,
then the universal set is the set of all
possible sequences of K characters or
the set of all tokens if
we hash the shingles.
Each element in the universal set is
represented by a row of the matrix.
And each set in the collection is
represented by a column of the matrix.
The matrix has one in the row for
element E and the column for
S, if and only if E is a member of S.
Otherwise that entry is zero.
The column corresponding to a set as
the characteristic vector of the set S.
The vector with ones only in the positions
that correspond to the members of S.
We shall often talk about
the Jaccard similarity of 2 columns.
From each column,
form the set represented by the column,
except consisting of the rows
where the column has 1.
Then the Jaccard similarity of the two
columns is the Jaccard similarity of
the sets they represent.
It is important to note that in typical
applications, the matrix is very sparse.
It has many more zeros than ones.
For example, we choose k for
k shingling, so
that documents have relatively
few of the possible shingles.
We translate into columns having
many more zeroes than ones.
For another example, suppose the matrix
represents the books bought by
Amazon customers, rows are the books and
columns are the customers.
And customers are similar if
they buy many of the same books.
Typical customer buys only a tiny
fraction of the books Amazon sells.
So again, we would expect our
matrix to be very sparse.
Here are two columns, C1 and C2.
They're not sparse,
because it's hard to do small
examples when most entries are zero.
However, the calculation of their
Jaccard similarity is simple.
There are two rows where
they both have one, so
the intersection of the sets
they represent is of size two.
And there are five rows where at
least one of the columns has one,
so the size of the union of
the represented sets is five.
Thus the Jacquard similarity
is two fifths of 40%.
In general, you can compute
the similarity of two columns,
by counting the number of
rows where both have one, and
dividing by the number of rows
in which one or both have one.
Our goal is to describe
how min hashing of sets or
matrix column works, and to show that we
can deduce the similarity of the sets or
columns by looking at the signatures
that result from in hashing.
Our first step will be to observe that
given two columns we can find four
different kinds of row, depending upon
which bits are present in that row.
For example,
type a row has one in both columns.
Notice that if the matrix is sparse,
most of the rows will be of type
d with zeros in both columns.
I find it useful to abuse the notation and
use a, b, c and d also
as integers representing the number of
rows of types A, B, C and D in the matrix.
We can express the Jaccard similarity of
two columns in terms of the counts of
the row types.
That is the similarity of columns C1 and
C2 is A, divided by A plus B plus C.
The reason is that A is the number
of rows in the intersection, and
A plus B plus C is the number
of rows in the union.
We're now going to define Minhashing.
Each Minshashing hash function is
associated with a permutation of
the rows of the matrix.
We don't physically permute the rows,
that would take much too much time.
We just imagine that
the rows are permuted.
The definition of the minhash function h,
associated with a permutation is,
is that h of a column C is the number
of the first row in the permuted order,
in which that column has 1.
To create a signature for
each of the columns of the matrix,
we pick some number.
About 100 is often a good
choice of permutations.
And use their associated Minhash
functions, say H1 through H100.
For each column, the signature is
the sequence of row numbers we
get when we apply each of these Minhash
functions in turn to the column.
It is important to remember that for
the entire matrix or collection of sets,
we select the Minhash functions once and
apply the same Minhash functions
to each of the columns.
We can think of the signatures
as another matrix.
The columns of the signature matrix
correspond to the columns of
the original matrix, that is,
to the sets in the collection.
While each row in the signature matrix
is the result of applying one of
the chosen Minhash functions
to each of the columns.
Let's look at a little example
that can make things clearer.
Here's an example matrix with
four columns and seven rows.
Okay, and here's a random well,
quote random permutation of the rows.
The fifth row is the first in order,
that's this.
And the sixth row is next, and
the top row is third and, and so on.
We construct the first
component of the signature for
each of the columns
using this permutation.
We start with the row ordered first,
that is row 5.
This.
And this row has one in the second and
fourth columns.
And thus we gave columns two and
four, their first Minhash value,
it is one, and that appears here.
Okay, because the first row in the
permuted order is surely the first in that
order to have a one in these columns.
We still don't know about the 2s in
the first row of the signature matrix.
These this.
We'll discover those next.
So now, we proceed to row 6.
This, which is the second
in the permuted order.
And this row has 1s in column 1 and 3.
It happens that neither of those
columns has been assigned a value yet,
because we haven't encountered a row in
which either of those columns have 1.
But they both get the value 2.
Because the second row in
the permuted order, but
not the first row in that order
has 1 in each of these columns.
In principle, we have to proceed down
the list of rows in the permuted order.
But since we've discovered
the Minhash value for
each column, there's no point in doing so.
Here's the second, quote,
random permutation, and
it's resulting row of
the signature matrix.
In this permutation, row 3 comes first.
It has a 1 in the second and
fourth column, so
the second row of the signature
matrix gets 1 in those columns.
Okay.
Now look at the second row in this order,
which is row two.
It has one in columns one and four.
We can't assign value two to column four
because we already have a value one.
But we don't yet
have a value for column one.
So, we assign it,
the value 2 as its Minhash value in the,
in the second Minhash function.
We still don't know the value for
column 3,
because neither of the two rows
examined so far, have 1 in that column.
So, we proceeds to the third row in
the permuted order, which is row 4.
And it has one's in columns two and
four, but both these columns have smaller
values already, so we're still not done.
So we move on to the fourth row.
It happens to be the top row here.
And now we find finally,
a one in column 3.
So, the Minhash value for
that column is four.
Okay, and
now we're done with this Minhash function.
He, here's a third permutation and the
resulting role of the signature matrix.
I'll, I'll leave it to you to study
the matter and work out, why the Minhash.
Now, the reason we like mean hashing is
a way to summarize answers expressed by
the following remarkable property.
Suppose we consider all possible
permutations of the rows and ask, for
what fraction of the permutations
would the mean hash values for
the two columns, C1 and C2, be the same?
It turns out this probability is exactly
the Juccard similarity of the columns or
the sets they represent.
Okay, now,
here's a simple proof of this fact.
Both the probability and
the similarity are a over a plus b plus c.
We already know that the Jucard similarity
of columns is given by that formula.
So, why is the probability of the Minhash
values being the same also given by
A over A plus B plus C?
Imagine the rows are commuted in a random
order, and imagine going down the two
columns in this order,
let's see here, C1, here C2.
Since most entries are zero, we'll
probably need a lot of type d rows zero,
zero, zero, zero zero, and so on.
Okay, and
eventually we'll come to a row where
at least one of the columns has a one.
So, let's suppose here's a one.
Now, if we came first to a type A row,
then the MinHash values for
the columns would agree,
because we'd have a one here, okay?
Okay, and they would both get this
row as the as their MinHash value.
If we come to a type B or C row first, or
let's say there's a zero here,
then one of the columns,
the first one with the one gets this
row as the, as it's meant hash value.
But the other column will have
to wait until we see a one.
So, it's definitely going to
get something higher, and
they will not have same MinHash value.
Thus the probability that the two columns
will have the same MinHash value,
is the probability that the first row
that isn't of type-d is a type-a row.
That probability is
the number of type-a rows
divided by the number of rows
of any of the types a, b or c.
That is, A divided by A plus B plus C.
Armed with this observation we can
sensibly define the similarity of
two signatures.
It is the fraction of
the Minhash functions for
which the two signatures
have the same value.
It follows that the expected
value of the similarity of two
signatures is the Jaccard
similarity of the underlying sets.
Moreover, as we use more and
more minhash functions,
the standard deviation of
the signature similarity goes down.
So, if we use several hundred
Minhash functions, that is,
signatures of several hundred components,.
We get a small enough standard
deviation that we can estimate the true
Jaccard similarity of the represented
sets to within a few percent.
That is good enough for
most data mining purposes.
Let's revisit our example
of computing signatures of
length three from this matrix.
Let's look at some of
the signature similarities and
the actual column similarities.
Remember that similarity means different
things for columns and signatures.
For columns or sets it is the jacard
similarity, while for signatures it
is the fraction of components in
which the two signatures agree.
So let's look at columns one and
three and their corresponding signatures.
Yeah, the Jaccard similarity of
the two columns is three fourths.
Notice that there are four rows where
at least one of these two columns is 1.
That is here, here,
here, and here.
And in all of this one,
they both have one.
Thus the size of the intersection is
three, and the size of the union is four.
Now, look at signatures one and three.
They agree for the first and
third Minhash functions.
But they disagree on the, the second.
Thus the si,
signature similarity is two-thirds.
Now two-thirds is pretty
close to three quarters, but
there is some discrepancy as we note,
here.
If we look at columns two and four [NOISE]
We again find the Jaccard
similarity is three-quarters.
But here the similarity
of the signatures is 1.
They are in fact identical
in all three components.
Another int,
interesting example is columns 1 and 2.
These columns have an empty intersection.
So their Jaccard similarity
similarities zero.
It turns out that when the similarity
is zero it is impossible for
any min hash function to return
the same value for these two columns.
As we see again in the white table.
Thus the similarity of these signatures
is zero as, as it, as it must be.
Remember that we've defined minhashing
as if we'd actually permuted the rows.
But it is not really feasible to do so.
So let's, consider, data of modest
size where there are a billion rows.
First of all, takes a lot of time to pick
a random permutation of a billion things.
You essentially have to generate
a build a billion random integers and
do something with each, and
representing a random permutation of
a billion items takes at least,
four gigabytes of space.
If we had, say, 100 random permutations,
then that's four tenths of a terabyte
just to store the permutations.
Okayt, And if you try to
access the rows of the matrix,
according to the order of
one of these permutations,
then you'll have to do many
disk accesses to get each row.
And that's incredibly time consuming.
Here's how we simulate permutations
without actually permuting rows.
For each main hash function pick
a normal sort of hash function that
hashes integers to some number of buckets.
We pretend that the position of
row R in the permutation is H of R
where H is the hash function.
so, for each column, we'll look for
that row r, in which the column has a one
and for which h of r is the smallest.
More specifically let's pick some
number of ordinary hash functions,
say 100 hash functions.
One for
each Minhash function we want to simulate.
Okay?
For each column c, we keep a slot for
each of the hash functions.
Call the slot for column c and
the ith hash function m of i and c.
If we want a 100 minhash functions,
then the number of slots is 100
times the numbers of columns.
Our goal is that eventually M of i and
c will become the smallest
value of h sub i of r.
For which column c has a 1 in row r.
That is, we suppose that the ith min hash
function orders rows by the value to
which h sub i sends each row.
Notice that this order is
not exactly a permutation.
It's Entirely possible that h of i,
h sub i, maps two or
more rows to the same designation.
But if we make the number of buckets
into which h of i hash is very large,
larger than the number of rows,
then the probability of a collision at
the smallest value is very small, and we
can ignore the probability of a collision.
So here's the algorithm in a nutshell.
The outer loop is on the rows.
Okay.
For each row r, the first thing
we do is compute each of the,
perhaps, hundred hash values,
h sub i of r.
That's this.
Then, we'll loop over all the column c,
and
if column c does not have a one in
row r then we do nothing for r and c.
Okay, but, now suppose matrix m
has one in row r in column c.
Then we're going to loop over the index I.
For all the hash functions, and for
each of these perhaps hundred values of I,
we check whether H of S of R is smaller.
Then the smallest value
currently in the slot for
the hash function, for,
hash function i in column c,
see, if that is the case then
we replace that slot by, h by r.
We take M of i and
c to be infinity initially.
So the first row in which we
find has a won in column,
Also note that it is important we
compute h survive r only once for
each hash function in each row.
Outside the loop over the columns,
that's, that was, that was this.
So, let's do a little example.
Our matrix has only two columns and
five rows, that's, that's this,
We're going to use two hash functions,
that is we compute signatures of length 2.
The two hash function,
functions that we use are, are shown here.
Each maps integers to five buckets.
The, the first which we call h of x,
maps any integer X to X marginal 5.
That is the remainder
when X is divided by 5.
The second G of X computes a 2X plus 1,
and again takes that modual 5,
takes the remainder of 2X plus 1 mod 5.
Okay, we are ready to compute the two
components of the signatures for
each of these columns.
Remember that initially,
we'll assume all slots are infinity.
Begin by looking at the first row.
And we find h of one is one and
g of one is three.
modulus.
Take, take them all modulus five, so
three modular five is in fact three.
now, row one has one in the first column,
but zero in, in the second column.
Therefore the second
signature is not changed, and
both its components remain at infinity.
But the first signature is changed
to the values of h of 1 and
g of 1 that is 1 and 3.
Okay, now, consider the second row,
h of 2 is 2 and
g of 2 is 5 modular 5, or 0.
Since column 1 has 0 in the second row,
we do not change its signature.
But column 2 has 1 in row 2, so
we replace the infinite values
in its signature by 2 and 0.
Next, the third row,
H of three is three, and
G of three is seven,
modular five, which is two.
There is one in row three of both columns,
so
both signatures are candidates for
being lowered.
However, H of three is three in the first
components of both signatures are already
lower, one and two respectively So,
we do not change either first component.
Now g of 3 is 2, so
we might change either second component.
For the first signature
the current value is 3.
So we lower it to 2.
But for the second signature,
the signature,
the current value is already zero.
So we leave it at zero.
H of 4 is 4 and
G of 4 is 9 modular five, which is four.
And since four is larger than
any of the current slots for
the first column, no changes are made.
Finally, h of five is five modular five or
zero.
And g of 5 is 11 modulo 5, or 1.
Only the second column has a 1 in row 5,
so we can only change its signature.
Since h to 5 equals 0, and
the old value of the slot for h is 2.
We change it to zero.
But the slot for g already has zero, which
is lower than g of five, which is one.
So, no change is made there.
Thus, the final symmetry is r one two for
the first column.
And zero, zero for the second column.
Incidentally notice that the two
signatures disagree for both components,
so they estimate the Jaccard similarities
of the columns that are zero.
That's off by a little since,
as you can see the true Jaccard's
similarity of the columns is one fifth.
One last detail is worth mentioning.
The algorithm we, we describe as soon
as we can visit the matrix row by row.
But often the data is available
by columns and not by rows.
For instance,
if we have a file of documents,
it's natural to process each document
once, computing its shingles.
That, in effect,
gives us one column of the matrix.
If so, we need to do one preliminary step,
sort the data, so it is organized by row.
That's not hard.
Start with a list of row column
pairs where the ones are.
Initially sort it by column,
and sort these pairs by row.