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, k10, metriceuclidean): 计算共享最近邻相似度 X: 样本特征矩阵shape (n_samples, n_features) k: 近邻个数 metric: 距离度量方式 返回: 稀疏SNN相似度矩阵 # 1. 构建k近邻图 nn NearestNeighbors(n_neighborsk1, metricmetric, 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, dtypenp.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(axis1)).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, k1) return sparse.csr_matrix(snn_similarity)这段代码用到了稀疏矩阵乘法来加速共享邻居数统计是一个很重要的小技巧。如果采用暴力双重循环两层循环的复杂度是O(n^2)数据量上万后就开始卡了。换成矩阵乘法后底层调BLAS库速度提升几个数量级。拿到SNN相似度矩阵后我通常直接用DBSCAN聚类。这里有个关键点要注意DBSCAN默认用metriceuclidean如果想把它改成用预计算距离矩阵需要传入的矩阵是“距离”而不是“相似度”需要做一个转换例如用1减去相似度矩阵。from sklearn.cluster import DBSCAN snn_sim compute_snn_similarity(X, k15) snn_dist 1 - snn_sim.toarray() # 使用预计算距离矩阵 db DBSCAN(eps0.5, min_samples5, metricprecomputed) 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相似度区分度下降。我在这个项目里做了从k5到k60的网格实验评估指标综合了轮廓系数、聚类的业务可解释性、簇大小的稳定性。最终k20的效果最为均衡。下面这个表格记录了我对不同k值的主观和客观评估k值轮廓系数簇数量噪声点比例业务可解释性50.21128.1%差簇内用户行为混杂100.2794.5%中等个别簇有清晰画像150.3172.8%较好大部分簇可解释200.3451.2%好5个簇画像都很清晰300.3040.6%中等簇边界模糊600.2530.1%差颗粒度太粗业务可解释性是我特别关注的维度。算法效果再好如果聚出的簇无法用业务语言描述运营团队也没法用。k20时得到的5个簇分别对应了“高价值高频复购用户”、“新客成长型用户”、“价格敏感型用户”、“大额低频用户”、“沉睡唤醒用户”业务方看到这些标签后可以直接落地运营动作。DBSCAN的eps参数也在同步调。SNN相似度分布大致呈偏态分布大量点对相似度接近0少量点对相似度很高。我会选取SNN相似度分布的80分位数作为eps的初始值再结合簇数量做微调。min_samples一般取2到5就够这个参数在SNN场景下不敏感只要不低于2结果差距不大。4.3 对比传统聚类的效果在同一个数据集上我把SNNDBSCAN和三种常见方案做了对比方案轮廓系数业务可解释性调参复杂度KMeans0.09差簇间重叠严重低传统DBSCAN欧氏距离-0.03差几乎全部点被当成噪声高PCA降维到50维KMeans0.16中等部分簇有含义中SNN相似度DBSCAN0.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的metricprecomputed要求距离矩阵是对称的、对角线为0的矩阵。如果不把SNN相似度转成距离且对角线未置0运行时会直接报错或者更糟糕的是不报错但结果完全不可用。用1减去相似度后还要注意数值下限截断避免因为浮点数误差出现极小的负值。第四个坑是高维稀疏数据下用精确k近邻搜索太慢。之前我在200万行、800维的数据上跑过sklearn的KNeighborsClassifier自带的brute-force算法吃掉了几乎所有运行时间。后来我换了Annoy做近似k近邻k20、搜索时扩展因子设置为150SNN结果跟精确版对比大约有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图上跑出稳定的社区划分速度也足够快。十万节点大概几十秒就能出结果。如果你还在为高维数据的聚类问题头疼我真心建议试试这条技术路线它会让你对“相似度”这件事的理解完全换一个角度。