Join thousands of AI enthusiasts and experts at the Learn AI Community.

Publication

Latest

Text Similarity using K-Shingling, Minhashing and LSH(Locality Sensitive Hashing)

Last Updated on October 29, 2021 by Editorial Team

Author(s): Supriya Ghosh

Natural Language Processing

Text Similarity using K-Shingling, Minhashing, and LSH(Locality Sensitive Hashing)

Text similarity plays an important role in Natural Language Processing (NLP) and there are several areas where this has been utilized extensively. Some of the applications include Information retrieval, text categorization, topic detection, machine translation, text summarization, document clustering, plagiarism detection, news recommendation, etc. encompassing almost allย domains.

But sometimes, it becomes difficult to understand the concept behind the Text Similarity Algorithms. This write-up will show an implementation of Text Similarity along with an explanation of the required concepts.

But before I start, let me tell you that there might be several ways and several algorithms to perform the same task. I will use one of the ways for depiction using K-Shingling, Minhashing, and LSH(Locality Sensitive Hashing).

Dataset considered is Text Extract from 3 documents for the problem atย hand.

We can use nโ€Šโ€”โ€Šnumber of documents with each document being of significant length. But to make it simpler and avoid heavy computations, I am considering a small chunk from each document.

Letโ€™s perform the implementation inย Steps.

Step 1ย :

Set your working directory to the folder where the files are placed so that R can read it. Then read all the input files from the working directory using the belowย code.

# Libraries used
library(dplyr)
library(proxy)
library(stringr)
library(data.table)
# Set the working directory
setwd(".\")
# Read the original text file 
files <- list.files(path=".", pattern='*.txt', all.files=FALSE,
full.names=FALSE)
( doc <- lapply( files, readLines ) )

R Studio Inputย Display

Step 2ย :

Preprocess the text to remove punctuation, convert it into lower cases, and split text into word byย word.

# Preprocess text
documents <- lapply(doc, function(x) {
text <- gsub("[[:punct:]]", "", x) %>% tolower()
text <- gsub("\\s+", " ", text) %>% str_trim()
word <- strsplit(text, " ") %>% unlist()
return(word)
})
# Print the texts in files
documents[[1]]
documents[[2]]
documents[[3]]

R Studioย Display

Step 3ย :

Introduce K-Shingling which is a technique of representing documents assets. We will understand further the importance of K-Shingling but as of now, we can just try getting familiar with theย Steps.

K-shingle of a document at hand is said to be all the possible consecutive sub-string of length k found inย it.

Letโ€™s illustrate with an example with k =ย 3.

Shingling <- function(document, k) {
shingles <- character( length = length(document) - k + 1 )

for( i in 1:( length(document) - k + 1 ) ) {
shingles[i] <- paste( document[ i:(i + k - 1) ], collapse = " " )
}

return( unique(shingles) )
}
# "shingle" the example document, with k = 3
documents <- lapply(documents, function(x) {
Shingling(x, k = 3)
})
list( Original = doc[[1]], Shingled = documents[[1]] )

R Studioย Display

Hence with k = 3, the k-shingles of the first document which got printed out, consist of sub-strings of lengthย 3.

The first K-Shingle is: โ€œthe nightย isโ€

The second Shingle is: โ€œnight is darkโ€ and soย on.

One important point to note is that a documentโ€™s k-shingle set should be unique. For example, if the first document above contains more than one โ€œthe night isโ€ then it will only appear once as the set of k-shingle for that document.

Step 4:

Construct a โ€œCharacteristicโ€ matrix that visualizes the relationships between the three documents. The โ€œcharacteristicโ€ matrix will be a Boolean matrix, withย :

rows = the elements of every unique possible combination of shingles set across all documents.

columns = one column per document.

Thus, the matrix will be filled with 1 in row i and column j if and only if document j contains the shingle iย , otherwise it will be filled withย 0.

Let us try to understand this with the below depiction.

# Unique shingles sets across all documents
doc_dict <- unlist(documents) %>% unique()
# "Characteristic" matrix
Char_Mat <- lapply(documents, function(set, dict) {
as.integer(dict %in% set)
}, dict = doc_dict) %>% data.frame()
# set the names for both rows and columns
setnames( Char_Mat, paste( "doc", 1:length(documents), sep = "_" ) )
rownames(Char_Mat) <- doc_dict
Char_Mat

R Studioย Display

The first row of the above matrix has all three columns as 1. This is because all three documents contain the 3-shingle โ€œthe nightย isโ€.

For the second column, the value is [1, 0, 1] which means that document 2 does not have the 3-shingle โ€œnight is dark, while document 1 and 3ย has.

One important point noted here is that most of the time these โ€œcharacteristic matricesโ€ are almost sparse. Therefore, we usually try to represent these matrices only by the positions in which 1 appears, so as to be more space-efficient.

Step 5ย :

After creating shingle sets and characteristic matrix, we now need to measure the similarity between documents.

We will make use of Jaccard Similarity for thisย purpose.

For example, with two shingle sets as set1 and set2, the Jaccard Similarity will beย :

With this we will calculate the pairwise Jaccard similarities for all three documents. โ€œdistโ€ function in โ€œRโ€ quickly computes and returns the distance/similarity matrix.

# how similar is two given document, Jaccard similarity 
JaccardSimilarity <- function(x, y) {
non_zero <- which(x | y)
set_intersect <- sum( x[non_zero] & y[non_zero] )
set_union <- length(non_zero)
return(set_intersect / set_union)
}
# create a new entry in the registry
pr_DB$set_entry( FUN = JaccardSimilarity, names = c("JaccardSimilarity") )
# Jaccard similarity distance matrix 
d1 <- dist( t(Char_Mat), method = "JaccardSimilarity" )
# delete the new entry
pr_DB$delete_entry("JaccardSimilarity")
d1
doc

R Studioย Display

The similarity matrix d1 tells us that document 1 and 3 is the most similar among the three documents.

For small datasets, the above method works perfectly fine, but imagine if we have a large number of documents to compare instead of just three that too with significantly larger lengths, then the above method might not scale well, and we might have heavy computation with performance issue building up as the sparse matrices with a set of unique shingles across all documents will be fairly large, making computation of the Jaccard similarity between the documents aย burden.

Under such situations, we employ a different technique that help us save computations and can compare document similarities on a large scale efficiently. The technique is called Minhashing.

Step 6ย :

Minhashing involves compressing the large sets of unique shingles into a much smaller representation called โ€œsignaturesโ€.

We then use these signatures to measure the similarity between documents.

Although it is impossible for these signatures to give the exact similarity measure, the estimates are prettyย close.

The larger the number of signatures chosen, the more accurate the estimateย is.

For illustration let us consider anย example.

Suppose we take up the above example to minhash characteristic matrix of 16 rows into 4 signatures. Then the first step is to generate 4 columns of randomly permutated rows that are independent of each other. We can see for ourselves that this simple hash function does in fact generate random permutated rows. To generate this, we use theย formula:

Whereย :

x is the row numbers of your original characteristic matrix.

a and b are any random numbers smaller or equivalent to the maximum number of x, and they both must be unique in each signature.

For e.g. For signature 1, if 5 is generated to serve as a- coefficient, it must be ensured that this value does not serve as a- coefficient multiple times within signature 1, though it can still be usedย as

b- coefficient in signature 1. And this restriction refreshes for the next signature as well, that is, 5 can be used to serve as a or b coefficient for signature 2, but again no multiple 5 for signature 2โ€™s a or b coefficient and soย on.

c is a prime number slightly larger than the total number of shingleย sets.

For the above example set, since the total row count is 16, thus prime number 17 will doย fine.

Now letโ€™s generate this through the โ€œRโ€ย code.

# number of hash functions (signature number)
signature_num <- 4
# prime number
prime <- 17
# generate the unique coefficients  
set.seed(12345)
coeff_a <- sample( nrow(Char_Mat), signature_num )
coeff_b <- sample( nrow(Char_Mat), signature_num )
# see if the hash function does generate permutations
permute <- lapply(1:signature_num, function(s) {
hash <- numeric( length = length(nrow(Char_Mat)) )
for( i in 1:nrow(Char_Mat) ) {
hash[i] <- ( coeff_a[s] * i + coeff_b[s] ) %% prime
}
return(hash)
})
# # convert to data frame
permute_df <- structure( permute, names = paste0( "hash_", 1:length(permute) ) ) %>%
data.frame()
permute_df

R Studioย Display

From the above output, we see that the 4 columns of randomly permutated rows got generated. There are 0s also, but it will not affect our computation and we will see thisย later.

Step 7ย :

Using the randomly permutated rows, now signatures will be calculated further. The signature value of any column (document) is obtained by using the permutated order generated by each hash function, the number of the first row in which the column has aย 1.

What we will do further is combine randomly permutated rows (generated by hash functions) with the original characteristic matrix and change the row names of the matrix to its row number to illustrate the calculation.

# use the first two signature as an example
# bind with the original characteristic matrix
Char_Mat1 <- cbind( Char_Mat, permute_df[1:2] )
rownames(Char_Mat1) <- 1:nrow(Char_Mat1)
Char_Mat1

R Studioย Display

Now considering the matrix generated above, we will start with the first hash function (hash_1).

According to our first hash functionโ€™s permutated row order, the first row is row 14 ( why row 14ย ? because 0 is the smallest value for our randomly generated permutation, and it has a 0 in row 14, making it the first row ). Then weโ€™ll look at row 14โ€™s entry for all three documents and try to find โ€œwhich documentโ€™s entry at row 14 is a 1ย ?โ€. document 3โ€™s (doc_3) row 14 is a 1, thus the signature value for document 3 generated by our first hash function is 0. But documents 2 and 3โ€™s entries at row 14 are both 0, thus weโ€™ll have to continueย looking.

According to our first hash functionโ€™s permutated row order, the second row is row 8 ( 1 is the second smallest value for our randomly generated permutation, and it has a value of 1 at row 8 ). We apply the same concept as above and find that document 2โ€™s (doc_2) entry for row 8 is a 1, thus the signature value for document 2 generated by our first hash function is 1. Note that weโ€™re already done with document 3, we do not need to check if it contains a 1 anymore. But weโ€™re still not done, document 1โ€™s entry at row 8 is still a 0. Hence, weโ€™ll have to lookย further.

Again, checking the permutated row order for our first hash function, the third row is row 2. document 1โ€™s entry for row 2 is 1. Therefore, weโ€™re done with calculating the signature values for all three columns using our first hash function!! Which are [2, 1,ย 0].

We can then apply the same notion to calculate the signature value for each column (document) using the second hash function, and so on for the third, fourth, etc. A quick look at the signature second hash function shows that the first row according to its permutated row order is row 8 and doc_2 has a 1 in row 3. Similarly, the second row is row 14 with doc_3 as 1 and the third row is row3 with doc_1 as 1. Hence, the signature values generated by our second hash function for all three documents are [2, 0,ย 1].

As for these calculated signature values, we will store them into a signature matrix along the way, which will later replace the original characteristic matrix. The following section will calculate the signature values for all 3 columns using all 4 hash functions and print out the signature matrix.

# obtain the non zero rows' index for all columns
non_zero_rows <- lapply(1:ncol(Char_Mat), function(j) {
return( which( Char_Mat[, j] != 0 ) )
})
# initialize signature matrix
SM <- matrix( data = NA, nrow = signature_num, ncol = ncol(Char_Mat) )
# for each column (document)
for( i in 1:ncol(Char_Mat) ) {
# for each hash function (signature)'s value
for( s in 1:signature_num ) {
SM[ s, i ] <- min( permute_df[, s][ non_zero_rows[[i]] ] )
}
}
# set names for clarity
colnames(SM) <- paste( "doc", 1:length(doc), sep = "_" )
rownames(SM) <- paste( "minhash", 1:signature_num, sep = "_" )
SM

R Studioย Display

Our signature matrix has the same number of columns as the original characteristic matrix, but it only has n rows, where n is the number of hash functions we wish to generate (in this caseย 4).

Let me elaborate on how do we interpret the aboveย result?

For e.g., for documents 1 and 3 (columns 1 and 3), its similarity would be 0.25 because they only agree in 1 row out of a total of 4 (both columnsโ€™ row 4 isย 1).

Letโ€™s calculate the same explanation throughย code.

# signature similarity
SigSimilarity <- function(x, y) mean( x == y )
# same trick to calculate the pairwise similarity 
pr_DB$set_entry( FUN = SigSimilarity, names = c("SigSimilarity") )
d2 <- dist( t(SM), method = "SigSimilarity" )
pr_DB$delete_entry("SigSimilarity")
list(SigSimilarity = d2, JaccardSimilarity = d1)

R Studioย Display

From the difference of the result between the original Jaccard similarity and the new similarity obtained using the signature similarity, we might doubt if this is an accurate estimate? But as mentioned earlier, Minhash's purpose is to provide a fast โ€œapproximationโ€ to the true Jaccard similarity and the estimate can be closer but not 100% accurate hence the difference. Also, the example considered here is way too small to depict closer accuracy using the law of large numbers. More accurate and close results are expected with large datasets.

In cases where the primary requirement is to compute the similarity of every possible pair, probably for text clustering or so, then LSH (Locality Sensitive Hashing) does not serve the purpose but if the requirement is to find the pairs that are most likely to be similar, then a technique called Locality Sensitive Hashing can be employed further which I am discussing below.

Locality Sensitive Hashing

While the information necessary to compute the similarity between documents has been compressed from the original sparse characteristic matrix into a much smaller signature matrix, but the underlying problem or need to perform pairwise comparisons on all the documents stillย exists.

The concept for locality-sensitive hashing (LSH) is that given the signature matrix of size n (row count), we will partition it into b bands, resulting in each band with r rows. This is equivalent to the simple math formulaโ€Šโ€”โ€Šn = br, thus when we are doing the partition, we have to be sure that the b we choose is divisible by n. Using the signature matrix above and choosing the band size to be 2 the above example will becomeย :

# number of bands and rows
bands <- 2
rows <- nrow(SM) / bands
data.frame(SM) %>% 
mutate( band = rep( 1:bands, each = rows ) ) %>%
select( band, everything() )

R Studioย Display

What locality-sensitive hashing tells us is: If the signature values of two documents agree in all the rows of at least one band, then these two documents are likely to be similar and should be compared (list it as the candidate pair). Using this small set of documents might be a bad example since it can happen that none of them will get chosen as our candidate pair. For instance, if the signature value of document 2 for band 1 becomes [ 0, 1 ] instead of the current [ 1, 0 ], then document 2 and document 3 will become a candidate pair as both of their rows in band1 takes the same value of [ 0, 1ย ].

Noteโ€Šโ€”โ€ŠMy computations and your computations, while executing the above set of R Codes might vary as the signatures are randomly generated.

Final Thoughts

The above technique using Jaccard Similarity, Minhashing, and LSH is one of the utilized techniques to compute document similarity although many more exists. Text similarity is an active research field, and techniques are continuously evolving. Hence which method to use is very much dependent on the Use Case and the requirements of what we want toย achieve.

Thanks for readingย !!!

You can follow me on medium as wellย as

LinkedIn: Supriyaย Ghosh

Twitter: @isupriyaghosh


Text Similarity using K-Shingling, Minhashing and LSH(Locality Sensitive Hashing) was originally published in Towards AI on Medium, where people are continuing the conversation by highlighting and responding to this story.

Published via Towards AI

Feedback โ†“