python - 如何在没有 networkx 的情况下对对进行聚类

Question

我有一个列表列表:

[['suzy', 'joe', ...], ['suzy', 'tom', ...], ['paul', 'kristy', ...], [ “克里斯蒂”、“格里芬”、...]、...]

我想要的输出是将这些对聚类成两个列表:

['suzy', 'joe', 'tom']
['paul', 'kristy', 'griffin']

我读了this post那有一个类似的问题，但是用 networkx 回答了。但是，我正在避免使用 networkx，并且一直在努力做到这一点。

我试着用一个名字创建一个字典，如果它们是一对的话，然后附加其他名字，但它变得越来越乱。感谢您的帮助!

Answer 1

您提到的 networkx 解决方案创建了一个无向图，其中节点是名称，边是观察到的配对。这些集群然后是 connected components图形的一部分，您可以使用图形遍历算法(例如 DFS、BFS)读取它。

所以，你有两个选择:

1. 构建您自己的图形实现，不使用 networkx，执行上述操作。我刚才描述的不是您只能使用 networkx 完成的事情。

2. 使用 disjoint sets data structure生成分组。顾名思义，我们维护一组不相交的集合(其中一个集合代表一群人)。每当我们看到一对时，我们就会合并这对中的两个人最初所属的集群。下面给出了 union-find 的实现及其对您所描述问题的应用:

# Union-find by size.
def find(data, target):
    if data[target] < 0:
        return target
    data[target] = find(data, data[target])
    return data[target]

def union(data, first, second):
    first_root, second_root = find(data, first), find(data, second)
    if first_root == second_root:
        return False
    elif first_root < second_root:
        data[first_root] += data[second_root]
        data[second_root] = first_root
        return True
    else:
        data[second_root] += data[first_root]
        data[first_root] = second_root
        return True

data = [['suzy', 'joe'], ['suzy', 'tom'], ['paul', 'kristy'], ['kristy', 'griffin']]

# Extract list of names from data.
name_set = set()
for pair in data:
    name_set.add(pair[0])
    name_set.add(pair[1])

name_list = list(name_set)
name_table = {name: index for index, name in enumerate(name_list)}

# Find disjoint sets.
disjoint_sets = [-1] * len(name_table)
for pair in data:
    union(disjoint_sets, name_table[pair[0]], name_table[pair[1]])

# Read off disjoint sets into lists.
result = {}
for name in name_table:
    set_id = find(disjoint_sets, name_table[name])
    if set_id not in result:
        result[set_id] = []
    result[set_id].append(name)

print(list(result.values()))