Text similarity is an essential part of Natural Language Processing (NLP). There are many areas in which this technique has been extensively used.
The applications are: Information retrieval; topic detection; text summarization; document clustering and plagiarism detection. encompassing almost all domains. Sometimes, however, understanding the Text Similarity Algorithms can be difficult. The following article will demonstrate Text Similarity and explain the concepts. Before I begin, however, let me remind you that different ways and algorithms might work for the exact same task.
One of three methods for depiction will be used: Minhashing (K-Shingling), Minhashing (Minhashing) and LSH (Locality Sensitive Hitching).
The dataset is Text Extract of 3 documents to address the issue at hand. Each document can be of considerable length, but we could use as many documents as necessary. To make things easier and to avoid complicated computations, I will only use a portion of each document. We will now move on to the next steps.
Step 1: Move your work directory to the location of the files so R can find them. Next, use the following code to read the files in the work directory.
# Libraries usedlibrary(dplyr)library(proxy)library(stringr)library(data.table)# Set the working directorysetwd(“.”) # Read the original text file files <- list.files(path=”. # Preprocess textdocuments library(dplyr)library(proxy)library (stringr)library.table# Set the working directorysetwd(“”) # Read original text file files – list.files.files(path=”. # Preprocess textdocuments <- 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 filesdocuments[[1]]documents[[2]]documents[[3]] R Studio Display
Step 3 : Introduce K-Shingling which is a technique of representing documents assets. While we will be able to understand the significance of K-Shingling, for now let’s just get familiar with the steps.
The K-shingle for a given document is all possible sub-strings of length k that are found within it. An example using k = 3 is an illustration. Shingling = function(document, K) = shingles.
For( i) 1:length(document), -k+1 ). # “shingle” The example document has k=3documents. lapply(documents) – list(original = Doc [[1]],Shingled = documents [[1]]_) R Studio Display. Thus, the k-shingles from the original document that got printed are composed of sub-strings with length3. K-Shingle 1 is “night is”.
The K-Shingle 2 is “night is dark”. And so forth. Important: A document’s unique k-shingle sets should not be duplicated. If the document that contains “the night” is more than the one above, it will be used only once to create the k-shingle set for the document.
Step 4: Create a “Characteristic matrix” that depicts the relationships among the documents. Boolean matrix: The elements of each unique combination of shingles across the documents will make up the “characteristic” matrix. Columns = One column for each document.
The matrix will therefore be filled by 1 in row I and column J if the document j has the shingle number i, else it will contain 0. # Unique shingles sets across all documentsdoc_dict <- unlist(documents) %>% unique # “Characteristic” matrixChar_Mat <- lapply(documents, function(set, dict) { as.integer(dict %in% set)}, dict = doc_dict) %>% data. # Only one set of shingles across all documentsdoc_dict unique # “Characteristic” matrixChar_Mat <- lapply(documents, function(set, dict) { as.integer(dict %in% set)}, dict = doc_dict) %>% Data.frame # Set the rows and columns names(Char_Mat, paste[ “doc”)))rownames (Char_Mat – Doc_dictChar_MatR Studio Display
In the first row above the matrix all three columns are 1. The 3-shingle “the evening is” is found in all three documents. The [1, 0, 1] value in the second column indicates that document 2 doesn’t have the 3-shingle night is dark while documents 1 and 3 do. It is important to note that these “characteristic matrixes” tend to be very sparse. These matrices are often represented by only the 1 position, to save space.
Step 5: Now that we have created shingle sets as well as a characteristic matrix, it is time to determine the degree of similarity among documents. This is where we will use Jaccard Similarity. If you have two sets of shingle sets, set1 and set2, then the Jaccard Similarity is.
This will allow us to calculate pairwise Jaccard similarities for each document. The “dist” function of “R” calculates the distance/similarity matrix quickly and returns it. # how similar is two given document, Jaccard similarity JaccardSimilarity <- function(x, y) 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 registrypr_DB$set_entry( FUN = JaccardSimilarity, names = c(“JaccardSimilarity”) ) # Jaccard similarity distance matrix d1 <- dist( t(Char_Mat), method = “JaccardSimilarity” ) # delete the new entrypr_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.
The above works well for small data sets. However, if there are many documents we need to compare, or if they have significantly longer documents, this method may not work.
Also, performance issues could arise as the number of documents and the unique shingles will make it difficult to compute the Jaccard similarities between them. In such cases, we use a different method that saves computations and allows us to compare documents on a large-scale efficiently. Minhashing is the name of this technique.
Step 6: Minhashing is the process of compressing large numbers of unique shingles to a smaller representation known as “signatures.” These signatures are then used to determine the similarities between documents. These signatures cannot give exact measures of similarity, but they are fairly close. A more extensive collection of signatures will give a better estimate. Let’s take an example as an illustration.
Let’s say we use the example above to generate 4 signatures from the 16 characteristic matrix. Next, generate four columns of random permutated rows which are independent from each other. This simple function can actually generate random permutated row. This is generated using the following formula: where x are the rows of the original matrix.
A and b represent any number that is smaller than or equal to the maximum number x. They must also be unique for each signature. E.g. If signature 1 generates 5 to be used for a-coefficient, this must be done so that it does not become a-coefficient multiple times in signature 1, although it is still possible to use it as a b- coefficient. This restriction is updated for each subsequent signature.