Как работает кластеризация (особенно кластеризация строк)?
Я слышал о кластеризации для группировки похожих данных. Я хочу знать, как это работает в конкретном случае для String.
У меня есть таблица с более чем 100 000 слов.
Я хочу идентифицировать одно и то же слово с некоторыми отличиями (например: house, house!!, hooouse, HoUse, @house, "house", etc...).
Что необходимо для определения сходства и группировки каждого слова в кластере? Какой алгоритм больше для этого рекомендуется?
4 ответа
Чтобы понять, что такое кластеризация, представьте географическую карту. Вы можете увидеть много различных объектов (например, дома). Некоторые из них находятся близко друг к другу, а другие далеко. Исходя из этого, вы можете разбить все объекты на группы (например, города). Алгоритмы кластеризации делают именно это - они позволяют вам разбивать данные на группы без предварительного указания границ групп.
Все алгоритмы кластеризации основаны на расстоянии (или вероятности) между 2 объектами. На географической карте это нормальное расстояние между двумя домами, в многомерном пространстве это может быть евклидово расстояние (фактически расстояние между двумя домами на карте также является евклидовым расстоянием). Для сравнения строк вы должны использовать что-то другое. 2 хороших варианта здесь - расстояние Хэмминга и Левенштейна. В вашем конкретном случае расстояние Левенштейна, если предпочтительнее (расстояние Хэмминга работает только со струнами одинакового размера).
Теперь вы можете использовать один из существующих алгоритмов кластеризации. Их много, но не все могут удовлетворить ваши потребности. Например, чистое k-means, уже упомянутое здесь, вряд ли поможет вам, так как для его поиска требуется начальное количество групп, а для большого словаря строк это может быть 100, 200, 500, 10000 - вы просто не знаете число, Поэтому другие алгоритмы могут быть более подходящими.
Одним из них является алгоритм максимизации ожидания. Его преимущество в том, что он может автоматически находить количество кластеров. Однако на практике часто он дает менее точные результаты, чем другие алгоритмы, поэтому обычно используют k-средства поверх EM, то есть сначала находят число кластеров и их центров с помощью EM, а затем используют k-средства для настройки результат.
Другая возможная ветвь алгоритмов, которая может подойти для вашей задачи, это иерархическая кластеризация. Результат кластерного анализа в этом случае не в наборе независимых групп, а в дереве (иерархии), где несколько меньших кластеров сгруппированы в один больший, и все кластеры, наконец, являются частью одного большого кластера. В вашем случае это означает, что все слова до некоторой степени похожи друг на друга.
Существует пакет с именем stringdist, который позволяет сравнивать строки, используя несколько различных методов. Копирование с этой страницы:
- Расстояние Хэмминга: количество позиций с одинаковым символом в обеих строках. Определяется только для строк одинаковой длины.
- Расстояние Левенштейна: минимальное количество вставок, удалений и замен, необходимых для преобразования строки a в строку b.
- (Полная версия) Расстояние Дамерау-Левенштейна: Как и расстояние Левенштейна, но допускается перемещение смежных символов.
- Оптимальное выравнивание строк / ограниченное расстояние Дамерау-Левенштейна: Как (полное) расстояние Дамерау-Левенштейна, но каждая подстрока может быть отредактирована только один раз.
- Longest Common Substring distance: минимальное количество символов, которое необходимо удалить в обеих строках, пока результирующие подстроки не будут идентичны.
- Расстояние q-граммы: сумма абсолютных разностей между векторами N-грамм обеих строк.
- Расстояние до косинуса: 1 минус косинусное сходство обоих N-граммовых векторов.
- Расстояние Жакара: 1 мин. Отношение общих N-грамм и всех наблюдаемых N-грамм.
- Расстояние Джаро: расстояние Джаро является формулой из 4 значений и фактически является частным случаем расстояния Джаро-Винклера с p = 0.
- Расстояние Джаро-Винклера: это расстояние представляет собой формулу из 5 параметров, определяемых двумя сравниваемыми строками (A,B,m,t,l) и p, выбранными из [0, 0,25].
Это даст вам расстояние. Вам может не потребоваться выполнить кластерный анализ, возможно, достаточно сортировки по расстоянию строк. Я создал скрипт, чтобы обеспечить базовую функциональность здесь... не стесняйтесь улучшать его по мере необходимости.
Вы можете использовать алгоритм кластеризации под названием «Распространение сходства». Этот алгоритм принимает входные данные, называемые матрицей сходства, которую вы можете сгенерировать, приняв отрицательное значение либо расстояния Левенштейна, либо среднего гармонического значения partial_ratio и token_set_ratio из библиотеки fuzzywuzzy, если вы используете Python.
Вы можете использовать алгоритм, как расстояние Левенштейна для расчета расстояния и k-means для кластеризации.
расстояние Левенштейна - это строковая метрика для измерения величины разности между двумя последовательностями
Проведите некоторое тестирование и найдите порог сходства для каждого слова, которое определит ваши группы.