"Обработка естественного языка"
Сходство текста с использованием K-Shingling, Minhashing и LSH (локально-чувствительное хэширование)
Сходство текста играет важную роль в обработке естественного языка (NLP), и есть несколько областей, где это широко используется. Некоторые из приложений включают в себя поиск информации, категоризацию текста, определение темы, машинный перевод, суммирование текста, кластеризацию документов, обнаружение плагиата, рекомендацию новостей и т. д., охватывающих почти все домены.
Но иногда становится трудно понять концепцию алгоритмов подобия текста. В этой статье будет показана реализация сходства текста с объяснением необходимых концепций.
Но прежде чем я начну, позвольте мне сказать вам, что может быть несколько способов и несколько алгоритмов для выполнения одной и той же задачи. Я буду использовать один из способов изображения, используя K-Shingling, Minhashing и LSH (Locality Sensitive Hashing).
Рассматриваемый набор данных представляет собой текстовую выдержку из 3 документов по рассматриваемой проблеме.
Мы можем использовать n — количество документов, каждый из которых имеет значительную длину. Но чтобы упростить задачу и избежать сложных вычислений, я рассматриваю небольшой фрагмент из каждого документа.
Давайте выполним реализацию по шагам.
Шаг 1:
Установите в качестве рабочего каталога папку, в которой размещены файлы, чтобы R мог их прочитать. Затем прочитайте все входные файлы из рабочего каталога, используя приведенный ниже код.
# 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 Студийный входной дисплей
Шаг 2:
Предварительно обработайте текст, чтобы удалить знаки препинания, преобразовать его в нижний регистр и разбить текст на слова.
# 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
Шаг 3:
Познакомьтесь с K-Shingling — методом представления активов документов. Мы еще больше поймем важность K-Shingling, но сейчас мы можем просто попробовать ознакомиться с шагами.
K-шинглом документа называется вся возможная последовательная подстрока длины k, найденная в нем.
Проиллюстрируем на примере с 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
Следовательно, при k = 3 k-шинглы первого распечатанного документа состоят из подстрок длины 3.
Первая K-Shingle: "ночь"
Вторая черепица: "ночь темна" и так далее.
Важно отметить, что набор k-шингла документа должен быть уникальным. Например, если первый вышеприведенный документ содержит более одного слова the night is, то оно будет отображаться только один раз как набор k-shingle для этого документа.
Шаг 4:
Создайте матрицу характеристик, которая визуализирует отношения между тремя документами. «Характеристическая» матрица будет булевой матрицей с:
строки = элементы каждой уникальной возможной комбинации черепицы, установленной во всех документах.
столбцы = один столбец на документ.
Таким образом, матрица будет заполнена 1 в строке i и столбце j тогда и только тогда, когда документ j содержит черепицу i , иначе он будет заполнен 0.
Давайте попробуем понять это с помощью изображения ниже.
# 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
В первой строке приведенной выше матрицы все три столбца равны 1. Это потому, что все три документа содержат 3-грань «ночь».
Для второго столбца значение равно [1, 0, 1], что означает, что документ 2 не имеет 3-голоса «ночь темная», в то время как документ 1 и 3 имеет.
Один важный момент, отмеченный здесь, заключается в том, что большую часть времени эти «характеристические матрицы» почти разрежены. Поэтому мы обычно пытаемся представить эти матрицы только позициями, в которых стоит 1, чтобы сэкономить место.
Шаг 5:
После создания наборов черепицы и матрицы характеристик нам теперь нужно измерить сходство между документами.
Для этой цели мы будем использовать подобие Jaccard.
Например, с двумя наборами гонтов как set1 и set2 сходство Жаккара будет:
При этом мы вычислим попарное сходство Жаккара для всех трех документов. Функция «dist» в «R» быстро вычисляет и возвращает матрицу расстояния/сходства.
# 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
Матрица подобия d1 говорит нам о том, что документы 1 и 3 являются наиболее похожими среди трех документов.
Для небольших наборов данных описанный выше метод отлично работает, но представьте, что если у нас есть большое количество документов для сравнения, а не только три документа значительно большей длины, тогда описанный выше метод может плохо масштабироваться, и у нас могут возникнуть тяжелые вычисления с проблема производительности, возникающая из-за того, что разреженные матрицы с набором уникальных шинглов во всех документах будут довольно большими, что усложнит вычисление сходства Жаккара между документами.
В таких ситуациях мы используем другой метод, который помогает нам экономить вычисления и может эффективно сравнивать сходство документов в больших масштабах. Этот метод называется Минхеширование.
Шаг 6:
Минхеширование включает в себя сжатие больших наборов уникальных черепиц в гораздо меньшее представление, называемое «сигнатурами».
Затем мы используем эти подписи для измерения сходства между документами.
Хотя для этих подписей невозможно дать точную меру подобия, оценки довольно близки.
Чем больше количество выбранных подписей, тем точнее оценка.
Для иллюстрации рассмотрим пример.
Предположим, мы возьмем приведенный выше пример для минхэширования характеристической матрицы из 16 строк в 4 подписи. Затем первым шагом является создание 4 столбцов случайно переставленных строк, которые не зависят друг от друга. Мы сами можем убедиться, что эта простая хеш-функция действительно генерирует случайные перестановочные строки. Чтобы сгенерировать это, мы используем формулу:
Где :
x - номера строк исходной матрицы характеристик.
a и b — любые случайные числа, меньшие или эквивалентные максимальному числу x, и оба они должны быть уникальными в каждой подписи.
Например, Для сигнатуры 1, если 5 генерируется для использования в качестве коэффициента, необходимо убедиться, что это значение не служит в качестве коэффициента несколько раз в сигнатуре 1, хотя его все же можно использовать в качестве коэффициента.
b- коэффициент в подписи 1. И это ограничение обновляется и для следующей подписи, то есть 5 может использоваться в качестве коэффициента a или b для подписи 2, но опять же не кратно 5 для коэффициента a или b подписи 2 и т.д. на.
c — простое число, немного превышающее общее количество наборов гонтов.
Для приведенного выше набора примеров, поскольку общее количество строк равно 16, поэтому простое число 17 подойдет.
Теперь давайте сгенерируем это с помощью кода «R».
# 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
Из приведенного выше вывода мы видим, что были сгенерированы 4 столбца случайно переставленных строк. Также есть 0, но это не повлияет на наши вычисления, и мы увидим это позже.
Шаг 7:
Используя случайно переставленные строки, теперь подписи будут рассчитываться дальше. Значение подписи любого столбца (документа) получается с использованием перестановочного порядка, сгенерированного каждой хэш-функцией, номер первой строки, в которой столбец имеет 1.
Что мы сделаем дальше, так это объединим случайно переставленные строки (сгенерированные хеш-функциями) с исходной характеристической матрицей и изменим имена строк матрицы на ее номер строки, чтобы проиллюстрировать расчет.
# 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
Теперь, рассматривая сгенерированную выше матрицу, мы начнем с первой хэш-функции (hash_1).
В соответствии с порядком переставленных строк нашей первой хеш-функции первой строкой является строка 14 (почему строка 14? потому что 0 — это наименьшее значение для нашей случайно сгенерированной перестановки, а в строке 14 есть 0, что делает ее первой строкой). Затем мы посмотрим на запись строки 14 для всех трех документов и попытаемся найти «запись какого документа в строке 14 равна 1?». Строка 14 документа 3 (doc_3) равна 1, поэтому значение подписи для документа 3, сгенерированное нашей первой хэш-функцией, равно 0. Но записи документов 2 и 3 в строке 14 равны 0, поэтому нам придется продолжить поиск.
В соответствии с порядком перестановки строк нашей первой хеш-функции второй строкой является строка 8 ( 1 — это второе наименьшее значение для нашей случайно сгенерированной перестановки, и она имеет значение 1 в строке 8). Мы применяем ту же концепцию, что и выше, и обнаруживаем, что запись документа 2 (doc_2) для строки 8 равна 1, поэтому значение подписи для документа 2, сгенерированное нашей первой хеш-функцией, равно 1. Обратите внимание, что мы уже закончили с документом 3, нам больше не нужно проверять, содержит ли он 1. Но мы еще не закончили, запись документа 1 в строке 8 по-прежнему равна 0. Следовательно, нам придется искать дальше.
Опять же, проверяя переставленный порядок строк для нашей первой хэш-функции, третья строка — это строка 2. Запись документа 1 для строки 2 равна 1. Таким образом, мы закончили вычисление значений подписи для всех трех столбцов с помощью нашей первой хеш-функции! ! Которые [2, 1, 0].
Затем мы можем применить то же самое понятие для вычисления значения подписи для каждого столбца (документа) с использованием второй хэш-функции и т. д. для третьего, четвертого и т. д. Беглый взгляд на вторую хеш-функцию подписи показывает, что первая строка в соответствии с к его переставленному порядку строк является строка 8, а doc_2 имеет 1 в строке 3. Точно так же вторая строка — это строка 14 с doc_3 как 1, а третья строка — это строка 3 с doc_1 как 1. Следовательно, значения подписи, сгенерированные нашим вторым хешем функция для всех трех документов [2, 0, 1].
Что же касается этих рассчитанных значений сигнатур, то мы попутно будем хранить их в матрице сигнатур, которая впоследствии заменит исходную матрицу характеристик. В следующем разделе будут вычислены значения подписи для всех 3 столбцов с использованием всех 4 хеш-функций и распечатана матрица подписи.
# 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
Наша матрица сигнатур имеет то же количество столбцов, что и исходная матрица характеристик, но только n строк, где n — количество хеш-функций, которые мы хотим сгенерировать (в данном случае 4).
Позвольте мне уточнить, как мы интерпретируем приведенный выше результат?
Например, для документов 1 и 3 (столбцы 1 и 3) его сходство будет равно 0,25, потому что они совпадают только в 1 строке из 4 (строка 4 обоих столбцов равна 1).
Давайте вычислим то же самое объяснение через код.
# 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
Из-за различия результата между исходным сходством Жаккара и новым сходством, полученным с использованием подобия сигнатур, мы можем усомниться в том, что это точная оценка? Но, как упоминалось ранее, цель Минхаша состоит в том, чтобы обеспечить быстрое «приближение» к истинному подобию Жаккара, и оценка может быть более близкой, но не на 100% точной, отсюда и разница. Кроме того, рассматриваемый здесь пример слишком мал для более точного отображения с использованием закона больших чисел. Более точные и близкие результаты ожидаются с большими наборами данных.
В тех случаях, когда основное требование состоит в том, чтобы вычислить сходство каждой возможной пары, возможно, для кластеризации текста или чего-то подобного, тогда LSH (локально-чувствительное хэширование) не служит этой цели, но если требуется найти пары, которые, скорее всего, будут аналогично, тогда можно использовать технику, называемую хешированием с учетом местоположения, о которой я расскажу ниже.
Хеширование с учетом местоположения
Хотя информация, необходимая для вычисления сходства между документами, была сжата из исходной разреженной матрицы характеристик в гораздо меньшую матрицу сигнатур, но основная проблема или необходимость выполнения попарных сравнений для всех документов все еще существует.
Концепция хеширования с учетом местоположения (LSH) заключается в том, что, учитывая матрицу сигнатур размером n (количество строк), мы разделим ее на b полос, в результате чего каждая полоса будет состоять из r строк. Это эквивалентно простой математической формуле — n = br, поэтому, когда мы делаем разбиение, мы должны быть уверены, что выбранное нами b делится на n. Используя приведенную выше матрицу подписи и выбрав размер полосы равным 2, приведенный выше пример станет следующим:
# 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
Хеширование с учетом местоположения говорит нам следующее: если значения подписи двух документов совпадают во всех строках хотя бы одной полосы, то эти два документа, вероятно, похожи и их следует сравнивать (укажите их как пару кандидатов). Использование этого небольшого набора документов может быть плохим примером, поскольку может случиться так, что ни один из них не будет выбран в качестве нашей пары-кандидата. Например, если значение подписи документа 2 для диапазона 1 становится [ 0, 1 ] вместо текущего [ 1, 0 ], тогда документ 2 и документ 3 станут парой кандидатов, поскольку обе их строки в диапазоне 1 принимают одинаковые значения. значение [ 0, 1 ].
Примечание — Мои расчеты и ваши расчеты при выполнении вышеуказанного набора R-кодов могут различаться, поскольку подписи генерируются случайным образом.
Последние мысли
Вышеупомянутый метод с использованием подобия Jaccard, Minhashing и LSH является одним из используемых методов для вычисления сходства документов, хотя существует множество других. Текстовое сходство является активной областью исследований, и методы постоянно развиваются. Следовательно, какой метод использовать, очень сильно зависит от варианта использования и требований того, чего мы хотим достичь.
Спасибо за чтение !!!
Вы можете подписаться на меня как на Medium, так и на
LinkedIn: Суприя Гош
Твиттер: @isupriaghosh
