Scipy层次聚类如何选择合适linkage方法实现簇内两两距离全为0

你要求的聚类规则是簇内所有成员两两距离均为0，本质是找无向图中的「团（clique）」，无向图的边定义为两点距离等于0。而scipy.cluster.hierarchy的所有linkage方法逻辑都不符合这个要求，不是linkage选择的问题：

• 你当前用的单连接（single）逻辑是：只要两点之间存在一条路径，路径上每步的距离都≤阈值，就会归为一类。你例子里ind5→ind4→ind9的路径每步距离都是0，所以被归为一类，完全忽略了ind5和ind9的直接距离为1的情况
• 全连接（complete）、平均连接（average）等其他linkage方法，判断的是簇间的聚合距离阈值，也无法保证簇内所有两两距离都为0，换linkage也解决不了你的需求。

推荐基于图的团查找方法实现你的需求，以下是两种常用场景的实现：

方法1：查找所有极大团（适合允许个体属于多个重叠簇的场景） #

极大团的定义是：无法再加入其他任何点、且团内所有点两两相连（对应你要求的两两距离为0）的簇，用networkx可以直接实现：

import networkx as nx
import pandas as pd

# 读取距离矩阵的代码和你原有逻辑一致
df = pd.read_csv(infile1, sep = '\t', index_col = 0)
# 初始化无向图
G = nx.Graph()
G.add_nodes_from(df.index)
# 添加边规则：两点距离为0时连边
for i, ind_a in enumerate(df.index):
    for j, ind_b in enumerate(df.index[i+1:]):
        if df.iloc[i, i+j+1] == 0:
            G.add_edge(ind_a, ind_b)
# 查找所有极大团
max_cliques = list(nx.find_cliques(G))
# 输出结果
for idx, clique in enumerate(max_cliques, 1):
    print(f"簇{idx}：{clique}")

你提供的示例数据跑出来的结果会包含两个3人团：['ind4', 'ind5', 'ind6']、['ind4', 'ind6', 'ind9']，剩下的个体都是单独簇，完全符合你的要求：ind5不会和ind9分到同一个簇。

方法2：非重叠团聚类（适合要求每个个体只属于一个簇的场景） #

如果你要求每个个体只能归到一个簇，可以优先分配大团，未被分配的点再继续归到对应簇：

# 接上面方法1的代码，已经得到max_cliques
# 按团的大小从大到小排序，优先分配大团
max_cliques.sort(key=lambda x: len(x), reverse=True)
assigned = set()
cluster_res = {}
cluster_id = 1

for clique in max_cliques:
    # 筛选当前团里还未被分配的个体
    unassigned = [x for x in clique if x not in assigned]
    if not unassigned:
        continue
    # 分配簇ID
    for ind in unassigned:
        cluster_res[ind] = cluster_id
        assigned.add(ind)
    cluster_id += 1

# 处理剩下没有进入任何多人团的个体
for ind in df.index:
    if ind not in assigned:
        cluster_res[ind] = cluster_id
        cluster_id += 1

# 输出和你原有格式一致的结果
result = pd.DataFrame(cluster_res.items(), columns=['Inds', 'Clusters']).sort_values('Inds')
print(result)

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