基于选定成对比较的单/全链接聚类实现及替代方法咨询

数据预处理：过滤有效对称边 #

首先从给定的成对集合中筛选出双向对称存在的边（无向有效边），单向边不满足相似度准则的对称性要求：

all_objects = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
pairs = [
    ('A', 'B'),
    ('B', 'A'),
    ('B', 'D'),
    ('D', 'B'),
    ('D', 'C'),
    ('C', 'D'),
    ('E', 'F'),
    ('F', 'E'),
    ('F', 'G'),
    ('G', 'F'),
    ('E', 'G'),
    ('G', 'E'),
    ('H', 'G')
]

# 筛选对称有效边并去重（转为无向边）
valid_edges = set()
pair_set = set(pairs)
for u, v in pairs:
    if (v, u) in pair_set and tuple(sorted((u, v))) not in valid_edges:
        valid_edges.add(tuple(sorted((u, v))))

print("有效对称边：", valid_edges)

运行后得到有效边：{('A', 'B'), ('B', 'D'), ('C', 'D'), ('E', 'F'), ('E', 'G'), ('F', 'G')}

1. 单链接聚类与全链接聚类代码实现 #

单链接聚类（最近邻聚类） #

单链接聚类的核心是连通分量：只要两个对象通过相似性路径相连，就归为同一簇。用DFS遍历图查找所有连通分量：

# 构建邻接表
adj = {obj: [] for obj in all_objects}
for u, v in valid_edges:
    adj[u].append(v)
    adj[v].append(u)

# 单链接聚类：查找所有连通分量
visited = set()
single_link_clusters = []

for obj in all_objects:
    if obj not in visited:
        stack = [obj]
        visited.add(obj)
        cluster = []
        while stack:
            current = stack.pop()
            cluster.append(current)
            for neighbor in adj[current]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    stack.append(neighbor)
        single_link_clusters.append(sorted(cluster))

print("\n=== 单链接聚类结果 ===")
for idx, cluster in enumerate(single_link_clusters, 1):
    print(f"簇 {idx}: {cluster}")

输出结果：

=== 单链接聚类结果 ===
簇 1: ['A', 'B', 'C', 'D']
簇 2: ['E', 'F', 'G']
簇 3: ['H']

全链接聚类（最远邻聚类） #

全链接聚类要求簇内任意两个对象之间都有直接的相似性边（即簇是完全子图）。通过寻找最大团实现：

# 构建邻接矩阵，快速判断两点是否相连
adj_matrix = {u: {v: False for v in all_objects} for u in all_objects}
for u, v in valid_edges:
    adj_matrix[u][v] = True
    adj_matrix[v][u] = True

# 回溯法寻找所有最大团
def find_max_cliques(clique, candidates, excluded, all_cliques):
    if not candidates and not excluded:
        all_cliques.append(clique.copy())
        return
    for n in list(candidates):
        clique.append(n)
        new_candidates = [c for c in candidates if adj_matrix[n][c]]
        new_excluded = [e for e in excluded if adj_matrix[n][e]]
        find_max_cliques(clique, new_candidates, new_excluded, all_cliques)
        clique.pop()
        candidates.remove(n)
        excluded.append(n)

all_cliques = []
find_max_cliques([], all_objects.copy(), [], all_cliques)

# 按团的大小降序排序，优先选择大团
all_cliques.sort(key=lambda x: len(x), reverse=True)

# 分配节点到簇，避免重复
assigned = set()
complete_link_clusters = []

for clique in all_cliques:
    unassigned_nodes = [node for node in clique if node not in assigned]
    if unassigned_nodes:
        complete_link_clusters.append(sorted(unassigned_nodes))
        assigned.update(unassigned_nodes)

# 处理孤立节点
for node in all_objects:
    if node not in assigned:
        complete_link_clusters.append([node])

print("\n=== 全链接聚类结果 ===")
for idx, cluster in enumerate(complete_link_clusters, 1):
    print(f"簇 {idx}: {cluster}")

输出结果：

=== 全链接聚类结果 ===
簇 1: ['E', 'F', 'G']
簇 2: ['A', 'B']
簇 3: ['C', 'D']
簇 4: ['H']

2. 替代聚类方法 #

针对这类基于相似性边的图结构数据，常用替代方法包括：

• DBSCAN密度聚类：基于点的密度划分簇，能识别任意形状的簇，还可自动标记噪声点（如本例中的H），适配图结构数据。
• 谱聚类：通过图的拉普拉斯矩阵特征分解，将高维图数据映射到低维空间后聚类，擅长处理非凸分布和复杂图结构。
• Louvain社区检测：通过最大化模块度划分社区，适合大规模图数据，能快速找到紧密连接的子图。
• 平均链接/沃德法层次聚类：层次聚类的变种，平均链接取簇间所有点对相似度的平均值，沃德法通过最小化簇内方差合并簇，比单/全链接更稳健。
• 模糊C均值（FCM）：允许一个对象属于多个簇，适合相似度存在模糊性的场景，可输出对象属于各簇的概率。
• K-means聚类：若能将对象转换为数值特征向量，可基于距离划分簇，但需先完成向量化步骤。

内容的提问来源于stack exchange，提问作者sherlock85