问题背景与传统方法的局限
在数据处理中，我们经常需要比较不同实体之间的相似性。假设我们有一个字典，其中键代表实体，值是这些实体的属性集合。例如：
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},
# ... 更多条目
}为了量化这些实体之间的相似性，我们通常会计算它们之间的相似度分数，例如余弦相似度。一种常见的做法是遍历所有可能的实体对，计算并存储它们的相似度：
from math import sqrt
def square_root(x):
return round(sqrt(sum([a * a for a in x])), 3)
def cosine_similarity(a, b):
# 确保a是较长的字典，以简化向量构建
input1, input2 = (a, b) if len(a) > len(b) else (b, a)
vector1 = list(input1.values())
vector2 = []
for k in input1.keys():
vector2.append(float(input2.get(k, 0))) # 如果key不存在，则视为0
numerator = sum(v1 * v2 for v1, v2 in zip(vector1, vector2))
denominator = square_root(vector1) * square_root(vector2)
return round(numerator / float(denominator), 3) if denominator != 0 else 0.0 # 避免除以零
# 假设 my_dict 已定义
keys = tuple(my_dict.keys())
pairwise_similarities = {}
for k1 in keys:
for k2 in keys:
if k1 != k2:
# 避免重复计算 (k1, k2) 和 (k2, k1)
if (k2, k1) not in pairwise_similarities:
pairwise_similarities[(k1, k2)] = cosine_similarity(my_dict[k1], my_dict[k2])
# 结果可能包含大量冗余信息，例如：
# {
# ('A', 'D'): 1.0,
# ('A', 'C'): 1.0,
# ('D', 'C'): 1.0,
# # ...
# }这种方法会产生大量冗余的成对相似度结果，例如('A', 'D'): 1.0和('D', 'A'): 1.0本质上是相同的。更重要的是，它并没有直接提供一种机制来识别并聚合所有彼此之间具有相同相似度分数的实体集合（例如，如果A、D、C三者之间两两相似度均为1.0，我们希望得到('A', 'D', 'C'): 1.0这样的分组）。手动通过嵌套循环和条件判断来构建这样的分组会变得异常复杂和低效。
图论方法：利用团（Clique）进行高效分组
为了解决上述问题，我们可以将数据分组的需求转化为图论中的“团问题”。其核心思想是：如果一组实体彼此之间都具有相同的相似度分数，那么它们可以被视为一个“团”。
具体步骤如下：
- 为每个独特的相似度值构建图： 遍历所有计算出的成对相似度。对于每一个独特的相似度值，我们创建一个独立的无向图。
-
添加节点和边：
- 图中的节点代表原始字典中的实体（例如 'A', 'D', 'T'）。
- 如果两个实体（例如 'A' 和 'D'）之间的相似度等于当前图所代表的相似度值，则在它们之间添加一条边。
- 寻找图中的团： 在每个构建好的图中，寻找所有的“极大团”（maximal cliques）。一个极大团是一个不能再添加任何其他节点而仍然保持团性质的团。在这个上下文中，每个极大团就代表了一个实体组，组内的所有实体彼此之间都具有相同的相似度分数。
这种方法利用了图论的强大表达能力和成熟的算法，能够优雅地解决复杂的实体分组问题。
使用 NetworkX 实现分组
Python的networkx库是一个功能强大的图论库，可以方便地构建图并查找团。下面是使用networkx实现上述分组逻辑的示例代码：
from collections import defaultdict
from itertools import combinations
import networkx as nx
from math import sqrt
# ----------------------------------------------------------------
# 1. 原始数据和相似度计算函数 (与问题描述中的函数相同)
# ----------------------------------------------------------------
def square_root(x):
return round(sqrt(sum([a * a for a in x])), 3)
def cosine_similarity(a, b):
input1, input2 = (a, b) if len(a) > len(b) else (b, a)
vector1 = list(input1.values())
vector2 = []
for k in input1.keys():
vector2.append(float(input2.get(k, 0)))
numerator = sum(v1 * v2 for v1, v2 in zip(vector1, vector2))
denominator = square_root(vector1) * square_root(vector2)
return round(numerator / float(denominator), 3) if denominator != 0 else 0.0
# 示例数据
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},
'C': {'HUE_SAT': 1, 'GROUP_INPUT': 1, 'GROUP_OUTPUT': 1}, # 添加'C'以便形成一个1.0相似度的组
'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},
}
# ----------------------------------------------------------------
# 2. 计算所有实体对的相似度
# ----------------------------------------------------------------
# 使用itertools.combinations生成所有不重复的实体对
all_entity_pairs_similarities = {}
for p, q in combinations(my_dict.keys(), 2):
all_entity_pairs_similarities[(p, q)] = cosine_similarity(my_dict[p], my_dict[q])
print("所有实体对的相似度 (部分):")
print({k: v for i, (k, v) in enumerate(all_entity_pairs_similarities.items()) if i < 5}) # 打印前5个
print("-" * 30)
# ----------------------------------------------------------------
# 3. 为每个独特的相似度值构建图
# ----------------------------------------------------------------
# 使用defaultdict来自动创建图
graphs = defaultdict(nx.Graph)
for (p, q), s in all_entity_pairs_similarities.items():
# 浮点数比较可能存在精度问题，建议对相似度值进行适当的四舍五入或量化
# 例如，s_key = int(1000 * s + 0.5) 可以将相似度映射到整数键
# 或者直接使用round(s, N)
s_key = round(s, 5) # 四舍五入到5位小数作为键
graphs[s_key].add_edge(p, q)
print(f"构建了 {len(graphs)} 个图，对应不同的相似度值。")
print("-" * 30)
# ----------------------------------------------------------------
# 4. 查找每个图中的极大团
# ----------------------------------------------------------------
cliques = {}
for s_value, G in graphs.items():
# nx.find_cliques 返回一个迭代器，生成图G中的所有极大团
for clique in nx.find_cliques(G):
# 团的节点数量必须大于1才有意义，因为单个节点不是“组”
if len(clique) > 1:
# 将团转换为元组作为键，相似度值作为值
# 注意：同一个团可能在不同的相似度图中找到，但其相似度值是唯一的
cliques[tuple(sorted(clique))] = s_value # 对团内的元素进行排序，确保键的唯一性
print("分组结果 (团):")
for k, v in cliques.items():
print(f"{k}: {v}")
# 预期输出示例 (可能因数据和相似度计算略有不同):
# ('A', 'C', 'D', 'T'): 1.0
# ('L', 'O', 'S'): 1.0 (如果它们之间相似度也是1.0)代码解析与注意事项
- 相似度计算 (cosine_similarity): 保持了原始问题中的余弦相似度函数，并添加了除以零的保护。这个函数是通用的，可以替换为任何其他适合你数据的相似度度量。
- 生成实体对 (itertools.combinations): itertools.combinations(my_dict.keys(), 2)是生成所有不重复实体对的有效方式，避免了手动嵌套循环和条件判断来处理 (k1, k2) 和 (k2, k1) 的冗余。
- 浮点数精度 (round(s, 5)): 浮点数在计算机中表示时可能存在精度问题，这会导致即使理论上相等的相似度值在实际存储时也略有不同。为了确保具有相同相似度的实体被分到同一个图，我们必须对相似度值进行统一的四舍五入或量化，作为graphs字典的键。这里使用了round(s, 5)，表示保留5位小数。
- defaultdict(nx.Graph): defaultdict在访问不存在的键时会自动创建一个nx.Graph对象，这使得为每个新的相似度值创建图变得非常简洁。
- nx.find_cliques(G): 这是networkx库的核心功能，用于查找图中所有的极大团。它返回一个生成器，每次迭代产生一个团（一个节点列表）。
- 结果存储 (cliques): 最终结果cliques字典的键是一个元组，包含一个团中的所有实体（已排序以确保唯一性），值是这些实体之间的相似度分数。我们过滤掉了长度为1的团，因为单个实体不能构成一个“组”。
总结
通过将字典条目分组问题转化为图论中的团问题，并利用networkx库的强大功能，我们能够以一种结构化、高效且优雅的方式解决实体聚合的需求。这种方法不仅避免了传统嵌套循环的复杂性，还提供了清晰的逻辑来识别所有彼此之间具有相同相似度分数的实体集合，从而实现了数据的高效组织和分析。在实际应用中，请注意相似度计算的精度以及对于大规模数据集，团查找算法的计算复杂性可能带来的性能考量。
