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