Кластеризация длинного списка строк (слов) в группы сходства

31

У меня под рукой следующая проблема: у меня есть очень длинный список слов, возможно, имен, фамилий и т. Д. Мне нужно сгруппировать этот список слов, чтобы похожие слова, например слова с одинаковым расстоянием редактирования (Левенштейна), появлялись в тот же кластер. Например, «алгоритм» и «алогритм» должны иметь высокие шансы появиться в одном кластере.

Мне хорошо известны классические неконтролируемые методы кластеризации, такие как кластеризация k-средних, EM-кластеризация в литературе по распознаванию образов. Проблема в том, что эти методы работают с точками, которые находятся в векторном пространстве. У меня есть слова струн в моей руке здесь. Похоже, что вопрос о том, как представлять строки в числовом векторном пространстве и вычислять «средние значения» кластеров струн, не получил достаточного ответа, согласно моим исследованиям до сих пор. Наивным подходом к решению этой проблемы было бы объединение кластеризации k-средних с расстоянием Левенштейна, но все еще остается вопрос «Как изобразить» средство «из строк?». Существует вес, называемый весом TF-IDF, но, похоже, он в основном относится к области кластеризации «текстовых документов», а не к кластеризации отдельных слов. http://pike.psu.edu/cleandb06/papers/CameraReady_120.pdf

Мои поиски в этой области все еще продолжаются, но я тоже хотел получить идеи. Что бы вы порекомендовали в этом случае, кто-нибудь знает какие-либо методы для такого рода проблемы?

clustering k-means pattern-recognition Уфук Джан Бичичи
источник
1
Я узнал о существовании варианта k-средних, названного «K-medoids». en.wikipedia.org/wiki/K-medoids Не работает с евклидовым расстоянием L2 и не требует вычисления средних значений. Он использует точку данных, которая ближе всего к другим в кластере, в качестве «медоида».
Уфук Джан Бичичи
1
It seems that there are some special string clustering algorithms, Если вы пришли именно из области интеллектуального анализа текста, а не из статистики / анализа данных, это утверждение оправдано. Однако, если вы изучите кластеризацию как таковую, вы обнаружите, что не существует «специальных» алгоритмов для строковых данных. «Специальный» - это то, как вы предварительно обрабатываете такие данные, прежде чем вводить их в кластерный анализ.
ttnphns
связанные: stackoverflow.com/questions/21511801/…
Андре Хольцнер
Обратите внимание на разницу между распространением Affinity и кластеризацией K-средних и тем, как это повлияет на время вычислений. quora.com/…
Габриэль Алон

Ответы:

37

Seconding @ mican рекомендация для распространения сродства .

Из статьи: Л. Фрей, Брендан Дж. И Дельберт Дуек. «Кластеризация путем передачи сообщений между точками данных». наука 315.5814 (2007): 972-976. ,

Его супер легко использовать через множество пакетов. Он работает на всем, что вы можете определить попарно сходство. Что вы можете получить, умножив расстояние Левенштейна на -1.

Я собрал быстрый пример, используя первый абзац вашего вопроса в качестве входных данных. В Python 3:

import numpy as np
import sklearn.cluster
import distance

words = "YOUR WORDS HERE".split(" ") #Replace this line
words = np.asarray(words) #So that indexing with a list will work
lev_similarity = -1*np.array([[distance.levenshtein(w1,w2) for w1 in words] for w2 in words])

affprop = sklearn.cluster.AffinityPropagation(affinity="precomputed", damping=0.5)
affprop.fit(lev_similarity)
for cluster_id in np.unique(affprop.labels_):
    exemplar = words[affprop.cluster_centers_indices_[cluster_id]]
    cluster = np.unique(words[np.nonzero(affprop.labels_==cluster_id)])
    cluster_str = ", ".join(cluster)
    print(" - *%s:* %s" % (exemplar, cluster_str))

Вывод был (примеры выделены курсивом слева от кластера, примером которого они являются):

  • есть: шансы, редактировать, рука, иметь, высокий
  • следующие: следующие
  • проблема: проблема
  • Я: Я, в, и т. Д., В, список, из
  • возможно: возможно
  • кластер: кластер
  • слово: для, и, для, долго, нужно, должно, очень, слово, слова
  • похожие: похожие
  • Левенштейн: Левенштейн
  • расстояние: расстояние
  • : это, это, чтобы, с
  • то же самое: пример, список, имена, такие же, такие, фамилии
  • алгоритм: алгоритм, алогритм
  • появляются: появляются, появляются

Запустив его в списке из 50 случайных имен :

  • Диана: Дина, Дайан, Дионн, Джеральд, Ирина, Лизетт, Минна, Ники, Рики
  • Яни: Клер, Яни, Джейсон, Джей Си, Кими, Ланг, Маркус, Максима, Рэнди, Рауль
  • Верлайн: Дестини, Келли, Мэрилин, Мерседес, Стерлинг, Верлайн
  • Гленн: Эленор, Гленн, Гвенда
  • Армандина: Армандина, Августина
  • Шиела: Ахмед, Эстелла, Милисса, Шиела, Треза, Уинелл
  • Лорин: Осень, Хейди, Лорин, Лорен
  • Альберто: Альберта, Альберто, Роберт
  • Лори : Амми, Дорин, Евра, Джозеф, Лори, Лори, Портер

Выглядит довольно здорово для меня (это было весело).

Линдон Уайт
источник
Можно ли использовать тот же алгоритм, используя только sklearn? или использовать scipy.spatial.distance с Хэмминга? в чем преимущество левенштейна? Я думаю, мне придется попробовать использовать этот вопрос: stackoverflow.com/questions/4588541/…
Pierre
1
@pierre Levenshtein - это то, что я бы назвал «расстоянием проверки правописания», это хороший показатель вероятности ошибки правописания человека. Дамеров Левенштейн может быть даже лучше. Я не знаю, что расстояние Хэмминга определено для строк неравной длины. Это позволяет только обмены, а не вставки. определить, как наиболее разумно дополнить / обрезать струну, почти так же сложно, как вычислить несогласие Левенштейна. Вы должны дополнить / урезать начало? Конец? Некоторые из середины?
Линдон Уайт
Если вы действительно хотели избежать зависимости от расстояний. Вы могли бы использовать реализацию кода Rossetta
Линдон Уайт
читая en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance, я могу увидеть, как транспонирование может иметь значение, особенно для опечаток, и у python есть новый пакет для этого. Я могу видеть, как я могу использовать это против списка слов и получить «самое близкое», но, возможно, не самое важное. Я должен получить свой список и проверить с помощью tf-idf. Круто спасибо
Пьер
1
@Dduhaime почти наверняка. В общем, Affinity Propagation работает для несиматрических предпочтений, но так как это симметрично, продолжайте. Я уверен, что что-то в SciPy имеет треугольный матричный тип, который является типом уток как полная матрица. Я слишком долго был в джулиан-ланге и не могу вспомнить, как это делается на питоне. (В джулии ты будешь использовать Symmetric)
Линдон Уайт
5

Используйте алгоритмы кластеризации графа, такие как кластеризация Лувена, кластеризация поиска по ограниченному району (RNSC), кластеризация по методу сходства (APC) или алгоритм кластеризации Маркова (MCL).

micans
источник
Как насчет метода K-medoids, который я нашел? Мне нужно как можно скорее реализовать это решение, чтобы оно мне показалось хорошим. Я знаю о существовании этих основанных на графике методов, но боюсь, что не могу позволить себе время, необходимое для их понимания и реализации.
Уфук Джан Бичичи
Для всех них программное обеспечение доступно с довольно неограничительными лицензионными соглашениями, такими как GNU GPL. Я не большой поклонник алгоритма типа k-mediods, в основном из-за параметра k, но, естественно, решать вам. Если вам нужна внутренняя реализация, то я думаю, что APC и MCL, вероятно, проще всего реализовать. Если вы должны были сделать это, попробуйте их сначала, конечно.
micans
2

Вы можете попробовать модель векторного пространства с n-граммами слов в качестве элементов векторного пространства. Я думаю, что вам придется использовать меру, подобную косинусному подобию в этом случае, а не редактировать расстояние.

peace_within_reach
источник