基于Python与Levenshtein distance的序列聚类算法选型咨询
适配预计算Levenshtein距离矩阵的序列聚类可选方案
当前已完成序列两两Levenshtein距离计算、生成完整距离矩阵,同时需要规避Affinity Propagation收敛不稳定的问题,以下算法均支持直接输入预计算距离矩阵,无迭代振荡、收敛不可控的问题:
- 层次凝聚聚类(Agglomerative Clustering)
调用scikit-learn的AgglomerativeClustering时,将affinity参数设置为precomputed即可传入距离矩阵。算法属于确定性的自底向上合并流程,不存在收敛波动,可灵活选择single/average/complete三类合并准则适配不同的序列相似性判断逻辑,还可通过输出的树状聚类图手动选择合理的簇切割点,不需要提前强制指定簇数。 - DBSCAN
scikit-learn内置的密度聚类算法,将metric参数设置为precomputed即可直接使用距离矩阵输入。算法无迭代收敛过程,不需要提前指定簇数,可自动识别数据集中的离群异常序列(比如和其余序列编辑距离都极高的离群值),将其标记为噪声而非硬归入某个簇。调整参数时可先统计距离矩阵的数值分位数,直接用分位值作为邻域半径eps的参考值,减少参数调试成本。 - K-Medoids(PAM算法)
天生适配任意预计算距离的聚类算法,不要求序列具备欧氏空间的几何性质,相比仅支持欧氏距离的K-Means适配性更强。算法迭代过程完全确定,不存在振荡不收敛的问题,簇中心直接选取距离簇内所有样本总和最小的真实序列,可解释性比基于虚拟质心的聚类更高。 - 谱聚类(Spectral Clustering)
支持预计算的亲和矩阵输入,需要注意谱聚类要求输入矩阵为相似度矩阵(值越高代表样本越相似),因此需要先将现有Levenshtein距离矩阵通过高斯核转换为亲和度矩阵,转换方式为S = np.exp(-gamma * (D ** 2)),转换完成后将affinity参数设为precomputed即可运行,对形状复杂的簇结构识别效果较好,收敛过程稳定。
实操注意事项
- 所有要求预计算输入的接口,需保证传入的距离矩阵满足对称、非负、对角元为0的合法距离要求,不要把相似度值直接当作距离传入,否则结果会出现严重偏差。
- 如果原始Levenshtein距离未做归一化,调整聚类参数时务必先遍历距离矩阵的数值分布,不要直接套用固定的阈值经验值。
- 不建议直接使用原生K-Means处理该场景:K-Means仅支持欧氏距离,无法直接消费Levenshtein距离矩阵,若要使用需额外通过MDS等方法将距离矩阵转换为低维欧氏坐标,反而增加额外步骤与误差。
内容的提问来源于stack exchange,提问作者mantunes
相关产品推荐
相关产品推荐

