Python中基于相似度对字典条目进行分组：图论与最大团算法-Python教程-PHP中文网

Python中基于相似度对字典条目进行分组：图论与最大团算法

针对字典条目间的冗余相似性比较问题，本教程介绍了一种基于图论和最大团算法的优雅解决方案。通过为每个独特的相似度值构建一个图，并将字典键作为节点，相似条目间的边作为连接，我们可以利用networkx库高效地识别出具有相同相似度的最大分组（即最大团），从而将具有相同相似性分数的条目进行有效聚合，避免重复计算并简化数据结构。

引言：处理字典条目相似性分组的挑战

在数据处理和分析中，我们经常需要计算不同数据点之间的相似度。当数据点以字典的形式存在时，例如：

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},
    # ... 更多条目
}

登录后复制

我们可能会计算所有条目间的成对相似度。然而，这种计算方式常常导致结果中出现大量冗余，例如 ('A', 'D'): 1.0 和 ('D', 'A'): 1.0。更进一步的需求是，我们希望将所有相互之间具有相同相似度分数的条目聚合到一个组中，形成如 ('A', 'D', 'C'): 1.0 这样的更简洁、有意义的结构，而不是零散的成对关系。

传统的迭代和缓冲方法，如尝试使用多层嵌套循环和条件判断来构建这些分组，往往会导致代码逻辑复杂、难以维护且效率低下。为了解决这个问题，我们可以引入图论中的最大团（Maximal Clique）概念，提供一个更为优雅和高效的解决方案。

核心概念：将问题转化为图论中的最大团问题

图论为解决复杂的分组和连接问题提供了强大的抽象工具。我们可以将字典条目相似性分组问题巧妙地转化为一个图论问题：

构建图 (Graph)：

立即学习“Python免费学习笔记（深入）”；
- 节点 (Vertices)： 原始字典中的每个键（例如 'A', 'D', 'T', 'O'）都代表图中的一个节点。
- 边 (Edges)： 如果两个节点（即两个字典键）之间的相似度达到某个特定的值，那么它们之间就存在一条边。
最大团 (Maximal Clique)：

百度文心百中
百度大模型语义搜索体验中心

22

查看详情
- 定义： 在一个无向图中，一个团是一个子图，其中任意两个节点之间都存在一条边。最大团是指一个团，它不能通过添加任何其他节点而变得更大。换句话说，它是图中一个完全连接的子图，且不是任何更大完全连接子图的真子集。
- 问题映射： 为什么找到最大团能够解决我们的分组问题？设想我们为每一个独特的相似度值构建一个独立的图。在这个图中，如果 'A' 和 'D' 之间有边，'D' 和 'C' 之间有边，'A' 和 'C' 之间也有边，并且它们都对应着相同的相似度分数（例如 1.0），那么 'A', 'D', 'C' 就形成了一个团。这个团正是我们所寻求的、相互之间具有相同相似度的分组。通过寻找这些团，我们就能有效地聚合具有相同相似性的条目。

使用 networkx 库实现相似性分组

networkx 是一个强大的 Python 库，用于创建、操作和研究图结构。它提供了高效的算法来实现图论中的各种操作，包括查找最大团。

步骤一：计算所有条目间的成对相似度

首先，我们需要一个函数来计算任意两个字典条目之间的相似度。这里使用余弦相似度作为示例，但此方法适用于任何自定义的相似度计算函数。

from math import sqrt
from itertools import combinations
import networkx as nx
from collections import defaultdict

# 原始字典数据
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},
    '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},
    'S': {'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},
    'N': {'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},
    'P': {'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},
}

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 = [a.get(k, 0) for k in all_keys]
    vector2 = [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)

# 计算所有不重复的成对相似度
pairwise_similarities = {}
keys = list(my_dict.keys())
for k1, k2 in combinations(keys, 2): # 使用combinations避免冗余和自比较
    pairwise_similarities[(k1, k2)] = cosine_similarity(my_dict[k1], my_dict[k2])

# 打印一些示例相似度结果
# print("成对相似度示例:")
# for (k1, k2), sim in pairwise_similarities.items():
#     print(f"  ('{k1}', '{k2}'): {sim}")

登录后复制

步骤二：为每个独特的相似度值构建独立的图

我们将使用 collections.defaultdict 来存储多个 networkx.Graph 对象，每个图对应一个独特的相似度值。

# 为每个独特的相似度值构建图
graphs_by_similarity = defaultdict(nx.Graph)

# 注意：浮点数比较可能存在精度问题。
# 可以选择对相似度值进行四舍五入或乘以一个大整数后再取整，
# 以确保相近的浮点数被视为相同的值。
# 例如：sim_key = int(sim_value * 1000)
for (p, q), s in pairwise_similarities.items():
    # 示例中，相似度已经四舍五入到小数点后三位，可以直接使用
    graphs_by_similarity[s].add_edge(p, q)

# print("\n构建的图数量:", len(graphs_by_similarity))
# for s, G in graphs_by_similarity.items():
#     print(f"  相似度 {s} 对应的图有 {G.number_of_nodes()} 个节点, {G.number_of_edges()} 条边")

登录后复制

步骤三：在每个图中寻找最大团

最后，遍历所有构建的图，并使用 nx.find_cliques(G) 函数来查找每个图中的所有最大团。nx.find_cliques 返回一个生成器，生成图中的所有最大团。

# 存储最终的分组结果
grouped_entries = {}

for s, G in graphs_by_similarity.items():
    for clique in nx.find_cliques(G):
        # 将团（列表）转换为元组作为字典键，并关联其相似度值
        # 确保团内的元素按字母顺序排序，以保证结果的确定性
        grouped_entries[tuple(sorted(clique))] = s

# 打印最终分组结果，按相似度降序排列
print("\n最终分组结果:")
sorted_grouped_entries = sorted(grouped_entries.items(), key=lambda item: item[1], reverse=True)
for group, sim_score in sorted_grouped_entries:
    print(f"  {group}: {sim_score}")

登录后复制

完整示例代码

from math import sqrt
from itertools import combinations
import networkx as nx
from collections import defaultdict

# 原始字典数据
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},
    '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},
    'S': {'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},
    'N': {'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},
    'P': {'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},
}

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 = [a.get(k, 0) for k in all_keys]
    vector2 = [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)

def group_similar_entries(data_dict):
    """
    根据相似度对字典条目进行分组。

    Args:
        data_dict (dict): 待分组的字典，键是条目名称，值是特征字典。

    Returns:
        dict: 分组后的字典，键是条目名称的元组（代表一个组），值是该组的相似度分数。
    """

    # 1. 计算所有条目间的成对相似度
    pairwise_similarities = {}
    keys = list(data_dict.keys())
    for k1, k2 in combinations(keys, 2):
        pairwise_similarities[(k1, k2)] = cosine_similarity(data_dict[k1], data_dict[k2])

    # 2. 为每个独特的相似度值构建独立的图
    graphs_by_similarity = defaultdict(nx.Graph)
    for (p, q), s in pairwise_similarities.items():
        graphs_by_similarity[s].add_edge(p, q)

    # 3. 在每个图中寻找最大团
    grouped_entries = {}
    for s, G in graphs_by_similarity.items():
        for clique in nx.find_cliques(G):
            # 将团（列表）转换为元组作为字典键，并关联其相似度值
            # 确保团内的元素按字母顺序排序，以保证结果的确定性
            grouped_entries[tuple(sorted(clique))] = s

    return grouped_entries

# 执行分组
final_grouped_results = group_similar_entries(my_dict)

# 打印最终分组结果，按相似度降序排列
print("最终分组结果:")
sorted_final_results = sorted(final_grouped_results.items(), key=lambda item: item[

登录后复制

以上就是Python中基于相似度对字典条目进行分组：图论与最大团算法的详细内容，更多请关注php中文网其它相关文章！