Чтобы понять, что такое кластеризация, представьте географическую карту.Вы можете увидеть много различных объектов (таких как дома).Некоторые из них находятся близко друг к другу, а другие далеко.Исходя из этого, вы можете разбить все объекты на группы (например, города).Алгоритмы кластеризации делают именно это - они позволяют вам разбивать данные на группы без предварительного указания границ групп.
Все алгоритмы кластеризации основаны на расстоянии (или вероятности) между 2 объектами.На географической карте это нормальное расстояние между двумя домами, в многомерном пространстве это может быть евклидово расстояние (фактически, расстояние между двумя домами на карте также является евклидовым расстоянием).Для сравнения строк вы должны использовать что-то другое.Вот два хороших варианта: Хэмминга и Расстояние Левенштейна .В вашем конкретном случае расстояние Левенштейна , если это более предпочтительно (расстояние Хэмминга работает только для струн одинакового размера).
Теперь вы можете использовать один из существующих алгоритмов кластеризации.Их много, но не все могут соответствовать вашим потребностям.Например, чистое k-means, уже упомянутое здесь, вряд ли поможет вам, так как для его поиска требуется начальное количество групп, а для большого словаря строк это может быть 100, 200, 500, 10000 - вы просто не знаете число,Поэтому другие алгоритмы могут быть более подходящими.
Одним из них является алгоритм максимизации ожидания алгоритм.Его преимущество в том, что он может автоматически находить количество кластеров.Однако на практике часто он дает менее точные результаты, чем другие алгоритмы, поэтому обычно используют k-средних поверх EM , то есть сначала находят число кластеров и их центров с EM, а затем используютk-означает, чтобы скорректировать результат.
Другая возможная ветвь алгоритмов, которая может подойти для вашей задачи, это иерархическая кластеризация .Результатом кластерного анализа в этом случае является не набор независимых групп, а дерево (иерархия), где несколько меньших кластеров сгруппированы в один больший, и все кластеры, наконец, являются частью одного большого кластера.В вашем случае это означает, что все слова до некоторой степени похожи друг на друга.