Текстовая кластеризация с расстояниями Левенштейна

Question

У меня есть набор (2k - 4k) маленьких строк (3-6 символов), и я хочу сгруппировать их. Поскольку я использую строки, предыдущие ответы на How does clustering (especially String clustering) work?, сообщил мне, что Levenshtein distance хорош для использования в качестве функции расстояния для строк. Кроме того, поскольку я не знаю заранее количество кластеров, hierarchical clustering - это путь, а не k-означает.

Хотя я получаю проблему в ее абстрактной форме, я не знаю, какой легкий способ на самом деле это сделать. Например, MATLAB или R - лучший выбор для фактической реализации иерархической кластеризации с пользовательской функцией (расстояние Левенштейна). Для обоих программ можно легко найти реализацию расстояния Левенштейна. Кластерная часть кажется сложнее. Например, Clustering text in MATLAB вычисляет массив расстояний для всех строк, но я не могу понять, как использовать массив расстояний для фактического получения кластеризации. Можете ли вы, чтобы кто-нибудь из вас, гуру, показал мне способ реализации иерархической кластеризации в MATLAB или R с помощью специальной функции?

Answer 1

Это может быть немного упрощенно, но вот пример кода, который использует иерархическую кластеризацию, основанную на расстояния Левенштейна в R.

set.seed(1) 
rstr <- function(n,k){ # vector of n random char(k) strings 
    sapply(1:n,function(i){do.call(paste0,as.list(sample(letters,k,replace=T)))}) 
} 

str<- c(paste0("aa",rstr(10,3)),paste0("bb",rstr(10,3)),paste0("cc",rstr(10,3))) 
# Levenshtein Distance 
d <- adist(str) 
rownames(d) <- str 
hc <- hclust(as.dist(d)) 
plot(hc) 
rect.hclust(hc,k=3) 
df <- data.frame(str,cutree(hc,k=3)) 

В этом примере мы создадим набор 30 случайных char (5) искусственно в 3 группах (начиная с «aa», «bb» и «cc»).Мы вычисляем матрицу расстояний Левенштейна с использованием adist(...), и мы запускаем иерархическую кластеризацию с использованием hclust(...). Затем мы вырезаем дендрограмму на три кластера с cutree(...) и добавляем идентификаторы кластера к исходным строкам.

Answer 2

В то время как ответ зависит от степени в значениях строк, в общем, ваша проблема решена семейством методов анализа последовательности. Более конкретно, Оптимальный анализ соответствия (OMA).

Чаще всего OMA выполняется в три этапа. Сначала вы определяете свои последовательности. Из вашего описания я могу предположить, что каждая буква является отдельным «состоянием», строительным блоком в последовательности. Во-вторых, вы будете использовать один из нескольких алгоритмов для расчета расстояний между всеми последовательностями в вашем наборе данных, таким образом получив матрицу расстояний. Наконец, вы подадите эту матрицу расстояний в алгоритм кластеризации, такой как иерархическая кластеризация или Partitioning Around Medoids (PAM), которая, похоже, набирает популярность из-за дополнительной информации о качестве кластеров. Последнее направляет вас на выбор количества кластеров, один из нескольких субъективных шагов анализа последовательности.

В R самым удобным пакетом с большим количеством функций является TraMineR, сайт можно найти here. Его руководство пользователя очень доступно, а разработчики более или менее активны на SO.

Возможно, вы обнаружите, что кластеризация не самая сложная часть, за исключением решения о количестве кластеров. В руководстве для TraMineR показано, что синтаксис очень прост, и результаты легко интерпретировать на основе графиков визуальной последовательности. Вот пример из руководства пользователя:

clusterward1 <- agnes(dist.om1, diss = TRUE, method = "ward") 

dist.om1 расстояние матрица, полученная ОМА, членство в кластер содержится в clusterward1 объекта, который вы можете делать все, что вы хотите: черчения, перекодирование в качестве переменных и т.д. Опция diss=TRUE указывает, что объект данных является матрицей несходства (или расстояния). Легко, а? Самый сложный выбор (не синтаксически, а методологически) заключается в выборе правильного алгоритма расстояния, подходящего для вашего конкретного приложения. После того, как вы это сделаете, будучи в состоянии оправдать выбор, остальное довольно просто. Удачи!

Answer 3

Если вы хотите получить четкое объяснение того, как использовать кластеризацию разделов (которая, безусловно, будет быстрее) для решения вашей проблемы, проверьте эту статью: Эффективные методы проверки орфографии с использованием алгоритмов кластеризации. https://www.researchgate.net/publication/255965260_Effective_Spell_Checking_Methods_Using_Clustering_Algorithms?ev=prf_pub

Авторы объясняют, как скопировать словарь с использованием модифицированной (PAM-подобной) версии iK-Means.

Лучшее из удач!

Answer 4

ELKI включает в себя расстояние Левенштейна и предлагает широкий выбор современных алгоритмов кластеризации, например, OPTICS кластеризация.

поддержки Text кластерного вклад Феликс Штальберг, как часть его работы по:

Штальберг, Ф., Шлиппа, Т., Vogel, S., & Schultz, Т.
сегментации слов через межъязычную привязку слова к фонне.
Разговорная языковая технологическая мастерская (SLT), 2012 IEEE. IEEE, 2012.

Мы, конечно, оценили бы дополнительные взносы.