{"id":19097,"date":"2022-10-21T09:09:48","date_gmt":"2022-10-21T07:09:48","guid":{"rendered":"https:\/\/www.codemotion.com\/magazine\/?p=19097"},"modified":"2023-06-19T12:30:43","modified_gmt":"2023-06-19T10:30:43","slug":"fast-document-similarity-in-python-minhashlsh","status":"publish","type":"post","link":"https:\/\/www.codemotion.com\/magazine\/backend\/fast-document-similarity-in-python-minhashlsh\/","title":{"rendered":"Fast Document Similarity in Python (MinHashLSH)"},"content":{"rendered":"\n
\n\n\n\n

Why is document similarity more important than ever? In the big data era, it is always more frequent that companies need to detect similar items in their database. Imagine platforms like Kijiji<\/a> or Subito<\/a>, trying to detect people that constantly duplicate announcements on the platform to boost their visibility without paying for sponsorship offered by the platform.<\/p>\n\n\n\n

Assume for example the platform has 1000000 announcements and it wants to detect duplicates. If we try to check one by one all the pairs we need to check 499999500000 (half a trillion) pairs. If it takes a microsecond (0.000001 s) to check a pair, it would take 499999 seconds, which is approximately six days of computation just to check document similarity.<\/p>\n\n\n\n

In this article, we are going to explore data mining techniques to speed up the whole process of finding and checking document similarity. The whole algorithm is inspired by chapter 3 of the book “Mining of Massive Datasets”<\/a>.<\/p>\n\n\n\n

Dataset<\/h2>\n\n\n\n

In this document similarity guide, we will use some apartment announcements scraped from Kijiji<\/a> a few years ago. You can also download the whole complete example here<\/a>.
The file is a tsv file with header:<\/p>\n\n\n\n

Title<\/th>Short Description<\/th>Location<\/th>Price (Euro)<\/th>Timestamp<\/th>Url Adv<\/th><\/tr><\/thead>
Studio accessoria\u2026<\/td>Affitto studio a \u2026<\/td>Roma<\/td>450<\/td>12 ottobre, 11:32<\/td>https:\/\/www.kijij\u2026<\/td><\/tr>
Negozio 169Mq per\u2026<\/td>Privato affitta n\u2026<\/td>Prenestino \/ Casi\u2026<\/td>1.700<\/td>12 ottobre, 08:45<\/td>https:\/\/www.kijij\u2026<\/td><\/tr>
Negozio in tiburt\u2026<\/td>Negozio c\/1 roma \u2026<\/td>Tiburtino \/ Colla\u2026<\/td>6.000<\/td>17 October, 21:20<\/td>https:\/\/www.kijij\u2026<\/td><\/tr>
Studio medico via\u2026<\/td>Studio medico avv\u2026<\/td>Trieste \/ Somalia\u2026<\/td>200<\/td>17 October, 20:22<\/td>https:\/\/www.kijij\u2026<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

To read the dataset<\/a> we use the pandas<\/a> library:<\/p>\n\n\n

import<\/span> pandas as<\/span> pd\ndataset=pd.read_csv(\"dataset_rent_rome_kijiji.tsv\"<\/span>, sep=\"\\t\"<\/span>)<\/code><\/span>Code language:<\/span> JavaScript<\/span> (<\/span>javascript<\/span>)<\/span><\/small><\/pre>\n\n\n
Fast document similarity: step by step<\/h2>\n\n\n\n
In the following section we are going to see:<\/p>\n\n\n\n
    \n
  1. how to transform a document into a set using k-shingling<\/li>\n\n\n\n
  2. how to represent a set in a compressed way computing its signature in such a way that set similarity is preserved, using MinHashing.<\/li>\n\n\n\n
  3. how to implement a hashing function that hashes similar items in the same bucket, using LSH (locality-sensitive hashing).<\/li>\n<\/ol>\n\n\n\n
    Shingling of Document<\/h2>\n\n\n\n
    In literature, representing documents as sets is considered an effective way to identify lexically similar documents. The k-shingles<\/a> method represents a document as a set of the substrings of length k.
    For example, if your document is ‘I love pizza Margherita, a 6-shingle representation of the document based on characters, including spaces, can be {'I love', ' love ', 'love p', 'ove pi', ...}<\/code>. According to the use case, you can compose shingles of words instead of characters or eliminate whitespaces and others.
    In     Python<\/a>, we can implement a class that, given the parameter k and a document read into a string, returns the k-shingle set of a document:<\/p>\n\n\n
    class<\/span> shingler<\/span>:<\/span>\n    def<\/span> __init__<\/span>(self, k)<\/span>:<\/span>\n        if<\/span> k > 0<\/span>:\n            self.k = int(k)\n        else<\/span>:\n            self.k = 10<\/span>   \n    #inner class utility<\/span>\n    def<\/span> process_doc<\/span>(self, document)<\/span>:<\/span>\n        return<\/span> re.sub(\"( )+|(\\n)+\"<\/span>,\" \"<\/span>,document).lower()\n\n    def<\/span> get_shingles<\/span>(self, document)<\/span>:<\/span>\n        shingles = set()\n        document= self.process_doc(document)\n        for<\/span> i in<\/span> range(0<\/span>, len(document)-self.k+1<\/span> ):\n            shingles.add(document[i:i+self.k])\n        return<\/span> shingles<\/code><\/span>Code language:<\/span> Python<\/span> (<\/span>python<\/span>)<\/span><\/small><\/pre>\n\n\n
    And use it as follows:<\/p>\n\n\n
    >>> <\/span>doc = \"I love pizza Margherita!                     xd 1111@\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\"<\/span>\n>>> <\/span>shingler_instance = shingler(10<\/span>)\n>>> <\/span>shingles_set = shingler_instance.get_shingles(doc)\n>>> <\/span>shingles_set\n{' xd 1111@ '<\/span>, 'herita! xd'<\/span>, 'izza margh'<\/span>, 'e pizza ma'<\/span>, 'rgherita! '<\/span>, 'ta! xd 111'<\/span>, 'ita! xd 11'<\/span>, ' pizza mar'<\/span>, 'argherita!'<\/span>, 'rita! xd 1'<\/span>, 'zza marghe'<\/span>, 'a! xd 1111'<\/span>, 'a margheri'<\/span>, ' love pizz'<\/span>, 'erita! xd '<\/span>, 'love pizza'<\/span>, 'za margher'<\/span>, 'margherita'<\/span>, 'gherita! x'<\/span>, ' margherit'<\/span>, 'i love piz'<\/span>, 'pizza marg'<\/span>, 've pizza m'<\/span>, 'ove pizza '<\/span>, '! xd 1111@'<\/span>}<\/code><\/span>Code language:<\/span> Python<\/span> (<\/span>python<\/span>)<\/span><\/small><\/pre>\n\n\n
    Now we can check if two documents are similar using the Jaccard Similarity, a popular set similarity indicator:
    $$ J(s1, s2) = \\frac{|s1 \\cap s2|}{|s1 \\cup s2|} $$<\/p>\n\n\n\n
    In general, we might want to hash shingles to reduce their size, but even by hashing, they can take in a mean 4 times the size of the original document. So “what’s the point?” you might think. Let me introduce you to MinHashing.<\/p>\n\n\n\n
    Minhash – The signature of a set<\/h2>\n\n\n\n
    The minash of a set can be seen as its signature, which is a unique and short representation of the set with a fixed length. The magic of MinHashing for a set is that it preserves Jaccard similarity (more or less).<\/p>\n\n\n\n
    We can represent a set with its characteristic matrix: a matrix whose columns are sets and rows are elements. The matrix contains a 1 in all the cells that correspond to an element contained in a set.
    For example:
    S1 = {a, b}, S2 = {a, c} S3 = {a,b,c,d}
    | |S1|S2|S3|
    |-| -| -| -|
    |a| 1| 1| 1|
    |b| 1| 0| 1|
    |c| 0| 1| 1|
    |d| 0| 0| 1|<\/p>\n\n\n\n
    Ideally, the minhash function takes a random permutation of the rows and for each set return the first element with a 1 in the characteristic matrix with permuted rows:
    if the permutation is badc<\/code>, the characteristic matrix is
    | |S1|S2|S3|
    |-| -| -| -|
    |b| 1| 0| 1|
    |a| 1| 1| 1|
    |d| 0| 0| 1|
    |c| 0| 1| 1|<\/p>\n\n\n\n
    and the minhash values are
    Minhash(S1) = b
    Minhash(S2) = a
    Minhash(S3) = b<\/p>\n\n\n\n
    We obtain a signature of size n for the set if we compute minhash for n random permutations of the rows of the characteristic matrix.<\/p>\n\n\n\n
    Minhash in practice<\/h3>\n\n\n\n
    The permutation approach is not feasible in practice, hence once again we use hash functions to approximate. We define a family of hash functions as<\/p>\n\n\n
    import<\/span> hashlib\n# the family of hash functions, in this case, is the same function (sha1) applied with a different salt.<\/span>\nclass<\/span> hashFamily<\/span>:<\/span>\n    def<\/span> __init__<\/span>(self, i)<\/span>:<\/span>\n        self.resultSize = 8<\/span> # how many bytes we want back<\/span>\n        self.maxLen = 20<\/span> # how long can our salt be (in decimal)<\/span>\n        self.salt = str(i).zfill(self.maxLen)[-self.maxLen:]\n\n    def<\/span> get_hash_value<\/span>(self, el_to_hash)<\/span>:<\/span>\n        return<\/span> int(hashlib.sha1(str(el_to_hash).encode('utf-8'<\/span>) + self.salt.encode('utf-8'<\/span>)).hexdigest()[-self.resultSize:], 16<\/span>)\n\n# NOTE:<\/span> we use sha1 to avoid installing and importing an external library, sacrificing performances. No crypto-hash is required for this use case.<\/span><\/code><\/span>Code language:<\/span> Python<\/span> (<\/span>python<\/span>)<\/span><\/small><\/pre>\n\n\n
    Then we compute a minhash signature for a set with the following algorithm:<\/p>\n\n\n\n
      \n
    1. Take the first hash function, and apply it to all of the shingle values in a document. Find the minimum hash value produced and use it as the first component of the MinHash signature.<\/li>\n\n\n\n
    2. Now take the second hash function, and again find the minimum resulting hash value, and use this as the second component.<\/li>\n\n\n\n
    3. And so on\u2026<\/li>\n<\/ol>\n\n\n\n
      So if we have 10 random hash functions, we\u2019ll get a MinHash signature with 10 values for each set. We\u2019ll use the same 10 hash functions for every document in the dataset and generate their signatures as well.<\/p>\n\n\n
      from<\/span> random import<\/span> randint, seed\nclass<\/span> minhashSigner<\/span>:<\/span>\n    def<\/span> __init__<\/span>(self, sig_size)<\/span>:<\/span>\n        self.sig_size=sig_size\n        # Init the hash family of functions using a random salt<\/span>\n        self.hash_functions = [hashFamily(randint(0<\/span>,10000000000<\/span>)) for<\/span> i in<\/span> range(0<\/span>,sig_size)]\n\n    def<\/span> compute_set_signature<\/span>(self, set_)<\/span>:<\/span>\n        set_sig = []\n        for<\/span> h_funct in<\/span> self.hash_functions:\n            min_hash = math.inf\n            for<\/span> el in<\/span> set_:\n                h = h_funct.get_hash_value(el)\n                if<\/span> h < min_hash:\n                    min_hash = h\n\n            set_sig.append(min_hash)\n\n        return<\/span> set_sig\n    #return a list of lists that can be seen as the signature matrix<\/span>\n    def<\/span> compute_signature_matrix<\/span>(self, set_list)<\/span>:<\/span>\n        signatures = []\n        for<\/span> s in<\/span> set_list:\n            signatures.append( self.compute_set_signature(s) )\n        return<\/span> signatures<\/code><\/span>Code language:<\/span> Python<\/span> (<\/span>python<\/span>)<\/span><\/small><\/pre>\n\n\n
      Example usage:<\/p>\n\n\n
      >>> <\/span>doc = \"Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.\"<\/span>\n>>> <\/span>doc2 = \"Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident bla bla bla.\"<\/span>\n>>> <\/span>shingler_inst = shingler(10<\/span>)\n>>> <\/span>shinglings = shingler_inst.get_shingles(doc)\n>>> <\/span>shinglings2 = shingler_inst.get_shingles(doc2)\n>>> <\/span>minhash_sig = minhashSigner(20<\/span>).compute_signature_matrix([shinglings,shinglings2])\n>>> <\/span>minhash_sig\n[[1783860<\/span>, 5303198<\/span>, 4845898<\/span>, 3935831<\/span>, 198103<\/span>, 5887007<\/span>, 8061377<\/span>, 4526224<\/span>, 8467452<\/span>, 7766250<\/span>, 15505788<\/span>, 825368<\/span>, 12316643<\/span>, 4502308<\/span>, 6403903<\/span>, 9259449<\/span>, 8533874<\/span>, 31889076<\/span>, 940623<\/span>, 278359<\/span>], [1783860<\/span>, 20203690<\/span>, 4845898<\/span>, 3935831<\/span>, 198103<\/span>, 12350289<\/span>, 8061377<\/span>, 4526224<\/span>, 8467452<\/span>, 7766250<\/span>, 15505788<\/span>, 825368<\/span>, 12316643<\/span>, 6122847<\/span>, 6403903<\/span>, 9259449<\/span>, 8533874<\/span>, 31889076<\/span>, 940623<\/span>, 278359<\/span>]]\n>>>\n>>> <\/span>set_sig_1 = set(minhash_sig[0<\/span>])\n>>> <\/span>set_sig_2 = set(minhash_sig[1<\/span>])\n>>> <\/span>jaccard_similarity_sig = len(set_sig_1.intersection(set_sig_2))\/len(set_sig_1.union(set_sig_2))\n>>> <\/span>jaccard_similarity_sig\n0.7391304347826086<\/span>\n>>>\n>>> <\/span>jaccard_similarity_shingle_set = len(set(shinglings).intersection(shinglings2))\/len(set(shinglings).union(shinglings2))\n>>> <\/span>jaccard_similarity_shingle_set\n0.8285077951002228<\/span><\/code><\/span>Code language:<\/span> Python<\/span> (<\/span>python<\/span>)<\/span><\/small><\/pre>\n\n\n
      From the example, we can see that the Jaccard similarity between set signatures is near to the similarity between shingle sets. Of course, we can achieve a lower approximation error by tuning the shingle size and signature size.<\/p>\n\n\n\n
      Locality Sensitive Hashing<\/h2>\n\n\n\n
      Quoting “Mining of Massive Datasets”<\/a><\/p>\n\n\n\n
      ‘Locality-sensitive hashing (also known as near-neighbor search) is a general theory focused on how to approximatively find similar pairs without investigating all of them. The principle is that we are going to hash items several times in such a way that similar items are more likely to be hashed to the same bucket than dissimilar items are.’<\/em>

      <\/em>When you have a minhashed set a popular choice for LSH is the “banding technique”, that is:<\/p>\n\n\n\n
        \n
      1. get the signature matrix and divide it into bands<\/li>\n\n\n\n
      2. hash each column of the band. The elements that hash to the same bucket are likely to be similar.<\/li>\n\n\n\n
      3. repeat for all the bands. You can use the same hash function of the previous band but you must use different buckets.<\/li>\n<\/ol>\n\n\n\n
        In python:<\/p>\n\n\n
        class<\/span> lsh<\/span>:<\/span>\n    def<\/span> __init__<\/span>(self, threshold=0.8<\/span>)<\/span>:<\/span>\n        self.threshold = threshold\n    def<\/span> get_signature_matrix_bands<\/span>(self, sig_matrix, bands_nr, sign_len)<\/span>:<\/span> \n        #bands_nr = b<\/span>\n        #sign_len = n<\/span>\n        r = int(sign_len\/bands_nr) #number of rows in each band<\/span>\n        bands = {} # {band_nr: [col_1,col_2,...]} where col_1 is all the values of Sig(S_i) for band b.<\/span>\n        for<\/span> i in<\/span> range(0<\/span>,bands_nr):\n            bands[i] = []\n        # put Subsets of the columns of signature matrix into the appropriate bucket and cosider a column <\/span>\n        # as a unique block so that we can hash the entire column.<\/span>\n        # Basically a band is a list of element, where each element is a subset of a signature of a given set.<\/span>\n        for<\/span> signature in<\/span> sig_matrix: \n            for<\/span> i in<\/span> range(0<\/span>, bands_nr):\n                idx = i*r    \n                bands[i].append(' '<\/span>.join(str(x) for<\/span> x in<\/span> signature[idx:idx+r]) )          \n        return<\/span> bands\n    #band is a list <\/span>\n    # construct a dictionary {hash(band_column): doc_id that produced this hash}<\/span>\n    def<\/span> get_band_buckets<\/span>(self, band, hash_funct)<\/span>:<\/span>\n        buckets = {}\n        for<\/span> doc_id in<\/span> range(0<\/span>,len(band)):\n            value = hash_funct.get_hash_value( band[doc_id] )\n            if<\/span> value not<\/span> in<\/span> buckets:\n                buckets[value] = [doc_id]\n            else<\/span>:\n                buckets[value].append(doc_id)      \n        return<\/span> buckets\n    def<\/span> get_candidates_list<\/span>(self, buckets)<\/span>:<\/span>\n        candidates = set()\n        # buckets is a dictionary containing key=bucket, value= list of doc_ids that hashed to bucket<\/span>\n        for<\/span> bucket,candidate_list in<\/span> buckets.items():\n            if<\/span> len(candidate_list) > 1<\/span>:\n                for<\/span> i in<\/span> range(0<\/span>,len(candidate_list)-1<\/span>):\n                    for<\/span> j in<\/span> range(i+1<\/span>,len(candidate_list)):  \n                        pair = tuple(sorted( (candidate_list[i],candidate_list[j]) ))\n                        candidates.add(pair)\n\n        return<\/span> candidates #ie a set of couples, each couple is a candidate pair<\/span>\n    def<\/span> check_candidates<\/span>(self, candidates_list, threshold, sigs)<\/span>:<\/span>\n        similar_docs = set() #set of tuples<\/span>\n        # similar_pair is a couple containing doc_ids of documents that hashed to same bucket<\/span>\n        for<\/span>  similar_pair in<\/span> candidates_list:\n            #for all the pairs of document in the list check similarity of their signatures<\/span>\n            doc_id_1 = similar_pair[0<\/span>]\n            doc_id_2 = similar_pair[1<\/span>]\n            signature_1 = set(sigs[doc_id_1]) #get the i-th column from signature matrix where i is doc_id in the collision list<\/span>\n            signature_2 = set(sigs[doc_id_2])\n            js = len(signature_1.intersection(signature_2)) \/len(signature_1.union(signature_2))\n            if<\/span> js >= threshold:\n                similar_docs.add( tuple(sorted((doc_id_1,doc_id_2) )) )          \n        return<\/span> similar_docs\n    def<\/span> get_similar_items<\/span>(self, sig_matrix, bands_nr, sign_len)<\/span>:<\/span>\n        similar_docs = set()\n        #divide signature matrix into bands<\/span>\n        bands = lsh_instance.get_signature_matrix_bands(sig_matrix,bands_nr,sign_len)\n        #for all the bands<\/span>\n        for<\/span> band_id, elements in<\/span> bands.items():\n            #produce the buckets for the given band (band_id) with a random hash function<\/span>\n            buckets = lsh_instance.get_band_buckets(elements, hash_funct=hashFamily(randint(0<\/span>,10000000000<\/span>)))\n            #Get all the candidate pairs<\/span>\n            candidates = lsh_instance.get_candidates_list(buckets)\n            #Check all candidate pairs' signatures<\/span>\n            for<\/span> sim_tuple in<\/span> lsh_instance.check_candidates(candidates, self.threshold, sig_matrix):\n                similar_docs.add( sim_tuple)\n        return<\/span> similar_docs #return all the similar signatures that respect the threshold<\/span><\/code><\/span>Code language:<\/span> Python<\/span> (<\/span>python<\/span>)<\/span><\/small><\/pre>\n\n\n
        The class performs the following tasks:<\/p>\n\n\n\n
          \n
        1. Divide signature matrix into bands with get_signature_matrix_bands(sig_matrix, bands_nr, sign_len)<\/code>. The method will return a list of strings where each string represents a column of the signature matrix for the given band. It is done to hash the entire column next when producing buckets.<\/li>\n\n\n\n
        2. Compute buckets for each band with get_band_buckets(band, hash_funct)<\/code>, which will take as input a band b<\/code> and a hash function h<\/code> and will return a dict containing as key the bucket ids and as value a list of document ids that hashed to that bucket for the given band b<\/code>: ${bucket_{id}:[doc_i, doc_k, \u2026] } $.<\/li>\n\n\n\n
        3. With get_candidates_list(buckets)<\/code> we are going to take as input a list of buckets (whose union is the signature matrix) and will produce as output a set of tuples: those tuples represent documents that are hashed in the same bucket.<\/li>\n\n\n\n
        4. With check_candidates(candidates_list, threshold, sigs)<\/code> we take all the candidates from all the bands and check if effectively their signatures produce a match with approximate Jaccard similarity greater than the threshold we give as a parameter.<\/li>\n\n\n\n
        5. With get_similar_items(sig_matrix, bands_nr, sign_len)<\/code> we put together all the methods listed above and return the ids of similar documents that respect the threshold value.<\/li>\n<\/ol>\n\n\n\n
          The similarity threshold is passed as a value to the constructor of the class, default is 0.8.<\/p>\n\n\n\n
          Example usage:<\/p>\n\n\n
          >>> <\/span>shingler_inst = shingler(10<\/span>)\n>>> <\/span>doc = \"Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.\"<\/span>\n>>> <\/span>doc2 = \"Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident bla bla bla.\"<\/span>\n>>>\n>>> <\/span>shinglings = shingler_inst.get_shingles(doc)\n>>> <\/span>shinglings = shingler_inst.get_hashed_shingles(shinglings)\n>>>\n>>> <\/span>shingle2 = shingler_inst.get_shingles(doc2)\n>>> <\/span>shingle2 = shingler_inst.get_hashed_shingles(shingle2)\n>>>\n>>> <\/span>signer = minhashSigner(100<\/span>)\n>>> <\/span>signature_matrix = signer.compute_signature_matrix([shinglings,shingle2])\n>>> <\/span>lsh_instance = lsh(threshold=0.7<\/span>)\n>>> <\/span>lsh_instance.get_similar_items(signature_matrix,10<\/span>,100<\/span>)\n{(0<\/span>, 1<\/span>)}<\/code><\/span>Code language:<\/span> Python<\/span> (<\/span>python<\/span>)<\/span><\/small><\/pre>\n\n\n
          Benchmark Time<\/h2>\n\n\n\n
          Now that we have implemented the whole code for fast approximate duplicate document detection, let’s test it out against brute force detection and see what happens.
          As the first step, we load the           dataset<\/a> as a pandas data frame.<\/p>\n\n\n
          print(\"Loading dataset...\"<\/span>)\ndataset=pd.read_csv(\"dataset_rent_rome_kijiji.tsv\"<\/span>, sep=\"\\t\"<\/span>)\ndataset['doc_id'<\/span>]=dataset.index\ndoc_nr = dataset['doc_id'<\/span>].max()\nprint(\"Dataset loaded correctly.\"<\/span>)<\/code><\/span>Code language:<\/span> Python<\/span> (<\/span>python<\/span>)<\/span><\/small><\/pre>\n\n\n
          Then transform documents into k-shingles.<\/p>\n\n\n
          print(\"Producing Shingles...\"<\/span>)\nstart_time = time.time()\n#an array where the index i represent the document_id and the element shingling_list[i] the hashed shingles for document document_id<\/span>\nshingling_list = [None<\/span>] * (doc_nr +1<\/span>) \nshingling_size = 10<\/span>\nsignature_size = 50<\/span>\nbands_nr = 10<\/span>\n\nshingler_inst = shingler(shingling_size)\n\n#produce hashed shinglings for all documents<\/span>\nfor<\/span> index, row in<\/span> dataset.iterrows():\n    doc = row['Title'<\/span>]+\" \"<\/span>+row['Short Description'<\/span>]\n    i = row['doc_id'<\/span>]\n\n    shinglings = shingler_inst.get_hashed_shingles( shingler_inst.get_shingles(doc) )\n    shingling_list[i] = shinglings\n\nend_time = time.time()\nprint(\"Shingles produced in:\\t %.2f seconds.\"<\/span>%(end_time - start_time))<\/code><\/span>Code language:<\/span> Python<\/span> (<\/span>python<\/span>)<\/span><\/small><\/pre>\n\n\n
          And we sign all the shingles and get the signature matrix.<\/p>\n\n\n
          signer = minhashSigner(signature_size)\nstart_time = time.time()\nprint(\"Computing signature matrix...\"<\/span>)\n#produce a signature for each shingle set<\/span>\nsignature_matrix = signer.compute_signature_matrix( shingling_list )\nend_time = time.time()\nprint(\"Signature Matrix computed in:\\t %.2f seconds.\"<\/span> %(end_time - start_time))<\/code><\/span>Code language:<\/span> Python<\/span> (<\/span>python<\/span>)<\/span><\/small><\/pre>\n\n\n
          In the end, we compute similar pairs with LSH.<\/p>\n\n\n
          lsh_instance = lsh(threshold=0.8<\/span>)\nstart_time = time.time()\nprint(\"Computing LSH similarity...\"<\/span>)\nlsh_similar_itemset = lsh_instance.get_similar_items(signature_matrix, bands_nr, signature_size)\nend_time = time.time()\nlsh_computation_time = end_time - start_time\nprint(\"LSH Similarity computed in:\\t %.2f seconds.\\nSimilar Elements Found: %d\"<\/span> %(lsh_computation_time,len(lsh_similar_itemset)))<\/code><\/span>Code language:<\/span> Python<\/span> (<\/span>python<\/span>)<\/span><\/small><\/pre>\n\n\n
          We compute similar pairs using brute force<\/p>\n\n\n
          class<\/span> bfsc<\/span>()<\/span>:<\/span>\n    def<\/span> compare_shingles_set_js<\/span>(self, set1, set2)<\/span>:<\/span>\n        return<\/span> len(set1.intersection(set2))\/len(set1.union(set2))\n\nbrute_force_comparer = bfsc()\nbrute_force_similar_items = set()\nstart_time = time.time()\n\nfor<\/span> i in<\/span> range(0<\/span>,doc_nr-1<\/span>):\n    for<\/span> j in<\/span> range(i+1<\/span>,doc_nr):\n        similarity = brute_force_comparer.compare_shingles_set_js(set(shingling_list[i]),set(shingling_list[j]))\n        if<\/span> similarity >= 0.8<\/span>:\n            brute_force_similar_items.add( (i,j) ) \n\nend_time = time.time()\nbf_computation_time = end_time - start_time      <\/code><\/span>Code language:<\/span> Python<\/span> (<\/span>python<\/span>)<\/span><\/small><\/pre>\n\n\n
          Check for similar pairs<\/p>\n\n\n\n
            \n
          1. LSH<\/li>\n<\/ol>\n\n\n
            docs = lsh_similar_itemset.pop()\nprint(\"Doc 1:\"<\/span>)\nprint(dataset.iloc[docs[0<\/span>]] )\nprint(\"Is similar to\\nDoc2:\"<\/span>)\nprint(dataset.iloc[docs[1<\/span>]] )<\/code><\/span>Code language:<\/span> Python<\/span> (<\/span>python<\/span>)<\/span><\/small><\/pre>\n\n\n
              \n
            1. Brute Force<\/li>\n<\/ol>\n\n\n
              docs = brute_force_similar_items.pop()\nprint(\"Doc 1:\"<\/span>)\nprint(dataset.iloc[docs[0<\/span>]] )\nprint(\"Is similar to\\nDoc2:\"<\/span>)\nprint(dataset.iloc[docs[1<\/span>]] )<\/code><\/span>Code language:<\/span> Python<\/span> (<\/span>python<\/span>)<\/span><\/small><\/pre>\n\n\n
              Print stats<\/p>\n\n\n
              report = ('LSH\\n%.2f seconds to execute\\n'<\/span>\n    '%d similar documents found\\n\\n'<\/span>\n    'Bruteforce search\\n%.2f seconds to execute\\n'<\/span>\n    '%d similar documents found.\\n\\n'<\/span>\n    'They find %d common similarities.'<\/span>)\n\nprint(report %(lsh_computation_time, len(lsh_similar_itemset),bf_computation_time,len(brute_force_similar_items),len(brute_force_similar_items.intersection(lsh_similar_itemset)) ))<\/code><\/span>Code language:<\/span> Python<\/span> (<\/span>python<\/span>)<\/span><\/small><\/pre>\n\n\n
              Conclusion<\/h2>\n\n\n\n
              In this article about checking document similarity we have seen:<\/p>\n\n\n\n
                \n
              1. how to transform a document into a set using k-shingling<\/li>\n\n\n\n
              2. how to represent a set in a compressed way computing its signature in such a way that set similarity is preserved, using MinHashing.<\/li>\n\n\n\n
              3. how to implement a hashing function that hashes similar items in the same bucket, using LSH (locality-sensitive hashing).<\/li>\n\n\n\n
              4. how to compare the approximate method with the brute force method.<\/li>\n<\/ol>\n\n\n\n
                All the theory behind the code here can be found in chapter 3 of the book “Mining of Massive Datasets”<\/a><\/p>\n\n\n\n
                You can find the full example on GitHub<\/a>. I wrote also a notebook with an Apache Spark implementation, available on GitHub<\/a>.<\/p>\n\n\n\n
                Despite it is interesting to understand how that algorithm works, it is always a good idea to check for robust libraries to put this algorithm in production. A lot of how implementations exist depends on the use case, here are a few:<\/p>\n\n\n\n