Python 聚类具有 n 到 m 关系的连接元素

Question

这不是家庭作业（请查看我的个人资料）。我没有计算机科学背景，这个问题出现在应用机器学习问题中。我很确定我不是第一个遇到这个问题的人，因此我正在寻找一个优雅的解决方案。我更喜欢使用 python 库而不是原始实现的解决方案。

假设我们有一个连接字母和数字的字典作为输入

connected = {
    'A': [1, 2, 3],
    'B': [3, 4],
    'C': [5, 6],
}

每个字母可以连接多个数字。并且一个数字可以连接到多个字母。但是每个字母只能连接一个数字一次。

如果我们查看字典，我们会发现数字 3 与字母 'A' 和字母 'B' 相关联，因此我们可以输入 'A' 和'B'成簇。字母 'C' 的数字不存在于其他字母中。因此，我们无法进一步对字母 'C' 进行聚类。 预期输出应该是

cluster = {
    '1': {
        'letters': ['A', 'B'],
        'numbers': [1, 2, 3, 4], 
    },
    '2': {
        'letters': ['C'],
        'numbers': [5, 6],
    }
}

我认为这应该与图算法和连接子图有关，但我不知道从哪里开始。

Answer 1

使用联合查找结构，您可以在 O(num letters + num numbers) 中有效地解决这个问题。关键思想是您可以将字母连接到它们的数字列表。对所有字母执行此操作后，您将自动拥有所需属性.

的并集（即簇）

class UnionFind:
    def __init__(self):
        self.id = {}
        self.size = {}

    def find(self, a):
        cur = a
        path = []
        while self.id[cur] != cur:
            path.append(cur)
            cur = self.id[cur]
        for x in path:
            self.id[x] = cur
        return cur

    def union(self, a, b):
        if a not in self.id:
            self.id[a] = a
            self.size[a] = 1
        if b not in self.id:
            self.id[b] = b
            self.size[b] = 1

        roota, rootb = self.find(a), self.find(b)
        if roota != rootb:
            if self.size[roota] > self.size[rootb]:
                roota, rootb = rootb, roota
            self.id[roota] = rootb
            self.size[rootb] += self.size[roota]

if __name__ == "__main__":
    from collections import defaultdict

    uf = UnionFind()
    connected = {
        'A': [1, 2, 3],
        'B': [3, 4],
        'C': [5, 6],
    }
    for letter, numbers in connected.items():
        for number in numbers:
            uf.union(letter, number)
    
    clusters = defaultdict(list)
    for key, cluster_id in uf.id.items():
        clusters[cluster_id].append(key)
    
    formatted_clusters = {}
    for i, cluster_elements in enumerate(clusters.values()):
        letters = [e for e in cluster_elements if isinstance(e, str)]
        numbers = [e for e in cluster_elements if not isinstance(e, str)]
        key = str(i+1)
        formatted_clusters[key] = {
            "letters": letters,
            "numbers": numbers
        }
    print(formatted_clusters)

输出：

{'1': {'letters': ['A', 'B'], 'numbers': [1, 2, 3, 4]}, '2': {'letters': ['C'], 'numbers': [5, 6]}}

Python 聚类具有 n 到 m 关系的连接元素

Python Cluster connnected elements with n to m relationship

python

algorithm

graph

strongly-connected-graph