4Jaccard Similarity and Shingling

1 4 Jaccard Similarity and ShinglingWe will study how to define the distance between sets, specifically with the Jaccard distance. To illustrateand motivate this study, we will focus on using Jaccard distance to measure the distance between uses the common bag of words model, which is simplistic, but is sufficient for many start with some big questions. This lecture will only begin to answer them. Given two homework assignments (reports) how can a computer detect if one is likely to have beenplagiarized from the other withoutunderstandingthe content? In trying to index webpages, how does Google avoid listing duplicates or mirrors? How does a computer quickly understand emails, for either detecting spam or placing effective adver-tisers? (If an ad worked on one email , how can we determine which others are similar?)

2 The key to answering these questions will be convert the data (homeworks, webpages, emails) into anobject in anabstract spacethat we know how to measure distance, and how to do it efficiently. The mostobvious abstract space is Euclidean spaceRd. An objectv Rdcan be through of as ad-dimensional point(or vector)v= (v1, v2, .. , vd). The notation of a list of objects, separated by commas, inside parenthesis(and)represents anordered set; that is(a, b)6= (b, a). The Euclidean distance between two pointsv, u Rdis measureddE(u, v) = u v = d i=1(vi ui) is the commonstraight linedistance. We will return to this later, as it will not be immediately usefulfor distances between documents. Instead we will use a different abstract distance between (unordered) Sets and DistancesAsetis a (unordered) collection of objects{a, b, c}.

3 We use the notation as elements separated by commasinside curly brackets{and}. They are unordered so{a, b}={b, a}.Although we are interested in a distance, we will actually focus on a dual notion of asimilarity. Adistanced(A, B)has the properties: it is small if objectsAandBare close, it is large if they are far, it is (usually)0if they are the same, and it has value in[0, ].On the other hand, a similaritys(A, B)has the properties: it is large if the objectsAandBare close, it is small if they are far, it is (usually)1if they are the same, and it is in the range[0,1].Often we can convert between the two asd(A, B) = 1 s(A, B), however sometimes it is better to used(A, B) = s(A, A) +s(B, B) 2s(A, B). Both restrict the distance to be a bounded (non infinite)domain, that can be converted with atanmap if one Jaccard SimilarityConsider two setsA={0,1,2,5,6}andB={0,2,3,5,7,9}.

4 How similar areAandB?TheJaccard similarityis definedJS(A, B) =|A B||A B|=|{0,2,5}||{0,1,2,3,5,6,7,9}|=38= notation, given a setA, thecardinalityofAdenoted|A|counts how many elements are inA. Theintersectionbetween two setsAandBis denotedA Band reveals all items which are inbothsets. Theunionbetween two setsAandBis denotedA Band reveals all items which are thatJSsatisfies the properties of a approach is to add clustering. We may have some items which basically representthe same thing. We place these represent-the-same-thing objects in {0,1,2}C2={3,4}C3={5,6}C4={7,8,9}For instance,C1might representactionmovies,C2comedies,C3docum entaries, we can representAclu={C1, C3}andBclu={C1, C2, C3, C4}sinceAonly contains elementsfromC1andC3, whileBcontains elements from all clusters. The Jaccard distance of the clustered sets isnowJSclu(A, B) =JS(Aclu, Bclu)=|{C1, C2}||{C1, C2, C3, C4}|=24= Documents to SetsHow do we apply this set machinery to documents?

5 Bag of words vs. ShinglesThe first option is thebag of wordsmodel, where each document is treatedas an unordered set of more general approach is toshinglethe document. This takes consecutive words and group them as asingle object. Ak-shingleis a consecutive set ofkwords. So the set of all1-shingles is exactly the bag ofwords model. An alternative name tok-shingleis ank-gram. These mean the same :I am :Sam I :I do not like green eggs and :I do not like them, Sam I (k= 1)-shingles ofD1 D2 D3 D4are:{[I], [am], [Sam], [do], [not], [like],[green], [eggs], [and], [ham], [them]}.CS 6955 Data Mining; Spring 2013 Instructor: Jeff M. Phillips, University of UtahThe(k= 2)-shingles ofD1 D2 D3 D4are:{[I am], [am Sam], [Sam Sam], [Sam I],[am I], [I do], [do not], [not like], [like green], [green eggs], [eggs and],[and ham], [like them], [them Sam]}.

6 The set ofk-shingles of a document withnwords is at mostn k. The takes spaceO(kn)to store themall. Ifkis small, this is not a high overhead. Furthermore, the space goes down as items are can also createk-shingles at the character level. The(k= 3)-character shingles ofD1 D2are:{[iam], [ams], [msa], [sam], [ami], [mia]}.The(k= 4)-character shingles ofD1 D2are:{[iams], [amsa], [msam], [sams], [sami],[amia], [miam]}.Modeling choices. White space?Should we include spaces, and returns? has touch downversusthrew a touchdown. Capitalization?Samversus sam. Can help distinguish proper nouns. Punctuation?May be indication of education level, or dialects. For instance English is punctuateddifferently in US and India. Punctuation is used differently in new articles (very proper style), blogs(more informal), and twitter (what is punctuation?)

7 Characters vs. Words?Long enough shingles with characters can simulate words, but will havemorefalse positives. Can pick up other dialect patterns. But is less interpretable. How large shouldkbe?General rule: probability of (almost all) shingles is low, so a collision word-shingles: emailsk= 2or3(small documents), research articlesk= 3or4(large docu-ments), news articles, blog posts (in between).In English there are27characters (26letters +1whitespace). Withk= 5there are275 14millionspossible shingles. (Maybe in practice closer to205since some letters ( ,q,xare rarely used.) Count replicas?Typicallybag of wordscounts replicas, butshinglingdoes not. Stop words?Words like{a, you, for, the, to, and, that, it, is, ..}are verycommon, and calledstop words. Sometimes omit these (typically in bag of words).)

8 In Shingling canbe effective to say usek= 3where the first word must be a stop word:the pizza are many variations of these methods. Natural Language Processing (NLP) studies these variations,but also focuses on finding much richer representations of bodies of text. Identifying all nouns and verbs,and disambiguating words with multiple meaningswent to the retreatversusthe troops hadto Jaccard with ShinglesSo how do we put this together. Consider the(k= 2)-shingles for eachD1,D2,D3, andD4:D1:[I am], [am Sam]D2:[Sam I], [I am]D3:[I do], [do not], [not like], [like green], [green eggs],[eggs and], [and ham]D4:[I do], [do not], [not like], [like them], [them Sam], [Sam I], [I am]CS 6955 Data Mining; Spring 2013 Instructor: Jeff M. Phillips, University of UtahNow the Jaccard Similarity is as follows:JS(D1, D2) = 1/3 (D1, D3) = 0 = (D1, D4) = 1/8 = (D2, D3) = 0 = (D3, D4) = 2/7 (D3, D4) = 3/11 time we will see how to use this special abstract structure of sets to compute this distance (approxi-mately) very efficiently and at extremely large 6955 Data Mining; Spring 2013 Instructor: Jeff M.

9 Phillips, University of Utah