name - title in ggplot2 r




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

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

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

Удачи!

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

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


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

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

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

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

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

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


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

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

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

Разумеется, мы будем ценить дополнительные взносы.





hierarchical-clustering