We're now going to take up a class of
problems where we're given a large
collection of sets, millions or
billions perhaps, and we are asked
to find those sets that are similar.
The notion of similarity is quite specific
and it's called Jaccard Similarity.
We'll learn this concept soon, but
the idea is roughly, that the larger
the fraction of elements the two sets
have in common the more similar they are.
There is a fundamental problem of scale.
If we have even a million sets not a large
number compared with the number of
web pages or Amazon users, the number
of pairs of sets is half a trillion.
We don't have the resources to compare
them all, so we need some magic defor,
focus us on the pairs that
are likely to be highly similar,
never looking at the vast
majority of pairs.
When you learned about hashing you're,
it probably seemed like a bit of magic.
You have a large set of keys, and
when you want to find some key k,
you go right to it without
having to look very far at all.
The technique we're going to learn,
locality sensitive hashing,
is another bit of magic.
Here we are pointed right at
the similar pairs without having to
wade through the morass of all pairs.
We'll begin by looking at some
applications where finding similar sets is
very useful.
We then are going to focus initially
on finding similar documents,
meaning that they have a substantial
amount of text in common.
For this problem we first study shingling,
which is a way to convert
the informal notion of similar documents
into a formal test for similarity of sets.
Then we learn the remarkable
technique called min hashing,
which allows us to replace a large
set by a much smaller list of values.
The magic of min hashing is that
the similarity of the small lists,
called signatures,
predicts the similarity of the whole sets.
Finally, we take up the locality
sensitive hashing technique itself and
see how to find similar sets or
similar documents without doing anything
that involves searching all pairs.
To begin, let's look at some of
the interesting data mining problems that
fit the pattern of mining for
similar sets.
For example, we can view web pages
as the set of words they contain.
If two pages have similar sets of words,
we might expect them to
be about the same topic.
For another example, imagine a matrix of
Netflix users where the rows correspond to
the users, and the columns to the movies.
The entry for a given user and
movie is the rating that the user has
given the movie, blank if no rating.
We might see a user as the set of
movies they have rated four or
five, that is movies they like.
Two users who have similar sets of liked
movies probably have the same tastes, and
Netflix can use the movies
one user said they
liked to recommend movies to the other.
We can use the same idea backwards.
Where we think of a movie as the set
of users who like that movie.
Movies with similar sets
of users can be expected to
belong to the same genre of movie.
People create records of data about
themselves at many different sites,
Google, Amazon, Facebook and so on.
We may want to figure out when two
records refer to the same individual, and
this need gives rise to the problem
called entity resolution,
determining the set of records
that refer to the same individual.
To see the problem,
many sites will ask for phone number.
But you might give your land line at one
site, your cell phone number at another,
not give a number at all at a third site,
and mistype your number at a fourth.
However, we can often wade
through the errors and
ambiguities by thinking of a record
as a set of attribute value pairs.
Pairs like, oh, phone is 555,
I don't know, whatever okay?
Records with similar even
if not identical sets of
attribute value pairs may well
represent the same individual, and
these records can be merged
to combine their information.
We're going to focus on
a particular important application,
finding lexically similar documents in a
large collection of docs such as the web.
Note we are not talking about
docs on a similar topic.
We want them to have sequences
of characters in common.
This question has
a variety of applications.
For example, the techniques we’re going
to learn were used to find mirror
pages on the web.
Mirror pages are typically almost the
same, but they will differ, for example,
in the information about the host site for
the page and links to the other mirrors.
Search engines use a technique
like the one we’ll learn so
they don’t show more than one
of a set of mirror sites.
Another application of finding
lexically similar documents is to
search for plagiarisms.
For example, spammers will take
your webpage, give it a new URL,
and place ads around it.
The plagiarizer may be clever, taking
only a part of the plagiarized document,
reordering pieces,
perhaps changing a word here and there.
We still want to be able to
find such pairs of documents in
a collection as large as the web without
having to compare all pairs of documents.
It can be done.
In fact, it's much easier than it looks.
And another application concerns
sites like Google News that
aggregate new stories.
An article may be written
by the Associated Press and
distributed to thousands of newspapers and
online news sites.
Each will make modifications,
perhaps truncating the story,
surrounding it with ads, and so on.
It's important for
an aggregator to realize that the two web
pages are really telling the same
story because they came from
the same original even if they
have been significantly modified.
As we suggested in the introduction,
we're going to learn three
important new techniques.
Shingling is how we convert
documents to sets so
that documents that have a lot of
text in common will be converted to
sets that are similar in the sense that
they have a lot of members in common.
Then we'll learn about minhashing,
which is how we convert
sets to short signatures.
The important property is that we can look
at the signatures of two sets and tell
approximately how similar are the sets
that we obtained by the shingling process.
And last but not least,
we'll learn the technique called
Locality-sensitive hashing or
LSH that let's us avoid looking
at most of the pairs of
signatures that do not
represent similar sets.
Here's an outline of how we'd
process documents to find those that
are similar without comparing all pairs.
At the outset, I want to emphasize that
there can be both false positives and
false negatives.
That is, the algorithms we use can
sometimes fail to find a pair of
documents that we would regard as similar.
That's a false negative.
We can also, if we're not careful to
check the details of the document,
sometimes have false positives.
Pairs of documents we declared to
be similar, but they really aren't.
However, by carefully choosing
the parameters involved, we can
make the probability of false positives
and negatives be as small as, as we like.
Okay so,
we start by shingling the document.
Okay, that is we replace the document by
the set of strings of some chosen length,
k, that appear in the document.
That's how we convert documents to sets.
We then construct signatures for
the sets of single, shingles using
the technique called minhashing.
The result of minhashing a set
is a short vector of integers.
The key property,
which we'll prove, is that the number
of components in which the, two of
these vectors agree is the expected value
of the similarity of the underlying sets.
Incidentally, the reason we want to
replace sets by their signatures is that
the signatures take up much less space.
If we're dealing with a large set of
documents, we'd like to be able to work in
main memory rather than with disc for
efficiency, and reducing the space of
the representations makes it more
likely that we can work in main memory.
But it seems we still need to
compare all pairs of signatures, and
that takes time that is quadratic
in the number of documents.
As we mentioned, even a million documents
leads to half a trillion pairs of
signatures to compare,
and that is too much.
So that's where locality
sensitive hashing comes in.
We do some magic, which we'll explain
soon, that allows us to look at
a small subset of the possible pairs, and
test only those pairs with similarity.
By doing so, we get almost all
the pairs that are truly similar, and
the total time spent is
much less than quadratic.
So lets begin the story by finding
exactly what shingles are.
For any integer k,
a k-shingle is sometimes called a k-gram,
is a sequence of k consecutive
characters in the document.
The blanks that separate the words of
the document are normally
considered characters.
If the document involves tags such as
an HTML document then the tags may
also be considered characters or
they can be ignored.
So here's an example of a little document
consisting of the five characters abcab.
We'll use k equals two for
this little example, although in
practice you want to use a k that is
large enough that most sequences of k
characters do not appear in the document.
A k in the range five to ten is used,
generally used but the two shingles for
our little document are ab, which is that,
then bc, then ca, and then ab again.
Since we're constructing a set,
we include the repeated
two shingle ab only once,
and thus our document
abcab is represented by
the set of shingles ab, bc and ca.
We need to assure ourselves
that replacing a document by
its shingles still lets us detect pairs of
documents that are intuitively similar.
In fact, similarity of shingle
sets captures many of the kinds of
document changes that we would regard
as keeping the documents similar.
For example, if we're using k-shingles and
we change one word, only the k-shingles to
the left and right of the word as well as
shingles within the word can be effected.
And we can re-order entire paragraphs
without affecting any shingles except
the shingles that cross the boundaries
between the paragraph we moved and
the paragraphs just before and
after in both the new and old positions.
For example,
suppose we use k equals three, and
we correctly change the which
in the sentence to that,
the only shingles that can be affected
are the ones that begin at most two
characters before which and
end at most two characters after which.
Okay, these are g blank w, blank wh,
and so on, up to h blank c.
A total of seven shingles.
These are replaced by
six different shingles.
G blank t, t is it blank th,
and so on up to t blank c.
however, all shingles other than these
remain the same in the two sentences.
Because documents tend to consist
mostly of the 26 letters, and
we want to make sure that most
shingles do not appear in a document,
we are often forced to use a large
value of k, like k equals ten.
But the number of different strings of
length ten that will actually appear in
any document is much smaller
than 256 to the tenth power or
even 26 to the tenth power.
Thus, it common to compress
shingles to save space while still
preserving the property that most shingles
do not appear in a given document.
For example, we can hash strings of
length ten to 32 bits or four bytes, thus
saving 60% of the space that are needed
to shore, to store the shingle sets.
The result of hashing shingles
is often called a token.
Thus, we can construct for
a document the set of it's tokens.
We construct the shingle set and
then hash each shingle to get a token.
Since documents are much shorter
than two to the 32nd power byte,
we still can be sure that a document
is only a small fraction of
the possible tokens in it's sets.
There's a small chance of a collision
where two shingles hashed to
the same token, but that could make two
documents appear to have shingles in
common when in fact they
have different shingles.
But such an an occurrence
will be quite rare.
In what follows we'll continue to
refer to shingles sets when these sets
might consist of token
rather than the raw shingles