基于编辑距离的序列聚类算法的优化

来源：计算机技术与发展杂志2018年第03期北京时间：

作者：孙启航;杨鹤标

摘要：现有的很多序列聚类算法都是基于“局部特征可以代表整个序列”的假设,在实际应用中不对序列局部相似性和全局相似性加以区分,这对于存在子模式的序列聚类是适用的,如基因序列和蛋白质序列。 但是对于不存在子模式的序列,如对临床行为序列、用户购买行为序列进行聚类时,用基于全局相似性度量的聚类方法更为恰当。 针对不存在子模式的序列聚类的需要,采用编辑距离作为序列相似性计算方法,在二分 K 均值算法的基础上,提出了利用编辑距离上下界以及通过前缀子序列进行剪枝的序列聚类算法 PSClu。 该算法能有效过滤编辑距离的计算量。 实验结果表明,PSClu 能有效减少编辑距离的直接计算,具有较好的聚类效率和聚类质量。

关键词：关键词:序列聚类;编辑距离;二分 K 均值;序列相似性