Database Reference
In-Depth Information
3
Finding Similar Items
A fundamental data-mining problem is to examine data for “similar” items. We shall take up
applications in
Section 3.1
,
but an example would be looking at a collection of Web pages
and finding near-duplicate pages. These pages could be plagiarisms, for example, or they
could be mirrors that have almost the same content but differ in information about the host
and about other mirrors.
We begin by phrasing the problem of similarity as one of finding sets with a relatively
large intersection. We show how the problem of finding textually similar documents can be
turned into such a set problem by the technique known as “shingling.” Then, we introduce
a technique called “minhashing,” which compresses large sets in such a way that we can
still deduce the similarity of the underlying sets from their compressed versions. Other tech-
niques that work when the required degree of similarity is very high are covered in
Section
Another important problem that arises when we search for similar items of any kind is that
there may be far too many pairs of items to test each pair for their degree of similarity, even
if computing the similarity of any one pair can be made very easy. That concern motivates a
technique called “locality-sensitive hashing,” for focusing our search on pairs that are most
likely to be similar.
Finally, we explore notions of “similarity” that are not expressible as intersection of sets.
This study leads us to consider the theory of distance measures in arbitrary spaces. It also
motivates a general framework for locality-sensitive hashing that applies for other defini-
tions of “similarity.”
3.1 Applications of Near-Neighbor Search
We shall focus initially on a particular notion of “similarity”: the similarity of sets by looking
at the relative size of their intersection. This notion of similarity is called “Jaccard similar-
ity,” and will be introduced in
Section 3.1.1
. We then examine some of the uses of finding
similar sets. These include finding textually similar documents and collaborative filtering by