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

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

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

Ответ 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(...) и добавляем идентификатор кластера к исходным строкам.

Ответ 2

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

Поддержка кластеризации текста была внесена Феликс Штальбергом в рамках его работы над:

Stahlberg, F., Schlippe, T., Vogel, S., and Schultz, T.
Сегментация Word через межъязычное выравнивание слова к фонетике.
Разговорный языковой технологический семинар (SLT), 2012 IEEE. IEEE, 2012.

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

Ответ 3

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

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

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

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

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

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

Ответ 4

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

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

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