如何将相似的列表聚在一起？

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

这看起来是一个很好的使用案例。潜在的Dirichlet分配 模型。

---

A LDA 是一个无监督模型，它能在一组观测值中找到相似的组，然后你可以用它来分配一个 课题 到他们每个人。

下面是你可以如何去做的。

from sklearn.feature_extraction.text import CountVectorizer
import lda

装上一个 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 模型的实现，比如在 遗传因子)

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首先，你应该使用距离度量，它将告知你你的集群之间的相似性.虚拟度量将是共同元素的数量，但对于比较存在-不存在，他们是其他像Jaccard.然后你会得到一个距离矩阵，总结你的列表之间的距离.在这一点上，你可以自由使用任何你想要的聚类（看看scipy或sklearn的聚类python库）。

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