如何聚类两两互近的点？寻求替代DBSCAN连通式聚类的方法

你需要的是团聚类（Clique Clustering）：每个簇是一个完全子图（Clique），即簇内任意两个点都彼此接近（对应邻接矩阵中的1），而非DBSCAN那种基于连通性的扩展聚类。以下是具体的实现方法和工具：

核心思路 #

团聚类的本质是将图划分为互不重叠的完全子图，每个子图内的所有节点两两相连（满足“彼此接近”的条件）。由于团划分是NP难问题，实际中常用启发式算法（如贪心策略）来获取近似解，结果可能有多种形式，符合你给出的[0 0 1 1 1 2 2]等预期。

工具与代码实现 #

使用NetworkX（Python） #

NetworkX是常用的图论工具库，内置团检测相关函数，可快速实现需求：

import numpy as np
import networkx as nx

# 你的邻接矩阵（1=两点接近，0=不接近）
adj = np.array([
    [1,1,0,1,0,1,1],
    [1,1,0,0,1,1,1],
    [0,0,1,1,1,0,0],
    [1,0,1,1,1,0,0],
    [0,1,1,1,1,1,1],
    [1,1,0,0,1,1,1],
    [1,1,0,0,1,1,1]])

# 从邻接矩阵构建无向图
G = nx.from_numpy_array(adj, create_using=nx.Graph())

# 贪心式团划分：找出所有最大团，再为未分配节点分配簇
labels = np.full(len(G), -1)
cluster_id = 0

# 遍历所有最大团，优先分配未被标记的节点
for clique in nx.find_cliques(G):
    unassigned = [node for node in clique if labels[node] == -1]
    if unassigned:
        labels[unassigned] = cluster_id
        cluster_id += 1

print(labels)

运行后可能得到类似[0 0 1 1 2 0 0]的结果，符合你预期的两两互近簇划分。

其他可选工具 #

• igraph：性能优于NetworkX，适合处理大规模图，提供max_cliques()等函数实现团检测
• 自定义贪心算法：手动实现“每次找最大团→移除团内节点→重复至所有节点被分配”的逻辑，灵活性更高

注意事项 #

1. 若你的输入是距离矩阵而非相似度邻接矩阵，需先转换：设定距离阈值eps，距离≤eps则邻接矩阵对应位置为1，否则为0
2. 团划分的结果不唯一，不同启发式算法或遍历顺序可能得到不同的合法划分，均符合你的需求

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