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

• 作者: 孙启航 杨鹤标
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 序列聚类 编辑距离 二分K均值 序列相似性
• 年，卷（期）: 2018,（3）
• 所属期刊栏目: 智能、算法、系统工程
• 页码范围: 109-113
• 页数: 5页
• 分类号: TP311
• 字数: 6216字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2018.03.023

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨鹤标	江苏大学计算机科学与通信工程学院	78	637	13.0	22.0
2	孙启航	江苏大学计算机科学与通信工程学院	3	8	2.0	2.0