如何从MinHash LSH生成相似度矩阵？用于聚类分析

我懂你这种头疼的感觉——MinHash LSH工具大多主打高效定位近似相似对，默认不会输出全量的相似度矩阵，毕竟对稍大一点的数据集来说，n×n的矩阵内存开销根本扛不住（比如10万条数据的矩阵要占80GB以上的内存）。不过根据你的聚类需求，我们可以分场景来实现目标：

场景1：数据集规模小（≤5000条）——直接生成全量相似度矩阵 #

如果你的数据量不大，完全可以跳过LSH的“近似匹配”环节，直接用每个样本的MinHash签名计算Jaccard相似度，生成完整矩阵。这里用datasketch库举个例子：

from datasketch import MinHash
import numpy as np

# 假设你已经为每个样本生成了MinHash对象，存在minhash_list列表中
sample_count = len(minhash_list)
similarity_matrix = np.zeros((sample_count, sample_count))

# 利用矩阵对称性减少计算量
for i in range(sample_count):
    similarity_matrix[i][i] = 1.0  # 自身相似度为1
    for j in range(i + 1, sample_count):
        sim = minhash_list[i].jaccard(minhash_list[j])
        similarity_matrix[i][j] = sim
        similarity_matrix[j][i] = sim

# 之后就可以把这个矩阵传入聚类算法，比如层次聚类
from sklearn.cluster import AgglomerativeClustering
clustering = AgglomerativeClustering(affinity='precomputed', linkage='average').fit(similarity_matrix)

场景2：数据集规模大——用LSH相似对构建邻接表做图聚类 #

大数据下生成全矩阵不现实，而LSH输出的相似对刚好可以用来构建相似图，然后用图聚类算法（比如Louvain、Label Propagation）完成聚类，这也是LSH+聚类的常规高效方案：

import networkx as nx
from community import community_louvain

# 假设你从LSH工具中得到了相似对列表，格式为[(样本索引1, 样本索引2, 相似度), ...]
similar_pairs = get_lsh_similar_pairs()  # 替换成你的实际获取逻辑

# 构建无向加权图
G = nx.Graph()
for idx1, idx2, sim in similar_pairs:
    G.add_edge(idx1, idx2, weight=sim)
# 给孤立节点（没有相似对的样本）单独添加自环，避免聚类时被忽略
for idx in range(sample_count):
    if idx not in G.nodes:
        G.add_node(idx)

# 运行Louvain聚类（目前最流行的图聚类算法之一）
cluster_result = community_louvain.best_partition(G, weight='weight')
# cluster_result是字典，key为样本索引，value为聚类标签

如果想用DBSCAN这类基于密度的聚类，也可以用相似对生成每个样本的近邻列表，再传入DBSCAN：

from sklearn.cluster import DBSCAN
from sklearn.neighbors import NearestNeighbors

# 先把相似对转换成邻接表格式
adj_list = {idx: [] for idx in range(sample_count)}
for idx1, idx2, sim in similar_pairs:
    adj_list[idx1].append((idx2, sim))
    adj_list[idx2].append((idx1, sim))

# 或者用MinHash签名构建KD-Tree找近邻（适合中等规模数据）
nn = NearestNeighbors(metric=lambda x, y: 1 - MinHash.jaccard(x, y))
nn.fit([mh.digest() for mh in minhash_list])
# 找每个样本的top-k近邻
neighbors = nn.kneighbors(n_neighbors=10, return_distance=False)

# 传入DBSCAN（注意metric用precomputed时需要距离矩阵，这里用近邻列表更高效）
dbscan = DBSCAN(eps=0.3, min_samples=5, metric='precomputed')

场景3：必须要近似相似度矩阵（比如某些聚类算法强制要求） #

如果你的聚类算法必须输入矩阵格式，可以用稀疏矩阵来存储只保留大于阈值的相似度，避免内存爆炸：

import scipy.sparse as sp

sample_count = len(minhash_list)
# 初始化LIL格式稀疏矩阵（方便修改）
sparse_sim_matrix = sp.lil_matrix((sample_count, sample_count))

# 填充相似对的相似度
for idx1, idx2, sim in similar_pairs:
    sparse_sim_matrix[idx1, idx2] = sim
    sparse_sim_matrix[idx2, idx1] = sim
# 对角线填充1（自身相似度）
for i in range(sample_count):
    sparse_sim_matrix[i, i] = 1.0

# 转换成CSR格式（适合大多数聚类算法的输入要求）
sparse_sim_matrix = sparse_sim_matrix.tocsr()

# 比如传入层次聚类
from sklearn.cluster import AgglomerativeClustering
clustering = AgglomerativeClustering(affinity='precomputed', linkage='average').fit(sparse_sim_matrix)

关键提醒 #

MinHash LSH的核心优势是避免全量计算，所以如果不是必须，优先用图聚类或基于近邻的聚类方案，既符合LSH的设计初衷，又能高效处理大数据。

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