如何高效分组字典中具有相同相似度的冗余条目-Python教程-PHP中文网

如何高效分组字典中具有相同相似度的冗余条目

本文旨在解决字典条目间相似度计算中存在的冗余分组问题。通过将问题建模为图论中的“最大团问题”，并利用 networkx 库，我们可以根据不同的相似度分数构建多个图，然后在每个图中找到完全连接的节点集合（即团），从而优雅地将具有相同相似度的条目进行高效分组，避免了复杂的嵌套循环，并生成清晰的、按组聚合的结果。

1. 问题描述与挑战

在处理包含多个条目的字典数据时，我们经常需要计算这些条目之间的相似度。例如，给定一个字典，其中每个键对应一个包含多个属性的子字典：

my_dict = {
    'A': {'HUE_SAT': 1, 'GROUP_INPUT': 1, 'GROUP_OUTPUT': 1},
    'D': {'HUE_SAT': 1, 'GROUP_INPUT': 1, 'GROUP_OUTPUT': 1},
    'T': {'HUE_SAT': 1, 'GROUP_INPUT': 1, 'GROUP_OUTPUT': 1},
    'O': {'GROUP_INPUT': 3, 'MAPPING': 2, 'TEX_NOISE': 2, 'UVMAP': 2, 'VALTORGB': 3, 'GROUP_OUTPUT': 1, 'AMBIENT_OCCLUSION': 1, 'MIX': 4, 'REROUTE': 1, 'NEW_GEOMETRY': 1, 'VECT_MATH': 1},
    # ... 更多条目
}

登录后复制

通常，我们会编写一个相似度计算函数（例如余弦相似度），并遍历所有可能的条目对来计算它们之间的相似度。这会生成一个包含大量冗余信息的相似度字典，例如：

results = {
    ('A', 'D'): 1.0,
    ('A', 'C'): 1.0,
    ('D', 'A'): 1.0,  # 与 ('A', 'D') 冗余
    ('D', 'C'): 1.0,
    ('C', 'A'): 1.0,  # 与 ('A', 'C') 冗余
    ('C', 'D'): 1.0,
    # ...
}

登录后复制

我们的目标是将这些具有相同相似度且彼此之间也具有该相似度的条目进行分组，形成类似 ('A', 'D', 'C'): 1.0 这样的聚合结果，从而消除冗余并提高数据的可读性与利用效率。传统的嵌套循环尝试解决此问题往往会导致代码复杂且难以维护。

2. 相似度计算函数示例

为了演示，我们沿用问题中提供的余弦相似度函数。这个函数接收两个字典作为输入，并返回它们之间的余弦相似度。

from math import sqrt
from itertools import combinations # 导入 combinations 用于生成所有不重复的对

def square_root(x):
    """计算向量平方和的平方根，用于余弦相似度的分母。"""
    return round(sqrt(sum([a * a for a in x])), 3)

def cosine_similarity(a, b):
    """
    计算两个字典（视为向量）之间的余弦相似度。
    字典的键被视为维度，值被视为维度上的分量。
    """
    # 确保输入字典的键集合一致性，并构建向量
    all_keys = sorted(list(set(a.keys()) | set(b.keys()))) # 合并所有键并排序以保持一致性

    vector1 = [float(a.get(k, 0)) for k in all_keys]
    vector2 = [float(b.get(k, 0)) for k in all_keys]

    numerator = sum(v1 * v2 for v1, v2 in zip(vector1, vector2))
    denominator = square_root(vector1) * square_root(vector2)

    if denominator == 0: # 避免除以零
        return 0.0
    return round(numerator / float(denominator), 3)

# 原始数据
my_dict = {
    'A': {'HUE_SAT': 1, 'GROUP_INPUT': 1, 'GROUP_OUTPUT': 1},
    'D': {'HUE_SAT': 1, 'GROUP_INPUT': 1, 'GROUP_OUTPUT': 1},
    'T': {'HUE_SAT': 1, 'GROUP_INPUT': 1, 'GROUP_OUTPUT': 1},
    'O': {'GROUP_INPUT': 3, 'MAPPING': 2, 'TEX_NOISE': 2, 'UVMAP': 2, 'VALTORGB': 3, 'GROUP_OUTPUT': 1, 'AMBIENT_OCCLUSION': 1, 'MIX': 4, 'REROUTE': 1, 'NEW_GEOMETRY': 1, 'VECT_MATH': 1},
    'C': {'HUE_SAT': 1, 'GROUP_INPUT': 1, 'GROUP_OUTPUT': 1}, # 添加'C'用于演示
    'L': {'GROUP_INPUT': 3, 'MAPPING': 2, 'TEX_NOISE': 2, 'UVMAP': 2, 'VALTORGB': 3, 'GROUP_OUTPUT': 1, 'AMBIENT_OCCLUSION': 1, 'MIX': 4, 'REROUTE': 1, 'NEW_GEOMETRY': 1, 'VECT_MATH': 1}, # 添加'L'用于演示
}

# 计算所有不重复的相似度对
pairwise_similarities = {}
for k1, k2 in combinations(my_dict.keys(), 2):
    pairwise_similarities[(k1, k2)] = cosine_similarity(my_dict[k1], my_dict[k2])

print("初始计算的相似度对：")
print(pairwise_similarities)
# 示例输出可能为：
# {('A', 'D'): 1.0, ('A', 'T'): 1.0, ('A', 'O'): 0.0, ('A', 'C'): 1.0, ('A', 'L'): 0.0,
#  ('D', 'T'): 1.0, ('D', 'O'): 0.0, ('D', 'C'): 1.0, ('D', 'L'): 0.0,
#  ('T', 'O'): 0.0, ('T', 'C'): 1.0, ('T', 'L'): 0.0,
#  ('O', 'C'): 0.0, ('O', 'L'): 1.0,
#  ('C', 'L'): 0.0}

登录后复制

3. 基于图论的解决方案：最大团问题

解决上述冗余分组问题的优雅方法是将其建模为图论中的“最大团问题”（Maximal Clique Problem）。其核心思想是：

构建图： 对于每一个独特的相似度分数，我们构建一个独立的无向图。
添加节点与边： 字典中的每个条目（键）被视为图中的一个节点。如果两个条目之间的相似度等于当前图所代表的相似度分数，则在这两个条目对应的节点之间添加一条边。
查找最大团： 在每个图中，一个“团”是指一个子图，其中任意两个节点之间都存在一条边。一个“最大团”是不能再通过添加更多节点来扩展的团。在本场景中，一个最大团就代表了一个条目组，其中所有成员彼此之间都具有相同的相似度。

networkx 是一个强大的Python库，用于创建、操作和研究图的结构、动态和功能。它提供了高效的算法来查找图中的团。

通义万相

通义万相，一个不断进化的AI艺术创作大模型

596

查看详情

4. 使用 networkx 实现分组

以下是使用 networkx 库来解决该问题的步骤和代码示例：

首先，确保安装了 networkx： pip install networkx

from collections import defaultdict
import networkx as nx

# 1. 准备数据：使用前面计算的 pairwise_similarities
# pairwise_similarities 已经包含所有不重复的相似度对

# 2. 根据不同的相似度值构建图
graphs = defaultdict(nx.Graph)
for (p, q), s in pairwise_similarities.items():
    # 考虑浮点数精度问题，可以对相似度进行适当的四舍五入或量化
    # 例如，如果相似度是浮点数，直接作为键可能导致精度问题，
    # 可以将其转换为整数或固定小数位数再作为键。
    # 这里我们假设相似度值已经足够精确或不需要额外处理。
    graphs[s].add_edge(p, q)

# 3. 查找每个图中的最大团
cliques = {}
for s, G in graphs.items():
    # nx.find_cliques(G) 返回图中所有最大团的迭代器
    # 每个团是一个节点列表
    for clique in nx.find_cliques(G):
        # 确保团的大小大于1，因为单个节点不能形成一个“组”
        if len(clique) > 1:
            # 将团转换为元组作为键，相似度作为值
            # 注意：nx.find_cliques 找到的是最大团，即不能再通过添加节点扩大的团。
            # 这可能意味着一个大团内部的子团不会被单独列出，但大团本身已经包含了这些关系。
            cliques[tuple(sorted(clique))] = s # 排序元组以确保唯一性

print("\n分组后的相似度结果：")
# 打印结果，可以按相似度排序
sorted_cliques = sorted(cliques.items(), key=lambda item: item[1], reverse=True)
for group, sim_score in sorted_cliques:
    print(f"{group}: {sim_score}")

登录后复制

代码解释：

from collections import defaultdict: defaultdict 是一个字典子类，它允许我们在访问不存在的键时提供一个默认值。在这里，它用于在首次遇到某个相似度值时自动创建一个新的 nx.Graph 对象。
import networkx as nx: 导入 networkx 库。
graphs = defaultdict(nx.Graph): 创建一个 defaultdict，其默认工厂函数是 nx.Graph。这意味着当我们尝试访问 graphs[s] 且 s 不存在时，会自动创建一个新的空图并将其与 s 关联。
for (p, q), s in pairwise_similarities.items():: 遍历之前计算的所有不重复的相似度对。
graphs[s].add_edge(p, q): 对于每一对 (p, q) 及其相似度 s，我们将其添加到与相似度 s 关联的图中。这意味着所有相似度为 s 的节点对都会在这个特定的图 graphs[s] 中形成一条边。
for s, G in graphs.items():: 遍历所有已创建的图，每个图 G 对应一个独特的相似度 s。
nx.find_cliques(G): 这是 networkx 的核心函数之一，用于查找图 G 中的所有最大团。一个最大团是一个节点集合，其中集合内的任意两个节点之间都存在一条边，并且这个集合不能再通过添加任何一个节点来扩大而仍然保持团的属性。
if len(clique) > 1:: 我们只关心包含两个或更多条目的组，因为单个条目无法形成一个“组”。
cliques[tuple(sorted(clique))] = s: 将找到的团（一个节点列表）转换为元组，并对其进行排序以确保作为字典键的唯一性和一致性（例如，('A', 'C', 'D') 和 ('D', 'A', 'C') 会被视为同一个键）。然后将该团及其对应的相似度 s 存储到 cliques 字典中。

5. 注意事项与总结

浮点数精度： 在使用浮点数作为字典键或进行比较时，始终要警惕浮点数精度问题。如果相似度值有微小差异但逻辑上应被视为相同，建议在将相似度作为 graphs 字典的键之前对其进行适当的四舍五入或量化（例如，int(s * 1000 + 0.5)）。
最大团的定义： nx.find_cliques 找到的是“最大团”，这意味着如果 (A, B, C) 是一个团，且 (A, B) 也是一个团，那么只有 (A, B, C) 会被报告，因为它是更大的那个。这符合我们分组的需求，因为它聚合了尽可能多的具有相同相似度的条目。
性能： 查找最大团是一个NP-完全问题，对于非常大的图（即非常多的条目和非常复杂的相似度关系），计算时间可能会显著增加。然而，对于大多数实际应用场景，networkx 的实现通常足够高效。
灵活性： 这种基于图论的方法与具体的相似度计算函数无关。您可以替换为任何其他相似度函数（如Jaccard相似度、欧氏距离等），只要它能产生一个相似度分数即可。

通过将冗余分组问题转化为图论中的最大团问题，并利用 networkx 这样的专业库，我们能够以一种结构化、高效且易于理解的方式解决复杂的条目分组需求，极大地提升了代码的简洁性和可维护性。

以上就是如何高效分组字典中具有相同相似度的冗余条目的详细内容，更多请关注php中文网其它相关文章！