Я слышал о кластеризации для группировки похожих данных. Я хочу знать, как это работает в конкретном случае для String.
У меня есть таблица с более чем 100 000 слов.
Я хочу идентифицировать одно и то же слово с некоторыми отличиями (например: house, house!!, hooouse, HoUse, @house, "house", etc...).
Что необходимо для определения сходства и группировки каждого слова в кластере? Какой алгоритм более рекомендуется для этого?
Чтобы понять, какая кластеризация представляет собой географическую карту. Вы можете увидеть много разных объектов (например, дома). Некоторые из них близки друг к другу, а другие - далеко. Исходя из этого, вы можете разбить все объекты на группы (например, города). Алгоритмы кластеризации делают именно эту вещь - они позволяют разделить ваши данные на группы без предварительного указания границ групп.
Все алгоритмы кластеризации основаны на расстоянии (или вероятности) между двумя объектами. На географической карте это нормальное расстояние между двумя домами, в многомерном пространстве это может быть евклидово расстояние (на самом деле расстояние между двумя домами на карте также является евклидовым расстоянием). Для сравнения строк вам нужно использовать что-то другое. 2 хороших варианта - Hamming и расстояние Левенштейна. В вашем конкретном случае расстояние Левенштейна, если это более предпочтительно (расстояние Хэмминга работает только со строками того же размера).
Теперь вы можете использовать один из существующих алгоритмов кластеризации. Их много, но не все могут соответствовать вашим потребностям. Например, чистые k-средства, уже упомянутые здесь, вряд ли помогут вам, поскольку для этого требуется начальное число групп, а с большим словарем строк может быть 100, 200, 500, 10000 - вы просто не знаете номер, Таким образом, другие алгоритмы могут быть более подходящими.
Один из них - алгоритм максимизации ожиданий. Его преимуществом является то, что он может автоматически найти количество кластеров. Однако на практике часто он дает менее точные результаты, чем другие алгоритмы, поэтому нормально использовать k-средства поверх EM, то есть сначала найти количество кластеров и их центров с EM, а затем используйте k-средства для настройки результата.
Еще одна возможная ветвь алгоритмов, которая может быть подходящей для вашей задачи, - иерархическая кластеризация. Результат кластерного анализа в этом случае не в множестве независимых групп, а скорее в дереве (иерархии), где несколько более мелких кластеров сгруппированы в одну большую, и все кластеры, наконец, являются частью одного большого кластера. В вашем случае это означает, что все слова похожи друг на друга до некоторой степени.
Существует пакет под названием stringdist, который позволяет сравнивать строки, используя несколько различные методы. Копирование с этой страницы:
Это даст вам дистанцию. Возможно, вам не понадобится выполнять кластерный анализ, возможно, сортировка по самому размеру строки достаточна. Я создал script, чтобы предоставить базовую функциональность здесь... не стесняйтесь улучшать ее по мере необходимости.
Вы можете использовать такой алгоритм, как расстояние Левенштейна для расчета расстояния и k-means для кластеризации.
расстояние Левенштейна является строковой метрикой для измерения величины разницы между двумя последовательностями
Проведите некоторое тестирование и найдите порог подобия для каждого слова, которое будет определять ваши группы.