最近在做一套用户行为分群系统特征是高维稀疏向量一开始我用欧氏距离算相似度结果聚类出来的簇几乎都是糊成一团。后来换了余弦相似度情况好了一点但对于密度差异很大的群体结果还是不稳定。折腾到最后是“共享最近邻相似度”Shared Nearest Neighbor简称SNN解决了问题。这个思路其实不复杂核心就一句话两个点像不像不光看它们离得近不近更要看它们共同认识多少“邻居”。这个思想最早来自Jarvis和Patrick在1973年提出的聚类算法后来在数据挖掘领域被反复使用尤其在高维数据、密度不均匀数据和噪声较多的场景里SNN的表现往往比传统距离度量稳定得多。如果你做聚类、做近邻检索、做异常检测或者正在被高维稀疏数据折磨这篇文章值得看完。我会把SNN的数学定义、计算流程、聚类应用、踩坑经验都过一遍最后给出一份可以直接跑的Python实现。1. 从“距离失效”说起为什么相似度度量会在大数据场景翻车很多人在做聚类或相似度计算时第一反应就是算距离。欧氏距离、曼哈顿距离、余弦相似度似乎是刻在DNA里的三板斧。但真实生产环境里这几个指标经常掉链子。1.1 高维空间里的“距离集中”陷阱在高维空间里所有点两两之间的距离会趋向于一个常数范围也就是所谓“距离集中”现象。这不是玄学背后是有数学原因的高维空间中坐标分量的方差贡献过于分散距离的增幅被维度数量的平方根稀释导致远近区分度急剧下降。举个例子在一个1000维的稀疏向量空间里随机取两个点和两个相似点它们之间的欧氏距离可能都在20到22之间浮动你根本无法通过绝对距离判断谁跟谁更像。余弦相似度在高维稀疏场景里比欧氏距离好一些但它只关心方向完全不关心局部密度——两个孤立的点和两个密集区域中的点即使余弦值相同实际语义也可能差得很远。1.2 密度不均衡时固定阈值必然顾此失彼另一个常见场景是密度差异大的数据。比如做用户分群时一线城市用户的行为数据稠密低频用户的特征非常稀疏。如果DBSCAN类算法用一个固定半径去扫描半径设大了稀疏簇被合并设小了稠密簇被切碎。你几乎找不到一个既能照顾稠密区域、又能覆盖稀疏区域的参数。这是基于密度方法的老大难问题。SNN应对这两个问题的方式完全不同。它不直接比较点之间的绝对距离而是先为每个点找出固定数量的最近邻然后比较这两个“邻居名单”的重合程度。高维空间里绝对距离可能失效但“谁是我最近的k个邻居”这个相对关系是稳定的同样不同密度区域中各点都按自己的局部情况取k个邻居不会出现固定半径那种“一杆子打翻一船人”的问题。1.3 噪声点给传统方法带来的麻烦还有一类问题是噪声点。传统KMeans会被离群点拉扯质心基于距离的相似度会让孤立点莫名跟某个簇产生中等强度关联。但在SNN里噪声点的邻居名单基本是随机拼凑的两个独立噪声点共享近邻的数量会天然趋近于零。这个“自动免疫噪声”的特性让SNN在真实脏数据上特别能打。2. SNN到底在算什么数学定义与直觉拆解这一节把SNN的原理讲透。我不会只给公式会把公式背后的直觉、变体选择、适用边界都展开让你拿到任何数据集时能自己判断该不该用。2.1 基础定义与计算流程给定一个数据集以及一个距离度量欧氏距离、余弦距离、曼哈顿距离皆可SNN相似度的计算分两步。第一步对每个点x找出它的k个最近邻记作集合N(x)。这里要注意k是用户指定的参数通常N(x)包含除x本身之外的k个点。第二步对任意两个点x和y定义SNN(x, y) |N(x) ∩ N(y)|也就是两个邻居集合的交集大小。交集越大说明两个点认识的人重叠越多它们越可能属于同一簇。例如k20时若SNN(x, y) 15意味着它们有15个共同邻居这是很强的“同伙”信号。这个定义简单到让人觉得有点朴素但它抓住了“物以类聚人以群分”的本质。在社区发现、推荐系统、生物学分类等领域共同邻居数量本身就是一种被广泛验证的关联强度指标。2.2 两种关键变体是否要求“互近邻”上面定义存在一个细微问题如果x把y列为近邻但y的邻居列表里根本没有x那么x和y算相似吗直觉上讲这种单方面“热脸贴冷屁股”的关系可信度是比较低的。因此Jarvis-Patrick原始算法里有个重要约束必须具备互近邻关系mutual nearest neighbor才参与相似度计算。也就是先判断x是否属于N(y)且y是否属于N(x)如果满足再用交集大小度量不满足则直接视为不相似。带不带互近邻约束对结果影响很大。我在实际项目中倾向于带上这个约束尤其是在簇边界模糊、点密度差异很大的数据中。不带互近邻约束时处于高密度区域边缘的点容易跟周围一堆低密度点产生虚假高相似度带约束后这些虚假连接会被直接切断。2.3 加权变体近邻排名里的信息不要浪费基础SNN只关心“是否在邻居名单里”完全忽略“在名单中排第几”。这其实是信息浪费。假设x和y共同拥有5个邻居且这5个邻居在双方名单里都排名前三另外一对点也共同拥有5个邻居但都是排在十五名开外的边缘邻居。显然前者的关系更牢固但基础SNN会把它们一视同仁。一个有效改进是在求交集时按排名加权。常见做法是给第r近邻赋予权重w(r)然后SNN(x, y) Σ w(r)叠加双方共享邻居的权重。权重函数可以用线性衰减、指数衰减或者基于排名的倒数函数。这样计算出来的相似度更能反映“强关系邻居”的贡献。代价是多了一个设计权重函数的步骤数据量小的时候直接用基础版就行不用过度设计。2.4 SNN不是距离也不是密度它是一张图理解SNN最好的方式是把它理解为一种“图的边权”。当你把所有点作为节点把SNN相似度作为节点之间的边权时你其实构造了一个加权的k近邻图。后面做聚类本质上是在对这个图做社区划分。这种视角的好处是聚类结果不受原始特征空间形状的限制可以拟合任意形状的簇包括环形、月牙形、甚至嵌套结构——这恰恰是KMeans做不到的。我会在第4节用一个具体实验展示这种形状拟合能力现在先记住SNN的输出是一个相似度矩阵后续接什么算法都行聚类、降维、异常检测都可以在这个矩阵上进行。3. 用Python从零构建SNN相似度与聚类理论讲多说无益直接上代码。这节提供一个完整、可运行的Python实现包含相似度矩阵计算、Jarvis-Patrick聚类、以及和传统方法的对比评估。3.1 数据集准备故意构造一个难例我故意生成一个让传统方法头疼的数据集外圈是一个环形簇内部是一个致密球状簇外加一些均匀分布的噪声点。数据量控制在几百个点方便可视化。import numpy as np import matplotlib.pyplot as plt from sklearn.datasets import make_circles, make_blobs from sklearn.preprocessing import StandardScaler # 环形簇 X_circle, _ make_circles(n_samples300, factor0.5, noise0.05) # 内部致密球状簇 X_blob, _ make_blobs(n_samples200, centers[[0, 0]], cluster_std0.15, random_state42) # 噪声点 rng np.random.RandomState(42) X_noise rng.uniform(low-1.5, high1.5, size(80, 2)) X np.vstack([X_circle, X_blob, X_noise]) X StandardScaler().fit_transform(X) plt.figure(figsize(6, 6)) plt.scatter(X[:, 0], X[:, 1], s8) plt.title(环形簇 致密簇 噪声点) plt.show()肉眼都能看出这个数据集有三个形态完全不同的部分但对很多聚类算法来说这已经是地狱难度了。3.2 SNN相似度矩阵计算接下来写核心代码。第一步用KD树或Ball Tree找出每个点的k近邻同时保留距离信息方便计算加权变体。这里直接用scikit-learn的NearestNeighbors。from sklearn.neighbors import NearestNeighbors def compute_knn_and_snn(X, k10, include_selfFalse): 计算k近邻索引和SNN相似度矩阵。 返回 knn_idx: 每个点的k近邻索引不含自身 snn: SNN相似度矩阵 (n x n) n X.shape[0] # k1是为了排除自身 nn NearestNeighbors(n_neighborsk 1, metriceuclidean) nn.fit(X) # distances和indices都是 (n, k1) distances, indices nn.kneighbors(X) if include_self: knn_idx indices # 有些人习惯把自身纳入邻居集合 else: knn_idx indices[:, 1:] # 去掉自身 # 构造one-hot近邻矩阵 indicator np.zeros((n, n), dtypenp.float32) for i in range(n): indicator[i, knn_idx[i]] 1.0 # SNN indicator indicator.T # indicator[i] 和 indicator[j] 的内积 共同近邻数 snn indicator indicator.T # 对角线处理自身与自身的交集理论上等于k如果不含自身 np.fill_diagonal(snn, k) return knn_idx, snn这段代码用向量化矩阵乘法代替逐对交集计算效率高很多。knn_idx用于后续调试snn就是我们要的相似度矩阵。3.3 加入“互近邻”约束如果要严格遵循Jarvis-Patrick的思路需要在SNN矩阵基础上再套一个互近邻的壳。判断条件很简单点i必须出现在点j的k近邻列表中同时点j必须出现在点i的最近邻列表中否则相似度直接清零。def apply_mutual_constraint(knn_idx, snn): 仅保留互相在对方k近邻列表中的点对相似度。 n knn_idx.shape[0] mutual np.zeros((n, n), dtypebool) for i in range(n): # i的近邻集合 nbrs_i set(knn_idx[i]) for j in nbrs_i: if i in set(knn_idx[j]): mutual[i, j] True mutual[j, i] True # 非互近邻的点对相似度归零 snn_constrained snn * mutual.astype(np.float32) return snn_constrained加了这一步之后原本一些“单方面认识”的虚假连接会被过滤掉。实际使用时你会发现聚类结果更干净脱离密集区域的孤立点几乎不与任何簇产生连接。3.4 在SNN矩阵上做聚类拿到SNN相似度矩阵后最简单的聚类方式是Jarvis-Patrick聚类构建一个无向图两个点之间有边当且仅当它们的SNN相似度大于等于阈值eps然后提取连通分量作为簇。from scipy.sparse import csr_matrix from scipy.sparse.csgraph import connected_components def snn_clustering(snn, eps5): 基于SNN相似度矩阵做连通分量聚类。 eps: 共享近邻数阈值只有SNN eps的点对才会被连接。 adj (snn eps).astype(np.int32) # 邻接矩阵对角线置0不把自身当环路 np.fill_diagonal(adj, 0) graph csr_matrix(adj) n_components, labels connected_components(csgraphgraph, directedFalse) return labels运行一下看看效果。k 15 knn_idx, snn compute_knn_and_snn(X, kk) snn_constrained apply_mutual_constraint(knn_idx, snn) labels snn_clustering(snn_constrained, eps6) # 可视化 plt.figure(figsize(8, 6)) plt.scatter(X[:, 0], X[:, 1], clabels, cmaptab10, s8) plt.title(fSNN聚类结果 (k{k}, eps6)) plt.show()我跑出来的结果是环形簇被完整保留内部致密簇也被单独识别噪声点大多被标记为孤立簇label为-1或在同一个极小的孤立连通分量中。整个聚类过程中我没有预设簇的数量不需要提供半径参数也不需要指定簇的密度均值。这就是SNN聚类最舒服的地方。3.5 与DBSCAN、KMeans的对比实验为了让对比公平我用相同的数据集跑一遍DBSCAN和KMeans参数各调一版最合适的。from sklearn.cluster import DBSCAN, KMeans # DBSCAN db DBSCAN(eps0.18, min_samples10).fit(X) db_labels db.labels_ # KMeans强行设3类 km KMeans(n_clusters3, n_init10, random_state42).fit(X) km_labels km.labels_ # 可视化对比 fig, axes plt.subplots(1, 3, figsize(15, 5)) for ax, labels_plot, title_plot in zip( axes, [db_labels, km_labels, labels], [DBSCAN, KMeans, SNN聚类] ): ax.scatter(X[:, 0], X[:, 1], clabels_plot, cmaptab10, s8) ax.set_title(title_plot) plt.tight_layout() plt.show()DBSCAN在这个数据集上会非常挣扎eps调小环形簇会断开稀疏区域全是噪声eps调大致密簇被噪声完全吞并。KMeans更不用说了面对环形簇天然无解。SNN聚类在这种非凸、多密度、带噪的场景中展现出明显的稳定优势。4. 参数不调好SNN也会翻车k和阈值的选择经验SNN不是免调参的银弹它的两个核心参数k和eps共享近邻阈值直接影响聚类质量。很多人第一次用SNN效果不好多半就是参数没选对。4.1 k的物理含义与选择逻辑k决定“每个点认识几个朋友”。这个值既不能太大也不能太小。k太小比如3到5邻居名单过于随机很容易出现两个同簇点共享邻居数量不足、连边断裂的情况。尤其是稀疏区域k3时近邻集合里很可能是几个毫不相干的噪声点簇内反而不如跨簇的连接紧密。k太大比如超过50邻居名单扩大到很远范围把属于不同簇的点也拉进了名单里共享近邻数自然涨上去导致不同簇被错误粘连。极端情况下所有点的邻居集合高度重叠聚类结果退化成一个大团。我调参的经验是先将k设为样本量的对数级别比如n1000时k取15到25然后观察SNN矩阵的分布找“低相似度点对占比”相对平稳的区间。如果k增大时簇结构变化很剧烈说明数据本身噪音大需要配合互近邻约束使用。4.2 eps共享近邻阈值与簇粒度的关系eps决定了两个点需要有多少共同朋友才愿意被连接。eps设成1整个图几乎完全连通所有点都粘连eps设成k的一半以上边会变得稀疏簇会细化。如果eps接近k聚类只剩最核心的小团体边缘点全变孤立点。经验法则eps通常取k的30%到50%之间作为起始试探点。k20时eps可以先试6到10k30时eps试10到15。然后根据聚类结果微调观察簇数和噪声点比例的变化。这块没有银弹但做一次网格搜索也不是不行for eps_candidate in [4, 6, 8, 10, 12, 14]: labels_candidate snn_clustering(snn_constrained, epseps_candidate) n_clusters len(set(labels_candidate)) - (1 if -1 in labels_candidate else 0) noise_ratio (labels_candidate -1).mean() if -1 in labels_candidate else 0 print(feps{eps_candidate}, 簇数{n_clusters}, 噪声比{noise_ratio:.3f})观察曲线找到“簇数稳定、噪声比可控”的位置。如果存在一个参数区间内簇数几乎不变说明聚类结构稳固这个区间里的参数都可以用。4.3 k与eps必须联动调整k与eps不是独立的。k增加时每个点能共享出更多的邻居eps也要相应提高否则假连接会增多。我做过一组实验k从10加到30eps固定为5聚类产生的簇数直接暴跌一半还多原因是太大k带来的“虚假熟人网络”让不同簇被连成一片。看参数时务必把(k, eps)当作一个组合来看不要单独调。4.4 如果聚类效果不稳先检查数据预处理最后提醒一个容易忽略的点SNN是基于近邻排名计算的对距离度量的绝对尺度不敏感但对特征标准化很敏感。如果特征是量纲差异极大的比如一列年龄、一列收入必须在计算近邻前做标准化或归一化否则近邻集合会被量纲最大的特征主导。另一个建议类别特征尽量做one-hot或嵌入向量之后再用SNN直接用序号编码会让近邻计算失真。5. 踩坑记录SNN应用中最容易翻车的五个细节代码跑通只是开始真正落地时会有各种细节陷阱。这一节全是我自己趟过的坑写出来帮你省时间。5.1 邻居列表是否包含自身会导致结果完全不同很多库返回的最近邻索引中第一个元素是样本自身距离为0。如果你忘了把自身排除掉每个点都会跟自己是“共享近邻”整个SNN矩阵会系统性多出1个“自交近邻”轻则阈值需要额外调整重则对角线数值异常影响后续谱聚类或连通分量计算。 所以我在代码里强制用indices[:, 1:]排除自身并且把对角线手动设为k。就这个小细节曾经让我多调了一晚上参数。5.2 SNN矩阵的计算复杂度不是闹着玩的朴素实现两两求交集复杂度是O(n^2 * k)n上一万就非常痛苦。即使向量化使用矩阵乘法SNN矩阵本身是n×n的稠密矩阵n10万时直接内存爆炸。经验做法是用KD树或Ball Tree加速近邻搜索用分块矩阵乘法计算SNN避免一次性生成全部指示矩阵聚类时使用稀疏图表示只保留SNN大于阈值的边。 如果你处理的是百万级数据SNN全矩阵的思路基本不现实需要考虑近似近邻算法或者只对局部候选点对计算SNN。5.3 “互近邻约束”在不同数据稠密度下的双面性互近邻约束能过滤很多假连接但也可能带来问题如果一个点恰好处于两个簇的交界处它可能只被一边认作近邻另一边不认识它那它就无法作为“桥梁”连接两边的邻居。高密度簇之间靠一些边界点连接时强上互近邻约束可能把簇切得太碎。所以互近邻约束不是必选项它是“净化连接”和“保留桥梁”之间的权衡。当你发现聚类结果碎片化严重时可以试试去掉约束只靠提升eps来控制连接强度。5.4 用SNN做异常检测时注意“孤儿簇”的判定基于连通分量的SNN聚类天然会把孤立的点自成一个分量。但这些“孤点”并不全是异常点也可能是小簇。比如只有两三个点的一个小团体它们互相之间共享邻居很多内部边很密。若你直接按连通分量分量来当异常会漏掉这种“小团伙”。我通常的做法是加一个过滤条件连通分量中节点数少于min_cluster_size的才判定为异常点或微小簇。这个参数跟DBSCAN的min_samples含义类似能帮你区分真正的噪声和有价值的小簇。5.5 高维稀疏场景下距离度量要先“对路”SNN本身不关心底层距离度量但它依赖的“最近邻”质量直接受底层度量影响。在高维稀疏数据如One-Hot编码后的用户行为向量中欧氏距离经常失效曼哈顿距离略好一点余弦距离往往最优。所以不要一上来就用默认欧式距离先自己实验几种距离度量看近邻列表里是否出现了合理的同簇点再定最终配置。6. 延伸场景SNN从聚类走向更多应用SNN的用法绝不止聚类。理解它的核心价值——“用局部相对关系衡量全局相似度”——你会发现它几乎可以嵌入任何需要相似度计算的地方。6.1 高维数据的异常检测传统异常检测如孤立森林、LOF在高维数据中经常因为距离集中现象失灵。但SNN提供了另一种视角一个点如果可以跟其它点共享大量近邻它是正常点如果它的整个邻居名单都跟任何别的点没有交集那它大概率是异常点。我处理过一批用户点击序列数据特征维度上千直接跑LOF总会出现误报改成“SNN相似度 阈值判异”之后误报率降了不少。核心原因是SNN天然对局部密度做了自适应不会因为某个区域点稀疏就直接判异常。6.2 推荐系统中的相似用户发现协同过滤推荐的一个核心步骤是计算用户与用户的相似度。传统皮尔逊相关和余弦相似度只考虑共同打分项冷启动用户经常算不出有效结果。改用SNN后先找到每个用户的k近邻这里的“近邻”可以用行为向量余弦距离定义然后通过共享近邻数挖掘潜在相似用户。好处是即使两个用户没有直接共同打分项只要它们周围的行为模式高度相似依然能建立起关联。这在冷启动场景中比传统方法更有弹性。6.3 基因表达谱与生物信息学应用生物信息里的单细胞RNA测序数据维度动辄两万起步且包含大量dropout噪声很多基因表达量为0。大量论文证明SNN在该类数据上做聚类比直接计算基因表达谱距离稳定得多因为SNN关注的是“哪些细胞最像哪些细胞”的相对关系而不是绝对表达量差异。做这类任务时建议k设得大一点比如25到50因为单细胞数据的噪声比例高需要足够大的邻居集合来平滑噪声影响。6.4 大规模工程落地时的降维与近邻搜索思路如果数据量实在太大直接算全量SNN矩阵不现实可以换一种思路先做ANN近邻检索如HNSW、FAISS找出每个点的近似k近邻然后只对“有边连接”的点对计算SNN。这样SKU数量在百万级时也能跑通因为邻接矩阵是稀疏的。聚类时同样用稀疏图上的连通分量或标签传播即可不必依赖全量的相似度矩阵。我经手过的一个商品向量去重项目就是用FAISS找近邻、再按SNN阈值做连通过滤把千万级商品向量压缩到了百万级去重集合效果和性能都可接受。6.5 多模态特征的统一相似度框架另一个有意思的方向是把SNN用到多模态特征融合上。比如用户既有文本向量、又有图像向量和行为特征传统做法是拼接后算距离但量纲和分布完全不同的特征拼在一起效果很难保证。而SNN可以在每种模态上分别计算近邻集合再对两种模态的邻居交集做加权求和。只要每个模态内部的近邻关系是可靠的跨模态的相似度就能通过“共同认识的人”建立起来。这种思路在多模态搜广推项目里值得试一下。7. 一份可以直接用的生产级实现从相似度到聚类的完整封装最后我把上文的代码整合成一个相对完整的模块方便你直接复制到项目里用。同时补上了稀疏化处理和批量计算的选项让小数据集上的实验代码能平滑过渡到中等规模数据。import numpy as np from sklearn.neighbors import NearestNeighbors from scipy.sparse import csr_matrix from scipy.sparse.csgraph import connected_components class SNNCluster: 共享最近邻相似度聚类器。 参数: k: 近邻数量 eps: 共享近邻阈值建议为k的30%~50% mutual: 是否使用互近邻约束 metric: 计算近邻时使用的距离度量 def __init__(self, k15, eps6, mutualTrue, metriceuclidean): self.k k self.eps eps self.mutual mutual self.metric metric def fit_predict(self, X): n X.shape[0] # 1. 计算k近邻 nn NearestNeighbors(n_neighborsself.k 1, metricself.metric) nn.fit(X) distances, indices nn.kneighbors(X) knn_idx indices[:, 1:] # 排除自身 # 2. 构建指示矩阵 indicator np.zeros((n, n), dtypenp.float32) for i in range(n): indicator[i, knn_idx[i]] 1.0 snn indicator indicator.T np.fill_diagonal(snn, self.k) # 3. 可选互近邻约束 if self.mutual: mutual_mask np.zeros((n, n), dtypebool) for i in range(n): nbrs_i set(knn_idx[i]) for j in nbrs_i: if i in set(knn_idx[j]): mutual_mask[i, j] True mutual_mask[j, i] True snn snn * mutual_mask.astype(np.float32) # 4. 阈值化并提取连通分量 adj (snn self.eps).astype(np.int32) np.fill_diagonal(adj, 0) graph csr_matrix(adj) _, labels connected_components(csgraphgraph, directedFalse) return labels, snn这部分代码没有做过度优化适合3000点以内的数据直接使用。更大规模时把indicator矩阵换成稀疏矩阵或分块计算即可。有两个生产细节值得注意 第一distance变量我在类里没有使用但调试时可以输出看下近邻距离分布判断数据局部密度差异是否过剧烈。 第二connected_components返回的label编号是按连通分量的先后顺序编号的不代表簇的语义顺序。如果下游需要稳定簇编号建议对聚类结果再做一次排序映射把最大的簇编号固定为0。拿前文的数据跑一下效果完全一致。你换成自己的数据时唯一需要的操作就是调k和eps。# 使用示例 from sklearn.datasets import make_blobs X_demo, _ make_blobs(n_samples800, centers4, cluster_std0.8, random_state42) model SNNCluster(k20, eps8, mutualTrue, metriceuclidean) labels, snn_matrix model.fit_predict(X_demo)调k和eps的过程中我的习惯是先把k定为经验区间25到40然后画一张eps-簇数曲线图找稳定平台再把k上下浮动20%做敏感性测试。如果簇结构在参数小幅变化下保持稳定那这套结果基本可以放心用。这个内容后面还可以继续扩展的方向把SNN矩阵接到谱聚类上替代原始特征空间重构拉普拉斯矩阵或者把近邻排名变成可学习的注意力权重做端到端的相似度学习。但从经典算法出发、先把基础用扎实永远是性价比更高的起点。