Как сгруппировать похожие списки вместе?

Question

Я ищу алгоритм, который может группировать списки строк, которые имеют почти одинаковое содержимое.

Это пример списков. Всего есть 5 разных слов.

A = ['first', 'second', 'third']
B = ['first', 'forth']
C = ['second', 'third']
D = ['first', 'third']
E = ['first', 'fifth']
F = ['fourth', 'fifth']

Вы можете видеть, что у A, C и D много общего, а также B, E и F.

Я думал о Алгоритм кластеризации, который может дать почти один и тот же список одному и тому же кластеру.

Я хочу, чтобы два кластера были уверены, что одно слово находится хотя бы в одном кластере.

В этом примере списка A, C и D должен иметь кластер 1

и кластер B, E и F 2.

Есть ли в Python алгоритм (или машинное обучение), который можно использовать для задач такого типа

Answer 1

Это похоже на хороший вариант использования для модели Скрытое распределение Дирихле .

---

A LDA - это модель без присмотра, которая находит подобные группы среди набора наблюдений , который вы затем можете использовать, чтобы назначить Topi c каждому из них.

Вот как вы могли бы go об этом:

from sklearn.feature_extraction.text import CountVectorizer
import lda

Fit a CountVectorizer для получения матрицы количества токенов из списка строк:

l = [' '.join(i) for i in [A,B,C,D,E,F]]
vec = CountVectorizer(analyzer='word', ngram_range=(1,1))

X = vec.fit_transform(l)

Используйте lda и подгоните модель к результату из CountVectorizer (есть и другие модули с реализацией модели lda, такие как gensim )

model = lda.LDA(n_topics=2, random_state=1)
model.fit(X)

И назначьте номер группы созданным темам 2 :

doc_topic = model.doc_topic_

for i in range(len(l)):
    print(f'Cluster {i}: Topic ', doc_topic[i].argmax())

Cluster 0: Topic  1 # -> A
Cluster 1: Topic  0
Cluster 2: Topic  1 # -> C
Cluster 3: Topic  1 # -> D
Cluster 4: Topic  0
Cluster 5: Topic  0

Answer 2

IMO сначала вы должны использовать метрики расстояния, которые сообщат вам о сходстве между вашими кластерами. фиктивные метрики были бы числом общих элементов, но для сравнения присутствия-отсутствия они такие же, как Джакард. Затем вы получите матрицу расстояний, которая суммирует расстояние между вашим списком. на данный момент вы можете использовать любую кластеризацию, какую захотите (посмотрите на scipy или sklearn для python библиотеки для кластеризации)

#A dummy code
l = [..] # list with all your list
distance_matrix = distance_funtion(l)
clustering(distance_matrix)