Python集群集合列表

Question

对于集合集合，我需要将它们分组到多个“集群”，集群中的所有节点都是该集群中最大节点的子集。例如

input = [{1, 2}, {1, 2, 3}, {1, 2, 4}, {1, 4}, {1}]

将获得：

[{1, 2, 3}, {1, 2}, {1}], 
[{1, 2, 4}, {1, 2}, {1, 4}, {1}]

我曾尝试使用this的引用构建子集树，但当输入较大时，它很快就会变得非常慢，因为它会对每个插入迭代所有子级

我不熟悉k-均值聚类，但它是否适用于这里的问题

最有效的方法是什么

Answer 1

也许通过降低长度顺序对集合进行排序将使每个集合中每个簇的交叉点数量减少到一个。这将取决于数据，如果没有子集也不会改善，但随着集群的扩大，情况应该会有所改善：

setList = [{1, 2}, {1, 2, 3}, {1, 2, 4}, {1, 4}, {1}]

groups = []
for aSet in sorted(setList,key=len,reverse=True):
    clusters = [g for g in groups if g[0].issuperset(aSet)]
    if not clusters:
        groups.append([])
        clusters = groups[-1:]
    for g in clusters:
        g.append(aSet)

print(groups)

[[{1, 2, 3}, {1, 2}, {1}], [{1, 2, 4}, {1, 2}, {1, 4}, {1}]]

Answer 2

首先按长度降序排列列表。这样，您就可以从最长的集合开始，这些集合肯定不是任何其他集合的子集

然后，将每个代表集保存为具有列表值的dict的键（转换为元组后）

对于每个集合，检查它是否是任何键的子集，并将其添加到相应的列表中

只有当它没有添加到任何键时，才意味着它是一个新的代表

最后，取result dict的values()：

l = [{1, 2}, {1, 2, 3}, {1, 2, 4}, {1, 4}, {1}]

grouped_sets = {}
for cur_set in sorted(l, key=len, reverse=True):
    is_subset = False
    for represent, sets in grouped_sets.items():
        if cur_set.issubset(represent):
            sets.append(cur_set)
            is_subset = True

    if not is_subset:
        grouped_sets[tuple(cur_set)] = [cur_set]

print(list(grouped_sets.values()))

其中：

[[{1, 2, 3}, {1, 2}, {1}], 
 [{1, 2, 4}, {1, 2}, {1, 4}, {1}]]