基于整体和局部相似性的序列聚类算法

被引：16

作者：

戴东波

汤春蕾

熊赟

机构：

[1] 复旦大学计算机科学技术学院

来源：

软件学报 | 2010年 / 21卷 / 04期

关键词：

序列数据; 相似性; 聚类;

D O I：

暂无

中图分类号：

TP311.13 [];

学科分类号：

1201 ;

摘要：

现有的很多序列聚类算法是基于"局部特征可以表征整个序列"的假设来进行的,即不区分实际应用中序列的整体相似性和局部相似性.这对存在保守子模式的序列,如DNA和蛋白质序列是适用的,但对一些注重整体序列相似性的应用领域,如:在交易数据库中用户购买行为的比较,时间序列数据中全局模式的匹配等,由于难以产生频繁子模式,用基于全局相似性的度量方法进行聚类显得更为合理.此外,在基于局部相似性的序列聚类算法中,选取的局部子模式表征序列的能力也有待进一步提高.由此,针对不同应用领域,分别提出基于整体相似性的序列聚类算法GSClu和基于局部相似性的序列聚类算法LSClu.GSClu和LSClu分别利用带剪枝策略的二分k均值算法和基于有gap约束的强区分度子模式方法对各自领域的序列数据进行聚类.实验采用交易序列数据和蛋白质序列数据,实验结果表明,GSClu和LSClu对各自领域的序列数据具有较快的处理速度和良好的聚类质量.

引用

页码：702 / 717

页数：16

共 7 条

[1] DNA序列数据挖掘技术
朱扬勇
熊赟
[J]. 软件学报, 2007, (11) : 2766 - 2781
[2] Clustering DNA sequences by feature vectors
Liu, Libin
Ho, Yee-kin
Yau, Stephen
[J]. MOLECULAR PHYLOGENETICS AND EVOLUTION, 2006, 41 (01) : 64 - 69
[3] SWORDS: A statistical tool for analysing large DNA sequences[J] . Probal Chaudhuri,Sandip Das.Journal of Biosciences . 2002 (1)
[4] Statistical analysis of large DNA sequences using distribution of DNA words
Chaudhuri, P
Das, S
[J]. CURRENT SCIENCE, 2001, 80 (09): : 1161 - 1166
[5] The power of amnesia: Learning probabilistic automata with variable memory length[J] . Dana Ron,Yoram Singer,Naftali Tishby.Machine Learning . 1997 (2)
[6] The String-to-String Correction Problem[J] . Robert A. Wagner,Michael J. Fischer.Journal of the ACM (JACM) . 1974 (1)
[7] Introduction to data mining .2 Tan PN,Steinbach M,Kumar V. Addison-Wesley . 2005

← 1 →