共享最近邻相似度：解决高维稀疏数据聚类的利器

1. 为什么我会盯上共享最近邻相似度

1.1 高维距离失效的尴尬现场

做数据挖掘这些年，我最怕遇到的不是数据量太大，而是特征维度太高、还稀疏。之前接过一个项目，要基于用户的行为序列做分群，每个用户抽出来几百上千个特征，标签列一打开，全是稀疏的0和1。最开始我图省事，直接扔给KMeans，结果聚出来的簇，簇心之间几乎分不开，轮廓系数只有0.12左右。换成DBSCAN，效果更惨，因为DBSCAN对密度参数epsilon极其敏感，高维空间下两点之间的距离差距越来越小，不管怎么调epsilon，要么一大片全是噪声点，要么全被并成一个簇。

问题的根源在于：在高维空间里，欧氏距离、曼哈顿距离这类基于直线距离的度量方式会逐渐“失效”。所有点之间的距离都趋向于接近某个值，点的远近关系变得不再可靠。这不是数据的问题，而是距离度量本身在高维几何下的必然现象。

那时候我就在想，有没有一种度量方式，不直接依赖两个点之间的空间距离，而是通过它们的“邻居关系”来判断相似性？后来我接触到了共享最近邻相似度（Shared Nearest Neighbor，简称SNN），这个概念帮我解决了不止一次类似的困局。

1.2 SNN解决的是什么问题

SNN的核心思想特别朴素：如果两个样本点有很多相同的最近邻居，那它们就应该被认为是相似的，哪怕它们本身在空间中的直线距离不近。

看一个实际场景就明白了。假设一批用户行为数据被映射到高维空间里，用户A和用户B虽然欧氏距离比较远，但它们都频繁跟用户C、E、F、G产生相似行为。在传统距离度量下，A和B可能永远不会被分到同一个簇，但在SNN看来，A和B共享了四个邻居，相似度非常高，应该被归为同类。这个特性在聚类场景里尤其好用，因为它考虑的是“局部邻域结构的一致性”，而不是“绝对空间位置的接近程度”。

所以，SNN适合谁？我的答案很直接：如果你正在做高维稀疏数据的聚类、异常检测，或者你发现传统距离度量在你的数据集上怎么调参都效果平平，那SNN值得你认真试试。它不挑场景，但尤其擅长处理两类问题：一是高维数据下的距离失真，二是密度差异较大的数据分布形态。

2. SNN算法原理拆解：从k近邻到共享邻居

2.1 第一步：求得每个样本的k近邻集合

SNN的第一步，实际上就是先跑一遍k近邻搜索。对数据集中的每个点，找出距离它最近的k个邻居。这里的距离度量可以根据业务场景选择，欧氏距离、余弦距离、曼哈顿距离都可以，实践中最常用的仍然是欧氏距离和余弦距离。需要特别说明的是，这一步的k值和最终评判相似度的阈值是两个概念，k值决定了“每个点的邻居范围”，直接影响SNN相似度的粒度。

我刚开始实现的时候偷了个懒，直接用Scikit-learn里的NearestNeighbors，先把每个点的k近邻索引和距离求出来。本质上，这一步是在为每个样本构建一个“局部邻域结构”，后续相似度计算全部基于这个结构，不再碰原始距离。

2.2 第二步：统计共享邻居数量

拿到每个点的k近邻集合后，接下来的操作是计算任意两个点之间“共有多少个邻居”。这个数量就是共享邻居数，也就是SNN相似度的雏形。

举个例子，假设k取10，点A的邻居集合为{N1, N2, ..., N10}，点B的邻居集合为{M1, M2, ..., M10}。如果A和B的邻居集合有7个重合，那两个点的SNN原始相似度就是7。有一点必须注意，A和B本身是否在对方的邻居集合里，不同实现方式定义不一样，有的会把点自身排除，有的会保留。我在实际项目中倾向于把自身排除掉，这样统计出来的共享邻居数更纯粹，也更稳定。

2.3 第三步：相似度归一化与后续使用

原始共享邻居数有一个问题：数量级受k值影响很大。k取20时，共享邻居数动辄10以上；k取5时，共享邻居数可能大概率只有1或2。所以，使用原始共享邻居数跨数据集对比没有意义，需要在计算后做归一化处理。

比较常见的两种归一化方法是Jaccard相似度和余弦归一化。Jaccard的实现方式是用两个点邻居集合的交集大小除以并集大小，将相似度压缩到0到1之间。计算公式是：

SNN_Similarity(A, B) = |N(A) ∩ N(B)| / |N(A) ∪ N(B)|

另一种方式是直接除以k，效果类似，但Jaccard的好处是天然考虑到了两个点邻居集合大小可能不对称的情况。实际上在做聚类时，我并不会先把所有样本的SNN相似度算成一个稠密矩阵再跑聚类，那样计算量和存储量都扛不住。更合理的做法是，只保留相似度高于某个阈值的点对，构建一个稀疏的相似度图，然后用图上的连通分量、社区发现算法或者带权图聚类方法做后续分析。实际项目中，我最常用的路径是“SNN相似度 + DBSCAN”，用SNN相似度替代原始距离作为DBSCAN的度量输入，效果对比传统方案提升非常明显。

3. 工程实现与性能优化

3.1 基于Scikit-learn的快速实现

理论讲完就得动手。我先给出一版最基础、最容易理解的Python实现，适用于中小规模数据集。整体思路分四步：构建k近邻矩阵、统计共享邻居数、生成稀疏相似度矩阵、基于相似度矩阵做聚类。

import numpy as np from sklearn.neighbors import NearestNeighbors from scipy import sparse def compute_snn_similarity(X, k=10, metric='euclidean'): """ 计算共享最近邻相似度 X: 样本特征矩阵，shape (n_samples, n_features) k: 近邻个数 metric: 距离度量方式 返回: 稀疏SNN相似度矩阵 """ # 1. 构建k近邻图 nn = NearestNeighbors(n_neighbors=k+1, metric=metric, n_jobs=-1) nn.fit(X) # 这里+1是因为每个点自身也会被算作最近邻 knn_distances, knn_indices = nn.kneighbors(X) # 去掉自身 knn_indices = knn_indices[:, 1:] n_samples = X.shape[0] # 2. 构建邻居指示矩阵（稀疏） # 每一行对应一个样本点，记录它的邻居集合 indptr = np.arange(0, n_samples * k + 1, k) data = np.ones(n_samples * k, dtype=np.float32) neighbour_matrix = sparse.csr_matrix( (data, knn_indices.ravel(), indptr), shape=(n_samples, n_samples) ) # 3. 计算共享邻居数 # 利用稀疏矩阵乘法：SNN_raw = neighbour_matrix * neighbour_matrix.T snn_raw = neighbour_matrix.dot(neighbour_matrix.T) snn_raw = snn_raw.toarray() # 4. 归一化为SNN相似度 # 分母：两个点的邻居并集大小 = 各自邻居数之和 - 共享邻居数 neighbour_counts = np.asarray(neighbour_matrix.sum(axis=1)).ravel() total_counts = neighbour_counts[:, None] + neighbour_counts[None, :] union_size = total_counts - snn_raw # 防止除以0 union_size[union_size == 0] = 1 snn_similarity = snn_raw / union_size # 只保留上三角部分（对称矩阵），并且对角线置0 snn_similarity = np.triu(snn_similarity, k=1) return sparse.csr_matrix(snn_similarity)

这段代码用到了稀疏矩阵乘法来加速共享邻居数统计，是一个很重要的小技巧。如果采用暴力双重循环，两层循环的复杂度是O(n^2)，数据量上万后就开始卡了。换成矩阵乘法后，底层调BLAS库，速度提升几个数量级。

拿到SNN相似度矩阵后，我通常直接用DBSCAN聚类。这里有个关键点要注意：DBSCAN默认用metric='euclidean'，如果想把它改成用预计算距离矩阵，需要传入的矩阵是“距离”，而不是“相似度”，需要做一个转换，例如用1减去相似度矩阵。

from sklearn.cluster import DBSCAN snn_sim = compute_snn_similarity(X, k=15) snn_dist = 1 - snn_sim.toarray() # 使用预计算距离矩阵 db = DBSCAN(eps=0.5, min_samples=5, metric='precomputed') labels = db.fit_predict(snn_dist)

3.2 大数据量下的加速思路

如果样本量超过几十万甚至百万级别，上面的实现方式也会吃力，因为邻接矩阵本身是n×n的，哪怕用稀疏矩阵存储，在构建snn_similarity矩阵时调用toarray()转换稠密矩阵，内存也会直接爆掉。真实业务场景里，我一般会用以下三种优化方式。

第一种方式是直接返回稀疏矩阵，不转换成稠密矩阵，后续聚类算法也选择支持稀疏输入的版本。上面的代码里，snn_raw = neighbour_matrix.dot(neighbour_matrix.T)得到的就是稀疏格式，理论上可以在转成snn_similarity后直接返回稀疏格式，不需要toarray()。但要注意，后续的DBSCAN并不直接支持稀疏的预计算距离矩阵，这时候就需要换算法。

第二种方式是采用分块计算。将整个样本分成多个块，每个块内部计算SNN相似度，只保留超过阈值的位置，再拼接起来。这种方式牺牲了一部分准确性，但内存占用可控，速度也还可以。

第三种方式是用近似最近邻替代精确最近邻。用Faiss或者Annoy做k近邻搜索，先从百万级样本里快速找到每个点的近似k近邻，再基于这些近似邻居集合计算SNN相似度。亲测下来，在百万级数据上，用Annoy做粗筛，相对精确的k近邻搜索，往往只需要牺牲一点相似度精度，但耗时从小时级降到了分钟级，属于性价比非常高的一种取舍。

4. 实战案例：SNN在高维用户分群中的应用

4.1 场景设定与数据准备

2024年我做过一个交易平台用户行为分群的项目，场景是这样的：平台有约10万名活跃用户，每个用户提取了行为特征向量，包括浏览行为、点击行为、收藏加购、不同品类的成交转化等，经过编码和特征工程后，每个用户的特征维度达到1200多，数据稀疏率大概在85%左右。业务方的核心诉求是：把用户分成若干有清晰行为画像的群体，方便后续做精准运营触达。

在这个数据形态下，直接跑KMeans的效果我是有预期的——高维稀疏数据对基于质心的聚类方法极不友好。但为了形成对照，我还是先跑了一版KMeans，轮廓系数只有0.09。随后我切换到SNN方案。

数据预处理阶段有些细节值得一说。原始特征中有些字段是计数值，量纲差异极大。比如“近30天支付金额”可能达到数万，“近30天访问次数”只有几十，直接计算欧氏距离会导致金额字段主导了距离计算。我的处理方式是先做标准化，再对部分长尾分布的特征做log1p变换，压缩极值的影响。标准化之后就开始调SNN。

4.2 参数k的调优实验

SNN算法在工程落地中最关键的参数就是k值。k值太小，邻居集合噪声大，共享邻居数极不稳定；k值太大，邻居关系被过度平滑，局部结构被抹平，SNN相似度区分度下降。

我在这个项目里做了从k=5到k=60的网格实验，评估指标综合了轮廓系数、聚类的业务可解释性、簇大小的稳定性。最终k=20的效果最为均衡。

下面这个表格记录了我对不同k值的主观和客观评估：

k值	轮廓系数	簇数量	噪声点比例	业务可解释性
5	0.21	12	8.1%	差，簇内用户行为混杂
10	0.27	9	4.5%	中等，个别簇有清晰画像
15	0.31	7	2.8%	较好，大部分簇可解释
20	0.34	5	1.2%	好，5个簇画像都很清晰
30	0.30	4	0.6%	中等，簇边界模糊
60	0.25	3	0.1%	差，颗粒度太粗

业务可解释性是我特别关注的维度。算法效果再好，如果聚出的簇无法用业务语言描述，运营团队也没法用。k=20时得到的5个簇，分别对应了“高价值高频复购用户”、“新客成长型用户”、“价格敏感型用户”、“大额低频用户”、“沉睡唤醒用户”，业务方看到这些标签后可以直接落地运营动作。

DBSCAN的eps参数也在同步调。SNN相似度分布大致呈偏态分布，大量点对相似度接近0，少量点对相似度很高。我会选取SNN相似度分布的80分位数作为eps的初始值，再结合簇数量做微调。min_samples一般取2到5就够，这个参数在SNN场景下不敏感，只要不低于2，结果差距不大。

4.3 对比传统聚类的效果

在同一个数据集上，我把SNN+DBSCAN和三种常见方案做了对比：

方案	轮廓系数	业务可解释性	调参复杂度
KMeans	0.09	差，簇间重叠严重	低
传统DBSCAN（欧氏距离）	-0.03	差，几乎全部点被当成噪声	高
PCA降维到50维+KMeans	0.16	中等，部分簇有含义	中
SNN相似度+DBSCAN	0.34	好，5个簇画像清晰	中

这个结果说明了两件事。第一，PCA虽然能在一定程度上缓解高维稀疏问题，但降维不可避免会丢失局部邻域结构信息，而SNN恰好把局部邻域结构当作核心信息保存了下来。第二，传统DBSCAN在高维空间里几乎不可用，因为epsilon的选择空间被高维距离分布压得几乎没有回旋余地，而SNN把距离度量替换成基于邻居重合度的相似度，epsilon的调节空间变得非常充裕。

关于聚类后如何评估稳定性，我补充一个细节步骤：我把10万样本随机分成5份，分别做SNN聚类，检查同一个用户在不同子样本中的分群归属是否一致。结果是约83%的用户在5次聚类中归属完全一致，稳定性高于KMeans方案的71%。这种稳定性验证在真实业务场景中很实用，否则模型上线后用户分群结果反复横跳，运营侧是没法接受的。

5. 常见问题与排查技巧实录

5.1 几个我反复踩过的坑

SNN在实际使用中并不是一个“跑通就完事”的算法，坑多且隐蔽。我挑几个最常见的踩坑现场分享出来，希望大家能跳过。

第一个坑是在计算邻居集合时忘了去掉样本自身。如果k近邻搜索时把每个点自身也计入邻居集合，那么共享邻居数里就会混入自身的干扰，尤其在样本量不大时，这个干扰会被显著放大，导致SNN相似度虚高。所以，在算SNN矩阵时，每行至少要从邻居集合中移除索引等于自己行号的那个点。

第二个坑是数据标准化方式影响SNN稳定性。有些代码实现里直接对原始特征矩阵算k近邻，不同特征的量纲差异会导致近邻集合严重偏向量纲大的特征。我的建议是至少做一次z-score标准化。如果特征分布是明显的长尾形态，先做log变换再标准化，效果会更好。

第三个坑是SNN相似度矩阵直接输入给聚类算法时类型不匹配。DBSCAN的metric='precomputed'要求距离矩阵是对称的、对角线为0的矩阵。如果不把SNN相似度转成距离且对角线未置0，运行时会直接报错，或者更糟糕的是不报错但结果完全不可用。用1减去相似度后，还要注意数值下限截断，避免因为浮点数误差出现极小的负值。

第四个坑是高维稀疏数据下，用精确k近邻搜索太慢。之前我在200万行、800维的数据上跑过，sklearn的KNeighborsClassifier自带的brute-force算法吃掉了几乎所有运行时间。后来我换了Annoy做近似k近邻，k=20、搜索时扩展因子设置为150，SNN结果跟精确版对比大约有92%的相似度，但运行时间显著下降。如果你的数据量在万级别以下，直接精确搜索没问题；一旦上了百万级，建议尽早切换到近似方案。

5.2 避坑经验总结

我把这些经验整理成一个速查表，方便大家在实际项目中快速对照：

问题	症状	解决方案
邻居集合包含自身	SNN相似度普遍偏高，聚类边界模糊	移除索引等于行号的邻居点
特征未标准化	近邻集合被高量纲特征主导	z-score标准化或min-max标准化
相似度未转距离	DBSCAN报错或结果异常	1 - snn_similarity并截断到[0,1]区间
k值过小	聚类结果噪声大、不稳定	用网格搜索选k，观察轮廓系数
数据量过大	内存溢出或计算超时	用Annoy/Faiss做近似k近邻
稀疏矩阵转稠密	内存爆炸	全程保留稀疏结构，分批处理

还有一点想补充：SNN相似度矩阵本质上是一个“密度连通性”上下文矩阵，在计算时最好把阈值之外的相似度置为0，保留稀疏性。这不仅能大幅减少内存开销，还能避免噪声点对后续聚类的干扰。

5.3 调参心得：不只看轮廓系数

参数调优这件事，我的经验是不要只看轮廓系数，尤其在高维稀疏数据上，轮廓系数的波动对噪声点非常敏感，很容易误导。我更建议的做法是：先固定k，画出SNN相似度的分布直方图，观察是否存在明显的“长尾 + 高峰”结构；然后选择分布中相对清晰的分界点作为DBSCAN的eps初始值。

另一个判断维度是簇的规模分布。理想情况下，簇大小应当比较均衡，不要出现一个簇占用90%样本而其他簇都很小的情况。如果出现这种形态，说明k值或eps值可能失配，往往需要调整参数后观察簇规模的变化趋势。

我通常在项目初期，会用一组小样本快速跑完整个SNN + DBSCAN流程，确定一个粗略的参数范围，然后再放全量数据跑，这样能避免全量参数调优带来的时间损耗。

6. 从SNN到大规模图聚类的扩展之路

SNN相似度矩阵本身构建完成后，如果你并不满足于直接聚类，它还有一个非常值得尝试的扩展方向：把SNN相似度矩阵当作一个带权无向图的邻接矩阵，然后在这个图上跑社区发现算法。

我的实际做法是：设定一个相似度阈值，只保留相似度高于阈值的边。这样图的边数会大幅下降，一个十万节点的图通常变成稀疏到几百万条边的规模。然后我用Louvain算法做社区发现，得到的社区划分比直接聚类结果更平滑、更符合业务直觉，而且社区之间还可以做可视化展示，运营侧同事更容易理解。

这种方案在用户分群、商品关系图谱、相似图片聚类等场景下都适用。如果你已经算完了SNN矩阵，把所有点对的相似度都掌握在手里，那用什么算法做后续的切分，反而成了次要问题。关键是SNN这个“度量层”已经帮你去掉了高维空间的距离噪声。

这个思路的落地并不复杂，我在项目里用的是networkx加python-louvain库，几行代码就能在稀疏SNN图上跑出稳定的社区划分，速度也足够快。十万节点大概几十秒就能出结果。如果你还在为高维数据的聚类问题头疼，我真心建议试试这条技术路线，它会让你对“相似度”这件事的理解完全换一个角度。