Кластеризация текста с расстояниями Левенштейна
У меня есть набор (2k - 4k) маленьких строк (3-6 символов), и я хочу их кластеризовать. Поскольку я использую строки, предыдущие ответы на Как работает кластеризация (особенно кластеризация строк)?, сообщил мне, что расстояние Левенштейна хорошо для использования в качестве функции расстояния для струн. Кроме того, поскольку я не знаю заранее количество кластеров, иерархическая кластеризация - это путь, а не k-средних.
Хотя я понимаю проблему в ее абстрактной форме, я не знаю, как проще всего это сделать. Например, является ли MATLAB или R лучшим выбором для фактической реализации иерархической кластеризации с пользовательской функцией (расстояние Левенштейна). Для обоих программ можно легко найти реализацию расстояния Левенштейна. Кластерная часть кажется более сложной. Например, кластеризация текста в MATLAB вычисляет массив расстояний для всех строк, но я не могу понять, как использовать массив расстояний для фактической кластеризации. Можете ли вы, гуру, показать мне, как реализовать иерархическую кластеризацию в MATLAB или R с помощью пользовательской функции?
4 ответа
Это может быть немного упрощенно, но вот пример кода, который использует иерархическую кластеризацию, основанную на расстоянии Левенштейна в 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(...)и мы запускаем heirarchal кластеризацию, используя hclust(...), Затем мы разрезаем дендрограмму на три группы: cutree(...) и добавьте идентификаторы кластера к исходным строкам.
ELKI включает расстояние Левенштейна и предлагает широкий выбор расширенных алгоритмов кластеризации, например, кластеризацию OPTICS.
Поддержка кластеризации текста была внесена Феликсом Штальбергом в рамках его работы над:
Штальберг Ф., Шлиппе Т., Фогель С. и Шульц Т.
Сегментация слов посредством межъязыкового выравнивания между словами и фонемами.
Семинар по разговорным языковым технологиям (SLT), 2012 IEEE. IEEE, 2012.
Мы, конечно, будем благодарны за дополнительный вклад.
Хотя ответ в некоторой степени зависит от значения строк, в целом ваша проблема решается с помощью семейства методов анализа последовательностей. В частности, анализ оптимального соответствия (OMA).
Чаще всего ОМА проводится в три этапа. Сначала вы определяете свои последовательности. Из вашего описания я могу предположить, что каждая буква является отдельным "состоянием", строительным блоком в последовательности. Во-вторых, вы будете использовать один из нескольких алгоритмов для вычисления расстояний между всеми последовательностями в вашем наборе данных, таким образом получая матрицу расстояний. Наконец, вы добавите эту матрицу расстояний в алгоритм кластеризации, такой как иерархическая кластеризация или Partitioning Around Medoids (PAM), который, кажется, приобретает популярность благодаря дополнительной информации о качестве кластеров. Последний поможет вам в выборе количества кластеров, один из нескольких субъективных шагов в анализе последовательности.
В R самый удобный пакет с большим количеством функций TraMineRСайт можно найти здесь. Его руководство пользователя очень доступно, и разработчики также более или менее активны в SO.
Вероятно, вы обнаружите, что кластеризация - не самая сложная часть, за исключением решения о количестве кластеров. Руководство для TraMineR показывает, что синтаксис очень прост, и результаты легко интерпретировать на основе визуальных графиков последовательности. Вот пример из руководства пользователя:
clusterward1 <- agnes(dist.om1, diss = TRUE, method = "ward")
dist.om1 матрица расстояний, полученная OMA, членство в кластере содержится в clusterward1 объект, который вы можете делать все, что вы хотите: построение, перекодирование в качестве переменных и т. д. diss=TRUE Параметр указывает, что объектом данных является матрица различий (или расстояний). Легко, а? Самый сложный выбор (не синтаксически, а методологически) - это выбрать правильный алгоритм расстояния, подходящий для вашего конкретного применения. Как только вы это сделаете, и сможете сделать выбор, все остальное будет легко. Удачи!
Если вы хотите получить четкое объяснение того, как использовать кластерную кластеризацию (что наверняка будет быстрее) для решения вашей проблемы, проверьте этот документ: Эффективные методы проверки орфографии с использованием алгоритмов кластеризации. https://www.researchgate.net/publication/255965260_Effective_Spell_Checking_Methods_Using_Clustering_Algorithms?ev=prf_pub
Авторы объясняют, как кластеризовать словарь, используя модифицированную (PAM-подобную) версию iK-Means.
Удачи!