第 1 页
Fall 2019 Finding Similar Sets Vassilis Christophides christop@csd.uoc.gr http://www.csd.uoc.gr/~hy562 University of Crete, Fall 2019 1 Motivation Fall 2019 Many Web-mining problems can be expressed as finding “similar” sets: Pages with similar words, e.g., for classification by topic NetFlix users with similar tastes in movies for recommendation systems Dual: movies with similar sets of fans Images of related things The best techniques depend on whether you are looking for items that are very similar or only somewhat similar Special cases are easy, e.g., identical documents, or one document contained character-by-character in another General case, where many small pieces of one document appear out of order in another, is very hard 2 1 1
第 2 页
Fall 2019 Comparing Documents for Near Duplicates Applications: Given a body of documents, find pairs of documents with a lot of text in common, e.g.: Mirror Web sites, or approximate mirrors Application: Don’t want to show both in a search Plagiarism, including large quotations Similar news articles at many news sites Application: Cluster articles by “same story” Simple IR approaches are not suited: Document = set of words appearing in document Document = set of “important” words Why? we need to account for ordering of words! 3 Main Issues Fall 2019 What is the right representation of the document when we check for similarity? E.g., representing a document as a set of characters will not do (why?) When we have billions of documents, keeping the full text in memory is not an option We need to find a shorter representation How do we do pairwise comparisons of billions of documents? If exact match was the issue it would be ok, can we replicate this idea? 4 2 2
第 3 页
Three Essential Techniques for Fall 2019 Detecting Similar Documents Candidate Locality- pairs : Docu- sensitive those pairs ment Hashing of signatures that we need to test for The set of Signatures : similarity strings of short integer vectors length k that that represent the appear in the sets, and reflect document their similarity Shingling: convert documents, emails, etc., to sets Minhashing: convert large sets to short signatures, while preserving similarity Locality-sensitive hashing: focus on pairs of signatures likely to be similar 5 Shingles Fall 2019 A k -shingle (or k -gram) for a document is a sequence of k characters that appears in the document Represent a document by its set of k-shingles Example: k=2; doc= abcab. Set of 2-shingles = {ab, bc, ca} Option: regard shingles as a bag (multiset), and count ab twice Working Assumption: Documents that have lots of shingles in common have similar text, even if the text appears in different order What if two documents differ by a word? Affects only k‐shingles within distance k from the word What if we reorder paragraphs? Affects only the 2k shingles that cross paragraph boundaries 6 3 3
第 4 页
Shingle Size Fall 2019 Is k=2 a good choice for size? Example: k=2; doc1 = abcab. 2-shingles = {ab, bc, ca} doc2 = cabc. 2-shingles = {ab, bc, ca} Careful decision: you must pick k large enough, or most documents will have most shingles k = 5 is OK for short documents k = 10 is better for long documents 7 Shingles: Compression Option Fall 2019 How about space overhead? Each character can be represented as a byte k‐shingle requires k bytes If k=9, to compare shingles we need to compare 9 bytes To improve efficiency, we can compress long shingles: hash them to (say) 4 bytes, and represent a document by the set of hash values of its k-shingles (aaabbbccc)(abcabcabc) h(aaabbbccc)h(abcabcabc) 18 bytes 8 bytes Working Assumption: Two documents could (rarely) appear to have shingles in common, when in fact only the hash-values were shared 8 4 4
第 5 页
Fall 2019 Thought Question Why is it better to hash 9-shingles (say) to 4 bytes than to use 4-shingles? There are many more possible shingles, this reduces the likelihood that documents that share many shingles are not similar Hint: How random are the 32-bit sequences that result from 4-shingling? Assuming 20 characters are common in English, there are (20)4 = 160000 4-shingles < 232 Using 9-shingles there are (20)9 >> 232 9 Fall 2019 MinHashing 10 5 5
第 6 页
Fall 2019 Basic Data Model: Sets Many similarity problems can be couched as finding subsets of some universal set that have significant intersection Examples include: Documents represented by their sets of shingles (or hashes of those shingles): Ci=S(Di) Similar customers or products Equivalently, each document is a 0/1 vector in the space of k-shingles Each unique shingle is a dimension Vectors are very sparse Interpret set intersection as bitwise AND, and set union as bitwise OR 11 Fall 2019 Jaccard Similarity of Sets The Jaccard similarity of two sets is the size of their intersection divided by the size of their union Sim (C1, C2) = |C1C2|/|C1C2| Example: A B 3 in intersection 8 in union Jaccard similarity = 3/8 12 6 6
第 7 页
Motivation for Min-Hash Fall 2019 Suppose we need to find near-duplicate documents among 𝑵=𝟏 million (106) documents Naïvely, we would have to compute pairwise Jaccard similarities for every pair of docs 𝑵(𝑵−𝟏)/𝟐 ≈ 5*1011 comparisons At ≈ 105 secs/day and 106 comparisons/sec, it would take 5 days For 𝑵= 𝟏0 million (107), it takes more than a year… 13 Fall 2019 From Sets to Boolean Matrices Rows = elements (shingles) of the universal set Columns = sets (documents) 1 in row e and column S if and only if e is a member of S Column similarity is the Jaccard similarity of the sets of their rows with 1 Typical matrix is sparse (most rows are of type d, see later) Sparse matrices are usually better represented by the list of places where there is a non-zero value But the boolean matrix picture is conceptually useful 14 7 7
第 8 页
Fall 2019 Example: Jaccard Similarity of Columns C1 C2 a0 1 * b1 0 * c 1 1 * * Sim (C1, C2) = 2/5 = 0.4 d0 0 e1 1 * * d(C1,C2) =1– (Jaccard similarity) = f 0 1 * 0.6 15 Outline: Finding Similar Columns Fall 2019 Naïve approach: Compute signatures of columns = small summaries of columns Examine pairs of signatures to find similar columns Requirement: similarities of signatures and columns are related Optional: check that columns with similar signatures are really similar This scheme works but … What if the set of signatures (or k‐shingles) is too large to fit in the memory? Or the number of documents are too large? Idea: Find a way to hash a document (column) to a single (small size) value! and similar documents to the same value! Warning: These methods can produce false negatives, and even false positives (if the above optional check is not made) 16 8 8
第 9 页
Signatures Fall 2019 Key idea: “hash” h(·) each column C to a small signature, such that: h(C) is small enough that we can fit a signature in main memory for each column Sim(C1, C2) is the same as the “similarity” of h(C1) and h(C2) By hashing columns into buckets we expect that “most” pairs of near duplicate documents hash into the same bucket! Goal: Find a hash function h(·) such that: If sim(C1,C2) is high, then with high probability h(C1) = h(C2) If sim(C1,C2) is low, then with high probability h(C1) ≠ h(C2) Clearly, the hash function depends on the similarity metric: Not all similarity metrics have a suitable hash function! There is a suitable hash function for the Jaccard similarity: It is called Min-Hashing! 17 Minhashing Fall 2019 History: invented by Andrei Broder in 1997 (AltaVista) to detect near duplicate web pages Imagine the rows of the Boolean matrix permuted under random permutation π Define a “hash” function hπ(C) = the index of the first (in the permuted order π) row in which column C has value 1: hπ(C) = minπ π(C) 18 9 9
第 10 页
Fall 2019 Min-hashing Example 2nd element of the permutation is the first to map to a 1 in col 1 Permutations Input matrix Signature matrix M 1 4 3 1 0 1 0 2 1 2 1 3 2 4 1 0 0 1 2 1 4 1 7 1 7 0 1 0 1 1 2 1 2 6 3 6 0 1 0 1 2 6 1 0 1 0 1 h2(3)=4 (permutation 2, column 3) 5 7 2 1 0 1 0 4th element of the permutation is the first to map to a 1 in col 3 4 5 5 1 0 1 0 19 Fall 2019 Surprising Property The probability (over all permutations of the rows) that h(C1)=h(C2) is the same as Sim(C1, C2): Pr[hπ(C1) = hπ(C2)] = sim(C1,C2) With multiple signatures we get a good approximation Use several independent hash functions to create a signature of a column The similarity of signatures is the fraction of the hash functions in which they agree Because of the Min-Hash property, the similarity of columns is the same as the expected similarity of their signatures 20 10 10
第 11 页
Fall 2019 Why? 0 0 0 0 Let X be a column (set of shingles), y ∈ X is a shingle 1 1 Then: Pr[π(y) = min(π(X))] = 1/|X| 0 0 It is equally likely that any shingle y∈X is mapped to the 0 1 min element 1 0 Let y be s.t. π(y) = min(π(C1∪C2)) One of the two Then either: π(y) = min(π(C1)) if y ∈ C1 , or cols had to have π(y) = min(π(C )) if y ∈ C 1 at position y 2 2 So the prob. that both are true is the prob. y ∈ C1 ∩ C2 Pr[min(π(C1))=min(π(C2))]=|C1∩C2|/|C1∪C2|= sim(C ,C ) 1 2 21 Four Types of Rows Fall 2019 Given columns C1 and C2, rows may be classified as: C1 C2 a 1 1 1 in both columns b 1 0 columns are different c 0 1 d 0 0 0 in both columns Also, a = # rows of type a , etc. The ratio of type a, b, and c that determine the similarity and the probability that h(C1) = h(C2) Note Sim(C1,C2) = a /(a +b +c ) Then: Pr[h(C1)=h(C2)] = Sim(C1,C2) Look down the permuted columns C1 and C2 until we see a 1 If it’s a type-a row, then h(C1)=h(C2) If a type-b or type-c row, then not 22 11 11
第 12 页
Fall 2019 Min Hashing – Example Signature matrix M Input matrix 1 4 3 1 0 1 0 2 1 2 1 3 2 4 1 0 0 1 2 1 4 1 7 1 7 0 1 0 1 1 2 1 2 6 3 6 0 1 0 1 2 6 1 0 1 0 1 Similarities: 1-3 2-4 1-2 3-4 5 7 2 1 0 1 0 Col/Col 0.75 0.75 0 0 4 5 5 1 0 1 0 Sig/Sig 0.67 1.00 0 0 23 Fall 2019 MinHash – False Positive/Negative Instead of comparing sets, we now compare only 1 bit! False positive? False positive can be easily dealt with by doing an additional layer of checking (treat minhash as a filtering mechanism) False negative? Requiring full match of signature is strict, some similar sets will be lost High error rate! Can we do better? 24 12 12
第 13 页
Minhash Signatures Fall 2019 Pick (say) 100 random permutations of the rows Think of Sig(C) as a column vector Let Sig(C)[i] = min(πi(C)) according to the i th permutation, the number of the first row that has a 1 in column C Note: The sketch (signature) of column C is small ~400 bytes! We achieved our goal! We “compressed” long bit vectors into short signatures 25 Implementation Trick Fall 2019 Permuting rows even once is prohibitive Suppose 1 billion rows Hard to pick a random permutation from 1…billion Sorting would take a long time Representing a random permutation requires 1 billion entries A good approximation to permuting rows: pick 100 (?) hash functions hi Simulate the effect of a random permutation by a random hash function that maps row numbers to as many buckets as there are rows Row hashing: ordering under hi gives a random row permutation! One-pass implementation For each column C and each hash function hi, keep a “slot” M(i,C) for the min-hash value Intent: M(i,C) will become the smallest value of hi(r) for which column C has 1 in row r i.e., hi(r) gives order of rows for i th permutation 26 13 13
第 14 页
Implementation Fall 2019 M(i,C) = ∞ for each row r for each column C if C has 1 in row r // Scan rows looking for 1s for each hash function hi do // Suppose row r has 1 in column C if hi(r) is a smaller value than M(i,C) then M(i,C):= hi(r); How to pick a random hash function h(x)? Universal hashing: ha,b(x)=((a·x+b) mod p) mod N where: a,b … random integers p … prime number (p > N) 27 Fall 2019 Example Sig1 Sig2 h(1) = 1 1 ∞ g(1) = 3 3 ∞ Row C1 C2 h(2) = 2 1 2 1 1 0 g(2) = 0 3 0 2 0 1 Jaccard=1/5 3 1 1 h(3) = 3 1 2 4 1 0 g(3) = 2 2 0 5 0 1 h(4) = 4 1 2 h(x) = x mod 5 g(4) = 4 2 0 M(i,C) g(x) = 2x+1 mod 5 h(5) = 0 1 0 g(5) = 1 2 0 28 14 14
第 15 页
So far … Fall 2019 Represent a document as a set of hash values (of its k‐shingles) Transform set of k‐shingles to a set of minhash signatures Use Jaccard to compare two documents by comparing their signatures Is this method (i.e., transforming sets to signature) necessarily “better”?? 30 Fall 2019 Locality-Sensitive Hashing 31 15 15
第 16 页
The BIG Picture (All‐pair comparison) Fall 2019 Suppose, in main memory, a representation of a large number of objects May be signatures of documents as in minhashing We want to pair-wise compare each for finding those pairs that are sufficiently similar 32 Finding Similar Pairs Fall 2019 While the signatures of all columns may fit in main memory, comparing the signatures of all pairs of columns is quadratic in the number of columns Naïve solution For each document, compare with the other N‐1 documents Takes N‐1 comparisons Can be optimized using filter‐and‐refine mechanisms Requires N*(N‐1)/2 comparisons Example: 107 columns implies ~ 1014 column-comparisons At 1 μs/comparison 108 (~ 3 years!) 33 16 16
第 17 页
Locality-Sensitive Hashing Fall 2019 Use a function f(x,y) that tells whether or not x and y is a candidate pair: a pair of elements whose similarity must be evaluated With only one hash function on one entire column of signature, likely to have many false negatives Key idea: Apply the hash function on the columns of signature matrix M multiple times, each on a partition of the column Arrange that (only) similar columns are likely to hash (i.e., with high probability) to the same bucket Each pair of columns that hashes at least once into the same bucket is a candidate pair 34 Fall 2019 Candidate Generation from Minhash Signatures s Signature Matrix M Pick a similarity threshold , a fraction 0 < s < 1 Prob(M(C,i) == M(C’,i)) = sim(C,C’) A pair of columns x and y M(C,i) is a candidate pair if their hash signatures agree in at least function i fraction s of the rows i.e., M(i,x) = M(i,y) for at least fraction s n hash M(C’,i) values of i functions we expect documents x and y to have the same (Jaccard) similarity as their signatures signature for set C’ signature for set C 35 17 17
第 18 页
Fall 2019 Partition Into Bands Divide matrix M into b bands of r rows For each document, compute b n = b*r hash functions sets of r minhash values Each set is a mini-signature with r minhash functions (or a concatenation of the r r rows minhash values together) per band b bands b mini-signatures Matrix M 36 Partition into Bands Fall 2019 Columns 2 and 6 Buckets are probably For each band, hash its portion of identical each column (i.e., the concatenated Columns 6 and 7 values) to a hash table with k buckets are surely different Matrix M this has the “same” effect as ensuring all columns have the same values make k as large as possible to r rows minimize collision Candidate column pairs are those 1 2 3 4 5 6 7 b bands that hash to the same bucket for ≥ 1 band Tune b and r to catch most similar pairs, but few non-similar pairs 37 18 18
第 19 页
Fall 2019 Simplifying Assumption There are enough buckets that columns are unlikely to hash to the same bucket unless they are identical in a particular band Hereafter, we assume that “same bucket” means “identical in that band” Assumption needed only to simplify analysis, not for correctness of algorithm Finding all pairs within a bucket become computationally cheaper! Declare all pairs within a bucket to be “matching” OR Perform pair‐wise comparisons for those documents that fall into the same bucket Much smaller than pair‐wise over all documents 38 Example: Effect of Bands Fall 2019 Suppose 105 columns of M (100k docs) Signatures of 102 integers (rows) If each signature is represented as a 4 byte integer value, we need only 102*4*105 = 40Mb of memory! 5*109 pairs of signatures can take a while to compare Choose 20 bands of 5 integers/band Goal: Find pairs of documents that are at least s = 0.8 similar 39 19 19
第 20 页
Fall 2019 Suppose C1, C2 are 80% Similar Find pairs of ≥ s=0.8 similarity, set b=20, r=5 Assume: sim(C1, C2) = 0.8 Since sim(C1, C2) ≥ s, we want C1, C2 to be a candidate pair We want them to hash to at least 1 common bucket (at least one band is identical) Probability C1, C2 identical in one particular band: (0.8)5 = 0.328 Probability C1, C2 are not similar in all of the 20 bands: (1-0.328)20 = 0.00035 i.e., about 1/3000th of the 80%-similar column pairs are false negatives (we miss them) We would find 99.965% pairs of truly similar documents 40 Fall 2019 Suppose C1, C2 are 30% Similar Find pairs of ≥ s=0.8 similarity, set b=20, r=5 Assume: sim(C1,C2) = 0.3 Since sim(C1, C2) < s we want C1, C2 to hash to NO common buckets (all bands should be different) Probability C1, C2 identical in one particular band: (0.3)5 = 0.00243 Probability C1, C2 identical in at least 1 of 20 bands: 1-(1-0.00243)20 = 0.0474 In other words, approximately 4.74% pairs of docs with similarity 0.3 end up becoming candidate pairs They are false positives since we will have to examine them (they are candidate pairs) but then it will turn out their similarity is below threshold s 41 20 20
评论 (0)
暂无评论。快来抢沙发吧！