如何高效找出两个聚类结果列表的公共部分？

核心思路 #

公共簇的本质是：一组节点在两个聚类结果中始终属于同一个子簇——也就是这组节点在第一个聚类里同属一个簇，在第二个聚类里也同属一个簇，且无法再添加其他节点满足这个条件。

要高效解决这个问题，可以通过「节点-簇集合映射」+「交集去重」的方式实现，时间复杂度为O(n)（n为总节点数），具体步骤如下：

具体步骤 #

1. 构建节点到簇集合的映射
   把每个聚类结果中的簇转换成集合，然后为每个节点记录它所在的簇集合。这样可以快速查询任意节点在对应聚类中的所属簇范围。

2. 计算节点的公共簇交集
   对每个节点，计算它在两个聚类中所属簇集合的交集——这个交集就是该节点在两个聚类中都被归为同一组的最大节点集合。

3. 去重得到公共簇
   把所有节点的交集结果去重，剩下的就是两个聚类的公共部分。

代码实现示例 #

def get_common_clusters(com1, com2):
    # 构建节点到簇集合的映射
    def build_cluster_map(clusters):
        cluster_map = {}
        for cluster in clusters:
            cluster_set = frozenset(cluster)
            for node in cluster:
                cluster_map[node] = cluster_set
        return cluster_map
    
    map1 = build_cluster_map(com1)
    map2 = build_cluster_map(com2)
    
    # 计算所有节点的交集，去重
    common_clusters = set()
    for node in map1:
        # 两个簇集合的交集就是公共子簇
        common = map1[node] & map2[node]
        common_clusters.add(common)
    
    # 转换成列表格式返回
    return [list(cluster) for cluster in common_clusters]

# 测试示例
com1 = [[1,2,3,4], [5, 6, 7, 8], [9]]
com2 = [[1, 2, 4], [3], [5, 6, 7, 8], [9]]
print(get_common_clusters(com1, com2))
# 输出: [[1,2,4], [3], [5,6,7,8], [9]]

方法优势 #

• 时间效率高：构建映射和计算交集都是线性时间操作，适合处理大规模节点的聚类结果。
• 逻辑清晰：通过集合交集直接锁定公共子簇，避免了复杂的簇匹配遍历。

内容的提问来源于stack exchange，提问作者CaponeBoom